C 中的多精度无符号减法

Question

我正在尝试在 C 中的有限域 (p=2^191-19) 上实现多精度无符号减法，但我无法弄清楚如何处理借用位！ 我的操作数以基数-2^16 表示为：

typedef unsigned long long T[12];

这意味着 T 型数组的每个元素都有恰好 16 位的数据(基数-2^16 表示)。 现在我想减去两个T类型的操作数，但我不知道哪个更小！如果结果为负数，我想将结果添加到素数值，以便在模算术中获得正结果。 这是我基于本书第30页(多精度减法算法)的实现：

void bigint192_sub(T r, const T a, const T b){
int i;
int borrow;
r[0] = a[0] - b[0];
borrow = r[0] >> 16;
r[0] &= 0xFFFF;
for(i=1;i<12;++i){
r[i] = a[i] - b[i] - borrow;
borrow = r[i] >> 16;
r[i] &= 0xFFFF;
}
}

但我得到了错误的答案！

My inputs:
a =0x2d7e33e5bba0f6bb87ce04b28e940662db8f3f81aaf94576
b =0x28afc585dca4a8003b081f7289de11c2d229d5a967081f72
Myresult=0x4d16e62defd4ebc4cc8e54104b7f4a0096769d843f12604
Crresult=0x4ce6e5fdefc4ebb4cc5e54004b5f4a0096569d843f12604

Answer 1

您应该修复borrow评估，因为它可能只有0或1。因此，您应该将下溢视为borrow等于1：

borrow = (r[i] >> 16) != 0;

此外，我会以更通用的形式重写函数，因为我们可能会将第一遍视为没有借用：

void bigint192_sub(T r, const T a, const T b){
int i;
int borrow;
for (borrow = 0, i = 0; i < 12; ++i) {
r[i] = a[i] - b[i] - borrow;
borrow = (r[i] >> 16) != 0;
r[i] &= 0xFFFF;
}
}