Small-base modexp

[Niels Möller]

"Marco Bodrato" <bodrato at 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.