Continued Fractions and Factoring

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.