扩展欧几里得算法本身无错，但 long long 无法承载大整数（如1024位）的中间乘除运算，易溢出；需用高精度库（如boost::cpp_int或OpenSSL BIGNUM），并注意输入校验、内存管理与上下文复用。
为什么扩展欧几里得不能直接套用 long long 算大整数模逆元
因为标准 std::gcd 和手写 ext_gcd 都默认操作 int 或 long long，而大整数（比如 1024 位）一除就溢出、一乘就翻车。不是算法错，是底层类型扛不住——a * b % mod 这种中间步骤在没高精度支持时根本没法算。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 别自己重造轮子：优先用
boost::multiprecision::cpp_int或openssl/bn.h的BIGNUM，它们内部已处理好 Montgomery 归约和溢出截断 - 如果必须手写，先确认模数
mod是奇数且与待求逆元的数a互质；否则逆元不存在，ext_gcd返回的g != 1就得立刻 reject -
ext_gcd本身不关心大小，但每一步的加减乘除都得落到高精度实现上——比如用vector<uint64_t></uint64_t>存数，加法要进位，乘法得用 Karatsuba 或 FFT
boost::multiprecision::cpp_int 下怎么写安全的模逆元函数
它封装了 OpenSSL 底层，支持 mod_inverse，但默认行为容易踩坑：不检查输入是否合法，也不保证结果落在 [0, mod) 区间。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 必须显式检查
gcd(a, mod) == 1，用boost::multiprecision::gcd(a, mod)，别信输入 - 调用
boost::multiprecision::mod_inverse(a, mod)后，手动做一次result %= mod，因为某些版本返回负值 - 避免在循环里反复构造
cpp_int：把常量如mod提前转成cpp_int对象复用，否则每次隐式转换都触发内存分配 - 性能提示：模数
mod若为梅森素数（如2^255 - 19），可用特化算法加速；通用场景下，cpp_int已启用 Barrett reduction，比朴素除法快 3–5 倍
OpenSSL 的 BIGNUM 怎么避免内存泄漏和错误码忽略
BIGNUM 全靠裸指针管理，BN_mod_inverse 返回 NULL 不代表失败——它可能只是因为 gcd != 1，而错误码藏在 ERR_get_error() 里，不查就静默出错。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 所有
BN_new()必须配对BN_free()，推荐用 RAII 封装，比如struct BN_CTX_ptr { ~BN_CTX_ptr() { BN_CTX_free(ptr); } BN_CTX* ptr; }; - 调用
BN_mod_inverse(ret, a, mod, ctx)后，立刻检查返回值是否为NULL，再调if (ERR_peek_error()) { /* 处理 */ }，不能只看返回值 -
BN_CTX必须复用，不能每次调用都BN_CTX_new()——它内部有缓存池，新建开销大，且多线程下需加锁 - 注意字节序：
BN_bin2bn读的是大端，如果你的数据来自网络或文件，确认顺序；否则逆元算出来是对的，但解释成整数就差 8 个 0
为什么有些场景下该用 Montgomery 逆元而不是普通模逆元
在 RSA 密钥生成或 ECC 标量乘中，你不是只要一个逆元，而是要在同一个模数下反复做百次以上模乘——这时普通 mod_inverse + BN_mul + BN_div 组合太慢，而 Montgomery 表示法能把除法换成移位。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- OpenSSL 里用
BN_MONT_CTX_set()初始化上下文后，后续所有BN_mod_mul_montgomery()都自动走 Montgomery 路径，但输入必须先用BN_to_montgomery()转换 - Montgomery 逆元只对固定模数有效，不能拿去解一般同余方程；它的“逆元”其实是
a^{-1} * R mod m，其中R = 2^{k * word_size}，别直接当数学逆元用 - 如果模数是编译期已知的常量（如 NIST 曲线参数），可预计算
R^2 mod m和mod_inv，省掉运行时BN_mod_inverse调用
真正麻烦的从来不是算法本身，而是大整数运算中那些看不见的隐式转换、未定义行为和上下文依赖——比如 OpenSSL 的 BN_CTX 生命周期、cpp_int 的表达式模板延迟求值、甚至不同平台下 uint128_t 是否可用。这些细节不爆一次内存错误，根本不会提醒你。
