Math►数论►素数

素数

简介

质数（Prime number），又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。大于1的自然数若不是素数，则称之为合数（也称为合成数）。

算术基本定理确立了素数于数论里的核心地位：任何大于1的整数均可被表示成一串唯一素数之乘积。

素数的个数

古希腊数学家欧几里得于公元前300年前后证明有无限多个素数存在（欧几里得定理）。

不存在最大质数!

已知最大的质数

找素数

即划掉不是素数的，剩下的就是素数。

梅森素数

早在2500年前，希腊数学家欧几里德就证明了素数是无限的，并提出少量素数可写成“2的n次方减1(2^n－1)”的形式，这里n也是一个素数。但是目前人类已知的素数很有限，因为数字越大，要发现新的素数就越困难。不过，很多数学家曾对素数问题进行过研究，17世纪的法国教士马丁·梅森就是其中成果较为卓著的一位，因此后人将“2的n次方减1(2^n－1)”形式的素数称为梅森素数。随后，以梅森素数的形式，最大素数的记录被不断刷新。

GIMPS计划

1995 年，美国程序设计师乔治·沃特曼整理有关梅森素数的资料，编制了一个梅森素数计算程序，并将其放置在因特网上供数学爱好者使用，这就是分布式计算因特网梅森素数大搜索（GIMPS）项目。目前有6万多名志愿者、超过20万台计算机参与这项计划。该计划采取分布式计算方式，利用大量普通计算机的闲置时间，获得相当于超级计算机的运算能力，第 37、38 和 39 个梅森素数都是用这种方法找到的。美国一家基金会还专门设立了 10 万美元的奖金，鼓励第一个找到超过千万位素数的人。

专门搜寻巨大质数的GIMPS计划再发现长达千万个位的质数，为甚麽会有些人对寻找大质数如此有兴趣？

2016, Dr. Curtis Cooper发现了第49个梅森素数和已知最大的素数：$2^74,207,281-1, 共有22,338,618位.

2017年12月26日，互联网梅森素数大搜索（GIMPS）项目宣布发现第 50 个梅森素数和已知最大的素数：2^77,232,917-1，共有 23,249,425 位。该素数已被多人使用不同的硬件和软件完成验证。发现者是 GIMPS 志愿者 Jonathan Pace，他住在田纳西州的 Germantown，是一位电机工程师，他有资格获得 3000 美元的研究发现奖。GIMPS 是一个分布式计算项目，至今已有 20 年历史，它利用志愿者的空闲 CPU 创建了一个遍布全球的超级计算机，它的 prime95 软件此前发现了英特尔处理器的一个漏洞。

大家利用梅森素数刷新最大素数记录，是否验证了两个梅森素数之间的所有数？

Prime Number Checker

素数的分布

统计规律

  • 数学家们之前认为素数是随机分布的。比如某一个位是1的素数，那么它的下一个素数以1结尾和以3结尾、以7结尾、以9结尾的概率都应大致相等。

如果素数与素数之间没有相互作用，那么素数分布就应该是之前我们所想的那样。”桑德拉说，“但事实上，一些有趣的事发生了。”
发生了什么？原来桑德拉他们发现，尽管素数分别以这四个数字结尾的总几率大致相同，但它们出现的顺序却有所“偏好”。比如个位为7的素数，它后面更容易跟着一个个位为9、3或者1的素数，而不是个位也为7的素数。据《量子杂志》（Quanta Magazine）3月13日的报道，在前10亿个素数中，以9结尾的素数之后跟着以1结尾的素数的比例比跟着以9结尾的素数的比例高了65%。

当素数趋于无穷时，这样的“偏好”会慢慢消失，分布更趋向于随机。但不可否认的是，“偏好”还是存在的。更重要的是，这些素数对尾数的偏好还很不一致。比如在前1亿个素数中，有750万个以3结尾的素数之后紧跟的是以9结尾的素数，有600万个以3结尾的素数之后紧跟的是以1结尾的素数，而只有440万个以3结尾的素数之后紧跟的是以3结尾的素数。

乌岚螺旋

乌岚螺旋，又称素数螺旋，是一个简单的展示出素数的一定明显规律的结构，同时它也指出一些二次多项式有着大量生成素数（富素数）的特性。

乌岚是写下了一个正方形的数组来构造了这个螺旋数组，从1开始且开始按照这个螺旋规律：

他然后圈起了所有的素数（如下图）：

令他吃惊的是这堆圈起来的数字趋向于与对角线排成一行。在200×200的乌岚素数表当中（上图），其中对角线都是清晰可见且完成整一个表，而且水平线和垂直线都是有证明显著突出素数的样子。

  • 为什么喜欢这种画法？其他画法呢？
    -
  • 映射的思想
    • 一维空间不可分，于是映射到二维空间。即乌岚螺旋仅仅将数据映射到二维空间而已。找不到规律也很正常。too naive
    • 乌岚螺旋等价于哪种映射？
      -
    • 映射到更高维空间呢？

乌岚螺旋的变种

https://en.wikipedia.org/wiki/Ulam_spiral

空间变换

局限于数空间，是否存在某个空间(类似频域)，使得

整数 VS 实数

只有整数具有质数、合数性质吗？

小数呢？

机器学习

用学习的方法呢？

分类

input: value
output: boolean(是否是质数)

这样构造一个二分类器？

回归

聚类

关于素数的猜想

猜想一

M=2×3×5×7×11×13×……×N+1,1~N为连续质数，用从1到N之间的任何一个质数去除M，总是余1！

那么这个M是质数还是合数呢？

M=2×3×5×7×11×13+1=30031=59×509, 所以M不一定是质数。

其他猜想

  • 费马猜想：
    • 所有具$2^{2^n} + 1$形式的数均为素数（称之为费马数）
    • 欧拉发现，下一个费马数$2^{32} + 1$即为合数
  • 梅森发现有的素数具$2^{p} − 1$的形式，其中p为素数。为纪念他的贡献，此类素数后来被称为梅森素数。
  • 黎曼猜想。 黎曼通过研究发现， 素数分布的绝大部分猜想都取决于黎曼zeta函数ζ（s）的零点位置。他猜测那些非平凡零点都落在复平面中实部为1/2的直线上， 这就是被誉为千禧年世界七大数学难题之一的黎曼猜想， 是解析数论的重要课题。
  • 孪生素数猜想
    • 存在无穷多对相差2的素数
    • 如果p和p+2都是素数， 那么就称他们为孪生素数。一个重要的问题就是：是否存在无限多对孪生素数？美国华人张益唐对这个问题的解决迈出了重要一步，他证明了有无穷多对差小于七千万的素数。之后大家不断改进他的证明，现在这个七千万已经缩小到246.
    • 3,5 5,7 11,13 17,19…
  • 哥德巴赫猜想（Goldbach Conjecture)
    • 偶数哥德巴赫猜想：任一大于2的偶数可表示成两个素数之和 (“1+1”)
    • 奇数哥德巴赫猜想：任一大于5的奇数都可以表示为三个素数之和
    • “a+b”：每个大偶数N都可表为A+B，其中A和B的素因子个数分别不超过a和b。显然，哥德巴赫猜想就可以写成”1+1”。
    • 证明：
      • 陈景润证明了 “1 + 2 ”，即任何大于6的偶数都是一个素数加上两个素数的积

哥德巴赫猜想（每个大于2的偶数可表示成两个素数之和

素数的应用

这个现实，又表明M一定是质数。

  • 公钥加密利用了难以将大数分解成其素因数之类的性质
    • 几个公开金钥加密算法，如RSA与迪菲－赫尔曼金钥交换，都是以大素数为其基础（如512位元的素数常被用于RSA里，而1024位元的素数则一般被迪菲-赫尔曼金钥交换所采用）。RSA依靠计算出两个（大）素数的相乘会比找出相乘后的数的两个素因数容易出许多这个假设。迪菲－赫尔曼金钥交换依靠存在模幂次的有效算法，但相反运算的离散对数仍被认为是个困难的问题此一事实。

参考