miller-rabin 复现程序
内容提要
文章介绍 Miller-Rabin 素性测试的复现程序，包括 64 位 MR、强 Lucas 与 BPSW 实现及测试工具，通过筛法、GMP 和已知伪素数交叉验证，演示溢出与零底数 bug，统计 Fermat 与强说谎者并核对 Monier 公式，并按 OpenSSL 建模 1024 位素数生成，绘制误差界图。
延伸解读
复现环境与工具链
文章基于 Intel Core i9-12900K、WSL2 内核 6.6.87.2、GCC 16.1.1、GMP 6.3.0、OpenSSL 3.6.2、Python 3.14.5 和 matplotlib 3.11.2 进行复现。计时无关的程序使用固定输入或固定种子，确保重复运行输出一致。这为结果的可重复性提供了基础，也提示读者若需复现，应尽量匹配这些环境条件。
外部数据依赖与验证
psp64_verify 需要 Jan Feitsma 计算、William Galway 整理的 2^64 以下全部 2-Fermat 伪素数表，该表不随仓库分发，需从指定网址下载。文件大小约 883 MB，解压后约 2.35 GB，共 118,968,378 行，并提供了 SHA-256 校验值。这强调了外部数据在验证中的关键作用，以及下载和校验的必要性。
测试覆盖与健壮性检查
mr64_test 与 10^8 以下筛法、GMP、已知强伪素数及 2^64 边界交叉测试，并演示溢出与零底数两个 bug。liars 统计 20000 以下奇合数的 Fermat 说谎者和强说谎者，并用 Korselt 交叉检查。monier_check.py 用 Monier 公式核对暴力结果。这些测试覆盖了正确性、边界条件和常见错误，有助于评估实现的可靠性。
素数生成建模与误差分析
prime_gen_sim 按 OpenSSL 3.6.2 的 probable_prime() 和 BN_generate_prime_ex2() 建模 1024 位素数生成统计。fips_c1.py 重算 FIPS 186-5 附录 C.1 公式 (2) 及 Table B.1 与 OpenSSL 文档中的误判率，并生成误差界图。这为理解实际素数生成中的误判率提供了参考，但需注意模型基于特定 OpenSSL 版本。
Q&A
Miller-Rabin 复现程序包含哪些主要文件和功能？
程序包含 mr64.h（64 位 Miller-Rabin、强 Lucas、BPSW 实现）、mr64_test.c（交叉测试与 bug 演示）、psp64_verify.c（用 2^64 以下伪素数表验证）、liars.c（统计 Fermat 与强说谎者）、monier_check.py（核对 Monier 公式）、fips_c1.py（重算误判率）、prime_gen_sim.c（建模 1024 位素数生成）、plot_liars.py 和 plot_error_bounds.py（绘图）。
如何运行 Miller-Rabin 复现程序中的测试？
使用 gcc 编译并运行，例如：gcc -O2 -Wall -Wextra -o mr64_test mr64_test.c -lgmp && ./mr64_test；psp64_verify 需要外部伪素数表，命令为 bzcat psps-below-2-to-64.txt.bz2 | ./psp64_verify；liars 运行 ./liars 20000 > liars.csv；monier_check.py 用 python3 monier_check.py 运行。
psp64_verify 需要什么外部数据？如何获取？
需要 Jan Feitsma 计算、William Galway 整理的 2^64 以下全部 2-Fermat 伪素数表，下载地址为 https://www.cecm.sfu.ca/Pseudoprimes/psps-below-2-to-64.txt.bz2，文件大小 883,505,091 字节，解压约 2.35 GB，共 118,968,378 行，SHA-256 为 3b92a884be4a365ca91cbd7c9272620bc7e081335a0251e3531b404f2d36f8ef。
程序演示了哪些 bug？如何验证？
演示了溢出与零底数两个 bug，在 mr64_test.c 中通过交叉测试展示。使用 -O1 -g -fsanitize=address,undefined -fno-sanitize-recover=all 编译运行可检测这些错误。
liars.c 和 monier_check.py 的作用是什么？
liars.c 统计 20000 以下奇合数的 Fermat 说谎者和强说谎者数量，并进行 Korselt 交叉检查，输出 liars.csv；monier_check.py 用 Monier 的强说谎者计数公式核对 liars.csv 中的全部暴力结果。
prime_gen_sim.c 模拟了什么？如何运行？
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。
