Integer factoring and compositeness witnesses

Abstract

We describe a reduction of the problem of factorization of integers n ≤ x in polynomial-time (log x)M+O(1) to computing Euler’s totient function, with exceptions of at most xO(1/M) composite integers that cannot be factored at all, and at most x exp −cM(loglog⁡x)3(logloglog⁡x)2$\begin{array}{} \displaystyle \left(-\frac{c_M(\log\log x)^3}{(\log\log\log x)^2}\right) \end{array}$ integers that cannot be factored completely. The problem of factoring square-free integers n is similarly reduced to that of computing a multiple D of ϕ(n), where D ≪ exp((log x)O(1)), with the exception of at most xO(1/M) integers that cannot be factored at all, in particular O(x1/M) integers of the form n = pq that cannot be factored.

Keywords

• large sieve
• factoring algorithms
• zn*-generating sets
• dirichlet characters
• smooth numbers
• discrete logarithm problem for composite numbers
• primality testing
• euler’s totient function
• rsa
• 11a05
• 11a15
• 11a51
• 11m06
• 11z05
• computational number theory: 11y05
• 11y16