Re: [爆卦] 德國密碼學家宣稱自己摧毀了RSA加密法
※ 引述《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,就等於是證明了世上存在著某種真理一樣。
--
先推,不然別人以為我看不懂
所以多項式難度如果是n的100次方 你算的出來嗎 XDDD
他只是把2的n次方 改成n的xx次方 xx可能很大阿
所以說是哲學問題啊,爽過之後還是要面對現實,不過很爽
就4惹
差多惹 那是你覺得大 超級電腦不同DER
LP
brute force 2^n有最佳DP解法通常能優化成n^2
更快的少部分能用數學解達到N或常數
嗯嗯,大四上過從來就沒有懂
簡單講就是想探究世界上有沒有金手指指令的存在
基本上多項式成長一定比指數慢啊
回mayolane:那也要NP等於EXP呀
怕爆
等,如果質因數分解可以是P,那黎漫猜想怎麼辦
常見錯誤, NP 不是 non-polynomial time, 是
non-deterministic polynomial time
拜託說中文...乾,這是中文??
推
推 march20
P與NP定義跟圖靈機有關 你的講法好理解但不正確
爆
首PoRSA加密法於1977年由Rivest、Shamir和Adleman提出,因為極大數的質因數分解困難度,此 方法成為世界上應用最廣泛的加密法。目前被破解的RSA密鑰最長紀錄是768個位元,因此 一般認為2048位元的密鑰非常安全可靠。 然而德國密碼學家Claus Peter Schnorr在自己新論文摘要中的最後一句宣稱:本文"摧毀"22
前面推文也有提到這件事 NP [1] 是指 non-deterministic polynomial time 並非 non-polynomial time 意思是能夠用非確定性圖靈機在多項式時間內解決的問題 現在常用的等價敘述是能夠在多項式時間內驗證是正確的問題 而 EXPTIME [2] 這個指的才是指數時間
爆
Re: [新聞] 京華城案約談8人都曾捐30萬 張益贍:民爆
[問卦] 驚!台灣的餐飲服務快崩潰了吧爆
[問卦] 侯佩岑現在長這樣?爆
[問卦] 驚!台灣大缺工!年輕人都去做什麼了爆
[問卦] 對岸酸菜魚店都倒一片 台灣能火多久?76
[問卦] 賴清德蘭香嗎?爆
[爆卦] 真主黨新領袖上位不到一天又被幹掉75
[問卦] 先進國家都在用核能,只有台灣政府在反?69
[問卦] 麻將到底是靠運氣還是技術60
[問卦] 超思案有發現1億4千萬神秘金流!???62
[問卦] 回到未來這部電影是有多厲害50
[問卦] 懷孕22周的預計單親媽媽你敢接?43
Re: [新聞] 準備打仗了?賴政府突要訓練40萬民兵 沈富雄提醒:會洋爆
[爆卦] 耶魯大學環境360:台灣科技業面臨能源危機45
[問卦] 這樣一盒生魚片要多少錢62
[問卦] 痛罵國軍將領 自己兒女躲在美國?爆
Re: [新聞] 京華城弊案朱亞虎坦承收賄!李文宗兩罪全不認 北院收押66
[問卦] 維基百科寫的96年台海飛彈危機真的有這麼誇張?39
[問卦] 掛假牌是不是可以爽停商場身障車位34
[問卦] 台灣餐飲業大缺工 誰要負責?31
[問卦] 大家覺得南部跟北部最大的差異在哪?32
[問卦] 請問社區出現烏龜找哪個單位31
[問卦] 找一部軍隊長官飆罵下屬的片30
[問卦] 台北三萬七軟體工程師要會什麼?25
[問卦] 台中要變國際一線城市了?30
[問卦] 生日蛋糕是Lady M是不是很頂?30
[問卦] 台灣若出 澤倫司機 腫麼辦?21
[問卦] 認真問 有人承認行賄 卻找不到收賄人 怎辦34
[問卦] 高雄啥時宣布停班停課?28
[問卦] 能夠力壓台中F1活動剩下什麼?