Better b^e mod m

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> (1) Tiny exponents such as 2, 3.

If we're to do special cases for small e, maybe it might make sense to
find optimal addition chains for small e. Not sure for which e this could
make a significant difference, though.

> (2) Bases that are much smaller than the mod argument.

> When the intermediate result operand becomes >= m, we
> decide whether to, for the remainder of the exponentiation, go into
> Montgomery repr to allow for Hensel division or stay Euclidean.  We
> should do the latter only if we're basically done.

I think we can accumulate and square in Montgomery representation,
without necessarily converting b to Montgomery.

Notation: Put x' = x B^n mod m, i.e., x' is the Montgomery
representation of x.

Do squarings the usual Montgomery way:

  (x^2)' = (x')^2 B^{-n} (mod m).

But when we multiply by b, we can do that with a plain multiplication
by b followed by an *Euclidean* reduction of a single limb

  (x b)' = x' b (mod m)

Since b is much smaller than b', I think that's going to be a win over
Montgomery, even for fairly small n.

And when we tabulate powers of b, we should do the same with powers
which fit in a single limb or just a few limbs.

(I've also been considering if we could also use single-limb hensel
reduction, doing b multiplies as

  (x' b) B^{-1}

Then we get a factor of B error (which is going to be amplified while
squaring). Let's say the accumulated error is the factor B^{-k}, then
after processing all exponent bits we get

  (x^e)' B^{-k} = x^e B^{n-k} (mod m)

and to get back from Montgomery to plain representation we need to
divide by B^{n-k} (mod m). So in the case that k <= n (small number of
exponent bits), we actually reduce the amount of work needed when
returning from montgomery to plain representation! And in case k > n, we
need to do Euclidean reductions rather than redc, so then this idea is
probably not very useful).

> For (3) we could reduce e mod |m*|, the order of the underlying
> multiplicative group...  We should not walk down that path, I think,
> even if we could of course factor small m quickly.

I agree that should be left to the caller, who, e.g., may know that m is
prime.

And in general, if m has a known factorization, one should use that
knowledge not only to reduce the exponent, but do the powering mod each
factor and combine using the chinese remainder theorem.

Hmm, maybe it would make some sense with a powm function which takes a prime
factorization of m as an additional argument?

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.