序章
みなさんは「既知の世界最大の素数」と聞いて，どれくらいの大きさを想像しますか？
現在発見されている世界最大の素数は，
$$ 2^{136279841}-1$$
です。これは10進法表記で41,024,320桁という途方もない巨大さを誇るもので，2024年10月12日にGIMPSでLuke Durant氏により発見されました。
このように10進法表記において $2^p-1$ とすることができる素数を「メルセンヌ素数」といい，指数部分を使って$M136279841$のように表記します。
$2^p-1$で表記できる数は，Lucas–Lehmer primality test(リュカ–レーマーテスト)と呼ばれるテストにより，普通の数に対する確率的素数判定法よりも圧倒的に少ない計算リソースで素数判定が行えるという特徴があります。
それゆえに，コンピュータの登場以降に発見されている巨大の素数のほとんどがこのメルセンヌ素数です。
本記事では現在の世界記録レベルのメルセンヌ素数を探索する方法について重点を置き，実際にGPUを使って世界記録レベルのメルセンヌ素数を探してみます。(もし見つけることができれば，数学史に名前が残ります！)
リュカレーマーテストのPoC
メルセンヌ数 $M_p = 2^p - 1$ に対して，次のような漸化式で定義される数列を考えます。
$$s_0 = 4, \ s_{n+1} = {s_n}^2 - 2$$
このとき，
$$M_p: prime \Leftrightarrow s_{p-2} \equiv 0 \bmod M_p$$
という性質が知られています。
つまり，初項を4として「二乗して2を引く」という操作を $p-2$ 回 繰り返した後の数が$M_p$ で割り切れることが，メルセンヌ数 $2^p-1$ が素数であるための必要十分条件ということです。
ここで，${s_n}$は2乗のオーダーで急速に増加するため，実際に計算する際には漸化式の計算を繰り返すごとに$\bmod M_p$をとります(合同式の成立より，結果は変わりません)。
実際にリュカレーマーテストをコードに落とし込むと，次のようになります(Rust)。
```Rust
pub fn lucas_lehmer(p: u32) ->bool {
// 2^p-1を計算 (左シフト演算を利用すると一瞬です)
let m: Integer = (Integer::from(1)<< p) - 1;
// 初項4の数列
let mut s: Integer = Integer::from(4);
let timer: Instant = Instant::now();
for n in 2..=p - 1 {
// 数列の次の項を計算
let timer: Instant = Instant::now();
s = s.pow(2) - 2;
println!("DEBUG: n = {}; s.pow(2)-2 took {}ms", n, timer.elapsed().as_micros());
// mod M_pを取る(折り畳みで高速化)
let mut i = 0;
while s >= m {
i = i + 1;
s = Integer::from(&s >>p) + (s & &m);
if s == m {
s = Integer::from(0);
break;
}
}
}
// sが0であるとき、M_pは素数
s == 0
}
```
実行してみると次のようにメルセンヌ数を正しく素数判定することができています。
この簡易的なプログラムでは，M859433のテストが1089秒で完了しています。しかし世界記録レベルの数にしてみると，ETRに5809時間(8か月)という文字が。単純な自前の実装では到底世界記録レベルの素数を探すのは難しいようです。
$M_p$が素数ならば，pは素数であることが知られています。対偶を取れば，
pが素数でないならば$M_p$は素数にはなりえないので，lucas_lehmerの前にフィルターすることをお勧めします。
GPUとメルセンヌ素数
長らくリュカレーマーテストはCPUにより行われてきました。実際，例えば2018年12月7日に発見された51番目のメルセンヌ素数$M82589933$は，i5-4590TでPrime95を利用して発見されています。
しかし2024年に新しく発見されたメルセンヌ素数$M136279841$は，はじめて探索にGPUが用いられました。より具体的には，GPUによる確率的素数判定に対応したPRPLLと呼ばれるソフトウェアが用いられました*。
事実上，2024年度以降の記録レベルの素数探索はGPUによって行われています。そもそもなぜ今までCPUが用いられていたかといえば，リュカレーマーテストは何度も剰余計算を繰り返す複雑な計算であり，並列化がほとんどできないためです。
しかしPRPLLはそもそも初回探索にリュカレーマーテストを用いておらず，確率的な素数判定問題に帰着させることでGPUによる並列処理に成功しています。つまり，GPUによるPRPで"候補"を絞り込んで，それを最終的にリュカレーマーテストで確定させる運用です。
*M136279841はA100というデータセンター向けのGPUを利用して発見されています。
PRPLLのセットアップ方法
ここではGPUクラウド「vast.ai」でGPUインスタンスを借りて動かしてみます。
Vast.ai | Console - cloud.vast.ai
手元のGPUで試す場合は以下のコマンドでコンテナを立ち上げてください。
```Bash
docker run -it --rm --gpus all nvidia/cuda:12.8.0-devel-ubuntu24.04 /bin/bash
```
私はひとまず練習用にRTX 4070のインスタンス($0.106/hr)を立ち上げてみます。
コンテナを立ち上げたら，以下のコマンドアップでセットアップができます。NVIDIAのGPUであっても，CUDAではなくOpenCLで動作することに注意してください。
```Bash
# 必要ライブラリの用意
apt-get update
apt-get install -y git build-essential ocl-icd-libopencl1 ocl-icd-opencl-dev opencl-headers clinfo
apt-get purge -y pocl-opencl-icd || true
mkdir -p /etc/OpenCL/vendors
echo libnvidia-opencl.so.1 >/etc/OpenCL/vendors/nvidia.icd
# PRPLLのビルド
git clone https://github.com/preda/gpuowl.git /opt/gpuowl
cd /opt/gpuowl
make -j"$(nproc)"
```
セットアップができたら，以下のコマンドで試しに$M859433$が素数であることを判定してみます。まずチューニングが行われたあとにテストが実行されます。
```Bash
./build-release/prpll -device 0 -dir /opt/gpuowl -prp 859433 -tune 256:2:256:1:1
```
チューニングには30分～1時間近くかかりますが，素数判定が10%ほど早くなります。
なお検証用途でチューニングを飛ばしたい場合は，以下のように私の構成をそのまま流用することもできます。
```Bash
curl https://api.end2end.tech/download?id=134b68b58ae0 -o tune.txt
./build-release/prpll -device 0 -dir /opt/gpuowl -prp 859433
```
1枚のRTX 4070では$M859433$の判定にちょうど100秒かかりました。
いろいろGPUを借りてやってみる
PRPLL/GpuOwlのPRPはFP64(二重精度)のFFTとIBDWTが中心なので，基本的にはFP64性能とメモリ帯域がボトルネックになります。そのためデータセンター向けのGPU「H100」や「A100」あたりがかなり有利です。
試しにいろいろなGPUを借りて，素数判定にかかる時間を実際に調べてみます。
なお記録レベルの素数を探す場合には，ストレージは一時的に50GB程度まで使うことがあるので，60GBくらいはあると安心です。またvCPUは8コア前後，RAMは32GB～64GB程度のものがお勧めです。
【RTX 4070】
\\$0.106/hrくらい。
M859433に100秒かかりました。
M13466917に3628秒かかりました。
【RTX 5090】
\\$0.369/hrくらい。
M859433に45秒かかりました。
M13466917に1286秒かかりました。
【A100 SXM4】
\\$0.600/hrくらい。
M859433に38秒かかりました。
M13466917に744秒かかりました。
【H100 SXM】
\\$1.342/hrくらい。
M859433に26秒かかりました。
M13466917に460秒かかりました。
【H200 NVL】
\\$1.659/hrくらい。
M859433に31秒かかりました。
M13466917に495秒かかりました。
以上を総合すると，$M13466917$の1回の判定にかかる金額はこんな感じになります。
RTX 4070: $0.1068
A100 SXM4: $0.1240
RTX 5090: $0.1318
H100 SXM: $0.1715
H200 NVL: $0.2281
ここから，RTX 4070が一番コスパが良いことが分かります。しかし指数を大きくしていくとメモリの帯域も重要になってくるため，世界最大レベルを探すには実際に$M136279841$に用いられたA100あたりが最適かもしれません。
ちなみに，$M859433$で計算すると結果が逆転してRTX 5090が一番コスパが良いことになります。これは扱う値が小さすぎて，A100がFP64性能を生かし切れていないことが原因だと推測できます。
実際に世界記録レベルの素数判定をやってみた
以上よりA100が最もコスパ良く計算できることが分かったので，A100のインスタンスを借りて，世界記録レベルの素数判定をやってみます。
今回はこのインスタンスを使うことにしました。
スペックはこんな感じです。
金額: \\$0.553/hr
CPU: 2xAMD EPYC 7502 32-Core Processor (128 vCPU)
GPU: A100 SXM4
メモリ: 225.5 GB
ディスク: 70GB
これだけ一つ突出して安かったのでなぜかと疑問に思っていたら，GFWが通されていました。GitHubにさえ接続できませんが，適当にプロキシを挟んでバイパスします。
```Bash
curl -L --max-time 60 -o /tmp/gpuowl.zip https://ghfast.top/https://github.com/preda/gpuowl/archive/refs/heads/master.zip
mkdir -p /opt/gpuowl && unzip -q /tmp/gpuowl.zip -d /tmp && mv /tmp/gpuowl-master/* /opt/gpuowl/ && rm -rf /tmp/gpuowl-master /tmp/gpuowl.zip
cd /opt/gpuowl
make -j"$(nproc)"
```
以下のコマンドで `autoprimenet.py` というツールを導入します。これもきちんとGFWをバイパスしていきます。
```Bash
cd /opt/gpuowl
# GFWをbypassするため一度Gitにあげて、そこから落とします
# GFWがない場合: curl -O https://download.mersenne.ca/AutoPrimeNet/autoprimenet.py
curl -O https://ghfast.top/https://gist.githubusercontent.com/ActiveTK/0915b91bfac2cc2deefa0ecc57c39496/raw/6f986f7627d2a7e446776c86d916c5fe6eaf9040/tmp_to_bypass_gfw_autoprimenet.py
mv tmp_to_bypass_gfw_autoprimenet.py autoprimenet.py
python3 autoprimenet.py --setup
```
表示されたプロンプトでは以下を入力します。
Program: 3 (PRPLL)
Type of work: 152 (既知最大素数の指数以下は割り当てない)
GPUの選択: 0 (手元だとA100が0番目にあります)
Proof一時領域: 50 (一時領域を50GBに指定)
そして，以下を実行して実際に割り当てられたメルセンヌ数を確認します。
```Bash
python3 autoprimenet.py --timeout 0
```
チューニングは面倒なので省略して，別環境のものを流用します。
```Bash
curl https://api.end2end.tech/download?id=134b68b58ae0 -o tune.txt
```
そして実行。sshが切れたら怖いのでscreenで実行します。
```Bash
apt-get update && apt-get install -y screen
screen -S prp -dm bash -lc "stdbuf -oL /opt/gpuowl/build-release/prpll -device 0 -dir /opt/gpuowl -prp 142515349 2>&1 | tee -a /opt/gpuowl/prpll.log"
screen -r prp
```
一度(続けながら)切りたいときは[Ctrl-a]→[d]で，再接続したいときは `screen -r prp` と入力してください。
ひとまず動いたので安心。128コアのCPUが余ってるのは勿体ないので，バックグラウンドではmkp224oでも動かしておきますか。端数の8コアだけ残して，120スレッドで立ち上げます。
```Bash
# mkp224oを入れてscreenで動かす
sudo apt install gcc libc6-dev libsodium-dev make autoconf
git clone https://ghfast.top/https://github.com/cathugger/mkp224o /opt/mkp224o
cd /opt/mkp224o
./autogen.sh
./configure
make
screen -S mkp224o -dm bash -lc "stdbuf -oL /opt/mkp224o/mkp224o {好きな文字列} -t {スレッド数} -v -s -d /opt/mkp224o/logs/ 2>&1 | tee -a /opt/mkp224o/mkp224o.log"
screen -r mkp224o
# 現在のscreen一覧を閲覧
screen -ls
# mkp224oを終わらせる
screen -S mkp224o -X quit
```
この環境では約23億key/sの速度で総当たりができるみたいです。以前512コアのサーバーを借りたときはちょうど100億key/s程度だったので，その1/5程度ですね。
あとはひたすら待機します。関係ないですが，GFWがあるのになぜかcloudflared tunnelは動きました。高スペックなPCのタスクマネージャーって，見ていてなんだかワクワクしますよね(小並感)。
予測では1d 03:15となっているので，処理に28時間くらいかかりそうです。事前・事後の準備含めて30時間と仮定すると，\\$0.553/h * 30h = \\$16.59。2500円くらいかかる予定です(高校生の私にはとても大きな出費！)。明日までこの記事を放置します。
明日の自分へ:
```Bash
ssh -p 54401 [email protected] -L 8080:localhost:8080 -i .ssh/vastai
screen -r prp
screen -r mkp224o
```
どうも。明日になりました(飛躍)。昨日の自分くんありがとう。
結果は... 残念ながら私がテストした $M142515349$ は素数ではありませんでした。
こんな感じのログが出てきます。statusが"C"なら合成数，"P"なら素数かもしれないというものです。
```Json
{
"status": "C",
"exponent": 142515349,
"worktype": "PRP-3",
"res64": "9e813c004847abcf",
"res2048": "31e291af11eb950ba276dd1282c5a39e0bbb5304608f22f2a787705c0db1dfc93ac2eaf3b6bf32983b40989ed78fece5b8567f205b30f666d35b396f3f35def60fd0ba76b37bad124a7a5cd735e0eb5d93f016ee8262f050ce29c136476be3f93fc4e998bec120c720a35dc06c1bda58ebc20c4ff077d0a650a90734331aef1fc8d63631a9d31a703c3fd5714e14ecca8308fd8f8e71f4de38d3388976bb57125e834ffd138dfc103a4ff25426d83933bf57ae5d65dfdf17e26bcc84e5c0f13e9d940eb47f041e4f57bc29202e01e3afcd37c5239b9cce01d834138832fa50575e2081bdab7989f0e5f49097862dd22e6079f805e7eb4d119e813c004847abcf",
"residue-type": 1,
"errors": {
"gerbicz": 0
},
"fft-length": 8388608,
"proof": {
"version": 1,
"power": 10,
"hashsize": 64,
"md5": "d7f868cff9aa15584211bdf02862598a"
},
"program": {
"name": "prpll",
"version": "",
"port": 8,
"os": {
"os": "Linux",
"version": "5.15.0-153-generic",
"architecture": "x86_64"
}
},
"uid": "gpuowl",
"timestamp": "2025-09-15 06:47:50"
}
```
完了したら，以下のコマンドで結果のアップロードを行います。
```Bash
python3 autoprimenet.py --upload-proofs --timeout 0
```
全体のログファイルは[こちら](https://end2end.tech/b2d968c7b8f1)に置いておきます。
また，私がテストした$M142515349$の結果は以下から調べることができます。
https://www.mersenne.org/report_exponent/?exp_lo=142515349&full=1
結局，トータルで27時間24分かかりました。同じテストをi9 12900Kで走らせたところETAが14 daysになっているので，A100はかなり高速でテストができていることが分かります。
なお，ついでにmkp224oの結果も入手しておきます。120スレッドで30時間近く動かしていたので，かなり多くのアドレスが見つかりました。
```Bash
tar -czf results_mkp224o.tar.gz /opt/mkp224o/logs/
curl https://api.end2end.tech/upload \
-X POST \
-F file=@results_mkp224o.tar.gz
```
ちなみに$M136279841$を発見したLuke Durant氏はGIMPSの[インタビュー](https://youtu.be/Yp4ilFOtoeg?si=6e-kh_GdfwTWIu4A&t=445)で，「どれくらいのお金を費やしたのか？」と聞かれて「I believe it's under two million.」と回答しているので，3億円近くGPUリソースを使って発見していることが分かります。
力こそPowerであり，お金こそMoneyということですね...なるほどなるほど。恐ろしい世界ですが，お金さえあれば数学史に歴史を残せるという意味ではロマンはあります。
さよなら，破格の最強GPUインスタンス(GFWのオマケ付き)さん👋
いつかまた使わせてもらうかもしれないので，覚えておこう。
Instance ID: 25884430
Host: 155386
Machine ID: 42479
ちなみに，セットアップまで含めた総費用は，
GPU代: \\$15.3
ストレージ代: \\$0.56
のトータル \\$15.86 でした。日本円換算で2,342円です。
メモ: WebTaskmgrを導入する
途中で画面が映っていましたが，WebTaskmgrは私が開発している「たった一つのPHPファイルだけで動作する」がコンセプトのサーバー管理用の多機能タスクマネージャーです。
Web上でリソース管理からプロセス操作，ファイル編集まで全部が完結します。パスワード設定やIPアドレス制限にも対応しています。
以下のコマンドで導入からCloudflare経由のポート公開まで全部できますので，よろしければご利用ください！
```Bash
set -euo pipefail
export DEBIAN_FRONTEND=noninteractive
if ! command -v php >/dev/null 2>&1; then
sudo apt-get update -y
sudo apt-get install -y php-cli curl ca-certificates
fi
if ! command -v cloudflared >/dev/null 2>&1; then
sudo mkdir -p /usr/local/bin
sudo curl -fsSL -o /usr/local/bin/cloudflared \
https://github.com/cloudflare/cloudflared/releases/latest/download/cloudflared-linux-amd64
sudo chmod +x /usr/local/bin/cloudflared
fi
sudo mkdir -p /var/www/html
sudo chown "$(id -u)":"$(id -g)" /var/www/html
[ -f /var/www/html/index.php ] || printf '%s\n' '/var/www/html/index.php
curl https://raw.githubusercontent.com/ActiveTK/WebTaskmgr/refs/heads/main/WebTaskmgr.php -o /var/www/html/_WebTaskmgr.php
PORT=""
for p in $(seq 18080 18120); do
if ! ss -tln 2>/dev/null | grep -q ":$p\b"; then
PORT=$p; break;
fi
done
[ -n "$PORT" ] || { echo "空きポートが見つかりませんでした"; exit 1; }
pkill -f "php -S 127.0.0.1:$PORT" 2>/dev/null || true
pkill -f "cloudflared tunnel --url http://127.0.0.1:$PORT" 2>/dev/null || true
sleep 0.2
PHP_LOG="/var/www/html/php_${PORT}.log"
nohup php -S 127.0.0.1:"$PORT" -t /var/www/html >"$PHP_LOG" 2>&1 & disown
for i in {1..20}; do
curl -fsS "http://127.0.0.1:$PORT" >/dev/null && break
sleep 0.3
done
CF_LOG="/var/www/html/cf_${PORT}.log"
nohup cloudflared tunnel --url "http://127.0.0.1:$PORT" --no-autoupdate --logfile "$CF_LOG" >>"$CF_LOG" 2>&1 & disown
URL=""
for i in {1..30}; do
URL=$(grep -o 'https://[0-9a-z.-]*trycloudflare.com' -m1 "$CF_LOG" || true)
[ -n "$URL" ] && break
sleep 0.5
done
echo "DOCROOT: /var/www/html"
echo "LOCAL : http://127.0.0.1:$PORT"
if [ -n "$URL" ]; then
echo "PUBLIC: $URL"
echo "WebTaskmgr: $URL/_WebTaskmgr.php"
else
echo "Cloudflareの外部公開用URLの取得に失敗しました。:"
tail -n 50 "$CF_LOG" || true
fi
```
別のクラウドのGPU鯖でcloudflared tunnelが動かないと思ったら，何がとは言いませんがリージョンが中国でした。
タイムリーですね(この記事が読まれている頃にはもうGFWの情報漏洩事件は忘れ去られているかもしれない)。
最後に
記事の内容は以上です！
みなさんもぜひメルセンヌ素数の探索に挑戦してみてください。もし歴史に名前が残ったらぜひ教えてくださいね；
最後までご覧いただきありがとうございます。