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