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 study the most relevant algorithm from the number theory.

Algorithms

There are a lot of algorithms in the computational number theory, the following are some of then and his complexity.

Multiplication

The multiplication has been a objective since the first computer appeared. If we see the standar multiplication in term of complexity (according to big O notation), we realize that the complexity if we compute a two huge number when it tend to infinite is O(n²). A long the time it complexity have been reduce thank to some algorithms. One of this algorithm is Schönhage–Strassen algorithm, it reduce the complexity of a multiplication to O(n log n log log n). There are other algorithms as Karatsuba algorithm, Fürer's algorithm and Toom–Cook multiplication.

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 standar 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 standar 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)⁶).

Integre factorization

The factorial is the product of all the positive integrer number since 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.