| Elementary Number Theory | p. 1 |
| Introduction | p. 1 |
| What is Number Theory? | p. 1 |
| Algebraic Preliminaries | p. 12 |
| Theory of Divisibility | p. 20 |
| Basic Properties of Divisibility | p. 20 |
| Fundamental Theorem of Arithmetic | p. 24 |
| Mersenne Primes and Fermat Numbers | p. 27 |
| Euclid's Algorithm | p. 32 |
| Continued Fractions | p. 36 |
| Diophantine Equations | p. 41 |
| Basic Concepts of Diophantine Equations | p. 41 |
| Linear Diophantine Equations | p. 42 |
| Pell's Equations | p. 45 |
| Arithmetic Functions | p. 50 |
| Multiplicative Functions | p. 50 |
| Functions ¿(n), ¿(n) and s(n) | p. 51 |
| Perfect, Amicable and Sociable Numbers | p. 54 |
| Functions ¿(n), ¿(n) and ¿(n) | p. 61 |
| Distribution of Prime Numbers | p. 64 |
| Prime Distribution Function ¿(x) | p. 65 |
| Approximations of ¿(x) by x/ ln x | p. 67 |
| Approximations of ¿(x) by Li(x) | p. 73 |
| The Riemann ¿-Function ¿(s) | p. 74 |
| The nth Prime | p. 83 |
| Distribution of Twin Primes | p. 86 |
| The Arithmetic Progression of Primes | p. 89 |
| Theory of Congruences | p. 90 |
| Basic Properties of Congruences | p. 90 |
| Modular Arithmetic | p. 94 |
| Linear Congruences | p. 96 |
| The Chinese Remainder Theorem | p. 101 |
| High-Order Congruences | p. 104 |
| Legendre and Jacobi Symbols | p. 107 |
| Orders and Primitive Roots | p. 115 |
| Indices and kth Power Residues | p. 120 |
| Arithmetic of Elliptic Curves | p. 124 |
| Basic Concepts of Elliptic Curves | p. 125 |
| Geometric Composition Laws of Elliptic Curves | p. 128 |
| Algebraic Computation Laws for Elliptic Curves | p. 129 |
| Group Laws on Elliptic Curves | p. 133 |
| Number of Points on Elliptic Curves | p. 134 |
| Bibliographic Notes and Further Reading | p. 135 |
| Algorithmic Number Theory | p. 139 |
| Introduction | p. 139 |
| What is Algorithmic Number Theory? | p. 139 |
| E ective Computability | p. 142 |
| Computational Complexity | p. 146 |
| Complexity of Number-Theoretic Algorithms | p. 153 |
| Fast Modular Exponentiations | p. 159 |
| Fast Group Operations on Elliptic Curves | p. 163 |
| Algorithms for Primality Testing | p. 167 |
| Deterministic and Rigorous Primality Tests | p. 167 |
| Fermat's Pseudoprimality Test | p. 170 |
| Strong Pseudoprimality Test | p. 173 |
| Lucas Pseudoprimality Test | p. 179 |
| Elliptic Curve Test | p. 186 |
| Historical Notes on Primality Testing | p. 190 |
| Algorithms for Integer Factorization | p. 192 |
| Complexity of Integer Factorization | p. 192 |
| Trial Division and Fermat Method | p. 196 |
| Legendre's Congruence | p. 198 |
| Continued FRACtion Method (CFRAC) | p. 201 |
| Quadratic and Number Field Sieves (QS/NFS) | p. 204 |
| Polland's "rho" and "p - 1" Methods | p. 208 |
| Lenstra's Elliptic Curve Method (ECM) | p. 215 |
| Algorithms for Discrete Logarithms | p. 218 |
| Shanks' Baby-Step Giant-Step Algorithm | p. 219 |
| Silver{Pohlig{Hellman Algorithm | p. 222 |
| Subexponential Algorithms | p. 226 |
| Algorithm for the Root Finding Problem | p. 227 |
| Quantum Number-Theoretic Algorithms | p. 230 |
| Quantum Information and Computation | p. 230 |
| Quantum Computability and Complexity | p. 235 |
| Quantum Algorithm for Integer Factorization | p. 236 |
| Quantum Algorithms for Discrete Logarithms | p. 241 |
| Miscellaneous Algorithms in Number Theory | p. 243 |
| Algorithms for Computing ¿(x) | p. 243 |
| Algorithms for Generating Amicable Pairs | p. 249 |
| Algorithms for Verifying Goldbach's Conjecture | p. 252 |
| Algorithm for Finding Odd Perfect Numbers | p. 255 |
| Bibliographic Notes and Further Reading | p. 257 |
| Applied Number Theory | p. 259 |
| Why Applied Number Theory? | p. 259 |
| Computer Systems Design | p. 261 |
| Representing Numbers in Residue Number Systems | p. 261 |
| Fast Computations in Residue Number Systems | p. 264 |
| Residue Computers | p. 269 |
| Complementary Arithmetic | p. 269 |
| Hashing Functions | p. 273 |
| Error Detection and Correction Methods | p. 277 |
| Random Number Generation | p. 282 |
| Cryptography and Information Security | p. 287 |
| Introduction | p. 288 |
| Secret-Key Cryptography | p. 289 |
| Data/Advanced Encryption Standard (DES/AES) | p. 299 |
| Public-Key Cryptography | p. 303 |
| Discrete Logarithm Based Cryptosystems | p. 309 |
| RSA Public-Key Cryptosystem | p. 313 |
| Quadratic Residuosity Cryptosystems | p. 326 |
| Elliptic Curve Public-Key Cryptosystems | p. 332 |
| Digital Signatures | p. 336 |
| Digital Signature Algorithm/Standard (DSA/DSS) | p. 342 |
| Database Security | p. 344 |
| Secret Sharing | p. 348 |
| Internet/Web Security and Electronic Commerce | p. 352 |
| Steganography | p. 356 |
| Quantum Cryptography | p. 358 |
| Bibliographic Notes and Further Reading | p. 359 |
| Bibliography | p. 363 |
| Index | p. 375 |
| Table of Contents provided by Publisher. All Rights Reserved. |
