17 Luglio 2020

Seminario: "An investigation on Integer Factorization applied to Public Key Cryptography" - Giordano Santilli

Seminario di De Cifris Augustae Taurinorum, in collaborazione con il Dipartimento di Scienze Matematiche "G.L. Lagrange" del Politecnico di Torino, il Dipartimento di Matematica "G. Peano" dell'Università degli Studi di Torino, Quadrans Foundation e Telsy SPA.

"An investigation on Integer Factorization applied to Public Key Cryptography"
Giordano Santilli - Università di Trento

Venerdì 17 Luglio 2020 - ore 14:30

Abstract: Among the difficult number-theoretic problems, the Integer Factorization Problem (IFP) is one of the most famous: given a composite integer number, recovering its factors is commonly believed to be hard. Many asymmetric algorithms such as RSA found their mathematical security on IFP. In this talk I will present two different approaches to attempt to solve IFP: the first one is a study on the remainders of a fixed integer for successive moduli, which can be seen as a second-degree interpolating polynomial of three initial monotonic consecutive remainders. This result leads to the creation of a formula that computes all the remainders, however I will show that the problem of finding a root for this formula is equivalent to IFP. The second part of the talk will be devoted to describing a possible generalization of the GNFS protocol: starting from two simple quadratic extensions of the rational numbers it is possible to define the biquadratic extension of degree 4 that contains both. We will prove that the first-degree prime ideals in the smaller extensions may be used to generate the same kind of ideals in the larger one and, adding some additional hypotheses, we will show that also the converse is true. Using this fact, it is possible to speed up the search for smooth principal ideals in the biquadratic extension in terms of its factorization in the smaller quadratic extensions.

Slides dell'evento: Le slides utilizzate durante il seminario possono essere scaricate qui application/pdf (918,60 kB).

Video dell'evento: La registrazione del seminario è disponibile sul canale YouTube del gruppo CrypTO. Video

Pubblicato il: 30/06/2020