a The problem of recognizing prime numbers in nature, has been one of the most ancient and the scientific community has always put great effort throughout history. to the sieve of Eratosthenes is the most ancient (200 BC) to find prime numbers, is able to recognize the first cousins to a given number, currently has more historical significance than practical, because of its high cost computer. Following the same idea to to Italian (Fibonacci) presented a very simple algorithm to determine whether a given number n is prime, consisting of checking that no less than the prime number to divide n. This algorithm has the feature of being deterministic (always get a solution) but returns to be completely ineffective. The first important result was announced in 1876 when Lucas adouard presented an algorithm to determine, in a surprisingly efficient, the primality of Mersenne numbers, today the largest prime known is A = A 1 , 12. 978.
189 digits, found by GIMPS / Edson Smith on August 23, 2008. Then in the absence of deterministic algorithms to determine if any number (without any form or property in particular) is prime, are called probabilistic primality test, the first to happen is the Fermat test based on Fermat's Little Theorem (PTF) which has a highly efficient and gives us a high degree reliability, but this test has an Achilles heel are called Carmichael numbers, which are recognized in this test as cousins, being really compounds. Correcting this detail appears Test Solovay-Strassen primality (SS) in A and amended by Atkin and Larson. But in 1980 that appears which is the most widely used today, it is simple to implement, has the same computational cost as the previous ones and shows a higher probability. Based on the theory of elliptic curves, we have the famous algorithm of Adleman-Pomerance cyclotomic-Rumely (APRCL) deterministic, which is not polynomial in the bits of the number, but is extremely efficient in practice to determine the primality of a number. Despite the effort to find efficient primality test and deterministic, it seemed impossible to find one that would be of order polynomial in the number of bits, so that in August 2002, surprising the community cientificaa Manindra Agrawal, Neeraj Kayal and Nitin Saxena, Department of Computing Research Institute Kanpur, India presented the AKS, and regarded as the first order polynomial deterministic test. I just