ACE Seminar: (Slightly) more practical quantum factoring

Speaker: Ben Smith

Date/Time: 04-Jun-2015, 15:00 UTC

Venue: MPEB 1.20

Details

Abstract

We use elementary number theory to improve the practical efficiency of Shor's quantum integer factorization algorithm. We find that one application of the quantum subroutine is always enough to factor strong RSA keys; further, in this case Shor's algorithm can be made completely deterministic.  This implies the somewhat surprising result that while strong RSA moduli are considered to be the hardest case for classical factoring algorithms, they are in fact the easiest case for Shor's algorithm.
 
This is a progress report on joint work with Frédéric Grosshans, Thomas Lawson, and François Morain. 

Bio

 

Ben Smith is a researcher in algorithmic number theory and asymmetric cryptography at INRIA (the French national computer science research institute) and the École Polytechnique.

Add to Calendar

This page was last modified on 27 Mar 2014.