bingcd.c

《应用密码学》一书源代码

/*
  Author:  Pate Williams (c) 1997

  14.54 Algorithm Binary gcd algorithm
  See "Handbook of Applied Cryptography" by Alfred
  J. Menezes et al page 606.
*/

#include <math.h>
#include <stdio.h>

#define DEBUG

long binary_gcd(long x, long y)
{
  long g = 1, t;
  #ifdef DEBUG
  printf("-----------\n");
  printf(" x   y   g\n");
  printf("-----------\n");
  #endif
  while (!(x & 1) && !(y & 1))
    x >>= 1, y >>= 1, g <<= 1;
  while (x != 0) {
    while (!(x & 1)) x >>= 1;
    while (!(y & 1)) y >>= 1;
    t = labs(x - y) >> 1;
    if (x >= y) x = t; else y = t;
    #ifdef DEBUG
    printf("%3ld %3ld %3ld\n", x, y, g);
    #endif
  }
  #ifdef DEBUG
  printf("-----------\n");
  #endif
  return g * y;
}

int main(void)
{
  long x = 1764, y = 868;

  printf("x = %ld y = %ld\n", x, y);
  printf("gcd(x, y) = %ld\n", binary_gcd(x, y));
  return 0;
}