论文标题
整数分解为子集问题
Integer factorization as subset-sum problem
论文作者
论文摘要
本文详细阐述了一种筛分技术，该技术于2018年首次应用于改善确定性整数分解的界限。我们将概括筛子，以从整数分解到多项式时间缩短到多项选择子集问题的特定实例。作为应用程序，我们将根据特殊目的的分解算法改进由差异较小的分隔线组成的整数。特别是，我们将通过大指数因子来完善Fermat分解算法的运行时复杂性。我们的第一个程序是确定性，严格，易于实施，并且空间复杂性可忽略不计。我们的第二个程序在启发式上比第一个程序更快，但具有不可忽略的空间复杂性。
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.
