## Number Theory for ComputingModern cryptography depends heavily on number theory, with primality test ing, factoring, discrete logarithms (indices), and elliptic curves being perhaps the most prominent subject areas. Since my own graduate study had empha sized probability theory, statistics, and real analysis, when I started work ing in cryptography around 1970, I found myself swimming in an unknown, murky sea. I thus know from personal experience how inaccessible number theory can be to the uninitiated. Thank you for your efforts to case the transition for a new generation of cryptographers. Thank you also for helping Ralph Merkle receive the credit he deserves. Diffie, Rivest, Shamir, Adleman and I had the good luck to get expedited review of our papers, so that they appeared before Merkle's seminal contribu tion. Your noting his early submission date and referring to what has come to be called "Diffie-Hellman key exchange" as it should, "Diffie-Hellman-Merkle key exchange", is greatly appreciated. It has been gratifying to see how cryptography and number theory have helped each other over the last twenty-five years. :'-Jumber theory has been the source of numerous clever ideas for implementing cryptographic systems and protocols while cryptography has been helpful in getting funding for this area which has sometimes been called "the queen of mathematics" because of its seeming lack of real world applications. Little did they know! Stanford, 30 July 2001 Martin E. Hellman Preface to the Second Edition Number theory is an experimental science. |

### What people are saying - Write a review

User Review - Flag as inappropriate

下载地址： ed2k://|file|Number%20theory%20for%20computing%20-%20Yan%20S%20Y..pdf|22166130|4EFF3F5AEFBF1C04CA01D553882DA42B|/

### Contents

I | 1 |

IV | 13 |

V | 14 |

VI | 21 |

VIII | 27 |

IX | 33 |

X | 40 |

XI | 44 |

LIX | 228 |

LXI | 232 |

LXII | 234 |

LXIII | 237 |

LXIV | 240 |

LXV | 244 |

LXVI | 251 |

LXVII | 254 |

XII | 52 |

XIV | 54 |

XV | 57 |

XVI | 63 |

XVIII | 66 |

XIX | 71 |

XX | 79 |

XXI | 85 |

XXIII | 87 |

XXIV | 94 |

XXV | 95 |

XXVI | 104 |

XXVII | 106 |

XXVIII | 110 |

XXIX | 111 |

XXXI | 118 |

XXXII | 123 |

XXXIII | 130 |

XXXIV | 133 |

XXXV | 139 |

XXXVI | 150 |

XXXVII | 155 |

XXXVIII | 160 |

XXXIX | 163 |

XL | 164 |

XLI | 168 |

XLII | 169 |

XLIII | 171 |

XLIV | 173 |

XLVI | 174 |

XLVII | 177 |

XLVIII | 181 |

XLIX | 188 |

L | 194 |

LI | 198 |

LII | 202 |

LIV | 206 |

LV | 208 |

LVI | 215 |

LVII | 222 |

LVIII | 225 |

LXVIII | 255 |

LXIX | 258 |

LXX | 262 |

LXXI | 266 |

LXXII | 270 |

LXXIII | 273 |

LXXV | 278 |

LXXVI | 279 |

LXXVII | 285 |

LXXVIII | 287 |

LXXX | 292 |

LXXXI | 295 |

LXXXII | 299 |

LXXXIII | 300 |

LXXXIV | 303 |

LXXXVI | 305 |

LXXXVIII | 308 |

LXXXIX | 312 |

XC | 315 |

XCI | 317 |

XCII | 321 |

XCIII | 326 |

XCIV | 332 |

XCVI | 344 |

XCVII | 348 |

XCVIII | 354 |

XCIX | 358 |

C | 373 |

CI | 379 |

CII | 385 |

CIII | 392 |

CIV | 395 |

CV | 399 |

CVI | 403 |

CVII | 409 |

CVIII | 410 |

CIX | 411 |

415 | |

429 | |

### Other editions - View all

### Common terms and phrases

algebraic Alice amicable pairs arithmetic binary bit operations called CFRAC Chinese Remainder Theorem choose cipher ciphertext complexity Computer Science congruence conjecture decryption defined Definition denoted Digital Signature Diophantine equation divisor elements elliptic curve encryption Euclid's algorithm Euler's example exponential Fermat numbers Field Sieve finite field Gauss gcd(a hence integer factorization inverse Jacobi symbol known Legendre symbol linear Lucas mathematician mathematics Mersenne primes method mod q multiplicative Note odd number odd perfect number odd prime Photo by courtesy plaintext points polynomial positive integer primality testing prime factors primitive root probabilistic probable prime Proof pseudoprimality test public-key cryptography public-key cryptosystems quadratic nonresidues quadratic residues quantum computer random number real number relatively prime residue classes result Riemann Hypothesis secure sequence simple continued fraction solve strong pseudoprimality subsection Suppose system of residues Table Turing machine twin primes Z/nZ zeros