A Computational Introduction to Number Theory and AlgebraCambridge University Press, 28 avr. 2005 - 517 pages 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. |
Table des matières
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 |
| 504 | |
| 510 | |
| 512 | |
Autres éditions - Tout afficher
Expressions et termes fréquents
abelian group addition arithmetic assume bound called Chinese remainder theorem coefficients compute congruence consider define definition deg(a deg(b denote discrete logarithms discussed divides elements of F Example exists expected number expected running F-algebra factorization finite field follows Gaussian elimination given greatest common divisor group homomorphism H₁ hash functions hence ideal img(p implies integral domain irreducible polynomials isomorphism ker(p kernel len(q Let F Let G linear log log loop iteration matrix minimal polynomial modulo monic Moreover multiplicative inverse multiplicative order non-negative integers non-trivial non-zero Note operations in F output pairwise independent polynomial ƒ polynomial of degree positive integer previous exercise primality test probabilistic algorithm probability distribution problem Proof prove quotient R-module random variable real numbers relatively prime ring homomorphism root sequence Show subgroup subring Suppose surjective takes as input uniformly distributed unique vector space verify zero
Fréquemment cités
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).