Quadratic Sieve
first made: 2021-10-19
Abstract
Quadratic Sieve (QS) is an integer factorisation algorithm of great historical significance, in fact the second-best such algorithm - and the grandfather of the best (General Number Field Sieve). We will explore a basic and simplified version of it, and understand in what sense it is "simplified."
We will discuss it and its role in the cryptographic historical context, using the RSA cryptosystem to contextualise its cryptographic relevance.
Notes
This talk was part of the Percorso Eccellenza in Matematica ("Excellency Path in Mathematics") of the University of Trento. The topic was suggested and supervised by Prof. Nadir Murru from the University of Trento, whom I thank for his prompt availability.
Material
Bibliography
For the historical perspective, I mainly relied on Pomerance’s article A Tale of Two Sieves; a highly interesting read for anyone looking to dive deeper. The other - much more technical - sources are in the pdf.