PTT推薦

Re: [爆卦] 德國密碼學家宣稱自己摧毀了RSA加密法

rafe 發表於 2021/4/13 上午12:08:26
看板Gossiping標題Re: [爆卦] 德國密碼學家宣稱自己摧毀了RSA加密法作者
rafe
 (Out of the hole)時間推噓13 推:13 噓:0 →:8

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

--

※ PTT 留言評論
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.233.149.50 (臺灣)
※ 文章網址: https://www.ptt.cc/Gossiping/M.1618243708.A.8F4
推

johnhmj04/13 00:10先推，不然別人以為我看不懂

推

StylishTrade04/13 00:10所以多項式難度如果是n的100次方 你算的出來嗎 XDDD

→

StylishTrade04/13 00:11他只是把2的n次方 改成n的xx次方 xx可能很大阿

推

wei11504/13 00:13所以說是哲學問題啊，爽過之後還是要面對現實，不過很爽

→

wei11504/13 00:13就4惹

→

TheBeast04/13 00:14差多惹 那是你覺得大 超級電腦不同DER

→

jodojeda04/13 00:14LP

→

TheBeast04/13 00:18brute force 2^n有最佳DP解法通常能優化成n^2

→

TheBeast04/13 00:19更快的少部分能用數學解達到N或常數

推

hsuan887104/13 00:29嗯嗯，大四上過從來就沒有懂

推

SHANGOYANYI04/13 00:31簡單講就是想探究世界上有沒有金手指指令的存在
推

mayolane04/13 00:43基本上多項式成長一定比指數慢啊

推

aarzbrv04/13 01:21回mayolane：那也要NP等於EXP呀

推

Tenging04/13 05:43怕爆

推

orze0404/13 05:48等，如果質因數分解可以是P，那黎漫猜想怎麼辦

推

march2004/13 06:05常見錯誤, NP 不是 non-polynomial time, 是

→

march2004/13 06:05non-deterministic polynomial time

→

tt764204/13 07:48拜託說中文...乾，這是中文？？

推

ironkyoater04/13 09:17推

推

LYSLYS04/13 09:44推 march20

推

juju12304/13 20:21P與NP定義跟圖靈機有關 你的講法好理解但不正確
同系列文章
[爆卦] 德國密碼學家宣稱自己摧毀了RSA加密法
Gossiping最新熱門推薦
🔥🔥🔥