【番外篇】目前已知最大素数2^136,279,841 - 1

最近，这个数字，比较火啊，那么也来蹭个热度吧，那么这个数字是什么呢，这个数字是目前为止(截止我发这篇文章)，发现的最大的素数，虽然，好像一段时间之内，应该也不太会有人找到比这个更大的数字，好了，那么本篇文章呢，我们就来聊一聊，这个最大的素数。

素数，在密码学当中，我们见到的频率应该还是比较高的，无论是大家熟知的RSA加密算法，还是基于椭圆曲线的密码体系，其中都不难发现素数的身影。

素数有无限多个

对于素数，它是有无限多个的，因此，理论上，我们永远不会找到最大的素数，但是，虽然我们可以证明素数有无限多个，但是，这个证明采用的是反证法，因此，我们并没有找到如何构造一个大素数，我们先来回顾一下这个证明[1]吧。

不妨假设，一共有n个素数，我们记作，然后，我们考虑一个新的数字

根据这个构造，对于任意的都不能被N整除，因此，这里我们可以得到，要么N本身是一个素数，要么N的因子不在列表当中，这与我们之前的假设矛盾，因此我们可以证明素数是有无限多个的。

值得注意的是，这里的N不一定是一个素数，比如，这里我们假设列表为，还有其他例子，可以参考[2]

那么，我们可以得到

因此，这个证明呢，只是告诉了我们素数有无限多个，并没有给出具体构造一个大的素数的方法，在密码学当中呢，我们实际上采用的是随机生成一个大整数，然后在用素性检验的办法，让这个数字大概率是一个素数，只要他是合数的概率小于某个可忽略的值，那么我们就认为他是一个素数，有关于素性检验的相关知识呢，大家可以自行查阅下相关资料，或者我之前写过的文章，这里就不展开来讲了。

梅森素数

之前，我们回顾了素数有无穷多个，那么我们如何来找一个大素数呢，我们来看一下梅森数。

「梅森数」是形如的整数(其中n是正整数)，我们记为，这是以法国数学家马兰·梅森的名字命名的，如果说是一个素数的话，那么我们称这个数字为梅森素数。

我们，先来看几个梅森素数的例子，来回顾下，数学大佬们找梅森素数的过程

这里，我们发现，是不是n如果是素数，那么就是一个素数了，如果这个成立的话，那么就没有本文了，很显然，我们接着往下来计算

结果非常的不amazing啊，我们很快的就找到了一个反例，相反，如果n是一个合数，那么一定不是素数，这个不难证明，我们简单的证明一下

因为n是一个合数，那么n一定可以写成两个数的乘积，也就是，注意，这里的a和b不一定是素数，我们有

好了，我们可以来聊一聊本文标题的数字了，在此之前，也就是2018年12月7日，人们已经找到了第51个梅森素数，然后在「今年(2024)的10月21号」找到了第52个梅森素数，也就是本文标题的数字，具体的每个梅森素数的发现时间，以及发现的方法，可以参考维基百科[3]。

卢卡斯-莱默检验法

根据维基百科的描述，后面几个梅森素数，都是采用卢卡斯-莱默检验法来检验的，那么，我们就捎带看一下这个检验法吧，咳咳，不是为了凑字数。

算法过程

令为检验对象，其中p是素数，因为合数的情况我们已经证明了，一定不会是梅森素数，定义序列

如果，是素数，当且仅当

我们，通过例子来看一下，比如我们要验证是一个素数，我们需要计算因此，验证通过，那么，我们接下来，就来写一个代码吧。

代码实现

这里，我们还是，用Python来简单的写一下吧。

def lucas_lehmer_test(p):
    if p < 2:
        return False

    s = 4
    M = (1 << p) - 1

    for _ in range(p - 2):
        s = (s * s - 2) % M

    return s == 0


if __name__ == '__main__':
    print(lucas_lehmer_test(11))

然后，通过这个，我们也可以发现确实不是梅森素数，但是，这个方法，实际上，只是给了我们检验的办法，并没有告诉我们他的分解是什么，也就是，只是一个判定的方案。这个的正确性证明比较复杂，感兴趣的读者，可以看一下维基百科给出的证明，这里就不写了。

番外

那么这个数字，具体有多大呢，我们来直观的看一下，为了直观的表示呢，我们将这些数字，转换成为音符，这里，我们还是用Python来处理一下。这里，我们首先需要安装一个依赖，将数字转换为midi文件。

pip install mido
pip install python-rtmidi

然后，我们将音符，做一个简单的映射，也就是从C4~A4，具体代码如下

from mido import Message, MidiFile, MidiTrack

# 数字到音符映射（C4到A4）
number_to_note = {
    '0': 60,  # C4
    '1': 61,  # C#4
    '2': 62,  # D4
    '3': 63,  # D#4
    '4': 64,  # E4
    '5': 65,  # F4
    '6': 66,  # F#4
    '7': 67,  # G4
    '8': 68,  # G#4
    '9': 69   # A4
}

def number_to_midi(number_str, filename="output.mid"):
    midi = MidiFile()
    track = MidiTrack()
    midi.tracks.append(track)

    for char in number_str:
        if char in number_to_note:
            note = number_to_note[char]
            track.append(Message('note_on', note=note, velocity=64, time=0))
            track.append(Message('note_off', note=note, velocity=64, time=120))

    midi.save(filename)
    print(f"MIDI file saved as {filename}")

这里，我们将BPM做到480，最终我们可以得到一个mid文件，注意，这里，我们只截取前1000位，至于为啥只要1000位呢，因为这个东西太大了，当然，如果你电脑，空间足够大，也可以试试全部转换（慎重尝试）。

那么，这里，我们可以通过BPM来计算一下音乐的大致时长，我们知道BPM是秒每拍，也就是

也就是，我们可以得到总时长为

也就是125秒，这里，这个数字有41,024,320位大小，也就是我们可以算出来，如果全部转换成音符，那么我们大约需要

如果，一直播放的话，也需要大约59.3天，才可以播放完毕，具体如何转换呢，我们可以采用fluidsynth[6]这个工具来进行转换，具体命令如下

fluidsynth -ni FluidR3_GM.sf2 output.mid -F output.wav -r 44100

然后，我们这里可以得到一个wav文件，就是具体的音频，这里就不放上来了，有兴趣的读者，可以自行的转换试试。

总结

本篇文章呢，我们主要聊了一下目前为止，发现的最大的一个素数，以及梅森素数的一个检验的办法，以及我们直观展示了，这个数字，具体究竟有多大，好了，快乐的时光总过得特别快，又到了说再见的时候了，咱们下次再见。

参考资料

1. https://en.wikipedia.org/wiki/Euclid%27s_theorem
2. https://www-users.york.ac.uk/~ss44/cyc/p/primeprf.htm
3. https://zh.wikipedia.org/zh-cn/%E6%A2%85%E6%A3%AE%E7%B4%A0%E6%95%B0
4. https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test
5. https://www.mersenne.org/
6. https://www.fluidsynth.org/