= Computational number theory
{wiki}
= Algorithmic number theory
{synonym}
Computational number theory studies algorithms for arithmetic objects, including <integers>, <finite fields>, <polynomials> and algebraic number fields. Typical tasks are greatest-common-divisor computation, modular inversion, primality testing and integer factorization. The output may be an answer together with a certificate that can be checked independently.
For example, the <extended Euclidean algorithm> finds $7\cdot15-26\cdot4=1$, certifying that the inverse of seven modulo twenty-six is fifteen. Modular exponentiation by repeated squaring computes $a^e\bmod m$ with a number of modular multiplications proportional to the bit length of $e$, instead of multiplying $e$ copies.
Input size is measured in bits, not by the numerical magnitude alone. An integer near $2^k$ has roughly $k$ bits, so an algorithm using time proportional to that integer can be exponential in its input length. Primality testing and complete factorization are distinct tasks; solving the former does not automatically supply the latter.
Back to article page
