【科技日报】素数界新任“带头大哥”来了 寻找最大素数可催生更可靠的芯片和加密技术

2016-01-25 科技日报 高博

【字体：大 中 小】

语音播报

　　最大的素数是多少？谁都念不出来，因为它有2233万多位，如果用普通字号将它打印出来长度将超过65公里。今年1月，美国数学家柯蒂斯·库柏公布了这个素数界的新任“带头大哥”。它没什么用，但寻找它却催生出更可靠的芯片和加密技术。

　　素数是什么？这是个初中数学知识：素数又称质数，只能被1和它本身整除，而数值越大成为素数的概率就越低。新发现的素数写成指数式子并不长：274207281-1。它也叫梅森素数。梅森是17世纪一位数学家，终身致力于研究“2p-1”形式的素数（p也是一个素数）。

　　数学家已经知道：在“2p-1”这类数字里更容易发现素数，寻找最大的梅森素数，基本等于寻找最大素数。数字越大，计算越难。1996年，有一位美国的数论爱好者和退休程序员，设立了GIMPS项目（“大互联网梅森素数搜索”的英文缩写），利用互联网上的空闲计算能力来找素数。共有100多万台计算机参与搜寻。

　　“寻找最大素数是一个游戏，没有实际用处。但寻找素数的努力，可以促进计算机科学。”数学家杨乐院士告诉科技日报记者，“因为计算这么大的数是否是素数，是很难的，所以要提出新的计算方法和技术。”

　　手算时代，人们只找到了12个梅森素数，而计算机则帮助找到了37个，其中有15个是GIMPS项目找到的。几十年来，爱好者们一直在创新算法，让计算机更快验证巨大的数字是否为素数。

　　“想知道‘天河二号’准确不准确，也可以让它验算刚被发现的这个梅森素数是不是素数。”杨乐说出了梅森大素数的一个用处。

　　“素数测试程序代码简短，能给出易于检查的答案：‘当该程序在一已知素数上运行时，经数十亿次计算，输出结果是TRUE。’”中科院数学所的高全泉研究员在一篇论文中写道，Intel公司在测试奔腾系列芯片时，就使用GIMPS的程序。另外一项有关素数的计算，还发现了奔腾芯片的一个著名“BUG”。1996年，美国克雷公司在测试超级计算机的运算速度时，还得到了一个新的梅森素数。

　　类似的原理，在研究分布式计算系统时，素数计算也是最合适的测试任务。

　　“大素数在加密算法中也有用。”杨乐说。目前广泛应用的一种加密算法原理是：一堆素数乘起来得到一个大数很容易，反过来把大数分解成一堆素数就很麻烦，尤其当涉及大素数时。

　　高全泉介绍说，1990年代初，苹果公司著名科学家理查德·克兰达尔在改进梅森素数的算法中，发现了一种加速办法。这种办法不但被GIMPS用于素数搜寻，还可用在其他计算中。而苹果公司拥有专利的克兰达尔发明的“快速椭圆加密系统”，就将梅森素数用于快速加密和解密信息。

　　（原载于《科技日报》 2016-01-25 01版）

　　最大的素数是多少？谁都念不出来，因为它有2233万多位，如果用普通字号将它打印出来长度将超过65公里。今年1月，美国数学家柯蒂斯·库柏公布了这个素数界的新任“带头大哥”。它没什么用，但寻找它却催生出更可靠的芯片和加密技术。
　　素数是什么？这是个初中数学知识：素数又称质数，只能被1和它本身整除，而数值越大成为素数的概率就越低。新发现的素数写成指数式子并不长：274207281-1。它也叫梅森素数。梅森是17世纪一位数学家，终身致力于研究“2p-1”形式的素数（p也是一个素数）。
　　数学家已经知道：在“2p-1”这类数字里更容易发现素数，寻找最大的梅森素数，基本等于寻找最大素数。数字越大，计算越难。1996年，有一位美国的数论爱好者和退休程序员，设立了GIMPS项目（“大互联网梅森素数搜索”的英文缩写），利用互联网上的空闲计算能力来找素数。共有100多万台计算机参与搜寻。
　　“寻找最大素数是一个游戏，没有实际用处。但寻找素数的努力，可以促进计算机科学。”数学家杨乐院士告诉科技日报记者，“因为计算这么大的数是否是素数，是很难的，所以要提出新的计算方法和技术。”
　　手算时代，人们只找到了12个梅森素数，而计算机则帮助找到了37个，其中有15个是GIMPS项目找到的。几十年来，爱好者们一直在创新算法，让计算机更快验证巨大的数字是否为素数。
　　“想知道‘天河二号’准确不准确，也可以让它验算刚被发现的这个梅森素数是不是素数。”杨乐说出了梅森大素数的一个用处。
　　“素数测试程序代码简短，能给出易于检查的答案：‘当该程序在一已知素数上运行时，经数十亿次计算，输出结果是TRUE。’”中科院数学所的高全泉研究员在一篇论文中写道，Intel公司在测试奔腾系列芯片时，就使用GIMPS的程序。另外一项有关素数的计算，还发现了奔腾芯片的一个著名“BUG”。1996年，美国克雷公司在测试超级计算机的运算速度时，还得到了一个新的梅森素数。
　　类似的原理，在研究分布式计算系统时，素数计算也是最合适的测试任务。
　　“大素数在加密算法中也有用。”杨乐说。目前广泛应用的一种加密算法原理是：一堆素数乘起来得到一个大数很容易，反过来把大数分解成一堆素数就很麻烦，尤其当涉及大素数时。
　　高全泉介绍说，1990年代初，苹果公司著名科学家理查德·克兰达尔在改进梅森素数的算法中，发现了一种加速办法。这种办法不但被GIMPS用于素数搜寻，还可用在其他计算中。而苹果公司拥有专利的克兰达尔发明的“快速椭圆加密系统”，就将梅森素数用于快速加密和解密信息。
　　（原载于《科技日报》 2016-01-25 01版）

更多分享

扫一扫在手机打开当前页