Back to search

Università degli studi di Trento

An investigation on Integer Factorization applied to Public Key Cryptography

Abstract

dc:description

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.

Degree

thesis:*
Grantor dc:publisher
Università degli studi di Trento
Year dc:date
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Santilli, Giordano
Contributors dc:contributor
  • Sala, Massimiliano

Subjects

dc:subject × 1

Rights

dc:rights
Statement dc:rights
  • info:eu-repo/semantics/closedAccess
  • license:Tutti i diritti riservati (All rights reserved)
Language dc:language
eng

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Università degli Studi di Trento
Base URL
iris.unitn.it/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Santilli, Giordano. An investigation on Integer Factorization applied to Public Key Cryptography. Università degli studi di Trento, 2019. https://hdl.handle.net/11572/369253