1. 从"能跑就行"到"跑得放心"：为什么密码学库的基本运算函数值得单独拎出来说
很多人第一次接触密码学C/C++实现，都是从"调库"开始的——OpenSSL里一个EVP_EncryptInit就完事了，谁还关心底层大数加减乘除怎么写的？我当初也是这么想的，直到有一次在一个嵌入式项目里，因为目标板子资源紧张，不得不自己裁剪一套轻量级的RSA实现，才发现基本运算函数这块的水比想象中深得多。
密码学里的"基本运算"和我们平时写业务代码时的a + b完全不是一回事。它主要指的是大整数运算（Big Integer Arithmetic），包括多精度整数的加、减、乘、除、取模、模逆、模幂这些。为什么这些看似基础的运算在密码学里如此关键？因为几乎所有公钥密码算法——RSA、ECC、DH密钥交换——底层都是建立在大整数模运算之上的。你写一个RSA加密，本质上就是在做m^e mod n，而这个模幂运算又会被拆解成无数次模乘和模平方。如果基本运算函数写得有问题，上层算法再优雅也是空中楼阁。
这篇文章我打算把密码学C/C++实现中基本运算函数这一块彻底讲透。从最底层的表示方法开始，到加减乘除的实现细节，再到模运算和模幂的优化技巧，最后聊聊实际工程中容易踩的坑。适合两类人看：一是正在学习密码学实现、想搞明白底层原理的学生和开发者；二是需要在资源受限环境下自己实现或裁剪密码学库的工程师。我不会假设你有很深的数学背景，但需要你会C/C++，知道指针和数组怎么用。
提醒一句：本文讨论的所有实现都是教学和工程实践层面的，目的是理解原理和掌握正确的实现方法。实际产品中请使用经过充分审计的成熟密码学库，自己手写的实现很容易在侧信道防护等方面出问题。
2. 大整数的表示方式：选错了后面全是坑
2.1 为什么不能用字符串或十进制数组
初学者最容易犯的错误，就是用十进制字符串或者十进制数字数组来表示大整数。比如把123456789表示成[1,2,3,4,5,6,7,8,9]。这样做的好处是直观，打印方便，但性能是灾难性的。
原因很简单：计算机的天然进制是二进制，CPU的算术逻辑单元就是按二进制设计的。你用十进制表示，每次做乘法和除法都要反复做十进制到二进制的转换，而且十进制每一位的信息量只有约3.32比特，而一个32位字能承载32比特的信息。用十进制数组表示，内存利用率不到12%，运算效率更是低得离谱。
正确的做法是用多精度整数（multi-precision integer）表示法，也就是把一个超大整数拆成若干个机器字（通常是32位或64位），存在一个数组里。比如一个1024位的RSA模数，用32位字来存就是32个uint32_t。
2.2 小端序存储与进位方向的选择
多精度整数的存储有个关键决策：低位在前还是高位在前。密码学库中绝大多数采用小端序（little-endian），也就是数组下标0存最低位，下标越大存越高位。
为什么选小端序？因为加法和乘法都是从低位往高位算的，进位也是从低位向高位传播。小端序下，你只需要从下标0开始顺序遍历，进位自然地向下一个下标传递，代码写起来非常自然。如果反过来用大端序，你就得从数组末尾往前遍历，代码可读性和缓存友好性都差一些。
// 小端序多精度整数结构定义 typedef struct { uint32_t *words; // 字数组，words[0]是最低32位 size_t len; // 当前使用的字数 size_t cap; // 分配的容量（字数） int sign; // 符号：0表示非负，1表示负（密码学中多数场景只需要非负） } bignum_t;这里有个细节值得说：len和cap要分开。len是当前有效字数，cap是分配的总容量。做加法时结果可能比操作数多一个字（进位溢出），如果每次运算都重新分配内存，性能会很差。预分配一定的冗余容量，运算时直接写入，只在必要时才扩容，这是工程上的常见做法。
2.3 定长 vs 变长：密码学场景下的取舍
通用大数库（比如GMP）通常用变长表示，数字能动态增长。但密码学场景下，很多时候我们用的是定长运算——比如模数固定是2048位，那所有中间结果都不会超过4096位（两个2048位数相乘）。
定长表示的好处是：不需要动态内存分配，可以用栈上数组，速度快且没有内存碎片问题。在嵌入式或实时系统中这一点尤其重要。缺点是不够灵活，换一个密钥长度就得改代码或重新配置。
我的建议是：如果是学习目的，先用变长实现把逻辑跑通；如果是工程实现，在明确密钥长度范围的前提下，用定长+预分配的方式，性能会好很多。很多成熟的密码学库内部就是这么做的，对外提供统一接口，内部针对常见长度做特化。
3. 加减法：看似简单，但边界条件能坑死人
3.1 加法的进位处理与溢出检测
多精度加法的逻辑很直接：从低位到高位逐字相加，加上低位的进位，结果的低位存入目标，高位作为新的进位。
// 多精度加法：r = a + b，返回最终进位 uint32_t bn_add(uint32_t *r, const uint32_t *a, const uint32_t *b, size_t n) { uint64_t carry = 0; for (size_t i = 0; i < n; i++) { uint64_t sum = (uint64_t)a[i] + b[i] + carry; r[i] = (uint32_t)(sum & 0xFFFFFFFF); carry = sum >> 32; } return (uint32_t)carry; }这段代码看起来简单，但有几个容易出问题的地方。第一，a[i] + b[i] + carry这三个数相加，最大可能是(2^32-1) + (2^32-1) + 1 = 2^33 - 1，用32位变量存会溢出，必须用64位中间变量。第二，返回的进位不能丢——在模运算中，这个进位决定了是否需要做条件减法。
实操心得：很多初学者写加法时忘了处理最高位的进位，导致在模加运算中结果偶尔出错。这种bug特别隐蔽，因为大部分测试用例不会触发进位溢出，只有在特定输入下才暴露。建议写完加法后，专门构造一组"所有位都是0xFFFFFFFF"的测试用例来验证。
3.2 减法与借位：如何避免负数结果
减法比加法稍微麻烦一点，因为涉及借位。当a[i] < b[i] + borrow时，需要向高位借1，相当于a[i] + 2^32 - b[i] - borrow。
// 多精度减法：r = a - b，返回最终借位（1表示a < b） uint32_t bn_sub(uint32_t *r, const uint32_t *a, const uint32_t *b, size_t n) { uint64_t borrow = 0; for (size_t i = 0; i < n; i++) { uint64_t diff = (uint64_t)a[i] - b[i] - borrow; r[i] = (uint32_t)(diff & 0xFFFFFFFF); borrow = (diff >> 32) & 1; // 如果借位了，高位全1，取最低位 } return (uint32_t)borrow; }这里用了一个技巧：在无符号64位运算中，如果a[i] - b[i] - borrow结果为负，它会回绕成一个很大的正数，高32位全是1。所以(diff >> 32) & 1就能提取出借位标志。
在密码学中，减法通常用在模约减的场景：当加法结果超过了模数，需要减去模数。这时候你事先知道a >= b，所以不需要处理借位为1的情况。但作为一个通用的基本运算函数，还是应该把借位返回出来，让调用者决定怎么处理。
3.3 条件减法和模加的实现
模加运算(a + b) mod m的标准做法是：先做普通加法得到sum，如果sum >= m或者加法产生了进位，就减去m。由于a < m且b < m，所以a + b < 2m，最多只需要减一次。
// 模加：r = (a + b) mod m void bn_mod_add(uint32_t *r, const uint32_t *a, const uint32_t *b, const uint32_t *m, size_t n) { uint32_t carry = bn_add(r, a, b, n); // 如果产生进位，或者 r >= m，则需要减去 m if (carry || bn_cmp(r, m, n) >= 0) { bn_sub(r, r, m, n); } }注意这里的bn_cmp是比较函数，从高位往低位比较。这个函数的实现也有讲究：不能从低位开始比，因为高位才是决定大小的关键。从最高有效字开始，找到第一个不相等的字，谁大谁就大。
注意：模加中的条件减法必须用"先加后减"的方式，不能先判断再决定加不加。因为判断本身可能引入时序差异，在密码学中时序攻击是一个真实的威胁。虽然本文不深入讨论侧信道防护，但养成常数时间实现的意识很重要。
4. 乘法：从学校竖式到Karatsuba的跨越
4.1 学校竖式乘法（Schoolbook）的实现
多精度乘法的基本算法就是我们小学学的竖式乘法：用b的每一位去乘a的每一位，然后错位相加。
// 学校竖式乘法：r = a * b，r需要2n个字的空间 void bn_mul_schoolbook(uint32_t *r, const uint32_t *a, size_t alen, const uint32_t *b, size_t blen) { memset(r, 0, (alen + blen) * sizeof(uint32_t)); for (size_t i = 0; i < alen; i++) { uint64_t carry = 0; for (size_t j = 0; j < blen; j++) { uint64_t prod = (uint64_t)a[i] * b[j] + r[i+j] + carry; r[i+j] = (uint32_t)(prod & 0xFFFFFFFF); carry = prod >> 32; } r[i + blen] = (uint32_t)carry; } }这段代码的时间复杂度是O(n²)。对于1024位（32个字）的乘法，需要约1024次32位乘法。现代CPU一次64位乘法大概几个时钟周期，所以总共几千个周期，还能接受。但如果密钥长度到4096位（128个字），就是16384次乘法，开始变得可观了。
这里有个容易忽略的细节：a[i] * b[j]是两个32位数相乘，结果最大是(2^32-1)^2 ≈ 2^64，刚好能用64位存下。但再加上r[i+j]和carry就可能溢出了。所以严格来说，(uint64_t)a[i] * b[j] + r[i+j] + carry的最大值是(2^32-1)^2 + (2^32-1) + (2^32-1) = 2^64 - 1，刚好不溢出。这是精心设计的边界，换任何一项都会溢出。
4.2 Karatsuba算法：什么时候值得用
Karatsuba算法是分治乘法的经典例子，把O(n²)降到O(n^1.585)。原理是把大数拆成高低两半，用三次半长乘法代替四次：
a = a1 * B + a0 b = b1 * B + b0 a * b = a1*b1 * B² + ((a1+a0)*(b1+b0) - a1*b1 - a0*b0) * B + a0*b0看起来多了一些加减法，但乘法次数从4次降到3次。当n足够大时，节省的乘法时间超过增加的加减法开销。
那"足够大"是多大？根据我的实测经验，在常见的x86-64平台上，阈值大约在16到32个字（即512到1024位）之间。低于这个长度，递归调用的开销和额外的加减法反而让Karatsuba更慢。高于这个长度，Karatsuba的优势逐渐显现。
| 字数n | Schoolbook乘法次数 | Karatsuba乘法次数 | 实测加速比 |
|---|---|---|---|
| 8 | 64 | 81（含递归开销） | 0.8x |
| 16 | 256 | 243 | 1.0x |
| 32 | 1024 | 729 | 1.3x |
| 64 | 4096 | 2187 | 1.7x |
| 128 | 16384 | 6561 | 2.2x |
实操心得：不要一上来就写Karatsuba。先用Schoolbook把功能跑通，确保正确性，然后再加Karatsuba作为优化。而且Karatsuba的递归实现容易在边界条件上出错，特别是当两个操作数长度不一致时。建议先补齐到相同长度（高位补零），再统一处理。
4.3 平方运算的特殊优化
在模幂运算中，平方的次数和乘法的次数差不多各占一半。平方运算有个特殊之处：a[i] * a[j]和a[j] * a[i]是相同的，可以只算一次然后乘2。
// 平方优化：利用对称性减少一半乘法 void bn_sqr(uint32_t *r, const uint32_t *a, size_t n) { memset(r, 0, 2 * n * sizeof(uint32_t)); // 先算对角线上的平方项 for (size_t i = 0; i < n; i++) { uint64_t prod = (uint64_t)a[i] * a[i]; // 加上之前的进位 uint64_t sum = prod + r[2*i]; r[2*i] = (uint32_t)(sum & 0xFFFFFFFF); r[2*i + 1] += (uint32_t)(sum >> 32); } // 再算交叉项，每个算一次乘2 for (size_t i = 0; i < n; i++) { uint64_t carry = 0; for (size_t j = i + 1; j < n; j++) { uint64_t prod = (uint64_t)a[i] * a[j]; // 乘2并加上目标位置已有的值 uint64_t sum = (prod << 1) + r[i+j] + carry; r[i+j] = (uint32_t)(sum & 0xFFFFFFFF); carry = sum >> 32; } r[i + n] += (uint32_t)carry; } }这个优化能省掉大约一半的乘法操作，在模幂这种平方密集的场景下效果很明显。不过实现起来比普通乘法更容易出错，特别是进位处理那块，建议写完后用随机测试和普通乘法对比验证。
5. 除法与取模：密码学实现中最容易翻车的部分
5.1 长除法：从高位到低位的逐位试商
多精度除法是四则运算中最复杂的。学校里的长除法是逐位试商，在多精度场景下，我们逐"字"试商。基本思路是：从被除数的最高位开始，每次取足够多的位（通常比除数多一个字），估算商的一位，然后减去除数乘以这一位商的积。
难点在于商位的估算。如果估大了，需要回退；估小了，需要补。经典的Knuth算法（《计算机程序设计艺术》第二卷）给出了一个精确的估算方法，用被除数的最高两个字和除数的最高一个字来估算商位，误差最多为1。
// 简化的除法核心：估算商位 // 假设 u 是被除数的高两位，v 是除数的最高位 uint32_t estimate_quotient(uint32_t u2, uint32_t u1, uint32_t u0, uint32_t v) { uint64_t numerator = ((uint64_t)u2 << 32) | u1; uint64_t q = numerator / v; // 修正：如果 q >= 2^32 或者 q*v 的高位部分大于 u2，则减小 q if (q >= 0x100000000ULL) { q = 0xFFFFFFFFULL; } // 用 q * v 和被除数的高位比较，必要时递减 q while (q * v > (((uint64_t)u2 << 32) | u1)) { q--; } return (uint32_t)q; }实际实现中，Knuth算法还需要处理除数只有一位的特殊情况（直接用每位除以除数），以及除数最高位太小时的归一化（把除数和被除数同时左移，使除数最高位>=2^31）。这些细节处理不好，就会出现商位估算错误，导致结果不对。
5.2 模约减的几种策略对比
在密码学中，我们很少做完整的除法，更多是做模约减——给定一个数x，求x mod m。根据x和m的关系，有几种策略：
策略一：条件减法。当x < 2m时，只需要判断x >= m，如果是就减一次m。这是模加和模减中用的方法，最简单最快。
策略二：Barrett约减。预先计算μ = floor(2^(2k) / m)（k是m的字数），然后用乘法和移位来估算商，再做修正。适合x远大于m的场景，比如模乘之后的结果。
策略三：Montgomery约减。把数转换到Montgomery域，在域内做模乘时不需要除法，只需要乘法和移位。特别适合模幂这种连续模乘的场景。代价是需要额外的域转换操作。
| 策略 | 适用场景 | 是否需要预计算 | 相对速度 |
|---|---|---|---|
| 条件减法 | x < 2m | 否 | 最快 |
| Barrett | x < m² | 是（μ） | 中等 |
| Montgomery | 连续模乘 | 是（R², m'） | 模幂中最快 |
注意：Barrett和Montgomery的预计算依赖于模数m。如果m经常变（比如每次加密都用不同的模数），预计算的开销可能抵消掉收益。在RSA中模数固定，预计算一次可以用很久，非常划算。
5.3 模逆运算：扩展欧几里得 vs 费马小定理
模逆是另一个高频操作，特别是在ECDSA签名和RSA密钥生成中。求a^(-1) mod m有两种常用方法：
扩展欧几里得算法（Extended GCD）：适用于任意模数，不要求m是素数。时间复杂度O(n²)。实现时需要处理有符号数，代码稍微复杂。
费马小定理：当m是素数时，a^(-1) = a^(m-2) mod m。这直接转化为模幂运算，可以复用已有的模幂函数。但模幂比扩展欧几里得慢不少（模幂是O(n³)级别），所以只在已经有快速模幂且不想额外实现GCD时使用。
// 扩展欧几里得求模逆（简化版，假设gcd(a,m)=1） int bn_mod_inverse(uint32_t *r, const uint32_t *a, const uint32_t *m, size_t n) { // 实现略复杂，需要处理有符号多精度运算 // 核心是维护 (old_r, r) = (a, m) 和 (old_s, s) = (1, 0) // 每轮做除法取余，更新系数 // 最终 old_r = gcd(a,m)，如果为1则 old_s 就是逆元 // ... return 0; // 成功返回0，无逆元返回-1 }实际工程中，如果模数是素数（ECC和DH中常见），且已经有常数时间的模幂实现，用费马小定理更省事。但要注意：费马小定理的模幂必须用常数时间实现，否则可能泄露密钥信息。
6. 模幂：密码学基本运算的"期末考试"
6.1 平方-乘法算法及其变体
模幂base^exp mod m是所有公钥密码算法的核心。最基础的算法是平方-乘法（Square-and-Multiply），也叫二进制幂法：
// 基础平方-乘法模幂（从左到右扫描指数位） void bn_mod_exp(uint32_t *r, const uint32_t *base, const uint32_t *exp, size_t explen, const uint32_t *m, size_t n) { uint32_t *tmp = malloc(2 * n * sizeof(uint32_t)); // 初始化结果为1 memset(r, 0, n * sizeof(uint32_t)); r[0] = 1; // 从指数最高位开始扫描 for (int i = explen * 32 - 1; i >= 0; i--) { // 平方 bn_mod_sqr(r, r, m, n); // 如果当前位是1，再乘base if ((exp[i / 32] >> (i % 32)) & 1) { bn_mod_mul(r, r, base, m, n); } } free(tmp); }这个算法对每个指数位做一次平方，对每个为1的位额外做一次乘法。平均来说，指数一半的位是1，所以总共约1.5n次模乘（n是指数位数）。
从左到右 vs 从右到左：从左到右扫描是上面这种写法，从右到左是另一种等价形式。从左到右的好处是只需要一个累加器，内存占用少；从右到左需要维护base的幂次，但可以做预计算优化。
6.2 窗口法：用空间换时间的经典操作
平方-乘法每次只看一位，窗口法一次看k位（窗口大小w），预计算base^0, base^1, ..., base^(2^w-1)，然后每次处理w位。这样乘法次数从约0.5n降到约n/w，代价是需要预计算和存储2^w个中间结果。
窗口大小w的选择是个权衡：w越大，乘法次数越少，但预计算和存储开销越大。根据经验：
| 窗口大小w | 预计算个数 | 每比特乘法次数 | 适用指数长度 |
|---|---|---|---|
| 1 | 1 | 0.5 | 任意 |
| 2 | 3 | 0.25 | > 64位 |
| 4 | 15 | 0.125 | > 256位 |
| 5 | 31 | 0.1 | > 512位 |
| 6 | 63 | 0.083 | > 1024位 |
对于RSA-2048的私钥指数（2048位），w=5或6比较合适。但要注意，预计算表的大小是2^w，w=6就是64个2048位数，内存占用约16KB，在嵌入式环境下可能偏大。
6.3 滑动窗口与蒙哥马利阶梯
滑动窗口是对固定窗口的改进：不要求窗口对齐，遇到连续的0就跳过，遇到1才开始取窗口。这样预计算表只需要存奇数幂（base^1, base^3, base^5, ...），表的大小减半。
蒙哥马利阶梯（Montgomery Ladder）是另一种模幂算法，它的特点是无论指数位是0还是1，每轮都做一次平方和一次乘法，只是乘的对象不同。这样做的好处是常数时间——运算模式不依赖指数位，能抵抗时序攻击。代价是比平方-乘法慢约33%（因为0位也要做乘法）。
// 蒙哥马利阶梯（简化示意） void bn_mod_exp_ladder(uint32_t *r, const uint32_t *base, const uint32_t *exp, size_t explen, const uint32_t *m, size_t n) { uint32_t *R0 = malloc(n * sizeof(uint32_t)); uint32_t *R1 = malloc(n * sizeof(uint32_t)); // R0 = 1, R1 = base memset(R0, 0, n * sizeof(uint32_t)); R0[0] = 1; memcpy(R1, base, n * sizeof(uint32_t)); for (int i = explen * 32 - 1; i >= 0; i--) { if ((exp[i / 32] >> (i % 32)) & 1) { bn_mod_mul(R0, R0, R1, m, n); // R0 = R0 * R1 bn_mod_sqr(R1, R1, m, n); // R1 = R1² } else { bn_mod_mul(R1, R0, R1, m, n); // R1 = R0 * R1 bn_mod_sqr(R0, R0, m, n); // R0 = R0² } } memcpy(r, R0, n * sizeof(uint32_t)); free(R0); free(R1); }实操心得：如果你的模幂实现要用于处理私钥（比如RSA解密或签名），强烈建议用蒙哥马利阶梯或至少做指数盲化。普通的平方-乘法会因为指数中0和1的分布不同而产生不同的运算时间，攻击者通过精确测量时间就能推断出私钥指数的信息。这不是危言耸听，是已经被实际验证过的攻击方式。
7. 那些文档里不会写的踩坑记录
7.1 内存对齐与性能的隐性关系
多精度运算的性能对内存对齐非常敏感。现代CPU从内存读数据是按缓存行（通常64字节）来的，如果一个多精度数的起始地址没有对齐到8字节或16字节边界，每次读取都可能跨越缓存行，导致性能下降。
我在一个ARM Cortex-M4的项目上实测过：同样的2048位模乘代码，用malloc分配的内存（通常8字节对齐）比用__attribute__((aligned(16)))声明的静态数组慢了约15%。原因就是对齐后的数据访问更高效。
建议：如果性能敏感，用aligned_alloc或平台特定的对齐分配函数，确保多精度数的起始地址至少对齐到16字节。对于栈上数组，可以用_Alignas(16)（C11）或编译器扩展来指定对齐。
7.2 编译器优化带来的"意外"
C编译器在优化时可能会做一些你意想不到的事情。比如，你写了一个"常数时间"的条件赋值：
// 意图：常数时间选择，不产生分支 uint32_t mask = -(uint32_t)(a > b); r = (a & mask) | (b & ~mask);但编译器可能把它优化成一个条件分支，因为分支预测在现代CPU上通常比位运算快。这就破坏了常数时间的特性。
另一个常见问题是编译器把memset优化掉。如果你用memset清零一个临时缓冲区来存放敏感数据，编译器可能认为这个缓冲区之后不再使用，直接把memset删掉。结果敏感数据留在内存里，可能被后续分配利用。
注意：处理敏感数据时，用
volatile指针或平台提供的内存擦除函数（如explicit_bzero）来防止编译器优化。这不是偏执，是密码学实现的基本要求。
7.3 测试用例的设计：随机测试远远不够
很多人写完基本运算函数后，用随机数测几组就认为没问题了。但密码学运算的bug往往出现在边界条件上：
- 所有字都是0xFFFFFFFF的加法（测试进位链）
- 高位为0但低位非0的减法（测试借位传播）
- 操作数长度不一致的乘法和除法
- 模数最高位为0或1的模约减（测试归一化逻辑）
- 指数为0、1、2的模幂（测试边界）
我的做法是：除了随机测试，还要构造一组定向测试用例，覆盖上述所有边界。然后用Python的int类型作为参考实现，对每组输入对比结果。Python的任意精度整数是经过充分验证的，作为参考基准很可靠。
# 用Python验证C实现的正确性（示意） import random def test_bn_add(c_bn_add, iterations=10000): for _ in range(iterations): a = random.getrandbits(2048) b = random.getrandbits(2048) expected = (a + b) & ((1 << 2048) - 1) # 截断到2048位 carry_expected = 1 if a + b >= (1 << 2048) else 0 result, carry = c_bn_add(a, b) assert result == expected, f"加法结果错误: {a} + {b}" assert carry == carry_expected, f"进位错误: {a} + {b}"这种交叉验证的方法能发现绝大多数逻辑错误。而且Python脚本写起来快，改起来也快，比在C里调试高效得多。
7.4 从"能算对"到"算得快"的优化路径
基本运算函数写对之后，下一步就是优化。但优化要有章可循，不能瞎改。我的经验是按以下顺序：
- 先测基线：用
perf或clock_gettime测出每个函数的耗时，找出瓶颈。通常模幂占了大头，而模幂中模乘又是核心。 - 优化模乘：模乘的优化空间最大。可以尝试Montgomery约减、Karatsuba乘法、延迟约减（允许中间结果略大于模数，减少约减次数）。
- 优化模幂：换用窗口法或滑动窗口，调整窗口大小。
- 底层优化：用内联汇编或编译器内建函数（如
__builtin_addcll）来优化进位处理。但这会牺牲可移植性，慎用。
每一步优化后都要重新跑正确性测试，确保没有引入bug。性能优化和正确性之间的平衡，是密码学实现中最考验功力的地方。
8. 写给自己和同行的一些话
回过头看，密码学C/C++实现中的基本运算函数，表面上是一堆加加减减乘乘除除，但每一个细节背后都有它的道理。进位为什么要那样处理，模约减为什么要分那么多种策略，模幂为什么要考虑常数时间——这些都不是凭空设计的，而是在正确性、性能、安全性三者之间反复权衡的结果。
我自己在这个领域踩过的坑，比这篇文章里写的要多得多。有些是逻辑错误，调试了好几天才发现是一个进位没处理；有些是性能问题，优化了半天发现瓶颈在内存分配而不是算法；还有些是安全问题，写完才发现时序泄露。每一次踩坑都是一次学习，也让我对那些成熟的密码学库多了一份敬意——它们能同时做到正确、快速、安全，背后是无数人的心血。
如果你也在学习或实现密码学基本运算，我的建议是：不要怕慢，先把正确性做扎实。用Python做参考实现，用大量边界测试用例验证，确保每一步都经得起推敲。然后再考虑性能优化，而且每次优化都要有数据支撑，不要凭感觉。最后，如果是要用于生产环境，请务必使用经过审计的库，自己实现的版本可以作为学习参考，但不要轻易用于保护真实数据。
这个领域还有很多值得深入的方向：椭圆曲线上的点运算、配对运算、后量子密码的格运算等等。基本运算函数是这一切的基础，把基础打牢，后面的路会好走很多。
