"Marco Bodrato" <bodr...@mail.dm.unipi.it> writes: > r0 comes from sqr+redc. > So, if I understood correctly, it has at most as many bits as m0, but may > be r0 >= m0.
Depends on the details... Say we start with r in canonical representation, 0 <= r < m. Then we want to compute r' = r^2 / B (mod m). Redc can be done either additively or subtractively. In either variant, we compute a full-limb 2-adic quotient q = ± r^2 m^{-1} (mod B). Additive redc: r' = (r^2 + q m) / B < m^2 / B + m This can be larger than m. And if m is close below a power of 2, it can also be one bit larger than m. And if m is close to B, it could even overflow, which needs checking for. To me, it seems a bit tricky to repeat this squaring without reduction to canonical representation. For small enough m we can probably arrange so that r, r', r'', r''', ..., all stay < 2m or so. But as m gets closer to B, that seems difficult. Subtractive redc: r' = (r^2 - qm) / B, -m < r' < m^2 / B This can obviously underflow, and if we check for that and add back m, we get canonical representation, 0 <= r' < m. A subtle advantage of subtractive redc is that in the double-limb subtraction r^2 - qm, the low limb always cancel, with no borrow, so we only need to subtract the high libms. While for additive redc, the addition r^2 + qm always gives a zero low limb, and *almost* always gives a carry out from the low limb addition. Except if r^2 mod B = 0, in which case also q = 0. So if it happens that r = 0 (mod 2^k), with k >= GMP_LIMB_BITS/2, there's no carry out. So we either need to do the low half of the addition, just to get the correct carry, or check for the r^2 = 0 (mod B) case in some other way. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677. Internet email is subject to wholesale government surveillance. _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel