|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'500'096
Articles rated: 2609
18 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Factoring Safe Semiprimes with a Single Quantum Query | | Frédéric Grosshans
; Thomas Lawson
; François Morain
; Benjamin Smith
; | | Date: |
13 Nov 2015 | | 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. | | Source: | arXiv, 1511.4385 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER