Fast constant-time gcd computation and modular inversion

Torbjörn Granlund tg at
Wed Aug 31 19:58:48 CEST 2022

  Much more unclear to me how close it might be to the typical or average
  number of iterations needed.

That's perhaps not very interesting, as early exit is not an option
here.  (Unless this algorithm would beat plain, "leaky" inverse.)

  Currently uses exponentiation for the field inverse, and nettle's
  version of sec_invert for inverses mod the group order, as needed by
  ecdsa. Except for the somewhat obscure gost curves (Russian standards),
  where sec_invert is used for all inverses, and A/B for gost-gc512a is
  almost 30%.

Why do you use sec_invert when inverting mod the group order when that
is of prime order?  (Yes, this question will become moot I suppose with
this new algorithm.

Please encrypt, key id 0xC8601622

More information about the gmp-devel mailing list