因此，在本周的新闻中，IBM创建了具有5个全功能量子位的通用量子计算机。逻辑和摩尔定律规定，他们将能够在几年内将其扩展到更多的量子比特。使用Shor算法，由于椭圆曲线的密钥长度较短，因此很可能会率先使用椭圆曲线加密技术，因此需要较少的量子位来破解它。如果使用具有更大密钥大小的RSA，例如2048位，这可能会花费几年的时间，希望可以过渡到后量子算法。

有人知道吗：


用量子计算机实时破解RSA 2048和RSA 4096需要多少个量子位？
打破Curve25519需要多少个量子位？
我想弄清楚密钥长度和长度之间的关系。打破该密钥长度所需的位数。是否有一个简单的外行公式来计算需要多少个qubit，使用密钥位数和qubit位数作为函数的输入？例如。 n =公钥位数，q =机器拥有的位数，a =答案（破解所需的位数）。也许公式只是a = n = q，即需要2048量子位才能破解RSA2048。

如果您可以通过引用任何论文或研究来证明自己的答案也将是有益的。 />
编辑：我找到了这个答案。无论如何，如果我将N = 2048插入Θ（log（N ^ 2））方程中，这将为我提供分解RSA 2048所需的15.25量子位。RSA4096位并不是更好，仅需要16量子位。那是对的吗？！为什么每个人都没有着火乱跑呢？

#1 楼



使用量子计算机实时破解RSA 2048和RSA 4096需要多少个量子位？



像您链接的答案一样如图所示，大约$ \ log_2（N ^ 2）= 2 \ log_2（N）$或只是$ 2n $，其中$ n $是模数$ N $的位数，即RSA的密钥大小。因此2048位RSA的4096，是4096位RSA的两倍。

本文（PDF）有一种使用$ 2n + 3 $量子位的算法，其中$ n = \ log_2（N）$，其中$ \ log_2（N）$是计算$ N $中位数的方法。



要打破Curve25519需要多少个量子位？



破坏椭圆曲线需要（pdf，参见6.2）大约$ 6n $量子位，其中$ n $是曲线的阶数或键大小，对于Curve25519而言，则为$ 6 * 255 = 1530 $。小于安全RSA大小所需的数量，但远远超过已完成的数量。



我想弄清密钥长度和破解该密钥所需的位数之间的关系。键长。



请参见上文。



编辑：我找到了这个答案。无论如何，如果我将N = 2048插入Θ（log（N ^ 2））方程中，这将为我提供分解RSA 2048所需的15.25量子位。RSA4096位并不是更好，仅需要16量子位。那是对的吗？！为什么每个人都没有着火呢？


您为$ N $使用了错误的值。它是模数，而不是位长。 2048位RSA所需的实际qubit数量约为4096。


注意（从删除的注释到当前答案）：在这里我们谈论的是理想的qubit。纠错可能会增加物理量子位的数量，超出这些数量。

评论

$ \ begingroup $
答案已被编辑为包括注释中显示的计算。在收到“评论删除”请求标记后，已过时的评论已出于历史目的而移至聊天。
$ \ endgroup $
– e-sushi
18年5月23日在15:18