0

Nは約1000で、K は非常に小さい (500 未満)。これらの数値の素数をテストしたいと思います。現在、私はベース 2 によるフェルマーの検定を使用しており、その前に小さな因子 (<10000) をチェックしています。

ただし、これは私の目的にはかなり遅いです。それより速いアルゴリズムはありますか？この特殊なフォームをどうにか悪用することはできますか?

また、2 つの数値が K のみ異なる場合、これら 2 つの数値をもう少し早くテストすることは可能でしょうか?

4

2 に答える 2

1

K の因数が 2 または 5 の場合、10^N + K は合成です。これにより、少数をすばやくテストできます。大きな素数はすべて、P mod 6 = 1 または 5 になります。これを使用して、可能な K 値の 2/3 を排除できます。ちょっとした作業で、多くの分割を避けるために 2 ～ 4 ホイールをセットアップできます。

increment <- either 2 or 4 as required
repeat
  K <- K + increment
  increment <- 6 - increment
  if (K mod 5 = 0) then 
    continue 
  endif
until (isPrime(10^N + K) or (K > 500))

大丈夫なら10,000までのファクタリングをお試しください。最初に 10,000 までの素数のリストを作成していますか? エラトステネスの篩を使用してリストを作成し、数字を読み取るだけです。

Fermat Test base 2 を実行するのは良いスタートです。多くの複合材料がかなり迅速に検出されます。

その後、確率論的 Miller-Rabin テストを実装し、数が合成されるのではなく、ハードウェアが故障する可能性が高くなるように十分な回数実行する必要があります。

于 2011-10-14T22:27:03.047 に答える
0
また、2 つの数値が K のみ異なる場合、これら 2 つの数値をもう少し早くテストすることは可能でしょうか?

[10 N +K 1 , 10 N +K 2 ]のような比較的短い間隔で素数を確認するには、エラトステネスのふるいを使用して、小さい数で割り切れるかどうかを確認します。

残りの最有力候補は、Miller-Rabin のような確率検定によってチェックできます。

于 2011-10-17T07:19:02.263 に答える