Computational Number Theory

Computational number theory is the branch of number theory concerned with finding and implementing efficient computer algorithms for solving various problems in number theory. Much progress has been made in this field in recent years, both in terms of improved computer speed and in terms of finding more efficient algorithms. Two important applications of computational number theory are primality testing and prime factorization of large integers.

Primality testing is considered easy in the sense that very large general numbers (currently up to 4000 digits or so) can be tested reliably for primality. In fact, on August 6, 2002, Agrawal, Saxena, and Kayal found a polynomial time algorithm for testing and proving the primality of general numbers. Although this algorithm is still impractical, it was a landmark discovery, since polynomial time algorithms are considered easy. On the other hand, factoring is considered hard in the sense that no polynomial time algorithm is currently known for factoring integers. The largest general integer to be factored was RSA-576, a 174-digit number that is the product of two 87-digit primes. The fact that primality testing is easy but factoring is hard allows for secure encryption, such as RSA encryption.

Other problems in computational number theory include computing the greatest common divisor of large numbers and computing various quantities associated with number fields, i.e., class numbers and class groups.

REFERENCES:

Bressoud, D. M. and Wagon, S. A Course in Computational Number Theory. London: Springer-Verlag, 2000.

Cohen, H. A Course in Computational Algebraic Number Theory. New York: Springer-Verlag, 1993.