Primality Tests and Factoring Using AKS Polynomials - Robert Erra - LSE Week 2015

Prime numbers are ubiquitous in modern cryptography and fortunately a lot of probabilistic and deterministic primality tests exist. The most famous is the AKS algorithm that has proved that “Prime is in P”, a result that has is one of the most important results in the last 30 years in computational number theory. On the other side, Factoring a large number is a hard problem whose complexity is still unknown. We propose here to analyse the following question: if we take a composite number what information can we obtain with primality tests ? We will explain how in some cases we can factor a number using primality tests ; we will for example explain why Charmichael numbers are easy to factor and we will finish with the presentation of a new (and curious) factorization algorithm that use the AKS polynomials, the algorithm is not efficient but it is deterministic and can still be improved.