mpz_powm_ui(...) is MUCH slower than mpz_powm(...)

[Zimmermann Paul]

       Torbjörn,
       
> Deeper hacking is needed to make things ideal.  See
> <http://gmplib.org/devel/>.

I don't think the proposed algorithm is optimal. In the final loop, using
the REDC representation for multiplying by b will need *full* modular
multiplies (since b' will be in general of the same size as m).

You should keep b small when it is, and thus replace r' <- REDC(r' * b', m)
by r' <- (r' * b) mod m. When b has only one word, this will only perform
one n * 1 -> n+1 multiplication, and one (n+1) / n division, which are cheap.

Paul