Lecture Notes in Computer Science 3000 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen UniversityofDortmund,Germany MadhuSudan MassachusettsInstituteofTechnology,MA,USA DemetriTerzopoulos NewYorkUniversity,NY,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA MosheY.Vardi RiceUniversity,Houston,TX,USA GerhardWeikum Max-PlanckInstituteofComputerScience,Saarbruecken,Germany 3 Berlin Heidelberg NewYork HongKong London Milan Paris Tokyo Martin Dietzfelbinger Primality Testing in Polynomial Time From RandomizedAlgorithms to "PRIMES is in P" 1 3 Author MartinDietzfelbinger TechnischeUniversita¨tIlmenau Fakulta¨tfu¨rInformatikundAutomatisierung 98684Ilmenau,Germany E-mail:[email protected] LibraryofCongressControlNumber:2004107785 CRSubjectClassification(1998):F.2.1,F.2,F.1.3,E.3,G.3 ISSN0302-9743 ISBN3-540-40344-2Springer-VerlagBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer-Verlag.Violationsare liabletoprosecutionundertheGermanCopyrightLaw. Springer-VerlagisapartofSpringerScience+BusinessMedia springeronline.com (cid:1)c Springer-VerlagBerlinHeidelberg2004 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyBollerMediendesign Printedonacid-freepaper SPIN:10936009 06/3142 543210 To Angelika, Lisa, Matthias, and Johanna Preface OnAugust6,2002,apaperwiththetitle“PRIMESisinP”,byM.Agrawal, N.Kayal, and N.Saxena, appeared on the website of the Indian Institute of Technologyat Kanpur,India. In this paper it wasshownthat the “primality problem” has a “deterministic algorithm” that runs in “polynomial time”. Findingoutwhetheragivennumbernisaprimeornotisaproblemthat was formulated in ancient times, and has caught the interest of mathemati- ciansagainandagainforcenturies.Onlyinthe20thcentury,withtheadvent ofcryptographicsystemsthatactuallyusedlargeprime numbers,diditturn out to be of practical importance to be able to distinguish prime numbers andcompositenumbersofsignificantsize.Readily,algorithmswereprovided that solved the problem very efficiently and satisfactorily for all practical purposes, and provably enjoyed a time bound polynomial in the number of digitsneededtowritedowntheinputnumbern.Theonlydrawbackofthese algorithms is that they use “randomization” — that means the computer that carries out the algorithm performs random experiments, and there is a slight chance that the outcome might be wrong, or that the running time mightnotbepolynomial.Tofindanalgorithmthatgetsbywithoutrandom- ness, solves the problem error-free, and has polynomial running time had been an eminent open problem in complexity theory for decades when the paper by Agrawal,Kayal,andSaxenahit the web.The news ofthis amazing result spread very fast around the world among scientists interested in the theory of computation, cryptology, and number theory; within days it even reachedTheNewYorkTimes,whichisquiteunusualforatopicintheoretical computer science. Practically,notmuchhaschanged.Incryptographicapplications,thefast randomized algorithms for primality testing continue to be used, since they are superior in running time and the error can be kept so small that it is irrelevant for practical applications. The new algorithm does not seem to imply that we can factor numbers fast, and no cryptographic system has beenbroken.Still,the newalgorithmis ofgreatimportance,bothbecauseof its long history and because of the methods used in the solution. As is quite common in the field of number-theoretic algorithms, the for- mulation of the deterministic primality test is very compact and uses only very simple basic procedures. The analysis is a little more complex, but as- VIII Preface toundingly it gets by with a small selection of the methods and facts taught in introductory algebra and number theory courses. On the one hand, this raises the philosophical question whether other important open problems in theoreticalcomputersciencemayhavesolutionsthatrequireonlybasicmeth- ods. On the other hand, it opens the rare opportunity for readers without a specializedmathematicaltrainingto fullyunderstandthe proofofanewand important result. It is the main purpose of this text to guide its reader all the way from the definitions of the basic concepts from number theory and algebra to a full understanding of the new algorithm and its correctness proof and time analysis,providingdetailsforalltheintermediatesteps.Ofcourse,thereader still has to go the whole way,which may be steep in some places;some basic mathematical training is required and certainly a good measure of persever- ance. To make a contrast, and to provide an introduction to some practically relevant primality tests for the complete novice to the field, also two of the classical primality testing algorithms are described and analyzed, viz., the “Miller-Rabin Test” and the “Solovay-Strassen Test”. Also for these algo- rithms and their analysis, all necessary background is provided. Ihopethatthistextmakestheareaofprimalitytestingandinparticular the wonderfulnew resultof Agrawal,Kayal,and Saxena a little easier to ac- cess for interestedstudents ofcomputer science,cryptology,ormathematics. I wish to thank the students of two courses in complexity theory at the TechnicalUniversityofIlmenau,whostruggledthroughpreliminaryversions of parts of the material presented here. Thanks are due to Juraj Hromkoviˇc for proposing that this book be written as well as his permanent encourage- ment on the way. Thomas Hofmeister and Juraj Hromkoviˇc read parts of the manuscript and gave many helpful hints for improvements. (Of course, the responsibility for any errors remains with the author.) The papers by D.G. Bernstein, generously made accessible on the web, helped me a lot in shaping an understanding of the subject matter. I wish to thank Alfred Hofmann of Springer-Verlag for his patience and the inexhaustible enthusi- asm with which he accompanied this project. And, finally, credit is due to M.Agrawal, N.Kayal, and N.Saxena, who found this beautiful result. Ilmenau, March 2004 Martin Dietzfelbinger Contents 1. Introduction: Efficient Primality Testing.................. 1 1.1 Algorithms for the Primality Problem..................... 1 1.2 Polynomial and Superpolynomial Time Bounds ............ 2 1.3 Is PRIMES in P?....................................... 6 1.4 Randomized and Superpolynomial Time Algorithms for the Primality Problem ............................... 7 1.5 The New Algorithm .................................... 9 1.6 Finding Primes and Factoring Integers .................... 10 1.7 How to Read This Book................................. 11 2. Algorithms for Numbers and Their Complexity........... 13 2.1 Notation for Algorithms on Numbers...................... 13 2.2 O-notation ............................................ 15 2.3 Complexity of Basic Operations on Numbers............... 18 3. Fundamentals from Number Theory ...................... 23 3.1 Divisibility and Greatest Common Divisor................. 23 3.2 The Euclidean Algorithm................................ 27 3.3 Modular Arithmetic .................................... 32 3.4 The Chinese Remainder Theorem......................... 35 3.5 Prime Numbers ........................................ 38 3.5.1 Basic Observations and the Sieve of Eratosthenes..... 39 3.5.2 The Fundamental Theorem of Arithmetic ........... 42 3.6 Chebychev’s Theorem on the Density of Prime Numbers..... 45 4. Basics from Algebra: Groups, Rings, and Fields .......... 55 4.1 Groups and Subgroups .................................. 55 4.2 Cyclic Groups.......................................... 59 4.2.1 Definitions, Examples, and Basic Facts.............. 59 4.2.2 Structure of Cyclic Groups ........................ 62 4.2.3 Subgroups of Cyclic Groups ....................... 64 4.3 Rings and Fields ....................................... 66 4.4 Generators in Finite Fields .............................. 69 X Contents 5. The Miller-Rabin Test.................................... 73 5.1 The Fermat Test ....................................... 73 5.2 Nontrivial Square Roots of 1............................. 78 5.3 Error Bound for the Miller-Rabin Test .................... 82 6. The Solovay-Strassen Test ................................ 85 6.1 Quadratic Residues ..................................... 85 6.2 The Jacobi Symbol ..................................... 87 6.3 The Law of Quadratic Reciprocity........................ 88 6.4 Primality Testing by Quadratic Residues .................. 92 7. More Algebra: Polynomials and Fields.................... 95 7.1 Polynomials over Rings.................................. 95 7.2 Division with Remainder and Divisibility for Polynomials.... 102 7.3 Quotients of Rings of Polynomials ........................ 105 7.4 Irreducible Polynomials and Factorization ................. 108 7.5 Roots of Polynomials ................................... 111 7.6 Roots of the Polynomial Xr−1 .......................... 112 8. Deterministic Primality Testing in Polynomial Time...... 115 8.1 The Basic Idea......................................... 115 8.2 The Algorithm of Agrawal,Kayal, and Saxena ............. 117 8.3 The Running Time ..................................... 118 8.3.1 Overall Analysis.................................. 118 8.3.2 Bound for the Smallest Witness r .................. 119 8.3.3 Improvements of the Complexity Bound............. 120 8.4 The Main Theorem and the Correctness Proof ............. 122 8.5 Proof of the Main Theorem.............................. 123 8.5.1 Preliminary Observations.......................... 124 8.5.2 Powers of Products of Linear Terms ................ 124 8.5.3 A Field F and a Large Subgroup G of F∗ ........... 126 8.5.4 Completing the Proof of the Main Theorem.......... 130 A. Appendix................................................. 133 A.1 Basics from Combinatorics............................... 133 A.2 Some Estimates ........................................ 136 A.3 Proof of the Quadratic Reciprocity Law ................... 137 A.3.1 A Lemma of Gauss ............................... 137 A.3.2 Quadratic Reciprocity for Prime Numbers ........... 139 A.3.3 Quadratic Reciprocity for Odd Integers ............. 141 References.................................................... 143 Index......................................................... 145 1. Introduction: Efficient Primality Testing 1.1 Algorithms for the Primality Problem A natural number n > 1 is called a prime number if it has no positive divisors other than 1 and n. If n is not prime, it is called composite, and can be written n = a·b for natural numbers 1 < a,b < n. Ever since this concept was defined in ancient Greece, the primality problem “Given a number n, decide whether n is a prime number or not” has been considered a natural and intriguing computational problem. Here is a simple algorithm for the primality problem: Algorithm 1.1.1 (Trial Division) Input: Integer n≥2. Method: 0 i: integer; 1 i ←2; 2 while i·i≤n repeat 3 if i divides n 4 then return 1; 5 i ←i+1; 6 return 0; This algorithm, when presented with an input number n, gives rise to√the followingcalculation:Inthe loopinlines2–5the numbers i=2,3,...,(cid:4) n(cid:6), in this order, are tested for being a divisor of n. As soon as a divisor is found, the calculation stops and returns the value 1. If no divisor is found, the answer 0 is returned. The algorithm solves the primality problem in the following sense: n is a prime number if and only if Algorithm 1.1.1 returns 0. This is because√if n=a·b for 1<a,b<n, then one of the factors a and b is notlargerthan n,andhencesuchafactormustbefoundbythealgorithm. Formoderatelylargenthisproceduremaybeusedforacalculationbyhand; using a modern computer, it is feasible to carry it out for numbers with 20 or 25 decimal digits. However,when confronted with a number like M. Dietzfelbinger: Primality Testing in Polynomial Time, LNCS 3000, pp. 1-12, 2004.  Springer-Verlag Berlin Heidelberg 2004