如何高效存储任意大整数并自研实现其模n乘法运算

你之前接触的char数组逐位存十进制数字的实现仅适用于教学演示，CPU字长利用率极低、进位操作频繁，模乘性能和工业级实现差距可达百倍以上，要做高效率的自主实现，按下面的路径走就行，不需要依赖任何第三方库。

存储结构设计 #

• 直接采用CPU原生字长作为大整数的进制位：64位环境下用uint64_t类型的动态数组存储数位，每个数组元素对应2^64进制的1位，单元素能表示的数值范围等价于19位十进制数，CPU字长利用率拉满，进位操作的频次直接降到十进制存储方案的1/19。32位环境替换成uint32_t数组即可，逻辑完全一致。
• 结构体仅需保留3个辅助字段：数组当前存储的有效字长度len、数组预分配的容量cap、符号标记sign（纯模乘场景下所有数都会被映射到0~n-1的正整数区间，可以直接删掉符号位省开销）。
• 数位统一采用小端序存储：数组下标为0的元素存最低位的字，下标越大对应数位的权重越高，做乘法、移位、进位处理时不需要倒序遍历数组，逻辑最简。

十进制逐位存储的唯一优势是打印输出时不需要做进制转换，但凡涉及千位十进制数以上的运算，这个方案没有任何工程上的性能价值。

模乘运算的效率核心 #

• 底层单字乘法直接利用CPU原生双字长乘法能力：x86、ARM等主流64位架构都原生支持64位整数相乘得到128位结果的指令，C/C++下直接用编译器原生支持的__int128类型接收乘积即可，不需要手动拆分高低位计算，单步乘法的耗时和原生64位乘法基本一致。
• 固定模场景直接上蒙哥马利模乘，这是目前所有工业级大整数实现通用的最优模乘方案，比“先算完整乘积再做除法取模”的朴素实现快3~10倍。核心思路是提前把所有运算数转换到蒙哥马利域下，整个模乘过程不需要做耗时的大整数除法，仅靠字乘、加法、移位、进位处理就能直接得到模n下的乘积结果，预计算的转换参数仅需在模n固定时算一次即可。
• 模值频繁变动的通用场景选巴雷特约减（Barrett Reduction）：预计算模n的相关缩放参数后，约减过程同样不需要执行全量大整数除法，性能略低于蒙哥马利模乘，但省去了域转换的固定开销，适配性更强。

可落地的优化细节 #

• 不要为了规避溢出选择2^32、109这类小于CPU字长的进制，会平白增加数组长度和循环次数，浪费CPU原生的双字乘法能力。
• 进位处理不要逐位做溢出分支判断，每轮字乘累加完成后，直接把超出当前字长的进位值存在临时变量里，下一轮计算直接累加该进位值即可，大幅减少分支预测失败的开销。
• 如果你的使用场景是固定长度的大整数运算（比如密码学常用的2048位、4096位模运算），可以直接把存储数组的长度设为编译期固定值，去掉动态内存分配的开销，性能还能再提升30%左右。

内容的提问来源于stack exchange，提问作者Ben Heckmann