Side-channel silent modular inverse

Niels Möller nisse at
Fri Dec 27 19:58:59 UTC 2013

Torbjorn Granlund <tg at> writes:

> I suppose I already suggested that one computes a^{-1} mod b
> as a^{b-1} mod b, using a plain old modexp.

For prime b (which is an important special case).

> I realise that this will be asymptotically slower, in this setting
> O(n^3) vs O(n^2), but it ought have a much lower constant factor.

I think powm actually was slower when I tried, for the sizes of a few
limbs which were relevant for ecdsa, but I'm not sure. Some benchmarking
is needed.


Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.

More information about the gmp-devel mailing list