A Computational Introduction to Number Theory and …

1 A Computational Introduction to Number Theoryand Algebra(Version 2)Victor ShoupThis PDF document contains hyperlinks, and one may navigate through it by click-ing on theorem, definition, lemma, equation, and page numbers, as well as URLs,and chapter and section titles in the table of contents; most PDF viewers shouldalso display a list of bookmarks that allow direct access to chapters and 2008 by Victor of this work is distributed under the terms and conditions ofa Creative Commons license (Attribution-NonCommercial-NoDerivs ):You are free to copy, distribute, and display the electronic versionof this work under the following must give the original author may not use the electronic version of thiswork for commercial Derivative may not alter, transform, or build uponthe electronic version of this any reuse or distribution, you must make these license termsclear to of these conditions can be waived if you get permission fromthe more information about the license, other rights reserved.

2 In particular, the right to publish or distribute this workinprint formbelongs exclusively toCambridge University properties of the and and greatest common consequences of unique and basic properties of linear Chinese remainder s phi s theorem and Fermat s little over divisors453 Computing with large models and complexity integer integer arithmetic ( ) s basic Euclidean extended Euclidean modular inverses and Chinese up algorithms via modular effective version of Fermat s two squares reconstruction and RSA distribution of s theorem on the density of s sieve of prime Number theorem.

3 And , basic properties, and and quotient homomorphisms and structure of finite abelian groups ( ) , basic properties, and and quotient homomorphisms and structure ofZ n2038 Finite and discrete probability probability and and useful and of randomness and the leftover hash lemma ( ) Discrete probability Notes275 Contentsvii9 Probabilistic a random Number from a given generate and test a random a random non-increasing a random factored complexity primality Trial The Miller Rabin Generating random primes using the Miller Rabin Factoring and computing Euler s phi Notes32411 Finding generators and discrete logarithms inZ Finding a generator forZ Computing discrete logarithms inZ The Diffie Hellman key establishment Notes34012 Quadratic reciprocity and computing modular square The

4 Legendre The Jacobi Computing the Jacobi Testing quadratic Computing modular square The quadratic residuosity Notes35713 Modules and vector Definitions, basic properties, and Submodules and quotient Module homomorphisms and Linear independence and Vector spaces and Basic definitions and Matrices and linear The inverse of a Gaussian Applications of Gaussian Notes39815 Subexponential-time discrete logarithms and Smooth An algorithm for discrete An algorithm for factoring Practical Notes41816 More The field of fractions of an integral Unique factorization of Polynomial Minimal General properties of extension Formal Formal power series and

5 Laurent Unique factorization domains ( ) Notes46417 Polynomial arithmetic and Basic Computing minimal polynomials inF[X]/(f)(I) Euclid s Computing modular inverses and Chinese Rational function reconstruction and Faster polynomial arithmetic ( ) Notes48418 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 ( ) Notes50819 Finite The existence of finite The subfield structure and uniqueness of finite Conjugates, norms and traces51620 Algorithms for finite Tests for and constructing irreducible Computing minimal polynomials inF[X]/(f)(III) Factoring polynomials: square -free Factoring polynomials: the Cantor Zassenhaus Factoring polynomials.

6 Berlekamp s Deterministic factorization algorithms ( ) Notes54621 Deterministic primality The basic The algorithm and its Notes558 Appendix: Some useful facts561 Bibliography566 Index of notation572 Index574 PrefaceNumber Theory and algebra play an increasingly significant role in computingand communications, as evidenced by the striking applications of these subjectsto such fields as cryptography and coding Theory . My goal in writing this bookwas to provide an Introduction to Number Theory and algebra, with an emphasison algorithms and applications, that would be accessible to a broad audience.

7 Inparticular, I wanted to write a book that would be appropriate for typical students incomputer science or mathematics who have some amount of general mathematicalexperience, but without presuming too much specific mathematical prerequisites are minimal: no particular math-ematical concepts beyond what is taught in a typical undergraduate calculussequence are computer science prerequisites are also quite minimal: it is assumed that thereader is proficient in programming, and has had some exposure to the analysis ofalgorithms, essentially at the level of an undergraduate course on algorithms anddata though it is mathematically quite self contained, the text does presup-pose that the reader is comfortable with mathematical formalism and also hassome experience in reading and writing mathematical proofs.

8 Readers may havegained such experience in computer science courses such as algorithms, automataor complexity Theory , or some type of discrete mathematics for computer sciencestudents course. They also may have gained such experience in undergraduatemathematics courses, such as abstract or linear algebra. The material in these math-ematics courses may overlap with some of the material presented here; however,even if the reader already has had some exposure to this material, it neverthelessmay be convenient to have all of the relevant topics easily accessible in one place;moreover, the emphasis and perspective here will no doubt be different from thatin a traditional mathematical presentation of these of the of the mathematics required beyond basic calculusis developed from scratch.

9 Moreover, the book generally alternates between Theory and applications : one or two chapters on a particular set of purelymathematical concepts are followed by one or two chapters on algorithms andapplications; the mathematics provides the theoretical underpinnings for the appli-cations, while the applications both motivate and illustrate the mathematics. Ofcourse, this dichotomy between Theory and applications is not perfectly main-tained: the chapters that focus mainly on applications include the developmentof some of the mathematics that is specific to a particular application, and veryoccasionally, some of the chapters that focus mainly on mathematics include adiscussion of related algorithmic ideas as developing the mathematics needed to discuss certain applications, I havetried to strike a reasonable balance between, on the one hand, presenting the abso-lute minimum required to understand and rigorously analyze the applications, andon the other hand.

10 Presenting a full-blown development of the relevant mathemat-ics. In striking this balance, I wanted to be fairly economical and concise, while atthe same time, I wanted to develop enough of the Theory so as to present a fairlywell-rounded account, giving the reader more of a feeling for the mathematical big picture. The mathematical material covered includes the basics of Number Theory (including unique factorization, congruences, the distribution of primes, andquadratic reciprocity) and of abstract algebra (including groups, rings, fields, andvector spaces).