7

私は最近、ポラードの Rho アルゴリズムの並列化に関する論文を偶然見つけました。私の特定のアプリケーションを考えると、必要なレベルの数学に達していないという事実に加えて、この特定の並列化方法が私の特定のケースに役立つかどうか疑問に思っています。 .

非常に大きな数の 2 つの因数 (半素数) を見つけようとしています。この論文について私が理解できることはほとんどないが、この並列化は 2 つの非常に大きな因数ではなく、多数の小さな因数を含む数に対してうまく機能するというのが私の推測である。

これは本当ですか？この並列化を使用するか、他のものを使用する必要がありますか? ポラードのローを使用する必要がありますか、それとも別の因数分解アルゴリズムのより良い並列化がありますか?

4

2 に答える 2

6

ウィキペディアの記事には、具体的な例が 2 つ記載されています。

Number                Original code      Brent's modification
18446744073709551617  26 ms              5 ms
10023859281455311421  109 ms             31 ms

まず、プログラムでこれら 2 つを実行し、時間を調べます。それらがこれに類似している場合 (「ハード」な数値は 4 ～ 6 倍長く計算されます)、それを受け入れることができるか自問してください。または、単純な古典的な「総当たり」因数分解などの他のアルゴリズムを使用して、それらが与える時間を見てください。私は彼らが 1 に近いハードイージー ファクターを持っているかもしれないと思いますが、絶対時間は悪いので、それは単純なトレードオフです。

補足: もちろん、並列化はここで進むべき道です。ご存知だと思いますが、強調することが重要だと思います。また、Pollard-rho タイミングの間に別のアプローチがある場合にも役立ちます(例: Pollard-Rho 5-31 ミリ秒、別のアプローチ 15-17 ミリ秒)。この場合、2 つのアルゴリズムを別々のスレッドで実行することを検討してください。 「因数分解競争」。

アルゴリズムの実際の実装がまだない場合は、ここにPython の実装があります。

于 2011-09-26T10:00:48.763 に答える
5

大きな整数を因数分解する際の基本的な考え方は、それぞれに長所と短所があるさまざまな方法を使用することです。通常の計画は、素数による試行除算を1000または10000に開始し、その後に数百万のポラードローステップを実行することです。それはあなたに約12桁までの因数を与えるはずです。その時点で、いくつかのテストが順番に行われます。素数冪または累乗の数です（これらのプロパティには簡単なテストがあります）。それでも数を因数分解していない場合は、それが難しいことを知っているので、頑丈なツールが必要になります。有用な次のステップは、ポラードのp-1法であり、その後にその近縁の楕円曲線法が続きます。しばらくして、それが機能しない場合、残っている唯一の方法は、本質的に並列である二次ふるい法または数体ふるい法です。

あなたが尋ねた並列rho法は、今日広く使用されていません。あなたが示唆したように、ポラード・ローは大きなものよりも小さなものを見つけるのに適しています。セミプライムの場合、ポラードローよりもふるいの1つで並列サイクルを使用することをお勧めします。

詳細については、mersenneforum.orgのファクタリングフォーラムをお勧めします。

于 2011-09-26T13:10:59.357 に答える