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 ).
В— 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 ).

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 , 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  and .
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  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 ). 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 , 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
 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 .
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  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 .
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  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  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  and ). 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
вЂ“, based upon the earlier work of Miller , which in turn appealed
to the ideas of Ankeny  (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  and ).
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 .)
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