pb_monic.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 /* makes b equal to the monic polynomial form of a */
  15 int pb_monic(pb_poly *a, pb_poly *b)
  16 {
  17    mp_int tmp;
  18    int err, x;
  19
  20    /* must be in GF(p)[x] */
  21    if (mp_iszero(&(b->characteristic)) == MP_YES) {
  22       return MP_VAL;
  23    }
  24
  25    /* if it's already monic  just copy */
  26    if (a->used == 0 || mp_cmp_d(&(a->terms[a->used - 1]), 1) == MP_EQ) {
  27       return pb_copy(a, b);
  28    }
  29
  30    /* grow b to hold result */
  31    if (b->alloc < a->used) {
  32       if ((err = pb_grow(b, a->used)) != MP_OKAY) {
  33          return err;
  34       }
  35    }
  36
  37    /* now init tmp and find the inverse of the leading digit */
  38    if ((err = mp_init(&tmp)) != MP_OKAY) {
  39       return err;
  40    }
  41
  42    if ((err = mp_invmod(&(a->terms[a->used-1]), &(b->characteristic), &tmp)) != MP_OKAY)             { goto _ERR; }
  43
  44    /* now reduce each coefficient */
  45    for (x = 0; x < a->used; x++) {
  46        if ((err = mp_mulmod(&(a->terms[x]), &tmp, &(b->characteristic), &(b->terms[x]))) != MP_OKAY) { goto _ERR; }
  47    }
  48
  49    /* zero excess digits */
  50    for (x = a->used; x < b->used; x++) {
  51        mp_zero(&(b->terms[x]));
  52    }
  53    b->used = a->used;
  54
  55    err = MP_OKAY;
  56 _ERR: mp_clear(&tmp);
  57    return err;
  58 }
  59
  60