Teoria De Numeros

A Computational Introduction to Number Theory and Algebra
(Version 2)
Victor Shoup

This PDF document contains hyperlinks, and one may navigate through it by clicking 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 should also display a list of “bookmarks” that allow direct access tochapters and sections.

Copyright © 2008 by Victor Shoup The electronic version of this work is distributed under the terms and conditions of a Creative Commons license (Attribution-NonCommercial-NoDerivs 3.0): You are free to copy, distribute, and display the electronic version of this work under the following conditions: Attribution. You must give the original author credit. Noncommercial. You maynot use the electronic version of this work for commercial purposes. No Derivative Works. You may not alter, transform, or build upon the electronic version of this work. For any reuse or distribution, you must make these license terms clear to others. Any of these conditions can be waived if you get permission from the author. For more information about the license, visitcreativecommons.org/licenses/by-nd-nc/3.0. All other rights reserved. In particular, the right to publish or distribute this work in print form belongs exclusively to Cambridge University Press.

Contents

Preface Preliminaries 1 Basic properties of the integers 1.1 Divisibility and primality 1.2 Ideals and greatest common divisors 1.3 Some consequences of unique factorization Congruences 2.1 Equivalence relations2.2 Definitions and basic properties of congruences 2.3 Solving linear congruences 2.4 The Chinese remainder theorem 2.5 Residue classes 2.6 Euler’s phi function 2.7 Euler’s theorem and Fermat’s little theorem 2.8 Quadratic residues 2.9 Summations over divisors Computing with large integers 3.1 Asymptotic notation 3.2 Machine models and complexity theory 3.3 Basic integer arithmetic 3.4 Computing inZn 3.5 Faster integer arithmetic (∗) 3.6 Notes Euclid’s algorithm 4.1 The basic Euclidean algorithm 4.2 The extended Euclidean algorithm 4.3 Computing modular inverses and Chinese remaindering v

page x xiv 1 1 5 10 15 15 16 19 22 25 31 32 35 45 50 50 53 55 64 69 71 74 74 77 82

2

3

4

vi

Contents

4.4 4.5 4.6 4.7 4.8 5

Speeding up algorithms via modular computation Aneffective version of Fermat’s two squares theorem Rational reconstruction and applications The RSA cryptosystem Notes

84 86 89 99 102 104 104 108 110 115 116 124 126 126 132 137 142 153 163 166 166 176 185 192 203 207 207 213 221 233 241 245 252 260 266 270 275

The distribution of primes 5.1 Chebyshev’s theorem on the density of primes 5.2 Bertrand’s postulate 5.3 Mertens’ theorem 5.4 The sieve ofEratosthenes 5.5 The prime number theorem . . . and beyond 5.6 Notes Abelian groups 6.1 Definitions, basic properties, and examples 6.2 Subgroups 6.3 Cosets and quotient groups 6.4 Group homomorphisms and isomorphisms 6.5 Cyclic groups 6.6 The structure of finite abelian groups (∗) Rings 7.1 Definitions, basic properties, and examples 7.2 Polynomial rings 7.3 Ideals and quotient rings 7.4 Ringhomomorphisms and isomorphisms 7.5 The structure of Z∗ n Finite and discrete probability distributions 8.1 Basic definitions 8.2 Conditional probability and independence 8.3 Random variables 8.4 Expectation and variance 8.5 Some useful bounds 8.6 Balls and bins 8.7 Hash functions 8.8 Statistical distance 8.9 Measures of randomness and the leftover hash lemma (∗) 8.10 Discrete probability distributions 8.11Notes

6

7

8

Contents

vii

9

Probabilistic algorithms 9.1 Basic definitions 9.2 Generating a random number from a given interval 9.3 The generate and test paradigm 9.4 Generating a random prime 9.5 Generating a random non-increasing sequence 9.6 Generating a random factored number 9.7 Some complexity theory 9.8 Notes Probabilistic primality testing 10.1 Trial division 10.2...