※ 引述《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,就等於是證明了世上存在著某種真理一樣。