Factoring numbers in O(log n) arithmetic steps

DOI10.1016/0020-0190(79)90087-5zbMath0401.68018OpenAlexW1508811963MaRDI QIDQ1255313

Adi Shamir

Publication date: 1979

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(79)90087-5

zbMATH Keywords

Number TheoryComputational ComplexityArithmetic ComplexityComplexity of Factoring AlgorithmsPrime Numbers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Radix representation; digital problems (11A63) Algorithms in computer science (68W99)

Cites Work

• A method for obtaining digital signatures and public-key cryptosystems
• Hilbert's Tenth Problem is Unsolvable
• Unnamed Item
• Unnamed Item

Related Items (17)

Terms of Lucas sequences having a large smooth divisor ⋮ Irreducibility of multivariate polynomials ⋮ Communication Complexity of Conditional Disclosure of Secrets and Attribute-Based Encryption ⋮ Boolean circuits versus arithmetic circuits ⋮ Computing discrete logarithms using \(\mathcal{O}((\log q)^2)\) operations from \(\{+,-,\times,\div,\&\}\) ⋮ Real data-integer solution problems within the Blum-Shub-Smale computational model ⋮ P-RAM vs. RP-RAM ⋮ On Faster Integer Calculations Using Non-arithmetic Primitives ⋮ Arbitrary sequence RAMs ⋮ The Road to Quantum Computational Supremacy ⋮ Generic hardness of inversion on ring and its relation to self-bilinear map ⋮ On the ultimate complexity of factorials ⋮ On the minimum gap between sums of square roots of small integers ⋮ Unnamed Item ⋮ On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines ⋮ Lexicographic ordering, ranking and unranking of combinations ⋮ Lexicographic Enumeration of k-ary Trees

This page was built for publication: Factoring numbers in O(log n) arithmetic steps