tompoly.h

   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 #ifndef TOMPOLY_H_
  13 #define TOMPOLY_H_
  14
  15 #include <tommath.h>
  16
  17 /* this structure holds a polynomial */
  18 typedef struct {
  19    int    used,                  /* number of terms */
  20           alloc;                 /* number of terms available (total) */
  21    mp_int characteristic,        /* characteristic, zero if not finite */
  22           *terms;                /* terms of polynomial */
  23 } pb_poly;
  24
  25
  26 /* default number of terms */
  27 #define PB_TERMS        4
  28
  29 /* Compare codes */
  30 #define PB_EQ           0        /* They're exactly equal */
  31 #define PB_DEG_LT       1        /* The left has a lower degree */
  32 #define PB_DEG_EQ       2        /* same degree  */
  33 #define PB_DEG_GT       3        /* The left has a higher degree */
  34
  35 int pb_init(pb_poly *a, mp_int *characteristic);
  36 int pb_init_size(pb_poly *a, mp_int *characteristic, int size);
  37 int pb_init_copy(pb_poly *a, pb_poly *b);
  38 int pb_init_multi(mp_int *characteristic, pb_poly *pb, ...);
  39 void pb_clear_multi(pb_poly *mp, ...);
  40 void pb_clear(pb_poly *a);
  41
  42 int pb_shrink(pb_poly *a);
  43 int pb_grow(pb_poly *a, int size);
  44 void pb_clamp(pb_poly *a);
  45
  46 /* dest(x) := src(x) */
  47 int pb_copy(pb_poly *src, pb_poly *dest);
  48
  49 /* compare these */
  50 int pb_cmp(pb_poly *a, pb_poly *b);
  51
  52 /* swap contents of a(x) and b(x) */
  53 void pb_exch(pb_poly *a, pb_poly *b);
  54
  55 /* a(x) = 0 */
  56 void pb_zero(pb_poly *a);
  57
  58 /* a(x) = a(x) / I(x)^x */
  59 int pb_rshd(pb_poly *a, int x);
  60
  61 /* a(x) = a(x) * I(x)^x */
  62 int pb_lshd(pb_poly *a, int x);
  63
  64 /* c(x) = a(x) + b(x) */
  65 int pb_add(pb_poly *a, pb_poly *b, pb_poly *c);
  66
  67 /* c(x) = a(x) - b(x) */
  68 int pb_sub(pb_poly *a, pb_poly *b, pb_poly *c);
  69
  70 /* c(x) = a(x) * b(x) */
  71 int pb_mul(pb_poly *a, pb_poly *b, pb_poly *c);
  72
  73 /* c(x) * b(x) + d(x) = a(x) */
  74 int pb_div(pb_poly *a, pb_poly *b, pb_poly *c, pb_poly *d);
  75
  76 /* c(x) = a(x) mod b(x) */
  77 int pb_mod(pb_poly *a, pb_poly *b, pb_poly *c);
  78
  79 /* d(x) = (a(x) + b(x)) mod c(x) */
  80 int pb_addmod(pb_poly *a, pb_poly *b, pb_poly *c, pb_poly *d);
  81
  82 /* d(x) = (a(x) - b(x)) mod c(x) */
  83 int pb_submod(pb_poly *a, pb_poly *b, pb_poly *c, pb_poly *d);
  84
  85 /* d(x) = (a(x) * b(x)) mod c(x) */
  86 int pb_mulmod(pb_poly *a, pb_poly *b, pb_poly *c, pb_poly *d);
  87
  88
  89 /* mathy stuff */
  90
  91 /* makes b equal to the monic polynomial form of a */
  92 int pb_monic(pb_poly *a, pb_poly *b);
  93
  94 /* returns the monic GCD of a,b in GF(p^k)[x] */
  95 int pb_gcd(pb_poly *a, pb_poly *b, pb_poly *c);
  96
  97 /* Extended euclidean algorithm of (a, b) produces  a*u1 + b*u2 = u3  */
  98 int pb_exteuclid(pb_poly *a, pb_poly *b, pb_poly *U1, pb_poly *U2, pb_poly *U3);
  99
 100 /* finds the inverse of a modulo b and stores it in c such that a*c == 1 mod b */
 101 int pb_invmod(pb_poly *a, pb_poly *b, pb_poly *c);
 102
 103 /* computes Y == G^X mod P [accepts negative values for X] */
 104 int pb_exptmod (pb_poly * G, mp_int * X, pb_poly * P, pb_poly * Y);
 105
 106 /* is a(x) irreducible (GF(p)[x] only) */
 107 int pb_isirreduc(pb_poly *a, int *res);
 108
 109
 110 /* I/O */
 111 int pb_rawsize(pb_poly *a);
 112 int pb_toraw(pb_poly *a, unsigned char *dst);
 113 int pb_readraw(pb_poly *a, unsigned char *buf, int len);
 114
 115 /* What follows should be in a private header, but it's fine for now like that. */
 116
 117 #ifndef PB_MIN
 118 #define PB_MIN(x, y) (((x) < (y)) ? (x) : (y))
 119 #endif
 120 #ifndef PB_MAX
 121 #define PB_MAX(x, y) (((x) > (y)) ? (x) : (y))
 122 #endif
 123
 124 #endif