解释基于费马小定理检查素性的代码
Explain a code to check primality based on Fermat's little theorem
我发现一些 Python 代码声称根据 Fermat's little theorem:
检查素数
def CheckIfProbablyPrime(x):
return (2 << x - 2) % x == 1
我的问题：
- 它是如何工作的？
- 它与费马小定理有什么关系？
- 这种方法的准确性如何？
- 如果不准确，使用它有什么好处？
我找到了here。
我相信，您示例中的代码是不正确的，因为二进制左移运算符不等同于费马小定理中使用的数字的幂。以二为底，二进制左移等于 x + 1 的幂，这在 Fermat 的小格式版本中不使用。
相反，使用 ** 作为 Python 中整数的幂。
def CheckIfProbablyPrime(x):
return (2 ** x - 2) % x == 0
" p − a 是 p 的整数倍" 因此对于素数，根据定理，2 的 x - 2 次方除以 x 的结果将剩下 0（模 '%' 检查剩余数分割后结束。
对于 x - 1 版本，
def CheckIfProbablyPrime(a, x):
return (a ** (x-1) - 1) % x == 0
这两种变体对于素数都应该是正确的，因为它们代表了 Python
中的费马小定理
1。它是如何工作的？
Fermat's little theorem 说如果一个数 x 是素数，那么对于任何整数 a:
两边除以a，则re-write可以得到如下等式：
我打算证明 这是如何工作的（你的第一个问题），因为在 this wiki page 上有很多很好的证据（比我能提供的更好）在一些 Google 搜索下。
2。代码与定理的关系
因此，您发布的函数检查是否 (2 << x - 2) % x == 1。
首先，(2 << x-2) 与写 2**(x-1) 或 math-form:
相同
那是因为 << 是 logical left-shift operator, which is explained better here。 bit-shifting 和乘以 2 的幂之间的关系特定于数字在计算机上的表示方式（二进制），但它都归结为
我可以从两边的指数中减去 1，得到
现在，我们从上面知道 对于任何数字 a，
那么假设a = 2。这给了我们
好吧，这和 2 << (x-2) 一样！那么我们可以写：
这导致最终关系：
现在，mod 的数学版本看起来有点奇怪，但我们可以编写如下等效代码：
(2 << x - 2) % x == 1
这就是关系。
3。方法的准确度
所以，我认为 "accuracy" 在这里是一个糟糕的术语，因为费马小定理对所有素数绝对成立。然而，这确实 not 意味着它对所有数字都是真或假——也就是说，如果我有一些数字 i，并且我我不确定 i 是否是素数，使用 Fermat 的小关系只会告诉我它是否绝对不是素数。如果费马的小关系为真，则 i 不可能是素数。这些类型的数字称为 pseudoprime numbers, or more specifically in this case Fermat Pseudoprime 数字。
如果这类事情听起来很有趣，请看一看 Carmichael numbers 又名绝对费马伪素数，它在任何基数上都通过了费马测试但不是素数。在我们的例子中，我们将 运行 转化为以 2 为基数的数字，但费马小定理可能不适用于其他基数的这些数字——卡迈克尔数通过了与 x 互质的所有基数的测试。
在 Carmichael 的 wiki 页面上讨论了它们在自然数范围内的分布——它们随您正在查看的范围的大小呈指数增长，尽管指数小于 1 （约 1/3）。因此，如果您在大范围内搜索素数，您将 运行 成指数级增长的 Carmichael 数，这实际上是此方法 CheckIfProbablyPrime 的误报。这可能没问题，具体取决于您的输入以及您对 运行误报的关心程度。
4。为什么这有用？
简而言之，这是一个优化。
使用这样的东西的主要原因是为了加快素数的搜索速度。那是因为实际检查一个数字是否为质数是昂贵的——即超过 O(1) 运行ning 时间。可行，但仍然比 O(1) 时间更昂贵。因此，如果我们可以避免对某些数字进行实际检查，我们将能够投入更多时间来检查实际候选人。由于费马小关系只会在一个数可能是质数时说是（如果数是质数它永远不会说不），并且可以在 O(1) 时间内检查它，我们可以将它扔进 is_prime循环忽略相当数量的数字。所以，我们可以加快速度。
像这样的素数检查有很多，你可以找到一些编码的素数检查器here
最后的笔记
关于此优化的一个令人困惑的事情是它使用位移运算符 << 而不是求幂运算符 **。这是因为位移是您的计算机可以执行的最快的操作之一，而取幂则慢一些。在很多情况下是 not always the best optimization，因为大多数 modern 语言都知道如何用更优化的操作替换我们编写的东西。但是，关于 为什么 这段代码的作者使用位移位而不是 2**(x-1).
这就是我的冒险
编辑：正如 MarkDickinson 指出的那样，取一个数的指数然后 mod 明确地计算它并不是最好的方法。这是一个叫做 modular exponentiation, and there exist algorithms which can do it faster than the way we've written it. Python's builtin pow 的东西实际上实现了这些算法之一，并且将可选的第三个参数传递给 mod by。所以我们可以编写这个函数的最终版本：
def CheckIfProbablyPrime(x):
return pow(2, x-1, x) == 1
这不仅更具可读性，而且 比令人困惑的 bit-shift 废话 更快。 You know what they say.
我发现一些 Python 代码声称根据 Fermat's little theorem:
检查素数def CheckIfProbablyPrime(x):
return (2 << x - 2) % x == 1
我的问题：
- 它是如何工作的？
- 它与费马小定理有什么关系？
- 这种方法的准确性如何？
- 如果不准确，使用它有什么好处？
我找到了here。
我相信，您示例中的代码是不正确的，因为二进制左移运算符不等同于费马小定理中使用的数字的幂。以二为底，二进制左移等于 x + 1 的幂，这在 Fermat 的小格式版本中不使用。
相反，使用 ** 作为 Python 中整数的幂。
def CheckIfProbablyPrime(x):
return (2 ** x - 2) % x == 0
" p − a 是 p 的整数倍" 因此对于素数，根据定理，2 的 x - 2 次方除以 x 的结果将剩下 0（模 '%' 检查剩余数分割后结束。
对于 x - 1 版本，
def CheckIfProbablyPrime(a, x):
return (a ** (x-1) - 1) % x == 0
这两种变体对于素数都应该是正确的，因为它们代表了 Python
中的费马小定理1。它是如何工作的？
Fermat's little theorem 说如果一个数 x 是素数，那么对于任何整数 a:
两边除以a，则re-write可以得到如下等式：
我打算证明 这是如何工作的（你的第一个问题），因为在 this wiki page 上有很多很好的证据（比我能提供的更好）在一些 Google 搜索下。
2。代码与定理的关系
因此，您发布的函数检查是否 (2 << x - 2) % x == 1。
首先，(2 << x-2) 与写 2**(x-1) 或 math-form:
那是因为 << 是 logical left-shift operator, which is explained better here。 bit-shifting 和乘以 2 的幂之间的关系特定于数字在计算机上的表示方式（二进制），但它都归结为
我可以从两边的指数中减去 1，得到
现在，我们从上面知道 对于任何数字 a，
那么假设a = 2。这给了我们
好吧，这和 2 << (x-2) 一样！那么我们可以写：
这导致最终关系：
现在，mod 的数学版本看起来有点奇怪，但我们可以编写如下等效代码：
(2 << x - 2) % x == 1
这就是关系。
3。方法的准确度
所以，我认为 "accuracy" 在这里是一个糟糕的术语，因为费马小定理对所有素数绝对成立。然而，这确实 not 意味着它对所有数字都是真或假——也就是说，如果我有一些数字 i，并且我我不确定 i 是否是素数，使用 Fermat 的小关系只会告诉我它是否绝对不是素数。如果费马的小关系为真，则 i 不可能是素数。这些类型的数字称为 pseudoprime numbers, or more specifically in this case Fermat Pseudoprime 数字。
如果这类事情听起来很有趣，请看一看 Carmichael numbers 又名绝对费马伪素数，它在任何基数上都通过了费马测试但不是素数。在我们的例子中，我们将 运行 转化为以 2 为基数的数字，但费马小定理可能不适用于其他基数的这些数字——卡迈克尔数通过了与 x 互质的所有基数的测试。
在 Carmichael 的 wiki 页面上讨论了它们在自然数范围内的分布——它们随您正在查看的范围的大小呈指数增长，尽管指数小于 1 （约 1/3）。因此，如果您在大范围内搜索素数，您将 运行 成指数级增长的 Carmichael 数，这实际上是此方法 CheckIfProbablyPrime 的误报。这可能没问题，具体取决于您的输入以及您对 运行误报的关心程度。
4。为什么这有用？
简而言之，这是一个优化。
使用这样的东西的主要原因是为了加快素数的搜索速度。那是因为实际检查一个数字是否为质数是昂贵的——即超过 O(1) 运行ning 时间。可行，但仍然比 O(1) 时间更昂贵。因此，如果我们可以避免对某些数字进行实际检查，我们将能够投入更多时间来检查实际候选人。由于费马小关系只会在一个数可能是质数时说是（如果数是质数它永远不会说不），并且可以在 O(1) 时间内检查它，我们可以将它扔进 is_prime循环忽略相当数量的数字。所以，我们可以加快速度。
像这样的素数检查有很多，你可以找到一些编码的素数检查器here
最后的笔记
关于此优化的一个令人困惑的事情是它使用位移运算符 << 而不是求幂运算符 **。这是因为位移是您的计算机可以执行的最快的操作之一，而取幂则慢一些。在很多情况下是 not always the best optimization，因为大多数 modern 语言都知道如何用更优化的操作替换我们编写的东西。但是，关于 为什么 这段代码的作者使用位移位而不是 2**(x-1).
编辑：正如 MarkDickinson 指出的那样，取一个数的指数然后 mod 明确地计算它并不是最好的方法。这是一个叫做 modular exponentiation, and there exist algorithms which can do it faster than the way we've written it. Python's builtin pow 的东西实际上实现了这些算法之一，并且将可选的第三个参数传递给 mod by。所以我们可以编写这个函数的最终版本：
def CheckIfProbablyPrime(x):
return pow(2, x-1, x) == 1
这不仅更具可读性，而且 比令人困惑的 bit-shift 废话 更快。 You know what they say.