寻找质数的意义是什么? 除了密码学之外,是否还可能有我们现在所不知道的作用,就像大多数基础研究一样?

推荐  (1) | 12人关注关注
5个答案
44 2

方弦科学松鼠会成员,信息学硕士生

2013-11-10 01:48

在数论中有很多猜想需要解决。除了那些大佬级别的,比如说黎曼猜想ABC猜想之类,还有很多小猜想。而在一些这样的猜想中,某些特殊形态的素数就有着很大的作用。

举个例子。

对于给定的k,我们考虑集合,这是所有形如的数组成的集合。这一堆数之间,每个数是质数还是合数似乎没有太大的关系。但是,波兰数学家Sierpinski证明了,存在这样的k,使得这个集合内的元素都是合数。这样的k被称为Sierpinski数。

http://en.wikipedia.org/wiki/Sierpinski_number
http://en.wikipedia.org/wiki/Sierpinski_number

目前已知的最小的Sierpinski数是78557。但这并不代表不可能有更小的Sierpinski数。要证明一个数k不是Sierpinski数,只要找到某个n,使得是一个质数就可以了。实际上,目前对于以下的几个小于78557的k值,仍然没有找到对应的n,使得相应的数是质数:

k = 10223, 21181, 22699, 24737, 55459, 67607

所以,我们现在并不能肯定最小的Sierpinski数就是78557。而Sierpinski和Selfridge猜想,78557就是最小的Sierpinski数。但他们不能证明这一点,因为在当时,仍然有17个k值,没有找到对应的质数。但后来,一个叫Seventeen or Bust志愿计算项目 ,利用全世界志愿者的闲置计算资源,去寻找这17个k值对应的质数。经过数年的努力,终于将可能的k值个数从17降到6,也就是说找到了11个对应的质数,来推翻11个候选k值的可能性。这不得不说是一个进步。

你可能会说,那如果Sierpinski和Selfridge的猜想是错的,在那六个候选值中有Sierpinski数,那岂不是要一直算下去?

但其实Sierpinski和Selfridge的猜想也不是毫无根据的。从目前观察到的状态来看,所有已知的Sierpinski数都有这样的性质:存在一个有限的质数集合P,使得对应的集合中的每个数,至少有一个质因数在P中。对于k=78557,P={3, 5, 7, 13, 19, 37, 73},也就是说,每个形如的数,都至少被P中某个数整除。而这个集合P也是证明某个数是Sierpinski数的证据。

而对于目前的6个候选值,经过检验,似乎不存在这样的“小”集合P。所以,它们不大可能是Sierpinski数。当然,数论这种东西,这种猜测作不了准,但起码依据是有的。所以,数学家们也比较有信心,这个问题大概是迟早可以解决的,只是时间问题。而解决这个问题的唯一办法,就是去找对应的质数。

这个猜想的意义其实在于每个Sierpinski数对应一个有限P集合这个概念。这其实是非常令人惊讶的,因为如果任取一个相同密度的合数集合,这个集合对应的P集合没什么理由是有限的。而对于Sierpinski数存在有限的P集合,就说明这其中包含了一些我们仍然不太清楚的数论结构,是非常值得研究的。

这是一个猜想本身就必须找质数的例子,类似的还有寻找除了1093和3511以外的Wieferich prime(也就是满足的质数p,它与数学很多方面有联系,比如说扩张数域),我们猜想存在无穷个Wieferich prime,但是目前只找到上面说的2个。还有所谓的对偶Sierpinski数,就是把换成

下面举一个质数帮助解决猜想的例子。

某个整数n是完全数,当且仅当n的所有真因子的和正好是n。比如说6就是一个完全数。现在找到的所有完全数都是偶数(实际上欧拉证明了偶完全数必然由梅森素数给出)。数学家猜想,不存在奇数同时是完全数,这就是所谓的奇完全数猜想。为了排除很多候选者,数学家需要一些特殊形式的数的某些质因子,而寻找这些质因子可以帮助探索这个猜想。

费马数是所有形如的数。费马猜想对于所有的n,对应的费马数都是质数,但这个猜想可耻地失败了,因为除了n=0,1,2,3,4之外,对于其它的n,貌似没有质数。所以现在反而猜想除此之外的n对应的费马数都是合数。而这些费马数的质因数,很多都是形如的所谓Proth质数。所以,像PrimeGrid这样寻找各种各样质数(包括Proth质数)的志愿计算项目,就有助于证明一些费马数是合数。

所以,其实寻找特殊形式的质数是对数学研究有帮助的,就更别说这个问题对于算法的需求催生了多少数学研究和程序研究,比如说AKS算法和LLR测试,都是很有名的数学结果,而GIMPS(搜寻梅森质数)的软件Prime95,就更是科学计算程序优化的极致典范。而对于这些质数的搜索,也催生了世界上最大的全球志愿者计算项目之一,这是罕有的全球协作,数学家和爱好者都投身其中,为数学研究做出了巨大的贡献。

总结一下,寻找质数,不仅仅对数学研究有贡献,而且对于算法和软件设计,还有国际协作,都有帮助。

最后做个广告。关于这个东西,欢迎到相关的小组讨论:
数学午餐会
分布式计算

26 0

冰红茶回复老被吞☠

2013-11-11 04:27

这个问题问得非常好,看样子这位童鞋有学过怎样提升问答技巧^_^
理论上的意义方弦已经说得很详细了,数理最简单的表达方式就是公式,你可以这么认为数理最为质朴说明就是公式,而公式你又可看做是数理最为精髓的表达。
以傅里叶变化理论为例,傅立叶是一位法国数学家和物理学家,他在1807年在法国科学学会上发表了一篇论文,运用正弦曲线来描述温度分布,论文的核心是任何连续周期信号可以由一组适当的正弦曲线组合而成,用正弦曲线来非常逼近地表示它,逼近到两种表示方法不存在能量差别。
以当时的科学条件来看,这绝对是让人匪夷所思的一个理论,以至于该论文直到35年后才被公开发表,而真正大规模的应用也是现代了。
随着对这个理论不断的认识,后人也在此基础上发展了更多的用途,根据原信号的不同类型,可以把傅立叶变换分为四种类别:
1
非周期性连续信号
傅立叶变换(Fourier Transform)
2
周期性连续信号
傅立叶级数(Fourier Series)
3
非周期性离散信号
离散时域傅立叶变换(Discrete Time Fourier Transform)
4
周期性离散信号
离散傅立叶变换(Discrete Fourier Transform)
这四种类别分别在在物理学、声学、光学、结构动力学、量子力学、数论、组合数学、概率论、统计学、信号处理、密码学、海洋学、通讯、金融等领域都有着广泛的应用。
就楼主的疑问我个人观点是,寻找质数意义在于完善现有理论的同时说不定又能在此基础上成为解决其他问题的踏板。

14 0

寻找质数就好比追寻科学的根源一样,解决数的始祖问题。好吧,其实我想说,黎曼猜想是一般的质数分布问题,方弦说的“Sierpinski数”和“Wieferich prime“属于寻找某类质数问题,冰红茶说的傅立叶变换和质数其实关系不大(anyway,因为质数太基础了,如果一定要找关系的话是可以找到),叶迎风的回答则比较哲学一些。

好奇是科学研究的根源,我们总是喜欢打破沙锅问到底,复数可以看成是特殊的二维实数,实数可用看成是有理数的逼近,有理数可以看成整数相除,整数可以进行素因子分解,那么作为目前最根本的素数又可以由什么组成呢?上帝创造素数之前还创造了什么?

不明白真相的群众可以考虑这样的问题,“如果A由B组成,那么B又由什么组成呢?“,“如果B由C组成,那么C又由什么组成呢?“,无穷无尽地问下去,那么现在我们对数学的理解就卡在了素数上面。这个问题在物理上的最明显了,质量是指包含物质的多少,可物质又是由什么组成的?分子?原子?中子?夸克?还是什么呢?我想,这就是我们寻找质数的意义了。

12 0

基础研究必须走在实践的前面,这是人类对于完美的一种追求,谁也不知道那些看似无聊的游戏一样的理论,将来会在什么样的现实中大放异彩。例如当初的非欧几何理论,谁也不曾想到它会成为新的引力理论的基石。十进制已经被人们用得很习惯,如果谁用二进制来表示数字一定会被人认为是闲得蛋疼,直到计算机的发明。数论的很多结果已经在计算机密码学中扮演着重要的角色,但是在一个世纪以前,只有数学家会关心因数分解的问题。自然数是无穷集合中势最小的集合,它有很多重要的应用可能未被我们知晓,例如素数和黎曼猜想的关系,可能会为我们打开一扇通向新世界的大门。

查看更多

添加回答

登录 后回答问题,你也可以用以下帐号直接登录

相关问答

关于我们 加入果壳 媒体报道 帮助中心 果壳活动 家长监控 免责声明 联系我们 移动版 移动应用

©果壳网    京ICP证100430号    京网文[2018] 6282-492号    新出发京零字第朝200003号     京公网安备11010502007133号

违法和不良信息举报邮箱:jubao@guokr.com    举报电话:18612934101    网上有害信息举报专区    儿童色情信息举报专区