A computational introduction to number theory and algebra

Select an Action

Place Hold(s)
Add to My Lists
Email
Print

Title:

Personal Author:

Shoup, Victor

Edition:

2nd ed.

Publication Information:

Cambridge, UK : Cambridge University Press, 2009

Physical Description:

xvii, 580 p. : ill. ; 26 cm.

ISBN:

9780521516440

Subject Term:

Number theory -- Data processing

Available:*

Library	Item Barcode	Call Number	Material Type	Item Category 1	Status
Searching... PSZ JB	30000010205852	QA241 S465 2009	Open Access Book	Book	Searching... Unknown

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

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

Available:*

On Order

Summary

Summary

Author Notes

Reviews 1

Choice Review

Table of Contents