26.1 factor: 素因数を表示する

factor は、素因数を表示する。

書式:

factor [number]…
factor option

number がコマンドラインで指定されていない場合、factor は標準入力から数値を読み込む。 このとき、改行、タブ、空白で区切って複数の数値を入力することができる。

factor コマンドで使えるオプションは、いくつもない。

‘--help’

簡単なヘルプメッセージを標準出力に表示し、それ以上の処理をせずに終了する。

‘--version’

プログラムのバージョンを標準出力に表示し、それ以上の処理をせずに終了する。

メルセンヌ素数の 8 番目と 9 番目の積を素因数に分解するには、2.2 GHz Athlon のシステムで、30 ミリセコンドの CPU 時間を要する。

M8=$(echo 2^31-1|bc)
M9=$(echo 2^61-1|bc)
n=$(echo "$M8 * $M9" | bc)
/usr/bin/time -f %U factor $n
4951760154835678088235319297: 2147483647 2305843009213693951
0.03

同様に、8 番目のフェルマー数、2^256+1 では、同じマシンで約 20 秒かかる。

大きな数の素因数分解は、そもそも大変な作業である。factor が使用している Pollard-Brent rho アルゴリズムは、比較的小さな因数を持つ数値に対してとりわけ効率がよい。 もし、小さな因数を持たない大きな数値 (たとえば、二つの大きな素数の積からなる数値) の素因数分解をなさりたいのなら、他の方法の方がずっとすぐれている。

factor が GNU MP を使用せずにビルドされている場合は、 単精度の算術しか利用できない。従って、大きな数値 (一般には 2^128 以上) には対応していない。単精度用のコードが使用しているアルゴリズムは、 比較的小さな数値を素因数に分解するためのものなのである。

終了ステータス 0 は成功を示し、0 以外の値は失敗を示す。

This document was generated on June 7, 2022 using texi2html 1.82.