Quadratic Sieve

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 context, using the RSA cryptosystem to contextualise its 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.

The intended audience is intermediate and with a little background in number theory.

Material

• handout (IT)
• slides (IT)

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.