3 ms·
Yeah, sorry, there are extra steps here. If n= 43112609 and you have some 2n-bit number to reduce, you can split it into two n-bit words and simply add the wor
by blintz 6y ago
Yeah, sorry, there are extra steps here. If n=
43112609 and you have some 2n-bit number to reduce, you can split it into two n-bit words and simply add the words together, since 1 = 2^n (mod 2^n - 1). You can do this very quickly (ie you can add an arbitrary number of 2n
-bit values together with only a small number of adds and shifts as overhead).
- mlyle 6y agoYah-- as mentioned-- just like we can find the residue mod 9 by adding digits up in base 10. There's notably also the all 1's case to deal with as an exception.