×

Small generating sets and DLPC problem. (English) Zbl 1395.11137

Summary: In the paper we investigate the set of odd, squarefree positive integers \(n\) that can be factored completely in polynomial time \(O(\log^{6+\varepsilon} n)\), given the prime decomposition of orders \(\mathrm{ord}_nb\) for \(b\leq\log^\eta n\), (\(\eta>2\)), which is closely related to DLPC problem. We prove that the number of \(n\leq x\) that may not be factored in deterministic time \(O(\log^{6+\varepsilon}n)\), is at most \((\eta-2)^{-1}x(\log x)^{-c(\eta-2)}\), for some \(c>0\) and arbitrary \(\varepsilon > 0\).

MSC:

11Y05 Factorization
11A51 Factorization; primality
PDFBibTeX XMLCite
Full Text: DOI