@ 2018.01.07 , 16:30
31

我们刷新了已知最大素数的记录

我们刷新了已知最大素数的记录
credit: 锐景创意

所谓梅森数,是指形如2^P-1的一类数,其中指数p是素数,常记为MP。如果梅森数是一个素数,就称为梅森Mersenne素数。

我们最新找到的最大素数,就是第50个梅森素数,M77232917。也就是2×2×……×2,一共自乘了77232917次之后,再减去1。

由于这种构成方式,使得它比之前发现的最大的素数(也是梅森素数)多出近一百万位数。所以我们就不在这里写下具体的数值了。

随着数字越来越大,素数(一个只能被1和它自身整除的自然数)也越来越难以被发现。两个素数之间的距离越来越远,目前还不存在素数的有效递推公式,所以也不存在一套专门的高效算法。

即使是寻找梅森素数的公式——以17世纪的法国修道士马林·梅森(Marin Mersenne)的名字命名,也不是一种精确的方法,它只是帮助我们缩小缩小范围,方便进一步枚举而已。

因此,在使用公式2^P-1带入不同的素数p得到一个梅森数之后,我们必须经历艰苦的素性检验过程。试着用它全部可能的因子来整除这个梅森数。对于很大的数字p,这种运算需要极其漫长的一段时间。

作为伟大的互联网协作搜索梅森素数计划(GIMPS)的一部分,来自田纳西州51岁的电气工程师志愿者Jonathan Pace在他的电脑上运行了一款专门搜索并检验素数软件。他已经狩猎了14年的素数,这一次他终于得偿所愿。

这一数值本身是在2017年12月26日被发现的。检验又花费了六天的功夫,进行不间断的计算。接下来,又在四种不同的硬件配置上,运行了四个不同的程序来进一步确认。

之前的记录是2016年1月发现的M74207281,比M77232917少910807位。

如果我们要将目前最大的素数打印到4A纸上,将需要高达9000页。

好吧,科学家为什么要寻找素数? 用来加密。

两个大数字相乘得到一个更大数字的过程,具有某种不对称性。比如说,555777159*337这一运算是简单的,但是反过来让你验证187296902583是那些哪些数字相乘的结果就困难得多。借助这一特性,我们找到2个足够大的素数作为双方的私有密钥,用它们的乘积作为公开密钥。而其他人就算看到了公开密钥,要想分解出两个私有密钥,将是十分漫长的过程。这种时间优势,就保证了密码的可靠性。

足够多的具体素数也可能帮助我们找到素数的模式,如果它们确实有一个的话。

但是对于业余以及专业数学家来说,那些大素数会带来意外的财富——GIMPS为每次刷新记录者提供了奖金。

Pace将会获得3000美元的奖金——更遑论在数学史上留下自己姓名的机会。说不定他的记录会占据GIMPS榜首很久。

本文译自 sciencealert,由译者 majer 基于创作共用协议(BY-NC)发布。


给这篇稿打赏,让译者更有动力
支付宝打赏 [x]
您的大名: 打赏金额:

4.3
赞一个 (11)

TOTAL COMMENTS: 31+1

  1. 3666828

    第51个梅森素数和第50个梅森素数相乘。。。估计核弹密码也没这么多位数吧?

  2. 食品级怪蜀黍
    @1 week ago
    3666831

    “遑论”不是谈不上的意思么

  3. 3666834

    “比如说,555,777,159*337这一运算是简单的,但是反过来让你验证187,296,902,583是那些数字相乘的结果就困难得多。”
    这段话很捉急啊。
    第一,这个算出来答案是多少的难度不低于验证后面那个数是不是答案的难度。因为你只要算出来了答案,那么把答案和后面那个数字对比一下就知道对不对了,这部带来额外的难度。反而是(如果后面那个数字是错的)有可能可以通过一些快速排除法证否(比如余数判定之类的)。
    第二,你想说的计算 A*B=C 和反过来找出 C 的因素分解为 A*B 的难度是不对等的,分解的难度远高于计算。但这里有个前提是A和B都是素数才有意义。而你举得这个例子,555,777,159能被3整除。所以如果你让我分解187,296,902,583,我会告诉你等于3*62,432,300,861,也很快……

  4. 3666836

    @xiu: 核弹密码是8个0

  5. 莱因哈特
    @1 week ago
    3666838

    @xiu: 密码为啥要用数字?不能混用?

  6. Spector
    @1 week ago
    3666845

    比起挖矿来收入怎么样?

  7. 3666847

    @莱因哈特: 字母符号本质上也是数字

  8. 3666851

    @abc: 第一,译文应该是“是哪些数字相乘的结果”,错别字啊oioi。
    第二,语境是A有私钥a,B有私钥b,相乘结果ab作为公钥拿来通信加密,这个ab如果被你D拿走了,你一定要分解成a和b才能去破解通信过程,而不是随便一个分解结果就行。
    综上,你的“捉急”我不认同。

  9. 3666863

    Jonathan Pace是运行了专门软件,不是开发了这个软件……

  10. 煤炭孙
    @1 week ago
    3666866

    何必解释

  11. 煤炭孙
    @1 week ago
    3666867

    @kay: 何必解释呢

  12. 3666932

    为啥要用素数作为秘钥呢?求解释

  13. 3666950

    @23: 因为素数相乘很简单,分解质因数很难。
    对应就是:加密很快,破译很难。

  14. 3666952

    貌似如果那个日本中二数学家的工作,是和这个有点关系的?

  15. o啊熊o
    @1 week ago
    3666977

    看蛋友的回复 我觉得我是文盲

  16. 云中君
    @1 week ago
    3666995

    密码学渣已经把rsa忘光了,离散对数问题或成最大输家。

  17. 小客
    @1 week ago
    3667004

    @abc: 这不是就比特币矿场的工作

  18. 作大死
    @1 week ago
    3667011

    @kay: 素数目前是有限的相应的素数组合目前也是有限的。我要是破解的话先把素数间相乘的有限结果进行比对可以吗?

  19. 庆丰五年
    @1 week ago
    3667022

    这是第50位,不是51

  20. gooooow
    @1 week ago
    3667240

    @xiu: 说的是密钥,不是密码。两者不是同一种东西

  21. 3667336

    @abc: 文中的例子举错了,555,777,159不是素数是合数,但这并不影响本文的结论。

    举例来说,8632033这个数是由两个数字相乘得到的,你能看出是哪两个数字吗?你不妨用计算器,看看多久能算出来。这还仅仅是两个四位素数的乘积,而现在的加密算法用的是2048位素数,以保证即使超级计算机也无法在合理的时间(比方说一个世纪)里算出来。

  22. 3667338

    @作大死: 当然可以,利用目前最快的超级计算机,也许在太阳毁灭之前能找出来。

  23. 俱舍莲帝
    @1 week ago
    3667351

    @作大死: 应该接触一下编程,里边有个时间复杂度的概念。

    大概就是,学会以后,和昨天的自己一比,发现很多天才般的想法不具有意义。以后就可以不要想太多,人生真是变美好了呢。

  24. 3667354

    @作大死: 没这么多地方存。1TB是2^40。你算算2^1024得多少TB吧

  25. 3667373

    @abc: 第二个你可以wiki 迪菲-赫尔曼密钥交换 看完这个你就能明白了

  26. telepathy
    @1 week ago
    3667392

    “随着数字越来越大,素数(一个只能被1和它自身整除的自然数)也越来越难以被发现。两个素数之间的距离越来越远…”这个说法是不正确的,素数的分布并非越大越稀疏,某些事实上黎曼猜想对素数分布做过预言,也有一些统计表明N个自然数中有k个素数的情况下,当N很大时,N增加一倍,k也近似增加一倍~

  27. 3667535

    @abc: 额。。你知道啥叫密钥不?。。你解密出来和原文完全不同那还解个毛。。

  28. lavaskeleton
    @1 week ago
    3667729

    @telepathy: 张益唐不是已经证明距离有限么?

  29. 3667796

    第一句表述不严谨。梅森数就只是 2^P -1 这样的数而已。「当」其指数 P 为素数时,记为 Mp,且不一定皆为素数。相对的还有 P 不为素数的情况,当 P 为合数,则 Mp 一定为合数。

  30. 3667923

    @lavaskeleton: 张证明的只是存在无限多有限距离的素数,总体而言还是在不断增大的。例如对任意n,n!-n到n!+n就全是合数。另外华罗庚证明了素数数量与大小之间近似成对数关系。

  31. 3668354

    @????: @Rune: @Pstnk:
    1. 我是计算机专业的,所以我完全明白其中的概念。
    2. 我说的针对的是这段文字和这个例子本身,而不是“写这段文字的人”“原本”想要用它传递的概念。
    3. 我猜你们都没点过去看原文,这段话原文里是没有的。

发表评论


24H最赞