Factoring numbers in O(log n) arithmetic steps

DOI10.1016/0020-0190(79)90087-5MaRDI QIDQ1255313zbMATH OpenOpenAlexFDO

Authors 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

• scientific article; zbMATH DE number 3141365 (Why is no real title available?)
• scientific article; zbMATH DE number 3460351 (Why is no real title available?)
• A method for obtaining digital signatures and public-key cryptosystems
• Hilbert's Tenth Problem is Unsolvable

Cited in

(17)

• Terms of Lucas sequences having a large smooth divisor
• Generic hardness of inversion on ring and its relation to self-bilinear map
• Real data-integer solution problems within the Blum-Shub-Smale computational model
• Lexicographic ordering, ranking and unranking of combinations
• On the ultimate complexity of factorials
• On Faster Integer Calculations Using Non-arithmetic Primitives
• On the minimum gap between sums of square roots of small integers
• Communication complexity of conditional disclosure of secrets and attribute-based encryption
• Computing discrete logarithms using \(\mathcal{O}((\log q)^2)\) operations from \(\{+,-,\times,\div,\&\}\)
• Arbitrary sequence RAMs
• Boolean circuits versus arithmetic circuits
• P-RAM vs. RP-RAM
• Irreducibility of multivariate polynomials
• Lexicographic Enumeration of k-ary Trees
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• The road to quantum computational supremacy
• scientific article; zbMATH DE number 7561765 (Why is no real title available?)

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

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