根据费马的小定理解释检查素性的代码

Question

我发现了一些基于Fermat的小定理声称检查素性的Python代码:

def CheckIfProbablyPrime(x):
    return (2 << x - 2) % x == 1

我的问题:

1. 它是如何工作的？
2. 它与费马小定理的关系是什么？
3. 这种方法有多准确？
4. 如果它不准确,使用它有什么好处？

我在这里找到了.

Answer 1

1.它是如何工作的？

费马的小定理说如果数字x是素数,那么对于任何整数a:

如果我们将两边除以a,那么我们可以重新编写等式如下:

我将试图证明这是如何工作的(你的第一个问题),因为在这个维基页面和一些谷歌搜索中有很多好的证明(比我能提供的好).

2.代码与定理之间的关系

所以,你发布的功能检查是否(2 << x - 2) % x == 1.

首先,(2 << x-2)与写作2**(x-1)或数学形式相同:

这是因为<<是逻辑左移操作,这是更好的解释这里.位移和乘以2的关系之间的关系特定于数字在计算机上的表示方式(二进制),但这一切都归结为

我可以从两边的指数中减去1,这给出了

现在,我们从上面知道任何数字a,

那么我们说a = 2.这给了我们

哎呀,那是一样的2 << (x-2)!那么我们可以写:

这导致了最终的关系:

现在,mod的数学版本看起来很奇怪,但我们可以编写如下的等效代码:

(2 << x - 2) % x == 1

这就是关系.

3.方法的准确性

因此,我认为"准确性"在这里是一个不好的术语,因为费马的小定理对于所有素数都是正确的.然而,这并不能意味着它是真的还是假的所有号码-这是说,如果我有一些数字我,我不知道如果我是总理,使用费马小关系只会告诉我,如果它是绝对不是素.如果费马的小关系是真的,那么我就不能成为素数.这些数字称为伪次数,或者更具体地说,在这种情况下称为Fermat Pseudoprime数.

如果这种事情听起来很有意思,请看看Carmichael的数字 AKA the Absolute Fermat Pseudoprimes,它在任何基础上通过Fermat测试,但不是素数.在我们的例子中,我们遇到了数字,这些数字在基数2中通过,但费马的小定理可能不适用于其他基数中的这些数字 - 卡迈克尔数字通过了所有基数的测试x.

在Carmichael的wiki页面上讨论了它们在自然数范围内的分布 - 它们以你所看到的范围的大小呈指数级增长,尽管指数小于1(约1/3) ).因此,如果你在大范围内搜索质数,那么你将会出现指数级更多的卡迈克尔数,这对于这种方法实际上是误报CheckIfProbablyPrime.这可能没问题,这取决于您的输入以及您对误报的关注程度.

4.为什么这有用？

简而言之,这是一种优化.

使用这样的东西的主要原因是加快搜索素数.那是因为实际检查数字是否为素数是昂贵的 - 即超过O(1)运行时间.可行,但仍比O(1)时间更昂贵.因此,如果我们可以避免对某些数字进行实际检查,我们将能够投入更多时间来检查实际候选人.因为Fermat的小关系只会说一个数字可能是素数(如果数字是素数就永远不会说不),并且可以在O(1)时间内检查,我们可以把它扔到一个is_prime循环中忽略一个公平数量.所以,我们可以加快速度.

有很多像这样的素数检查,你可以在这里找到一些编码的素数检查器

最后的说明

关于此优化的一个令人困惑的事情是它使用位移运算符<<而不是取幂运算符**.这是因为位移是计算机可以执行的最快的操作之一,而取幂则会慢一些.在许多情况下,它并不总是最佳的优化,因为大多数现代语言都知道如何用更优化的操作替换我们编写的内容.但是,这是我的冒险,为什么这个代码的作者使用位移而不是2**(x-1).

编辑:正如MarkDickinson指出的那样,取一个数字的指数然后明确地修改它并不是最好的方法.这是一种称为模幂运算的东西,并且存在比我们编写它的方式更快的算法.Python的内置pow实际上实现了这些算法之一,并且为mod提供了一个可选的第三个参数.所以我们可以编写这个函数的最终版本:

def CheckIfProbablyPrime(x):
    return pow(2, x-1, x) == 1

这不仅比可疑的比特换档更易读,而且速度更快.你知道他们说了什么.