![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to up_gf2n.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib2 / asir2000 / engine|
Return to up_gf2n.c CVS log | Up to [local] / OpenXM_contrib2 / asir2000 / engine |
1.1 ! noro 1: /* $OpenXM: OpenXM/src/asir99/engine/up_gf2n.c,v 1.1.1.1 1999/11/10 08:12:26 noro Exp $ */
! 2: #include "ca.h"
! 3: #include <math.h>
! 4:
! 5: extern int debug_up;
! 6: extern int up_lazy;
! 7: extern GEN_UP2 current_mod_gf2n;
! 8:
! 9: void squarep_gf2n(vl,n1,nr)
! 10: VL vl;
! 11: P n1;
! 12: P *nr;
! 13: {
! 14: UP b1,br;
! 15:
! 16: if ( !n1 )
! 17: *nr = 0;
! 18: else if ( OID(n1) == O_N )
! 19: mulp(vl,n1,n1,nr);
! 20: else {
! 21: ptoup(n1,&b1);
! 22: squareup_gf2n(b1,&br);
! 23: uptop(br,nr);
! 24: }
! 25: }
! 26:
! 27: void squareup_gf2n(n1,nr)
! 28: UP n1;
! 29: UP *nr;
! 30: {
! 31: UP r;
! 32: GF2N *c1,*c;
! 33: int i,d1,d;
! 34:
! 35: if ( !n1 )
! 36: *nr = 0;
! 37: else if ( !n1->d ) {
! 38: *nr = r = UPALLOC(0); r->d = 0;
! 39: squaregf2n((GF2N)n1->c[0],(GF2N *)(&r->c[0]));
! 40: } else {
! 41: d1 = n1->d;
! 42: d = 2*d1;
! 43: *nr = r = UPALLOC(d); r->d = d;
! 44: c1 = (GF2N *)n1->c; c = (GF2N *)r->c;
! 45: bzero((char *)c,(d+1)*sizeof(GF2N *));
! 46: for ( i = 0; i <= d1; i++ )
! 47: squaregf2n(c1[i],&c[2*i]);
! 48: }
! 49: }
! 50:
! 51: /* x^(2^n) mod f */
! 52:
! 53: void powermodup_gf2n(f,xp)
! 54: UP f;
! 55: UP *xp;
! 56: {
! 57: UP x,t,invf;
! 58: int k,n;
! 59: GF2N lm;
! 60: struct oEGT eg_sq,eg_rem,eg_mul,eg_inv,eg0,eg1,eg2;
! 61:
! 62: n = degup2(current_mod_gf2n->dense);
! 63: MKGF2N(ONEUP2,lm);
! 64: x = UPALLOC(1); x->d = 1; x->c[1] = (Num)lm;
! 65:
! 66: reverseup(f,f->d,&t);
! 67: invmodup(t,f->d,&invf);
! 68: for ( k = 0; k < n; k++ ) {
! 69: squareup_gf2n(x,&t);
! 70: rembymulup_special(t,f,invf,&x);
! 71: /* remup(t,f,&x); */
! 72: }
! 73: *xp = x;
! 74: }
! 75:
! 76: /* g^d mod f */
! 77:
! 78: void generic_powermodup_gf2n(g,f,d,xp)
! 79: UP g,f;
! 80: Q d;
! 81: UP *xp;
! 82: {
! 83: N e;
! 84: UP x,y,t,invf,s;
! 85: int k;
! 86: GF2N lm;
! 87:
! 88: e = NM(d);
! 89: MKGF2N(ONEUP2,lm);
! 90: y = UPALLOC(0); y->d = 0; y->c[0] = (Num)lm;
! 91: remup(g,f,&x);
! 92: if ( !x ) {
! 93: *xp = !d ? y : 0;
! 94: return;
! 95: } else if ( !x->d ) {
! 96: pwrup(x,d,xp);
! 97: return;
! 98: }
! 99: reverseup(f,f->d,&t);
! 100: invmodup(t,f->d,&invf);
! 101: for ( k = n_bits(e)-1; k >= 0; k-- ) {
! 102: squareup_gf2n(y,&t);
! 103: rembymulup_special(t,f,invf,&s);
! 104: y = s;
! 105: if ( e->b[k/32] & (1<<(k%32)) ) {
! 106: mulup(y,x,&t);
! 107: remup(t,f,&s);
! 108: y = s;
! 109: }
! 110: }
! 111: *xp = y;
! 112: }
! 113:
! 114: /* g+g^2+...+g^(2^(nd-1)) mod f; where e = deg(mod) */
! 115:
! 116: void tracemodup_gf2n(g,f,d,xp)
! 117: UP g,f;
! 118: Q d;
! 119: UP *xp;
! 120: {
! 121: UP x,t,s,u,invf;
! 122: int en,i;
! 123:
! 124: en = QTOS(d)*degup2(current_mod_gf2n->dense);
! 125: remup(g,f,&x);
! 126: if ( !x ) {
! 127: *xp = 0;
! 128: return;
! 129: }
! 130: reverseup(f,f->d,&t);
! 131: invmodup(t,f->d,&invf);
! 132: for ( i = 1, t = s = x; i < en; i++ ) {
! 133: squareup_gf2n(t,&u);
! 134: rembymulup_special(u,f,invf,&t);
! 135: addup(s,t,&u); s = u;
! 136: }
! 137: *xp = s;
! 138: }
! 139:
! 140: void tracemodup_gf2n_slow(g,f,d,xp)
! 141: UP g,f;
! 142: Q d;
! 143: UP *xp;
! 144: {
! 145: UP x,t,s,u;
! 146: int en,i;
! 147:
! 148: en = QTOS(d)*degup2(current_mod_gf2n->dense);
! 149: remup(g,f,&x);
! 150: if ( !x ) {
! 151: *xp = 0;
! 152: return;
! 153: }
! 154: for ( i = 1, t = s = x; i < en; i++ ) {
! 155: squareup_gf2n(t,&u);
! 156: remup(u,f,&t);
! 157: addup(s,t,&u); s = u;
! 158: }
! 159: *xp = s;
! 160: }
! 161:
! 162: static struct oEGT eg_trace_tab,eg_trace_mul;
! 163:
! 164: void tracemodup_gf2n_tab(g,f,d,xp)
! 165: UP g,f;
! 166: Q d;
! 167: UP *xp;
! 168: {
! 169: UP x0,x2,t,s,u;
! 170: int en,i;
! 171: UP *tab;
! 172: GF2N one;
! 173: struct oEGT eg1,eg2;
! 174:
! 175: en = QTOS(d)*degup2(current_mod_gf2n->dense);
! 176: remup(g,f,&t); g = t;
! 177: if ( !g ) {
! 178: *xp = 0;
! 179: return;
! 180: }
! 181:
! 182: MKGF2N(ONEUP2,one);
! 183: x0 = UPALLOC(0); x0->d = 0; x0->c[0] = (Num)one;
! 184: x2 = UPALLOC(2); x2->d = 2; x2->c[2] = (Num)one;
! 185:
! 186: tab = (UP *)ALLOCA(en*sizeof(UP));
! 187: tab[0] = x0;
! 188: remup(x2,f,&tab[1]);
! 189:
! 190: for ( i = 2; i < en; i++ ) {
! 191: mulup(tab[i-1],tab[1],&t); remup(t,f,&tab[i]);
! 192: }
! 193:
! 194: for ( i = 1, t = s = g; i < en; i++ ) {
! 195: square_rem_tab_up_gf2n(t,tab,&u); t = u;
! 196: addup(s,t,&u); s = u;
! 197: }
! 198: *xp = s;
! 199: }
! 200:
! 201: void square_rem_tab_up_gf2n(f,tab,rp)
! 202: UP f;
! 203: UP *tab;
! 204: UP *rp;
! 205: {
! 206: UP s,t,u,n;
! 207: Num *c;
! 208: int i,d;
! 209:
! 210: n = UPALLOC(0); n->d = 0;
! 211: if ( !f )
! 212: *rp = 0;
! 213: else {
! 214: d = f->d; c = f->c;
! 215: up_lazy = 1;
! 216: for ( i = 0, s = 0; i <= d; i++ ) {
! 217: squaregf2n((GF2N)c[i],(GF2N *)(&n->c[0]));
! 218: mulup(tab[i],n,&t); addup(s,t,&u); s = u;
! 219: }
! 220: up_lazy = 0;
! 221: simpup(s,rp);
! 222: }
! 223: }
! 224:
! 225: void powertabup_gf2n(f,xp,tab)
! 226: UP f;
! 227: UP xp;
! 228: UP *tab;
! 229: {
! 230: UP y,t,invf;
! 231: int i,d;
! 232: GF2N lm;
! 233:
! 234: d = f->d;
! 235: MKGF2N(ONEUP2,lm);
! 236: y = UPALLOC(0); y->d = 0; y->c[0] = (Num)lm;
! 237: tab[0] = y;
! 238: tab[1] = xp;
! 239:
! 240: reverseup(f,f->d,&t);
! 241: invmodup(t,f->d,&invf);
! 242:
! 243: for ( i = 2; i < d; i++ ) {
! 244: if ( debug_up )
! 245: fprintf(stderr,".");
! 246: if ( !(i%2) )
! 247: squareup_gf2n(tab[i/2],&t);
! 248: else
! 249: kmulup(tab[i-1],xp,&t);
! 250: rembymulup_special(t,f,invf,&tab[i]);
! 251: /* remup(t,f,&tab[i]); */
! 252: }
! 253: }
! 254:
! 255: void find_root_gf2n(f,r)
! 256: UP f;
! 257: GF2N *r;
! 258: {
! 259: UP g,ut,c,t,h,rem;
! 260: int n;
! 261: GF2N rn;
! 262: struct oEGT eg0,eg1,eg_trace;
! 263:
! 264: n = degup2(current_mod_gf2n->dense);
! 265: g = f;
! 266: while ( g->d > 1 ) {
! 267: ut = UPALLOC(1); ut->c[0] = 0;
! 268: randomgf2n(&rn);
! 269: if ( !rn )
! 270: continue;
! 271: ut->c[1] = (Num)rn; ut->d = 1;
! 272: tracemodup_gf2n_tab(ut,f,ONE,&c);
! 273: gcdup(c,g,&h);
! 274: if ( h->d && h->d < g->d ) {
! 275: if ( 2*h->d > g->d ) {
! 276: qrup(g,h,&t,&rem); g = t;
! 277: if ( rem )
! 278: error("find_root_gf2n : cannot happen");
! 279: } else
! 280: g = h;
! 281: }
! 282: monicup(g,&t); g = t;
! 283: printf("deg(g)=%d\n",g->d);
! 284: }
! 285: divgf2n((GF2N)g->c[0],(GF2N)g->c[1],r);
! 286: }