锐客网

  1. 首页 > 睿知 > >

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

生活知识睿知


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年的天敌吃到灭绝 。

推荐阅读


上一篇：赛马娘皇帝事件怎么选 赛马娘手游皇帝事件选项介绍

下一篇：褶皱怎么读 褶皱怎样读