With his article Algorithms for Quantum Computation: Discrete Logarithms and factoring, Shor creates a new path in the research of the factorization of large numbers. He proves that he can have polynomials time algorithms for prime factorization and discrete logarithms on a quantum computer. In this new field, quantum number theory, the efficiency is radically different from the classical. And this is the key for application of quantum computers. In comparison with classical algorithms, the speed-up of Shor’s factoring algorithm is due to the quantum subroutine, the quantum order finding algorithm. With these algorithms we can calculate efficiently the order of an integer α modulo N. More precisely, if we have α and N coprimes, then the quantum order finding algorithm returns the smallest integer r > 0 such that α^r mod N=1. If r is even then α factor of N may be given by gcd(α^r/2±1,Ν). If a factor is not found or r is odd, then the procedure is relaunched with a different random value of α. A lot of work has been done with the quantum part of the algorithm, for example computing prime factors with Josephson phase qubit quantum processor. Compiled versions of Shor’s algorithm have been demonstrated on ensemble systems and photonic systems. But we can also try to optimize the classical part of the Shor’s algorithm. Grosshans and al reduce the probability of failure by applying elementary results in number theory. They illustrate their approach with the use of only one single call to the quantum order finding algorithm to prove that almost always this procedure is sufficient to factor safe semiprimes which are defined as the product of two safe primes. This class of primes was introduced by Sophie Germain in her study of Fermat’s last theorem.