Primality testing versus Factorization. Although at this moment efficient techniques for factorization on classical computers are not known to exist, there is an efficient algorithm that decides for us whether a number is prime or not: the so-called AKS primality test (Agrawal et al. 2004). So, we might know a number is not prime, while we still do not have access to its set of factors. 