检查14位数字是否为素数的最快算法是什么？

Question

我需要最快的程序来检查14位(或更大)数字的素数.我搜索了多个网站,但我不确定我发现的那些网站会使用与此相同的数字.

Answer 1

就主要测试而言,14位数字并不是很大.当数字具有一些特殊结构时,可能会有更快的专业测试(例如,如果它是梅森数),但一般来说,对该范围内数字的最快测试是

1. 通过一些小数字开始试验除法.如果你计划进行很多检查,那么值得列出n最小的素数,这样试验区只能用素数除以一次测试,只是避免测试除数(除了2)和3的倍数(除了3),够好了.什么"小"意味着解释,截止100到10000之间的选择似乎是合理的,许多(很少)分裂仍然很快完成,他们找到了绝大多数的复合数字.

2. 如果试验部门没有将数字确定为复合数(或者如果它实际上小于截止的平方数),则可以使用已知对您感兴趣的范围确定的快速概率素数测试之一在,通常的候选人是

   • Baillie/Pomerance/Selfridge/Wagstaff测试,对基数2的强大Fermat测试,然后测试为正方形和(强)Lucas测试.这不会产生低于2 ^64的误报,所以对于14-18位的数字来说这是肯定的.
   • 强大的Fermat测试已经确定了所考虑范围的一系列碱基.根据Chris Caldwell的主要页面,"如果n < 341,550,071,728,321是2个,3个,5个,7个,11个,13个和17个SPRP,则n是素数".

快速确定性的通用初级测试,即APR-CL,ECPP,AKS,速度稍慢,实施起来要困难得多.对于14位或更多位数的数字,它们应该已经超过了纯粹的试验分区,但是比偶然发生的已知正确范围的概率测试慢得多.

但是,根据您的使用情况,最好的方法也可以是筛选连续的数字范围(例如,如果您想要找到10 ¹⁴ -10 ⁹和10 ¹⁴之间的质数,筛子将比几亿快速个人主要测试).

Answer 2

正如丹尼尔·菲舍尔（Daniel Fischer）所指出的那样，对于素数测试，14位数字并不是特别大。这给您几个选择。首先是简单的审判部门：

function isPrime(n)
    d := 2
    while d * d <= n
        if n % d == 0
            return Composite
        d := d + 1
    return Prime

10 ^ 14的平方根是10 ^ 7，因此可能要花一点时间。使用原动机可以更快一些：

struct wheel(delta[0 .. len-1], len, cycle)

w := wheel([1,2,2,4,2,4,2,4,6,2,6], 11, 3)

function isPrime(n, w)
    d := 2; next := 0
    while d * d <= n
        if n % d == 0
            return Composite
        else
            d := d + w.delta[next]
            next := next + 1
            if next == w.len
                next := w.cycle
    return Prime

这样可以将幼稚的试验划分速度提高2到3倍，这可能足以满足您的需求。

更好的选择可能是Miller-Rabin伪素数测试仪。从一个强大的伪素数测试开始：

function isStrongPseudoprime(n, a)
    d := n - 1; s := 0
    while d is even
        d := d / 2; s := s + 1
    t := powerMod(a, d, n)
    if t == 1 return ProbablyPrime
    while s > 0
        if t == n - 1
            return ProbablyPrime
        t := (t * t) % n
        s := s - 1
    return DefinitelyComposite

每一个用于该函数返回的ProbablyPrime是一个见证到的素数Ñ：

function isPrime(n)
    for a in [2,3,5,7,11,13,17]
        if isStrongPseudoprime(n, a) == DefinitelyComposite
            return DefinitelyComposite
    return ProbablyPrime

正如Fischer所指出的，根据Gerhard Jaeschke 的论文，对于n <10 ^ 14，这是完全可靠的。如果你想测试更大的数字的素数，选择25名证人一个 随机的。该函数返回b ^ e（mod m）。如果您的语言不提供该功能，则可以像下面这样高效地进行计算：powerMod(b,e,m)

function powerMod(b, e, m)
    x := 1
    while e > 0
        if e % 2 == 1
            x := (b * x) % m
        b := (b * b) % m
        e := floor(e / 2)
    return x

如果您对此测试背后的数学感兴趣，我会在我的博客中适度推荐论文“ 使用质数编程”。