On the ultimate complexity of factorials
type: Item
instance of: scholarly article
title: On the ultimate complexity of factorials
zbMATH Open document ID: 1079.11060
author: Qi Cheng
published in: Theoretical Computer Science
publication date: 2005-01-11T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 2126124
zbMATH Keywords: computational and structural complexity
zbMATH Keywords: elliptic curve
zbMATH Keywords: factorization
reviewed by: Dimitros Poulakis
MaRDI profile type: Publication
full work available at URL: j.tcs.2004.06.020
OpenAlex ID: W2007080245
cites work: Q4372496
cites work: On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
cites work: Q4331740
cites work: On a problem of Oppenheim concerning ''Factorisatio Numerorum''
cites work: Q4425948
cites work: Torsion points on elliptic curves and \(q\)-coefficients of modular forms
cites work: Torsion points on elliptic curves defined over quadratic fields
cites work: Q4385516
cites work: Factoring integers with elliptic curves
cites work: Factoring numbers in O(log n) arithmetic steps
cites work: On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?''
cites work: Q3710637
cites work: Some results on computational complexity
DOI: 10.1016/J.TCS.2004.06.020
description: scientific article; zbMATH DE number 2126124