pb_isirreduc.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 /* is a(x) irreducible?  */
  15 int pb_isirreduc(pb_poly *a, int *res)
  16 {
  17    pb_poly u, tmp, fm, d;
  18    int err, i;
  19
  20    /* default to no */
  21    *res = MP_NO;
  22
  23    /* init temps */
  24    if ((err = pb_init_multi(&(a->characteristic),
  25        &u, &tmp, &fm, &d, NULL)) != MP_OKAY) {
  26        return err;
  27    }
  28
  29    /* fm = monic(a(x)) */
  30    if ((err = pb_monic(a, &fm)) != MP_OKAY)                                   { goto _ERR; }
  31
  32    /* u  = x */
  33    mp_set(&(u.terms[1]), 1); u.used = 2;
  34
  35    /* loop */
  36    for (i = 1; i <= (a->used / 2); i++) {
  37        /* u = u^p mod fm */
  38        if ((err = pb_exptmod(&u, &(a->characteristic), &fm, &u)) != MP_OKAY)  { goto _ERR; }
  39
  40        /* tmp = u - x */
  41        pb_zero(&tmp);
  42        mp_set(&(tmp.terms[1]), 1); tmp.used = 2;
  43        if ((err = pb_sub(&u, &tmp, &tmp)) != MP_OKAY)                         { goto _ERR; }
  44
  45        /* d = gcd(fm, tmp) */
  46        if ((err = pb_gcd(&fm, &tmp, &d)) != MP_OKAY)                          { goto _ERR; }
  47
  48        /* if d != 1 then reducible */
  49        if (d.used > 1)                                                        { err = MP_OKAY; goto _ERR; }
  50    }
  51
  52    /* irreducible */
  53    *res = MP_YES;
  54    err  = MP_OKAY;
  55 _ERR: pb_clear_multi(&u, &tmp, &fm, &d, NULL);
  56    return err;
  57 }
  58
  59