demo/demo.c

   1 #include <tompoly.h>
   2
   3 void draw_poly(pb_poly *a)
   4 {
   5    int x;
   6    char buf[8192];
   7
   8    if (a->used == 0) {
   9       printf("0");
  10    } else {
  11       for (x = a->used - 1; x >= 0; x--) {
  12           if (mp_iszero(&(a->terms[x])) == MP_YES) continue;
  13           mp_toradix(&(a->terms[x]), buf, 10);
  14           if ((x != a->used - 1) && a->terms[x].sign == MP_ZPOS) {
  15              printf("+");
  16           }
  17           printf(" %sx^%d ", buf, x);
  18       }
  19    }
  20    if (mp_iszero(&(a->characteristic)) == MP_NO) {
  21       mp_toradix(&(a->characteristic), buf, 10);
  22       printf(" (mod %s)", buf);
  23    }
  24    printf("\n");
  25 }
  26
  27 int main(void)
  28 {
  29    mp_int chara;
  30    pb_poly a,b,c,d,e;
  31    mp_int  aa,bb,cc,dd,ee;
  32    int res;
  33
  34    mp_init(&chara);
  35    mp_init_multi(&aa,&bb,&cc,&dd,&ee,NULL);
  36    pb_init_size(&a, &chara, 32);
  37    pb_init_size(&b, &chara, 32);
  38    pb_init_size(&c, &chara, 32);
  39    pb_init_size(&d, &chara, 32);
  40    pb_init_size(&e, &chara, 32);
  41
  42    /* a = 3x + 4 */
  43    mp_set(&(a.terms[1]), 3);
  44    mp_set(&(a.terms[0]), 4);
  45    a.used = 2;
  46    pb_clamp(&a);
  47    printf("a == \n");
  48    draw_poly(&a);
  49
  50    /* b = 7x^2 + 5x + 7 */
  51    mp_set(&(b.terms[2]), 7);
  52    mp_set(&(b.terms[1]), 5);
  53    mp_set(&(b.terms[0]), 7);
  54    b.used = 3;
  55    pb_clamp(&b);
  56    printf("b == \n");
  57    draw_poly(&b);
  58
  59    /* c = a + b */
  60    printf("a + b\n");
  61    pb_add(&a, &b, &c);
  62    draw_poly(&c);
  63
  64    /* c = b + a */
  65    printf("b + a\n");
  66    pb_add(&b, &a, &c);
  67    draw_poly(&c);
  68
  69    /* now test clearing */
  70    printf("Shifting previous up one\n");
  71    pb_lshd(&c, 1);
  72    draw_poly(&c);
  73    pb_rshd(&c, 1);
  74    draw_poly(&c);
  75    pb_lshd(&c, 1);
  76    pb_add(&a, &b, &c);
  77    printf("previous add (test if excess cleared)\n");
  78    draw_poly(&c);
  79
  80    /* multiply */
  81    printf("Multiply:\n");
  82    draw_poly(&a);
  83    draw_poly(&b);
  84    pb_mul(&a, &b, &c);
  85    draw_poly(&c);
  86
  87    /* subtract */
  88    printf("a - b\n");
  89    pb_sub(&a, &b, &c);
  90    draw_poly(&c);
  91    printf("b - a\n");
  92    pb_sub(&b, &a, &c);
  93    draw_poly(&c);
  94
  95
  96    /* now hijack the char */
  97    mp_set(&(a.characteristic), 17);
  98    mp_set(&(b.characteristic), 17);
  99    mp_set(&(c.characteristic), 17);
 100    mp_set(&(d.characteristic), 17);
 101    mp_set(&(e.characteristic), 17);
 102
 103    /* perform modular addition */
 104    printf("a + b (in GF(17))\n");
 105    pb_add(&a, &b, &c);
 106    draw_poly(&c);
 107    pb_add(&b, &a, &c);
 108    draw_poly(&c);
 109
 110    /* perform modular subtaction */
 111    printf("a - b (in GF(17))\n");
 112    pb_sub(&a, &b, &c);
 113    draw_poly(&c);
 114    printf("b - a (in GF(17))\n");
 115    pb_sub(&b, &a, &c);
 116    draw_poly(&c);
 117
 118    /* perform division */
 119    printf("Division (b/a)\n");
 120    pb_div(&b, &a, &c, &d);
 121    draw_poly(&a);
 122    draw_poly(&b);
 123    printf("Q == \n"); draw_poly(&c);
 124    printf("R == \n"); draw_poly(&d);
 125
 126    /* now test it */
 127    pb_mul(&a, &c, &c);
 128    pb_add(&c, &d, &c);
 129    printf("aQ + R =\n"); draw_poly(&c);
 130
 131    /* test mod */
 132    pb_mod(&b, &a, &c);
 133    printf("b mod a == "); draw_poly(&c);
 134
 135    /* test GCD of (x^2 - 1) and 5*x^4+5*x^3+7*x^2+8*x+1 [should be x+1] */
 136    printf("GCD Test\n");
 137    pb_zero(&a);
 138    mp_set(&(a.terms[2]), 1);
 139    mp_set(&(a.terms[0]), 16);
 140    a.used = 3;
 141    pb_clamp(&a);
 142    printf("a == \n");
 143    draw_poly(&a);
 144
 145    pb_zero(&b);
 146    mp_set(&(b.terms[4]), 5);
 147    mp_set(&(b.terms[3]), 5);
 148    mp_set(&(b.terms[2]), 7);
 149    mp_set(&(b.terms[1]), 8);
 150    mp_set(&(b.terms[0]), 1);
 151    b.used = 6;
 152    pb_clamp(&b);
 153    printf("b == \n");
 154    draw_poly(&b);
 155
 156    pb_gcd(&a, &b, &c);
 157    printf("GCD: "); draw_poly(&c);
 158
 159    /* test GCD */
 160    pb_div(&a, &c, &d, &e);
 161    printf("a/c == "); draw_poly(&d); printf("a mod c == "); draw_poly(&e); pb_mul(&d, &c, &e); printf("should be a: "); draw_poly(&e);
 162    pb_div(&b, &c, &d, &e);
 163    printf("b/c == "); draw_poly(&d); printf("b mod c == "); draw_poly(&e); pb_mul(&d, &c, &e); printf("should be b: "); draw_poly(&e);
 164
 165    /* test modular inverse... x^2 + 3 or so should work nice */
 166    printf("Modular Inverse\n");
 167    pb_zero(&a);
 168    mp_set(&(a.terms[2]), 1);
 169    mp_set(&(a.terms[1]), 0);
 170    mp_set(&(a.terms[0]), 3);
 171    a.used = 3;
 172    pb_clamp(&a);
 173    printf("a == \n");
 174    draw_poly(&a);
 175
 176    /* take inverse of 2x + 9 */
 177    pb_zero(&b);
 178    mp_set(&(b.terms[1]), 2);
 179    mp_set(&(b.terms[0]), 9);
 180    b.used = 2;
 181    pb_clamp(&b);
 182    printf("b == \n");
 183    draw_poly(&b);
 184
 185    /* invert */
 186    pb_invmod(&b, &a, &c);
 187    printf("Inverse\n");
 188    draw_poly(&c);
 189
 190    /* test */
 191    pb_mulmod(&b, &c, &a, &d);
 192    pb_mul(&b, &c, &e);
 193    printf("This should be 1               : "); draw_poly(&d);
 194    printf("This should be equal to k*a + 1: "); draw_poly(&e);
 195
 196    /* now b has order [dividing] 17^2 - 1 == 288 so b^287 should equal c */
 197    printf("exptmod test\n");
 198    mp_set(&aa, 287);
 199    pb_exptmod(&b, &aa, &a, &d);
 200    printf("This should be invmod          : "); draw_poly(&d);
 201
 202    /* test irreduc */
 203    printf("Irreducibility testing\n");
 204    pb_isirreduc(&a, &res);
 205    printf("This should be 1               : %d\n", res);
 206
 207    pb_isirreduc(&b, &res);
 208    printf("This should be 0               : %d\n", res);
 209
 210
 211
 212    return EXIT_SUCCESS;
 213 }
 214
 215
 216