On the ultimate complexity of factorials (Q703565)

Let \(y\) be a positive integer. A positive integer is said to be \(y\)-smooth, if all of its prime factors are less or equal to \(y\). Let \[ \Psi(x,y)= |\{n\in\mathbb{Z}: 0< n\leq x\text{ and }n\text{ is }y\text{-smooth}\}| \] and \(L_x[c]= \exp\{c\sqrt{\log x\log\log x}\}\). A widely believed conjecture asserts that for any constant \(a> 0\), we have \[ \Psi(p+ 1+ 2\sqrt{p}, L_p[a])- \Psi(p+ 1- 2\sqrt{p}, L_p[a])= \sqrt{p}, L_p[-1/2a+ o(1)]. \] In the paper under review, the author assumes that the above conjecture is true and proves that there exist absolute constants \(c_1\) and \(c_2\) such that for any natural number \(n\), a nonzero multiple of \(n!\) can be computed by a straight-line program of length at most \(L_n[c_1]\). Furthermore, the straight-line program can be constructed in time \(L_n[c_2]\) by a probabilistic Turing machine. Note that the essential part of the proof of this result is relied on Lenstra's elliptic curve factorization method.