An investigation on Integer Factorization applied to Public Key Cryptography

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 thesis, after a brief explaination of the developments on integer factorization and a description of the General Number Field Sieve (GNFS), we will present different strategies to face this well-known problem of Number Theory. First, we will employ elementary remarks on modular arithmetic to produce a formula that describes the remainders of a given integer, starting from just three monotonic remainders and we will link this result to the behaviour of a second-degree interpolating polynomial. Secondly, we will show an attempt to improve GNFS, considering two linearly disjoint quadratic fields and study the relation between first-degree prime ideals. Finally, we will characterize the elements used in GNFS through some systems having integer solutions, that can be found using Groebner Bases.