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 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