_basecase or _sec? [

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> I see the need of the following:
>
>   function
>   --------
>   mul
>   gcdext
>   add, sub

mod (div_r_sec) is more important than general division. And modular
inverse is more important than general gcdext.

I've also seen some need for add_1/sub_1.

Modular inverse is a bit tricky, I have an implementation (at
http://git.lysator.liu.se/nettle/nettle/blobs/master/sec-modinv.c) which
is some 50 time slower than mpn_gcdext. As far as I'm aware, this is a
"novel" algorithm. I think it could be extended to return the gcd and/or
a success/fail indication without leaking.

Regards,
/Niels

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