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 , certifying that the inverse of seven modulo twenty-six is fifteen. Modular exponentiation by repeated squaring computes with a number of modular multiplications proportional to the bit length of , instead of multiplying copies.
Input size is measured in bits, not by the numerical magnitude alone. An integer near has roughly 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.
Articles by others on the same topic
Computational number theory is a branch of number theory that focuses on the use of algorithms and computational techniques to solve problems related to integers and their properties. It encompasses a wide range of topics, including but not limited to: 1. **Primality Testing**: Developing algorithms to determine whether a given number is prime. Techniques such as the Miller-Rabin test and the AKS primality test are examples in this area.
