pb_gcd.c

   1 /* LibTomPoly, Polynomial Basis Math -- Tom St Denis
   2  *
   3  * LibTomPoly is a public domain library that provides
   4  * polynomial basis arithmetic support.  It relies on
   5  * LibTomMath for large integer support.
   6  *
   7  * This library is free for all purposes without any
   8  * express guarantee that it works.
   9  *
  10  * Tom St Denis, tomstdenis@iahu.ca, http://poly.libtomcrypt.org
  11  */
  12 #include <tompoly.h>
  13
  14 /* returns the monic GCD only for GF(p^k)[x] */
  15 int pb_gcd(pb_poly *a, pb_poly *b, pb_poly *c)
  16 {
  17    pb_poly A, B, tmp;
  18    int err;
  19
  20    if (mp_iszero(&(c->characteristic)) == MP_YES) {
  21       return MP_VAL;
  22    }
  23
  24    /* special cases (one or both are zero) */
  25    if (a->used == 0 && b->used == 0) {
  26       /* both zero, set to 1 */
  27       pb_zero(c);
  28       c->used = 1;
  29       mp_set(&(c->terms[0]), 1);
  30       return MP_OKAY;
  31    } else if (a->used == 0) {
  32       return pb_copy(b, c);
  33    } else if (b->used == 0) {
  34       return pb_copy(a, c);
  35    }
  36
  37    if ((err = pb_init(&tmp, &(c->characteristic))) != MP_OKAY) {
  38       return err;
  39    }
  40    if ((err = pb_init_copy(&A, a)) != MP_OKAY) {
  41       goto __TMP;
  42    }
  43    if ((err = pb_init_copy(&B, b)) != MP_OKAY) {
  44       goto __A;
  45    }
  46
  47    while (B.used > 0) {
  48        if ((err = pb_mod(&A, &B, &tmp)) != MP_OKAY) {
  49           goto __B;
  50        }
  51        /* A = B, B = tmp */
  52        if ((err = pb_copy(&B, &A)) != MP_OKAY) {
  53           goto __B;
  54        }
  55        if ((err = pb_copy(&tmp, &B)) != MP_OKAY) {
  56           goto __B;
  57        }
  58    }
  59
  60    /* ensure it's monic */
  61    err = pb_monic(&A, c);
  62
  63 __B  : pb_clear(&B);
  64 __A  : pb_clear(&A);
  65 __TMP: pb_clear(&tmp);
  66    return err;
  67 }
  68
  69