Integer factorization as subset-sum problem
arXiv:2205.10074 · doi:10.1016/j.jnt.2023.02.010
Abstract
This paper elaborates on a sieving technique that has first been applied in 2018 for improving bounds on deterministic integer factorization. We will generalize the sieve in order to obtain a polynomial-time reduction from integer factorization to a specific instance of the multiple-choice subset-sum problem. As an application, we will improve upon special purpose factorization algorithms for integers composed of divisors with small difference. In particular, we will refine the runtime complexity of Fermat's factorization algorithm by a large subexponential factor. Our first procedure is deterministic, rigorous, easy to implement and has negligible space complexity. Our second procedure is heuristically faster than the first, but has non-negligible space complexity.
arXiv comment22 pages (including appendix), v2: Corrected technical typo in Theorem 3.5, Corollary 7.4, and Remark 7.5
References in corpus (4)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- A babystep-giantstep method for faster deterministic integer factorization
- A log-log speedup for exponent one-fifth deterministic integer factorisation
- A time-space tradeoff for Lehman's deterministic integer factorization method