On the ultimate complexity of factorials

DOI10.1016/J.TCS.2004.06.020MaRDI QIDQ703565zbMATHOpenAlexFDO

Authors Qi Cheng

Publication date 11 January 2005

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2004.06.020

zbMATH Keywords

factorizationelliptic curvecomputational and structural complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Number-theoretic algorithms; complexity (11Y16)

Recommendations

• scientific article; zbMATH DE number 1962810
• The straight line complexity of small factorials and primorials
• On the complexity of calculating factorials
• scientific article; zbMATH DE number 1186936
• A hyperelliptic smoothness test. I

Cites work

• scientific article; zbMATH DE number 3937328 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 1096865 (Why is no real title available?)
• scientific article; zbMATH DE number 1142300 (Why is no real title available?)
• scientific article; zbMATH DE number 1979493 (Why is no real title available?)
• Factoring integers with elliptic curves
• Factoring numbers in O(log n) arithmetic steps
• On a problem of Oppenheim concerning Factorisatio Numerorum
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?
• Some results on computational complexity
• Torsion points on elliptic curves and \(q\)-coefficients of modular forms
• Torsion points on elliptic curves defined over quadratic fields

Cited in

(6)

• On the complexity of calculating factorials
• Counting arithmetic formulas
• Generic hardness of inversion on ring and its relation to self-bilinear map
• scientific article; zbMATH DE number 1962810 (Why is no real title available?)
• Semialgebraic proofs, IPS lower bounds, and the \(\tau\)-conjecture: can a natural number be negative?
• Algebraic complexity classes

This page was built for publication: On the ultimate complexity of factorials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q703565)