On completely factoring any integer efficiently in a single run of an order-finding algorithm

DOI10.1007/S11128-021-03069-1MaRDI QIDQ2690484zbMATH OpenOpenAlexFDO

Authors Martin Ekerå

Publication date 17 March 2023

Published in Quantum Information Processing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2007.10044

zbMATH Keywords

factoringorder findingShor's algorithms

Mathematics Subject Classification ID

Factorization; primality (11A51) Factorization (11Y05) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Recommendations

• Odd orders in Shor's factoring algorithm
• On computing ord\(_{N}(2)\) and its application
• Probability estimates for Shor's algorithm
• Improving the success probability for Shor's factorization algorithm
• Factorization

Cites work

• A method for obtaining digital signatures and public-key cryptosystems
• Detecting perfect powers by factoring into coprimes
• Factoring polynomials with rational coefficients
• scientific article; zbMATH DE number 1617936 (Why is no real title available?)
• scientific article; zbMATH DE number 3460351 (Why is no real title available?)
• Improving the success probability for Shor's factorization algorithm
• Odd orders in Shor's factoring algorithm
• On post-processing in the quantum algorithm for computing short discrete logarithms
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Probabilistic algorithm for testing primality
• Probability estimates for Shor's algorithm
• Quantum algorithms for computing general discrete logarithms and orders with tradeoffs
• Quantum algorithms for computing short discrete logarithms and factoring RSA integers
• Riemann's hypothesis and tests for primality
• The discrete logarithm modulo a composite hides \(O(n)\) bits

Cited in

(6)

• Odd orders in Shor's factoring algorithm
• Finding eigenvectors with a quantum variational algorithm
• Computing (N) for an RSA module with a single quantum query
• Reducing the number of qubits in quantum factoring
• Extending Regev's factoring algorithm to compute discrete logarithms
• Parallel spooky pebbling makes Regev factoring more practical

This page was built for publication: On completely factoring any integer efficiently in a single run of an order-finding algorithm

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