pd.if.org Git - zpackage/blob - tomsfastmath/src/numtheory/fp_gcd.c

   1 /* TomsFastMath, a fast ISO C bignum library.
   2  *
   3  * This project is meant to fill in where LibTomMath
   4  * falls short.  That is speed ;-)
   5  *
   6  * This project is public domain and free for all purposes.
   7  *
   8  * Tom St Denis, tomstdenis@gmail.com
   9  */
  10 #include <tfm_private.h>
  11
  12 /* c = (a, b) */
  13 void fp_gcd(fp_int *a, fp_int *b, fp_int *c)
  14 {
  15    fp_int u, v, r;
  16
  17    /* either zero than gcd is the largest */
  18    if (fp_iszero (a) == 1 && fp_iszero (b) == 0) {
  19      fp_abs (b, c);
  20      return;
  21    }
  22    if (fp_iszero (a) == 0 && fp_iszero (b) == 1) {
  23      fp_abs (a, c);
  24      return;
  25    }
  26
  27    /* optimized.  At this point if a == 0 then
  28     * b must equal zero too
  29     */
  30    if (fp_iszero (a) == 1) {
  31      fp_zero(c);
  32      return;
  33    }
  34
  35    /* sort inputs */
  36    if (fp_cmp_mag(a, b) != FP_LT) {
  37       fp_init_copy(&u, a);
  38       fp_init_copy(&v, b);
  39    } else {
  40       fp_init_copy(&u, b);
  41       fp_init_copy(&v, a);
  42    }
  43
  44    fp_zero(&r);
  45    while (fp_iszero(&v) == FP_NO) {
  46       fp_mod(&u, &v, &r);
  47       fp_copy(&v, &u);
  48       fp_copy(&r, &v);
  49    }
  50    fp_copy(&u, c);
  51 }
  52
  53 /* $Source$ */
  54 /* $Revision$ */
  55 /* $Date$ */