论文标题
雷曼确定性整数分解方法的时间空间权衡
A time-space tradeoff for Lehman's deterministic integer factorization method
论文作者
论文摘要
Fermat众所周知的分解算法是基于找到自然数$ n $作为正方形的表示形式。 1895年，劳伦斯（Lawrence）概括了这个想法，并将其应用于原始数字的$ kn $。雷曼（Lehman）在1974年引入了一种系统的选择，以选择合适的$ k $值，这导致第一种确定性分解算法要比试验部要快得多。在本文中，我们为劳伦斯的概括构建了一个时空权衡，并将其与雷曼的结果一起应用，以获得具有运行时复杂性$ o（n^{2/9+o（1）}）$的确定性整数分解算法。这是自1977年建立$ o（n^{1/4+o（1）}）以来的第一个指数改进。
Fermat's well-known factorization algorithm is based on finding a representation of natural numbers $N$ as the difference of squares. In 1895, Lawrence generalized this idea and applied it to multiples $kN$ of the original number. A systematic approach to choose suitable values for $k$ was introduced by Lehman in 1974, which resulted in the first deterministic factorization algorithm considerably faster than trial division. In this paper, we construct a time-space tradeoff for Lawrence's generalization and apply it together with Lehman's result to obtain a deterministic integer factorization algorithm with runtime complexity $O(N^{2/9+o(1)})$. This is the first exponential improvement since the establishment of the $O(N^{1/4+o(1)})$ bound in 1977.
