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 .. 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 ( )

3 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 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 Laurent Unique factorization domains ( ) Notes46417 Polynomial arithmetic and Basic Computing minimal polynomials inF[X]/(f)(I)

4 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: 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 .

5 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. 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.

6 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. 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.

7 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, 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.

8 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). It also includes an Introduction to discrete probability Theory thismaterial is needed to properly treat the topics of probabilistic algorithms and cryp-tographic applications. The treatment of all these topics is more or less standard,except that the text only deals with commutative structures ( , abelian groups andcommutative rings with unity) this is all that is really needed for the purposes ofthis text, and the Theory of these structures is much simpler and more transparentthan that of more general, non-commutative choice of topics covered in this book was motivated primarily by theirapplicability to computing and communications, especially to the specific areasof cryptography and coding Theory .

9 Thus, the book may be useful for referenceor self-study by readers who want to learn about cryptography, or it could also beused as a textbook in a graduate or upper-division undergraduate course on (com-putational) Number Theory and algebra, perhaps geared towards computer this is an Introduction , and not an encyclopedic reference for specialists,some topics simply could not be covered. One such, whose exclusion will undoubt-edly be lamented by some, is the Theory of lattices, along with algorithms for andapplications of lattice basis reduction. Another omission is fast algorithms forxiiPrefaceinteger and polynomial arithmetic although some of the basic ideas of this topicare developed in the exercises, the main body of the text deals only with classical,quadratic-time algorithms for integer and polynomial arithmetic .

10 However, thereare more advanced texts that cover these topics perfectly well, and they should bereadily accessible to students who have mastered the material in this that while continued fractions are not discussed, the closely related prob-lem of rational reconstruction is covered, along with a Number of interestingapplications (which could also be solved using continued fractions).Guidelines for using the text. There are a few sections that are marked with a ( ), indicating that thematerial covered in that section is a bit technical, and is not needed else-where. There are many examples in the text, which form an integral part of thebook, and should not be skipped. There are a Number of exercises in the text that serve to reinforce, as wellas to develop important applications and generalizations of, the materialpresented in the text.