作者wayne750213 (冰酿绿茶)
看板NTUE-CS98
标题[转录]Re: [新闻] 美德数学家 发现超大质数
时间Tue Sep 23 23:37:31 2008
※ [本文转录自 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
1F：推 syuemei:你人也很好 09/19 23:45
2F：→ ufoon: 屌 09/19 23:45
3F：推 kick:是某些乡民先在推文白烂的吧 09/19 23:46
4F：→ invigorator:反方答辩了 09/19 23:46
5F：推 vibba:半桶水响叮当 09/19 23:46
6F：推 thomasjr:真专业 09/19 23:47
7F：→ lirnitex:量子力学也可以用在密码学吗? 09/19 23:48
8F：推 tsioge:专业不代表可以呛别人 你也重蹈附辙霸了~ 09/19 23:51
9F：推 sukeda:可以阿~ 09/19 23:51
10F：推 xhole:听说量子电脑可以一瞬间解出来 不知道有没有这方面的强者 09/19 23:51
11F：→ xhole:来讲解一下 09/19 23:51
12F：推 deju:小心原po抓狂想一个需要很大质数的加密演算法XXD 09/19 23:51
13F：→ sukeda:quantum entanglement 09/19 23:52
14F：推 realestate:专业推一个 09/19 23:52
15F：推 asynchronous:量子电脑可能还要很久 09/19 23:53
16F：推 jengjye:不就是变形金刚 XD 09/19 23:53
17F：推 JSD:推专业 可是知识不要拿来PK 我觉得比较好.... 09/19 23:53
18F：→ asynchronous:还要很久才会有实用版. 目前还是在努力的缩小晶圆中 09/19 23:53
19F：推 Wush978:push 09/19 23:56
20F：推 TroyLee:要开战搂.... 09/19 23:56
21F：→ keepoo: π字派的上啊！！！ 09/19 23:57
22F：推 librabook:这篇有呛人吗?? 感觉不出来阿 是不懂的人内心受创吧 09/19 23:58
23F：→ librabook:话说被懂的人呛还比倍半调子的人唬还爽一点点 09/19 23:58
24F：推 kolodona:被真正不懂得人呛也很可怜 09/20 00:00
25F：推 smi1e:上篇根本就虎烂＋欠呛XD 09/20 00:00
26F：推 styleppt:嗯嗯 第3段的第4行解释的不错 09/20 00:00
27F：推 startlequiet:本串第一篇的syu外行斗内行 把一堆专业都引出来了.. 09/20 00:01
28F：推 realestate:所以syu唯一的贡献 就是让我们看了很多篇专业文罗? 09/20 00:02
29F：推 syuemei:贡献喔 就是让你们知道这麽大的数没有什麽实际用途 09/20 00:04
30F：→ syuemei:刚好跟我一开始的说法一样 很巧 09/20 00:04
31F：推 yayaoh:看不懂啦＝ ＝ 09/20 00:05
32F：→ syuemei:说不定真的有人用到它 然後又被翻盘也说不定 09/20 00:05
33F：推 coronach:其实举RSA也只是要告诉无知的人大质数是有用的吧 09/20 00:07
34F：→ coronach:所以就说不定真的有一天有人会用到..... 09/20 00:08
35F：→ neverfly:能不能拜读一下世界上实作最快质因数分解的paper呢？ 09/20 00:09
36F：推 ILoveRiva:推中研院的前同仁 XD 09/20 00:11
37F：推 coronach:楼楼上+1 刚好这学期要修密码学... 09/20 00:12
38F：推 smi1e:呃，用多大的质数是速度问题，你总不想加密个字串 09/20 00:13
39F：→ coronach:author name or keyword来一下...XD 09/20 00:13
40F：→ smi1e:就要让自己的电脑跑上五天吧?^^" 09/20 00:13
41F：推 flamesky:问一下M-R算法依赖黎曼猜想，是因为用了质数定理和质数 09/20 00:14
42F：→ flamesky:布之间的的近似程度的原因麽 09/20 00:15
43F：→ Freak1033:paper 现在应该还搜不到, 因为 eurocrypt 还在审. 09/20 00:15
44F：→ Freak1033:不过我们有在 CHES 的时候先做了一份投影片, 09/20 00:15
45F：推 cyp001:喔~~~(假装看懂了!) 09/20 00:16
47F：→ Freak1033:其实是没什麽新方法,只是把旧方法跟硬体推到极限而已.:p 09/20 00:17
48F：→ flamesky:不过我好像看不懂,呵呵，好像使用椭圆曲线在某个特定域 09/20 00:20
49F：推 alamabarry:其实~~你不打算让然看懂的吧@@ 09/20 00:20
50F：→ flamesky:上算的麽，搞不清了，果然隔行如隔山啊 09/20 00:21
没错, 就是用椭圆曲线法来处理跑 1024-bits GNFS 之後生出来的那些"小"合数.
它们的范围大约就是在 256-bits 上下.
我们这篇 paper 的主要价值在於使用 GPU 来计算,
我们都知道近代 GPU 的算术能力已经远超过 CPU. :p
51F：→ alamabarry:个人认为这个理论在压电偶合与阻抗匹配有极大的功用 09/20 00:22
52F：→ flamesky:不过你原文的结论我觉得很对，那个质数没啥用，太太大了 09/20 00:23
53F：推 coronach:........看到郑老师的名字 不会是本人吧 (抖) 09/20 00:23
54F：→ Freak1033:not me, I'm Chen. :p 09/20 00:23
55F：→ coronach:所以是用CUDA做的罗 这学期郑老师开CUDA的课 我没选 XD 09/20 00:25
※ 编辑: Freak1033 来自: 140.109.224.64 (09/20 00:26)
56F：→ Freak1033:没错, 的确是 CUDA. :) 09/20 00:27
57F：推 YukiPhoenix:打仗输入密码要一小时解密 09/20 00:41
58F：→ YukiPhoenix:仗都打完了... 09/20 00:41
59F：推 ILoveRiva:用GPU算...敢问是采用Nvidia还是ati ....?XD 09/20 00:43
60F：推 medama:推すてプリ 09/20 00:44
61F：→ flamesky:近代GPU算术能力远超CPU？(惊） 09/20 00:46
62F：推 tantu:都说是CUDA了就是Nvdia了阿~Nvidia好棒阿! 09/20 00:54
63F：推 superbabaya:他指的是3d浮点运算能力吧.... 09/20 00:54
64F：推 tantu:GPU的优势在於平行运算 09/20 00:58
65F：推 yellowbooky:高手 能投稿到crypto 能说说是哪个实验室吗xd 09/20 00:59
66F：→ Faberge:我推有人会这样呛你: 09/20 01:00
67F：→ Faberge:你几点要meeting?把schedule先拿出来 (中文夹英文) 09/20 01:01
68F：推 tantu:其实就是在等待此篇好文才没推第一po,我的疑惑解了! 09/20 01:02
69F：→ tyf99:我从来不敢断言有什麽新发现是没用的（除了太阳能手电筒） 09/20 01:24
70F：→ tyf99:费马小定理当初发表时，全世界有谁料到这将来会被用在RSA上 09/20 01:26
71F：推 lamontlui:嗯嗯 （装懂中） 09/20 01:47
72F：推 ethanjava: 呵呵 是杨X因老师的实验室吗? 09/20 02:30
73F：→ ethanjava: 跟 bernstein, lange, yang一起发论文 真爽 09/20 02:38
74F：推 eggbird:完全看不懂... 09/20 02:52
75F：推 Conpana:原po的态度明明就很婉转很客气，说他呛也太过分了点 09/20 02:53
76F：推 cguava:可是如果将来电脑发展到跑RSA-43112609只需要0.1sec ..... 09/20 03:38
77F：推 ETTom:推专业，虽然看不懂XD 09/20 03:38
78F：→ cguava:那大质数还是没有用吗?... 09/20 03:38
79F：推 EightSir:推 09/20 03:42
80F：推 kido183:靠盃 说实在的看不懂 但是给推XD 09/20 05:30
81F：推 davidr:推你 真屌 09/20 09:39
82F：推 jlsdob:文组哭哭 完全看不懂 09/20 09:53
83F：→ final01:我记得高司 费码之类的人兴趣就是找质数 09/20 10:37
84F：推 nosod:看不懂啦....哭哭 09/20 10:49
85F：推 Yulicha:完全看不懂 09/20 12:34
86F：推 abc0:没有足够大的量子电脑,那够强的GPU那麽多单元可以混过去吗? 09/20 12:43
87F：推 Yie: 09/20 13:43
88F：推 crazysinger:看不懂啦 哭哭 09/20 14:18
89F：推 nanahiei:这串讨论文真的说的是中文吗?我竟然有看没有懂,我是笨蛋 09/20 16:15
90F：推 jgnh:来自中研院的文 科科 09/20 16:20
91F：推 tomin:比之前的好几篇容易懂 09/20 16:23
※ 编辑: Freak1033 来自: 140.109.224.64 (09/20 21:24)
92F：推 finkel:请问一下是哪一所大学有开课??有课程网页吗 09/20 21:44
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 118.168.3.179
93F：推 dreamwing11:你们两个干麻?? 让人家以为我们都看的懂吗?? 09/24 00:00
94F：推 aeolus1215:弓三小... 09/24 00:01