Politecnico di Torino (logo)

Shor's algorithm

Vito Medici

Shor's algorithm.

Rel. Antonio Lioy, Ignazio Pedone. Politecnico di Torino, Corso di laurea magistrale in Ingegneria Informatica (Computer Engineering), 2022

PDF (Tesi_di_laurea) - Tesi
Licenza: Creative Commons Attribution Non-commercial No Derivatives.

Download (3MB) | Preview

Quantum computing will be a threat to the cryptography world in the next years, as certified by the NIST call for proposals to select quantum-resistant algorithms. An analysis of the circuit needed to implement Shor’s algorithm, which can be used to break public-key cryptosystems like RSA and elliptic curves, is provided in this work, explaining all the necessary elements to understand it. Additionally, we implemented different realizations of the oracle using Qiskit, writing programs to break RSA and elliptic curve cryptography, and tested them in IBM quantum devices and simulators. The final objective is to estimate the distance between the needed capabilities to actually be able to break the security mechanisms used nowadays and the current state of the art of the quantum hardware world, considering the time that would be needed to update these mechanisms with quantum-resistant ones.

Relators: Antonio Lioy, Ignazio Pedone
Academic year: 2021/22
Publication type: Electronic
Number of Pages: 130
Corso di laurea: Corso di laurea magistrale in Ingegneria Informatica (Computer Engineering)
Classe di laurea: New organization > Master science > LM-32 - COMPUTER SYSTEMS ENGINEERING
Aziende collaboratrici: UNSPECIFIED
URI: http://webthesis.biblio.polito.it/id/eprint/22653
Modify record (reserved for operators) Modify record (reserved for operators)