Small Generating Sets and DLPC Problem

Abstract

In the paper we investigate the set of odd, squarefree positive integers n that can be factored completely in polynomial time O(log^6+ɛn), given the prime decomposition of orders ord _n b 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(log^6+ɛn), is at most (η − 2)⁻¹x(log x)^−c(η−2), for some c > 0 and arbitrary ɛ > 0.