algorithm - 素数を 2 つの平方和として表現する最速のアルゴリズムは?

Question

素数より小さい 2 つの整数のすべての組み合わせをチェックするために 2 つのループを使用できますpが、非常に非効率的です。この問題にアプローチするためのより良いアルゴリズムはありますか? 何か案が？

どこでp mod 4 = 1。

ありがとう、

Answer 1

Hermite-Serretアルゴリズムを使用してみることができます。

また、この math.se ページでアルゴリズムの優れたリストを見つけることができます: https://math.stackexchange.com/questions/5877/effectively-finding-two-squares-which-sum-to-a-prime

特に、Robin Chapman の回答を参照してください: https://math.stackexchange.com/questions/5877/effectively-finding-two-squares-which-sum-to-a-prime/5883#5883

Answer 2

すべての組み合わせを検索する必要はありません。単純な単純な実装の大まかな概要は次のとおりです。

• 範囲 [1..trunc(sqrt(p))] 内の各整数 i を検討してください。
• sqrt(pi^2) を計算し、整数かどうかを確認します。もしそうなら、あなたは終わりです。
• そうでない場合は、次の i に進みます。

これはあなたのニーズに十分ですか？p が比較的小さい場合は問題なく動作しますが、暗号化で使用される大きな素数の場合は明らかに遅くなります。

Answer 3

フェルマーの 4n+1 の定理をもう一度読むことをお勧めします。

ソフトウェア エンジニアが仕事に適したツールを使用すれば、シンプルなソリューションが得られます。私の Mathematica 関数：

P[p_] := Reduce[-p + x^2 + y^2 == 0, {x, y}, Integers]

例:

1 または 2 (mod 4) である最初のいくつかの素数 p の解を見つけます。

P /@ {2, 5, 13, 17, 29, 37, 41, 53, 61}