9783540691990

In this volume one finds basic techniques from algebra and number theory (e.g. congruences, unique factorization domains, finite fields, quadratic residues, primality tests, continued fractions, etc.) which in recent years have proven to be extremely useful for applications to cryptography and coding theory. Both cryptography and codes have crucial applications in our daily lives, and they are described here, while the complexity problems that arise in implementing the related numerical algorithms are also taken into due account. Cryptography has been developed in great detail, both in its classical and more recent aspects. In particular public key cryptography is extensively discussed, the use of algebraic geometry, specifically of elliptic curves over finite fields, is illustrated, and a final chapter is devoted to quantum cryptography, which is the new frontier of the field. Coding theory is not discussed in full; however a chapter, sufficient for a good introduction to the subject, has been devoted to linear codes. Each chapter ends with several complements and with an extensive list of exercises, the solutions to most of which are included in the last chapter. Though the book contains advanced material, such as cryptography on elliptic curves, Goppa codes using algebraic curves over finite fields, and the recent AKS polynomial primality test, the authors' objective has been to keep the exposition as self-contained and elementary as possible. Therefore the book will be useful to students and researchers, both in theoretical (e.g. mathematicians) and in applied sciences (e.g. physicists, engineers, computer scientists, etc.) seeking a friendly introduction to the important subjects treated here. The book will also be useful for teachers who intend to give courses on these topics.

A round-up on numbers	p. 1
Mathematical induction	p. 1
The concept of recursion	p. 5
Fibonacci numbers	p. 6
Further examples of population dynamics	p. 11
The tower of Hanoi: a non-homogeneous linear case	p. 13
The Euclidean algorithm	p. 14
Division	p. 14
The greatest common divisor	p. 16
Bezout's identity	p. 17
Linear Diophantine equations	p. 20
Euclidean rings	p. 21
Polynomials	p. 23
Counting in different bases	p. 30
Positional notation of numbers	p. 30
Base 2	p. 32
The four operations in base 2	p. 33
Integer numbers in an arbitrary base	p. 39
Representation of real numbers in an arbitrary base	p. 40
Continued fractions	p. 43
Finite simple continued fractions and rational numbers	p. 44
Infinite simple continued fractions and irrational numbers	p. 48
Periodic continued fractions	p. 56
A geometrical model for continued fractions	p. 57
The approximation of irrational numbers by convergents	p. 58
Continued fractions and Diophantine equations	p. 61
Appendix to Chapter 1	p. 62
Theoretical exercises	p. 62
Computational exercises	p. 73
Programming exercises	p. 84
Computational complexity	p. 87
The idea of computational complexity	p. 87
The symbol O	p. 89
Polynomial time, exponential time	p. 92
Complexity of elementary operations	p. 95
Algorithms and complexity	p. 97
Complexity of the Euclidean algorithm	p. 98
From binary to decimal representation: complexity	p. 101
Complexity of operations on polynomials	p. 101
A more efficient multiplication algorithm	p. 103
The Ruffini-Horner method	p. 105
Appendix to Chapter 2	p. 107
Theoretical exercises	p. 107
Computational exercises	p. 109
Programming exercises	p. 113
From infinite to finite	p. 115
Congruence: fundamental properties	p. 115
Elementary applications of congruence	p. 120
Casting out nines	p. 120
Tests of divisibility	p. 121
Linear congruences	p. 122
Powers modulo n	p. 126
The Chinese remainder theorem	p. 128
Examples	p. 133
Perpetual calendar	p. 133
Round-robin tournaments	p. 136
Appendix to Chapter 3	p. 136
Theoretical exercises	p. 136
Computational exercises	p. 140
Programming exercises	p. 147
Finite is not enough: factoring integers	p. 149
Prime numbers	p. 149
The Fundamental Theorem of Arithmetic	p. 150
The distribution of prime numbers	p. 152
The sieve of Eratosthenes	p. 157
Prime numbers and congruences	p. 160
How to compute Euler function	p. 160
Fermat's little theorem	p. 162
Wilson's theorem	p. 165
Representation of rational numbers in an arbitrary base	p. 166
Fermat primes, Mersenne primes and perfect numbers	p. 168
Factorisation of integers of the form b[superscript n] [plus or minus] 1	p. 168
Fermat primes	p. 170
Mersenne primes	p. 172
Perfect numbers	p. 173
Factorisation in an integral domain	p. 173
Prime and irreducible elements in a ring	p. 174
Factorial domains	p. 175
Noetherian rings	p. 177
Factorisation of polynomials over a field	p. 179
Factorisation of polynomials over a factorial ring	p. 182
Polynomials with rational or integer coefficients	p. 188
Lagrange interpolation and its applications	p. 191
Kronecker's factorisation method	p. 195
Appendix to Chapter 4	p. 198
Theoretical exercises	p. 198
Computational exercises	p. 204
Programming exercises	p. 211
Finite fields and polynomial congruences	p. 213
Some field theory	p. 213
Field extensions	p. 213
Algebrac extensions	p. 214
Splitting field of a polynomial	p. 217
Roots of unity	p. 218
Algebraic closure	p. 219
Finite fields and their subfields	p. 220
Automorphisms of finite fields	p. 222
Irreducible polynomials over Z[subscript p]	p. 222
The field F[subscript 4] of order four	p. 224
The field F[subscript 8] of order eight	p. 225
The field F[subscript 16] of order sixteen	p. 226
The field F[subscript 9] of order nine	p. 226
About the generators of a finite field	p. 227
Complexity of operations in a finite field	p. 228
Non-linear polynomial congruences	p. 229
Degree two congruences	p. 234
Quadratic residues	p. 236
Legendre symbol and its properties	p. 238
The law of quadratic reciprocity	p. 243
The Jacobi symbol	p. 245
An algorithm to compute square roots	p. 248
Appendix to Chapter 5	p. 251
Theoretical exercises	p. 251
Computational exercises	p. 255
Programming exercises	p. 260
Primality and factorisation tests	p. 261
Pseudoprime numbers and probabilistic tests	p. 261
Pseudoprime numbers	p. 261
Probabilistic tests and deterministic tests	p. 263
A first probabilistic primality test	p. 263
Carmichael numbers	p. 264
Euler pseudoprimes	p. 265
The Solovay-Strassen probabilistic primality test	p. 268
Strong pseudoprimes	p. 268
The Miller-Rabin probabilistic primality test	p. 272
Primitive roots	p. 273
Primitive roots and index	p. 278
More about the Miller-Rabin test	p. 279
A polynomial deterministic primality test	p. 281
Factorisation methods	p. 290
Fermat factorisation method	p. 291
Generalisation of Fermat factorisation method	p. 292
The method of factor bases	p. 294
Factorisation and continued fractions	p. 299
The quadratic sieve algorithm	p. 300
The [rho] method	p. 309
Variation of [rho] method	p. 311
Appendix to Chapter 6	p. 313
Theoretical exercises	p. 313
Computational exercises	p. 315
Programming exercises	p. 317
Secrets...and lies	p. 319
The classic ciphers	p. 319
The earliest secret messages in history	p. 319
The analysis of the ciphertext	p. 325
Enciphering machines	p. 329
Mathematical setting of a cryptosystem	p. 330
Some classic ciphers based on modular arithmetic	p. 334
Affine ciphers	p. 336
Matrix or Hill ciphers	p. 340
The basic idea of public key cryptography	p. 341
An algorithm to compute discrete logarithms	p. 344
The knapsack problem and its applications to cryptography	p. 345
Public key cipher based on the knapsack problem, or Merkle-Hellman cipher	p. 348
The RSA system	p. 349
Accessing the RSA system	p. 351
Sending a message enciphered with the RSA system	p. 352
Deciphering a message enciphered with the RSA system	p. 354
Why did it work?	p. 356
Authentication of signatures with the RSA system	p. 360
A remark about the security of RSA system	p. 362
Variants of RSA system and beyond	p. 363
Exchanging private keys	p. 363
ElGamal cryptosystem	p. 364
Zero-knowledge proof: persuading that a result is known without revealing its content nor its proof	p. 365
Historical note	p. 366
Cryptography and elliptic curves	p. 366
Cryptography in a group	p. 367
Algebraic curves in a numerical affine plane	p. 368
Liens and rational curves	p. 369
Hyperelliptic curves	p. 370
Elliptic curves	p. 372
Group law on elliptic curves	p. 374
Elliptic curves over R, C and Q	p. 380
Elliptic curves over finite fields	p. 381
Elliptic curves and cryptography	p. 384
Pollard's p - 1 factorisation method	p. 385
Appendix to Chapter 7	p. 386
Theoretical exercises	p. 386
Computational exercises	p. 390
Programming exercises	p. 401
Transmitting without... fear of errors	p. 405
Birthday greetings	p. 406
Taking photos in space or tossing coins, we end up at codes	p. 407
Error-correcting codes	p. 410
Bounds on the invariants	p. 413
Linear codes	p. 419
Cyclic codes	p. 425
Goppa codes	p. 429
Appendix to Chapter 8	p. 436
Theoretical exercises	p. 436
Computational exercises	p. 439
Programming exercises	p. 443
The future is already here: quantum cryptography	p. 445
A first foray into the quantum world: Young's experiment	p. 446
Quantum computers	p. 449
Vernam's cipher	p. 451
A short glossary of quantum mechanics	p. 454
Quantum cryptography	p. 460
Appendix to Chapter 9	p. 467
Theoretical exercises	p. 467
Computational exercises	p. 468
Programming exercises	p. 469
Solution to selected exercises	p. 471
Exercises of Chapter 1	p. 471
Exercises of Chapter 2	p. 482
Exercises of Chapter 3	p. 483
Exercises of Chapter 4	p. 487
Exercises of Chapter 5	p. 492
Exercises of Chapter 6	p. 496
Exercises of Chapter 7	p. 498
Exercises of Chapter 8	p. 501
Exercises of Chapter 9	p. 504
References	p. 507
Index	p. 511
Table of Contents provided by Ingram. All Rights Reserved.

Amazon no longer offers textbook rentals. We do!

Amazon no longer offers textbook rentals. We do!

We're the #1 textbook rental company. Let us show you why.

Elementary Number Theory, Cryptography and Codes

3540691995

Supplemental Materials

Summary

Author Biography

Table of Contents

Supplemental Materials

Rewards Program