Computing (g**u)*(h**v) mod n with Shamir's trick

Francois Grieu fgrieu at gmail.com
Thu Apr 8 15:39:07 UTC 2021


I'd like to efficiently compute
  (g**u)*(h**v) mod n
where positive integers g, h, n are say 3072-bit, and u, v are say 256-bit. In
the context (DSA or Schnorr signature verification) it is NOT useful to have
constant-time execution.

The naive method would use two mpz_powm, then mpz_mul and mpz_mod. I'm after a
speed improvement using "Shamir's trick". In it's simplest form, it pre-computes
  gh = g*h mod n
then performs left-to-right binary exponentiation, alternating modular squaring
and (depending on a bit in each of u and v) modular multiplication by gh, g, h,
or nothing. There is a very significant speedup, since the number of squaring is
about halved, and the number of multiplications is reduced by about 1/4 compared
to basic modular exponentiation. Further optimizations are possible with a
sliding window.

I have not seen this in GMP 6.2.1. Did I miss it? Or is there recommendable open
source code doing this on top of GMP?
TIA,
  François Grieu


More information about the gmp-discuss mailing list