Available:*
Library | Item Barcode | Call Number | Material Type | Item Category 1 | Status |
---|---|---|---|---|---|
Searching... | 30000010205852 | QA241 S465 2009 | Open Access Book | Book | Searching... |
On Order
Summary
Summary
Number theory and algebra play an increasingly significant role in computing and communications, as evidenced by the striking applications of these subjects to such fields as cryptography and coding theory. 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 Notes
Victor Shoup is a Professor in the Department of Computer Science at the Courant Institute of Mathematical Sciences, New York University.
Reviews 1
Choice Review
Computer scientists are some of the most ardent consumers of number theory, formerly among the purest branches of pure mathematics. Compared with mathematics majors, computer science students will naturally come to number theory with distinct goals, culture, and background, and thus will welcome this purpose-built introduction. Shoup definitely takes pains to address the calculator generation taking up number theory without even intuition derived from such arcana as solid practice with manual long division. As computer science students have very likely not previously mastered probability theory, linear algebra, or basic abstract algebra, Shoup packages crash courses in each. Despite taking time for so many basics, Shoup climaxes with careful treatment of the late-breaking, ingenious, polynomial-time deterministic primality test of Agrawal, Kayal, and Saxena. Apart from number theory, one could easily build a fine discrete mathematics course on this book. An aside to librarians: from his Web site, Shoup freely distributes this book as a usefully hyperlinked PDF, with some supplementary material. Nevertheless, one really should buy the book--as the Internet age flowers, academic libraries must carry a new role as patrons of worthy intellectual endeavor, not just distributors of shared material. This reviewer advocates supporting rather than penalizing authors who generously make their work globally available. Summing Up: Highly recommended. General readers; lower- and upper-division undergraduates; professionals. D. V. Feldman University of New Hampshire
Table of Contents
Preface | p. x |
Preliminaries | p. xiv |
1 Basic properties of the integers | p. 1 |
1.1 Divisibility and primality | p. 1 |
1.2 Ideals and greatest common divisors | p. 5 |
1.3 Some consequences of unique factorization | p. 10 |
2 Congruences | p. 15 |
2.1 Equivalence relations | p. 15 |
2.2 Definitions and basic properties of congruences | p. 16 |
2.3 Solving linear congruences | p. 19 |
2.4 The Chinese remainder theorem | p. 22 |
2.5 Residue classes | p. 25 |
2.6 Euler's phi function | p. 31 |
2.7 Euler's theorem and Fermat's little theorem | p. 32 |
2.8 Quadratic residues | p. 35 |
2.9 Summations over divisors | p. 45 |
3 Computing with large integers | p. 50 |
3.1 Asymptotic notation | p. 50 |
3.2 Machine models and complexity theory | p. 53 |
3.3 Basic integer arithmetic | p. 55 |
3.4 Computing in Z n | p. 64 |
3.5 Faster integer arithmetic (*) | p. 69 |
3.6 Notes | p. 71 |
4 Euclid's algorithm | p. 74 |
4.1 The basic Euclidean algorithm | p. 74 |
4.2 The extended Euclidean algorithm | p. 77 |
4.3 Computing modular inverses and Chinese remaindering | p. 82 |
4.4 Speeding up algorithms via modular computation | p. 84 |
4.5 An effective version of Fermat's two squares theorem | p. 86 |
4.6 Rational reconstruction and applications | p. 89 |
4.7 The RSA cryptosystem | p. 99 |
4.8 Notes | p. 102 |
5 The distribution of primes | p. 104 |
5.1 Chebyshev's theorem on the density of primes | p. 104 |
5.2 Bertrand's postulate | p. 108 |
5.3 Mertens' theorem | p. 110 |
5.4 The sieve of Eratosthenes | p. 115 |
5.5 The prime number theorem ...and beyond | p. 116 |
5.6 Notes | p. 124 |
6 Abelian groups | p. 126 |
6.1 Definitions, basic properties, and examples | p. 126 |
6.2 Subgroups | p. 132 |
6.3 Cosets and quotient groups | p. 137 |
6.4 Group homomorphisms and isomorphisms | p. 142 |
6.5 Cyclic groups | p. 153 |
6.6 The structure of finite abelian groups (*) | p. 163 |
7 Rings | p. 166 |
7.1 Definitions, basic properties, and examples | p. 166 |
7.2 Polynomial rings | p. 176 |
7.3 Ideals and quotient rings | p. 185 |
7.4 Ring homomorphisms and isomorphisms | p. 192 |
7.5 The structure of Z * n | p. 203 |
8 Finite and discrete probability distributions | p. 207 |
8.1 Basic definitions | p. 207 |
8.2 Conditional probability and independence | p. 213 |
8.3 Random variables | p. 221 |
8.4 Expectation and variance | p. 233 |
8.5 Some useful bounds | p. 241 |
8.6 Balls and bins | p. 245 |
8.7 Hash functions | p. 252 |
8.8 Statistical distance | p. 260 |
8.9 Measures of randomness and the leftover hash lemma (*) | p. 266 |
8.10 Discrete probability distributions | p. 270 |
8.11 Notes | p. 275 |
9 Probabilistic algorithms | p. 277 |
9.1 Basic definitions | p. 278 |
9.2 Generating a random number from a given interval | p. 285 |
9.3 The generate and test paradigm | p. 287 |
9.4 Generating a random prime | p. 292 |
9.5 Generating a random non-increasing sequence | p. 295 |
9.6 Generating a random factored number | p. 298 |
9.7 Some complexity theory | p. 302 |
9.8 Notes | p. 304 |
10 Probabilistic primality testing | p. 306 |
10.1 Trial division | p. 306 |
10.2 The Miller-Rabin test | p. 307 |
10.3 Generating random primes using the Miller-Rabin test | p. 311 |
10.4 Factoring and computing Euler's phi function | p. 320 |
10.5 Notes | p. 324 |
11 Finding generators and discrete logarithms in Z * p | p. 327 |
11.1 Finding a generator for Z * p | p. 327 |
11.2 Computing discrete logarithms in Z * p | p. 329 |
11.3 The Diffie-Hellman key establishment protocol | p. 334 |
11.4 Notes | p. 340 |
12 Quadratic reciprocity and computing modular square roots | p. 342 |
12.1 The Legendre symbol | p. 342 |
12.2 The Jacobi symbol | p. 346 |
12.3 Computing the Jacobi symbol | p. 348 |
12.4 Testing quadratic residuosity | p. 349 |
12.5 Computing modular square roots | p. 350 |
12.6 The quadratic residuosity assumption | p. 355 |
12.7 Notes | p. 357 |
13 Modules and vector spaces | p. 358 |
13.1 Definitions, basic properties, and examples | p. 358 |
13.2 Submodules and quotient modules | p. 360 |
13.3 Module homomorphisms and isomorphisms | p. 363 |
13.4 Linear independence and bases | p. 367 |
13.5 Vector spaces and dimension | p. 370 |
14 Matrices | p. 377 |
14.1 Basic definitions and properties | p. 377 |
14.2 Matrices and linear maps | p. 381 |
14.3 The inverse of a matrix | p. 386 |
14.4 Gaussian elimination | p. 388 |
14.5 Applications of Gaussian elimination | p. 392 |
14.6 Notes | p. 398 |
15 Subexponential-time discrete logarithms and factoring | p. 399 |
15.1 Smooth numbers | p. 399 |
15.2 An algorithm for discrete logarithms | p. 400 |
15.3 An algorithm for factoring integers | p. 407 |
15.4 Practical improvements | p. 414 |
15.5 Notes | p. 418 |
16 More rings | p. 421 |
16.1 Algebras | p. 421 |
16.2 The field of fractions of an integral domain | p. 427 |
16.3 Unique factorization of polynomials | p. 430 |
16.4 Polynomial congruences | p. 435 |
16.5 Minimal polynomials | p. 438 |
16.6 General properties of extension fields | p. 440 |
16.7 Formal derivatives | p. 444 |
16.8 Formal power series and Laurent series | p. 446 |
16.9 Unique factorization domains (*) | p. 451 |
16.10 Notes | p. 464 |
17 Polynomial arithmetic and applications | p. 465 |
17.1 Basic arithmetic | p. 465 |
17.2 Computing minimal polynomials in F[x]/(f)(I) | p. 468 |
17.3 Euclid's algorithm | p. 469 |
17.4 Computing modular inverses and Chinese remaindering | p. 472 |
17.5 Rational function reconstruction and applications | p. 474 |
17.6 Faster polynomial arithmetic (*) | p. 478 |
17.7 Notes | p. 484 |
18 Linearly generated sequences and applications | p. 486 |
18.1 Basic definitions and properties | p. 486 |
18.2 Computing minimal polynomials: a special case | p. 490 |
18.3 Computing minimal polynomials: a more general case | p. 492 |
18.4 Solving sparse linear systems | p. 497 |
18.5 Computing minimal polynomials in F[X]/(f)(II) | p. 500 |
18.6 The algebra of linear transformations (*) | p. 501 |
18.7 Notes | p. 508 |
19 Finite fields | p. 509 |
19.1 Preliminaries | p. 509 |
19.2 The existence of finite fields | p. 511 |
19.3 The subfield structure and uniqueness of finite fields | p. 515 |
19.4 Conjugates, norms and traces | p. 516 |
20 Algorithms for finite fields | p. 522 |
20.1 Tests for and constructing inrreducible polynomials | p. 522 |
20.2 Computing minimal polynomials in F[X](f)(III) | p. 525 |
20.3 Factoring polynomials: square-free decomposition | p. 526 |
20.4 Factoring polynomials: the Cantor-Zassenhaus algorithm | p. 530 |
20.5 Factoring polynomials: Berlekamp's algorithm | p. 538 |
20.6 Deterministic factorization algorithms (*) | p. 544 |
20.7 Notes | p. 546 |
21 Deterministic primality testing | p. 548 |
21.1 The basic idea | p. 548 |
21.2 The algorithm and its analysis | p. 549 |
21.3 Notes | p. 558 |
Appendix: Some useful facts | p. 561 |
Bibliography | p. 566 |
Index of notation | p. 572 |
Index | p. 574 |