Small Generating Sets and DLPC Problem
Jacek Pomykała · Fundamenta Informaticae · 2016
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) −1 x(log x) − c( η−2) , for some c > 0 and arbitrary ɛ > 0.