Prime Numbers

2.3 Squares and roots			107
t = p − b2;
if(t ≡0 (mod d)) return { };			// Return empty.
if(t/d not a square) return { };			// Return empty.
return (±b, ±	t/d	);	// Solution(s) found.

This completely solves the computational Diophantine problem at hand. Note that an integer square-root finding routine (Algorithm 9.2.11) is invoked at two junctures. The second invocation—the determination as to whether t/d is a perfect square—can be done along the lines discussed in the text following the Algorithm 9.2.11 description. Incidentally, the proof that Algorithm 2.3.12 works is, in words from [Cohen 2000], “a little painful.” There is an elegant argument, due to H. Lenstra, in [Schoof 1995], and a clear explanation from an algorist’s point of view (for d = 1) in [Bressoud and Wagon 2000, p. 283].

The second case, namely for the Diophantine equation x2 + |D|y2 = 4p, for D < 0, can be handled in the following way [Cohen 2000]. First we observe that if D ≡ 0 (mod 4), then x is even, whence the problem comes down to solving (x/2)2 +(|D|/4)y2 = p, which we have already done. If D ≡ 1 (mod 8), we have x2 − y2 ≡ 4 (mod 8), and so x, y are both even, and again we defer to the previous method. Given the above argument, one could use the next algorithm only for D ≡ 5 (mod 8), but in fact, the following will work for what turn out to be convenient cases D ≡ 0, 1 (mod 4):

Algorithm 2.3.13. (Represent 4p as x2 + |D|y2 (modified Cornacchia– Smith)) Given a prime p and −4p < D < 0 with D ≡ 0, 1 (mod 4), this algorithm either reports that no solution exists, or returns a solution (x, y).

1.	[Case p = 2]
	if(p == 2) {
	if(D + 8 is a square) return (√
	return { };
2.	}
	[Test for solvability]
3.	if( Dp < 1) return { };
	[Initial square root]
	x0 = √				mod p;
		D
4.	if(x0 ≡D (mod 2)) x0 = p − x0;
	[Initialize Euclid chain]
	(a, b) = (2p, x );
	0
	c = 2√				;
			p
5.	[Euclid chain]
	while(b > c) (a, b) = (b, a mod b);
6.	[Final report]
	t = 4p − b2;

if(t ≡0 (mod |D|)) return { }; if(t/|D| not a square) return { };

return (±b, ± t/|D|);

D+ 8, 1);

//Return empty: no solution.

//Return empty.

//Via Algorithm 2.3.8 or 2.3.9.

//Ensure x20 ≡ D (mod 4p).

//Via Algorithm 9.2.11.

//Return empty.

//Return empty.

//Found solution(s).

108	Chapter 2 NUMBER-THEORETICAL TOOLS

Again, the algorithm either says that there is no solution, or reports the essentially unique solution to x2 + |D|y2 = 4p.

2.4Exercises

2.1.Prove that 16 is, modulo any odd number, an eighth power.

2.2.Show that the least common multiple lcm (a, b) satisfies

ab lcm (a, b) = gcd(a, b) ,

and generalize this formula for more than two arguments. Then, using the prime number theorem (PNT), find a reasonable estimate for the lcm of all the integers from 1 through (a large) n.

2.3. Recall that ω(n) denotes the number of distinct prime factors of n. Prove that for any positive squarefree integer n,

#{(x, y) : x, y positive integers, lcm (x, y) = n} = 3ω(n).

2.4.Study the relation between the Euclid algorithm and simple continued fractions, with a view to proving the Lam´e theorem (the first part of Theorem 2.1.3).

2.5.Fibonacci numbers are defined u0 = 0, u1 = 1, and un+1 = un + un−1 for n ≥ 1. Prove the remarkable relation

gcd(ua, ub) = ugcd(a,b),

which shows, among many other things, that un, un+1 are coprime for n > 1, and that if un is prime, then n is prime. Find a counterexample to the converse (find a prime p such that up is composite). By analyzing numerically several Fibonacci numbers, guess—then prove—a simple, general formula for the inverse of un (mod un+1).

Fibonacci numbers appear elsewhere in this book, e.g., in Sections 1.3.3, 3.6.1 and Exercises 3.25, 3.41, 9.50.

2.6.Show that for x ≈ y ≈ N , and assuming classical divide with remainder,

the bit-complexity of the classical Euclid algorithm is O ln2 N . It is helpful to observe that to find the quotient–remainder pair q, r with x = qy+r requires O((1 + ln q) ln x) bit operations, and that the quotients are constrained in a certain way during the Euclid loop.

2.7.Prove that Algorithm 2.1.4 works; that is, the correct gcd and inverse pair are returned. Answer the following question: When, if ever, do the returned a, b have to be reduced further, to a mod y and b mod x, to yield legitimate, unique inverses?

2.8.Argue that for a naive application of Theorem 2.1.6 the mod operations involved consume at least O ln2 M bit operations if arithmetic be done in

2.4 Exercises

109

grammar-school fashion, but only O r ln2 m via Algorithm 2.1.7, where m denotes the maximum of the mi.

2.9.Write a program to e ect the asymptotically fast, preconditioned CRT Algorithm 9.5.26, and use this to multiply two numbers each of, say, 100 decimal digits, using su ciently many small prime moduli.

2.10.Following Exercise 1.48 one can use, for CRT moduli, Mersenne numbers having pairwise coprime exponents (the Mersenne numbers need not themselves be prime). What computational advantages might there be

in choosing such a moduli set (see Section 9.2.3)? Is there an easy way to find inverses (2a − 1)−1 (mod 2b − 1)?

2.11.Give the computational complexity of the “straightforward inverse”

algorithm implied by relation (2.3). Is there ever a situation when one should use this, or use instead Algorithm 2.1.4 to obtain a−1 mod m?

2.12.Let Nk(p) be the number of monic irreducible polynomials in Fp[x]

of degree k. Using formula (2.5), show that pk/k ≥ Nk(p) > pk/k − 2pk/2/k for every prime p and every positive integer k. Show too that we always have Nk(p) > 0.

2.13.Does formula (2.5) generalize to give the number of irreducible polynomials of degree k in Fpn [x]?

2.14.Show how Algorithm 2.2.2 plays a role in finite field arithmetic, namely in the process of finding a multiplicative inverse of an element in Fpn .

2.15.Prove Theorem 2.2.8.

2.16.Show how Algorithms 2.3.8 and 2.3.9 may be appropriately generalized to find square roots of squares in the finite field Fpn .

2.17.By considering the binary expansion of the exponent n, show that the computational complexity of Algorithm 2.1.5 is O(ln n) operations. Argue that if x, n are each of size m and we are to compute xn mod m, and classical multiply-mod is used, that the overall bit complexity of this powering grows as the cube of the number of bits in m.

2.18.Say we wish to compute a power xy mod N , with N = pq, the product of two distinct primes. Describe an algorithm that combines a binary ladder and Chinese remainder theorem (CRT) ideas, and that yields the desired power more rapidly than does a standard, (mod N )-based ladder.

2.19.The “repunit” number r1031 = (101031 − 1)/9, composed of 1031 decimal ones, is known to be prime. Determine, via reciprocity, which of

7, −7 is a quadratic residue of this repunit. Then give an explicit square root (mod r1031) of the quadratic residue.

110	Chapter 2 NUMBER-THEORETICAL TOOLS

2.20.Using appropriate results of Theorem 2.3.4, prove that for prime p > 3,

p				−		(p−1) mod 6
	−	3	= (		1)
						4	.
Find a similar closed form for			p5 when p = 2, 5.

2.21. Show that for prime p ≡ 1 (mod 4), the sum of the quadratic residues in [1, p − 1] is p(p − 1)/4.

2.22. Show that if a is a nonsquare integer, then										ap = −1 for infinitely many
primes p. (Hint: First assume that a is positive									and odd. Show that there is
an integer b such that				ab	= −1 and b ≡ 1 (mod 4). Then any positive integer
		b (mod 4a)	satisfies		a
n					n =			1, and so is divisible by a prime p with
	≡						−
a
p	= −1. Show that			infinitely many primes p arise in this way. Then deal

with the cases when a is even or negative.)

2.23.Use Exercise 2.22 to show that if f (x) is an irreducible quadratic

polynomial in Z[x], then there are infinitely many primes p such that f (x) mod p is irreducible in Zp[x]. Show that x4 + 1 is irreducible in Z[x], but is reducible in each Zp[x]. What about cubic polynomials?

2.24.Develop an algorithm for computing the Jacobi symbol ma along the lines of the binary gcd method of Algorithm 9.4.2.

2.25.Prove: For prime p with p ≡ 3 (mod 4), given any pair of square roots of a given x ≡0 (mod p), one root is itself a quadratic residue and the other is not. (The root that is the quadratic residue is known as the principal square root.) See Exercises 2.26 and 2.42 for applications of the principal root.

2.26.We denote by Zn the multiplicative group of the elements in Zn that are coprime to n.

(1)Suppose n is odd and has exactly k distinct prime factors. Let J denote

the set of elements x Zn with the Jacobi symbol nx = 1 and let S denote the set of squares in Zn. Show that J is a subgroup of Zn of ϕ(n)/2 elements, and that S is a subgroup of J.

(2)Show that squares in Zn have exactly 2k square roots in Zn and conclude that #S = ϕ(n)/2k.

(3)Now suppose n is a Blum integer; that is, n = pq is a product of two di erent primes p, q ≡ 3 (mod 4). (Blum integers have importance in cryptography (see [Menezes et al. 1997] and our Section 8.2).) From parts

(1) and (2), #S = 12 #J, so that half of J’s elements are squares, and half are not. From part (2), an element of S has exactly 4 square roots. Show that exactly one of these square roots is itself in S.

(4)For a Blum integer n = pq, show that the squaring function s(x) = x2 mod n is a permutation on the set S, and that its inverse function is

s−1(y) = y((p−1)(q−1)+4)/8 mod n.

2.4 Exercises

111

2.27.Using Theorem 2.3.7 prove the two equalities in relations (2.12).

2.28.Here we prove the celebrated quadratic reciprocity relation (2.11) for two distinct odd primes p, q. Starting with Definition 2.3.6, show that G is multiplicative; that is, if gcd(m, n) = 1, then

G(m; n)G(n; m) = G(1; mn).

(Hint: mj2/n + nk2/m is similar—in a specific sense—to (mj + nk)2/(mn).) Infer from this and Theorem 2.3.7 the relation (now for primes p, q)

q		p		= (−1)(p−1)(q−1)/4.
	p		q

These are examples par excellence of the potential power of exponential sums; in fact, this approach is one of the more e cient ways to arrive at reciprocity. Extend the result to obtain the formula of Theorem 2.3.4 for p2 . Can this approach be extended to the more general reciprocity statement (i.e., for coprime m, n) in Theorem 2.3.4? Incidentally, Gauss sums for nonprime arguments m, n can be evaluated in closed form, using the techniques of Exercise 1.66 or the methods summarized in references such as [Graham and Kolesnik 1991].

2.29. This exercise is designed for honing one’s skills in manipulating Gauss sums. The task is to count, among quadratic residues modulo a prime p, the exact number of arithmetic progressions of given length. The formal count of length-3 progressions is taken to be

& '

A(p) = # (r, s, t) : pr = ps = pt = 1; r =s; s − r ≡ t − s (mod p) .

Note we are taking 0 ≤ r, s, t ≤ p − 1, we are ignoring trivial progressions (r, r, r), and that 0 is not a quadratic residue. So the prime p = 11, for which the quadratic residues are {1, 3, 4, 5, 9}, enjoys a total of A(11) = 10 arithmetic progressions of length three. (One of these is 4, 9, 3; i.e., we allow wraparound (mod 11); and also, descenders such as 5, 4, 3 are allowed.)

First, prove that

A(p) =	p − 1 +		1 p−1	e2πik(r−2s+t)/p,
−
	2		p
			k=0 r,s,t

where each of r, s, t runs through the quadratic residues. Then, use relations (2.12) to prove that

8

−

−

p

−

p

A(p) =

p − 1

p

6

2

2

−1

.

Finally, derive for the exact progression count the attractive expression

	−	8
A(p) = (p		1)	p − 2	.

112	Chapter 2 NUMBER-THEORETICAL TOOLS

An interesting extension to this exercise is to analyze progressions of longer length. Another direction: How many progressions of a given length would be expected to exist amongst a random half of all residues {1, 2, 3, . . . , p − 1} (see Exercise 2.41)?

2.30.Prove that square-root Algorithms 2.3.8 and 2.3.9 work.

2.31.Prove that the following algorithm (certainly reminiscent of the text Algorithm 2.3.9) works for square roots (mod p), for p an odd prime. Let x be the quadratic residue for which we desire a square root. Define a particular Lucas sequence (Vk) by V0 = 2, V1 = h, and for k > 1

	Vk = hVk−1 − xVk−2,
where h is such that h2−p	4x = −1. Then compute a square root of x as
	y =	1	V(p+1)/2 (mod p).
	2

Note that the Lucas numbers can be computed via a binary Lucas chain; see Algorithm 3.6.7.

2.32. Implement Algorithm 2.3.8 or 2.3.9 or some other variant to solve each of

x2 ≡ 3615 (mod 216 + 1),

x2 ≡ 552512556430486016984082237 (mod 289 − 1).

2.33.Show how to enhance Algorithm 2.3.8 by avoiding some of the powerings called for, perhaps by a precomputation.

2.34.Prove that a primitive root of an odd prime p is a quadratic nonresidue.

2.35.Prove that Algorithm 2.3.12 (alternatively 2.3.13) works. As intimated in the text, the proof is not entirely easy. It may help to first prove a specialcase algorithm, namely for finding representations p = a2 + b2 when p ≡ 1 (mod 4). Such a representation always exists and is unique.

2.36.Since we have algorithms that extract square roots modulo primes, give an algorithm for extracting square roots (mod n), where n = pq is the product of two explicitly given primes. (The Chinese remainder theorem (CRT) will be useful here.) How can one extract square roots of a prime power n = pk? How can one extract square roots modulo n if the complete prime factorization of n is known?

Note that in ignorance of the factorization of n, square root extraction is extremely hard—essentially equivalent to factoring itself; see Exercise 6.5.

2.37.Prove that for odd prime p, the number of roots of ax2 + bx + c ≡ 0

(mod p), where a ≡0 (mod p), is given by 1 + Dp , where D = b2 − 4ac is the

2.5 Research problems

discriminant. For the case 1 + all the roots.

113

D > 0, give an algorithm for calculation of

p

2.38. Find a prime p such that the least primitive root of p exceeds the number of binary bits in p. Find an example of such a prime p that is also a Mersenne prime (i.e., some p = Mq = 2q − 1 whose least primitive root exceeds q). These findings show that the least primitive root can exceed lg p. For more exploration along these lines see Exercise 2.39.

2.5Research problems

2.39. Implement a primitive root-finding algorithm, and study the statistical occurrence of least primitive roots.

The study of least primitive roots is highly interesting. It is known on the GRH that 2 is a primitive root of infinitely many primes, in fact for a

positive proportion α = (1 − 1/p(p − 1)) ≈ 0.3739558, the product running over all primes (see Exercise 1.90). Again on the GRH, a positive proportion whose least primitive root is not 2, has 3 as a primitive root and so on; see [Hooley 1976]. It is conjectured that the least primitive root for prime p is O((ln p)(ln ln p)); see [Bach 1997a]. It is known, on the GRH, that the least primitive root for prime p is O ln6 p ; see [Shoup 1992]. It is known unconditionally that the least primitive root for prime p is O(p1/4+ ) for every > 0, and for infinitely many primes p it exceeds c ln p ln ln ln p for some positive constant c, the latter a result of S. Graham and C. Ringrosee. The study of the least primitive root is not unlike the study of the least quadratic nonresidue—in this regard see Exercise 2.41.

2.40.Investigate the use of CRT in the seemingly remote domains of integer convolution, or fast Fourier transforms, or public-key cryptography. A good reference is [Ding et al. 1996].

2.41.Here we explore what might be called “statistical” features of the Legendre symbol. For odd prime p, denote by N (a, b) the number of residues

whose successive quadratic characters are (a, b); that is, we wish to count those integers x [1, p − 2] such that

p , x

p

= (a, b),

x

+ 1

with each of a, b attaining possible values ±1. Prove that

p−2

x

x + 1

4N (a, b) = x=1

1 + a p 1 + b

p

and therefore that

p

4

−

−

−

−

N (a, b) =

1

p

2

b

ab

a

−1

.

114	Chapter 2 NUMBER-THEORETICAL TOOLS

Establish the corollary that the number of pairs of consecutive quadratic residues is (p − 5)/4, (p − 3)/4, respectively, as p ≡ 1, 3 (mod 4). Using the formula for N (a, b), prove that for every prime p the congruence

x2 + y2 ≡ −1 (mod p)

is solvable.

One satisfying aspect of the N (a, b) formula is the statistical notion that sure enough, if the Legendre symbol is thought of as generated by a “random coin flip,” there ought to be about p/4 occurrences of a given pair (±1, ±1).

All of this makes sense: The Legendre symbol is in some sense random. But in another sense, it is not quite so random. Let us estimate a sum:

sA,B = A x<B	p ,
	x
≤

which can be thought of, in some heuristic sense we suppose, as a random walk with N = B − A steps. On the basis of remarks following Theorem 2.3.7, show that

	1 p−1			sin(πN b/p)			1 p−1
|sA,B | ≤ √p b=0				sin(πb/p)		≤ √p b=0

Finally, arrive at the P´olya–Vinogradov inequality:

|sA,B | < √p ln p.

1

| sin(πb/p)| .

Actually, the inequality is often expressed more generally, where instead of the Legendre symbol as character, any nonprincipal character applies. This attractive inequality says that indeed, the “statistical fluctuation” of the quadratic residue/nonresidue count, starting from any initial x = A, is always bounded by a “variance factor” √p (times a log term). One can prove more than this; for example, using an inequality in [Cochrane 1987] one can obtain

s

|

<

4

√

ln p + 0.41√

+ 0.61,

p

p

| A,B

π2

and it is known that on the GRH, sA,B

= O √

ln ln p ; see [Davenport

p

1980]. In

any case, we

deduce that out

of any N consecutive

integers,

N/2 + O(p

1/2

ln p) are quadratic residues (mod p). We also conclude that the

least quadratic nonresidue (mod p) is bounded above by, at worst,

√

ln p.

p

Further results on this interesting inequality are discussed in [Hildebrand 1988a, 1988b].

The P´olya–Vinogradov inequality thus restricted to quadratic characters tells us that not just any coin-flip sequence can be a Legendre-symbol sequence. The inequality says that we cannot, for large p say, have a Legendresymbol sequence such as (1, 1, 1, . . . , −1 − 1 − 1) (i.e., first half are 1’s second

2.5 Research problems

115

half −1’s). We cannot even build up more than an O √p ln p excess of one symbol over the other. But in a truly random coin-flip game, any pattern of 1’s and −1’s is allowed; and even if you constrain such a game to have equal numbers of 1’s and −1’s as does the Legendre-symbol game, there are still vast numbers of possible coin-flip sequences that cannot be symbol sequences. In some sense, however, the P´olya–Vinogradov inequality puts the Legendre symbol sequence smack in the middle of the distribution of possible sequences: It is what we might expect for a random sequence of coin flips. Incidentally, in view of the coin-flip analogy, what would be the expected value of the least quadratic nonresidue (mod p)? In this regard see Exercise 2.39. For a di erent kind of constraint on presumably random quadratic residues, see the remarks at the end of Exercise 2.29.

2.42. Here is a fascinating line of research: Using the age-old and glorious theory of the arithmetic–geometric mean (AGM), investigate the notion of what we might call a “discrete arithmetic–geometric mean (DAGM).” It was a tour de force of analysis, due to Gauss, Legendre, Jacobi, to conceive of the analytic AGM, which is the asymptotic fixed point of the elegant iteration

(a, b) → a 2 , √ab			,
	+ b

that is, one replaces the pair (a, b) of real numbers with the new pair of arithmetic and geometric means, respectively. The classical AGM, then, is the real number c to which the two numbers converge; sure enough, (c, c) →(c, c) so the process tends to stabilize for appropriate initial choices of a and b. This scheme is connected with the theory of elliptic integrals, the calculation of π to (literally) billions of decimal places, and so on [Borwein and Borwein 1987].

But consider doing this procedure not on real numbers but on residues modulo a prime p ≡ 3 (mod 4), in which case an x (mod p) that has a square root always has a so-called principal root (and so an unambiguous choice

of square root can be taken; see Exercise 2.25). Work out a theory of the

√

DAGM modulo p. Perhaps you would want to cast ab as a principal root if

√

said root exists, but something like a di erent principal root, say gab, for some fixed nonresidue g when ab is a nonresidue. Interesting theoretical issues are these: Does the DAGM have an interesting cycle structure? Is there any relation between your DAGM and the classical, analytic AGM? If there were any fortuitous connection between the discrete and analytic means, one might have a new way to evaluate with high e ciency certain finite hypergeometric series, as appear in Exercise 7.26.

Chapter 3

RECOGNIZING PRIMES AND COMPOSITES

Given a large number, how might one quickly tell whether it is prime or composite? In this chapter we begin to answer this fundamental question.

3.1Trial division

3.1.1Divisibility tests

A divisibility test is a simple procedure to be applied to the decimal digits of a number n so as to determine whether n is divisible by a particular small number. For example, if the last digit of n is even, so is n. (In fact, nonmathematicians sometimes take this criterion as the definition of being even, rather than being divisible by two.) Similarly, if the last digit is 0 or 5, then n is a multiple of 5.

The simple nature of the divisibility tests for 2 and 5 are, of course, due to 2 and 5 being factors of the base 10 of our numeration system. Digital divisibility tests for other divisors get more complicated. Probably the next most well-known test is divisibility by 3 or 9: The sum of the digits of n is congruent to n (mod 9), so by adding up digits themselves and dividing by 3 or 9 respectively reveals divisibility by 3 or 9 for the original n. This follows from the fact that 10 is one more than 9; if we happened to write numbers in base 12, for example, then a number would be congruent (mod 11) to the sum of its base-12 “digits.”

In general, divisibility tests based on digits get more and more complicated as the multiplicative order of the base modulo the test divisor grows. For example, the order of 10 (mod 11) is 2, so there is a simple divisibility test for 11: The alternating sum of the digits of n is congruent to n (mod 11). For 7, the order of 10 is 6, and there is no such neat and tidy divisibility test, though there are messy ones.

From a computational point of view, there is little di erence between a special divisibility test for the prime p and dividing by p to get the quotient and the remainder. And with dividing there are no special formulae or rules peculiar to the trial divisor p. So when working on a computer, or even for extensive hand calculations, trial division by various primes p is simpler and just as e cient as using various divisibility tests.