1 #include "os.h"
2 #include <mp.h>
3
4 // extended euclid
5 //
6 // For a and b it solves, d = gcd(a,b) and finds x and y s.t.
7 // ax + by = d
8 //
9 // Handbook of Applied Cryptography, Menezes et al, 1997, pg 67
10
11 void
mpeuclid(mpint * a,mpint * b,mpint * d,mpint * x,mpint * y)12 mpeuclid(mpint *a, mpint *b, mpint *d, mpint *x, mpint *y)
13 {
14 mpint *tmp, *x0, *x1, *x2, *y0, *y1, *y2, *q, *r;
15
16 if(mpcmp(a, b) < 0){
17 tmp = a;
18 a = b;
19 b = tmp;
20 tmp = x;
21 x = y;
22 y = tmp;
23 }
24
25 if(b->top == 0){
26 mpassign(a, d);
27 mpassign(mpone, x);
28 mpassign(mpzero, y);
29 return;
30 }
31
32 a = mpcopy(a);
33 b = mpcopy(b);
34 x0 = mpnew(0);
35 x1 = mpcopy(mpzero);
36 x2 = mpcopy(mpone);
37 y0 = mpnew(0);
38 y1 = mpcopy(mpone);
39 y2 = mpcopy(mpzero);
40 q = mpnew(0);
41 r = mpnew(0);
42
43 while(b->top != 0 && b->sign > 0){
44 // q = a/b
45 // r = a mod b
46 mpdiv(a, b, q, r);
47 // x0 = x2 - qx1
48 mpmul(q, x1, x0);
49 mpsub(x2, x0, x0);
50 // y0 = y2 - qy1
51 mpmul(q, y1, y0);
52 mpsub(y2, y0, y0);
53 // rotate values
54 tmp = a;
55 a = b;
56 b = r;
57 r = tmp;
58 tmp = x2;
59 x2 = x1;
60 x1 = x0;
61 x0 = tmp;
62 tmp = y2;
63 y2 = y1;
64 y1 = y0;
65 y0 = tmp;
66 }
67
68 mpassign(a, d);
69 mpassign(x2, x);
70 mpassign(y2, y);
71
72 mpfree(x0);
73 mpfree(x1);
74 mpfree(x2);
75 mpfree(y0);
76 mpfree(y1);
77 mpfree(y2);
78 mpfree(q);
79 mpfree(r);
80 mpfree(a);
81 mpfree(b);
82 }
83