[轉錄]Re: [新聞] 美德數學家 發現超大質數

[wayne750213 (冰釀綠茶)]

※ [本文轉錄自 Gossiping 看板]

作者: Freak1033 (金が信念! XD) 看板: Gossiping
標題: Re: [新聞] 美德數學家  發現超大質數
時間: Fri Sep 19 23:44:53 2008

※ 引述《ainor (><)》之銘言：
: http://www.csie.nctu.edu.tw/~rjchen/BigPrime.files/show.htm
: <恕刪>
: -----------------------------------------------------------------------------
: 隨便找都有資料
: 有沒有某些鄉民，自己無知算了，還怕別人不知道的八卦
: 還有沒有人要問算那麼大的要幹嘛？

請問您非常有知嗎? 這麼大脾氣就說別人無知?
我不認為會用 google 就有資格數落別人了. XD

我就直說了吧, 我在實驗室的主要研究領域就是密碼學與因數分解,
我可以斷言這麼大的質數在密碼學(至少在 RSA 上)沒有任何的實用價值,
而一堆人在產生這麼大的質數, 目的只是對純數學之神秘的探索而已.

為什麼說這麼大的質數在 RSA 上沒有任何實用價值呢? 起碼有以下原因:

1. 在 RSA 上面需要用的質數除了要夠大以外,
   最重要的是要能夠兩個質數的乘積必須難以被它人分解.
   而主題中所提到的質數其實是一個梅森質數,
   它是一種具有特殊型狀的質數(二的冪次減一夠特別了吧?),
   因此存在的候選並不多(事實上現在也才發現了 40 個梅森質數),
   一下就會被猜中, 更糟的是它已經被公開出來了, 就等於沒有用了.
   要是哪個傻子跟我說他的 RSA key 有 5 MB 那我一定馬上笑出來. A_A

2. 在實用上我們不會用到 Lucas-Lehmer test 來驗證質數,
   就算我們要用大質數, 也只要用 Miller-Rabin test 就可以了.
   這兩種測試的差別在於, Lucas-Lehmer test 能夠產生出一組 certificate,
   藉由它你可以在很短的時間內驗證出該數 100% 是個質數.
   而 Miller-Rabin test 則沒辦法產生出這種 certificate,
   它是一種隨機演算法, 只能保證對於某個合數在隨機測試中,
   有起碼 3/4 的機率它會被抓包出來是合數, 但是它沒辦法完全證明某個數是質數.
   (note: 除非 generalized Riemann hypothesis 被證明為真)
   在實務上, 其實我們不太需要那麼 100% 的證明,
   我們只要多跑幾次 Miller-Rabin test, 而某個數沒有被抓包,
   我們就可以相信它 99.999999% 是個質數, 那就夠用了. :p
   所以我說原本新聞上所講的尋找質數多半只是對於數學神秘的探究,
   而並非作為實際加密應用目的. :p

3. 用太大的 key 除了會降低破密速度以外, 同時也會讓正常的加解密變慢,
   光是用 RSA-1024 來做加解密就得花上大約 0.1 sec 的時間,
   而我們知道, 加解密的時間"至少"與 key 的長度成正比,
   也就是說 RSA-43112609 起碼得花上一小時才能進行一次的加密. XD

   而用這麼大的質數是否能帶來額外的安全性呢?
   事實上是沒有, 目前地球上最快的因數分解實作剛好是我們的作品,
   前日才剛投稿到 Eurocrypt. 我們估計出來,
   目前實用上能夠破到最大的 RSA 大約是 RSA-768,
   而這需要價值三百萬美元的機器與半年的計算時間.
   以個人使用而言 RSA-1024 已經足夠安全,
   而政府機關則是推薦使用 RSA-4096. (中華民國行政院的 key 便是 4096)

4. RSA 現在已經快要走到盡頭了, 自從 GNFS 發明之後,
   為了達到足夠的安全性, 所採用的 key 必須越來越長,
   使得加解密時間也越來越久.

   現在密碼學界所注目的 PKI 已經漸漸轉移到 elliptic curve based system,
   以及 multivariate quadratic system. 其中又以後者特別讓大家興奮,
   因為一般的 MQ 問題已知是屬於 NP-hard 問題,
   假使能夠產生某種 MQ trapdoor 使得產生出來的 key space 是所有的 MQ instance,
   那麼除非能夠發現 P = NP 的演算法(which is believed not exist),
   不然 MQ 的系統可以認為是安全的.

   另外目前也尚未發現解 MQ 問題的量子演算法,
   而質因數分解目前已知可用量子電腦破解,
   只差技術上沒辦法造出足夠大的量子電腦.
---
感謝網友來信指正, 第三段的數據有修正.
--
「ふ…ふざけるな！そんあ短い咒文で、魔法を起動できるわけないだろうが！
  お前わマウゼルの神に逆らう氣なのか？！傲慢な～」

「失禮致しました、誠實に全力でお相手致します。
  第一戰術級‧軍用攻性魔法‧出よ、武雷神〈トール〉！」
                                                〈スクラップド‧プリンセス〉

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.109.224.64
推 syuemei:你人也很好
→ ufoon:                         屌
推 kick:是某些鄉民先在推文白爛的吧
→ invigorator:反方答辯了
推 vibba:半桶水響叮噹
推 thomasjr:真專業
→ lirnitex:量子力學也可以用在密碼學嗎?
推 tsioge:專業不代表可以嗆別人 你也重蹈附轍霸了~
推 sukeda:可以阿~
推 xhole:聽說量子電腦可以一瞬間解出來 不知道有沒有這方面的強者
→ xhole:來講解一下
推 deju:小心原po抓狂想一個需要很大質數的加密演算法XXD
→ sukeda:quantum entanglement
推 realestate:專業推一個
推 asynchronous:量子電腦可能還要很久
推 jengjye:不就是變形金剛 XD
推 JSD:推專業  可是知識不要拿來PK   我覺得比較好....
→ asynchronous:還要很久才會有實用版.  目前還是在努力的縮小晶圓中
推 Wush978:push
推 TroyLee:要開戰摟....
→ keepoo:　　　　　　　　　　π字派的上啊！！！
推 librabook:這篇有嗆人嗎??  感覺不出來阿  是不懂的人內心受創吧
→ librabook:話說被懂的人嗆還比倍半調子的人唬還爽一點點
推 kolodona:被真正不懂得人嗆也很可憐
推 smi1e:上篇根本就虎爛＋欠嗆XD
推 styleppt:嗯嗯  第3段的第4行解釋的不錯
推 startlequiet:本串第一篇的syu外行鬥內行 把一堆專業都引出來了..
推 realestate:所以syu唯一的貢獻  就是讓我們看了很多篇專業文囉?
推 syuemei:貢獻喔 就是讓你們知道這麼大的數沒有什麼實際用途
→ syuemei:剛好跟我一開始的說法一樣 很巧
推 yayaoh:看不懂啦＝ ＝
→ syuemei:說不定真的有人用到它 然後又被翻盤也說不定
推 coronach:其實舉RSA也只是要告訴無知的人大質數是有用的吧
→ coronach:所以就說不定真的有一天有人會用到.....
→ neverfly:能不能拜讀一下世界上實作最快質因數分解的paper呢？
推 ILoveRiva:推中研院的前同仁 XD
推 coronach:樓樓上+1 剛好這學期要修密碼學...
推 smi1e:呃，用多大的質數是速度問題，你總不想加密個字串
→ coronach:author name or keyword來一下...XD
→ smi1e:就要讓自己的電腦跑上五天吧?^^"
推 flamesky:問一下M-R算法依賴黎曼猜想，是因為用了質數定理和質數
→ flamesky:布之間的的近似程度的原因麼
→ Freak1033:paper 現在應該還搜不到, 因為 eurocrypt 還在審.
→ Freak1033:不過我們有在 CHES 的時候先做了一份投影片,
推 cyp001:喔~~~(假裝看懂了!)
→ Freak1033:可以拿來參考: http://0rz.tw/204Mh
→ Freak1033:其實是沒什麼新方法,只是把舊方法跟硬體推到極限而已.:p
→ flamesky:不過我好像看不懂,呵呵，好像使用橢圓曲線在某個特定域
推 alamabarry:其實~~你不打算讓然看懂的吧@@
→ flamesky:上算的麼，搞不清了，果然隔行如隔山啊
沒錯, 就是用橢圓曲線法來處理跑 1024-bits GNFS 之後生出來的那些"小"合數.
它們的範圍大約就是在 256-bits 上下.
我們這篇 paper 的主要價值在於使用 GPU 來計算,
我們都知道近代 GPU 的算術能力已經遠超過 CPU. :p

→ alamabarry:個人認為這個理論在壓電偶合與阻抗匹配有極大的功用
→ flamesky:不過你原文的結論我覺得很對，那個質數沒啥用，太太大了
推 coronach:........看到鄭老師的名字 不會是本人吧 (抖)
→ Freak1033:not me, I'm Chen. :p
→ coronach:所以是用CUDA做的囉 這學期鄭老師開CUDA的課 我沒選 XD
※ 編輯: Freak1033       來自: 140.109.224.64       (09/20 00:26)
→ Freak1033:沒錯, 的確是 CUDA. :)
推 YukiPhoenix:打仗輸入密碼要一小時解密
→ YukiPhoenix:仗都打完了...
推 ILoveRiva:用GPU算...敢問是採用Nvidia還是ati ....?XD
推 medama:推すてプリ
→ flamesky:近代GPU算術能力遠超CPU？(驚）
推 tantu:都說是CUDA了就是Nvdia了阿~Nvidia好棒阿!
推 superbabaya:他指的是3d浮點運算能力吧....
推 tantu:GPU的優勢在於平行運算
推 yellowbooky:高手 能投稿到crypto 能說說是哪個實驗室嗎xd
→ Faberge:我推有人會這樣嗆你:
→ Faberge:你幾點要meeting?把schedule先拿出來 (中文夾英文)
推 tantu:其實就是在等待此篇好文才沒推第一po,我的疑惑解了!
→ tyf99:我從來不敢斷言有什麼新發現是沒用的（除了太陽能手電筒）
→ tyf99:費馬小定理當初發表時，全世界有誰料到這將來會被用在RSA上
推 lamontlui:嗯嗯 （裝懂中）
推 ethanjava:     呵呵   是楊X因老師的實驗室嗎?
→ ethanjava: 跟 bernstein, lange, yang一起發論文  真爽
推 eggbird:完全看不懂...
推 Conpana:原po的態度明明就很婉轉很客氣，說他嗆也太過分了點
推 cguava:可是如果將來電腦發展到跑RSA-43112609只需要0.1sec .....
推 ETTom:推專業，雖然看不懂XD
→ cguava:那大質數還是沒有用嗎?...
推 EightSir:推
推 kido183:靠盃 說實在的看不懂 但是給推XD
推 davidr:推你  真屌
推 jlsdob:文組哭哭  完全看不懂
→ final01:我記得高司 費碼之類的人興趣就是找質數
推 nosod:看不懂啦....哭哭
推 Yulicha:完全看不懂
推 abc0:沒有足夠大的量子電腦,那夠強的GPU那麼多單元可以混過去嗎?
推 Yie:
推 crazysinger:看不懂啦 哭哭
推 nanahiei:這串討論文真的說的是中文嗎?我竟然有看沒有懂,我是笨蛋
推 jgnh:來自中研院的文   科科
推 tomin:比之前的好幾篇容易懂
※ 編輯: Freak1033       來自: 140.109.224.64       (09/20 21:24)
推 finkel:請問一下是哪一所大學有開課??有課程網頁嗎
--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 118.168.3.179
推 dreamwing11:你們兩個幹麻?? 讓人家以為我們都看的懂嗎??
推 aeolus1215:弓三小...