A Computational Introduction to Number Theory and Algebra

by Victor Shoup

• ISBN13: 9780521516440
• ISBN10: 0521516447
• Edition: 2nd
• Format: Hardcover
• Copyright: 2009-02-16
• Publisher: Cambridge University Press

Summary

This introductory book emphasizes algorithms and applications, such as cryptography and error correcting codes, and is accessible to a broad audience. The presentation alternates between theory and applications in order to motivate and illustrate the mathematics. The mathematical coverage includes the basics of number theory, abstract algebra and discrete probability theory. This edition now includes over 150 new exercises, ranging from the routine to the challenging, that flesh out the material presented in the body of the text, and which further develop the theory and present new applications. The material has also been reorganized to improve clarity of exposition and presentation. Ideal as a textbook for introductory courses in number theory and algebra, especially those geared towards computer science students.

Author Biography

Victor Shoup is a Professor in the Department of Computer Science at the Courant Institute of Mathematical Sciences, New York University.

Table of Contents

Preface	p. x
Preliminaries	p. xiv
Basic properties of the integers	p. 1
Divisibility and primality	p. 1
Ideals and greatest common divisors	p. 5
Some consequences of unique factorization	p. 10
Congruences	p. 15
Equivalence relations	p. 15
Definitions and basic properties of congruences	p. 16
Solving linear congruences	p. 19
The Chinese remainder theorem	p. 22
Residue classes	p. 25
Euler's phi function	p. 31
Euler's theorem and Fermat's little theorem	p. 32
Quadratic residues	p. 35
Summations over divisors	p. 45
Computing with large integers	p. 50
Asymptotic notation	p. 50
Machine models and complexity theory	p. 53
Basic integer arithmetic	p. 55
Computing in Zn	p. 64
Faster integer arithmetic (*)	p. 69
Notes	p. 71
Euclid's algorithm	p. 74
The basic Euclidean algorithm	p. 74
The extended Euclidean algorithm	p. 77
Computing modular inverses and Chinese remaindering	p. 82
Speeding up algorithms via modular computation	p. 84
An effective version of Fermat's two squares theorem	p. 86
Rational reconstruction and applications	p. 89
The RSA cryptosystem	p. 99
Notes	p. 102
The distribution of primes	p. 104
Chebyshev's theorem on the density of primes	p. 104
Bertrand's postulate	p. 108
Mertens' theorem	p. 110
The sieve of Eratosthenes	p. 115
The prime number theorem ...and beyond	p. 116
Notes	p. 124
Abelian groups	p. 126
Definitions, basic properties, and examples	p. 126
Subgroups	p. 132
Cosets and quotient groups	p. 137
Group homomorphisms and isomorphisms	p. 142
Cyclic groups	p. 153
The structure of finite abelian groups (*)	p. 163
Rings	p. 166
Definitions, basic properties, and examples	p. 166
Polynomial rings	p. 176
Ideals and quotient rings	p. 185
Ring homomorphisms and isomorphisms	p. 192
The structure of Z*n	p. 203
Finite and discrete probability distributions	p. 207
Basic definitions	p. 207
Conditional probability and independence	p. 213
Random variables	p. 221
Expectation and variance	p. 233
Some useful bounds	p. 241
Balls and bins	p. 245
Hash functions	p. 252
Statistical distance	p. 260
Measures of randomness and the leftover hash lemma (*)	p. 266
Discrete probability distributions	p. 270
Notes	p. 275
Probabilistic algorithms	p. 277
Basic definitions	p. 278
Generating a random number from a given interval	p. 285
The generate and test paradigm	p. 287
Generating a random prime	p. 292
Generating a random non-increasing sequence	p. 295
Generating a random factored number	p. 298
Some complexity theory	p. 302
Notes	p. 304
Probabilistic primality testing	p. 306
Trial division	p. 306
The Miller-Rabin test	p. 307
Generating random primes using the Miller-Rabin test	p. 311
Factoring and computing Euler's phi function	p. 320
Notes	p. 324
Finding generators and discrete logarithms in Z*p	p. 327
Finding a generator for Z*p	p. 327
Computing discrete logarithms in Z*p	p. 329
The Diffie-Hellman key establishment protocol	p. 334
Notes	p. 340
Quadratic reciprocity and computing modular square roots	p. 342
The Legendre symbol	p. 342
The Jacobi symbol	p. 346
Computing the Jacobi symbol	p. 348
Testing quadratic residuosity	p. 349
Computing modular square roots	p. 350
The quadratic residuosity assumption	p. 355
Notes	p. 357
Modules and vector spaces	p. 358
Definitions, basic properties, and examples	p. 358
Submodules and quotient modules	p. 360
Module homomorphisms and isomorphisms	p. 363
Linear independence and bases	p. 367
Vector spaces and dimension	p. 370
Matrices	p. 377
Basic definitions and properties	p. 377
Matrices and linear maps	p. 381
The inverse of a matrix	p. 386
Gaussian elimination	p. 388
Applications of Gaussian elimination	p. 392
Notes	p. 398
Subexponential-time discrete logarithms and factoring	p. 399
Smooth numbers	p. 399
An algorithm for discrete logarithms	p. 400
An algorithm for factoring integers	p. 407
Practical improvements	p. 414
Notes	p. 418
More rings	p. 421
Algebras	p. 421
The field of fractions of an integral domain	p. 427
Unique factorization of polynomials	p. 430
Polynomial congruences	p. 435
Minimal polynomials	p. 438
General properties of extension fields	p. 440
Formal derivatives	p. 444
Formal power series and Laurent series	p. 446
Unique factorization domains (*)	p. 451
Notes	p. 464
Polynomial arithmetic and applications	p. 465
Basic arithmetic	p. 465
Computing minimal polynomials in F[x]/(f)(I)	p. 468
Euclid's algorithm	p. 469
Computing modular inverses and Chinese remaindering	p. 472
Rational function reconstruction and applications	p. 474
Faster polynomial arithmetic (*)	p. 478
Notes	p. 484
Linearly generated sequences and applications	p. 486
Basic definitions and properties	p. 486
Computing minimal polynomials: a special case	p. 490
Computing minimal polynomials: a more general case	p. 492
Solving sparse linear systems	p. 497
Computing minimal polynomials in F[X]/(f)(II)	p. 500
The algebra of linear transformations (*)	p. 501
Notes	p. 508
Finite fields	p. 509
Preliminaries	p. 509
The existence of finite fields	p. 511
The subfield structure and uniqueness of finite fields	p. 515
Conjugates, norms and traces	p. 516
Algorithms for finite fields	p. 522
Tests for and constructing inrreducible polynomials	p. 522
Computing minimal polynomials in F[X](f)(III)	p. 525
Factoring polynomials: square-free decomposition	p. 526
Factoring polynomials: the Cantor-Zassenhaus algorithm	p. 530
Factoring polynomials: Berlekamp's algorithm	p. 538
Deterministic factorization algorithms (*)	p. 544
Notes	p. 546
Deterministic primality testing	p. 548
The basic idea	p. 548
The algorithm and its analysis	p. 549
Notes	p. 558
Appendix: Some useful facts	p. 561
Bibliography	p. 566
Index of notation	p. 572
Index	p. 574
Table of Contents provided by Ingram. All Rights Reserved.