An investigation on integer factorization applied to public key cryptography
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
Sarà possibile seguire live il seminario mediante Zoom, attraverso il seguente link: An investigation on Integer Factorization applied to Public Key Cryptography
Il client di Zoom esiste su ogni piattaforma e può essere scaricato gratuitamente al link: https://zoom.us/download
In caso aveste dei problemi a seguire il seminario in diretta, vi ricordiamo che tutti i seminari sono visionabili a posteriori sul canale YouTube CrypTO.
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.