Factoring numbers in O(log n) arithmetic steps
From MaRDI portal
Publication:1255313
DOI10.1016/0020-0190(79)90087-5zbMath0401.68018OpenAlexW1508811963MaRDI QIDQ1255313
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
Number TheoryComputational ComplexityArithmetic ComplexityComplexity of Factoring AlgorithmsPrime Numbers
Analysis of algorithms and problem complexity (68Q25) Radix representation; digital problems (11A63) Algorithms in computer science (68W99)
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
Cites Work
This page was built for publication: Factoring numbers in O(log n) arithmetic steps
