algorithm - ポラード ロー因数分解法の実装

Question

ポラード ロー因数分解法を使用して数値を因数分解するたびに、ポラード ロー因数分解の前にその素数をチェックする必要がありますか? はいの場合、任意の数を因数分解するたびに、Miller Rabin の素数性テストまたは任意の素数性テストを実装する必要がありますが、強力な疑似素数を処理する必要があります。複雑ではありませんか? これを処理する簡単で高速な方法はありますか? (私はこれらのテストを 10 桁までの数字に使用しています)

Answer 1

はい、ポラードローを適用する前に、因数分解している数値が複合であることを確認する必要があります。素数の場合、素数は常に他のすべての数と互いに素であるため、gcdステップは常に1を返し、ポラードローは結果なしで永久に実行されます。

10桁までの数字の場合、ポラードローは必要ありません。必要な素数は100000未満であり、素数は9592しかないため、単純な試行割り算は十分に高速です。