Integer Factorization via Continued Fractions and Quadratic Forms

Abstract

We propose a novel factorization algorithm that leverages the theory underlying the SQUFOF method, including reduced quadratic forms, infrastructural distance, and Gauss composition. We also present an analysis of our method, which has a computational complexity of $O\left(\exp \left(\frac{3}{\sqrt{8}}\sqrt{\ln N\ln \ln N}\right)\right)$, making it more efficient than the classical SQUFOF and CFRAC algorithms. Additionally, our algorithm is polynomial-time, provided knowledge of a (not too large) multiple of the regulator of $\mathbb{Q}(\sqrt{N})$.

21 pages