Integer factoring and compositeness witnesses

AbstractWe describe a reduction of the problem of factorization of integersn≤xin polynomial-time (logx)M+O(1)to computing Euler’s totient function, with exceptions of at mostxO(1/M)composite integers that cannot be factored at all, and at mostxexp$\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 integersnis similarly reduced to that of computing a multipleDofϕ(n), whereD≪ exp((logx)O(1)), with the exception of at mostxO(1/M)integers that cannot be factored at all, in particularO(x1/M) integers of the formn=pqthat cannot be factored.