Continued Fractions, Quadratic Forms, and Regulator Computation for Integer Factorization

Abstract: In the realm of integer factorization, certain methods, such as CFRAC, leverage the properties of continued fractions, while others, like SQUFOF, combine these properties with the tools provided by quadratic forms. Recently, Michele Elia revisited the fundamental concepts of SQUFOF, including reduced quadratic forms, distance between quadratic forms, and Gauss composition, offering a new perspective for designing factorization methods.

In this seminar, we present our algorithm, which is a refinement of Elia's method, along with a precise analysis of its computational cost. Our algorithm is polynomial-time, provided knowledge of a (not too large) multiple of the regulator of $\mathbb{Q}(\sqrt{N})$. The computation of the regulator governs the total computational cost, which is subexponential, and in particular $O(\exp(\frac{3}{\sqrt{8}}\sqrt{\ln N \ln \ln N}))$. This makes our method more efficient than CFRAC and SQUFOF, though less efficient than the General Number Field Sieve.

We identify a broad family of integers to which our method is applicable including certain classes of RSA moduli. Finally, we introduce some promising avenues for refining our method. These span several areas, ranging from Algebraic Number Theory, particularly for estimating the size of the regulator of $\mathbb{Q}(\sqrt{N})$, to Analytic Number Theory, particularly for computing a specific class of $L$-functions.

Joint work with Nadir Murru.

dynamical systemsnumber theory

Audience: researchers in the topic

( paper | slides )

---

One World Numeration seminar

Series comments: Description: Online seminar on numeration systems and related topics

For questions or subscribing to the mailing list, contact the organisers at numeration@irif.fr

---