Affiliations: Institute of Mathematics, Warsaw University, Banacha 2, 02-097 Warszawa, Poland. pomykala@mimuw.edu.pl
Correspondence:
[*]
The work was supported thy NCBR grant no: DOBR/0001/RON/ID1/2013/01. Address for correspondence: Institute of Mathematics, Warsaw University, Banacha 2, 02-097 Warszawa, Poland.
Abstract: In the paper we investigate the set of odd, squarefree positive integers n that can be factored completely in polynomial time O(log6+ɛ n), given the prime decomposition of orders ordnb for b ≤ logη n, (η > 2), which is closely related to DLPC problem. We prove that the number of n ≤ x that may not be factored in deterministic time O(log6+ɛ n), is at most (η − 2)−1x(log x)−c(η−2), for some c > 0 and arbitrary ɛ > 0.
Keywords: factoring algorithms, Z*n-generating sets, Dirichlet characters, smooth numbers, discrete logarithm problem for composite numbers, large sieve estimates
