Skip to main content
deleted 56 characters in body
Source Link
kelalaka
  • 49.5k
  • 12
  • 118
  • 205

You know much more about Shor's algorithm than I do, so I can only give a very simple-minded answer.

In N. David Mermin's Quantum Computer Science: An Introduction, in his explanation of RSA encryption in Section 3.3, he says

Efficient period finding is of interest in this cryptographic setting not only because it leads directly to efficient factoring (as described in Section 3.10), but also because it can lead Eve directly to an alternative way to decode Alice's message $b$ without her knowing or having to compute the factors $p$ and $q$ of $N$ [Bob's public key]. Here is how it works:

He then goes on to explain how to decrypt the message using Shor's algorithm for period finding in a fairly straightforward way. Only significantly later, in section 3.10 after he has completely finished explain how to use Shor's algorithm for directly decrypting RSA, does he then separately explain how Shor's period finding algorithm can also be used for factoring large numbers (which in turn can then also be used to break RSA in a different way).

This latter method seems slightly more complicated for me to understand, but I don't know which method requires more computational resources. I suspect that they're pretty close to equivalent, because I think they only differ in the classical post-processing and not in their use of the quantum Fourier transform. (Although, I believe that the classical post-processing is actually the computational bottleneck for Shor's algorithm, so maybe there is a significant difference in resources.)

You know much more about Shor's algorithm than I do, so I can only give a very simple-minded answer.

In N. David Mermin's Quantum Computer Science: An Introduction, in his explanation of RSA encryption in Section 3.3, he says

Efficient period finding is of interest in this cryptographic setting not only because it leads directly to efficient factoring (as described in Section 3.10), but also because it can lead Eve directly to an alternative way to decode Alice's message $b$ without her knowing or having to compute the factors $p$ and $q$ of $N$ [Bob's public key]. Here is how it works:

He then goes on to explain how to decrypt the message using Shor's algorithm for period finding in a fairly straightforward way. Only significantly later, in section 3.10 after he has completely finished explain how to use Shor's algorithm for directly decrypting RSA, does he then separately explain how Shor's period finding algorithm can also be used for factoring large numbers (which in turn can then also be used to break RSA in a different way).

This latter method seems slightly more complicated for me to understand, but I don't know which method requires more computational resources. I suspect that they're pretty close to equivalent, because I think they only differ in the classical post-processing and not in their use of the quantum Fourier transform. (Although, I believe that the classical post-processing is actually the computational bottleneck for Shor's algorithm, so maybe there is a significant difference in resources.)

I can only give a very simple-minded answer.

In N. David Mermin's Quantum Computer Science: An Introduction, in his explanation of RSA encryption in Section 3.3, he says

Efficient period finding is of interest in this cryptographic setting not only because it leads directly to efficient factoring (as described in Section 3.10), but also because it can lead Eve directly to an alternative way to decode Alice's message $b$ without her knowing or having to compute the factors $p$ and $q$ of $N$ [Bob's public key]. Here is how it works:

He then goes on to explain how to decrypt the message using Shor's algorithm for period finding in a fairly straightforward way. Only significantly later, in section 3.10 after he has completely finished explain how to use Shor's algorithm for directly decrypting RSA, does he then separately explain how Shor's period finding algorithm can also be used for factoring large numbers (which in turn can then also be used to break RSA in a different way).

This latter method seems slightly more complicated for me to understand, but I don't know which method requires more computational resources. I suspect that they're pretty close to equivalent, because I think they only differ in the classical post-processing and not in their use of the quantum Fourier transform. (Although, I believe that the classical post-processing is actually the computational bottleneck for Shor's algorithm, so maybe there is a significant difference in resources.)

Source Link
tparker
  • 165
  • 9

You know much more about Shor's algorithm than I do, so I can only give a very simple-minded answer.

In N. David Mermin's Quantum Computer Science: An Introduction, in his explanation of RSA encryption in Section 3.3, he says

Efficient period finding is of interest in this cryptographic setting not only because it leads directly to efficient factoring (as described in Section 3.10), but also because it can lead Eve directly to an alternative way to decode Alice's message $b$ without her knowing or having to compute the factors $p$ and $q$ of $N$ [Bob's public key]. Here is how it works:

He then goes on to explain how to decrypt the message using Shor's algorithm for period finding in a fairly straightforward way. Only significantly later, in section 3.10 after he has completely finished explain how to use Shor's algorithm for directly decrypting RSA, does he then separately explain how Shor's period finding algorithm can also be used for factoring large numbers (which in turn can then also be used to break RSA in a different way).

This latter method seems slightly more complicated for me to understand, but I don't know which method requires more computational resources. I suspect that they're pretty close to equivalent, because I think they only differ in the classical post-processing and not in their use of the quantum Fourier transform. (Although, I believe that the classical post-processing is actually the computational bottleneck for Shor's algorithm, so maybe there is a significant difference in resources.)