Number Theory for Computing

Includes index

Includes bibliography (p. 363-374) and references

1. Elementary Number Theory Theory of Divisibility Diophantine Equations Arithmetic Functions Distribution of Prime Numbers Theory of Congruences Arithmetic of Elliptic Curves 2. Computational/Algorithmic Number Theory Algorithms for Primality Testing Algorithms for Integer Factorization Algorithms for Discrete Logarithms Quantum Number-Theoretic Algorithms Miscellaneous Algorithms in Number Theory 3. Applied Number Theory in Computing/Cryptography Why Applied Number Theory? Computer Systems Design Cryptography and Information Security.

Mathematicians do not study objects, but relations among objectsj they are indifferent to the replacement of objects by others as long as relations do not change. Matter is not important, only form interests them. HENRI POINCARE (1854-1912) Computer scientists working on algorithms for factorization would be well advised to brush up on their number theory. IAN STEWART [219] The theory of numbers, in mathematics, is primarily the theory of the prop­ erties of integers (i.e., the whole numbers), particularly the positive integers. For example, Euclid proved 2000 years aga in his Elements that there exist infinitely many prime numbers.