Deterministic Integer Factorization with Oracles for Euler’s Totient Function

In this paper, we construct deterministic factorization algorithms for natural numbers N under the assumption that the prime power decomposition of Euler’s totient function φ (N ) is known. Their runtime complexities depend on the number ω (N ) of distinct prime divisors of N , and we present efficient methods for relatively small values of ω (N ) as well as for its large values. One of our main goals is to establish an asymptotic expression with explicit remainder term O (x /A ) for the number of positive integers N ≤ x composed of s distinct prime factors that can be factored nontrivially in deterministic time t = t (x ), provided that the prime power decomposition of φ (N ) is known. We obtain it for A = A (x ) = x 1–ɛ , where ɛ = ɛ (s ) > 0 is sufficiently small and t = t (x ) is a polynomial in log x of degree d = d (ɛ ). An analogous bound is deduced under the assumption of the oracle providing the decomposition of orders of elements in ℤ N * .