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

[Paul Zimmermann]

       Hi François,

as far as I know, this is not implemented in GMP. However, if you implement it
at the mpz level, not sure you get the speedup you would expect, since mpz_powm
uses several tricks: Montgomery multiplication, sliding window exponentiation.

Being faster than GMP is always a challenge.

Paul Zimmermann

> From: Francois Grieu <fgrieu at gmail.com>
> Date: Thu, 8 Apr 2021 17:39:07 +0200
> 
> 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
> _______________________________________________
> gmp-discuss mailing list
> gmp-discuss at gmplib.org
> https://gmplib.org/mailman/listinfo/gmp-discuss