Pomykała, Jacek Small generating sets and DLPC problem. (English) Zbl 1395.11137 Fundam. Inform. 145, No. 2, 143-150 (2016). 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\). Cited in 1 Review MSC: 11Y05 Factorization 11A51 Factorization; primality Keywords:factoring algorithms; \(\mathbb Z^\ast_n\)-generating sets; Dirichlet characters; smooth numbers; discrete logarithm problem for composite numbers; large sieve estimates PDFBibTeX XMLCite \textit{J. Pomykała}, Fundam. Inform. 145, No. 2, 143--150 (2016; Zbl 1395.11137) Full Text: DOI