An Investigation on Integer Factorization applied to Public Key Cryptography

Cycle 31th Oral Defence of the Phd Thesis

October 4, 2019
Versione stampabile

Venue: Seminar Room “-1” – Department of Mathematics – Via Sommarive, 14 Povo - Trento
Time: 11.00 a.m.

  • Giordano Santilli - PhD in Mathematics

Public key cryptography allows two or more users to communicate in a secure way on an insecure channel, using two different keys: a public key, which has the function to encrypt the messages, and a private key, employed in the decryption of the ciphertext. Because of the importance of these keys, their generation is a sensible issue and it is often based on an underlying mathematical problem, which is considered hard to be solved. Among these difficult 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 (worst-case complexity).
In this talk, after a brief explaination of the developments on integer factorization and a description of the General Number Field Sieve (GNFS), I will present different strategies to face this well-known problem of Number Theory. First, I will show an attempt to improve GNFS, considering two linearly disjoint quadratic fields Q(θ1) and Q(θ2) and studying the relation between first-degree prime ideals in Z[θ1] and Z[θ2] and those in Z[θ], where Q(θ) is the quartic extension that contains both Q(θ1) and Q(θ2). Secondly, I will characterize the elements used in GNFS through some systems having integer solutions, that can be found using Groebner Bases.

Supervisor: Massimiliano Sala