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