1*8ccd4a63SDavid du Colombier #include "os.h"
2*8ccd4a63SDavid du Colombier #include <mp.h>
3*8ccd4a63SDavid du Colombier
4*8ccd4a63SDavid du Colombier #define iseven(a) (((a)->p[0] & 1) == 0)
5*8ccd4a63SDavid du Colombier
6*8ccd4a63SDavid du Colombier // use extended gcd to find the multiplicative inverse
7*8ccd4a63SDavid du Colombier // res = b**-1 mod m
8*8ccd4a63SDavid du Colombier void
mpinvert(mpint * b,mpint * m,mpint * res)9*8ccd4a63SDavid du Colombier mpinvert(mpint *b, mpint *m, mpint *res)
10*8ccd4a63SDavid du Colombier {
11*8ccd4a63SDavid du Colombier mpint *dc1, *dc2; // don't care
12*8ccd4a63SDavid du Colombier
13*8ccd4a63SDavid du Colombier dc1 = mpnew(0);
14*8ccd4a63SDavid du Colombier dc2 = mpnew(0);
15*8ccd4a63SDavid du Colombier mpextendedgcd(b, m, dc1, res, dc2);
16*8ccd4a63SDavid du Colombier if(mpcmp(dc1, mpone) != 0)
17*8ccd4a63SDavid du Colombier abort();
18*8ccd4a63SDavid du Colombier mpmod(res, m, res);
19*8ccd4a63SDavid du Colombier mpfree(dc1);
20*8ccd4a63SDavid du Colombier mpfree(dc2);
21*8ccd4a63SDavid du Colombier }
22