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

[Torbjörn Granlund]

Francois Grieu <fgrieu at gmail.com> writes:

  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.

Neat idea.

I am not sure k-ary would be as useful here as for plain modular
exponentiation.  If I am not mistaken, for a k-ary exponentiation one
would need a table of size 4^k as opposed to 2^k for the plain
exponentiation case.  That quickly becomes expensive in terms of memory
but also in terms of (pre-) computation.

Furthermore, k-ary with sliding window would not slide as much as in the
plain case as the expected zero runs would be much shorter.  That is so
because u OR v will not typically have many long zero runs.

These observations do not mean that the Shamir trick in its basic form
is not useful.  But it means that the speedup might be slightly less
than expected.

-- 
Torbjörn
Please encrypt, key id 0xC8601622