Prime Numbers

168	Chapter 3 RECOGNIZING PRIMES AND COMPOSITES

3.38.Consider a specific choice for the Lagarias–Odlyzko turn-o function

c(u, x), namely, a straight-line connection between the 1, 0 values. Specifically,

√

for y = x, define c = 1, (x − u)/y, 0 as u ≤ x − y, u (x − y, x], u > x, respectively. Show that the Mellin companion function is

F (s, x) = 1 xs+1 − (x − y)s+1 . y s(s + 1)

Now derive a bound, as in Exercise 3.37, on proper values of T such that π(x) will be calculated correctly on the basis of

T

π (x) ≈ Re F (s, x) ln ζ(s) dt.

0

Calculate numerically some correct values of π(x) using this particular turn-o function c.

3.39.In regard to the Galway functions of which F is defined by (3.31), make rigorous the notion that even though the Riemann zeta function somehow embodies, if you will, “all the secrets of the primes,” we need to know ζ only to an imaginary height of “about” x1/2 to count all primes not exceeding x.

3.40.Using integration by parts, show that the F defined by (3.31) is indeed the Mellin transform of the given c.

3.9Research problems

3.41. Find a number n ≡ ±2 (mod 5) that is simultaneously a base- 2 pseudoprime and a Fibonacci pseudoprime. Pomerance, Selfridge, and Wagsta o er $620 for the first example. (The prime factorization must also be supplied.) The prize money comes from the three, but not equally: Selfridge o ers $500, Wagsta o ers $100 and Pomerance o ers $20. However, they also agree to pay $620, with Pomerance and Selfridge reversing their roles, for a proof that no such number n exists.

3.42.Find a composite number n, together with its prime factorization, that

is a Frobenius pseudoprime for x2 +5x+5 and satisfies n5 = −1. J. Grantham has o ered a prize of $6.20 for the first example.

3.43.Consider the least witness function W (n) defined for odd composite numbers n. It is relatively easy to see that W (n) is never a power; prove this. Are there any other forbidden numbers in the range of W (n)? If some n exists

3.9 Research problems

169

with W (n) = k, let nk denote the smallest such n. We have

n2	=	9	n12	>	1016
n3	=	2047	n13	=	2152302898747
n5	=	1373653	n14	=	1478868544880821
n6	=	134670080641	n17	=	3474749660383
n7	=	25326001	n19	=	4498414682539051
n10	=	307768373641	n23	=	341550071728321.
n11	=	3215031751

(These values were computed by D. Bleichenbacher, also see [Jaeschke 1993], [Zhang and Tang 2003], and Exercise 4.34.) S. Li has shown that W (n) = 12 for

n = 1502401849747176241,

so we know that n12 exists. Find n12 and extend the above table. Using Bleichenbacher’s computations, we know that any other value of nk that exists must exceed 1016.

3.44.Study, as a possible alternative to the simple trial-division Algorithm 3.1.1, the notion of taking (perhaps extravagant) gcd operations with the N to be factored. For example, you could compute a factorial of some B and take gcd(B!, N ), hoping for a factor. Describe how to make such an algorithm complete, with the full prime factorizations resulting. This completion task is nontrivial: For example, one must take note that a factor k2 of N with k < B might not be extracted from a single factorial.

Then there are complexity issues. Should one instead multiply together sets of consecutive primes, i.e., partial “primorials” (see Exercise 1.6), to form numbers {Bi}, and then test various gcd(Bi, N )?

3.45.Let f (N ) be a worst-case bound on the time it takes to decide primality on any particular number between N and N + N 1/4. By sieving first with the primes below N 1/4 we are left with the numbers in the interval +N, N + N 1/4, that have no prime factor up to N 1/4. The number of these

remaining numbers is O(N 1/4/ ln N ). Thus one can find all the primes in the interval in a time bound of O(N 1/4f (N )/ ln N ) + O(N 1/4 ln ln N ). Is there a way of doing this either in time o(N 1/4f (N )/ ln N ) or in time O(N 1/4 ln ln N )?

3.46.The ordinary sieve of Eratosthenes, as discussed above, may be segmented, so that but for the final list of primes collected, the space required along the way is O(N 1/2). And this can be accomplished without sacrificing on the time bound of O(N ln ln N ) bit operations. Can one prepare a table of primes up to N in o(N ) bit operations, and use only O(N 1/2) space along the way? Algorithm 3.2.2 meets the time bound goal, but not the space bound. (The paper [Atkin and Bernstein 2004] nearly solves this problem.)

3.47.Along the lines of the formalism of Section 3.7.2, derive an integral condition on x, ∆ and involving the Riemann ζ function such that there exist

170	Chapter 3 RECOGNIZING PRIMES AND COMPOSITES

no primes in the interval [x, x+∆]. Describe how such a criterion could be used for given x, ∆ to show numerically, but rigorously, whether or not primes exist in such an interval. Of course, any new theoretical inroads into the analysis of these “gaps” would be spectacular.

3.48.Suppose T is a probabilistic test that takes composite numbers n and, with probability p(n), provides a proof of compositeness for n. (For prime inputs, the test T reports only that it has not succeeded in finding a proof of compositeness.) Is there such a test T that has p(n) → 1 as n runs to infinity through the composite numbers, and such that the time to run T on n is no longer than doing k pseudoprime tests on n, for some fixed k?

3.49.For a positive integer n coprime to 12 and squarefree, define K(n) depending on n mod 12 according to one of the following equations:

K(n) = #{(u, v)	:	u > v > 0; n = u2 + v2},	for n ≡ 1, 5 (mod 12),
K(n) = #{(u, v)	:	u > 0, v > 0; n = 3u2 + v2}, for n ≡		7 (mod 12),
K(n) = #{(u, v)	:	u > v > 0; n = 3u2 − v2},	for n ≡ 11	(mod 12).

Then it is a theorem in [Atkin and Bernstein 2004] that n is prime if and only if K(n) is odd. First, prove this theorem using perhaps the fact (or related facts) that the number of representations of (any) positive n as a sum of two squares is

	d|n,
r2(n) = 4	(−1)(d−1)/2,
	d odd

where we count all n = u2 + v2 including negative u or v representations; e.g. one has as a check the value r2(25) = 12.

A research question is this: Using the Atkin–Bernstein theorem can one fashion an e cient sieve for primes in an interval, by assessing the parity of K for many n at once? (See [Galway 2000].)

Another question is, can one fashion an e cient sieve (or even a primality test) using alternative descriptions of r2(n), for example by invoking various connections with the Riemann zeta function? See [Titchmarsh 1986] for a relevant formula connecting r2 with ζ.

Yet another research question runs like so: Just how hard is it to

“count up” all lattice points (in the three implied lattice regions) within a

√

given “radius” n, and look for representation numbers K(n) as numerical discontinuities at certain radii. This technique may seem on the face of it to belong in some class of brute-force methods, but there are e cient formulae— arising in analyses for the celebrated Gauss circle problem (how many lattice points lie inside a given radius?)—that provide exact counts of points in surprisingly rapid fashion. In this regard, show an alternative lattice theorem, that if n ≡ 1 (mod 4) is squarefree, then n is prime if and only if r2(n) = 8. A simple starting experiment that shows n = 13 to be prime by lattice counting, via analytic Bessel formulae, can be found in [Crandall 1994b, p. 68].

3.9 Research problems

171

3.50. The closing theme of the chapter, analytic prime-counting, involves the Riemann zeta function in a certain way. Pursuant to Exercise 1.60, consider the following research path, whereby we use information about the zeta function within, rather than to the right of, the critical strip.

Start with the Riemann–von Mangoldt formula, closely reminiscent of (1.23) and involving the π function in (3.25):

		∞		dt
π (x) = li0	(x) − ρ	li0(xρ) − ln 2 + x				,
			t(t2	−	1) ln t

observing the computational cautions of Exercise 1.36 such as the need to employ Ei for reliable results. The zeros ρ here are the Riemann critical zeros, and one may replace the sum with twice a sum over real parts.

The research problem then is: Find a computationally rapid algorithm to estimate π(x) extremely accurately using a collection of Riemann critical zeros. It is known that with a few zeros, say, one may actually compute π(x) as the integer-valued staircase that it is, at least up to some x depending on how many zeros are employed. A hard extension to this problem is then: Given x, how far does one have to go up the critical line with ρ values to compute a numerical approximation—call it πa(x)—in order to have

π(n) = πa(n + 1/2) hold exactly for every integer n [2, x]? We certainly

√

expect on theoretical grounds that one must need at least O( x) values of ρ, but the idea here is to have an analytically precise function πa(x) for a given range on x.

References on the use of Riemann critical zeros for prime-counting are [Riesel and G¨ohl 1970] and [Borwein et al. 2000].

Chapter 4

PRIMALITY PROVING

In Chapter 3 we discussed probabilistic methods for quickly recognizing composite numbers. If a number is not declared composite by such a test, it is either prime, or we have been unlucky in our attempt to prove the number composite. Since we do not expect to witness inordinate strings of bad luck, after a while we become convinced that the number is prime. We do not, however, have a proof; rather, we have a conjecture substantiated by numerical experiments. This chapter is devoted to the topic of how one might actually prove that a number is prime. Note that primality proving via elliptic curves is discussed in Section 7.6.

4.1 The n − 1 test

Small numbers can be tested for primality by trial division, but for larger numbers there are better methods (1012 is a possible size threshold, but this depends on the specific computing machinery used). One of these better methods is based on the same theorem as the simplest of all of the pseudoprimality tests, namely, Fermat’s little theorem (Theorem 3.4.1). Known as the n − 1 test, the method somewhat surprisingly suggests that we try our hand at factoring not n, but n − 1.

4.1.1The Lucas theorem and Pepin test

We begin with an idea of E. Lucas, from 1876.

Theorem 4.1.1 (Lucas theorem). If a, n are integers with n > 1, and

an−1 ≡ 1 (mod n), but a(n−1)/q ≡1 (mod n) for every prime q|n − 1, (4.1)

then n is prime.

Proof. The first condition in (4.1) implies that the order of a in Zn is a divisor of n − 1, while the second condition implies that the order of a is not a proper divisor of n − 1; that is, it is equal to n − 1. But the order of a is also a divisor of ϕ(n), by the Euler theorem (see (2.2)), so n − 1 ≤ ϕ(n). But if n is composite and has the prime factor p, then both p and n are integers in {1, 2, . . . , n} that are not coprime to n, so from the definition of Euler’s totient function ϕ(n), we have ϕ(n) ≤ n − 2. This is incompatible with n − 1 ≤ ϕ(n), so it must be the case that n is prime.

174	Chapter 4 PRIMALITY PROVING

Remark. The version of Theorem 4.1.1 above is due to Lehmer. Lucas had such a result where q runs through all of the proper divisors of n − 1.

The hypothesis (4.1) of the Lucas theorem is not vacuous for prime numbers; such a number a is called a primitive root, and all primes have them. That is, if n is prime, the multiplicative group Zn is cyclic; see Theorem 2.2.5. In fact, each prime n > 200560490131 has more than n/(2 ln ln n) primitive roots in {1, 2, . . . , n − 1}; see Exercise 4.1. (Note: The prime 200560490131 is 1 greater than the product of the first 11 primes.)

A consequence is that if n > 200560490131 is prime, it is easy to find a number satisfying (4.1) via a probabilistic algorithm. Just choose random integers a in the range 1 ≤ a ≤ n − 1 until a successful one is found. The expected number of trials is less than 2 ln ln n.

Though we know no deterministic polynomial-time algorithm for finding a primitive root for a prime, the principal hindrance in implementing the Lucas theorem as a primality test is not the search for a primitive root a, but rather finding the complete prime factorization of n − 1. As we know, factorization is hard in practice for many numbers. But it is not hard for every number. For example, consider a search for primes that are 1 more than a power of 2. As seen in Theorem 1.3.4, such a prime must be of the form Fk = 22k +1. Numbers in this sequence are called Fermat numbers after Fermat, who thought they were all prime.

In 1877, Pepin gave a criterion similar to the following for the primality of a Fermat number.

2k	+ 1 is prime
Theorem 4.1.2 (Pepin test). For k ≥ 1, the number Fk = 2
if and only if 3(Fk −1)/2 ≡ −1 (mod Fk).

Proof. Suppose the congruence holds. Then (4.1) holds with n = Fk, a = 3, so Fk is prime by the Lucas Theorem 4.1.1. Conversely, assume Fk is prime.

Since 2k	is even, it follows that 2	2k	≡ 1 (mod 3),	so that F		k ≡	2 (mod 3). But
				3
also Fk ≡ 1 (mod 4), so the Legendre symbol					is −1, that is, 3 is not a
				Fk
square (mod Fk). The congruence in the theorem thus follows from Euler’s
criterion (2.6).

Actually, Pepin gave his test with the number 5 in place of the number 3 (and with k ≥ 2). It was noticed by Proth and Lucas that one can use 3. In this regard, see [Williams 1998] and Exercise 4.5.

As of this writing, the largest Fk for which the Pepin test has been used is F24. As discussed in Section 1.3.2, this number is composite, and in fact, so is every other Fermat number beyond F4 for which the character (prime or composite) has been resolved.

4.1.2Partial factorization

Since the hardest step, in general, in implementing the Lucas Theorem 4.1.1 as a primality test is coming up with the complete prime factorization of n−1,

4.1 The n − 1 test

175

one might wonder whether any use can be made of a partial factorization of n − 1. In particular, say

n − 1 = F R, and the complete prime factorization of F is known. (4.2)

If F is fairly large as a function of n, we may fashion a primality proof for n along the lines of (4.1), if indeed n happens to be prime. Our first result on these lines allows us to deduce information on the prime factorization of n.

Theorem 4.1.3 (Pocklington). Suppose (4.2) holds and a is such that

an−1 ≡ 1 (mod n) and gcd(a(n−1)/q − 1, n) = 1 for each prime q|F. (4.3)

Then every prime factor of n is congruent to 1 (mod F ).

Proof. Let p be a prime factor of n. From the first part of (4.3) we have that the order of aR in Zp is a divisor of (n − 1)/R = F . From the second part of (4.3) it is not a proper divisor of F , so is equal to F . Hence F divides the

p		−	1.
order of Z , which is p
Corollary 4.1.4.	If (4.2) and (4.3) hold and F ≥ √				, then n is prime.
				n

Proof. Theorem 4.1.3 implies that each prime factor of n is congruent to 1

(mod F ), and so each prime factor of n exceeds F . But F ≥

√

, so each

n

prime factor of n exceeds √

, so n must be prime.

n

The next result allows a still smaller value of F .

Theorem 4.1.5 (Brillhart, Lehmer, and Selfridge).

Suppose

(4.2) and

(4.3)

both hold

and suppose that n

1/3

≤ F < n

1/2

. Consider the base F

2

representation of n, namely n = c2F

+ c1F + 1, where c1, c2 are integers in

[0, F − 1]. Then n is prime if and only if c12 − 4c2 is not a square.

Proof.

Since n

≡

1 (mod F ), it follows that the base-F “units” digit of n

2

+ c1F + 1, as

is 1. Thus n has its base-F representation in the form c2F

claimed. Suppose n is composite. From Theorem 4.1.3, all the prime factors of n are congruent to 1 (mod F ), so must exceed n1/3. We conclude that n has exactly two prime factors:

n = pq, p = aF + 1, q = bF + 1, a ≤ b.

We thus have

c2F 2 + c1F + 1 = n = (aF + 1)(bF + 1) = abF 2 + (a + b)F + 1.

Our goal is to show that we must have c2 = ab and c1 = a + b, for then it will

follow that c2

is a square.

1 − 4c2

3

≥ n > abF

2

, so that ab ≤ F − 1. It follows that either

a

3

First note that F

≤

F

−

1 or a = 1, b = F

−1/3

−

1)F +1) =

+b

1. In the latter case, n = (F +1)((F

F

+ 1, contradicting F ≥ n

. Hence both ab and a + b are positive integers

176	Chapter 4 PRIMALITY PROVING

smaller than F . From the uniqueness of the base-F representation of a number it follows that c2 = ab and c1 = a + b as claimed.

Now suppose, conversely, that c21 − 4c2 is a square, say u2. Then

	2			2
n =	c1 + u	F + 1	c1	− u	F + 1 .

The two fractions are both integers, since c1 ≡ u (mod 2). It remains to note that this factorization is nontrivial, since c2 > 0 implies |u| < c1. Thus, n is composite.

To apply Theorem 4.1.5 as a primality test one should have a fast method of verifying whether the integer c21 − 4c2 in the theorem is a square. This is a orded by Algorithm 9.2.11.

The next result allows F to be even smaller.

Theorem 4.1.6 (Konyagin and Pomerance). Suppose that n ≥ 214, both (4.2) and (4.3) hold, and n3/10 ≤ F < n1/3. Say the base-F expansion of n is c3F 3 + c2F 2 + c1F + 1, and let c4 = c3F + c2. Then n is prime if and only if the following conditions hold:

(1)(c1 + tF )2 + 4t − 4c4 is not a square for t = 0, 1, 2, 3, 4, 5.

(2)Let u/v be the continued fraction convergent to c1/F such that v is maximal subject to v < F 2/√n. If d = c4v/F + 1/2 , then the polynomial vx3 + (uF − c1v)x2 + (c4v − dF + u)x − d Z[x] has no integral root a such that aF + 1 is a nontrivial factor of n.

Proof. Since every prime factor of n is congruent to 1 (mod F ) (by Theorem 4.1.3), we have that n is composite if and only if there are positive integers a1 ≤ a2 with n = (a1F + 1)(a2F + 1). Suppose n is composite and (1) and

(2) hold. We begin by establishing some identities and inequalities. We have

n = c4F 2 + c1F + 1 = a1a2F 2 + (a1 + a2)F + 1,

and there is some integer t ≥ 0 with

a1a2 = c4 − t,

a1 + a2 = c1 + tF.

Since (1) holds, we have t ≥ 6. Thus

a2 ≥

a1 + a2

≥

c1 + 6F

≥ 3F

2

2

and

n

n

≤

a1 <

.

a2F 2

3F 3

We have from (4.4) that

t ≤

a1 + a2

≤

a1a2

+ 1

<

c4

<

n

.

F

F

F

F 3

(4.4)

(4.5)

(4.6)

4.1 The n − 1 test

177

Also, (4.4) implies that

a1c1 + a1tF = a12 + c4 − t.

(4.7)

With the notation of condition (2), we have from (4.7) that

a1u + a1tv

c4v

= a1v

u

c1

+ (a1c1 + a1tF )

v

c4v

−

F

u

− c1

−c4v

v

v

F

F

F

u

c1

v

= a1v

v

−

F

+ (a12 + c4 − t)

F

−

F

= a1v

−

+ (a12 − t)

.

(4.8)

v

F

F

Note that (4.5), (4.6), and t ≥ 6 imply that

0

|a12 − t| < max{a12, t} ≤ max

1

n

2

n

1

n

2

(4.9)

,

≤

.

9

F 3

F 3

6

F 3

First suppose that u/v = c1/F . Then (4.8) and (4.9) imply that

a1u + a1tv −

c4v

= |a12 − t|

v

1

n

2

v

n2

F 2

n3/2

1

<

<

·

√

=

≤

.

F

F

6

F 3

F

6F 7

6F 5

6

n

(4.10)

If u/v =c1/F , let u /v be the next continued fraction convergent to c1/F after u/v, so that

F 2

u

c1

1

√

n

v < √n ≤ v ,

v

− F

≤ vv

≤ vF 2 .

Thus, from (4.5), (4.8), and the calculation in (4.10),

c4v

√

1

n3/2

1

1

n

≤

a1u + a1tv − F

≤ a1v vF 2

+ 6 <

3F 5 +

6

2 .

Let d = a1u

|

−

|

< 1/2, which implies that d =

+ a1tv, so that

d

c4v/F

c4v/F + 1/2 . Multiplying (4.7) by a1v, we have

va31 − c1va21 − a21tvF − a1tv + c4a1v = 0,

and using −a1tv = ua1 − d, we get

va31 + (uF − c1v)a21 + (c4v − dF + u)a1 − d = 0.

Hence (2) does not hold after all, which proves that if n is composite, then either (1) or (2) does not hold.

Now suppose n is prime. If t {0, 1, 2, 3, 4, 5} and (c1 +tF )2 −4c4 +4t = u2, with u integral, then

n = (c4 − t)F 2 + (c1 + tF )F + 1									−		F + 1 .
=		c	1	+ 2	F + 1		1	2
				tF + u		c		+ tF		u

178 Chapter 4 PRIMALITY PROVING

Since n is prime, this must be a trivial factorization of n, that is,

c1 + tF − |u| = 0,

which implies c4 = t. But c4 ≥ F ≥ n3/10 ≥ 2143/10 > 5 ≥ t, a contradiction. So if (1) fails, n must be composite. It is obvious that if n is prime, then (2) holds.

As with Theorem 4.1.5, if Theorem 4.1.6 is to be used as a primality test, one should use Algorithm 9.2.11 as a subroutine to recognize squares. In addition, one should use Newton’s method or a divide and conquer strategy to search for integral roots of the cubic polynomial in condition (2) of the theorem. We next embody Theorems 4.1.3-4.1.6 in one algorithm.

Algorithm 4.1.7 (The n − 1 test). Suppose we have an integer n ≥ 214 and that (4.2) holds with F ≥ n3/10. This probabilistic algorithm attempts to decide whether n is prime (YES) or composite (NO).

1.	[Pocklington test]
	Choose random a [2, n − 2];
	if(an−1	≡			// n is composite.
		1 (mod n)) return NO;
	for(prime q|F ) {
	g = gcd (a(n−1)/q mod n)		−	1, n ;
	if(1 < g < n) return NO;
	if(g == n) goto [Pocklington test]
2.	}	// Exhausting the ‘for’ loop means relation (4.3) holds.
	[First magnitude test]
3.	if(F ≥ n1/2) return YES;
	[Second magnitude test]
	if(n1/3 ≤ F < n1/2) {		2	+ c1F + 1;
	Cast n in base F : n = c2F

if(c21 − 4c2 not a square) return YES; return NO;

}

4. [Third magnitude test]

if(n3/10 ≤ F < n1/3) {

If conditions (1) and (2) of Theorem 4.1.6 hold, return YES; return NO;

}

Though Algorithm 4.1.7 is probabilistic, any returned value YES (n is prime) or NO (n is composite) is a rigorous declaration. We remark that the various powerings a(n−1)/q mod n and the powering an−1 mod n in Step [Pocklington test] might be better organized so as to reduce the e ort spent, as in Algorithm 2.2.10.