Re: [爆卦] 德国密码学家宣称自己摧毁了RSA加密法

楼主: 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,就等于是证明了世上存在着某种真理一样。
作者: johnhmj (耗呆肥羊)   2021-04-13 00:10:00
先推,不然别人以为我看不懂
作者: StylishTrade   2021-04-13 00:10:00
所以多项式难度如果是n的100次方 你算的出来吗 XDDD他只是把2的n次方 改成n的xx次方 xx可能很大阿
作者: wei115 (ㄎㄎ)   2021-04-13 00:13:00
所以说是哲学问题啊,爽过之后还是要面对现实,不过很爽就4惹
作者: TheBeast (边缘肥宅)   2021-04-13 00:14:00
差多惹 那是你觉得大 超级电脑不同DER
作者: jodojeda (jodojeda)   2021-04-13 00:14:00
LP
作者: TheBeast (边缘肥宅)   2021-04-13 00:18:00
brute force 2^n有最佳DP解法通常能优化成n^2更快的少部分能用数学解达到N或常数
作者: hsuan8871 (★_★)   2021-04-13 00:29:00
嗯嗯,大四上过从来就没有懂
作者: SHANGOYANYI (彦一)   2021-04-13 00:31:00
简单讲就是想探究世界上有没有金手指指令的存在
作者: mayolane (mayolaneisyagami)   2021-04-13 00:43:00
基本上多项式成长一定比指数慢啊
作者: aarzbrv (我爱钻石光! 芒! 长!~~)   2021-04-13 01:21:00
回mayolane:那也要NP等于EXP呀

Links booklink

Contact Us: admin [ a t ] ucptt.com