This section describes two methods for checking the primality of an
integer *n*, one with order of growth _{}, and a "probabilistic" algorithm with order
of growth _{}. The exercises at the end
of this section suggest programming projects based on these
algorithms.

**Searching for divisors**

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.

We can test whether a number is prime as follows:(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))

The end test for(define (prime? n) (= n (smallest-divisor n)))

**The Fermat test**

The _{} primality test is based on a
result from number theory known as Fermat's Little Theorem. ^{45}

**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*th 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 modulo *n*modulo *n* *
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

To implement the Fermat test, we need a procedure that computes the exponential of a number modulo another number:

(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))))

This is very similar to the ` fast-expt` procedure of section
1.2.4. It uses successive
squaring, so that the number of steps grows logarithmically with the
exponent. ^{46}

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*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:

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.(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)))

**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.

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

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. ^{48}

**Exercise 1.21**

Use the `smallest-divisor` procedure to find the smallest
divisor of each of the following numbers: 199, 1999, 19999.

**Exercise 1.22**

Most Lisp implementations include a primitive called `runtime`
that returns an integer that specifies the amount of time the system
has been running (measured, for example, in microseconds). The
following `timed-prime-test` procedure, when called with an
integer *n*, prints *n* and checks to see if *n*
is prime. If *n* is prime, the procedure prints three asterisks
followed by the amount of time used in performing the test.

Using this procedure, write a procedure(define (timed-prime-test n) (newline) (display n) (start-prime-test n (runtime))) (define (start-prime-test n start-time) (if (prime? n) (report-prime (- (runtime) start-time)))) (define (report-prime elapsed-time) (display " *** ") (display elasped-time))

**Exercise 1.23**

The `smallest-divisors` procedure shown at the start of this
section does lots of needless testing: After it checks to see if the
number is divisible by 2 there is no point in checking to see if it is
divisible by any larger even number. This suggests that the values
used for `test-divisor` should not be 2,3,4,5,6,..., but rather
2,3,5,7,9,...To implement this change, define a procedure
`next` that returns 3 if its input is equal to 2 and otherwise
returns its input plus 2. Modify the `smallest-divisor`
procedure to use `(next test-divisor)` instead of `(+
test-divisor 1)`. With `timed-prime-test` incorporating
this modified version of `smallest-divisor`, run the test for
each of the 12 primes found in exercise 1.22. Since this modification
halves the number of test steps, you should expect it to run about
twice as fast. Is this expectation confirmed? If not, what is the
observed ratio of the speeds of the two algorithms, and how do you
explain the fact that it is different from 2?

**Exercise 1.24**

Modify the `timed-prime-text` procedure of exercise 1.22 to use
`fast-prime?` (the Fermat method), and test each of the 12
primes you found in that exercise. Since the Fermat test has

**Exercise 1.25**

Alyssa P. Hacker complains that we went to a lot of extra work in
writing `expmod`. After all, she says, since we already know
how to compute exponentials, we could have simply written

Is she correct? Would this procedure serve as well for our fast prime tester? Explain.(define (expmod base exp m) (remainder (fast-expt base exp) m))

**Exercise 1.26**

Louis Reasoner is having great difficulty doing exercise 1.23. His
`fast-prime?` test seems to run more slowly than his
`prime?` test. Louis calls his friend Eva Lu Ator over to
help. When they examine Louis's code, they find that he has rewritten
the `expmod` procedure to use an explicit multiplication,
rather than calling `square`:

"I don't see what difference that could make," says Louis. "I do." says Eva. "By writing the procedure like that, you have transformed the(define (expmod base exp m) (cond ((= exp 0) 1) ((even? exp) (remainder ( (expmod base (/ exp 2) m) (expmod base (/ exp 2) m)) m)) (else (remainder ( base (expmod base (- exp 1) m)) m))))

**Exercise 1.27**

Demonstrate that the Carmichael numbers listed in footnote 47 really
do fool the Fermat test. That is, write a procedure that takes an
integer *n* and tests whether *a ^{n}* is
congruent to

**Exercise 1.28**

One variant of the Fermat test that cannot be fooled is called the
*Miller-Rabin test* (Miller 1976; Rabin 1980). This starts from
an alternate form of Fermat's Little Theorem, which states that if
*n* is a prime number and *a* is any positive integer
less than *n*, then *a* raised to the (*n* -1)st
power is congruent to 1 modulo *n*. To test the primality of a
number *n* by the Miller-Rabin test, we pick a random number
*a < n* and raise *a* to the (*n* -1)st power
modulo *n* using the `expmod` procedure. However, when
we perform the squaring step in `expmod`, we check to see if we
have discovered a "nontrivial square root of 1 modulo *n*,"
that is, a number not equal to 1 or *n* -1 whose square is
equal to 1 modulo *n*. It is possible to prove that if such a
nontrivial square root of 1 exists, then *n* is not prime. It
is also possible to prove that if *n* is an odd number that is
not prime, then for at least half the numbers *a < n*,
computing *a ^{(n-1)}* in this way will reveal a
nontrivial square root of 1 modulo