Elementary Number Theory: Primes, Congruences, and Secrets

1 This is page iPrinter: Opaque thisElementary Number Theory: Primes, Congruences, and SecretsWilliam SteinJanuary 23, 2017vTo my wife Clarita LefthandviThis is page viiPrinter: Opaque thisContentsPrefaceix1 Prime Prime Factorization .. The Sequence of Prime Numbers .. Exercises ..192 The Ring of Integers Congruences Modulon.. The Chinese Remainder Theorem .. Quickly Computing Inverses and Huge Powers .. Primality Testing .. The Structure of (Z/pZ) .. Exercises ..443 Public-key Playing with Fire .. The Diffie-Hellman Key Exchange .. The RSA Cryptosystem .. Attacking RSA .. Exercises ..674 Quadratic Statement of the Quadratic Reciprocity Law .. Euler s Criterion .. First Proof of Quadratic Reciprocity.

2 A Proof of Quadratic Reciprocity Using Gauss Sums .. Finding Square Roots .. Exercises ..895 Continued The Definition .. Finite Continued Fractions .. Infinite Continued Fractions .. The Continued Fraction ofe.. Quadratic Irrationals .. Recognizing Rational Numbers .. Sums of Two Squares .. Exercises .. 1216 Elliptic The Definition .. The Group Structure on an Elliptic Curve .. Integer Factorization Using Elliptic Curves .. Elliptic Curve Cryptography .. Elliptic Curves Over the Rational Numbers .. Exercises .. 146 Answers and Hints149 References155 Index160 This is page ixPrinter: Opaque thisPrefaceThis is a book about prime numbers, congruences, secret messages, andelliptic curves that you can read cover to cover.

3 It grew out of undergrad-uate courses that the author taught at Harvard, UC San Diego, and theUniversity of systematic study of Number theory was initiated around Euclid proved that there are infinitely many prime numbers, andalso cleverly deduced the fundamental theorem of arithmetic, which assertsthat every positive integer factors uniquely as a product of primes. Over athousand years later (around ) Arab mathematicians formulatedthecongruent Number problemthat asks for a way to decide whether or nota given positive integernis the area of a right triangle, all three of whosesides are rational numbers. Then another thousand years later (in 1976),Diffie and Hellman introduced the first ever public-key cryptosystem, whichenabled two people to communicate secretely over a public communicationschannel with no predetermined secret; this invention and the ones thatfollowed it revolutionized the world of digital communication.

4 In the 1980sand 1990s, elliptic curves revolutionized Number theory , providing strikingnew insights into the congruent Number problem, primality testing, public-key cryptography, attacks on public-key systems, and playing a central rolein Andrew Wiles resolution of Fermat s Last , pure and applied Number theory is an exciting mix of simultane-ously broad and deep theory , which is constantly informed and motivatedby algorithms and explicit computation. Active research is underway thatpromises to resolve the congruent Number problem, deepen our understand-ing into the structure of prime numbers, and both challenge and improvexPrefaceour ability to communicate securely. The goal of this book is to bring thereader closer to this reader is strongly encouraged to do every exercise in this book,checking their answers in the back (where many, but not all, solutionsare given).

5 Also, throughout the text there, are examples of calculationsdone using the powerful free open source mathematical software systemSage ( ), and the reader should try every suchexample and experiment with similar reader should know how to read and write mathemati-cal proofs and must know the basics of groups, rings, and fields. Thus, theprerequisites for this book are more than the prerequisites for most ele-mentary Number theory books, while still being aimed at and letN={1,2,3,..}denote the naturalnumbers, and use the standard notationZ,Q,R, andCfor the rings ofinteger, rational, real, and complex numbers, respectively. In this book, wewill use the words proposition, theorem, lemma, and corollary as a proposition is a less important or less fundamental assertion, atheorem is a deeper culmination of ideas, a lemma is something that we willuse later in this book to prove a proposition or theorem, and a corollaryis an easy consequence of a proposition, theorem, or lemma.

6 More difficultexercises are marked with a (*). would like to thank Brian Conrad, Carl Pomer-ance, and Ken Ribet for many clarifying comments and suggestions. Bau-rzhan Bektemirov, Lawrence Cabusora, and Keith Conrad read drafts ofthis book and made many comments, and Carl Witty commented exten-sively on the first two chapters. Frank Calegari used the course whenteaching Math 124 at Harvard, and he and his students provided muchfeedback. Noam Elkies made comments and suggested Exercise SethKleinerman wrote a version of Section as a class project. HendrikLenstra made helpful remarks about how to present his factorization al-gorithm. Michael Abshoff, Sabmit Dasgupta, David Joyner, Arthur Pat-terson, George Stephanides, Kevin Stern, Eve Thompson, Ting-You Wang,and Heidi Williams all suggested corrections.

7 I also benefited from conver-sations with Henry Cohn and David Savitt. I used Sage ([Sag08]), emacs,and LATEX in the preparation of this is page 1 Printer: Opaque this1 Prime NumbersEvery positive integer can be written uniquely as a product of prime num-bers, , 100 = 22 52. This is surprisingly difficult to prove, as we willsee below. Even more astounding is that actuallyfindinga way to writecertain 1,000-digit numbers as a product of primes seems out of the reach ofpresent technology, an observation that is used by millions of people everyday when they buy things prime numbers are the building blocks of integers, it is natural towonder how the primes are distributed among the integers. There are two facts about the distribution of prime first is that, [they are] the most arbitrary and ornery ob-jects studied by mathematicians: they grow like weeds amongthe natural numbers, seeming to obey no other law than that ofchance, and nobody can predict where the next one will second fact is even more astonishing, for it states just theopposite: that the prime numbers exhibit stunning regularity,that there are laws governing their behavior, and that they obeythese laws with almost military precision.

8 Don Zagier [Zag75]The Riemann Hypothesis, which is the most famous unsolved problem innumber theory , postulates a very precise answer to the question of how theprime numbers are chapter lays the foundations for our study of the theory of numbersby weaving together the themes of prime numbers, integer factorization,and the distribution of primes. In Section , we rigorously prove that the21. Prime Numbersevery positive integer is a product of primes, and give examples of specificintegers for which finding such a decomposition would win one a large cashbounty. In Section , we discuss theorems about the set of prime numbers,starting with Euclid s proof that this set is infinite, and discuss the largestknown prime. Finally we discuss the distribution of primes via the primenumber theorem and the Riemann Prime PrimesThe set ofnatural numbersisN={1,2,3,4.}

9 },and the set ofintegersisZ={.., 2, 1,0,1,2,..}.Definition (Divides).Ifa,b Zwe say thatadividesb, writtena|b, ifac=bfor somec Z. In this case, we sayais adivisorofb. Wesay thatadoes not divideb, writtena-b, if there is noc Zsuch thatac= example, we have 2|6 and 3|15. Also, all integers divide 0, and 0divides only 0. However, 3 does not divide 7 notationb.:afor bis divisible bya is common inRussian literature on Number (Prime and Composite).An integern >1 isprimeifthe only positive divisors ofnare 1 andn. We callncompositeifnis Number 1 is neither prime nor composite. The first few primes ofNare2,3,5,7,11,13,17,19,23,29,31,37,41 ,43,47,53,59,61,67,71,73,79,..,and the first few composites are4,6,8,9,10,12,14,15,16,18,20,21,22,24 ,25,26,27,28,30,32,33,34,.. H. Conway argues in [Con97, viii] that 1 should beconsidered a prime, and in the 1914 table [Leh14], Lehmer considers 1 tobe a prime.

10 In this book, we consider neither 1 nor 1 to be use Sage to compute all prime numbers betweenaandb Prime Factorization3sage: prime_range(10,50)[11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]We can also compute the composites in an : [n for n in range(10,30) if not is_prime(n)][10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28]Every natural Number is built, in a unique way, out of prime numbers:Theorem (Fundamental Theorem of Arithmetic).Every naturalnumber can be written as a product of primes uniquely up to that primes are the products with only one factor and 1 is theempty , which we will prove in Section , is trick-ier to prove than you might first think. For example, unique factorizationfails in theringZ[ 5] ={a+b 5 :a,b Z} C,where 6 factors in two different ways:6 = 2 3 = (1 + 5) (1 5).