On the ultimate complexity of factorials

DOI10.1016/j.tcs.2004.06.020zbMath1079.11060OpenAlexW2007080245MaRDI QIDQ703565

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

elliptic curvefactorizationcomputational and structural complexity

Mathematics Subject Classification ID

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

Related Items

Counting arithmetic formulas ⋮ Generic hardness of inversion on ring and its relation to self-bilinear map ⋮ Algebraic Complexity Classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a problem of Oppenheim concerning Factorisatio Numerorum
• Factoring integers with elliptic curves
• Some results on computational complexity
• Factoring numbers in O(log n) arithmetic steps
• Torsion points on elliptic curves and \(q\)-coefficients of modular forms
• On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?
• Torsion points on elliptic curves defined over quadratic fields
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines