This section describes two methods for checking the primality of an integer
n, one with order of growth Θ
(
本节介绍两种检验整数 n 是否为素数的方法：一种的增长的阶为 Θ(
n
√n
), and a
“probabilistic” algorithm with order of growth Θ
(
log
n
).
The exercises at the end of this section suggest programming projects based on
these algorithms.
Subheading: Searching for divisors
)，另一种是增长的阶为 Θ(log n) 的「概率性」算法。本节末尾的习题给出了基于这些算法的程序设计项目。小节标题：寻找因子
Since ancient times, mathematicians have been fascinated by problems concerning
prime numbers, and many people have worked on the problem of determining ways
to test if numbers are prime. One way to test if a number is prime is to find
the number’s divisors. The following program finds the smallest integral
divisor (greater than 1) of a given number n. It does this in a
straightforward way, by testing n for divisibility by successive integers
starting with 2.
自古以来，数学家们就对素数问题着迷，许多人致力于研究判断一个数是否为素数的方法。检验一个数是否为素数的一种方法是找出它的因子。下面的程序求给定整数 n 的最小整因子（大于 1）。它采用最直接的方式，从 2 开始依次用连续整数试除 n，检验其整除性。
We can test whether a number is prime as follows: n is prime if and only if
n is its own smallest divisor.
检验一个数是否为素数可以按如下方式进行：当且仅当 n 是自身最小因子时，n 为素数。
The end test for find-divisor is based on the fact that if n is not
prime it must have a divisor less than or equal to
n. This means that the algorithm need only test divisors
between 1 and n. Consequently, the number of steps required
to identify n as prime will have order of growth
Θ
(
`find-divisor` 的终止判断基于如下事实：若 n 不是素数，则它必有一个小于或等于 √n 的因子。这意味着算法只需检验 1 到 √n 之间的因子。因此，判定 n 为素数所需的步骤数的增长的阶为 Θ(
n
√n
).
Subheading: The Fermat test
)。
小节标题：费马检验
The Θ
(
log
n
) primality test is based on a result from
number theory known as Fermat’s Little Theorem.
Θ(log n) 的素性检验基于数论中一个称为费马小定理的结论。
Fermat’s Little Theorem: If n is a prime number and a is any
positive integer less than n, then a raised to the n
费马小定理：若 n 是素数，a 是小于 n 的任意正整数，则 a 的 n
th power is
congruent to a modulo n.
次方与 a 模 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
（若两个数除以 n 的余数相同，则称它们模 n 同余。数 a 除以 n 的余数也称为 a 被 n 除后的
modulo n, or simply as a
modulo n.)
余数，简称 a 模 n 的余数。）
If n is not prime, then, in general, most of the numbers a
若 n 不是素数，则一般来说，大多数小于 n 的整数 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，随机选取一个小于 n 的整数 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.
计算 a 的 n 次方模 n 的余数。若结果不等于 a，则 n 必定不是素数；若结果等于 a，则 n 很可能是素数。再随机选取另一个整数 a，用同样的方法检验。若它也满足该等式，则我们对 n 是素数更有把握。通过尝试越来越多的 a 值，可以不断提升对结果的信心。这一算法称为费马检验 (Fermat test)。
To implement the Fermat test, we need a procedure that computes the exponential
of a number modulo another number:
为实现费马检验，我们需要一个计算某个数模另一个数的幂次的过程：
This is very similar to the fast-expt procedure of 1.2.4.
It uses successive squaring, so that the number of steps grows logarithmically
with the exponent.
这与 1.2.4 节的 `fast-expt` 过程非常相似。它使用逐次平方法，因此步骤数随指数的增长呈对数增长。
The Fermat test is performed by choosing at random a number a between 1 and
n
−
1 inclusive and checking whether the remainder modulo n of the
n
费马检验的实施方式是：在 1 到 n − 1 之间（含端点）随机选取一个数 a，然后检验 a 的 n
th power of a is equal to a. The random number a is chosen
using the procedure random, which we assume is included as a primitive
in Scheme. Random returns a nonnegative integer less than its integer
input. Hence, to obtain a random number between 1 and n
−
1, we call
random with an input of n
−
1 and add 1 to the result:
次方模 n 的余数是否等于 a。随机数 a 通过过程 `random` 选取，我们假设 Scheme 将其作为基本过程提供。`random` 返回一个小于其整数输入的非负整数。因此，为得到 1 到 n − 1 之间的随机数，我们以 n − 1 为参数调用 `random`，再将结果加 1：
The following procedure runs the test a given number of times, as specified by
a parameter. Its value is true if the test succeeds every time, and false
otherwise.
下面的过程按参数指定的次数运行该检验，若每次检验均通过则返回真，否则返回假。
Subheading: Probabilistic methods
小节标题：概率性方法
The Fermat test differs in character from most familiar algorithms, in which
one computes an answer that is guaranteed to be correct. Here, the answer
obtained is only probably correct. More precisely, if n ever fails the
Fermat test, we can be certain that n is not prime. But the fact that
n passes the test, while an extremely strong indication, is still not a
guarantee that n is prime. What we would like to say is that for any
number n, if we perform the test enough times and find that n always
passes the test, then the probability of error in our primality test can be
made as small as we like.
费马检验在性质上与大多数我们熟悉的算法不同——后者计算出的答案保证正确，而费马检验给出的答案只是「大概率正确」。更确切地说，若 n 未能通过费马检验，我们可以确定 n 不是素数；但 n 通过检验，尽管是非常有力的证据，仍不能保证 n 就是素数。我们希望说的是：对于任意数 n，若我们执行足够多次检验，发现 n 每次都通过，那么素性检验出错的概率可以被压缩到任意小。
Unfortunately, this assertion is not quite correct. There do exist numbers
that fool the Fermat test: numbers n that are not prime and yet have the
property that a
n is congruent to a modulo n for all integers
a
遗憾的是，上述断言并不完全正确。确实存在能够欺骗费马检验的数：某些 n 不是素数，却对所有整数 a（小于 n）都有 a 的 n 次方模 n 同余于 a，满足上述关系的整数 a
n. Such numbers are extremely rare, so the Fermat test is quite
reliable in practice.
皆如此。这样的数极为罕见，因此费马检验在实践中相当可靠。
There are variations of the Fermat test that cannot be fooled. In these tests,
as with the Fermat method, one tests the primality of an integer n by
choosing a random integer a
费马检验存在若干变体，它们不会被愚弄。在这些检验中，与费马方法类似，通过随机选取一个整数 a 来检测整数 n 的素性，
n and checking some condition that depends
upon n and a. (See Exercise 1.28 for an example of such a test.)
On the other hand, in contrast to the Fermat test, one can prove that, for any
n, the condition does not hold for most of the integers a
n，并验证某个依赖于 n 与 a 的条件。（参见练习 1.28 中此类检验的一个例子。）另一方面，与费马检验不同的是，对于任意 n，可以证明：除非 n 是素数，否则该条件对大多数整数 a
n unless
n is prime. Thus, if n passes the test for some random choice of
a, the chances are better than even that n is prime. If n passes
the test for two random choices of a, the chances are better than 3 out of
4 that n is prime. By running the test with more and more randomly chosen
values of a we can make the probability of error as small as we like.
n 都不成立。因此，若 n 对某个随机选取的 a 通过了检验，则 n 是素数的概率超过二分之一。若 n 对两个随机选取的 a 均通过检验，则 n 是素数的概率超过四分之三。通过以越来越多的随机选取的 a 值运行检验，我们可以将出错的概率缩小到任意小的程度。
The existence of tests for which one can prove that the chance of error becomes
arbitrarily small has sparked interest in algorithms of this type, which have
come to be known as
probabilistic algorithms. There is a great deal
of research activity in this area, and probabilistic algorithms have been
fruitfully applied to many fields.
存在这样的检验——可以证明其出错概率可以任意地小——这一事实激发了人们对此类算法的兴趣，它们被称为概率算法 (probabilistic algorithms)。这一领域目前有大量研究活动，概率算法已被富有成效地应用于许多领域。
(define (smallest-divisor n)
(find-divisor n 2))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n)
n)
((divides? test-divisor n)
test-divisor)
(else (find-divisor
n
(+ test-divisor 1)))))
(define (divides? a b)
(= (remainder b a) 0))(define (prime? n)
(= n (smallest-divisor n)))(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder
(square (expmod base (/ exp 2) m))
m))
(else
(remainder
(* base (expmod base (- exp 1) m))
m))))(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a))
(try-it (+ 1 (random (- n 1)))))(define (fast-prime? n times)
(cond ((= times 0) true)
((fermat-test n)
(fast-prime? n (- times 1)))
(else false)))