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 phi(N) is known. Their runtime complexities depend on the number omega(N) of distinct prime divisors of N, and we present efficient methods for relatively small values of omega(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 phi(N) is known. We obtain it for A = A(x) = x(1-epsilon), where epsilon = epsilon(s) 0 is sufficiently small and t = t(x) is a polynomial in log x of degree d = d(epsilon) . An analogous bound is deduced under the assumption of the oracle providing the decomposition of orders of elements in Z(N)*.