Continued Fractions, Quadratic Fields, and Factoring: Some Computational Aspects
arXiv:2103.14861
Abstract
Legendre discovered that the continued fraction expansion of having odd period leads directly to an explicit representation of as the sum of two squares. In this vein, it was recently observed that the continued fraction expansion of having even period directly produces a factor of composite . It is proved here that these apparently fortuitous occurrences allow us to propose and apply a variation of Shanks' infrastructural method which significantly reduces the asymptotic computational burden with respect to currently used factoring techniques.
8 pages, to appear on Collectio Cyphrarum. arXiv admin note: text overlap with arXiv:1905.10704