锐客网

  1. 首页 > 睿知 > >

你知道怎么样才能找到一个素数吗？ 什么是素数

生活知识睿知

什么是质数(你知道怎么求质数吗？)
素数
会上瘾的 。
关于质数的轶事
2017年12月26日，数学界发生了一件大事 。美国普通电气工程师乔纳森·佩斯(Jonathan Pace)在担任GIMPS志愿者的第14年发现了第50个梅森素数，即277232917-1 。这是迄今为止人类发现的最大的素数，共有23249425位数 。
然后，2018年初，又发生了一件相关的轶事 。
第50个梅森素数诞生两周后，日本红颜色学会紧急发布了一本名为《2017年最大素数》(简称《2017年最大素数》)的书，厚约32mm，共719页 。整本书只印了一个数字，第50个梅森素数 。
数学书从来没有这么受欢迎过 。然而，这本书出版两周之后，迅速攀升至日本亚马逊数学类畅销书第一名，并卖断货 。出版社被迫紧急印刷以满足市场需求 。
如果你对2000多万位数没有概念，你应该知道这本书的厚度 。
出版社的山口先生和一夫先生在接受媒体采访时表示，印刷这样一本书并没有什么特殊的目的 。他也考虑过把圆周率印成一本书，但因为圆周率小数点后的位数是无限的，他只好作罢 。
然而，2017年底《梅森素数》的诞生，再次刺激了他将数字印刷成书的神经，促使他以最快的速度出版这本书 。这本书不仅实现了山口那津男先生的纯愿，而且这本书的销售过程一不小心还成了出版界的奇闻 。
《2017年最大质数》内页全是数字 。
对于读者来说，把这本书买回家的精神意义远大于现实意义 。自17世纪法国数学家马林·梅森以来，人们一直在寻找梅森素数 。找到第50个梅森素数是数学领域的重大发现，是人类发展的新里程碑 。把这个里程碑带回家，这本书更多的是一个信物，代表着人类自强不息、勇攀高峰的精神 。
什么是质数？
为什么一个梅森素数的诞生会引起如此大的轰动？我们先来了解一下什么是质数 。
在一个定义为大于1的质数的自然数中，除了1和它本身，没有其他因素 。
这个定义很好理解 。以小于10的自然数为例 。二、三、五和七是质数 。比如7只能分解成1乘以7，没有其他的分解方式 。对于其他数，比如8可以分解成2×4，所以8不可能是质数 。
和质数的原子一样，是其他数的基石 。自然数是无穷的，那么有多少个质数是基石？
这个问题在2300多年前就有答案了:素数有无穷多个 。古希腊数学家欧几里得在《几何原本》中给出了简洁优美的证明 。
虽然有无限个素数，但寻找和验证大素数并不容易，这就是素数的秘密 。难度有多大？
我们可以快速列出50以内的质数:
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47……
它们看起来很密集，但随着质数变大，它们之间的距离也变长了 。重要的是，它们的分布距离是不相等的 。寻找一个大素数，往往需要巨大的计算量，分解验证也是如此 。为了掌握素数定律，数学家们绞尽脑汁 。
其中，有两个关于素数的著名猜想:
孪生素数猜想:差为2的素数对有无限多组 。
哥德巴赫猜想:所有偶数都可以表示为两个素数之和 。
这两个猜想在数学史上非常有名 。几千年来，许多数学家都梦想用自己的双手解决难题 。好在最近100年，这两个猜想都有了很大的突破 。
其中，中国数学家张在2012年成功证明了孪生素数有无数对，每对中两个素数之差不超过7000万 。虽然孪生素数的猜想只有把7000万化为2才能最终证明，但他在孪生素数之间的距离由无限变为有限上取得了突破 。
张取得这一突破后，许多学者试图用他的方法来缩小差距，进一步缩小了距离孪生素数猜想最终解的距离 。2014年2月，7000万人减少到246人 。
另一方面，中国数学家陈景润在1966年成功证明了“1+2”成立，距离哥德巴赫猜想“1+1”成立仅一步之遥 。
这里我们引入一个概念叫做几乎质数，它是一个素数因子很少的正整数 。
假设N是偶数，虽然目前无法证明N是两个素数之和，但足以证明可以写成两个几乎素数之和，即N=A+B，其中A和B的素数个数不太多，例如素数个数不超过10 。
我们可以用“a+b”来表达如下命题:每一个大偶数n都可以表示为A+B，其中A和B的素因子个数分别不超过A和B 。显然，哥德巴赫猜想可以写成“1+1” 。
这方面的进展是通过所谓的筛选方法实现的 。自1920年挪威数学家布伦证明“9+9”以来，这一公式不断被各大数学家简化，1966年中国数学家陈景润证明了“1+2” 。
3素数搜索计划-GIMPS
在素数中，有一类特殊的素数，如2p-1，在17世纪被法国数学家马林·梅森内深入研究 。为了纪念梅森的贡献，学术界称这个数字为梅森数 。如果梅森数是一个素数，称为梅森素数 。
在手工计算的时代，人们开始搜索梅森素数 。直到19世纪末，只发现了12个梅森素数 。p的值是:2，3，5，7，13，17，19，31，61，89，107，127 。
计算机诞生后，人们搜索梅森素数的速度更快了 。直到1996年，数学家使用超级计算机Cray-T94，发现了第34个梅森素数 。
进入互联网时代，一种更微妙的方法诞生了 。1996年1月，美国数学家和程序员乔治·沃特曼编写了一个梅森素数计算程序 。他把程序放在网页上，供数学家和数学爱好者免费使用，这就是最初伟大的互联网梅森素数搜索(GIMPS) 。任何拥有个人电脑的人都可以加入GIMPS，成为一名质数猎人 。自1997年以来，所有新的梅森素数都是通过GIMPS分布式计算项目发现的 。这个项目成功聚集了几十万台计算机来计算一个问题，其计算能力已经远远超出了我们的想象 。
其中，最新发现第50个梅森素数的是美国普通电气工程师乔纳森·佩斯(Jonathan Pace)，他使用了一台CPU型号为i5-6600的普通家用电脑 。幸运的是，他通过GIMPS发现了这个梅森素数，不仅在数学史上留下了自己的名字，还获得了3000美元的奖励 。(有兴趣可以下载一个试试 。第一个找到超过1亿位数的梅森素数的人将获得15万美元的奖励 。)
4素数搜索算法
质数的去向是不确定的，它们的分布也是未知的 。怎样才能找到质数？
公元前2世纪，希腊数学家厄拉多塞就已经提出了一种非常简单有效的素数筛选方法，我们称之为厄拉多塞筛 。核心是:要得到自然数n以内的所有素数，必须消去所有素数不大于根号n的倍数，剩下的都是素数 。
具体筛选方法如下:
第一步:确定要筛选的素数的范围，确定范围的最大值，比如120 。
第二步:根号120的结果是10.95，所以你只需要用11以内所有素数的倍数来消去120以内的数，剩下的都是素数 。先剔除11以内的2、4、6、8、10的倍数的数，以及120以内的所有2的倍数的数 。
第三步:没有被消除的最小数是3 。剔除3的倍数的数字，剔除11以内的9的倍数的数字，剔除120以内的所有3的倍数的数字 。
第四步:没有消除的最小数是5 。消除5的倍数 。11以内不需要消去任何数，120以内所有是5的倍数的数同时消去 。
……
以此类推，120以内的质数都可以完全找到 。
厄拉多塞筛法的一个例子
素数5有什么用？
为什么科学家如此热衷于寻找质数？一方面是对自己理想的追求，孜孜不倦地攀登数学高峰 。另一方面，素数在实际场景中有很大的价值 。
1.计算机字段
质数计算机领域的应用无非就是信息的加密，包括著名的RSA算法(小智之前写过RSA算法的介绍，点击入口) 。目前，由于大整数的因式分解，很难找到它的素因子 。目前除了暴力破解，还没有找到其他有效的方法 。也就是说，只要密钥长度足够长，就需要很长时间才能找到素数因子，RSA加密的信息实际上是无法破解的 。因此，素数在密码学中起着重要的作用 。
只有你有了密钥(私钥)，你才能解开信息 。
2.工业领域
在汽车变速箱齿轮的设计中，可以将相邻两个大小齿轮的齿数设计为质数，以增加两个齿轮中两个相同齿啮合次数的最小公倍数，可以增强齿轮的耐久性，减少故障 。
汽车顺序变速箱详图
3.生物领域
北美的周期性蝉(magic蝉)有着奇特的生命周期 。它们需要很长时间，每13或17年，才能成群结队地破土而出 。
自17世纪中叶以来，科学家们一直对周期性蝉的生命周期感到困惑 。它们遵循相同的基本生命周期:幼虫在地下生活13或17年，然后在夏季大量出现 。它们爬树，蜕皮，长成成虫，然后在短短几周内，成虫相遇，交配，产卵 。孵化后，幼虫将返回地面，等待下一次轮回 。
为什么这个数恰好是质数时，是13年或17年，而不是其他数？
当这些周期性的蝉被大量出土繁殖后，它们的天敌就会吃得很多，它们就会有更多的营养用于繁殖，所以天敌的数量就会大大增加 。假设天敌只能性成熟6年，其后代6年后才性成熟繁殖 。因为没有周期性的蝉吃，所以数量一直在下降 。假设周期性蝉的周期是18年，那么第18年天敌会继续吃啊吃，在这个18年的周期里会产生更多的天敌，这样每18年，天敌的总数就不断上升，周期性蝉的数量就越来越少 。同样，周期为16年的蝉很可能被周期为2年、4年或8年的天敌吃到灭绝 。
而13年的蝉和17年的蝉正好避开了这些可能，因为13和17是质数，除非天敌年年繁殖，或者只是13、17年，否则无法帮助天敌繁殖 。因为13年的蝉和17年的蝉选择了质数的生命周期，帮助天敌繁衍的几率大大降低，得以存活至今 。
篱笆上密密麻麻周期性的蝉鸣
数学美无处不在 。就素数的特性而言，一方面，人类已经将素数分布的特性应用到计算机的加密算法中；另一方面，自然界按照既定规律自然运行，但也产生了质数期的特征 。令人惊奇的是，有黄金期的生物适应性最强 。这让人联想到包含斐波那契数列的松果，以及具有分形结构的山川(门户) 。这与其说是大自然的神奇，不如说是数学规律的幕后策划者的结果 。
【你知道怎么样才能找到一个素数吗？ 什么是素数】松果顺时针8，逆时针13，是斐波那契数列中的数字 。

    推荐阅读


    上一篇：它就像这个时代的 NOKIA 808 808 pureview

    下一篇：钢铁是怎样炼成的读书笔记600字 钢铁是怎样炼成的读书笔记