Side-channel silent modular inverse

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> 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.

Regards,
/Niels

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