SICP，费马测试问题
SICP, Fermat Test Issue
SICP的Section 1.2.6描述了一个费马素数检验的算法如下（我自己的话）：
判断n是否为素数：
- 在
1和n-1之间选择一个随机整数a包括。
- 如果
a^n %n = a，那么n可能是素数。
我被卡住的部分是我们允许 a = 1 因为在这种情况下，无论我们选择 n（质数与否），测试总是会通过.
你是对的；没有理由选择 a = 1。也就是说，[1, n-1] 上的均匀分布与 [2, n-1] 上的均匀分布之间的统计距离是 O(1/n)，所以当n 很大（大到你不想做试验除法），实际影响很小（记住这已经是一个概率测试，所以很多其他选择 a 也行不通).
你 link 的文字实际上是说（强调我的）：
Fermat's Little Theorem: If n is a prime number and a is any positive integer less than n, then a raised to the nth power is congruent to a modulo n.
(Two numbers are said to be congruent modulo n if they both have the same remainder when divided by n. The remainder of a number a when divided by n is also referred to as the remainder of a modulo n, or simply as a modulo n.)
If n is not prime, then, in general, most of the numbers a < n will not satisfy the above relation. This leads to the following algorithm for testing primality: Given a number n, pick a random number a < n and compute the remainder of a^n modulo n. If the result is not equal to a, then n is certainly not prime. If it is a, then chances are good that n is prime. Now pick another random number a and test it with the same method. If it also satisfies the equation, then we can be even more confident that n is prime. By trying more and more values of a, we can increase our confidence in the result. This algorithm is known as the Fermat test.
到目前为止，它从来没有说要实际选择 1。不过它稍后会这样做。我认为这是一个错误，虽然不是一个大错误。即使给定值是正确的，您也应该测试多个值才能确定。
pseudocode on Wikipedia uses [2, n - 1] as the range for example. You should probably use this range in practice (although the Fermat test isn't really used in practice, since Miller-Rabin更好）。
Section 1.2.6描述了一个费马素数检验的算法如下（我自己的话）：
判断n是否为素数：
- 在
1和n-1之间选择一个随机整数a包括。 - 如果
a^n %n = a，那么n可能是素数。
我被卡住的部分是我们允许 a = 1 因为在这种情况下，无论我们选择 n（质数与否），测试总是会通过.
你是对的；没有理由选择 a = 1。也就是说，[1, n-1] 上的均匀分布与 [2, n-1] 上的均匀分布之间的统计距离是 O(1/n)，所以当n 很大（大到你不想做试验除法），实际影响很小（记住这已经是一个概率测试，所以很多其他选择 a 也行不通).
你 link 的文字实际上是说（强调我的）：
Fermat's Little Theorem: If n is a prime number and a is any positive integer less than n, then a raised to the nth power is congruent to a modulo n.
(Two numbers are said to be congruent modulo n if they both have the same remainder when divided by n. The remainder of a number a when divided by n is also referred to as the remainder of a modulo n, or simply as a modulo n.)
If n is not prime, then, in general, most of the numbers a < n will not satisfy the above relation. This leads to the following algorithm for testing primality: Given a number n, pick a random number a < n and compute the remainder of a^n modulo n. If the result is not equal to a, then n is certainly not prime. If it is a, then chances are good that n is prime. Now pick another random number a and test it with the same method. If it also satisfies the equation, then we can be even more confident that n is prime. By trying more and more values of a, we can increase our confidence in the result. This algorithm is known as the Fermat test.
到目前为止，它从来没有说要实际选择 1。不过它稍后会这样做。我认为这是一个错误，虽然不是一个大错误。即使给定值是正确的，您也应该测试多个值才能确定。
pseudocode on Wikipedia uses [2, n - 1] as the range for example. You should probably use this range in practice (although the Fermat test isn't really used in practice, since Miller-Rabin更好）。