Categoria: Seminari e Convegni
Stato: Archiviata
6 dicembre 2019 - ore 15,00

Continued fractions and factoring

Sala Orsi, Dipartimento di Matematica "G. Peano" - Università di Torino, Via Carlo Alberto 10

"Continued fractions and factoring"
Michele Elia - Politecnico di Torino

Abstract: Legendre found that the continued fraction expansion of √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 √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 √N are derived.