0

我有一些 10 N + K 形式的数字，其中 N 约为 1000，而 K 非常小（低于 500）。我想测试这些数字的素数。目前我正在使用以 2 为底的费马检验，然后检查小因素（<10000）。

但是，就我的目的而言，这相当慢。有比这更快的算法吗？能以某种方式利用这种特殊形式吗？

另外，如果两个数字仅在 K 上有所不同，是否可以更快地测试这两个数字？

4

2 回答 2

1

如果 K 的因子为 2 或 5，则 10^N + K 是复合的。这允许快速测试少量。大素数都使得 P mod 6 = 1 或 5。您可以使用它来消除 2/3 的可能 K 值。通过一些工作，您可以设置一个 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 个素数的列表？使用 Eratosthenes 的筛子创建列表并读出数字。

运行 Fermat Test base 2 是一个好的开始，它可以相当快地找到很多复合材料。

之后，您需要实施概率 Miller-Rabin 测试，并运行它足够的次数，以便您的硬件更有可能发生故障，而不是数字是复合的。

于 2011-10-14T22:27:03.047 回答
0
另外，如果两个数字仅在 K 上有所不同，是否可以更快地测试这两个数字？

要检查像 [10 N +K 1 , 10 N +K 2 ]这样相对较小的区间内的素数，您可以使用 Erathostenes 的筛子来检查小数的可分性。

然后可以通过像 Miller-Rabin 这样的概率测试来检查剩余的主要候选人。

于 2011-10-17T07:19:02.263 回答