Computational number theory

The algorithmic number theory is a branch of number theory, which in turn is a branch of mathematics. It deals with the question of efficient algorithmic solutions for number-theoretic questions.

Most important areas of elementary algorithmic number theory are

  • Primality tests
  • Method for factoring an integer
  • Computation of discrete logarithms

This is required other methods, which are also tested:

  • Rapid multiplication
  • Fast exponentiation
  • Computing the greatest common divisor using the Euclidean algorithm
  • Calculating the Jacobi symbol using the quadratic reciprocity law
  • Factorization of polynomials, especially fast square root.

New research findings on algorithmic number theory will be presented, among others, on the 1994 two -yearly conference ANTS ( Algorithmic Number Theory Symposium ).


The most important application of algorithmic number theory cryptography. For example, exploited for the RSA procedure that the primality of a number can be checked quickly, but so far there are no known similar fast method, a composite number (which is a number that is not prime ) to factor. On this fact is based in particular the security of data transmission over the internet. In this context, RSA Security had awarded large sums for those who succeed to factorize certain numbers. Next application in cryptography algorithms, see for example in the calculation of discrete logarithms for other encryption and signature schemes.

A much -studied problem with far-reaching applications is to be found in a number grid, the grid generating a base that consists of as short as possible and if possible orthogonal basis vectors ( lattice basis reduction).