On Deterministic Reduction of Factoring Integers to Computing the Exponents of Elements in Modular Group

Abstract

In the paper we prove that all but at most x/A(x) positive integers n ≤ x can be completely factored in deterministic polynomial time C(x), querying the prime decomposition exponent oracle at most D(x) times. The functions A(x), C(x) and D(x) have the polynomial growth (of log x) at infinity.