Factoring Safe Semiprimes with a Single Quantum Query

Abstract : Shor's factoring algorithm (SFA), by its ability to efficiently factor large numbers, has the potential to undermine contemporary encryption. At its heart is a process called order finding, which quantum mechanics lets us perform efficiently. SFA thus consists of a quantum order finding algorithm (QOFA), bookended by classical routines which, given the order, return the factors. But, with probability up to 1/2, these classical routines fail, and QOFA must be rerun. We modify these routines using elementary results in number theory, improving the likelihood that they return the factors. We present a new quantum factoring algorithm based on QOFA which is better than SFA at factoring safe semiprimes, an important class of numbers used in RSA encryption (and reputed to be the hardest to factor). With just one call to QOFA, our algorithm almost always factors safe semiprimes. As well as a speed-up, improving efficiency gives our algorithm other, practical advantages: unlike SFA, it does not need a randomly picked input, making it simpler to construct in the lab; and in the (unlikely) case of failure, the same circuit can be rerun, without modification. We consider generalising this result to other cases, although we do not find a simple extension, and conclude that SFA is still the best algorithm for general numbers (non safe semiprimes, in other words). Even so, we present some simple number theoretic tricks for improving SFA in this case.
Type de document :
Pré-publication, Document de travail
2016
Liste complète des métadonnées

https://hal.inria.fr/hal-01229587
Contributeur : Benjamin Smith <>
Soumis le : lundi 16 novembre 2015 - 23:57:51
Dernière modification le : lundi 22 octobre 2018 - 14:48:04

Lien texte intégral

Identifiants

  • HAL Id : hal-01229587, version 1
  • ARXIV : 1511.04385

Citation

Frédéric Grosshans, Thomas Lawson, Benjamin Smith, François Morain. Factoring Safe Semiprimes with a Single Quantum Query. 2016. 〈hal-01229587〉

Partager

Métriques

Consultations de la notice

469