我们能用光学傅里叶变换打破RSA吗？

Question

我们都知道RSA可以使用Shor的量子算法进行妥协。这种算法背后的马力是傅里叶变换。但是，我们可以使用其他方法来执行此功能，例如一种直接相位测定的光学傅里叶变换协处理器。

根据论文，您可能需要一个高分辨率的光学传感器来完成这项任务.但是它需要有多高呢？我们能用较低的分辨率得到粗略的估计吗？

这些替代方案(在不久的将来)是否有可能打破RSA？

PS:现存最大的光学传感器是32亿像素。

Answer 1

这种算法背后的马力是傅里叶变换。

不完全是这样；算法是生成一个状态的叠加，计算这些状态的模幂(产生这些结果的叠加)，然后使用一个量子FFT (实际上是逆FFT)来找到一个周期性(从这样的周期，你可以推导出因式分解)。

问题是，这是一个固有的量子操作；连接到的硬件执行离散(经典) FFT，它不对叠加操作。如果不对叠加执行逆FFT，那么就不能实现Shor的算法。

因此，你在叠加中使用光学硬件的想法根本解决不了这个问题。

这些替代方案(在不久的将来)是否有可能打破RSA？

不是这样的..。

需要一个反FFT不是主要的反对-我相信光学也可以执行那个操作。

实际上，在软件中计算FFT(和反向FFT)是相当容易的--链接硬件只是声称它可以更快地计算它，但是软件已经相当快.

Answer 2

对于n-bit RSA密钥，需要进行傅里叶变换的顺序为-bit，n= 2048通常是这样的。这对于任何经典的机器来说都太大了，即使使用物理光学。