UNIX/Linuxの部屋 factorコマンドの使い方

TOP UNIX/Linuxの部屋 UNIX/Linuxコマンド一覧 用語集 新版 由来/読み方辞書 環境変数マニュアル Cシェル変数 システム設定ファイル システムコール・ライブラリ ネットワークプログラミングの基礎知識 クラウドサービス徹底比較・徹底解説




コマンド factor 数値の素因数分解・素数判定を行う。 このエントリーをはてなブックマークに追加

factor コマンドを使うと、数値の素因数分解・素数判定を行うことができる。
% factor 873231
873231: 3 291077
→ 873231 の素因数は 3×291077 である。よって素数ではない。
% factor 2305843009213693951
2305843009213693951: 2305843009213693951
→ 素因数が 1つしか表示されなかったため、素数である。

大きな数について現実的な時間内で素因数分解を行うことは非常に困難である。もしこれが簡単に行えるならば、公開鍵暗号方式である RSA 暗号方式は崩壊する。よって、factor コマンドで
% factor 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541
の答えがいつまで経っても返ってこなくても悲観してはいけない (ちなみにこれは RSA-129 の問題である)。

factor コマンドは少なくとも 1990年頃の 4.3BSD の頃には存在しており、結構歴史のあるコマンドである。*BSD 系はもちろん、AIX・Solaris 等の各種 UNIX でも使用できるようだ。Linux では GNU coreutils に含まれているため、事実上すべての Linux 系 OS で利用可能であろう。

古いバージョンのマニュアルには「factor が素因数分解できる最大値は 2147483647」などの記述があるが、2018年に FreeBSD・Linux で確認した限りでは多倍長整数ライブラリを使っているので、事実上桁数制限は存在しない。ちなみに FreeBSD の factor コマンド は OpenSSL の多倍長整数ライブラリを使っている。GNU Coreutils の factor コマンドは GNU の多倍長整数演算ライブラリである "GNU MP" を使っている。
>> Solaris10オンラインマニュアル(man) Solaris10 factor(1)
>> Linuxオンラインマニュアル(man) Linux factor(1)
>> Linuxオンラインマニュアル(man) Linux factor(6)