我发现了当今最大的素数，数学界怎么判断我这是真的还是瞎编的？

发布时间：

2024-11-01 12:39

阅读量：

看到这个问题的第一反应以为你在问

我找到了一个非常大的素数, 比目前已知的所有素数都大, 别人怎么判断我发现的是不是真的素数.

但是往下翻了翻发现大家都在回答"素数有无穷多个, 所以不存在最大的素数". 现在我也不确定题主的原意是什么了.

我会这么想是因为电子前沿基金会 (EFF) 设立了寻找大素数的奖项, 具体信息可以查询官网^[1].

Through the EFF Cooperative Computing Awards, EFF will confer prizes of:
$50,000 to the first individual or group who discovers a prime number with at least 1,000,000 decimal digits (awarded Apr. 6, 2000)
$100,000 to the first individual or group who discovers a prime number with at least 10,000,000 decimal digits (awarded Oct. 22, 2009)
$150,000 to the first individual or group who discovers a prime number with at least 100,000,000 decimal digits
$250,000 to the first individual or group who discovers a prime number with at least 1,000,000,000 decimal digits

第一个被找出超过 $100$ 万位的素数是 $2^{6972593}-1$ , 有 $2,098,960$ 位数;

第一个被找出超过 $1000$ 万位的素数是 $2^{43112609}-1$ , 有 $12,978,189$ 位数;

目前人们发现的最大素数是 $2^{136279841}-1$ , 有 $41,024,320$ 位数, 这是前几天 (2024年10月21日) 最新的结果^[2], 但仍然没有突破一亿位的大关.

五万美金和十万美金的奖已经被人拿走了, 但十五万和二十五万美金的奖项还在. 如果你能找到更大的素数, 是有机会获得奖金的.

回到原题. 如果题主真的是说"找到了最大的素数", 那么确实如其他答主所说, 不存在最大的素数, 因为有无穷多个素数; 如果是我理解的那个意思, 那么不妨了解一下素数检验法.

试除法

检验一个正整数 $n$ 是否为素数最笨的方法是: 用所有小于 $n$ 大于 $1$ 的正整数去除 $n$ , 如果都不能整除, 那么 $n$ 就是素数; 否则就是合数.

读过小学二年级的学生都很聪明, 他们发现只需要考虑小于等于 $\frac{n}{2}$ 的正整数就行了, 因为如果某个大于 $\frac{n}{2}$ 的正整数可以整除 $n$ , 那么商必定小于等于 $\frac{n}{2}$ , 所以在此之前我们就已经把 $n$ 整除掉了.

初中生观察力更强, 他们发现只需要拿小于等于 $\sqrt{n}$ 的正整数去检验就够了, 理由和上面一样.

高中生又注意到一个细节, 在拿小于等于 $\sqrt{n}$ 的正整数试除时, 我们只需要拿素数去试除就够了, 因为如果 $n$ 能被某个合数整除, 那么必定能被某个小于这个合数的素数整除.

因此试除法的策略是这样:

给定一个正整数 $n$ , 用每一个小于等于 $\sqrt{n}$ 的素数试除 $n$ . 如果某个素数将 $n$ 整除了, 那么 $n$ 就是合数; 如果都不能整除, 那么 $n$ 是素数.

Wilson (威尔逊) 检验法

初等数论里有一个广为人知的结论:

Wilson定理: $p$ 是素数的充分必要条件是 $(p-1)!\equiv -1 \pmod p$ .

这个定理给出了一个充分必要条件来做素性检验, 不需要像试除法一样一个个试过去.

如果 $p$ 是一个相对较小的正整数, 我们可以很轻松地利用Wilson定理来确定 $p$ 是不是素数; 但是当 $p$ 很大时, 阶乘 $(p-1)!$ 的计算量是很大的.

Fermat (费马) 检验法

此外, 费马小定理提供了一个用来排除合数的检验法.

Fermat小定理: 如果 $p$ 是素数, $1\leq a\leq p-1$ , 那么 $a^{p-1}\equiv 1 \pmod p$ .

如果某个自然数 $p$ 不满足上述同余性, 就必定是合数; 但是这个定理的逆命题不成立, 一个正整数满足上述性质并不表明它就一定是素数, 也有可能是合数.

Miller–Rabin (米勒-拉宾) 检验法

类似地, 我们也有可以用来筛选疑似素数的检验法.

定义: 设 $n>2$ 是正整数且满足 $n-1=2^{s}t$ , 其中 $s$ 是非负整数, $t$ 是正奇数. 我们称 $n$ 通过以 $b$ 为基的Miller (米勒) 检验, 如果
$b^t\equiv \pmod{n}$
或者对某个 $j\in\{1\cdots, s-1\}$ 成立
$b^{2^jt}\equiv -1\pmod{n}.$

Rabin概率素性检验法是基于以下定理:

定理: 设 $n$ 是一个正整数. 取 $k$ 个不同的小于 $n$ 的正整数作为基, 对 $n$ 做每一个基的米勒检验. 如果 $n$ 是一个合数, 那么 $n$ 通过所有 $k$ 个检验的概率不超过 $\frac{1}{4^k}$ .

如果一个正整数能够多次通过以上检验, 就表明这个数很有可能是素数, 于是我们就可以把它筛选出来进一步研究.

Lucas-Lehmer (卢卡斯-雷默) 检验法

一般而言, 想要找到一个充分必要且高效的素性检验法并不容易; 但是对于梅森数却有这么一个定理.

目前我们发现的大素数大都是Mersenne (梅森) 素数.

定义: 设 $m$ 是正整数, 我们称 $M_m:=2^m-1$ 为第 $m$ 个梅森数; 如果 $p$ 是一个素数, 并且 $M_p$ 也是素数, 就称 $M_p$ 为梅森素数.

一直以来, 很多人都致力于寻找更大的梅森素数, 而且还成立了互联网梅森素数大搜索 (Great Internet Mersenne Prime Search 简称GIMPS) 这么一个团队. 前些天发现的目前已知最大素数 $2^{136279841}-1$ 就是GIMPS的志愿者找出来的.

对于梅森素数, 有一个非常高效的检验法:

Lucas-Lehmer定理: 设 $p$ 是素数, 考虑梅森数 $M_p:=2^p-1$ . 定义序列
$\begin{equation*} r_k= \begin{cases} 4 &\mbox{如果 } k=1,\\ r_{k-1}^2-2 &\mbox{如果 } k\ge2. \end{cases} \end{equation*}$
那么 $M_p$ 是素数的充分必要条件是 $r_{p-1}\equiv 0 \pmod{M_p}$ .