A Computational Introduction to Number Theory and Algebra

Front Cover
Cambridge University Press, Apr 28, 2005 - Computers - 517 pages
0 Reviews
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 emphasises algorithms and applications, such as cryptography and error correcting codes, and is accessible to a broad audience. The mathematical prerequisites are minimal: nothing beyond material in a typical undergraduate course in calculus is presumed, other than some experience in doing proofs - everything else is developed from scratch. Thus the book can serve several purposes. It can be used as a reference and for self-study by readers who want to learn the mathematical foundations of modern cryptography. It is also ideal as a textbook for introductory courses in number theory and algebra, especially those geared towards computer science students.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Basic properties of the integers
1
12 Ideals and greatest common divisors
4
13 Some consequences of unique factorization
8
Congruences
13
22 Solving linear congruences
15
23 Residue classes
20
24 Eulers phi function
24
25 Fermats little theorem
25
Quadratic residues and quadratic reciprocity
283
122 The Legendre symbol
285
123 The Jacobi symbol
287
124 Notes
289
Computational problems related to quadratic residues
290
132 Testing quadratic residuosity
291
133 Computing modular square roots
292
134 The quadratic residuosity assumption
297

26 Arithmetic functions and Möbius inversion
28
Computing with large integers
33
32 Machine models and complexity theory
36
33 Basic integer arithmetic
39
34 Computing in Zₙ
48
35 Faster integer arithmetic
51
36 Notes
52
Euclids algorithm
55
42 The extended Euclidean algorithm
58
43 Computing modular inverses and Chinese remaindering
62
44 Speeding up algorithms via modular computation
63
45 Rational reconstruction and applications
66
46 Notes
73
The distribution of primes
74
52 Bertrands postulate
78
53 Mertens theorem
81
54 The sieve of Eratosthenes
85
55 The prime number theorem and beyond
86
56 Notes
94
Finite and discrete probability distributions
96
62 Conditional probability and independence
99
63 Random variables
104
64 Expectation and variance
111
65 Some useful bounds
117
66 The birthday paradox
121
67 Hash functions
125
68 Statistical distance
130
69 Measures of randomness and the leftover hash lemma
136
610 Discrete probability distributions
141
611 Notes
147
Probabilistic algorithms
148
72 Approximation of functions
155
73 Flipping a coin until a head appears
158
74 Generating a random number from a given interval
159
75 Generating a random prime
162
76 Generating a random nonincreasing sequence
167
77 Generating a random factored number
170
78 The RSA cryptosystem
174
79 Notes
179
Abelian groups
180
82 Subgroups
185
83 Cosets and quotient groups
190
84 Group homomorphisms and isomorphisms
194
85 Cyclic groups
202
86 The structure of finite abelian groups
208
Rings
211
92 Polynomial rings
220
93 Ideals and quotient rings
231
94 Ring homomorphisms and isomorphisms
236
Probabilistic primality testing
244
102 The structure of Zₙ
245
103 The MillerRabin test
247
104 Generating random primes using the Miller Rabin test
252
105 Perfect power testing and prime power factoring
261
106 Factoring and computing Eulers phi function
262
107 Notes
266
Finding generators and discrete logarithms in Z
268
112 Computing discrete logarithms Zₚ
270
113 The DiffieHellman key establishment protocol
275
114 Notes
281
135 Notes
298
Modules and vector spaces
299
142 Submodules and quotient modules
301
143 Module homomorphisms and isomorphisms
303
144 Linear independence and bases
306
145 Vector spaces and dimension
309
Matrices
316
152 Matrices and linear maps
320
153 The inverse of a matrix
323
154 Gaussian elimination
324
155 Applications of Gaussian elimination
328
156 Notes
334
Subexponentialtime discrete logarithms and factoring
336
162 An algorithm for discrete logarithms
337
163 An algorithm for factoring integers
344
164 Practical improvements
352
165 Notes
356
More rings
359
172 The field of fractions of an integral domain
363
173 Unique factorization of polynomials
366
174 Polynomial congruences
371
175 Polynomial quotient algebras
374
176 General properties of extension fields
376
177 Formal power series and Laurent series
378
178 Unique factorization domains
383
179 Notes
397
Polynomial arithmetic and applications
398
182 Computing minimal polynomials in 𝑭𝐗𝑓 I
401
183 Euclids algorithm
402
184 Computing modular inverses and Chinese remaindering
405
185 Rational function reconstruction and applications
410
186 Faster polynomial arithmetic
415
187 Notes
421
Linearly generated sequences and applications
423
a special case
428
a more general case
429
194 Solving sparse linear systems
435
195 Computing minimal polynomials in 𝑭𝐗𝑓 II
438
196 The algebra of linear transformations
440
197 Notes
447
Finite fields
448
202 The existence of finite fields
450
203 The subfield structure and uniqueness of finite fields
454
204 Conjugates norms and traces
456
Algorithms for finite fields
462
212 Computing minimal polynomials in in 𝑭𝐗𝑓 III
465
the CantorZassenhaus algorithm
467
Berlekamps algorithm
475
215 Deterministic factorization algorithms
483
216 Faster squarefree decomposition
485
217 Notes
487
Deterministic primality testing
489
222 The algorithm and its analysis
490
223 Notes
500
Some useful facts
501
Bibliography
504
Index of notation
510
Index
512
Copyright

Other editions - View all

Common terms and phrases

Popular passages

Page 506 - D. Shanks, Class number, a theory of factorization, and genera, in Proceedings of Symposia in Pure Mathematics 20, Providence: American Mathematical Society (1971).

References to this book

All Book Search results »

About the author (2005)

Victor Shoup is Associate Professor at The Courant Institute of Mathematical Sciences at New York University.

Bibliographic information