Fast constant-time gcd computation and modular inversion

Niels Möller nisse at
Thu Sep 1 07:51:26 CEST 2022

Torbjörn Granlund <tg at> writes:

> 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.

No good reason, it's just that I implemented inverse-by-powering (with a
hand-tuned addition chain) as a side effect of implementing square root,
since in some cases they can share much of the addition chain, and that
work touched field prime arithmetic only.

Sorry we're getting a bit off topic, we should take nettle discussion


Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.

More information about the gmp-devel mailing list