Square form factorization, II
Volume 70 / 2022
Bulletin Polish Acad. Sci. Math. 70 (2022), 13-34
MSC: Primary 11A51; Secondary 11E16, 11R11, 11Y05.
DOI: 10.4064/ba211003-1-11
Published online: 2 December 2022
Abstract
We propose a new subexponential time integer factoring algorithm called SQUFOF2, based on ideas of D. Shanks and R. de Vogelaere. It begins by using a sieve like that in the multiple polynomial Quadratic Sieve to construct a square value of a binary quadratic form. It uses this value to produce a square form. Then it factors the integer $N$ as the original SQUFOF does by taking an inverse square root and following a nonprincipal cycle to a symmetry point. This marriage with the Quadratic Sieve transforms SQUFOF from an $O(N^{1/4})$ algorithm into one with subexponential time. On the way we prove new facts about the infrastructure distance, which is used in the time complexity analysis.
