blob: 712db1706b322d1ffe93fa443b935a1354bbd4bb [file] [log] [blame]
#include "os.h"
#include <mp.h>
#define iseven(a) (((a)->p[0] & 1) == 0)
/* extended binary gcd */
/* */
/* For a anv b it solves, v = gcd(a,b) and finds x and y s.t. */
/* ax + by = v */
/* */
/* Handbook of Applied Cryptography, Menezes et al, 1997, pg 608. */
void
mpextendedgcd(mpint *a, mpint *b, mpint *v, mpint *x, mpint *y)
{
mpint *u, *A, *B, *C, *D;
int g;
if(a->sign < 0 || b->sign < 0){
mpassign(mpzero, v);
mpassign(mpzero, y);
mpassign(mpzero, x);
return;
}
if(a->top == 0){
mpassign(b, v);
mpassign(mpone, y);
mpassign(mpzero, x);
return;
}
if(b->top == 0){
mpassign(a, v);
mpassign(mpone, x);
mpassign(mpzero, y);
return;
}
g = 0;
a = mpcopy(a);
b = mpcopy(b);
while(iseven(a) && iseven(b)){
mpright(a, 1, a);
mpright(b, 1, b);
g++;
}
u = mpcopy(a);
mpassign(b, v);
A = mpcopy(mpone);
B = mpcopy(mpzero);
C = mpcopy(mpzero);
D = mpcopy(mpone);
for(;;) {
/* print("%B %B %B %B %B %B\n", u, v, A, B, C, D); */
while(iseven(u)){
mpright(u, 1, u);
if(!iseven(A) || !iseven(B)) {
mpadd(A, b, A);
mpsub(B, a, B);
}
mpright(A, 1, A);
mpright(B, 1, B);
}
/* print("%B %B %B %B %B %B\n", u, v, A, B, C, D); */
while(iseven(v)){
mpright(v, 1, v);
if(!iseven(C) || !iseven(D)) {
mpadd(C, b, C);
mpsub(D, a, D);
}
mpright(C, 1, C);
mpright(D, 1, D);
}
/* print("%B %B %B %B %B %B\n", u, v, A, B, C, D); */
if(mpcmp(u, v) >= 0){
mpsub(u, v, u);
mpsub(A, C, A);
mpsub(B, D, B);
} else {
mpsub(v, u, v);
mpsub(C, A, C);
mpsub(D, B, D);
}
if(u->top == 0)
break;
}
mpassign(C, x);
mpassign(D, y);
mpleft(v, g, v);
mpfree(A);
mpfree(B);
mpfree(C);
mpfree(D);
mpfree(u);
mpfree(a);
mpfree(b);
return;
}