18

このfactorコマンドは、指定された整数 NUMBER の素因数を出力します。

やってみたところ

factor 12345678912345678912

そのような大きな数であっても、ミル内で結果が得られます。

どのアルゴリズムを使用していますか?

4

3 に答える 3

17

Gnu coreutilsマニュアルは、Pollardのrhoアルゴリズムが使用されていることを通知します。

http://www.gnu.org/software/coreutils/manual/html_node/factor-invocation.html

于 2012-06-22T11:36:39.857 に答える
7

GNUファクターのソースの1つのバージョンの例を次に示します。

http://www.futuretg.com/FTHumanEvolutionCourse/Source/factor.c

これには、試行割り法とポラードローの両方のルーチンが含まれています。lg(n)^2試行除算を使用していくつかの小さな要因（最大で約4000、この場合は約4000）を見つけるかのようにクイックスキャンで私に見えます。次に、残っているものがおそらくプライムでない場合はポラードです。この場合、205432623008947それは私が4000について正しい場合です35129 * 5847949643。

あなたの例で2番目に大きい素因数は35129であり、最大の平方根は約76471です。したがって、試行割り算だけでも、約25,000人の候補者を試行するだけでよいため高速になります。

于 2012-06-22T11:34:30.783 に答える
1

ソースコードから：

アルゴリズム：

  1. 小さな素数テーブルを使用して試行除算を実行しますが、素数テーブルは語底を法とする逆数を格納するため、ハードウェア除算は行いません。(このコードの GMP バリアントは、事前に計算された逆数を使用しませんが、高速な割り切れるテストのために GMP に依存しています。)
  2. Miller-Rabin を使用してコンポジットを検出し、Lucas を使用して素数を検出して、分解されていない部分の性質を確認します。
  3. Pollard-Brent rho アルゴリズムを使用して残りの複合部品を因数分解するか、USE_SQUFOF が 1 に定義されている場合は、最初にそれを試してください。Miller-Rabin と Lucas を使用して、見つかった因子のステータスを再度確認します。

前者の方がはるかに高速なコードにつながるため、より馴染みのあるユークリッド ノルムではなく、除算でヘンゼル ノルムを使用することを好みます。Pollard-Brent rho コードと主要なテスト コードでは、すべての n 残基を語基数で乗算するというモンゴメリーのトリックを使用して、安価な Hensel 縮約 mod n を可能にします。

GMP コードはかなり遅いアルゴリズムを使用します。たとえば、2017 年頃の Intel Xeon Silver 4116 では、2^{127}-3 の因数分解に 2 ワード アルゴリズムで約 50 ミリ秒かかりますが、GMP コードでは約 750 ミリ秒かかります。

一般的に、factor快適に高速です。ただし、これは魔法ではありません。因数分解が非常に困難な数値を選択すると、劇的に遅くなります。

RSA 暗号化の基礎となるセキュリティは、2 つの大きな素数を因数分解することの難しさに基づいています。factorでは、大きな余素を使ってどれだけ頑張れるか見てみましょう。因数分解できる最大の数factorは 2 127 -1 (おそらく int64_t で内部的に表される) で、たまたま素数です。

$ factor $(bc <<< 2^127)
factor: ‘170141183460469231731687303715884105728’ is too large
$ factor $(bc <<< 2^127-1)
170141183460469231731687303715884105727: 170141183460469231731687303715884105727
$ factor $(bc <<< 2^127-2)
170141183460469231731687303715884105726: 2 3 3 3 7 7 19 43 73 127 337 5419 92737 649657 77158673929
$

2 127 -1 と 2 127 -2 はどちらもほとんどすぐに因数分解されます。2 127 -1 はすぐに素数であることがわかり、2 127 -2 の約数は比較的小さくなります。

もっと難しいことはどうですか？2 60のオーダーの 2 つのファクターの積は、どのファクターが機能するかのより高いオーダーに近づきます。では、2 60を超える次の 2 つの素数はどうでしょうか。

$ primes $(bc <<< 2^60) | head -2
1152921504606847009
1152921504606847067
$ bc <<< 1152921504606847009*1152921504606847067
1329227995784916015866073631529372603
$ time factor 1329227995784916015866073631529372603
1329227995784916015866073631529372603: 1152921504606847009 1152921504606847067

real    0m30.628s
user    0m30.578s
sys 0m0.004s
$

そのため、素因数のビット数が増えると、因数分解時間はさらに急速に増加します。

于 2021-02-09T19:01:29.477 に答える