楼主:
rafe (Out of the hole)
2021-04-13 00:08:26※ 引述《jackliao1990 (j)》之铭言：
: https://eprint.iacr.org/2021/232.pdf
: 一般认为,我们要等到使用秀尔算法的量子电脑普及后,RSA加密法才会被破解。然而
本
: 文宣称透过晶格密码学中的SVP法(寻找最接近向量)，即使使用传统电脑，我们也有机
会
: 比二次筛选法和普通数域筛选法(已知最快的传统因子分解算法)更快完成分解。
: 这篇论文目前还未通过同行评审。GitHub上已经有人实作文中的算法,但是没人成功。
也
: 有人指出论文中的可能漏洞:文中"将整数的指数加倍"这操作在过去被认为需要指数时
间
: ，但作者却"证明"这需要多项式时间。这表示:过去被认为属于NP问题的操作，被本文
证
: 明属于P，这样岂不就证明P=NP了?(然而质因子分解从没被证明是NP完全问题)
解说一下什么是P=NP
P的意思是polynomial，也就是线性或多项式，NP则指非线性或是指数。
这俩个词是形容问题的复杂度，以玩游戏来举例，
例如说打只狼破关，你花的时间大致上是线性的，
如果增加魔王，或是出了dlc你大概只要多花几个小时就能破关。
而NP问题就像是要挑战无伤破关，你要不断全破好几次去熟悉魔王，找出最佳的路径，道
具
跟策略。加一个头目或dlc，代表的是好几天，几个月或几年的训练。
作者证明RSA可被破解，就像是说他找到了方法可以无伤忍杀掉所有魔王，
让打倒魔王花的时间变成线性，不论加了多少头目玩家都只要多花几个小时就能无伤通关
，
只狼变成手游难度，是完全的平衡破坏者。
而证明P=NP就比较像是哲学问题，简单来讲就是对于这世上所有的困难问题，
能不能证明他们都存在一个简单的解法，
就像是说不止是只狼，世上所有的游戏都存在类似的秘技可以无伤通关，只是还没被发现
而已。
衍生来说可以说证明了P=NP，就等于是证明了世上存在着某种真理一样。