Affiliations: [a] SBA Research, Floragasse 7, 1040 Vienna, Austria. [email protected] | [b] Institute of Mathematics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland. [email protected]
Correspondence:
[*]
Address for correspondence: Institute of Mathematics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland.
Abstract: 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) = x1–ɛ, 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*.
