Computational number theory

In mathematics and computer science, computational number theory, also known as algorithmic number theory, is the study of algorithms for performing number theoretic computations. The aim of the computational number theory is to study the most relevant algorithm from the number theory.

Algorithms

There are many algorithms in the computational number theory. The following are some of the algorithms and their complexities:

Multiplication

The lower bound for the computational complexity of multiplication has been a focus since the first computer appeared. The standard multiplication algorithm has complexity O(n²). But the time complexity has been long conjectured to be O(n log(n)), this was proved in 2019.

Exponential

As the multiplication, exponential has been a aim for the number theory. If we try to compute a exponential operation with successive multiplication we get a complexity as same as the multiplication with standard algorithm (O(n²)). To improve this, we can use the repeated multiplication and reduction algortihm, with this, we reduce the complexity to O(M(n) 2^k). Other algortihms are Exponentiation by squaring or Montgomery reduction that reduce the complexity to O(M(n) k).

Primality test

This is very important part of the computational number theory,to know if a number is prime, is difficult because take a lot of computer power when we want to prove it in a large number.

The more easier algortihm to know if a number is prime, is a successive division by all the lowers numbers, if we depart from that the standard division take a complexity of O(n²) and we want to know if a number n is prime, the global complexity is O(n × n²). To improve this, we can go to AKS primality test, and if we assumen Agrawal's conjecture the complexity is O((log n)³), otherwise it take O((log n)⁶).

Integer factorials

The factorial is the product of all the positive integer numbers from 1 to the number n. We could make this with successive multiplication, and we get a complexity of O(n × n²⁾), with the Bottom-up multiplication algorithm we reduce this complexity to O(M(m²) log m).

Greatest common divisor

The greatest common divisor is a main scope of the computational number theory, one method to calculate this, is commparing all the divisors between two number, but this is very inefficient. The computational number theory have developed some algorithms to improve this as Euclidean algorithm that can commpute the GCD with complexity of O(n²) o the Binary GCD that can solve this problem with the same complexity. There exist some other algortihms that get further as Stehlé–Zimmermann algorithm, it algorithm can get the GCD with the complexity of O(M(n) log n).

Uses

One of the main uses of the algotihms of the computational number theory is the cryptography.

See also

• Computational complexity of mathematical operations
• SageMath
• Number Theory Library
• PARI/GP
• Fast Library for Number Theory

Further reading

• Eric Bach and Jeffrey Shallit, Algorithmic Number Theory, volume 1: Efficient Algorithms. MIT Press, 1996, ISBN 0-262-02405-5
• D. M. Bressoud (1989). Factorisation and Primality Testing. Springer-Verlag. ISBN 0-387-97040-1.

• Buhler, J.P.; P., Stevenhagen, eds. (2008). Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography. MSRI Publications. Vol. 44. Cambridge University Press. ISBN 978-0-521-20833-8. Zbl 1154.11002.
• Henri Cohen, A Course in Computational Algebraic Number Theory, Graduate Texts in Mathematics 138, Springer-Verlag, 1993.
• Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, Springer-Verlag, 2001, ISBN 0-387-94777-9
• Riesel, Hans (1994). Prime Numbers and Computer Methods for Factorization. Progress in Mathematics. Vol. 126 (second ed.). Boston, MA: Birkhäuser. ISBN 0-8176-3743-5. Zbl 0821.11001.
• Victor Shoup, A Computational Introduction to Number Theory and Algebra. Cambridge, 2005, ISBN 0-521-85154-8
• Samuel S. Wagstaff, Jr. (2013). The Joy of Factoring. Providence, RI: American Mathematical Society. ISBN 978-1-4704-1048-3.