![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to Hgfs.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 Hgfs.c CVS log | Up to [local] / OpenXM_contrib2 / asir2000 / engine |
1.29 ! noro 1: /* $OpenXM: OpenXM_contrib2/asir2000/engine/Hgfs.c,v 1.28 2002/11/22 07:32:10 noro Exp $ */
1.1 noro 2:
3: #include "ca.h"
1.22 noro 4: #include "inline.h"
1.1 noro 5:
1.18 noro 6: void lnfsf(int n,UM p0,UM p1,struct p_pair *list,UM np0,UM np1);
1.20 noro 7: void extractcoefbm(BM f,int dx,UM r);
1.1 noro 8:
1.18 noro 9: int comp_dum(DUM a,DUM b)
1.12 noro 10: {
11: if ( DEG(a->f) > DEG(b->f) )
12: return -1;
13: else if ( DEG(a->f) < DEG(b->f) )
14: return 1;
15: else
16: return 0;
17: }
18:
1.25 noro 19: void ufctrsf(P p,DCP *dcp)
1.1 noro 20: {
21: int n,i,j,k;
22: DCP dc,dc0;
23: P lc;
24: UM mp;
25: UM *tl;
1.18 noro 26: Obj obj;
1.1 noro 27: struct oDUM *udc,*udc1;
28:
1.18 noro 29: simp_ff((Obj)p,&obj); p = (P)obj;
1.1 noro 30: if ( !p ) {
1.21 noro 31: NEWDC(dc); COEF(dc) = 0; DEG(dc) = ONE;
32: NEXT(dc) = 0; *dcp = dc;
33: return;
1.1 noro 34: }
35: mp = W_UMALLOC(UDEG(p));
36: ptosfum(p,mp);
37: if ( (n = DEG(mp)) < 0 ) {
38: *dcp = 0; return;
39: } else if ( n == 0 ) {
40: NEWDC(dc); COEF(dc) = p; DEG(dc) = ONE;
41: NEXT(dc) = 0; *dcp = dc;
42: return;
43: }
44: lc = COEF(DC(p));
45: if ( !_isonesf(COEF(mp)[n]) ) {
46: monicsfum(mp);
47: }
48:
49: W_CALLOC(n+1,struct oDUM,udc);
50: gensqfrsfum(mp,udc);
51:
52: tl = (UM *)ALLOCA((n+1)*sizeof(UM));
53: W_CALLOC(DEG(mp)+1,struct oDUM,udc1);
54:
55: for ( i = 0,j = 0; udc[i].f; i++ )
56: if ( DEG(udc[i].f) == 1 ) {
57: udc1[j].f = udc[i].f; udc1[j].n = udc[i].n; j++;
58: } else {
59: bzero((char *)tl,(n+1)*sizeof(UM));
60: czsfum(udc[i].f,tl);
61: for ( k = 0; tl[k]; k++, j++ ) {
62: udc1[j].f = tl[k]; udc1[j].n = udc[i].n;
63: }
64: }
65: udc = udc1;
1.12 noro 66: for ( i = 0; udc[i].f; i++ );
67: qsort(udc,i,sizeof(struct oDUM),
68: (int (*)(const void *,const void *))comp_dum);
69:
1.1 noro 70: NEWDC(dc0); COEF(dc0) = lc; DEG(dc0) = ONE; dc = dc0;
71: for ( n = 0; udc[n].f; n++ ) {
72: NEWDC(NEXT(dc)); dc = NEXT(dc);
73: STOQ(udc[n].n,DEG(dc)); sfumtop(VR(p),udc[n].f,&COEF(dc));
74: }
75: NEXT(dc) = 0; *dcp = dc0;
76: }
77:
1.18 noro 78: void gensqfrsfum(UM p,struct oDUM *dc)
1.1 noro 79: {
80: int n,i,j,d,mod;
81: UM t,s,g,f,f1,b;
1.29 ! noro 82: GFS u,v;
1.1 noro 83:
84: if ( (n = DEG(p)) == 1 ) {
85: dc[0].f = UMALLOC(DEG(p)); cpyum(p,dc[0].f); dc[0].n = 1;
86: return;
87: }
88: t = W_UMALLOC(n); s = W_UMALLOC(n); g = W_UMALLOC(n);
89: f = W_UMALLOC(n); f1 = W_UMALLOC(n); b = W_UMALLOC(n);
90: diffsfum(p,t); cpyum(p,s); gcdsfum(t,s,g);
91: if ( !DEG(g) ) {
92: dc[0].f = UMALLOC(DEG(p)); cpyum(p,dc[0].f); dc[0].n = 1;
93: return;
94: }
95: cpyum(p,b); cpyum(p,t); divsfum(t,g,f);
96: for ( i = 0, d = 0; DEG(f); i++ ) {
97: while ( 1 ) {
98: cpyum(b,t);
99: if ( divsfum(t,f,s) >= 0 )
100: break;
101: else {
102: cpyum(s,b); d++;
103: }
104: }
105: cpyum(b,t); cpyum(f,s); gcdsfum(t,s,f1);
106: divsfum(f,f1,s); cpyum(f1,f);
107: dc[i].f = UMALLOC(DEG(s)); cpyum(s,dc[i].f); dc[i].n = d;
108: }
109: mod = characteristic_sf();
110: if ( DEG(b) > 0 ) {
111: d = 1;
112: while ( 1 ) {
113: cpyum(b,t);
114: for ( j = DEG(t); j >= 0; j-- )
115: if ( COEF(t)[j] && (j % mod) )
116: break;
117: if ( j >= 0 )
118: break;
119: else {
120: DEG(s) = DEG(t)/mod;
1.29 ! noro 121: for ( j = 0; j <= DEG(t); j++ ) {
! 122: iftogfs(COEF(t)[j*mod],&u);
! 123: pthrootgfs(u,&v);
! 124: COEF(s)[j] = v?FTOIF(CONT(v)):0;
! 125: }
1.1 noro 126: cpyum(s,b); d *= mod;
127: }
128: }
129: gensqfrsfum(b,dc+i);
130: for ( j = i; dc[j].f; j++ )
131: dc[j].n *= d;
132: }
133: }
134:
1.18 noro 135: void randsfum(int d,UM p)
1.1 noro 136: {
137: int i;
138:
1.2 noro 139: for ( i = 0; i < d; i++ )
1.1 noro 140: COEF(p)[i] = _randomsf();
1.2 noro 141: for ( i = d-1; i >= 0 && !COEF(p)[i]; i-- );
142: p->d = i;
1.1 noro 143: }
144:
1.18 noro 145: void pwrmodsfum(UM p,int e,UM f,UM pr)
1.1 noro 146: {
147: UM wt,ws,q;
148:
149: if ( e == 0 ) {
150: DEG(pr) = 0; COEF(pr)[0] = _onesf();
151: } else if ( DEG(p) < 0 )
152: DEG(pr) = -1;
153: else if ( e == 1 ) {
154: q = W_UMALLOC(DEG(p)); cpyum(p,pr);
155: DEG(pr) = divsfum(pr,f,q);
156: } else if ( DEG(p) == 0 ) {
157: DEG(pr) = 0; COEF(pr)[0] = _pwrsf(COEF(p)[0],e);
158: } else {
159: wt = W_UMALLOC(2*DEG(f)); ws = W_UMALLOC(2*DEG(f));
160: q = W_UMALLOC(2*DEG(f));
161: pwrmodsfum(p,e/2,f,wt);
162: if ( !(e%2) ) {
163: mulsfum(wt,wt,pr); DEG(pr) = divsfum(pr,f,q);
164: } else {
165: mulsfum(wt,wt,ws);
166: DEG(ws) = divsfum(ws,f,q);
167: mulsfum(ws,p,pr);
168: DEG(pr) = divsfum(pr,f,q);
169: }
170: }
171: }
172:
1.18 noro 173: void spwrsfum(UM m,UM f,N e,UM r)
1.1 noro 174: {
175: UM t,s,q;
176: N e1;
177: int a;
178:
179: if ( !e ) {
180: DEG(r) = 0; COEF(r)[0] = _onesf();
181: } else if ( UNIN(e) )
182: cpyum(f,r);
183: else {
184: a = divin(e,2,&e1);
1.2 noro 185: t = W_UMALLOC(2*DEG(m)); spwrsfum(m,f,e1,t);
1.1 noro 186: s = W_UMALLOC(2*DEG(m)); q = W_UMALLOC(2*DEG(m));
187: mulsfum(t,t,s); DEG(s) = divsfum(s,m,q);
188: if ( a ) {
189: mulsfum(s,f,t); DEG(t) = divsfum(t,m,q); cpyum(t,r);
190: } else
191: cpyum(s,r);
192: }
193: }
194:
1.18 noro 195: void tracemodsfum(UM m,UM f,int e,UM r)
1.2 noro 196: {
197: UM t,s,q,u;
198: int i;
199:
200: q = W_UMALLOC(2*DEG(m)+DEG(f)); /* XXX */
201: t = W_UMALLOC(2*DEG(m));
202: s = W_UMALLOC(2*DEG(m));
203: u = W_UMALLOC(2*DEG(m));
204: DEG(f) = divsfum(f,m,q);
205: cpyum(f,s);
206: cpyum(f,t);
207: for ( i = 1; i < e; i++ ) {
208: mulsfum(t,t,u);
209: DEG(u) = divsfum(u,m,q); cpyum(u,t);
210: addsfum(t,s,u); cpyum(u,s);
211: }
212: cpyum(s,r);
213: }
214:
1.18 noro 215: void make_qmatsf(UM p,UM *tab,int ***mp)
1.1 noro 216: {
217: int n,i,j;
218: int *c;
219: UM q,r;
220: int **mat;
221: int one;
222:
223: n = DEG(p);
224: *mp = mat = almat(n,n);
225: for ( j = 0; j < n; j++ ) {
226: r = W_UMALLOC(DEG(tab[j])); q = W_UMALLOC(DEG(tab[j]));
227: cpyum(tab[j],r); DEG(r) = divsfum(r,p,q);
228: for ( i = 0, c = COEF(r); i <= DEG(r); i++ )
229: mat[i][j] = c[i];
230: }
231: one = _onesf();
232: for ( i = 0; i < n; i++ )
233: mat[i][i] = _subsf(mat[i][i],one);
234: }
235:
1.18 noro 236: void nullsf(int **mat,int n,int *ind)
1.1 noro 237: {
238: int i,j,l,s,h,inv;
239: int *t,*u;
240:
241: bzero((char *)ind,n*sizeof(int));
242: ind[0] = 0;
243: for ( i = j = 0; j < n; i++, j++ ) {
244: for ( ; j < n; j++ ) {
245: for ( l = i; l < n; l++ )
246: if ( mat[l][j] )
247: break;
248: if ( l < n ) {
249: t = mat[i]; mat[i] = mat[l]; mat[l] = t; break;
250: } else
251: ind[j] = 1;
252: }
253: if ( j == n )
254: break;
255: inv = _invsf(mat[i][j]);
256: for ( s = j, t = mat[i]; s < n; s++ )
257: t[s] = _mulsf(t[s],inv);
258: for ( l = 0; l < n; l++ ) {
259: if ( l == i )
260: continue;
261: u = mat[l]; h = _chsgnsf(u[j]);
262: for ( s = j; s < n; s++ )
263: u[s] = _addsf(_mulsf(h,t[s]),u[s]);
264: }
265: }
266: }
267:
1.18 noro 268: void null_to_solsf(int **mat,int *ind,int n,UM *r)
1.1 noro 269: {
270: int i,j,k,l;
271: int *c;
272: UM w;
273:
274: for ( i = 0, l = 0; i < n; i++ ) {
275: if ( !ind[i] )
276: continue;
277: w = UMALLOC(n);
278: for ( j = k = 0, c = COEF(w); j < n; j++ )
279: if ( ind[j] )
280: c[j] = 0;
281: else
282: c[j] = mat[k++][i];
283: c[i] = _chsgnsf(_onesf());
284: for ( j = n; j >= 0; j-- )
285: if ( c[j] )
286: break;
287: DEG(w) = j;
288: r[l++] = w;
289: }
290: }
291: /*
292: make_qmatsf(p,tab,mp)
293: nullsf(mat,n,ind)
294: null_to_solsf(ind,n,r)
295: */
296:
1.18 noro 297: void czsfum(UM f,UM *r)
1.1 noro 298: {
299: int i,j;
300: int d,n,ord;
301: UM s,t,u,v,w,g,x,m,q;
302: UM *base;
303:
304: n = DEG(f); base = (UM *)ALLOCA(n*sizeof(UM));
305: bzero((char *)base,n*sizeof(UM));
306:
307: w = W_UMALLOC(2*n); q = W_UMALLOC(2*n); m = W_UMALLOC(2*n);
308:
309: base[0] = W_UMALLOC(0); DEG(base[0]) = 0; COEF(base[0])[0] = _onesf();
310:
311: t = W_UMALLOC(1); DEG(t) = 1; COEF(t)[0] = 0; COEF(t)[1] = _onesf();
312:
313: ord = field_order_sf();
314: pwrmodsfum(t,ord,f,w);
315: base[1] = W_UMALLOC(DEG(w));
316: cpyum(w,base[1]);
317:
318: for ( i = 2; i < n; i++ ) {
319: mulsfum(base[i-1],base[1],m);
320: DEG(m) = divsfum(m,f,q);
321: base[i] = W_UMALLOC(DEG(m)); cpyum(m,base[i]);
322: }
323:
324: v = W_UMALLOC(n); cpyum(f,v);
325: DEG(w) = 1; COEF(w)[0] = 0; COEF(w)[1] = _onesf();
326: x = W_UMALLOC(1); DEG(x) = 1; COEF(x)[0] = 0; COEF(x)[1] = _onesf();
327: t = W_UMALLOC(n); s = W_UMALLOC(n); u = W_UMALLOC(n); g = W_UMALLOC(n);
328:
329: for ( j = 0, d = 1; 2*d <= DEG(v); d++ ) {
330: for ( DEG(t) = -1, i = 0; i <= DEG(w); i++ )
331: if ( COEF(w)[i] ) {
332: mulssfum(base[i],COEF(w)[i],s);
333: addsfum(s,t,u); cpyum(u,t);
334: }
335: cpyum(t,w); cpyum(v,s); subsfum(w,x,t);
336: gcdsfum(s,t,g);
337: if ( DEG(g) >= 1 ) {
338: berlekampsf(g,d,base,r+j); j += DEG(g)/d;
339: divsfum(v,g,q); cpyum(q,v);
340: DEG(w) = divsfum(w,v,q);
341: for ( i = 0; i < DEG(v); i++ )
342: DEG(base[i]) = divsfum(base[i],v,q);
343: }
344: }
345: if ( DEG(v) ) {
346: r[j] = UMALLOC(DEG(v)); cpyum(v,r[j]); j++;
347: }
348: r[j] = 0;
349: }
350:
1.18 noro 351: int berlekampsf(UM p,int df,UM *tab,UM *r)
1.1 noro 352: {
353: int n,i,j,k,nf,d,nr;
354: int **mat;
355: int *ind;
356: UM mp,w,q,gcd,w1,w2;
357: UM *u;
358: int *root;
359:
360: n = DEG(p);
361: ind = ALLOCA(n*sizeof(int));
362: make_qmatsf(p,tab,&mat);
363: nullsf(mat,n,ind);
364: for ( i = 0, d = 0; i < n; i++ )
365: if ( ind[i] )
366: d++;
367: if ( d == 1 ) {
368: r[0] = UMALLOC(n); cpyum(p,r[0]); return 1;
369: }
370: u = ALLOCA(d*sizeof(UM *));
371: r[0] = UMALLOC(n); cpyum(p,r[0]);
372: null_to_solsf(mat,ind,n,u);
373: root = ALLOCA(d*sizeof(int));
374: w = W_UMALLOC(n); mp = W_UMALLOC(d);
375: w1 = W_UMALLOC(n); w2 = W_UMALLOC(n);
376: for ( i = 1, nf = 1; i < d; i++ ) {
377: minipolysf(u[i],p,mp);
378: nr = find_rootsf(mp,root);
379: for ( j = 0; j < nf; j++ ) {
380: if ( DEG(r[j]) == df )
381: continue;
382: for ( k = 0; k < nr; k++ ) {
383: cpyum(u[i],w1); cpyum(r[j],w2);
384: COEF(w1)[0] = _chsgnsf(root[k]);
385: gcdsfum(w1,w2,w);
386: if ( DEG(w) > 0 && DEG(w) < DEG(r[j]) ) {
387: gcd = UMALLOC(DEG(w));
388: q = UMALLOC(DEG(r[j])-DEG(w));
389: cpyum(w,gcd); divsfum(r[j],w,q);
390: r[j] = q; r[nf++] = gcd;
391: }
392: if ( nf == d )
393: return d;
394: }
395: }
396: }
1.18 noro 397: /* NOT REACHED */
398: error("berlekampsf : cannot happen");
399: return 0;
1.1 noro 400: }
401:
1.18 noro 402: void minipolysf(UM f,UM p,UM mp)
1.1 noro 403: {
404: struct p_pair *list,*l,*l1,*lprev;
405: int n,d;
406: UM u,p0,p1,np0,np1,q,w;
407:
408: list = (struct p_pair *)MALLOC(sizeof(struct p_pair));
409: list->p0 = u = W_UMALLOC(0); DEG(u) = 0; COEF(u)[0] = _onesf();
410: list->p1 = W_UMALLOC(0); cpyum(list->p0,list->p1);
411: list->next = 0;
412: n = DEG(p); w = UMALLOC(2*n);
413: p0 = UMALLOC(2*n); cpyum(list->p0,p0);
414: p1 = UMALLOC(2*n); cpyum(list->p1,p1);
415: q = W_UMALLOC(2*n);
416: while ( 1 ) {
417: COEF(p0)[DEG(p0)] = 0; DEG(p0)++; COEF(p0)[DEG(p0)] = _onesf();
418: mulsfum(f,p1,w); DEG(w) = divsfum(w,p,q); cpyum(w,p1);
419: np0 = UMALLOC(n); np1 = UMALLOC(n);
420: lnfsf(n,p0,p1,list,np0,np1);
421: if ( DEG(np1) < 0 ) {
422: cpyum(np0,mp); return;
423: } else {
424: l1 = (struct p_pair *)MALLOC(sizeof(struct p_pair));
425: l1->p0 = np0; l1->p1 = np1;
426: for ( l = list, lprev = 0, d = DEG(np1);
427: l && (DEG(l->p1) > d); lprev = l, l = l->next );
428: if ( lprev ) {
429: lprev->next = l1; l1->next = l;
430: } else {
431: l1->next = list; list = l1;
432: }
433: }
434: }
435: }
436:
1.18 noro 437: void lnfsf(int n,UM p0,UM p1,struct p_pair *list,UM np0,UM np1)
1.1 noro 438: {
1.18 noro 439: int h,d1;
1.1 noro 440: UM t0,t1,s0,s1;
441: struct p_pair *l;
442:
443: cpyum(p0,np0); cpyum(p1,np1);
444: t0 = W_UMALLOC(n); t1 = W_UMALLOC(n);
445: s0 = W_UMALLOC(n); s1 = W_UMALLOC(n);
446: for ( l = list; l; l = l->next ) {
447: d1 = DEG(np1);
448: if ( d1 == DEG(l->p1) ) {
449: h = _divsf(COEF(np1)[d1],_chsgnsf(COEF(l->p1)[d1]));
450: mulssfum(l->p0,h,t0); addsfum(np0,t0,s0); cpyum(s0,np0);
451: mulssfum(l->p1,h,t1); addsfum(np1,t1,s1); cpyum(s1,np1);
452: }
453: }
454: }
455:
1.18 noro 456: int find_rootsf(UM p,int *root)
1.1 noro 457: {
458: UM *r;
1.18 noro 459: int i,n;
1.1 noro 460:
461: n = DEG(p);
462: r = ALLOCA((DEG(p))*sizeof(UM));
463: canzassf(p,1,r);
464: for ( i = 0; i < n; i++ )
465: root[i] = _chsgnsf(COEF(r[i])[0]);
466: return n;
467: }
468:
1.18 noro 469: void canzassf(UM f,int d,UM *r)
1.1 noro 470: {
471: UM t,s,u,w,g,o;
472: N n1,n2,n3,n4,n5;
473: UM *b;
1.18 noro 474: int n,q,ed;
1.1 noro 475:
476: if ( DEG(f) == d ) {
477: r[0] = UMALLOC(d); cpyum(f,r[0]);
478: return;
479: } else {
480: n = DEG(f); b = (UM *)ALLOCA(n*sizeof(UM));
481: bzero((char *)b,n*sizeof(UM));
482:
483: t = W_UMALLOC(2*d);
484: s = W_UMALLOC(DEG(f)); u = W_UMALLOC(DEG(f));
485: w = W_UMALLOC(DEG(f)); g = W_UMALLOC(DEG(f));
486: o = W_UMALLOC(0); DEG(o) = 0; COEF(o)[0] = _onesf();
487: q = field_order_sf();
1.2 noro 488: if ( q % 2 ) {
489: STON(q,n1); pwrn(n1,d,&n2); subn(n2,ONEN,&n3);
490: STON(2,n4); divsn(n3,n4,&n5);
491: } else
492: ed = d*extdeg_sf();
1.1 noro 493: while ( 1 ) {
1.2 noro 494: randsfum(2*d,t);
495: if ( q % 2 ) {
496: spwrsfum(f,t,n5,s); subsfum(s,o,u);
497: } else
498: tracemodsfum(f,t,ed,u);
499: cpyum(f,w);
500: gcdsfum(w,u,g);
1.1 noro 501: if ( (DEG(g) >= 1) && (DEG(g) < DEG(f)) ) {
502: canzassf(g,d,r);
503: cpyum(f,w); divsfum(w,g,s);
504: canzassf(s,d,r+DEG(g)/d);
505: return;
506: }
507: }
508: }
509: }
510:
1.3 noro 511: /* Hensel related functions */
512:
1.28 noro 513: int sfberle(V,V,P,int,GFS *,DCP *);
1.3 noro 514: void sfgcdgen(P,ML,ML *);
1.5 noro 515: void sfhenmain2(BM,UM,UM,int,BM *);
516: void ptosfbm(int,P,BM);
1.28 noro 517: void sfhensel(int count,P f,V x,V y,int degbound,GFS *evp,P *sfp,ML *listp);
1.3 noro 518:
519: /* f = f(x,y) */
520:
1.28 noro 521: void sfhensel(int count,P f,V x,V y,int degbound,GFS *evp,P *sfp,ML *listp)
1.3 noro 522: {
1.18 noro 523: int i;
524: int fn;
1.4 noro 525: ML rlist;
1.5 noro 526: BM fl;
1.3 noro 527: VL vl,nvl;
1.19 noro 528: int dx,dy,bound;
1.3 noro 529: GFS ev;
1.18 noro 530: P f1,t,c,sf;
1.21 noro 531: DCP dc,dct,dc0;
1.18 noro 532: UM q,fm,hm;
1.4 noro 533: UM *gm;
1.12 noro 534: struct oEGT tmp0,tmp1,eg_hensel,eg_hensel_t;
1.3 noro 535:
536: clctv(CO,f,&vl);
537: if ( vl->v != x ) {
538: reordvar(vl,x,&nvl); reorderp(nvl,vl,f,&f1);
539: vl = nvl; f = f1;
540: }
1.28 noro 541: if ( vl->next )
542: y = vl->next->v;
1.3 noro 543: dx = getdeg(x,f);
544: dy = getdeg(y,f);
545: if ( dx == 1 ) {
1.4 noro 546: *listp = rlist = MLALLOC(1); rlist->n = 1; rlist->c[0] = 0;
1.3 noro 547: return;
548: }
1.28 noro 549: fn = sfberle(x,y,f,count,&ev,&dc);
1.3 noro 550: if ( fn <= 1 ) {
551: /* fn == 0 => short of evaluation points */
1.4 noro 552: *listp = rlist = MLALLOC(1); rlist->n = fn; rlist->c[0] = 0;
1.3 noro 553: return;
554: }
1.21 noro 555: if ( degbound >= 0 ) {
556: /*
557: * reconstruct dc so that
558: * dc[1],... : factors satisfy degree bound
559: * dc[0] : product of others
560: */
561: c = dc->c; dc = NEXT(dc);
562: dc0 = 0;
563: fn = 0;
564: while ( dc ) {
565: if ( getdeg(x,COEF(dc)) <= degbound ) {
566: dct = NEXT(dc); NEXT(dc) = dc0; dc0 = dc; dc = dct;
567: fn++;
568: } else {
569: mulp(vl,COEF(dc),c,&t); c = t;
570: dc = NEXT(dc);
571: }
572: }
573: if ( OID(c) == O_P ) {
574: NEWDC(dc); COEF(dc) = c; DEG(dc) = ONE; NEXT(dc) = dc0;
575: fn++;
576: } else {
577: mulp(vl,dc0->c,c,&t); dc0->c = t; dc = dc0;
578: }
579: } else {
580: /* pass the the leading coeff. to the first element */
581: c = dc->c; dc = NEXT(dc);
582: mulp(vl,dc->c,c,&t); dc->c = t;
583: }
1.4 noro 584:
585: /* convert mod y-a factors into UM */
586: gm = (UM *)ALLOCA(fn*sizeof(UM));
1.3 noro 587: for ( i = 0; i < fn; i++, dc = NEXT(dc) ) {
1.4 noro 588: gm[i] = W_UMALLOC(UDEG(dc->c));
589: ptosfum(dc->c,gm[i]);
1.3 noro 590: }
1.4 noro 591:
1.19 noro 592: /* set bound */
1.20 noro 593: /* g | f, lc_y(g) = lc_y(f) => deg_y(g) <= deg_y(f) */
594: /* so, bound = dy is sufficient, but we use slightly large value */
1.19 noro 595: bound = dy+2;
596:
1.4 noro 597: /* f(x,y) -> f(x,y+ev) */
1.19 noro 598: fl = BMALLOC(dx,bound);
599: ptosfbm(bound,f,fl);
1.15 noro 600: if ( ev ) shiftsfbm(fl,FTOIF(CONT(ev)));
1.4 noro 601:
1.8 noro 602: /* sf = f(x+ev) */
1.14 noro 603: sfbmtop(fl,x,y,&sf);
1.8 noro 604:
1.4 noro 605: /* fm = fl mod y */
606: fm = W_UMALLOC(dx);
1.5 noro 607: cpyum(COEF(fl)[0],fm);
1.4 noro 608: hm = W_UMALLOC(dx);
609:
610: q = W_UMALLOC(dx);
1.19 noro 611: rlist = MLALLOC(fn); rlist->n = fn; rlist->bound = bound;
1.12 noro 612: fprintf(asir_out,"%d candidates\n",fn);
613: init_eg(&eg_hensel);
1.7 noro 614: for ( i = 0; i < fn-1; i++ ) {
1.12 noro 615: fprintf(asir_out,"deg(fm) = %d, deg(gm[%d]) = %d\n",
616: DEG(fm),i,DEG(gm[i]));
617: init_eg(&eg_hensel_t);
618: get_eg(&tmp0);
1.4 noro 619: /* fl = gm[i]*hm mod y */
620: divsfum(fm,gm[i],hm);
1.19 noro 621: /* fl is replaced by the cofactor of gk mod y^bound */
1.4 noro 622: /* rlist->c[i] = gk */
1.19 noro 623: sfhenmain2(fl,gm[i],hm,bound,(BM *)&rlist->c[i]);
1.4 noro 624: cpyum(hm,fm);
1.12 noro 625: get_eg(&tmp1); add_eg(&eg_hensel_t,&tmp0,&tmp1);
626: add_eg(&eg_hensel,&tmp0,&tmp1);
627: print_eg("Hensel",&eg_hensel_t);
628: fprintf(asir_out,"\n");
1.4 noro 629: }
1.12 noro 630: print_eg("Hensel total",&eg_hensel);
631: fprintf(asir_out,"\n");
1.7 noro 632: /* finally, fl must be the lift of gm[fn-1] */
1.4 noro 633: rlist->c[i] = fl;
634:
1.8 noro 635: #if 0
1.4 noro 636: /* y -> y-a */
637: mev = _chsgnsf(FTOIF(CONT(ev)));
638: for ( i = 0; i < fn; i++ )
1.14 noro 639: shiftsfbm((BM)(rlist->c[i]),mev);
1.8 noro 640: #endif
641: *evp = ev;
642: *sfp = sf;
1.4 noro 643: *listp = rlist;
1.3 noro 644: }
645:
646: /* main variable of f = x */
647:
1.28 noro 648: int sfberle(V x,V y,P f,int count,GFS *ev,DCP *dcp)
1.3 noro 649: {
650: UM wf,wf1,wf2,wfs,gcd;
1.18 noro 651: int fn,n;
1.3 noro 652: GFS m,fm;
653: DCP dc,dct,dc0;
1.28 noro 654: VL vl;
1.18 noro 655: P lc,lc0,f0;
656: Obj obj;
1.23 noro 657: int j,q,index,i;
1.3 noro 658:
1.28 noro 659: NEWVL(vl); vl->v = x;
660: NEWVL(NEXT(vl)); NEXT(vl)->v = y;
661: NEXT(NEXT(vl)) =0;
1.18 noro 662: simp_ff((Obj)f,&obj); f = (P)obj;
1.3 noro 663: n = QTOS(DEG(DC(f)));
664: wf = W_UMALLOC(n); wf1 = W_UMALLOC(n); wf2 = W_UMALLOC(n);
665: wfs = W_UMALLOC(n); gcd = W_UMALLOC(n);
1.23 noro 666: q = field_order_sf();
1.3 noro 667: lc = DC(f)->c;
668: for ( j = 0, fn = n + 1, index = 0;
1.23 noro 669: index < q && j < count && fn > 1; index++ ) {
670: indextogfs(index,&m);
1.3 noro 671: substp(vl,lc,y,(P)m,&lc0);
672: if ( lc0 ) {
673: substp(vl,f,y,(P)m,&f0);
1.4 noro 674: ptosfum(f0,wf); cpyum(wf,wf1);
675: diffsfum(wf1,wf2); gcdsfum(wf1,wf2,gcd);
1.3 noro 676: if ( DEG(gcd) == 0 ) {
1.25 noro 677: ufctrsf(f0,&dc);
1.3 noro 678: for ( dct = NEXT(dc), i = 0; dct; dct = NEXT(dct), i++ );
679: if ( i < fn ) {
680: dc0 = dc; fn = i; fm = m;
681: }
682: j++;
683: }
684: }
685: }
1.23 noro 686: if ( index == q )
1.3 noro 687: return 0;
688: else if ( fn == 1 )
689: return 1;
690: else {
691: *dcp = dc0;
692: *ev = fm;
693: return fn;
694: }
695: }
696:
1.18 noro 697: void sfgcdgen(P f,ML blist,ML *clistp)
1.3 noro 698: {
699: int i;
700: int n,d,np;
701: UM wf,wm,wx,wy,wu,wv,wa,wb,wg,q,tum;
702: UM *in,*out;
703: ML clist;
704:
705: n = UDEG(f); np = blist->n;
706: d = 2*n;
707: q = W_UMALLOC(d); wf = W_UMALLOC(d);
708: wm = W_UMALLOC(d); wx = W_UMALLOC(d);
709: wy = W_UMALLOC(d); wu = W_UMALLOC(d);
710: wv = W_UMALLOC(d); wg = W_UMALLOC(d);
711: wa = W_UMALLOC(d); wb = W_UMALLOC(d);
712: ptosfum(f,wf); DEG(wg) = 0; COEF(wg)[0] = _onesf();
713: *clistp = clist = MLALLOC(np); clist->n = np;
714: for ( i = 0, in = (UM *)blist->c, out = (UM *)clist->c; i < np; i++ ) {
715: divsfum(wf,in[i],q); tum = wf; wf = q; q = tum;
716: cpyum(wf,wx); cpyum(in[i],wy);
717: eucsfum(wx,wy,wa,wb); mulsfum(wa,wg,wm);
718: DEG(wm) = divsfum(wm,in[i],q); out[i] = UMALLOC(DEG(wm));
719: cpyum(wm,out[i]); mulsfum(q,wf,wu);
720: mulsfum(wg,wb,wv); addsfum(wu,wv,wg);
721: }
722: }
723:
1.14 noro 724: /* f = g0*h0 mod y -> f = gk*hk mod y^(dy+1), f is replaced by hk */
1.3 noro 725:
1.18 noro 726: void sfhenmain2(BM f,UM g0,UM h0,int dy,BM *gp)
1.4 noro 727: {
1.18 noro 728: int i,k;
729: int dx;
730: UM wt,wa,wb,q,w1,w2,wh1,wg1,ws;
1.4 noro 731: UM wc,wd,we,wz;
1.5 noro 732: BM wb0,wb1;
1.14 noro 733: int dg,dh;
1.5 noro 734: BM fk,gk,hk;
1.4 noro 735:
1.14 noro 736: if ( DEG(f) < dy )
737: error("sfhenmain2 : invalid input");
738:
739: dx = degbm(f);
740: dg = DEG(g0);
741: dh = DEG(h0);
742:
743: W_BMALLOC(dx,dy,wb0); W_BMALLOC(dx,dy,wb1);
744: wt = W_UMALLOC(dx); ws = W_UMALLOC(dx); q = W_UMALLOC(2*dx);
745: wg1 = W_UMALLOC(2*dx); wh1 = W_UMALLOC(2*dx);
1.5 noro 746:
1.4 noro 747: /* fk = gk*hk mod y^k */
1.14 noro 748: W_BMALLOC(dx,dy,fk);
1.8 noro 749: cpyum(COEF(f)[0],COEF(fk)[0]);
1.14 noro 750: gk = BMALLOC(dg,dy);
1.8 noro 751: cpyum(g0,COEF(gk)[0]);
1.14 noro 752: W_BMALLOC(dh,dy,hk);
1.5 noro 753: cpyum(h0,COEF(hk)[0]);
1.4 noro 754:
1.14 noro 755: wc = W_UMALLOC(2*dx); wd = W_UMALLOC(2*dx);
756: we = W_UMALLOC(2*dx); wz = W_UMALLOC(2*dx);
1.4 noro 757:
758: /* compute wa,wb s.t. wa*g0+wb*h0 = 1 mod y */
1.14 noro 759: w1 = W_UMALLOC(dg); cpyum(g0,w1);
760: w2 = W_UMALLOC(dh); cpyum(h0,w2);
761: wa = W_UMALLOC(2*dx); wb = W_UMALLOC(2*dx); /* XXX */
1.4 noro 762: eucsfum(w1,w2,wa,wb);
763:
1.14 noro 764: fprintf(stderr,"dy=%d\n",dy);
765: for ( k = 1; k <= dy; k++ ) {
1.4 noro 766: fprintf(stderr,".");
767:
768: /* at this point, f = gk*hk mod y^k */
769:
770: /* clear wt */
1.14 noro 771: clearum(wt,dx);
1.4 noro 772:
773: /* wt = (f-gk*hk)/y^k */
1.5 noro 774: subsfum(COEF(f)[k],COEF(fk)[k],wt);
1.4 noro 775:
776: /* compute wf1,wg1 s.t. wh1*g0+wg1*h0 = wt */
777: mulsfum(wa,wt,wh1); DEG(wh1) = divsfum(wh1,h0,q);
778: mulsfum(wh1,g0,wc); subsfum(wt,wc,wd); DEG(wd) = divsfum(wd,h0,wg1);
779:
780: /* check */
781: #if 0
782: if ( DEG(wd) >= 0 || DEG(wg1) > ng )
1.5 noro 783: error("henmain2 : cannot happen(adj)");
1.4 noro 784:
785: mulsfum(wg1,h0,wc); mulsfum(wh1,g0,wd); addsfum(wc,wd,we);
786: subsfum(we,wt,wz);
787: if ( DEG(wz) >= 0 )
788: error("henmain2 : cannot happen");
789: #endif
790:
1.14 noro 791: /* fk += ((wg1*hk+wh1*gk)*y^k+wg1*wh1*y^(2*k) mod y^(dy+1) */
1.4 noro 792: /* wb0 = wh1*y^k */
1.14 noro 793: clearbm(dx,wb0);
1.5 noro 794: cpyum(wh1,COEF(wb0)[k]);
795:
1.14 noro 796: /* wb1 = gk*wb0 mod y^(dy+1) */
797: clearbm(dx,wb1);
798: mulsfbm(gk,wb0,wb1);
1.4 noro 799: /* fk += wb1 */
1.14 noro 800: addtosfbm(wb1,fk);
1.4 noro 801:
802: /* wb0 = wg1*y^k */
1.14 noro 803: clearbm(dx,wb0);
1.5 noro 804: cpyum(wg1,COEF(wb0)[k]);
805:
1.14 noro 806: /* wb1 = hk*wb0 mod y^(dy+1) */
807: clearbm(dx,wb1);
808: mulsfbm(hk,wb0,wb1);
1.4 noro 809: /* fk += wb1 */
1.14 noro 810: addtosfbm(wb1,fk);
1.4 noro 811:
1.14 noro 812: /* fk += wg1*wh1*y^(2*k) mod y^(dy+1) */
813: if ( 2*k <= dy ) {
1.5 noro 814: mulsfum(wg1,wh1,wt); addsfum(COEF(fk)[2*k],wt,ws);
815: cpyum(ws,COEF(fk)[2*k]);
1.4 noro 816: }
817:
818: /* gk += wg1*y^k, hk += wh1*y^k */
1.5 noro 819: cpyum(wg1,COEF(gk)[k]);
820: cpyum(wh1,COEF(hk)[k]);
1.4 noro 821: }
822: fprintf(stderr,"\n");
823: *gp = gk;
1.14 noro 824: DEG(f) = dy;
825: for ( i = 0; i <= dy; i++ )
1.5 noro 826: cpyum(COEF(hk)[i],COEF(f)[i]);
1.27 noro 827: }
828:
829: /* a0*g+b0*h = 1 mod y -> a*g+b*h = 1 mod y^(dy+1) */
830:
831: void sfexgcd_by_hensel(BM g,BM h,int dy,BM *ap,BM *bp)
832: {
833: int i,k;
834: int dx;
835: UM wt,wa,wb,q,w1,w2,ws;
836: UM wc,wd,we,wz,wa1,wb1;
837: BM wz0,wz1;
838: int dg,dh;
839: BM a,b,c;
840:
841: dg = degbm(g);
842: dh = degbm(h);
843: dx = dg+dh;
844:
845: a = BMALLOC(dh,dy);
846: b = BMALLOC(dg,dy);
847: /* c holds a*g+b*h-1 */
848: c = BMALLOC(dg+dh,dy);
849:
850: W_BMALLOC(dx,dy,wz0); W_BMALLOC(dx,dy,wz1);
851:
852: wt = W_UMALLOC(dx); ws = W_UMALLOC(dx); q = W_UMALLOC(2*dx);
853: wa1 = W_UMALLOC(2*dx); wb1 = W_UMALLOC(2*dx);
854: wc = W_UMALLOC(2*dx); wd = W_UMALLOC(2*dx);
855: we = W_UMALLOC(2*dx); wz = W_UMALLOC(2*dx);
856:
857: /* compute wa,wb s.t. wa*g0+wb*h0 = 1 mod y */
858: w1 = W_UMALLOC(dg); cpyum(COEF(g)[0],w1);
859: w2 = W_UMALLOC(dh); cpyum(COEF(h)[0],w2);
860: wa = W_UMALLOC(2*dx); wb = W_UMALLOC(2*dx); /* XXX */
861: eucsfum(w1,w2,wa,wb);
862: cpyum(wa,COEF(a)[0]); cpyum(wb,COEF(b)[0]);
863:
864: /* initialize c to a*g+b*h-1 */
865: mulsfbm(a,g,c); mulsfbm(b,h,wz0); addtosfbm(wz0,c);
866: COEF(COEF(c)[0])[0] = 0;
867:
868: fprintf(stderr,"dy=%d\n",dy);
869: for ( k = 1; k <= dy; k++ ) {
870: fprintf(stderr,".");
871:
872: /* at this point, a*g+b*h = 1 mod y^k, c = a*g+b*h-1 */
873:
874: /* wt = -((a*g+b*h-1)/y^k) */
875: cpyum(COEF(c)[k],wt);
876: for ( i = DEG(wt); i >= 0; i-- )
877: COEF(wt)[i] = _chsgnsf(COEF(wt)[i]);
878:
879: /* compute wa1,wb1 s.t. wa1*g0+wb1*h0 = wt */
880: mulsfum(wa,wt,wa1); DEG(wa1) = divsfum(wa1,COEF(h)[0],q);
881: mulsfum(wa1,COEF(g)[0],wc); subsfum(wt,wc,wd);
882: DEG(wd) = divsfum(wd,COEF(h)[0],wb1);
883:
884: /* c += ((wa1*g+wb1*h)*y^k mod y^(dy+1) */
885: /* wz0 = wa1*y^k */
886: clearbm(dx,wz0);
887: cpyum(wa1,COEF(wz0)[k]);
888:
889: /* wz1 = wz0*g mod y^(dy+1) */
890: clearbm(dx,wz1);
891: mulsfbm(g,wz0,wz1);
892: /* c += wz1 */
893: addtosfbm(wz1,c);
894:
895: /* wz0 = wb1*y^k */
896: clearbm(dx,wz0);
897: cpyum(wb1,COEF(wz0)[k]);
898:
899: /* wz1 = wz0*h mod y^(dy+1) */
900: clearbm(dx,wz1);
901: mulsfbm(h,wz0,wz1);
902: /* c += wz1 */
903: addtosfbm(wz1,c);
904:
905: /* a += wa1*y^k, b += wb1*y^k */
906: cpyum(wa1,COEF(a)[k]);
907: cpyum(wb1,COEF(b)[k]);
908: }
909: fprintf(stderr,"\n");
910: DEG(a) = dy;
911: DEG(b) = dy;
912: *ap = a;
913: *bp = b;
1.3 noro 914: }
915:
1.5 noro 916: /* fl->c[i] = coef_y(f,i) */
917:
1.18 noro 918: void ptosfbm(int dy,P f,BM fl)
1.5 noro 919: {
920: DCP dc;
1.14 noro 921: int d,i,dx;
1.5 noro 922: UM t;
923:
1.14 noro 924: dx = QTOS(DEG(DC(f)));
925: if ( DEG(fl) < dy )
926: error("ptosfbm : invalid input");
927: DEG(fl) = dy;
928: clearbm(dx,fl);
929: t = UMALLOC(dy);
1.5 noro 930: for ( dc = DC(f); dc; dc = NEXT(dc) ) {
931: d = QTOS(DEG(dc));
932: ptosfum(COEF(dc),t);
933: for ( i = 0; i <= DEG(t); i++ )
934: COEF(COEF(fl)[i])[d] = COEF(t)[i];
935: }
1.14 noro 936: for ( i = 0; i <= dy; i++ )
937: degum(COEF(fl)[i],dx);
1.5 noro 938: }
939:
940: /* x : main variable */
941:
1.18 noro 942: void sfbmtop(BM f,V x,V y,P *fp)
1.5 noro 943: {
944: UM *c;
1.14 noro 945: int i,j,d,a,dy;
1.8 noro 946: GFS b;
947: DCP dc0,dc,dct;
948:
1.14 noro 949: dy = DEG(f);
1.8 noro 950: c = COEF(f);
1.14 noro 951: d = degbm(f);
1.8 noro 952:
953: dc0 = 0;
954: for ( i = 0; i <= d; i++ ) {
955: dc = 0;
1.14 noro 956: for ( j = 0; j <= dy; j++ ) {
1.8 noro 957: if ( DEG(c[j]) >= i && (a = COEF(c[j])[i]) ) {
958: NEWDC(dct);
959: STOQ(j,DEG(dct));
1.23 noro 960: iftogfs(a,&b);
1.8 noro 961: COEF(dct) = (P)b;
962: NEXT(dct) = dc;
963: dc = dct;
964: }
965: }
966: if ( dc ) {
967: NEWDC(dct);
968: STOQ(i,DEG(dct));
969: MKP(y,dc,COEF(dct));
970: NEXT(dct) = dc0;
971: dc0 = dct;
972: }
973: }
974: if ( dc0 )
975: MKP(x,dc0,*fp);
976: else
977: *fp = 0;
978: }
979:
1.18 noro 980: void sfsqfr(P f,DCP *dcp)
1.14 noro 981: {
1.18 noro 982: Obj obj;
1.14 noro 983: DCP dc;
984: VL vl;
985:
1.18 noro 986: simp_ff((Obj)f,&obj); f = (P)obj;
1.14 noro 987: clctv(CO,f,&vl);
988: if ( !vl ) {
989: /* f is a const */
990: NEWDC(dc); DEG(dc) = ONE; COEF(dc) = f; NEXT(dc) = 0; *dcp = dc;
991: } else if ( !NEXT(vl) )
992: sfusqfr(f,dcp);
993: else
1.24 noro 994: sqfrsf(f,dcp);
1.14 noro 995: }
996:
1.18 noro 997: void sfusqfr(P f,DCP *dcp)
1.14 noro 998: {
999: DCP dc,dct;
1000: struct oDUM *udc;
1001: V x;
1002: P lc;
1003: int n,i;
1004: UM mf;
1005:
1006: x = VR(f);
1007: n = getdeg(x,f);
1008: mf = W_UMALLOC(n);
1009: ptosfum(f,mf);
1010: lc = COEF(DC(f));
1011: if ( !_isonesf(COEF(mf)[n]) ) {
1012: monicsfum(mf);
1013: }
1014: W_CALLOC(n+1,struct oDUM,udc);
1015: gensqfrsfum(mf,udc);
1016: for ( i = 0, dc = 0; udc[i].f; i++ ) {
1017: NEWDC(dct); STOQ(udc[i].n,DEG(dct));
1018: sfumtop(x,udc[i].f,&COEF(dct));
1019: NEXT(dct) = dc; dc = dct;
1020: }
1021: NEWDC(dct); DEG(dct) = ONE; COEF(dct) = (P)lc; NEXT(dct) = dc;
1022: *dcp = dct;
1023: }
1024:
1.24 noro 1025: #if 0
1.21 noro 1026: void sfbsqfrmain(P f,V x,V y,DCP *dcp)
1027: {
1028: /* XXX*/
1029: }
1030:
1031: /* f is bivariate */
1032:
1.18 noro 1033: void sfbsqfr(P f,V x,V y,DCP *dcp)
1.14 noro 1034: {
1035: P t,rf,cx,cy;
1036: VL vl,rvl;
1.21 noro 1037: DCP dcx,dcy,dct,dc;
1.14 noro 1038: struct oVL vl0,vl1;
1039:
1.21 noro 1040: /* cy(y) = cont(f,x), f /= cy */
1.14 noro 1041: cont_pp_sfp(vl,f,&cy,&t); f = t;
1042: /* rvl = [y,x] */
1043: reordvar(vl,y,&rvl); reorderp(rvl,vl,f,&rf);
1044: /* cx(x) = cont(rf,y), Rf /= cy */
1045: cont_pp_sfp(rvl,rf,&cx,&t); rf = t;
1046: reorderp(vl,rvl,rf,&f);
1047:
1048: /* f -> cx*cy*f */
1.21 noro 1049: sfsqfr(cx,&dcx); dcx = NEXT(dcx);
1050: sfsqfr(cy,&dcy); dcy = NEXT(dcy);
1051: if ( dcx ) {
1052: for ( dct = dcx; NEXT(dct); dct = NEXT(dct) );
1053: NEXT(dct) = dcy;
1054: } else
1055: dcx = dcy;
1056: if ( OID(f) == O_N )
1057: *dcp = dcx;
1058: else {
1059: /* f must be bivariate */
1060: sfbsqfrmain(f,x,y,&dc);
1061: if ( dcx ) {
1062: for ( dct = dcx; NEXT(dct); dct = NEXT(dct) );
1063: NEXT(dct) = dc;
1064: } else
1065: dcx = dc;
1066: *dcp = dcx;
1067: }
1.14 noro 1068: }
1.24 noro 1069: #endif
1.14 noro 1070:
1.8 noro 1071: void sfdtest(P,ML,V,V,DCP *);
1072:
1.21 noro 1073: /* if degbound >= 0 find factor s.t. deg_x(factor) <= degbound */
1074:
1075: void sfbfctr(P f,V x,V y,int degbound,DCP *dcp)
1.8 noro 1076: {
1077: ML list;
1078: P sf;
1.9 noro 1079: GFS ev;
1080: DCP dc,dct;
1081: BM fl;
1.14 noro 1082: int dx,dy;
1.8 noro 1083:
1084: /* sf(x) = f(x+ev) = list->c[0]*list->c[1]*... */
1.28 noro 1085: sfhensel(5,f,x,y,degbound,&ev,&sf,&list);
1.13 noro 1086: if ( list->n == 0 )
1087: error("sfbfctr : short of evaluation points");
1088: else if ( list->n == 1 ) {
1089: /* f is irreducible */
1090: NEWDC(dc); DEG(dc) = ONE; COEF(dc) = f; NEXT(dc) = 0;
1091: *dcp = dc;
1092: return;
1093: }
1.9 noro 1094: sfdtest(sf,list,x,y,&dc);
1.15 noro 1095: if ( ev ) {
1096: dx = getdeg(x,sf);
1097: dy = getdeg(y,sf);
1098: W_BMALLOC(dx,dy,fl);
1099: for ( dct = dc; dct; dct = NEXT(dct) ) {
1100: ptosfbm(dy,COEF(dct),fl);
1101: shiftsfbm(fl,_chsgnsf(FTOIF(CONT(ev))));
1102: sfbmtop(fl,x,y,&COEF(dct));
1103: }
1.9 noro 1104: }
1105: *dcp = dc;
1.26 noro 1106: }
1107:
1108: /* returns shifted f, shifted factors and the eval pt */
1109:
1110: void sfbfctr_shift(P f,V x,V y,int degbound,GFS *evp,P *sfp,DCP *dcp)
1111: {
1112: ML list;
1113: P sf;
1114: GFS ev;
1115: DCP dc,dct;
1116: int dx,dy;
1117:
1118: /* sf(x) = f(x+ev) = list->c[0]*list->c[1]*... */
1.28 noro 1119: sfhensel(5,f,x,y,degbound,&ev,&sf,&list);
1.26 noro 1120: if ( list->n == 0 )
1121: error("sfbfctr_shift : short of evaluation points");
1122: else if ( list->n == 1 ) {
1123: /* f is irreducible */
1124: NEWDC(dc); DEG(dc) = ONE; COEF(dc) = f; NEXT(dc) = 0;
1125: *evp = 0;
1126: *sfp = f;
1127: *dcp = dc;
1128: } else {
1129: sfdtest(sf,list,x,y,dcp);
1130: *evp = ev;
1131: *sfp = sf;
1132: }
1.8 noro 1133: }
1134:
1.14 noro 1135: /* f = f(x,y) = list->c[0]*list->c[1]*... mod y^(list->bound+1) */
1.8 noro 1136:
1.18 noro 1137: void sfdtest(P f,ML list,V x,V y,DCP *dcp)
1.8 noro 1138: {
1.14 noro 1139: int np,dx,dy;
1.20 noro 1140: int i,j,k,bound;
1.8 noro 1141: int *win;
1142: P g,lcg,factor,cofactor,lcyx;
1.18 noro 1143: P csum;
1.8 noro 1144: DCP dcf,dcf0,dc;
1145: BM *c;
1146: BM lcy;
1.20 noro 1147: UM lcg0,lcy0,w;
1148: UM *d1c;
1.8 noro 1149: ML wlist;
1150: struct oVL vl1,vl0;
1151: VL vl;
1.19 noro 1152: int z,dt,dtok;
1.8 noro 1153:
1154: /* vl = [x,y] */
1155: vl0.v = x; vl0.next = &vl1; vl1.v = y; vl1.next = 0; vl = &vl0;
1156:
1.9 noro 1157: /* setup various structures and arrays */
1.14 noro 1158: dx = getdeg(x,f);
1159: dy = getdeg(y,f);
1160: np = list->n;
1161: win = W_ALLOC(np+1);
1162: wlist = W_MLALLOC(np);
1163: wlist->n = list->n;
1.20 noro 1164: bound = wlist->bound = list->bound;
1.8 noro 1165: c = (BM *)COEF(wlist);
1166: bcopy((char *)COEF(list),(char *)c,(int)(sizeof(BM)*np));
1167:
1.14 noro 1168: lcg0 = W_UMALLOC(2*dy);
1.9 noro 1169:
1.8 noro 1170: /* initialize g by f */
1.9 noro 1171: g = f;
1172:
1173: /* initialize lcg */
1174: mulp(vl,g,COEF(DC(g)),&lcg);
1175:
1176: /* initialize lcg0 */
1177: const_term(lcg,lcg0);
1178:
1179: /* initialize csum = lcg(1) */
1180: sfcsump(vl,lcg,&csum);
1.8 noro 1181:
1182: /* initialize lcy by LC(f) */
1.14 noro 1183: W_BMALLOC(0,dy,lcy);
1.9 noro 1184: NEWDC(dc); COEF(dc) = COEF(DC(g)); DEG(dc) = 0;
1.8 noro 1185: NEWP(lcyx); VR(lcyx) = x; DC(lcyx) = dc;
1.14 noro 1186: ptosfbm(dy,lcyx,lcy);
1.8 noro 1187:
1.20 noro 1188: /* initialize lcy0 by LC(f) */
1189: lcy0 = W_UMALLOC(bound);
1190: ptosfum(COEF(DC(g)),lcy0);
1191:
1192: /* ((d-1 coefs)*lcy0 */
1193: d1c = (UM *)W_ALLOC(np*sizeof(UM));
1194: w = W_UMALLOC(2*bound);
1195: for ( i = 1; i < np; i++ ) {
1196: extractcoefbm(c[i],degbm(c[i])-1,w);
1197: d1c[i] = W_UMALLOC(2*bound);
1198: mulsfum(w,lcy0,d1c[i]);
1199: /* d1c[i] = d1c[i] mod y^(bound+1) */
1200: if ( DEG(d1c[i]) > bound ) {
1201: for ( j = DEG(d1c[i]); j > bound; j-- )
1202: COEF(d1c[i])[j] = 0;
1203: degum(d1c[i],bound);
1204: }
1205: }
1206:
1.8 noro 1207: fprintf(stderr,"np = %d\n",np);
1.19 noro 1208: dtok = 0;
1.8 noro 1209: for ( g = f, k = 1, dcf = dcf0 = 0, win[0] = 1, --np, z = 0; ; z++ ) {
1210: if ( !(z % 1000) ) fprintf(stderr,".");
1.20 noro 1211: dt = sfdegtest(dy,bound,d1c,k,win);
1.19 noro 1212: if ( dt )
1213: dtok++;
1214: if ( dt && sfdtestmain(vl,lcg,lcg0,lcy,csum,wlist,
1215: k,win,&factor,&cofactor) ) {
1.8 noro 1216: NEXTDC(dcf0,dcf); DEG(dcf) = ONE; COEF(dcf) = factor;
1217: g = cofactor;
1218:
1219: /* update lcg */
1220: mulp(vl,g,COEF(DC(g)),&lcg);
1221:
1.9 noro 1222: /* update lcg0 */
1223: const_term(lcg,lcg0);
1224:
1225: /* update csum */
1226: sfcsump(vl,lcg,&csum);
1227:
1.19 noro 1228: /* update dy */
1229: dy = getdeg(y,g);
1230:
1.8 noro 1231: /* update lcy */
1.14 noro 1232: clearbm(0,lcy);
1233: COEF(dc) = COEF(DC(g));
1234: ptosfbm(dy,lcyx,lcy);
1.8 noro 1235:
1236: for ( i = 0; i < k - 1; i++ )
1237: for ( j = win[i] + 1; j < win[i + 1]; j++ )
1238: c[j-i-1] = c[j];
1239: for ( j = win[k-1] + 1; j <= np; j++ )
1240: c[j-k] = c[j];
1241: if ( ( np -= k ) < k )
1242: break;
1243: if ( np - win[0] + 1 < k )
1244: if ( ++k > np )
1245: break;
1246: else
1247: for ( i = 0; i < k; i++ )
1248: win[i] = i + 1;
1249: else
1250: for ( i = 1; i < k; i++ )
1251: win[i] = win[0] + i;
1.20 noro 1252:
1253:
1254: /* update lcy0 */
1255: ptosfum(COEF(DC(g)),lcy0);
1256:
1257: /* update d-1 coeffs */
1258: for ( i = 1; i <= np; i++ ) {
1259: extractcoefbm(c[i],degbm(c[i])-1,w);
1260: mulsfum(w,lcy0,d1c[i]);
1261: /* d1c[i] = d1c[1] mod y^(bound+1) */
1262: if ( DEG(d1c[i]) > bound ) {
1263: for ( j = DEG(d1c[i]); j > bound; j-- )
1264: COEF(d1c[i])[j] = 0;
1265: degum(d1c[i],bound);
1266: }
1267: }
1.8 noro 1268: } else if ( !ncombi(1,np,k,win) )
1269: if ( k == np )
1270: break;
1271: else
1272: for ( i = 0, ++k; i < k; i++ )
1273: win[i] = i + 1;
1274: }
1.19 noro 1275: fprintf(stderr,"total %d, omitted by degtest %d\n",z,z-dtok);
1.8 noro 1276: NEXTDC(dcf0,dcf); COEF(dcf) = g;
1277: DEG(dcf) = ONE; NEXT(dcf) = 0; *dcp = dcf0;
1278: }
1279:
1.20 noro 1280: void extractcoefbm(BM f,int dx,UM r)
1.19 noro 1281: {
1282: int j;
1283: UM fj;
1284:
1285: for ( j = DEG(f); j >= 0; j-- ) {
1286: fj = COEF(f)[j];
1.20 noro 1287: if ( fj && DEG(fj) >= dx ) {
1288: COEF(r)[j] = COEF(fj)[dx];
1.19 noro 1289: } else
1290: COEF(r)[j] = 0;
1291: }
1292: degum(r,DEG(f));
1293: }
1294:
1295: /* deg_y(prod mod y^(bound+1)) <= dy ? */
1296:
1.20 noro 1297: int sfdegtest(int dy,int bound,UM *d1c,int k,int *in)
1.19 noro 1298: {
1.20 noro 1299: int i,j;
1300: UM w,w1,wt;
1.19 noro 1301: BM t;
1302:
1303: w = W_UMALLOC(bound);
1304: w1 = W_UMALLOC(bound);
1305: clearum(w,bound);
1306: for ( i = 0; i < k; i++ ) {
1.20 noro 1307: addsfum(w,d1c[in[i]],w1); wt = w; w = w1; w1 = wt;
1.19 noro 1308: }
1.20 noro 1309: return DEG(w) <= dy ? 1 : 0;
1.19 noro 1310: }
1311:
1.9 noro 1312: /* lcy = LC(g), lcg = lcy*g, lcg0 = const part of lcg */
1.19 noro 1313:
1.18 noro 1314: int sfdtestmain(VL vl,P lcg,UM lcg0,BM lcy,P csum,ML list,
1315: int k,int *in,P *fp,P *cofp)
1.8 noro 1316: {
1.14 noro 1317: P fmul,csumg,q,cont;
1.8 noro 1318: V x,y;
1319:
1320: x = vl->v;
1321: y = vl->next->v;
1.9 noro 1322: if (!sfctest(lcg0,lcy,list,k,in))
1.8 noro 1323: return 0;
1324: mulsfbmarray(UDEG(lcg),lcy,list,k,in,x,y,&fmul);
1325: if ( csum ) {
1326: sfcsump(vl,fmul,&csumg);
1327: if ( csumg ) {
1328: if ( !divtp(vl,csum,csumg,&q) )
1329: return 0;
1330: }
1331: }
1.11 noro 1332: if ( divtp_by_sfbm(vl,lcg,fmul,&q) ) {
1.14 noro 1333: cont_pp_sfp(vl,fmul,&cont,fp);
1334: cont_pp_sfp(vl,q,&cont,cofp);
1.8 noro 1335: return 1;
1336: } else
1337: return 0;
1338: }
1339:
1.18 noro 1340: void const_term(P f,UM c)
1.9 noro 1341: {
1342: DCP dc;
1343:
1344: for ( dc = DC(f); dc && DEG(dc); dc = NEXT(dc) );
1345: if ( dc )
1346: ptosfum(COEF(dc),c);
1347: else
1348: DEG(c) = -1;
1349: }
1350:
1.18 noro 1351: void const_term_sfbm(BM f,UM c)
1.9 noro 1352: {
1.14 noro 1353: int i,dy;
1.9 noro 1354:
1.14 noro 1355: dy = DEG(f);
1356: for ( i = 0; i <= dy; i++ )
1.9 noro 1357: if ( DEG(COEF(f)[i]) >= 0 )
1358: COEF(c)[i] = COEF(COEF(f)[i])[0];
1359: else
1360: COEF(c)[i] = 0;
1.14 noro 1361: degum(c,dy);
1.9 noro 1362: }
1363:
1364: /* lcy*(product of const part) | lcg0 ? */
1365:
1.18 noro 1366: int sfctest(UM lcg0,BM lcy,ML list,int k,int *in)
1.8 noro 1367: {
1.14 noro 1368: int dy,i,dr;
1.9 noro 1369: UM t,s,u,w;
1370: BM *l;
1371:
1.14 noro 1372: dy = list->bound;
1373: t = W_UMALLOC(2*dy);
1374: s = W_UMALLOC(2*dy);
1375: u = W_UMALLOC(2*dy);
1376: const_term_sfbm(lcy,t);
1.9 noro 1377: if ( DEG(t) < 0 )
1378: return 1;
1.8 noro 1379:
1.9 noro 1380: l = (BM *)list->c;
1381: for ( i = 0; i < k; i++ ) {
1.14 noro 1382: const_term_sfbm(l[in[i]],s);
1.9 noro 1383: mulsfum(t,s,u);
1.14 noro 1384: if ( DEG(u) > dy )
1385: degum(u,dy);
1.9 noro 1386: w = t; t = u; u = w;
1387: }
1388: cpyum(lcg0,s);
1389: dr = divsfum(s,t,u);
1390: if ( dr >= 0 )
1391: return 0;
1392: else
1.8 noro 1393: return 1;
1394: }
1395:
1396: /* main var of f is x */
1397:
1.18 noro 1398: void mulsfbmarray(int dx,BM lcy,ML list,int k,int *in,V x,V y,P *g)
1.8 noro 1399: {
1.14 noro 1400: int dy,i;
1.18 noro 1401: BM wb0,wb1,t;
1.8 noro 1402: BM *l;
1403:
1.14 noro 1404: dy = list->bound;
1405: W_BMALLOC(dx,dy,wb0); W_BMALLOC(dx,dy,wb1);
1.8 noro 1406: l = (BM *)list->c;
1.14 noro 1407: clearbm(dx,wb0);
1408: mulsfbm(lcy,l[in[0]],wb0);
1.8 noro 1409: for ( i = 1; i < k; i++ ) {
1.14 noro 1410: clearbm(dx,wb1);
1411: mulsfbm(l[in[i]],wb0,wb1);
1.8 noro 1412: t = wb0; wb0 = wb1; wb1 = t;
1413: }
1.14 noro 1414: sfbmtop(wb0,x,y,g);
1.8 noro 1415: }
1416:
1.18 noro 1417: void sfcsump(VL vl,P f,P *s)
1.8 noro 1418: {
1419: P t,u;
1420: DCP dc;
1421:
1422: for ( dc = DC(f), t = 0; dc; dc = NEXT(dc) ) {
1423: addp(vl,COEF(dc),t,&u); t = u;
1424: }
1425: *s = t;
1426: }
1427:
1428: /* *fp = primitive part of f w.r.t. x */
1429:
1.18 noro 1430: void cont_pp_sfp(VL vl,P f,P *cp,P *fp)
1.8 noro 1431: {
1432: V x,y;
1433: int d;
1434: UM t,s,gcd;
1435: DCP dc;
1.14 noro 1436: GFS g;
1.5 noro 1437:
1.8 noro 1438: x = vl->v;
1439: y = vl->next->v;
1440: d = getdeg(y,f);
1.14 noro 1441: if ( d == 0 ) {
1.23 noro 1442: itogfs(1,&g);
1.14 noro 1443: *cp = (P)g;
1.8 noro 1444: *fp = f; /* XXX */
1.14 noro 1445: } else {
1.8 noro 1446: t = W_UMALLOC(2*d);
1447: s = W_UMALLOC(2*d);
1448: gcd = W_UMALLOC(2*d);
1449: dc = DC(f);
1450: ptosfum(COEF(dc),gcd);
1451: for ( dc = NEXT(dc); dc; dc = NEXT(dc) ) {
1452: ptosfum(COEF(dc),t);
1453: gcdsfum(gcd,t,s);
1454: cpyum(s,gcd);
1455: }
1.14 noro 1456: sfumtop(y,gcd,cp);
1457: divsp(vl,f,*cp,fp);
1.5 noro 1458: }
1.11 noro 1459: }
1460:
1.18 noro 1461: int divtp_by_sfbm(VL vl,P f,P g,P *qp)
1.11 noro 1462: {
1463: V x,y;
1464: int fx,fy,gx,gy;
1465: BM fl,gl,ql;
1466: UM *cf,*cg,*cq;
1467: UM hg,q,t,s;
1468: int i,j,dr;
1469:
1470: x = vl->v; y = vl->next->v;
1471: fx = getdeg(x,f); fy = getdeg(y,f);
1472: gx = getdeg(x,g); gy = getdeg(y,g);
1473:
1474: if ( fx < gx || fy < gy )
1475: return 0;
1.14 noro 1476: W_BMALLOC(fx,fy,fl); ptosfbm(fy,f,fl); cf = COEF(fl);
1477: W_BMALLOC(gx,gy,gl); ptosfbm(gy,g,gl); cg = COEF(gl);
1478: W_BMALLOC(fx-gx,fy-gy,ql); cq = COEF(ql);
1.11 noro 1479:
1480: hg = cg[gy];
1481: q = W_UMALLOC(fx); t = W_UMALLOC(fx); s = W_UMALLOC(fx);
1482:
1483: for ( i = fy; i >= gy; i-- ) {
1484: if ( DEG(cf[i]) < 0 )
1485: continue;
1486: dr = divsfum(cf[i],hg,q);
1487: if ( dr >= 0 )
1488: return 0;
1489: if ( DEG(q) > fx-gx )
1490: return 0;
1491: cpyum(q,cq[i-gy]);
1492: for ( j = 0; j <= gy; j++ ) {
1493: mulsfum(cg[j],q,t);
1494: subsfum(cf[j+i-gy],t,s);
1495: cpyum(s,cf[j+i-gy]);
1496: }
1497: }
1498: for ( j = gy-1; j >= 0 && DEG(cf[j]) < 0; j-- );
1499: if ( j >= 0 )
1500: return 0;
1.14 noro 1501: sfbmtop(ql,x,y,qp);
1.18 noro 1502: return 1;
1.16 noro 1503: }
1504:
1505: /* XXX generate an irreducible poly of degree n */
1506:
1.17 noro 1507: extern int current_gfs_q1;
1.22 noro 1508: extern int *current_gfs_ntoi;
1.17 noro 1509:
1.18 noro 1510: void generate_defpoly_sfum(int n,UM *dp)
1.16 noro 1511: {
1.17 noro 1512: UM r,dr,t,g;
1513: UM *f;
1514: int *c,*w;
1515: int max,i,j;
1516:
1517: *dp = r = UMALLOC(n);
1518: DEG(r) = n;
1519: c = COEF(r);
1520: c[n] = _onesf();
1521: max = current_gfs_q1;
1522: w = (int *)ALLOCA(n*sizeof(int));
1523: bzero(w,n*sizeof(int));
1524:
1525: dr = W_UMALLOC(n); t = W_UMALLOC(n); g = W_UMALLOC(n);
1526: f = (UM *)ALLOCA((n+1)*sizeof(UM));
1527: while ( 1 ) {
1528: for ( i = 0; i < n && w[i] == max; i++ );
1529: if ( i == n ) {
1530: /* XXX cannot happen */
1531: error("generate_defpoly_sfum : cannot happen");
1532: }
1533: for ( j = 0; j < i; j++ )
1534: w[j] = 0;
1535: w[i]++;
1.22 noro 1536: if ( !current_gfs_ntoi )
1537: for ( i = 0; i < n; i++ )
1538: c[i] = w[i]?FTOIF(w[i]):0;
1539: else
1540: for ( i = 0; i < n; i++ )
1541: c[i] = w[i]?FTOIF(w[i]-1):0;
1.17 noro 1542: if ( !c[0] )
1543: continue;
1544: diffsfum(r,dr); cpyum(r,t); gcdsfum(t,dr,g);
1545: if ( DEG(g) > 0 )
1546: continue;
1547:
1548: czsfum(r,f);
1549: for ( i = 0; f[i]; i++ );
1550: if ( i == 1 )
1551: return;
1552: }
1.3 noro 1553: }