ポラード・ロー因数分解法は、関数ジェネレーターf（x）= x ^ 2-a（mod n）またはf（x）= x ^ 2 + a（mod n）を使用します。この関数（放物線）の選択は、重要性、または自明でない除数を見つけるためにnを法とする同じ合同クラスに属する数を識別または見つける必要があるため、任意の関数（3次、多項式、または線形）を使用できますか？
質問する
1506 次
1 に答える
2
Knuth Vol II（The Art Of Computer Programming-Seminumerical Algorithms）セクション4.5.4Knuthは次のように述べています。
さらに、f（y）mod pが集合{0、1、... p-1}からそれ自体へのランダムなマッピングとして動作する場合、演習3.1-12は、そのような最小のmの平均値がsqrtのオーダーになることを示しています。 （p）...第3章の理論から、線形多項式f（x）= ax+cは目的に対して十分にランダムではないことがわかります。次の最も単純なケースは2次式で、たとえばf（x）= x ^ 2 + 1です。この関数が十分にランダムであるかどうかはわかりませんが、知識の欠如はランダム性の仮説を支持する傾向があり、経験的テストはこれを示していますfは基本的に予測どおりに機能します
f（x）がsqrt（p）についての長さのサイクルを持っているという確率論は、特に、fがランダムに選択されるため、f（y）= f（z）となる2つの値yとzが存在する可能性があることを前提としています。 。ポラードローのローにはそのようなジャンクションが含まれており、サイクルには複数の線が含まれています。一次関数f（x）= ax + bの場合、gcd（a、p）= 1 mod p（pは素数である可能性が高い）f（y）= f（z）は、y = zmodpを意味します。したがって、そのようなジャンクションはありません。
http://www.agner.org/random/theory/chaosran.pdfを見ると、ランダム関数の予想されるサイクル長は状態サイズの平方根とほぼ同じですが、ランダムの予想されるサイクル長は全単射は、状態のサイズについてです。評価するときにのみランダム関数を生成することを考えると、関数が完全にランダムである場合、これまでに表示されたすべての値をランダムに再度選択してサイクルを見つけることができるため、サイクルを閉じる確率が高くなります。サイクルの長さを使用しますが、関数を反転可能にする必要がある場合、サイクルを閉じる唯一の方法は開始点を生成することです。これは、可能性がはるかに低いです。
于 2012-05-29T17:15:19.960 に答える