论文链接 https://arxiv.org/pdf/2212.12372.pdf

相关新闻链接 https://www.schneier.com/blog/archives/2023/01/breaking-rsa-with-a-quantum-computer.html

但是貌似放了个空炮－并且是故意放的 https://scottaaronson.blog/?p=6957
--
FROM 37.136.12.*

整数 factor 到素数的算法目前用量子计算机的复杂度是 5 logN。但这篇论文声称复杂度是  (log N) / (log log N)，并且只需要少得多的 noise-tolerant qbits，其后果是目前 IBM 的量子计算机即可有效的破解 RSA-2048 － 非常惊人的结论。作者声称已经用 10 qbits 分解了 2^48 的整数。同时，这篇论文还号称对 lattice 有根本性的改进，于是暗示对 lattice 为基础的 post quant crypto 也有严重后果（NIST round3 面临挑战）。所以如果属实的话，是个双杀的突破性进展。

然而，貌似不仅论证过程有错，而且是作者明知道结论错误还是强行投稿给某期刊，意图误导群众，“intent to mislead”。
--
FROM 37.136.12.*

这篇论文的通讯作者，龙桂鲁，清华大学物理系高能物理与核物理研究所所长，在最后那个链接的 blog 后面回复了。大意是，我们的方法也许不会更快，但是分解了目前创纪录的最大的 48bits 整数； Shor 在一篇访谈中给我们的方法以正面评价；我们在 conclusion 中明确指出了这个算法目前缺乏复杂度分析。


而 blog 作者也给出了回应，大意是你既然自己都知道没有复杂度上的进展，干嘛不在 abstract 里直说。潜台词是你这是搞眼球经济，故意误导没知识的普通群众。




【 在 vale 的大作中提到: 】
: 这是图啥 ...
--
FROM 37.136.12.*

那就是算法有效，但效果并没有论文中声称的那么好？
--
FROM 171.221.52.*

分解48位这个也没实际证明啊，国内有堪用的量子计算机么

【 在 philbloo 的大作中提到: 】
:
: 整数 factor 到素数的算法目前用量子计算机的复杂度是 5 logN。但这篇论文声称复杂度是 (log N) / (log log N)，并且只需要少得多的 noise-tolerant qbits，其后果是目前 IBM 的量子计算机即可有效的破解 RSA-2048 － 非常惊人的结论。作者声称已经用 10 qbits 分解了 2^48 的整数。同时，这篇论文还号称对 lattice 有根本性的改进，于是暗示对 lattice 为基础的 post quant crypto 也有严重后果（NIST round3 面临挑战）。所以如果属实的话，是个双杀的突破性进展。
:
: 然而，貌似不仅论证过程有错，而且是作者明知道结论错误还是强行投稿给某期刊，意图误导群众，“intent to mislead”。

#发自zSMTH@Mi 10 Pro
--
FROM 223.104.40.*