Continued Fractions, Quadratic Fields, and Factoring: Some Computational Aspects

Autor:	Elia, Michele
Rok vydání:	2021
Předmět:	Mathematics - Number Theory 11A55 11A51
Druh dokumentu:	Working Paper
Popis:	Legendre discovered 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. In this vein, it was recently observed that the continued fraction expansion of $\sqrt N$ having even period directly produces a factor of composite $N$. 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. Comment: 8 pages, to appear on Collectio Cyphrarum. arXiv admin note: text overlap with arXiv:1905.10704
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2103.14861 Zobrazit plný text záznamu View this record from Arxiv