A Computational Introduction to Number Theory …

1 A Computational Introduction to Number Theoryand Algebra(Version 1)Victor ShoupThis PDF document contains hyperlinks, and one may navigate through itby clicking on theorem, definition, lemma, equation, and page numbers, aswell as URLs, and chapter and section titles in the table of contents; mostPDF viewers should also display a list of bookmarks that allow directaccess to chapters and 2005 by Victor rights reserved. The right to publish or distribute this work inprint formbelongs exclusively toCambridge University Press; however, thiselectronicversionis distributed under the terms and conditions of a Creative Commonslicense (Attribution-NonCommercial-NoDerivs ):You are free to copy, distribute, and display this electronicversion under the following must give the original author may not use this electronic version forcommercial Derivative may not alter, transform, orbuild upon this electronic any reuse or distribution, you must make clear to othersthe license terms of this of these conditions can be waived if you get permissionfrom the more information about the license.

2 Basic properties of the Divisibility and Ideals and greatest common Some consequences of unique factorization82 Definitions and basic Solving linear Residue Euler s phi Fermat s little Arithmetic functions and M obius inversion283 Computing with large Asymptotic Machine models and complexity Basic integer Computing Faster integer arithmetic ( ) Notes524 Euclid s The basic Euclidean The extended Euclidean Computing modular inverses and Chinese Speeding up algorithms via modular Rational reconstruction and Notes73vviContents5 The distribution of Chebyshev s theorem on the density of Bertrand s Mertens The sieve of The prime Number theorem .. and Notes946 Finite and discrete probability Finite probability distributions.

3 Basic Conditional probability and Random Expectation and Some useful The birthday Hash Statistical Measures of randomness and the leftover hash lemma ( ) Discrete probability Notes1477 Probabilistic Basic Approximation of Flipping a coin until a head Generating a random Number from a given Generating a random Generating a random non-increasing Generating a random factored The RSA Notes1798 Abelian Definitions, basic properties, and Cosets and quotient Group homomorphisms and Cyclic The structure of finite abelian groups ( )2089 Definitions, basic properties, and Polynomial Ideals and quotient Ring homomorphisms and isomorphisms23610 Probabilistic primality Trial The structure ofZ The Miller Rabin Generating random primes using the Miller Rabin Perfect power testing and prime power Factoring and computing Euler s phi Notes26611 Finding generators and discrete logarithms inZ Finding a generator forZ Computing discrete logarithmsZ The Diffie Hellman key establishment Notes28112 Quadratic residues and quadratic Quadratic The Legendre The Jacobi Notes28913 Computational problems related to quadratic Computing the Jacobi Testing quadratic Computing modular square The quadratic residuosity Notes29814 Modules and vector Definitions, basic properties.

4 And Submodules and quotient Module homomorphisms and Linear independence and Vector spaces and dimension30915 Basic definitions and Matrices and linear The inverse of a Gaussian Applications of Gaussian Notes33416 Subexponential-time discrete logarithms and Smooth An algorithm for discrete An algorithm for factoring Practical Notes35617 More The field of fractions of an integral Unique factorization of Polynomial Polynomial quotient General properties of extension Formal power series and Laurent Unique factorization domains ( ) Notes39718 Polynomial arithmetic and Basic Computing minimal polynomials inF[X]/(f) (I) Euclid s Computing modular inverses and Chinese remaindering Rational function reconstruction and Faster polynomial arithmetic ( ) Notes42119 Linearly generated sequences and Basic definitions and Computing minimal polynomials: a special Computing minimal polynomials: a more general Solving sparse linear Computing minimal polynomials inF[X]/(f) (II) The algebra of linear transformations ( ) Notes44720 Finite The existence of finite The subfield structure and uniqueness of finite Conjugates, norms and traces456 Contentsix21 Algorithms for finite Testing and constructing irreducible Computing minimal polynomials inF[X]/(f) (III) Factoring polynomials: the Cantor Zassenhaus algorithm Factoring polynomials.

5 Berlekamp s Deterministic factorization algorithms ( ) Faster square-free decomposition ( ) Notes48722 Deterministic primality The basic The algorithm and its Notes500 Appendix: Some useful facts501 Bibliography504 Index of notation510 Index512 PrefaceNumber Theory and algebra play an increasingly significant role in comput-ing and communications, as evidenced by the striking applications of thesesubjects to such fields as cryptography and coding Theory . My goal in writ-ing this book was to provide an Introduction to Number Theory and algebra,with an emphasis on algorithms and applications, that would be accessibleto a broad audience. In particular, I wanted to write a book that would beaccessible to typical students in computer science or mathematics who havea some amount ofgeneralmathematical experience, but without presumingtoo muchspecificmathematical mathematical prerequisites are minimal: no particularmathematical concepts beyond what is taught in a typical undergraduatecalculus sequence are computer science prerequisites are also quite minimal: it is assumedthat the reader is proficient in programming, and has had some exposureto the analysis of algorithms, essentially at the level of an undergraduatecourse on algorithms and data though it is mathematically quite self contained, the text does pre-suppose that the reader is comfortable with mathematical formalism andhas some experience in reading and writing mathematical proofs.

6 Read-ers may have gained such experience in computer science courses such asalgorithms, automata or complexity Theory , or some type of discrete math-ematics for computer science students course. They also may have gainedsuch experience in undergraduate mathematics courses, such as abstract orlinear algebra these courses overlap with some of the material presentedhere, but even if the reader already has had some exposure to this material,it nevertheless may be convenient to have all of the relevant material easilyaccessible in one place, and moreover, the emphasis and perspective herexPrefacexiwill no doubt be different than in a typical mathematics course on of the of the mathematics required beyond basic cal-culus is developed from scratch. Moreover, the book generally alternatesbetween Theory and applications : one or two chapters on a particularset of purely mathematical concepts are followed by one or two chapters onalgorithms and applications the mathematics provides the theoretical un-derpinnings for the applications, while the applications both motivate andillustrate the mathematics.

7 Of course, this dichotomy between Theory andapplications is not perfectly maintained: the chapters that focus mainlyon applications include the development of some of the mathematics thatis specific to a particular application, and very occasionally, some of thechapters that focus mainly on mathematics include a discussion of relatedalgorithmic ideas as developing the mathematics needed to discuss certain applications, Itried to strike a reasonable balance between, on the one hand, presentingthe absolute minimum required to understand and rigorously analyze theapplications, and on the other hand, presenting a full-blown developmentof the relevant mathematics. In striking this balance, I wanted to be fairlyeconomical and concise, while at the same time, I wanted to develop enoughof the Theory so as to present a fairly well-rounded account, giving the readermore of a feeling for the mathematical big picture.

8 The mathematical material covered includes the basics of Number Theory (including unique factorization, congruences, the distribution of primes, andquadratic reciprocity) and abstract algebra (including groups, rings, fields,and vector spaces). It also includes an Introduction to discrete probabilitytheory this material is needed to properly treat the topics of probabilisticalgorithms and cryptographic applications. The treatment of all these topicsis more or less standard, except that the text only deals with commutativestructures ( , abelian groups and commutative rings with unity) this isall that is really needed for the purposes of this text, and the Theory of thesestructures is much simpler and more transparent than that of more general,non-commutative choice of topics covered in this book was motivated primarily bytheir applicability to computing and communications, especially to the spe-cific areas of cryptography and coding Theory .

9 For example, the book maybe useful for reference or self-study by readers who want to learn aboutcryptography. The book could also be used as a textbook in a graduatexiiPrefaceor upper-division undergraduate course on ( Computational ) Number theoryand algebra, perhaps geared towards computer science this is an introductory textbook, and not an encyclopedic referencefor specialists, some topics simply could not be covered. One such topicwhose exclusion will undoubtedly be lamented by some is the Theory oflattices, along with algorithms for and applications of lattice basis such topic is that of fast algorithms for integer and polynomialarithmetic although some of the basic ideas of this topic are developed inthe exercises, the main body of the text deals only with classical, quadratic-time algorithms for integer and polynomial arithmetic.

10 As an introductorytext, some topics just had to go; moreover, there are more advanced textsthat cover these topics perfectly well, and these texts should be readilyaccessible to students who have mastered the material in this that while continued fractions are not discussed, the closely relatedproblem of rational reconstruction is covered, along with a Number of in-teresting applications (which could also be solved using continued fractions).Using the are a few tips on using the text. There are a few sections that are marked with a ( ), indicatingthat the material covered in that section is a bit technical, and is notneeded elsewhere. There are many examples in the text. These form an integral part ofthe text, and should not be skipped. There are a Number of exercises in the text that serve to reinforce,as well as to develop important applications and generalizations of,the material presented in the text.