mpz_powm_ui(...) is MUCH slower than mpz_powm(...)
Paul.Zimmermann at loria.fr
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