miller-rabin 复现程序
环境：Intel Core i9-12900K，WSL2 内核 6.6.87.2，GCC 16.1.1 20260430，GMP 6.3.0，OpenSSL 3.6.2（源码对照），Python 3.14.5，matplotlib 3.11.2。计时无关的程序都用固定输入或固定种子，重复运行输出相同。
| 文件 | 内容 | 命令 |
|---|---|---|
mr64.h |
64 位 Miller-Rabin（前 12 个素数底、Sinclair 7 底）、强 Lucas、BPSW | 头文件 |
mr64_test.c |
与 \(10^8\) 以下筛法、GMP 6.3.0、已知强伪素数、\(2^{64}\) 边界交叉测试；演示溢出与零底数两个 bug | gcc -O2 -Wall -Wextra -o mr64_test mr64_test.c -lgmp && ./mr64_test |
psp64_verify.c |
用 \(2^{64}\) 以下全部 2-伪素数表计算 \(\psi_k\)，检查各底数集合与 BPSW | gcc -O2 -Wall -Wextra -o psp64_verify psp64_verify.c && bzcat psps-below-2-to-64.txt.bz2 \| ./psp64_verify |
liars.c |
20000 以下奇合数的 Fermat 说谎者、强说谎者计数，Korselt 交叉检查 | gcc -O2 -Wall -Wextra -o liars liars.c && ./liars 20000 > liars.csv |
monier_check.py |
用 Monier 的强说谎者计数公式核对 liars.csv
中的全部暴力结果（先运行 liars） |
python3 monier_check.py |
fips_c1.py |
FIPS 186-5 附录 C.1 公式 (2)，重算 Table B.1 与 OpenSSL 文档中的误判率 | python3 fips_c1.py |
prime_gen_sim.c |
按 OpenSSL 3.6.2 probable_prime() +
BN_generate_prime_ex2() 建模的 1024
位素数生成统计 |
gcc -O2 -Wall -Wextra -o prime_gen_sim prime_gen_sim.c -lgmp -lm && ./prime_gen_sim |
plot_liars.py |
由 liars.csv 生成
../strong-liar-ratio.svg（先运行
liars） |
/tmp/mplenv/bin/python plot_liars.py |
plot_error_bounds.py |
由 fips_c1.py 生成
../mr-error-bounds.svg |
/tmp/mplenv/bin/python plot_error_bounds.py |
外部数据（不随仓库分发）：psp64_verify 需要
Jan Feitsma 计算、William Galway 整理的 \(2^{64}\) 以下全部 2-Fermat
伪素数表。
- 下载：https://www.cecm.sfu.ca/Pseudoprimes/psps-below-2-to-64.txt.bz2（说明页 https://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html）
- 大小 883,505,091 字节，解压约 2.35 GB，118,968,378 行
- SHA-256：
3b92a884be4a365ca91cbd7c9272620bc7e081335a0251e3531b404f2d36f8ef
mr64_test（-DSIEVE_N=2000000
缩小规模）、liars 3000、psp64_verify（表的前
30 万行）在
-O1 -g -fsanitize=address,undefined -fno-sanitize-recover=all
下完整运行，无报错；prime_gen_sim
在同样选项下运行了 150 秒（未跑完）无报错。