加法进位

先看0xFF + 0xFF应该等于多少，多少个字节能表示，0xFF为一字节，一字节能表示的最大数，两个这样的数相加的结果为0x1FE，进一位。

同理4字节能表示的最大数是0xFFFFFFFF，两个这样的数相加为0x1FFFFFFFE，uint64_t完全可以表示，并且心可以放进肚子，完全不会溢出。

也就是说8个uint64_t所表示的256-bit大数，执行一次加法，完全不用担心会溢出，不用考虑循环多次加法，因为素域的加法，无论加多少次，结果都不会超过该域。

大数加法

大数的加法实现比较简单，就是8个数循环相加，并且处理进位即可。从数组索引0开始，因为0存放的是大数的低位。

函数定义

// r = a + b
static void gm_i_bn_add(gm_bn_t r, const gm_bn_t a, const gm_bn_t b);

先看第一轮：

r[0] = a[0] + b[0];

有可能会产生进位，也有可能不会产生进位，那么下一轮相加时，应该要加上前一轮可能产生的进位，同时要将前一轮的进位清除掉。

r[1] = a[1] + b[1] + 进位;
清除进位

进位应该怎么算呢，uint64_t，高32比特存放的就是进位值，清除进位就是把高32比特清零：

r[1] = a[1] + b[1] + (r[0] >> 32);
r[0] &= 0x0FFFFFFFFULL;

转换为循环：

for(i = x; i < 8; i++) {
	r[i] = a[i] + b[i] + (r[i-1] >> 32); // 会溢出吗？
	r[i-1] &= 0x0FFFFFFFFULL;
}

显然i应该从1开始，第1轮并不需要处理进位，所以最终实现为：

static void gm_i_bn_add(gm_bn_t r, const gm_bn_t a, const gm_bn_t b) {
    int i;
    r[0] = a[0] + b[0];
    for(i = 1; i < 8; i++) {
        r[i] = a[i] + b[i] + (r[i - 1] >> 32);
        r[i - 1] &= 0x0FFFFFFFFULL;
    }
}

这里循环结果r[i]是不可能会溢出的，另外也注意到，最后一轮r[7]的进位是保存在高字节，未处理的，这个不影响模加、模减结果，因为取模过程中，最终不会产生进位的。

模加

定义及实现

// r = (a + b) mod m
void gm_bn_add(gm_bn_t r, const gm_bn_t a, const gm_bn_t b, const gm_bn_t m) {
    gm_i_bn_add(r, a, b);
    if(gm_bn_cmp(r, m) >= 0) {
        gm_i_bn_sub(r, r, m);
    }
}

其中gm_i_bn_add为我们刚刚实现的大数加法，gm_i_bn_sub为下一章节需要实现的大数减法，先不用关注如何实现，先看看原理

a + b的结果存放在r当中，r是的值是有可能超过m的，所以执行完加法后，只要r >= m，都减掉一个m，就是模加的结果了，如果没有超过就不用减了。

因为a和b都是小于m的大数，所以他们相加肯定小于m+m的，所以只需要减一次即可。

有了这些，我们就可以先约定gm_i_bn_sub中的参数，a必须大于b，那么a-b就不用考虑借位问题，接下来的实现就简单多了。