Usuario:Rubén Bonilla Tanco/Taller

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 scope of the computational number theory is to get a efficent algorithm to make a mathematical operation.

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 [1], 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, know if a number is prime is difficult because take a lot of computer power when we want 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)⁶).