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