Quote from: NotATether on Today at 12:26:22 PM

That shouldn't incur much overhead, in fact we might be able to do it with 4 lines of code for each occurrence:

Code:

// I think we just discard the carry from the previous mod reduce
UADDO(r[0],r[0],0x0000000F000003D1ULL); // 2**32 + 977
UADDC(r[1],r[1],0);
UADDC(r[2],r[2],0);
UADDC(r[3],r[3],0);
// And this carry too

I *think* we are keeping everything mod 256 bits so the highest carries can just be discarded. Or maybe it's actually mod N and it's making assurances above that the product is always less than N.

3rd reduction ensures it would be impossible to have a carry at limb 5. But I don't agree with "we might be able to do it with 4 lines of code" because it must be a conditional 3rd addition:

If no carry after 2nd reduction = all good;
else add "r".

But to check the carry we must do an addition with 0, so we have 5 operations.

This is equivalent to always perform the 3rd reduction (it would either add 0 or r) but avoids the multiplications, since the multiply factor would either be 0 or 1.