/*
  Author:  Pate Williams (c) 1997

  Extended binary Euclid algorithm. See "Handbook
  of Applied Cryptography" by Alfred J. Menezes et
  al Section 14.4.3 pages 608 - 610.
*/

#include <stdio.h>
#include "lip.h"

#define DEBUG

void zbinary_ext_gcd(verylong zx, verylong zy,
                     verylong *za, verylong *zb,
                     verylong *zv)
/* returns a * x + b * y = v, v = gcd(x, y) */
{
  verylong zA = 0, zB = 0, zC = 0, zD = 0;
  verylong zX = 0, zY = 0, zc = 0,  zg = 0;
  verylong zu = 0;

  zone(&zg);
  zcopy(zx, &zX);
  zcopy(zy, &zY);
  while (!zodd(zX) && !zodd(zY)) {
    zrshift(zX, 1l, &zc);
    zcopy(zc, &zX);
    zrshift(zY, 1l, &zc);
    zcopy(zc, &zY);
    zlshift(zg, 1l, &zc);
    zcopy(zc, &zg);
  }
  zcopy(zX, &zu);
  zcopy(zY, zv);
  zone(&zA);
  zzero(&zB);
  zzero(&zC);
  zone(&zD);
  do {
    while (!zodd(zu)) {
      zrshift(zu, 1l, &zc);
      zcopy(zc, &zu);
      if (!zodd(zA) && !zodd(zB)) {
        zrshift(zA, 1l, &zc);
        zcopy(zc, &zA);
        zrshift(zB, 1l, &zc);
        zcopy(zc, &zB);
      }
      else {
        zadd(zA, zY, &zc);
        zrshift(zc, 1l, &zA);
        zsub(zB, zX, &zc);
        zrshift(zc, 1l, &zB);
      }
    }
    while (!zodd(*zv)) {
      zrshift(*zv, 1l, &zc);
      zcopy(zc, zv);
      if (!zodd(zC) && !zodd(zD)) {
        zrshift(zC, 1l, &zc);
        zcopy(zc, &zC);
        zrshift(zD, 1l, &zc);
        zcopy(zc, &zD);
      }
      else {
        zadd(zC, zY, &zc);
        zrshift(zc, 1l, &zC);
        zsub(zD, zX, &zc);
        zrshift(zc, 1l, &zD);
      }
    }
    if (zcompare(zu, *zv) >= 0) {
      zsub(zu, *zv, &zc);
      zcopy(zc, &zu);
      zsub(zA, zC, &zc);
      zcopy(zc, &zA);
      zsub(zB, zD, &zc);
      zcopy(zc, &zB);
    }
    else {
      zsub(*zv, zu, &zc);
      zcopy(zc, zv);
      zsub(zC, zA, &zc);
      zcopy(zc, &zC);
      zsub(zD, zB, &zc);
      zcopy(zc, &zD);
    }
    #ifdef DEBUG
    zwrite(zu); printf(" ");
    zwrite(*zv); printf(" ");
    zwrite(zA); printf(" ");
    zwrite(zB); printf(" ");
    zwrite(zC); printf(" ");
    zwriteln(zD);
    #endif
  } while (zscompare(zu, 0l) != 0);
  zcopy(zC, za);
  zcopy(zD, zb);
  zmul(zg, *zv, &zc);
  zcopy(zc, zv);
  zfree(&zA);
  zfree(&zB);
  zfree(&zC);
  zfree(&zD);
  zfree(&zX);
  zfree(&zY);
  zfree(&zc);
  zfree(&zg);
  zfree(&zu);
}

int main(void)
{
  verylong za = 0, zb = 0, zv = 0, zx = 0, zy = 0;

  zintoz(693l, &zx);
  zintoz(609l, &zy);
  zbinary_ext_gcd(zx, zy, &za, &zb, &zv);
  printf("a = "); zwriteln(za);
  printf("b = "); zwriteln(zb);
  printf("v = "); zwriteln(zv);
  zfree(&za);
  zfree(&zb);
  zfree(&zv);
  zfree(&zx);
  zfree(&zy);
  return 0;
}