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