Small Generating Sets and DLPC Problem

In the paper we investigate the set of odd, squarefree positive integers n that can be factored completely in polynomial timeO(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.

---

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.