Continued Fractions and Factoring

Abstract

Legendre found that the continued fraction expansion of $\sqrt{N}$ having odd period leads directly to an explicit representation of $N$ as the sum of two squares. Similarly, it is shown here that the continued fraction expansion of $\sqrt{N}$ having even period directly produces a factor of a composite $N$. Shanks' infrastructural method is then revisited, and some consequences of its application to factorization by means of the continued fraction expansion of $\sqrt{N}$ are derived.

21 pages

Cited by in corpus (3)

• Continued Fractions of Quadratic Numbers
• Continued Fractions, Quadratic Fields, and Factoring: Some Computational Aspects
• On Means of Near Continued Fractions