This section describes two methods for checking the primality of an
integer $n$, one with order of growth
$\Theta(\sqrt{n})$, and a
probabilistic

algorithm with order of growth
$\Theta(\log n)$. The exercises at the end of
this section suggest programming projects based on these algorithms.

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.

function smallest_divisor(n) { return find_divisor(n, 2); } function find_divisor(n, test_divisor) { return square(test_divisor) > n ? n : divides(test_divisor, n) ? test_divisor : find_divisor(n, test_divisor + 1); } function divides(a, b) { return b % a === 0; }

We can test whether a number is prime as follows: $n$ is prime if and only if $n$ is its own smallest divisor.

function is_prime(n) { return n === smallest_divisor(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
$\sqrt{n}$.[1]
This means that the algorithm need only test divisors between 1 and
$\sqrt{n}$. Consequently, the number of steps
required to identify $n$ as prime will have order
of growth $\Theta(\sqrt{n})$.

The $\Theta(\log n)$ primality test is based on a result from number theory known as Fermat's Little Theorem.[2]

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

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.

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

function expmod(base, exp, m) { return exp === 0 ? 1 : is_even(exp) ? square(expmod(base, exp / 2, m)) % m : (base * expmod(base, exp - 1, m)) % m; }

This is very similar to the
`fast_expt`
function
of section 1.2.4. It uses successive
squaring, so that the number of steps grows logarithmically with the
exponent.[3]

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
function
`random`, which we assume
our JavaScript environment defines as a primitive function.
The function `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:

function fermat_test(n) { function try_it(a) { return expmod(a, n, n) === a; } return try_it(1 + random(n - 1)); }

The following function 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.

function fast_is_prime(n, times) { return times === 0 ? true : fermat_test(n) ? fast_is_prime(n, times - 1) : false; }

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 $a$ modulo $n$ for all integers $a < n$. Such numbers are extremely rare, so the Fermat test is quite reliable in practice.[4]

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

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.[5]

smallest_divisor(199); // smallest_divisor(1999); // smallest_divisor(19999);

function timed_prime_test(n) { display(n); return start_prime_test(n, runtime()); } function start_prime_test(n, start_time) { return is_prime(n) ? report_prime(runtime() - start_time) : true; } function report_prime(elapsed_time) { display(" *** "); display(elapsed_time); }

function search_for_primes(start, times) { return times === 0 ? true : start > 2 && start % 2 === 0 ? search_for_primes(start + 1, times) // if we get undefined -> its a prime : is_undefined(timed_prime_test(start)) ? search_for_primes(start + 2, times - 1) : search_for_primes(start + 2, times); }

function next(input) { return input === 2 ? 3 : input + 2; } function find_divisor(n, test_divisor) { return square(test_divisor) > n ? n : divides(test_divisor, n) ? test_divisor : find_divisor(n, next(test_divisor)); }

function timed_prime_test(n) { display(n); return start_prime_test(n, runtime()); } function start_prime_test(n, start_time) { return fast_is_prime(n, math_floor(math_log(n))) ? report_prime(runtime() - start_time) : true; } function report_prime(elapsed_time) { display(" *** "); display(elapsed_time); }

function expmod(base, exp, m) { return fast_expt(base, exp) % m; }

function expmod(base, exp, m) { return exp === 0 ? 1 : is_even(exp) ? expmod(base, exp / 2, m) * expmod(base, exp / 2, m) % m : base * expmod(base, exp - 1, m) % m; }

I don't see what difference that could make,says Louis.

I do.says Eva.

By writing the function like that, you have transformed the $\Theta(\log n)$ process into a $\Theta(n)$ process.Explain.

expmod(base, exp / 2, m) * expmod(base, exp / 2, m) % m

function carmichael(n) { function expmod(base, exp, m) { return exp === 0 ? 1 : is_even(exp) ? square(expmod(base, exp / 2, m)) % m : (base * expmod(base, exp - 1, m)) % m; } function fermat_test(n, a) { return expmod(a, n, n) === a; } function iter(n, i) { return i === n ? true : fermat_test(n, i) ? iter(n, i + 1) : false; } return iter(n, 2); }

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 $n$. (This is why the Miller-Rabin test cannot be fooled.) Modify the

function random(n) { return math_floor(math_random() * n); } function miller_rabin_test(n) { function expmod(base, exp, m) { return exp === 0 ? 1 : is_even(exp) ? square(trivial_test(expmod(base, exp / 2, m), m)) % m : (base * expmod(base, exp - 1, m)) % m; } function trivial_test(r, m) { return r === 1 || r === m - 1 ? r : square(r) % m === 1 ? 0 : r; } function try_it(a) { return expmod(a, n - 1, n) === 1; } return try_it(1 + random(n - 1)); } function do_miller_rabin_test(n, times) { return times === 0 ? true : miller_rabin_test(n) ? do_miller_rabin_test(n, times - 1) : false; }

[1]
If
$d$ is a divisor of
$n$, then so is $n/d$.
But $d$ and $n/d$
cannot both be greater than $\sqrt{n}$.

[2]
Pierre de Fermat (1601–1665) is considered to be
the founder of
modern number theory. He obtained many important number-theoretic results,
but he usually announced just the results, without providing his proofs.
Fermat's Little Theorem was stated in a letter he wrote in 1640.
The first published proof was given by
Euler in 1736 (and an
earlier, identical proof was discovered in the unpublished manuscripts
of Leibniz). The most famous of Fermat's results—known as
Fermat's Last Theorem—was jotted down in 1637 in his copy of
the book *Arithmetic* (by the third-century Greek mathematician
Diophantus) with the remark

I have discovered a truly remarkable proof, but this margin is too small to contain it.Finding a proof of Fermat's Last Theorem became one of the most famous challenges in number theory. A complete solution was finally given in 1995 by Andrew Wiles of Princeton University.

[3]
The reduction steps in the cases where the exponent
$e$ is greater than 1 are based on the fact that,
for any integers $x$,
$y$, and $m$, we can
find the remainder of $x$ times
$y$ modulo $m$ by
computing separately the remainders of $x$ modulo
$m$ and $y$ modulo
$m$, multiplying these, and then taking the
remainder of the result modulo $m$. For
instance, in the case where $e$ is even, we
compute the remainder of $b^{e/2}$ modulo
$m$, square this, and take the remainder modulo
$m$. This technique is useful because it means
we can perform our computation without ever having to deal with numbers much
larger than $m$. (Compare
exercise 1.25.)

[4]
Numbers that fool the
Fermat test are called *Carmichael numbers*, and little is known
about them other than that they are extremely rare. There are 255
Carmichael numbers below 100,000,000. The smallest few are 561, 1105,
1729, 2465, 2821, and 6601. In testing primality of very large
numbers chosen at random, the chance of stumbling upon a value that
fools the Fermat test is less than the chance that
cosmic radiation will cause the computer to make an error in carrying out a

correctalgorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering.

[5]
One of the most
striking applications of
probabilistic prime testing has been to the field of cryptography. Although
it is now computationally infeasible to factor an arbitrary 200-digit number,
the primality of such a number can be checked in a few seconds with the
Fermat test. This fact forms the basis of a technique for constructing
*RSA algorithm* has become a widely used technique for enhancing the
security of electronic communications. Because of this and related
developments, the study of
prime numbers, once considered the epitome of a topic in

unbreakable codessuggested by Rivest, Shamir, and Adleman (1977). The resulting

puremathematics to be studied only for its own sake, now turns out to have important practical applications to cryptography, electronic funds transfer, and information retrieval.

1.2.6 Example: Testing for Primality