扩展欧几里得与模逆元复现程序

目录

所有程序均为零外部依赖的标准 C11(GCC/Clang,使用 __int128 / unsigned __int128)与 Python 3 实现,可通过 run.sh 一键完成编译、Sanitizer 检测、差错验证与实验统计。

文件说明

文件 内容
ext_euclid_core.c 扩展欧几里得、模逆元、Bernstein-Yang divstep 常数时间逆元、CRT、Garner(含 q > 2p 负数修正)、Bellcore 故障攻击、64 位 Montgomery REDC(含 \(m \ge 2^{63}\) 进位修正)与 Barrett 约减的测试
bench_ops.c 32–1024 位 GCD 步数对比(随机输入 vs Fibonacci Lamé 最坏情况 vs Stein vs divstep 上界)与 512–4096 位多精度 CIOS Montgomery RSA-CRT 64 位 limb 乘法次数/耗时测量
rsa_vectors.h 512 / 1024 / 2048 / 4096 位确定性 RSA 测试密钥与明密文向量(\(e = 65537\))
oracle_verify.py 独立 Python 差错验证器(生成 results/walkthrough_traces.txt 并交叉检验 256 位批量 N=62 divstep 矩阵求逆)
plot_bench.py 读取 results/gcd_steps.csv 与 results/rsa_crt_bench.csv 生成 ../gcd-rsa-bench.svg
run.sh 使用临时目录 BUILD_DIR=$(mktemp -d) 构建 -O1 -fsanitize=address,undefined 与 -O2 并产出全部 results/

运行命令

单行执行完整复现(若机器有并行负载,建议用 flock 串行执行计时步骤):

bash run.sh

如需单独重新绘制图表(需安装 matplotlib 的 Python 环境):

python3 plot_bench.py

源码下载

本文相关源码已整理,共 6 个文件。

打开下载目录 →


By .