因数分解问题的一些技术讨论

[Caravel]

https://crypto.stackexchange.com/questi ... -not-secur

“Claus Peter Schnorr recently posted a 12-page factoring method by SVP algorithms. Is it correct?

It says that the algorithm factors integers N≈2^400
and N≈2^800
by 4.2⋅109
and 8.4⋅1010
arithmetic operations."

那篇量子计算文章based on一个有争议的经典算法Schnorr factoring。 业内专家的实验表明需要尝试的次数远大于论文claim。

This suggest that the approach may be sensible, but that not all short vectors give rise to factoring relations, and that obtaining a sufficient success rate requires much larger lattice dimension than claimed in [Sch21].

Personnal study (unfortunately, never written down cleanly) of this approach suggested me that this approach requires solving SVP in dimensions beyond reasonable, leading to a factorization algorithm much slower than the state of the art. My impression is that this is the consensus among experts having spent some time on it as well.

[FoxMe]

应该说Schnorr这个算法理论上是成立的，并且该算法是Adleman（RSA之一）早先提出的，争议只是复杂度。行内的人跑了算法，但是发现并没有他说的那么快。

那篇量子计算文章基于这个算法，问题就比较大了。

[Caravel]

应该说Schnorr这个算法理论上是成立的，并且该算法是Adleman（RSA之一）早先提出的，争议只是复杂度。行内的人跑了算法，但是发现并没有他说的那么快。

那篇量子计算文章基于这个算法，问题就比较大了。

时间复杂度是最关键的，慢的就没有意义了，现在1024位经典算法也能破了，需要很长时间就是了。

[FoxMe]

这就是量子计算的问题所在。肖彼得画了座空中楼阁，目前实现不了；所以人们转向NISQ，但是没有令人信服的结果。

[Caravel]

这就是量子计算的问题所在。肖彼得画了座空中楼阁，目前实现不了；所以人们转向NISQ，但是没有令人信服的结果。

用在计算化学上更有用，破解RSA其实是很无聊的应用，只是因为他容易验证猜提出来

[FoxMe]

我觉得量子计算的试金石就是破解RSA，如果能做到，那么就是一锤定音。

[Caravel]

我觉得量子计算的试金石就是破解RSA，如果能做到，那么就是一锤定音。

有人预测过shor算法破2048可能需要上万个logic qbit，几百万个physical qbit，没那么容易。这就好比，你当了首富可以追到女神姑娘，但是追到女神未必需要当首富。