Computing (N) for an RSA module with a single quantum query

DOI10.1007/S11128-025-05008-WMaRDI QIDQ6860586zbMATH OpenFDO

Authors Luis Dieulefait, Jorge J. Urroz

Publication date 10 February 2026

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

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S11128-025-05008-W

zbMATH Keywords

Euler's \(\varphi\) functionfactorization of integersShor's algorithm

Mathematics Subject Classification ID

Quantum computation (81P68)

Cites work

• A method for obtaining digital signatures and public-key cryptosystems
• Deterministic polynomial-time equivalence of computing the RSA secret key and factoring
• Every integer can be written as a square plus a squarefree
• scientific article; zbMATH DE number 1617936 (Why is no real title available?)
• Improving the success probability for Shor's factorization algorithm
• Integer multiplication in time \(O(n\log n)\)
• Odd orders in Shor's factoring algorithm
• On completely factoring any integer efficiently in a single run of an order-finding algorithm
• On post-processing in the quantum algorithm for computing short discrete logarithms
• On Schönhage's algorithm and subquadratic integer gcd computation
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum algorithms for computing short discrete logarithms and factoring RSA integers
• Small solutions to polynomial equations, and low exponent RSA vulnerabilities
• Square rooting is as difficult as multiplication

This page was built for publication: Computing \(\varphi(N)\) for an RSA module with a single quantum query

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