CONTINUED FRACTIONS AND FACTORING - MICHELE ELIA

"Continued fractions and factoring"
Michele Elia - Politecnico di Torino
Venerdì 6 Dicembre 2019 - ore 15:00
Sala Orsi, Dipartimento di Matematica "G. Peano"
Università di Torino, Via Carlo Alberto 10

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.

• Link al sito CrypTo - Gruppo di ricerca interateneo di Crittografia e Teoria dei Numeri