Paper 2024/2034
The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
Abstract
We present a compact quantum circuit for factoring a large class of integers, including some whose classical hardness is expected to be equivalent to RSA (but not including RSA integers themselves). Most notably, we factor
Note: Minor updates.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Major revision. STOC 2025
- Keywords
- factoringquantumShor's algorithmsquarefree decomposition
- Contact author(s)
-
gkm @ mit edu
sragavan @ mit edu
vinodv @ mit edu
kvankirk @ g harvard edu - History
- 2025-06-05: last of 4 revisions
- 2024-12-17: received
- See all versions
- Short URL
- https://ia.cr/2024/2034
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/2034, author = {Gregory D. Kahanamoku-Meyer and Seyoon Ragavan and Vinod Vaikuntanathan and Katherine Van Kirk}, title = {The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/2034}, year = {2024}, url = {https://eprint.iacr.org/2024/2034} }