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