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

Zimmermann Paul Paul.Zimmermann at
Mon Nov 5 17:50:50 CET 2012

> Deeper hacking is needed to make things ideal.  See
> <>.

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.


More information about the gmp-bugs mailing list