Chapter 4

Probabilistic Primality
Tests

Probable impossibilities are to be preferred to improbable possibilities.
Aristotle (384“322 B.C.) Greek philosopher


4.1 Introduction
For long-term security of the RSA cipher, the primes in the modulus should
be 154 digits (512 bits) each ensuring a modulus of 308 digits (1024 bits). Hence,
it is essential to generate large “random primes” (see Remark 1.13 ). To do this,
we generate large random numbers and test them for primality using primality
testing algorithms. The fastest known such algorithms are probabilistic algo-
rithms (those that use random numbers ” see the discussion of randomized
algorithms on page 205). This is in contrast to deterministic algorithms, also
discussed on page 205. (See Exercises 4.1“4.5, where some deterministic primal-
ity testing algorithms, also called primality proofs may be found). Moreover,
there are much faster (compared to deterministic) probabilistic algorithms for
primality testing. There exist several general types of probabilistic algorithms,
which we now describe. (If necessary, the reader may review complexity theory
in Appendix B before proceeding.)
x Types of Probabilistic Algorithms
The following probabilistic algorithms are based upon decision problems
” those problems whose solution is either “yes” or “no” (see the discussion
of problem classi¬cation on page 207). In each of the following algorithms,
there is an assigned error probability or failure probability (computed over all
possible random choices made by the algorithm when it is run with a given
input), ± ∈ R such that 0 ¤ ± < 1. This means that the algorithm will give an
incorrect answer with probability at most ±. However, by running the algorithm
a su¬cient number of times, we may reduce ± to a value as small as desired.


79
© 2003 by CRC Press LLC
80 4. Probabilistic Primality Tests

We will discuss this in more detail once we have the speci¬c primality tests at
our disposal.
❶ Monte Carlo Algorithms
Monte Carlo algorithms are those probabilistic polynomial-time algorithms
that answer correctly at least ¬fty percent of the time. More precisely, A yes-
biased Monte Carlo algorithm is a probabilistic algorithm for which a “yes”
answer is always correct, but a “no” answer may be incorrect. A no-biased
Monte Carlo algorithm is one for which a “no” answer is always correct, but a
“yes” answer may be incorrect. Hence, either form of Monte Carlo yields that
half its answers are certain to be correct. The term “Monte Carlo” algorithm
has been used since the turn of the twentieth century (see [119]).
— Atlantic City Algorithms
An Atlantic City algorithm is a a probabilistic polynomial-time algorithm
that answers correctly at least seventy-¬ve percent of the time. In other versions
of the algorithm, the value 3/4 may be replaced by any value greater than
1/2. The term “Atlantic City” was ¬rst introduced in 1982 by J. Finn in an
unpublished manuscript entitled Comparison of probabilistic tests for primality.
❸ Las Vegas Algorithms
A Las Vegas algorithm is a probabilistic expected polynomial-time algorithm
that either produces no answer whatsoever, or it produces a correct answer. A
Las Vegas algorithm is often viewed as a combination of both the yes-biased
and no-biased Monte Carlo algorithms. The term “Las Vegas” algorithm was
introduced by L. Babai in 1982 (see [114]).

As noted above, the error probability in the above algorithms may be reduced
to an acceptably small value by running the algorithm a “su¬cient number” of
times. So, how many integers will have to be tested to determine one that is
prime? The Prime Number Theorem (see Theorem C.29 on page 218) tells us
that if n ∈ N is ¬xed then the number of primes less than n is around n/ ln n.
One may therefore conclude that if m is a randomly chosen (odd) integer, its
probability of being prime is approximately 2/ ln m. For instance, we stated
above that the RSA modulus should have primes p of 512 bits each, so

2/ ln p ∼ 2/355, since ln(2512 ) ∼ 355.
= =

Hence, for every 355 odd integers searched two are likely be prime. This is not
unreasonable. In Section 4.4, we will begin to look in detail at some of the
probabilistic primality tests that are most utilized.




© 2003 by CRC Press LLC
4.2. Pseudoprimes and Carmichael Numbers 81

4.2 Pseudoprimes and Carmichael Numbers
Time™s glory is to calm contending kings,
To unmask falsehood, and bring truth to light.
William Shakespeare (1564“1616)

In Section 4.1, we looked at various types of randomized primality testing
algorithms and alleged that they are faster than deterministic types. We now
discuss this in further detail with an eye to setting up some notions essential
for the two types of probabilistic primality tests that we will study in Sections
4.3“4.4.
There do not exist any practical primality tests that encompass the three
desired properties of: (1) generality; (2) speed; and (3) correctness. In fact, in
each test that has been discovered, exactly one of these properties is sacri¬ced.
For instance, there are deterministic polynomial time algorithms, but they lack
generality. A case in point is Pepin™s test presented in Exercise 4.5, which works
well on Fermat numbers n
Fn = 22 + 1.


On the other hand, there are deterministic tests that allow for general input,
and are guaranteed to produce a proof of primality when a prime is input.
However, in general, these tests require factorization, and there are no known
polynomial time algorithms to do this, as we have already discussed in Chapter 3
and will discuss in more detail in Chapter 5. For instance, there is Pocklington™s
Theorem given in Exercise 4.1, that relies on a partial factorization of n ’ 1
given input n. This is a deterministic test since it produces a proof of primality.
There is also the improvement by Kraitchik and Lehmer given in Exercise 4.2,
and that by Brillhart and Selfridge in Exercise 4.3, all requiring some knowledge
of factorization. In fact, the results in Exercises 4.2“4.3 rely on Fermat™s Little
Theorem, C.10 on page 214, the converse of which does not hold without some
additional information. The tests in Exercises 4.2“4.3 actually use the converse
of Fermat™s Little Theorem by giving a primality test with the additional data
input as stated in each Exercise. This motivates the following notion.
De¬nition 4.1 (Pseudoprimes)4.1
If n ∈ N is composite and there exists an a ∈ N such that

an’1 ≡ 1 (mod n), (4.1)

then n is called a pseudoprime to base a. The set of all pseudoprimes to base a
is denoted by psp(a).4.2
4.1 In [84], Erd¨s states that the term “pseudoprime” is due to D.H. Lehmer (see Footnote
o
4.3). The notion has been generalized several times over. For instance, see [135] and [159].
In this text, we do not allow (as is sometimes done in the literature) for a pseudoprime to be
prime.
4.2 Although some sources do not use this symbol for the set of such pseudoprimes, we adopt

the convention as it is used in [15] since we ¬nd it to be a convenient usage.



© 2003 by CRC Press LLC
82 4. Probabilistic Primality Tests

We see why we would call such entities “pseudoprimes” since (4.1) is the
property held by primes in Fermat™s Little Theorem. In fact, the reader can go
to Exercise 4.6 for more connections in this regard.

Example 4.2 Consider:
2560 ≡ 1 (mod 561).
Also
38910 ≡ 1 (mod 8911).
However,
561 = 3 · 11 · 17 and 8911 = 7 · 19 · 67.
Thus, 561 and 8911 are pseudoprimes to base 2 and 3, respectively. However,
561 and 8911 are much more and in fact are examples of a very important kind
of composite number.


De¬nition 4.3 (Carmichael Number)
A composite n ∈ N satisfying

an’1 ≡ 1 (mod n) for each a ∈ N with gcd(a, n) = 1

is called a Carmichael number.

In 1922, the American mathematician, Robert Carmichael conjectured that
there are in¬nitely many Carmichael numbers. This was proved some seventy
years later by Alford, Granville, and Pomerance (see [3]). The reader may ver-
ify that both 561 and 8911 are indeed Carmichael numbers using Exercise 4.7.
In fact, 561 is the smallest Carmichael number. De¬nition 4.3 tells us that
all Carmichael numbers are pseudoprimes to base a for all a ∈ N such that
gcd(a, n) = 1, so Carmichael numbers are sometimes called absolute pseudo-
primes. We see that the converse of Fermat™s Little Theorem fails in the ex-
treme for Carmichael numbers. However, what Exercises 4.1“4.3 demonstrate
is that the converse of Fermat™s Little Theorem can be used to prove primality
of n if we can ¬nd an element of order n ’ 1 in (Z/nZ)— , namely, a primitive
root modulo n (see Proposition C.22 on page 216).
In Sections 4.3“4.4, we introduce variants of the notion in De¬nition 4.1
in the presentation of two probabilistic primality tests. These tests sacri¬ce
correctness, but are extremely fast and allow for general input. Moreover, if
the input is prime, we are guaranteed that the test will declare it to be so.
However, the uncertainty comes attached to the fact that a composite number
might also be deemed to be prime. Nevertheless, we can reduce this probability
to acceptably low levels.




© 2003 by CRC Press LLC
4.2. Pseudoprimes and Carmichael Numbers 83

Exercises
4.1. Let n = ab + 1 (a, b ∈ N, b > 1). Suppose that for any prime divisor q
of b > 1, there exists an integer m with gcd(m(n’1)/q ’ 1, n) = 1, and
mn’1 ≡ 1 (mod n). Prove that p ≡ 1 (mod b) for every prime p dividing

n. Also, if b > n ’ 1, then n is prime. (This is known as Pocklington™s
Theorem, which is a deterministic primality test (see page 124).)
4.2. Given n ∈ N with n ≥ 3, prove that n is prime if and only if there is an
m ∈ N such that mn’1 ≡ 1 (mod n), but m(n’1)/q ≡ 1 (mod n) for any
prime q (n ’ 1). (This is another deterministic primality test due to
Lehmer4.3 and Kraitchik4.4 , according to [15, p. 267] ” see [125, p. 135].)
4.3. Prove that n ≥ 3 is prime if and only if for each prime q (n ’ 1), there
(n’1)/q
exists an mq ∈ Z with both mn’1 ≡ 1 (mod n) and mq ≡ 1 (mod n).
q
4.5
(This deterministic test is due to Brillhart and Selfridge (see Footnote
4.10) in [47], improving upon the result in Exercise 4.2.)
n
4.4. Let Fn = 22 + 1 for n ∈ N be the n-th Fermat number. Prove that if Fn
is prime, then 3 is a primitive root modulo Fn .
n
4.5. Let Fn = 22 + 1 be the n-th Fermat number. Prove that Fn is prime
if and only if 3(Fn ’1)/2 ≡ ’1 (mod Fn ). (This is called Pepin™s primality
test, another deterministic test.)
4.6. If n is an odd composite number satisfying (4.1), sometimes called Fer-
mat™s Primality test, for some integer a, then a is called a Fermat Liar (to
the primality of n). Thus, the elements of psp(a) (see De¬nition 4.1) are
sometimes called ordinary pseudoprimes or Fermat pseudoprimes. Find
all Fermat liars for n = 65.
r
4.7. Let n = j=1 pj where r ≥ 2 and the pj are distinct odd primes. Prove
that n is a Carmichael number if and only if (pj ’ 1) (n ’ 1) for j =
1, 2, . . . , r. (See De¬nition 4.3.)
4.3 Derrick Henry Lehmer (1905“1991) was born in Berkeley, California on February 23, 1905.
He obtained his Ph.D. from Brown University in 1930. After some brief stints elsewhere, he
took a position at UC Berkeley in 1940, remaining there until he retired in 1972. He was a
truly great pioneer in computational number theory. See a collection of his selected works
[133] for evidence of his genius.
4.4 Maurice Borisovich Kraitchik (1882“1957) obtained his Ph.D. from the University of Brus-

sels in 1923. He worked as an engineer in Brussels and later as a Director at the Mathematical
Sciences section of the Mathematical Institute for Advanced Studies there. From 1941“1946,
he was Associate Professor at the New School for Social Research in New York. In 1946, he
returned to Belgium where he died on August 19, 1957. His work over thirty-¬ve years on
factoring methods stands tall today because he devised and used a variety of practical tech-
niques that are found today in computer methods such as the Quadratic Sieve (see Chapter
5). He is also the author of the popular book Mathematical Recreations [126].
4.5 John Brillhart is a Professor Emeritus at the University of Arizona at Tucson. He obtained

his Ph.D. under the supervision of Dick Lehmer (see Footnote 4.3) at UC Berkeley. He is a
pioneer in computational number theory, and a co-inventor of the continued fraction factoring
algorithm (see Chapter 5). His seminal work in primality testing and factoring is part of the
structure of the computational edi¬ce we enjoy today.



© 2003 by CRC Press LLC
84 4. Probabilistic Primality Tests

4.3 Solovay-Strassen Test
Idleness is only the refuge of weak minds.
Lord Chester¬eld
(Philip Dormer Stanhope, Earl of Chester¬eld) (1694“1773)
English writer and politician

To prepare for this section, the reader must be familiar with the Jacobi sym-
bol and Euler™s criterion, for which Appendix C will provide a quick reference
(see the discussion starting on page 217). The probabilistic primality test in the
title of this section was the ¬rst such test that became prominent due to the
arrival of public-key cryptography upon the cryptographic scene. We present it
here for both historical and motivational reasons in comparison to the stronger
test to be presented in Section 4.4 since it will provide us with a means of
introducing new concepts for later use.
The following is our ¬rst example of one of the types of algorithms pre-
sented in Section 4.1. It is a Monte Carlo algorithm for compositeness, namely,
a yes-biased Monte Carlo algorithm for the decision problem: “Is the input com-
posite?” (See the discussion of problem classi¬cation in Appendix B starting on
page 207.) Thus, if the algorithm answers that input n ∈ N is composite, then
indeed it is, whereas if it answers that n is prime, we only have some (good)
evidence of primality. This is due to the fact that the test is based upon the
Euler criterion (see Corollary C.27 on page 218), which is a necessary, but not
su¬cient, test for primality in terms of the Jacobi symbol. The following is
named after the discoverers who published the result [224] in 1977. Also, due
to the use of Euler™s criterion, the test is also called the Euler pseudoprimality
test. This test was modi¬ed in 1982 by Atkin and Larson [8].
x The Solovay-Strassen Primality Test
Let n ∈ N, n > 1 and select at random r positive random integers aj with
aj < n and gcd(aj , n) = 1 for j = 1, 2, . . . , r ∈ N. For each such j compute
both:
aj
(n’1)/2
aj and modulo n
n
until one of the following occurs.
(1) For some j ¤ r,
aj
(n’1)/2

aj (mod n),
n
in which case, terminate the algorithm with “n is de¬nitely not prime”.
(2) For all j = 1, 2, . . . , r,
aj
(n’1)/2

aj (mod n) (4.4)
n
in which case, terminate the algorithm with “n is probably prime”.




© 2003 by CRC Press LLC
4.3. Solovay-Strassen 85

Any composite integer n that is declared to be “probably prime” to base a
by the Solovay-Strassen test is said to be a base-a Euler pseudoprime,4.6 and a is
called an Euler liar4.7 (to the primality of n). The set of Euler psuedoprimes to
base a is denoted by epsp(a). The set of Euler liars, E(n), is de¬ned in Exercise
4.8, which shows that E(n) actually is a subgroup of (Z/nZ)— . When

a ∈ (Z/nZ)— , but a ∈ E(n),

then a is called an Euler witness (to the compositeness of n). Exercise 4.13
tells us that at least half of the integers a with 1 < a < n are Euler witnesses.
Moreover, by Exercise 4.12:

n is an odd prime if and only if E(n) = (Z/nZ) ,

a foundational fact upon which the Solovay-Strassen test is built.
If n is declared to be “de¬nitely not prime” in step (1) of the test, then
we may conclude with certainty that n is composite since Euler™s criterion tells
us that all primes necessarily satisfy (4.4), so failure to do so in step (1) is
a guarantee that the number cannot be prime. Moreover, if n is indeed prime
then the test will declare that it is since it will pass Euler™s criterion, necessarily.
However, if n is composite, then there is no certainty that the test will declare
it to be so. Nevertheless, by Exercises 4.12“4.13, the probability that an odd
composite integer will be declared to be prime by the Solovay-Strassen test is
less than (1/2)r for randomly chosen r. Hence, the larger the parameter r,
the greater the probability that a composite number will not be declared to be
prime by the Solovay-Strassen test.

Example 4.5 Let n = 8911 and choose a = 2. Then

2
2(n’1)/2 ≡ 24455 ≡ 6364 ≡ ≡ 1 (mod n).
n

hence, n is declared to be composite by the Solovay-Strassen test. Indeed, 8911 =
7 · 19 · 67.

In terms of complexity, it can be shown that for a given base a, in the
Solovay-Strassen test, each of the computations takes O((1 + log2 |n| )3 ) bit
operations (see [15, Theorem 9.4.2, p. 280]). In Section 4.4, we will introduce
a test which also uses this number of bit operations, but which is both more
e¬cient and more often correct in its outcome.
4.6 The term “Euler pseudoprime” was introduced by Shanks [204] in 1978.
4.7 In the literature, the term “false witness” is sometimes used instead of “liar”.




© 2003 by CRC Press LLC
86 4. Probabilistic Primality Tests

Exercises

4.8. Let n ∈ N be odd and composite. De¬ne E(n) by
a
{a ∈ (Z/nZ)— : ≡ a(n’1)/2 (mod n)}.
n
Prove that this is a subgroup of (Z/nZ)— , called the group of Euler liars for
n. (Hint: It is su¬cient to prove that ab’1 ∈ E(n) whenever a, b ∈ E(n).)
4.9. Prove that if p > 2 is prime, a ∈ N, then

x2 ≡ 1 (mod pa ) if and only if x ≡ ±1 (mod pa ).

4.10. Prove that if n is a Carmichael number, then n is squarefree.
4.11. Prove that 8911 and 10585 are Carmichael numbers, and that 10585 is
also an Euler pseudoprime to base 2.
Exercises 4.12“4.13 are in reference to Exercise 4.8.
4.12. Prove that any odd natural number n ≥ 3 is prime if and only if E(n) =
(Z/nZ)— . (Hint: Use Exercise 4.10.)
4.13. Prove that for composite n, |E(n)| ¤ φ(n)/2.
4.14. Prove that 15841 is an Euler pseudoprime to base 2.
4.15. Prove that 29341 is an Euler pseudoprime to base 2.
4.16. Prove that 41041 is an Euler pseudoprime to base 2.
4.17. Prove that 62745 is an Euler pseudoprime to base 2.
4.18. Prove that the values in Exercises 4.14“4.17 are all Carmichael numbers.
(Hint: Use Exercise 4.7.)
4.19. Find an Euler pseudoprime to base 3 that is also a Carmichael number.
° 4.20. Let n be an odd natural number. With reference to Exercise 4.8, prove
that if
r
mj
n= pj
j=1

where the pj are distinct primes, then
r
n’1
|E(n)| = dn , pj ’ 1 ,
gcd
2
j=1

where dn ∈ {1/2, 1, 2}.
(Hint: Use Theorem C.28 on page 218.)




© 2003 by CRC Press LLC
4.4. Miller-Selfridge-Rabin 87

4.4 Miller-Selfridge-Rabin Test
Beauty is the ¬rst test: there is no permanent place in the world for ugly
G. H. Hardy4.8
mathematics.

We may now provide our second example of a Monte Carlo algorithm for
compositeness (see Section 4.1).
There are methods for proving that a number is composite without ¬nd-
ing any factors of that number. For instance, consider the following simple
illustration.
Example 4.6 It is easy to prove that n = 77 is composite without ¬nding a
factor, since by Fermat™s Little Theorem C.10 on page 214, 77 cannot be prime,
given that
2n’1 ≡ 1 (mod n).
(The reader may show this to be true in incremental steps. Consider:

28 ≡ 25 (mod 77); 212 ≡ 24 · 28 ≡ 16 · 25 ≡ 15 (mod 77);

216 ≡ 252 ≡ 9 (mod 77); 232 ≡ 92 ≡ 4 (mod 77); 264 ≡ 16 (mod 77);
so 276 ≡ 264 · 212 ≡ 16 · 15 ≡ 9 (mod 77).)

This idea is used in a more general fashion as follows.
x The Miller4.9 -Selfridge4.10 -Rabin4.11 Primality Test
Let n ’ 1 = 2t m where m ∈ N is odd and t ∈ N. The value n is the input to
be tested by executing the following steps, where all modular exponentiations
are done using the repeated squaring method described on page 50.

(1) Choose a random integer a with 2 ¤ a ¤ n ’ 2.
4.8 Godfrey Harold Hardy was born in Cranleigh, Surrey on February 7, 1877. He taught
at Trinity College, Cambridge from 1906 to 1919. In 1919, he was appointed to the Savilian
Chair of Geometry at Oxford University. In 1931, he was appointed Sadlerian Professor of Pure
Mathematics at Cambridge, where he died on December 1, 1947. Hardy is famous, not only
for his numerous contributions to number theory, but also for his book, ¬rst published in 1940,
A Mathematician™s Apology, from which this quote is taken. This book took the stand that
number theory is “useless” in the sense of having no real-world applications. Hardy perhaps
foresaw that some applications might come to the fore when he said in his book: “Time may
change all this.” Indeed, he would be greatly surprised to see the impact of number theory on
cryptography and its varied applications.
4.9 Gary Miller obtained his Ph.D. in Computer Science from UC Berkeley in 1974. He is

currently a Professor in Computer Science at Carnegie-Mellon University. His expertise lies
in computer algorithms.
4.10 This test is most often called the Miller-Rabin Test in the literature. However, John

Selfridge was using the test in 1974 before Miller ¬rst published the result, so we credit
Selfridge here with this recognition. John Selfridge was born in Ketchican, Alaska, on February
17, 1927. He received his doctorate from U.C.L.A. in August of 1958, and became a Professor
at Pennsylvania State University six years later. He is a pioneer in computational number
theory.
4.11 See Footnote B.11 on page 211.




© 2003 by CRC Press LLC
88 4. Probabilistic Primality Tests

(2) Compute:
x ≡ am (mod n).
If
x ≡ ±1 (mod n),
then terminate the algorithm with:

“n is probably prime”.

If t = 1, terminate the algorithm with

“n is de¬nitely not prime.”

Otherwise, set j = 1 and go to step (3).
(3) Compute:
j
x ≡ a2 m
(mod n).
If x ≡ 1 (mod n), then terminate the algorithm with

“n is de¬nitely not prime.”

If x ≡ ’1 (mod n), terminate the algorithm with

“n is probably prime.”

Otherwise set j = j + 1 and go to step (4).
(4) If j = t ’ 1, then go to step (5). Otherwise, go to step (3).
(5) Compute:
t’1
x ≡ a2 m
(mod n).
If x ≡ ’1 (mod n), then terminate the algorithm with

“n is de¬nitely not prime.”

If x ≡ ’1 (mod n), then terminate the algorithm with

“n is probably prime.”


If n is declared to be “probably prime” with base a by the Miller-Selfridge-
Rabin test, then

n is said to be a strong pseudoprime to base a.

Thus, the above test is often called the strong pseudoprime test4.12 in the liter-
ature. The set of all pseudoprimes to base a is denoted by spsp(a).
4.12 Theterm “strong pseudoprime” was introduced by Selfridge in the mid-1970s, but he did
not publish this reference. However, it did appear in a paper by Williams [235] in 1978.



© 2003 by CRC Press LLC
4.4. Miller-Selfridge-Rabin 89

Let us look a little closer at the above test to see why it it is possible to
declare that “n is de¬nitely not prime” in step (3). If x ≡ 1 (mod n) in step (3),
then for some j with 1 ¤ j < t ’ 1:
j j’1
≡ 1 (mod n), but a2 ≡ ±1 (mod n).
a2 m m


Thus, by Exercise 4.23 (a special case of which appears in Exercise 3.12)
j’1
gcd(a2 m ’ 1, n) is a nontrivial factor of n. Hence, if the Miller-Selfridge-
Rabin test declares in step (3) that n is “de¬nitely not prime”, then indeed
it is composite. Another way of saying this is that if n is prime, then Miller-
Selfridge-Rabin will declare it to be so. However, if n is composite, then it can
be shown that the test fails to recognize n as composite with probability at most
(1/4). This is why the most we can say is that “n is probably prime”. However,
if we perform the test r times for r large enough, this probability (1/4)r can be
brought arbitrarily close to zero. Moreover, at least in practice, using the test
with a single choice of a base a is usually su¬cient.
Also, in step (5), notice that we have not mentioned the possibility that
t’1
≡ 1 (mod n)
a2 m


speci¬cally. However, if this did occur, then that means that in step (3), we
would have determined that
t’2
≡ ±1 (mod n),
a2 m


so by Exercise 4.9, n cannot be prime. Furthermore, by the above method, we
t’2
can factor n since gcd(a2 m ’ 1, n) is a nontrivial factor. This ¬nal step (4) is
required since, if we get to j = t’1, with x ≡ ±1 (mod n) for any j < t’1, then
simply invoking step (3) again would dismiss those values of x ≡ ±1 (mod n),
and this would not allow us to claim that n is composite in those cases. Hence,
it allows for more values of n to be deemed composite, with certainty, than if
we merely performed step (3) as with previous values of j.
The above discussion contains a fundamental principle that is worth discus-
sion. A basic point made in Exercise 4.23 is that if we have a natural number
n > 1 such that

x2 ≡ y 2 (mod n) with x ≡ ±y (mod n) for integers x, y, (4.7)

then n is necessarily composite since gcd(x ’ y, n) is a nontrivial factor of n.
Although Gauss knew this, the basic idea goes back to Fermat who, in 1643,
developed a method of factoring that was based upon a simple observation. If

n = rs is an odd natural number with 1 < r < n, then

n = a2 ’ b2 where a = (s + r)/2 and b = (s ’ r)/2.

Therefore, in order to ¬nd a factor of n, we need only look at values x = y 2 ’ n
for √ √
n + 1, n + 2, . . . , (n ’ 1)/2
y=


© 2003 by CRC Press LLC
90 4. Probabilistic Primality Tests

until a perfect square is found. We call this Fermat™s di¬erence of squares
method, which has been rediscovered numerous times and is the underpinning
of many algorithms for factoring today. (The basic idea is attributed also to
Legendre.) We will discuss this in more detail in Chapter 5. Exercise 3.12
illustrates how this idea of Fermat can be used to factor an RSA modulus,
n = pq, when p and q are “close together”. This is one of the reasons for
ensuring that the primes are “properly” chosen in an RSA modulus, a topic
that we will revisit in Chapter 6. Now we return to the Miller-Selfridge-Rabin
test with an illustration.

Example 4.8 Let n = 1105. Since n ’ 1 = 2t m = 24 · 69, we choose a = 2 and
compute
x ≡ 2m ≡ 967 (mod n)
in step (2). Then we go to steps (3)“(4), compute
j
x ≡ 22 m
(mod n) for j = 1, 2,

for which x ≡ ±1 (mod n). Since j = 3 = t ’ 1 in step (4), we go to step (5)
and compute:
3
x ≡ 22 m ≡ 1 (mod n).
Thus, we conclude with “n is de¬nitely not prime”.

Example 4.8 shows that 1105 is not a strong pseudoprime to base 2. However,

21104 ≡ 1 (mod 1105),

so 1105 is a pseudoprime to base 2. In general, there are far fewer strong pseudo-
primes than pseudoprimes (see Exercise 4.21). Moreover, 1105 is a Carmichael
number (see De¬nition 4.3). By Exercise 4.27, a Carmichael number n cannot
be a strong pseudoprime to every base a with gcd(a, n) = 1. Also, Carmichael
numbers provide in¬nitely many counterexamples to the converse of Fermat™s
Little Theorem. However, there exists an additional condition that makes the
converse of Fermat™s theorem work as a primality test ” see Exercise 4.28.
Exercise 4.22 provides another characterization of strong pseudoprimes.
Therein, we de¬ne a strong witness to the compositeness of n. It can be shown
that there are at most (n ’ 1)/4 natural numbers (prime to, and less than
n) which are not strong witnesses for the compositeness of n, namely, if n is
composite, then in the notation of Exercise 4.22,

|S(n)| ¤ (n ’ 1)/4.

In fact, it is known that for any natural number n = 9,

|S(n)| ¤ φ(n)




© 2003 by CRC Press LLC
4.4. Miller-Selfridge-Rabin 91

(see [15] and [156]). This gives further evidence for the earlier allegation that
the probability of a composite number n failing detection by the strong pseu-
doprimality test is less than 1/4. It can also be shown, as well, that the Miller-
Selfridge-Rabin test uses O((1 + log2 |n| )3 ) bit operations (see [15, Theorem
9.4.5, p. 282]). Also, the following may be of interest to the reader with knowl-
edge of the generalized Riemann hypothesis (GRH). Under the assumption of
GRH, it has been shown that for every composite integer n, there exists a base
a with
1 < a ¤ 2(log2 n),
2

such that n fails the Miller-Selfridge-Rabin test to base a. This was done by Bach
[13]“[14], based upon the earlier work of Miller [158], which in turn appealed
to the ideas of Ankeny [4] (see [239, p. 351]). Lastly, it has been shown, under
the assumption of the GRH, that there exists a deterministic polynomial time
algorithm for primality testing (see [156] and [245]).
Now we have a look at comparisons among the tests we have discussed in
this chapter. We know that both of the Solovay-Strassen and Miller-Selfridge-
Rabin tests use O((1 + log2 |n| )3 ) bit operations for input n. However,
Miller-Selfridge-Rabin is computationally less expensive to implement than the
Solovay-Strassen test given that the latter requires computation of Jacobi sym-
bols. Furthermore, for a given number, r, of iterations of either algorithm, the
error probability of Solovay-Strassen is at most (1/2)r , while that for Miller-
Selfridge-Rabin is at most (1/4)r . Also, by Exercise 4.35, strong liars must be
Euler liars, so Miller-Selfridge-Rabin can never err more than Solovay-Strassen.
In other words, Miller-Selfridge-Rabin is always at least as correct as Solovay-
Strassen. By Exercises 4.6 and 4.35“4.36, we have the following diagram.



Figure 4.8: Hierarchy of Pseudoprimality


Fermat Liars Euler Liars Strong Liars




This diagram encapsulates the practical fact that one should never use either
of Fermat or Solovay-Strassen over Miller-Selfrige-Rabin. The former two were
presented for motivational, historical, and pedagogical reasons.
In Chapter 5, we move up to the next cryptographic step by looking at
factoring methods, which will lead us into Chapter 6 where we discuss security
issues surrounding RSA and public-key cryptography in general.




© 2003 by CRC Press LLC
92 4. Probabilistic Primality Tests

Exercises
4.21. For given a ∈ N, prove that spsp(a) ⊆ psp(a). (See De¬nition 4.1.)
4.22. Assume that n = 1 + 2t m is composite, where m ∈ N is odd, and t ∈ N.
Let S(n) denote the following set:
— j
{a ∈ (Z/nZ) : am ≡ 1 (mod n) or a2 ≡ ’1 (mod n) for 0 ¤ j < t},
m


called the set of strong liars (to primality) for n. If a ∈ (Z/nZ)— and
a ∈ S(n) then a is called a strong witness (to compositeness) for n. Prove
that a ∈ S(n) if and only if n is a strong pseudoprime to base a.
4.23. Let n ∈ N and x, y ∈ Z with x2 ≡ y 2 (mod n) and x ≡ ±y (mod n). Prove
that n is composite and gcd(x ’ y, n) is a nontrivial factor of n.
4.24. Prove that if S(n) = (Z/nZ)— , de¬ned in Exercise 4.22, then n is a
Carmichael number.
4.25. Prove that each of 15841, 29341, 52633, and 252601 is both a Carmichael
number and a strong pseudoprime to base 2.
4.26. Prove that the only possible even Carmichael number is n = 2. (This
leads to the trivial statement that a ≡ 1 (mod 2) for all odd integers a.
Thus, we always assume that a Carmichael number is odd.)
4.27. Prove that a Carmichael number n cannot be a strong pseudoprime to
every base a with gcd(a, n) = 1.
4.28. Let g be a primitive root modulo an odd prime p. Prove that if a prime
q (p ’ 1), then g (p’1)/q ≡ 1 (mod p).
4.29. Use the Miller-Selfridge-Rabin test to prove that n = 561 is a composite
number (in fact, as noted in Section 4.2, the smallest Carmichael number).
In Exercises 4.30“4.34, use the Miller-Selfridge-Rabin test to determine
that the given value of n is a strong pseudoprime to the given base(s) a.
4.30. n = 2047 and a = 2. (This is the smallest strong pseudoprime to base 2.)
4.31. n = 121 and a = 3. (This is the smallest strong pseudoprime to base 3.)
4.32. n = 781 and a = 5. (This is the smallest strong pseudoprime to base 5.)
4.33. n = 25 and a = 7. (This is the smallest strong pseudoprime to base 7.)
4.34. n = 3215031751 and a = 2, 3, 5, 7. (This is the smallest strong pseudo-
prime to all bases 2, 3, 5, 7. This discovery was published in [190].)
4.35. Prove that for a ∈ N, epsp(a) ⊆ psp(a).
° 4.36. Prove that spsp(a) ⊆ epsp(a). (Hint: Use the general theory of orders of
integers and properties of the Jacobi symbol given in Appendix C.)
4.37. Prove that for any prime power pb ∈ spsp(a) if and only if pb ∈ psp(a).



© 2003 by CRC Press LLC