8
$\begingroup$

We all known that RSA can be compromised using quantum Shor's algorithm. The horsepower underlying this algorithm is the Fourier transform. However, we can use alternatives to perform this function, such as An optical Fourier transform coprocessor with direct phase determination.

In accordance to the paper, you may need a high resolution optical sensor for this task. But how high does it need to be? Can we get a rough estimation using a lower resolution and guess something close?

Are such alternatives viable (in a near future) to break RSA?

PS: The largest optical sensor in existence is a 3.2 gigapixel

$\endgroup$
5
$\begingroup$

The horsepower underlying this algorithm is the Fourier transform

Not quite; the algorithm is to generate a superposition of states, compute the modular exponentiation of those states (generating the superposition of those results), and then use a Quantum FFT (actually, the inverse FFT[1]) to find a periodicity (and from such a period, you can deduce the factorization).

The issue for you is that this is an inherently quantum operation; the hardware you linked to performs a Discrete (Classical) FFT [2], which doesn't operation on superpositions. And, if you don't perform the inverse FFT on a superposition, then you can't implement Shor's algorithm.

Hence, your idea using an optical hardware within superposition doesn't solve the problem at all...

Are such alternatives viable (in a near future) to break RSA?

It doesn't appear that way...

[1] Requiring an inverse FFT isn't the main objection - I believe optics can perform that operation as well...

[2] Actually, it's rather easy to compute FFTs (and inverse FFTs) in software - the linked hardware's just claims it can compute it somewhat faster, but software already is pretty fast...

| improve this answer | |
$\endgroup$
  • $\begingroup$ OK, seems we can still rest for awhile. $\endgroup$ – shumy Feb 4 at 10:15
  • $\begingroup$ @shumy: yes, at least until someone builds a moderately large error-correcting Quantum Computer... $\endgroup$ – poncho Feb 4 at 14:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.