Annotation of OpenXM_contrib/pari/src/modules/galois.c, Revision 1.1.1.1
1.1 maekawa 1: /**************************************************************/
2: /* */
3: /* Galois group for degree between 8 and 11 (included) */
4: /* */
5: /**************************************************************/
6: /* $Id: galois.c,v 1.1.1.1 1999/09/16 13:48:11 karim Exp $ */
7: #include "pari.h"
8: #ifndef WINCE
9: # include <fcntl.h>
10: #endif
11:
12: #define NMAX 11 /* maximum degree */
13:
14: typedef char *OBJ;
15: typedef OBJ *POBJ;
16: typedef OBJ PERM;
17: typedef POBJ GROUP;
18: typedef POBJ RESOLVANTE;
19:
20: static long isin_G_H(GEN po, GEN *r, long n1, long n2);
21:
22: static long N,CAR,PREC,PRMAX,TSCHMAX,coeff[9][10];
23: static char SID[] = { 0,1,2,3,4,5,6,7,8,9,10,11 };
24: static char* str_coset = GPDATADIR"/COS";
25: static char* str_resolv = GPDATADIR"/RES";
26:
27: static long par_N, *par_vec;
28:
29: static void
30: do_par(long k, long n, long m)
31: {
32: long i;
33:
34: if (n<=0)
35: {
36: GEN p1 = new_chunk(par_N+1);
37: for (i=1; i<k ; i++) p1[i] = par_vec[i];
38: for ( ; i<=par_N; i++) p1[i] = 0;
39: return;
40: }
41: if (n<m) m=n;
42: for (i=1; i<=m; i++)
43: {
44: par_vec[k] = i;
45: do_par(k+1, n-i, i);
46: }
47: }
48:
49: /* compute the partitions of m. T[0][0] = p(m) */
50: static long **
51: partitions(long n)
52: {
53: long av,av1,i, j = 1, l = n+1;
54: GEN T;
55:
56: par_vec = new_chunk(l); par_N = n;
57: l = l*sizeof(long);
58: av = avma; do_par(1,n,n); av1 = avma;
59: T = new_chunk((av-av1)/l + 1);
60: for (i=av-l; i>=av1; i-=l) T[j++]=i;
61:
62: if (DEBUGLEVEL > 7)
63: {
64: fprintferr("Partitions of %ld: p(%ld) = %ld\n",n,n,j-1);
65: for (i=1; i<j; i++)
66: {
67: fprintferr("i = %ld: ",i);
68: for (l=1; l<=n; l++)
69: fprintferr("%ld ",((long**)T)[i][l]);
70: fprintferr("\n"); flusherr();
71: }
72: }
73: T[0] = lgeti(1); ((long**)T)[0][0] = j-1;
74: return (long**)T;
75: }
76:
77: /* affect to the permutation x the N arguments that follow */
78: static void
79: _aff(char *x,...)
80: {
81: va_list args; long i;
82: va_start(args,x); for (i=1; i<=N; i++) x[i] = va_arg(args,int);
83: va_end(args);
84: }
85:
86: /* return an array of length |len| from the arguments (for galoismodulo) */
87: static GEN
88: _gr(long len,...)
89: {
90: va_list args;
91: long i, l = labs(len);
92: GEN x = new_chunk(l+1);
93:
94: va_start(args,len); x[0] = len;
95: for (i=1; i<=l; i++) x[i] = va_arg(args,int);
96: va_end(args); return x;
97: }
98:
99: /* create a permutation with the N arguments of the function */
100: static PERM
101: _cr(char a,...)
102: {
103: static char x[NMAX+1];
104: va_list args;
105: long i;
106:
107: va_start(args, a); x[0] = N; x[1] = a;
108: for (i=2; i<=N; i++) x[i] = va_arg(args,int);
109: va_end(args); return x;
110: }
111:
112: static PERM
113: permmul(PERM s1, PERM s2)
114: {
115: long i, n1 = s1[0];
116: PERM s3 = gpmalloc(n1+1);
117: for (i=1; i<=n1; i++) s3[i]=s1[(int)s2[i]];
118: s3[0]=n1; return s3;
119: }
120:
121: static void
122: printperm(PERM perm)
123: {
124: long i, n = perm[0];
125: fprintferr("(");
126: for (i=1; i<=n; i++) fprintferr(" %d",perm[i]);
127: fprintferr(" )\n");
128: }
129:
130: /* ranger dans l'ordre decroissant (quicksort) */
131: static void
132: ranger(long *t, long n)
133: {
134: long tpro,l,r,i,j;
135:
136: l=1+n/2; r=n; tpro=t[1];
137: for(;;)
138: {
139: if (l>1) { l--; tpro=t[l]; }
140: else
141: {
142: tpro=t[r]; t[r]=t[1]; r--;
143: if (r==1) { t[1]=tpro; return; }
144: }
145: i=l;
146: for (j=i<<1; j<=r; j<<=1)
147: {
148: if (j < r && t[j] > t[j+1]) j++;
149: if (t[j] >= tpro) break;
150: t[i] = t[j]; i=j;
151: }
152: t[i]=tpro;
153: }
154: }
155:
156: /* 0 if t1=t2, -1 if t1<t2, 1 if t1>t2 */
157: static long
158: compareupletlong(long *t1,long *t2)
159: {
160: long i;
161: for (i=1; i<=N; i++)
162: if (t1[i]!=t2[i]) return (t1[i] < t2[i])? -1: 1;
163: return 0;
164: }
165:
166: /* return i if typ = TYP[i], 0 otherwise */
167: static long
168: numerotyp(long **TYP, long *galtyp)
169: {
170: long i, nb = TYP[0][0];
171: for (i=1; i<=nb; i++)
172: if (!compareupletlong(galtyp,TYP[i])) return i;
173: return 0;
174: }
175:
176: static int
177: raye(long *g, long num)
178: {
179: long i, nb = labs(g[0]);
180: for (i=1; i<=nb; i++)
181: if (g[i] == num) return 0;
182: return 1;
183: }
184:
185: /* we can never determine the group completely in there */
186: static long
187: rayergroup11(long num, long *gr)
188: {
189: long r = 0;
190:
191: if (CAR)
192: switch(num)
193: {
194: case 2: case 5:
195: if (gr[3]) { gr[3]=0; r++; }
196: case 3: case 6: case 7:
197: if (gr[2]) { gr[2]=0; r++; }
198: case 4:
199: if (gr[1]) { gr[1]=0; r++; }
200: }
201: else
202: switch(num)
203: {
204: case 2: case 3:
205: if (gr[1]) { gr[1]=0; r++; }
206: }
207: return r;
208: }
209:
210: static long
211: rayergroup(long **GR, long num, long *gr)
212: {
213: long i,nbgr,r;
214:
215: if (!GR) return rayergroup11(num,gr);
216: nbgr = lg(GR); r = 0 ;
217: if (CAR)
218: {
219: for (i=1; i<nbgr; i++)
220: if (gr[i] && GR[i][0] < 0 && raye(GR[i],num)) { gr[i]=0; r++; }
221: }
222: else
223: {
224: for (i=1; i<nbgr; i++)
225: if (gr[i] && GR[i][0] > 0 && raye(GR[i],num)) { gr[i]=0; r++; }
226: }
227: return r;
228: }
229:
230: static long
231: galmodp(GEN pol, GEN dpol, long **TYP, long *gr, long **GR)
232: {
233: long p = 0, i,k,l,n,nbremain,dtyp[NMAX+1];
234: byteptr d = diffptr;
235: GEN p1;
236:
237: switch(N)
238: {
239: case 8: nbremain = CAR? 28: 22; break;
240: case 9: nbremain = CAR? 18: 16; break;
241: case 10: nbremain = CAR? 12: 33; break;
242: case 11: nbremain = CAR? 5: 3; break;
243: }
244:
245: k = gr[0]; for (i=1; i<k; i++) gr[i]=1;
246: for (k=1; k<15; k++, d++)
247: {
248: p += *d; if (!*d) err(primer1);
249: if (smodis(dpol,p)) /* p does not divide dpol */
250: {
251: p1 = simplefactmod(pol,stoi(p));
252: p1 = (GEN)p1[1]; l = lg(p1);
253: for (i=1; i<l ; i++) dtyp[i] = itos((GEN)(p1[l-i]));
254: for ( ; i<=N; i++) dtyp[i] = 0;
255: ranger(dtyp,N); n = numerotyp(TYP,dtyp);
256: if (!n) return 1; /* only for N=11 */
257: nbremain -= rayergroup(GR,n,gr);
258: if (nbremain==1) return 1;
259: }
260: }
261: return 0;
262: }
263:
264: static long
265: _aux(GEN z)
266: {
267: return signe(z)? ((expo(z)+165) >> TWOPOTBITS_IN_LONG) - lg(z)
268: : (expo(z)+101) >> TWOPOTBITS_IN_LONG;
269: }
270:
271: static long
272: suffprec(GEN z)
273: {
274: long s,t;
275:
276: if (typ(z)==t_COMPLEX)
277: {
278: s=_aux((GEN)z[1]);
279: t=_aux((GEN)z[2]); return (t>s)? t: s;
280: }
281: return _aux(z);
282: }
283:
284: static void
285: preci(GEN *r, long p)
286: {
287: GEN x;
288: long d,i;
289:
290: if (p>PRMAX) err(talker,"too large precision in preci()");
291: for (d=0; d<TSCHMAX; d++) for (i=1; i<=N; i++)
292: {
293: x = (GEN) r[d][i];
294: if (typ(x)==t_COMPLEX) { setlg(x[1],p); setlg(x[2],p); } else setlg(x,p);
295: }
296: }
297:
298: static long
299: getpreci(GEN *r)
300: {
301: GEN x = (GEN)r[0][1];
302: return (typ(x)==t_COMPLEX)? lg(x[1]): lg(x);
303: }
304:
305: static void
306: new_pol(GEN *r, long *a, long d)
307: {
308: long av,i,j;
309: GEN x, p1;
310: for (i=1; i<=N; i++)
311: {
312: av =avma; p1 = (GEN)r[0][i]; x = gaddsg(a[0], p1);
313: for (j=1; j<=d; j++) x = gaddsg(a[j], gmul(p1,x));
314: r[d][i] = (long) gerepileupto(av,x);
315: }
316: }
317:
318: static void
319: rangeroots(GEN newr, GEN oldr)
320: {
321: long av = avma,i,j,k,z[NMAX+1],t[NMAX+1];
322: GEN diff,diff0;
323:
324: for (i=1; i<=N; i++) t[i]=1;
325: for (i=1; i<=N; i++)
326: {
327: diff0 = gun;
328: for (j=1; j<=N; j++)
329: if (t[j])
330: {
331: diff = gabs(gsub((GEN)oldr[i], (GEN)newr[j]), PREC);
332: if (gcmp(diff,diff0) < 0) { diff0=diff; k=j; }
333: }
334: z[i]=newr[k]; t[k]=0;
335: }
336: avma=av; for (i=1; i<=N; i++) newr[i]=z[i];
337: }
338:
339: /* clean up roots. If root is real replace it by its real part */
340: GEN
341: myroots(GEN p, long prec)
342: {
343: GEN y,x = roots(p,prec);
344: long i,lx = lg(x);
345: for (i=1; i<lx; i++)
346: {
347: y = (GEN)x[i];
348: if (signe(y[2])) break; /* remaining roots are complex */
349: x[i]=y[1]; /* root is real; take real part */
350: }
351: return x;
352: }
353:
354: /* increase the roots accuracy */
355: static void
356: moreprec(GEN po, GEN *r, long pr)
357: {
358: if (DEBUGLEVEL) { fprintferr("$$$$$ New prec = %ld\n",pr); flusherr(); }
359: if (pr > PRMAX)
360: { /* recompute roots */
361: GEN p1;
362: long d = PRMAX + 5;
363:
364: PRMAX = (pr < d)? d: pr;
365: p1 = myroots(po,PRMAX); rangeroots(p1,*r); *r=p1;
366: for (d=1; d<TSCHMAX; d++) new_pol(r,coeff[d],d);
367: }
368: preci(r,pr);
369: }
370:
371: #define setcard_obj(x,n) ((x)[0] = (char*)(n))
372: #define getcard_obj(x) ((long)((x)[0]))
373:
374: /* allocate a list of m arrays of length n (index 0 is codeword) */
375: static POBJ
376: alloc_pobj(long n, long m)
377: {
378: long i, sz = (m+1)*sizeof(OBJ) + (n+1)*m;
379: POBJ g = (POBJ) gpmalloc(sz);
380: OBJ gpt = (OBJ) (g + (m+1));
381:
382: for (i=1; i<=m; i++) { g[i] = gpt; gpt += (n+1); }
383: setcard_obj(g, m); return g;
384: }
385:
386: /* swap args ! Return an empty RESOLVANTE */
387: #define allocresolv(n,m) alloc_pobj(m, n)
388:
389: static GROUP
390: allocgroup(long n, long card)
391: {
392: GROUP gr = alloc_pobj(n,card);
393: long i;
394:
395: for (i=1; i<=card; i++) gr[i][0]=(char)n;
396: return gr;
397: }
398:
399: static char *
400: name(char *pre, long n, long n1, long n2, long no)
401: {
402: static char chn[128];
403: char ch[6];
404:
405: sprintf(chn, "%s%ld_%ld_%ld", pre,n,n1,n2);
406: if (no) { sprintf(ch,"_%ld",no); strcat(chn, ch); }
407: return chn;
408: }
409:
410: static long
411: galopen(char *s)
412: {
413: #ifdef WINCE
414: HANDLE h;
415: short ws[256];
416: MultiByteToWideChar(CP_ACP, 0, s, strlen(s)+1, ws, 256);
417: h = CreateFile(ws,GENERIC_READ,FILE_SHARE_READ,NULL,OPEN_EXISTING,FILE_ATTRIBUTE_NORMAL,NULL);
418: if (h == INVALID_HANDLE_VALUE)
419: err(talker, "galois files not available in this version, sorry");
420: if (DEBUGLEVEL > 3) msgtimer("opening %s", s);
421: return (long)h;
422: #else
423: long fd = open(s,O_RDONLY);
424:
425: if (fd == -1)
426: err(talker,"galois files not available in this version, sorry");
427:
428: if (DEBUGLEVEL > 3) msgtimer("opening %s",s);
429: return fd;
430: #endif
431: }
432:
433: static char
434: bin(char c)
435: {
436: if (c>='0' && c<='9') c=c-'0';
437: else if (c>='A' && c<='Z') c=c-'A'+10;
438: else if (c>='a' && c<='z') c=c-'a'+36;
439: else err(talker,"incorrect value in bin()");
440: return c;
441: }
442:
443: #define BUFFS 512
444: /* fill in g[i][j] (i<=n, j<=m) with (buffered) data from fd */
445: static void
446: read_obj(POBJ g, long fd, long n, long m)
447: {
448: char ch[BUFFS];
449: long i,j, k = BUFFS;
450:
451: i = j = 1;
452: for(;;)
453: {
454: #ifdef WINCE
455: if (k==BUFFS) { DWORD chRead; ReadFile((HANDLE)fd, ch, BUFFS, &chRead, NULL); k=0; }
456: #else
457: if (k==BUFFS) { read(fd,ch,BUFFS); k=0; }
458: #endif
459: g[i][j++] = bin(ch[k++]);
460: if (j>m) { j=1; i++; if (i>n) break; }
461: }
462: #ifdef WINCE
463: CloseHandle((HANDLE)fd); if (DEBUGLEVEL > 3) msgtimer("read_object");
464: #else
465: close(fd); if (DEBUGLEVEL > 3) msgtimer("read_object");
466: #endif
467: }
468: #undef BUFFS
469:
470: /* the first 8 bytes contain size data (possibly padded with \0) */
471: static GROUP
472: lirecoset(long n1, long n2, long n)
473: {
474: GROUP gr, grptr;
475: char c, ch[8];
476: long no,m,cardgr,fd;
477:
478: #ifdef WINCE
479: long chRead;
480: if (n<11 || n1<8)
481: {
482: fd = galopen(name(str_coset, n, n1, n2, 0));
483: ReadFile((HANDLE)fd,&c,1, &chRead, NULL); m=bin(c); ReadFile((HANDLE)fd,&c,1, &chRead, NULL);
484: ReadFile((HANDLE)fd,ch,6, &chRead, NULL); cardgr=atol(ch); gr=allocgroup(m,cardgr);
485: read_obj(gr, fd,cardgr,m); return gr;
486: }
487: m = 11; cardgr = 45360;
488: gr = grptr = allocgroup(n, 8 * cardgr);
489: for (no=1; no<=8; no++)
490: {
491: fd = galopen(name(str_coset, n, n1, n2, no)); ReadFile((HANDLE)fd,ch,8, &chRead, NULL);
492: read_obj(grptr, fd,cardgr,m); grptr += cardgr;
493: }
494: return gr;
495: #else
496: if (n<11 || n1<8)
497: {
498: fd = galopen(name(str_coset, n, n1, n2, 0));
499: read(fd,&c,1); m=bin(c); read(fd,&c,1);
500: read(fd,ch,6); cardgr=atol(ch); gr=allocgroup(m,cardgr);
501: read_obj(gr, fd,cardgr,m); return gr;
502: }
503: m = 11; cardgr = 45360;
504: gr = grptr = allocgroup(n, 8 * cardgr);
505: for (no=1; no<=8; no++)
506: {
507: fd = galopen(name(str_coset, n, n1, n2, no)); read(fd,ch,8);
508: read_obj(grptr, fd,cardgr,m); grptr += cardgr;
509: }
510: return gr;
511: #endif
512: }
513:
514: static RESOLVANTE
515: lireresolv(long n1, long n2, long n, long *nv, long *nm)
516: {
517: RESOLVANTE b;
518: char ch[5];
519: long fd;
520:
521: #ifdef WINCE
522: long chRead;
523: fd = galopen(name(str_resolv, n, n1, n2, 0));
524: ReadFile((HANDLE)fd,ch,5, &chRead, NULL); *nm=atol(ch);
525: ReadFile((HANDLE)fd,ch,3, &chRead, NULL); *nv=atol(ch);
526: b = allocresolv(*nm,*nv);
527: read_obj(b, fd,*nm,*nv); return b;
528: #else
529: fd = galopen(name(str_resolv, n, n1, n2, 0));
530: read(fd,ch,5); *nm=atol(ch);
531: read(fd,ch,3); *nv=atol(ch);
532: b = allocresolv(*nm,*nv);
533: read_obj(b, fd,*nm,*nv); return b;
534: #endif
535: }
536:
537: static GEN
538: monomial(GEN r, PERM bb, long nbv)
539: {
540: long i; GEN p1 = (GEN)r[(int)bb[1]];
541:
542: for (i=2; i<=nbv; i++) p1 = gmul(p1, (GEN)r[(int)bb[i]]);
543: return p1;
544: }
545:
546: static GEN
547: gpolynomial(GEN r, RESOLVANTE aa, long nbm, long nbv)
548: {
549: long i; GEN p1 = monomial(r,aa[1],nbv);
550:
551: for (i=2; i<=nbm; i++) p1 = gadd(p1, monomial(r,aa[i],nbv));
552: return p1;
553: }
554:
555: static void
556: zaux1(GEN *z, GEN *r)
557: {
558: GEN p2,p1;
559: p2=gsub(r[1],gadd(r[2],r[5]));
560: p2=gmul(p2,gsub(r[2],r[5]));
561: p1=gmul(p2,r[1]);
562: p2=gsub(r[3],gadd(r[2],r[4]));
563: p2=gmul(p2,gsub(r[4],r[2]));
564: p1=gadd(p1,gmul(p2,r[3]));
565: p2=gmul(r[5],gsub(r[4],r[5]));
566: z[1]=gadd(p1,gmul(p2,r[4]));
567:
568: p2=gsub(r[1],gadd(r[3],r[4]));
569: p2=gmul(p2,gsub(r[3],r[4]));
570: p1=gmul(p2,r[1]);
571: p2=gsub(r[5],gadd(r[3],r[2]));
572: p2=gmul(p2,gsub(r[2],r[3]));
573: p1=gadd(p1,gmul(p2,r[5]));
574: p2=gmul(r[4],gsub(r[2],r[4]));
575: z[2]=gadd(p1,gmul(p2,r[2]));
576: }
577:
578: static void
579: zaux(GEN *z, GEN *r)
580: {
581: zaux1(z, r); zaux1(z+2, r+5);
582: }
583:
584: static GEN
585: gpoly(GEN rr, long n1, long n2)
586: {
587: GEN p1,p2,z[6], *r = (GEN*)rr; /* syntaxic kludge */
588: long i,j;
589:
590: if (N==8)
591: {
592: if (n1==47 && n2==46)
593: {
594: p1=gsub(r[3],r[4]);
595: for (i=1; i<3; i++) for (j=i+1; j<5; j++) p1 = gmul(p1,gsub(r[i],r[j]));
596: for (i=5; i<8; i++) for (j=i+1; j<9; j++) p1 = gmul(p1,gsub(r[i],r[j]));
597: p2=r[1];
598: for (i=2; i<5; i++) p2=gadd(p2,r[i]);
599: for (i=5; i<9; i++) p2=gsub(p2,r[i]);
600: }
601: else /* n1==44 && n2==40 */
602: {
603: for (i=1; i<5; i++) z[i] = gadd(r[2*i-1],r[2*i]);
604: p1 = gsub(r[1],r[2]);
605: for (i=2; i<5; i++) p1 = gmul(p1,gsub(r[2*i-1],r[2*i]));
606: p2=gsub(z[3],z[4]);
607: for (i=1; i<3; i++) for (j=i+1; j<5; j++) p2 = gmul(p2,gsub(z[i],z[j]));
608: }
609: return gmul(p1,p2);
610: }
611:
612: if (N==9)
613: {
614: if (n1==31 && n2==29)
615: {
616: p1=gsub(r[2],r[3]);
617: for (j=2; j<4; j++) p1 = gmul(p1,gsub(r[1],r[j]));
618: for (i=4; i<6; i++) for (j=i+1; j<7; j++) p1 = gmul(p1,gsub(r[i],r[j]));
619: p2 = gsub(r[8],r[9]);
620: for (j=8; j<10; j++) p2 = gmul(p2,gsub(r[7],r[j]));
621: }
622: else /* ((n1==34 && n2==31) || (n1=33 && n2==30)) */
623: {
624: p1=r[1]; for (i=2; i<4; i++) p1=gadd(p1,r[i]);
625: p2=r[4]; for (i=5; i<7; i++) p2=gadd(p2,r[i]);
626: p1=gmul(p1,p2);
627: p2=r[7]; for (i=8; i<10; i++) p2=gadd(p2,r[i]);
628: }
629: return gmul(p1,p2);
630: }
631:
632: if (N==10)
633: {
634: if ((n1==45 && n2==43) || (n1==44 && n2==42))
635: {
636: p1=r[1]; for (i=2; i<6; i++) p1=gadd(p1,r[i]);
637: p2=r[6]; for (i=7; i<11; i++) p2=gadd(p2,r[i]);
638: return gmul(p1,p2);
639: }
640: else if ((n1==45 && n2==39) || (n1==44 && n2==37))
641: {
642: p1 = gadd(r[1],r[2]);
643: for (i=2; i<6; i++) p1 = gmul(p1,gadd(r[2*i-1],r[2*i]));
644: return p1;
645: }
646: else if ((n1==43 && n2==41) || (n1==33 && n2==27))
647: {
648: p1=gsub(r[4],r[5]);
649: for (i=1; i<4; i++) for (j=i+1; j<6; j++) p1=gmul(p1,gsub(r[i],r[j]));
650: p2=gsub(r[9],r[10]);
651: for (i=6; i<9; i++) for (j=i+1; j<11; j++) p2=gmul(p2,gsub(r[i],r[j]));
652: return gmul(p1,p2);
653: }
654: else if ((n1==43 && n2==33) || (n1==42 && n2==28) || (n1==41 && n2==27)
655: || (n1==40 && n2==21))
656: {
657: p2=gadd(r[2],r[5]);
658: p2=gsub(p2,gadd(r[3],r[4]));
659: p1=gmul(p2,r[1]);
660: p2=gsub(r[3],gadd(r[4],r[5]));
661: p1=gadd(p1,gmul(p2,r[2]));
662: p2=gsub(r[4],r[5]);
663: p1=gadd(p1,gmul(p2,r[3]));
664: z[1]=gadd(p1,gmul(r[4],r[5]));
665:
666: p2=gadd(r[7],r[10]);
667: p2=gsub(p2,gadd(r[8],r[9]));
668: p1=gmul(p2,r[6]);
669: p2=gsub(r[8],gadd(r[9],r[10]));
670: p1=gadd(p1,gmul(p2,r[7]));
671: p2=gsub(r[9],r[10]);
672: p1=gadd(p1,gmul(p2,r[8]));
673: z[2]=gadd(p1,gmul(r[9],r[10]));
674: return gadd(gsqr(z[1]), gsqr(z[2]));
675: }
676: else if (n1==41 && n2==40)
677: {
678: p1=gsub(r[4],r[5]);
679: for (i=1; i<4; i++) for (j=i+1; j<6; j++) p1 = gmul(p1,gsub(r[i],r[j]));
680: p2=gsub(r[9],r[10]);
681: for (i=6; i<9; i++) for (j=i+1; j<11; j++) p2 = gmul(p2,gsub(r[i],r[j]));
682: return gadd(p1,p2);
683: }
684: else if ((n1==41 && n2==22) || (n1==40 && n2==11) || (n1==17 && n2==5)
685: || (n1==10 && n2==4) || (n1==9 && n2==3) || (n1==6 && n2==1))
686: {
687: p1=gadd(r[1],r[6]);
688: for (i=2; i<6; i++) p1=gmul(p1,gadd(r[i],r[i+5]));
689: return p1;
690: }
691: else if ((n1==39 && n2==38) || (n1==29 && n2==25))
692: {
693: for (i=1; i<6; i++) z[i]=gadd(r[2*i-1],r[2*i]);
694: p1=gsub(r[1],r[2]);
695: for (i=2; i<6; i++) p1=gmul(p1,gsub(r[2*i-1],r[2*i]));
696: p2=gsub(z[4],z[5]);
697: for (i=1; i<4; i++) for (j=i+1; j<6; j++) p2=gmul(p2,gsub(z[i],z[j]));
698: return gmul(p1,p2);
699: }
700: else if ((n1==39 && n2==36) || (n1==37 && n2==34) || (n1==29 && n2==23)
701: || (n1==24 && n2==15))
702: {
703: for (i=1; i<6; i++) z[i]=gadd(r[2*i-1],r[2*i]);
704: p1=gsub(z[4],z[5]); p2=gmul(gsub(z[3],z[4]),gsub(z[3],z[5]));
705: for (i=1; i<3; i++) for (j=i+1; j<6; j++) p2=gmul(p2,gsub(z[i],z[j]));
706: return gmul(p1,p2);
707: }
708: else if ((n1==39 && n2==29) || (n1==38 && n2==25) || (n1==37 && n2==24)
709: || (n1==36 && n2==23) || (n1==34 && n2==15))
710: {
711: for (i=1; i<6; i++) z[i]=gadd(r[2*i-1],r[2*i]);
712: p2=gadd(z[2],z[5]); p2=gsub(p2,gadd(z[3],z[4]));
713: p1=gmul(p2,z[1]);
714: p2=gsub(z[3],gadd(z[4],z[5]));
715: p1=gadd(p1,gmul(p2,z[2]));
716: p2=gsub(z[4],z[5]);
717: p1=gadd(p1,gmul(p2,z[3]));
718: p1=gadd(p1,gmul(z[4],z[5])); return gsqr(p1);
719: }
720: else if ((n1==39 && n2==22) || (n1==38 && n2==12) || (n1==36 && n2==11)
721: || (n1==29 && n2== 5) || (n1==25 && n2== 4) || (n1==23 && n2== 3)
722: || (n1==16 && n2== 2) || (n1==14 && n2== 1))
723: {
724: p1=r[1]; for (i=2; i<6; i++) p1=gadd(p1,r[2*i-1]);
725: p2=r[2]; for (i=2; i<6; i++) p2=gadd(p2,r[2*i]);
726: return gmul(p1,p2);
727: }
728: else if (n1==28 && n2==18)
729: {
730: zaux(z, r);
731: p1=gmul(z[1],gsub(z[3],z[4]));
732: p2=gmul(z[2],gadd(z[3],z[4])); return gadd(p1,p2);
733: }
734: else if (n1==27 && n2==20)
735: {
736: zaux(z, r); p1=gmul(z[1],z[3]); p2=gmul(z[2],z[4]);
737: p1 = gsub(p1,p2); p2=r[1];
738: for (i=2; i<6 ; i++) p2=gadd(p2,r[i]);
739: for ( ; i<11; i++) p2=gsub(p2,r[i]);
740: return gmul(p1,p2);
741: }
742: else if (n1==27 && n2==19)
743: {
744: zaux(z, r); p1=gmul(z[1],z[3]); p2=gmul(z[2],z[4]);
745: return gsub(p1,p2);
746: }
747: else if ((n1==27 && n2==17) || (n1==21 && n2==9))
748: {
749: zaux(z, r); p1=gmul(z[1],z[3]); p2=gmul(z[2],z[4]);
750: return gadd(p1,p2);
751: }
752: else if (n1==23 && n2==16)
753: {
754: for (i=1; i<6; i++) z[i]=gadd(r[2*i-1],r[2*i]);
755: p1=gsub(z[1],gadd(z[2],z[5])); p1=gmul(p1,gsub(z[2],z[5]));
756: p2=gmul(p1,z[1]); p1=gsub(z[3],gadd(z[2],z[4]));
757: p1=gmul( p1,gsub(z[4],z[2])); p2=gadd(p2,gmul(p1,z[3]));
758: p1=gmul(z[5],gsub(z[4],z[5])); p2=gadd(p2,gmul(p1,z[4]));
759: p1=gsub(r[1],r[2]);
760: for (i=2; i<6; i++) p1=gmul(p1,gsub(r[2*i-1],r[2*i]));
761: return gmul(p1,p2);
762: }
763: else if (n1==22 && n2==12)
764: {
765: for (i=1; i<6; i++) z[i]=gadd(r[i],r[i+5]);
766: p1=gsub(r[1],r[6]);
767: for (i=2; i<6; i++) p1=gmul(p1,gsub(r[i],r[i+5]));
768: p2=gsub(z[4],z[5]);
769: for (i=1; i<4; i++) for (j=i+1; j<6; j++) p2=gmul(p2,gsub(z[i],z[j]));
770: return gmul(p1,p2);
771: }
772: else if ((n1==22 && n2==11) || (n1==5 && n2==3))
773: {
774: for (i=1; i<6; i++) z[i]=gadd(r[i],r[i+5]);
775: p1=gsub(z[4],z[5]); p2=gmul(gsub(z[3],z[4]),gsub(z[3],z[5]));
776: for (i=1; i<3; i++) for (j=i+1; j<6; j++) p2=gmul(p2,gsub(z[i],z[j]));
777: return gmul(p1,p2);
778: }
779: else if ((n1==22 && n2==5) || (n1==12 && n2==4) || (n1==11 && n2==3))
780: {
781: for (i=1; i<6; i++) z[i]=gadd(r[i],r[i+5]);
782: p2=gadd(z[2],z[5]); p2=gsub(p2,gadd(z[3],z[4])); p1=gmul(p2,z[1]);
783: p2=gsub(z[3],gadd(z[4],z[5])); p1=gadd(p1,gmul(p2,z[2]));
784: p2=gsub(z[4],z[5]);
785: p1=gadd(p1,gmul(p2,z[3])); p1=gadd(p1,gmul(z[4],z[5]));
786: return gsqr(p1);
787: }
788: else if (n1==21 && n2==10)
789: {
790: zaux(z, r); p1=gmul(z[1],z[4]); p2=gmul(z[2],z[3]);
791: return gsub(p1,p2);
792: }
793: }
794: err(talker,"indefinite invariant polynomial in gpoly()");
795: return NULL; /* not reached */
796: }
797:
798: static void
799: tschirn(GEN po, GEN *r, long pr)
800: {
801: long av0 = avma, a[NMAX],v,i,d;
802: GEN h,u;
803:
804: d = TSCHMAX+1;
805: if (d>=N)
806: err(talker,"too large degree for Tschirnhaus transformation in tschirn");
807: if (DEBUGLEVEL)
808: {
809: fprintferr("\n$$$$$ Tschirnhaus transformation of degree %ld: $$$$$\n",d);
810: flusherr();
811: }
812: v=varn(po); h=polun[v];
813: do
814: {
815: avma = av0;
816: for (i=0; i<d; i++)
817: {
818: a[i] = ((mymyrand()>>4) & 7) + 1;
819: h = gaddsg(a[i],gmul(polx[v],h));
820: }
821: u=caract(gmodulcp(h,po),v);
822: }
823: while (lgef(srgcd(u,deriv(u,v))) > 3);
824: if (DEBUGLEVEL>2) { bruterr(u,'g',-1); fprintferr("\n"); flusherr(); }
825:
826: avma = av0; d = TSCHMAX;
827: for (i=0; i<=d; i++) coeff[d][i] = a[i];
828: preci(r,PRMAX); r[d]=cgetg(N+1,t_VEC);
829: new_pol(r,a,d); preci(r,pr); TSCHMAX++;
830: }
831:
832: static GEN
833: get_pol_perm(PERM S1, PERM S2, GEN rr, RESOLVANTE a,
834: long nbm, long nbv)
835: {
836: static long r[NMAX+1];
837: long i;
838:
839: for (i=1; i<=N; i++) r[i] = rr[(int)S1[(int)S2[i]]];
840: return a? gpolynomial(r,a,nbm,nbv): gpoly(r,nbm,nbv);
841: }
842:
843: static void
844: dbg_rac(long nri,long nbracint,long numi[],GEN racint[],long multi[])
845: {
846: long k;
847: if (nbracint>nri+1)
848: fprintferr(" there are %ld rational integer roots:\n",nbracint-nri);
849: else if (nbracint==nri+1)
850: fprintferr(" there is 1 rational integer root:\n");
851: else
852: fprintferr(" there is no rational integer root.\n");
853: for (k=nri+1; k<=nbracint; k++)
854: {
855: fprintferr(" number%2ld: ",numi[k]);
856: bruterr(racint[k],'g',-1); fprintferr(", order %ld.\n",multi[k]);
857: }
858: flusherr();
859: }
860:
861: static GEN
862: is_int(GEN g)
863: {
864: GEN gint,p1;
865: long av;
866:
867: if (typ(g) == t_COMPLEX)
868: {
869: p1 = (GEN)g[2];
870: if (signe(p1) && expo(p1) >= - (bit_accuracy(lg(p1))>>1)) return NULL;
871: g = (GEN)g[1];
872: }
873: gint = ground(g); av=avma; p1 = subri(g,gint);
874: if (signe(p1) && expo(p1) >= - (bit_accuracy(lg(p1))>>1)) return NULL;
875: avma=av; return gint;
876: }
877:
878: static PERM
879: isin_end(PERM S, PERM uu, PERM s0, GEN gpol, long av1)
880: {
881: PERM vv = permmul(S,uu), ww = permmul(vv,s0);
882:
883: if (DEBUGLEVEL)
884: {
885: fprintferr(" testing roots reordering: ");
886: bruterr(gpol,'g',-1); flusherr();
887: }
888: free(vv); avma = av1; return ww;
889: }
890:
891: #define M 2521
892: /* return NULL if not included, the permutation of the roots otherwise */
893: static PERM
894: check_isin(GEN po,GEN *r,long nbm,long nbv, POBJ a, POBJ tau, POBJ ss, PERM s0)
895: {
896: long pr = PREC, av1 = avma, av2,nogr,nocos,init,i,j,k,l,d,nrm,nri,sp;
897: long nbgr,nbcos,nbracint,nbrac,lastnbri,lastnbrm;
898: static long numi[M],numj[M],lastnum[M],multi[M],norac[M],lastnor[M];
899: GEN rr,ro,roint,racint[M];
900: PERM uu;
901:
902: nbcos = getcard_obj(ss);
903: nbgr = getcard_obj(tau);
904: lastnbri = lastnbrm = -1; /* for lint */
905: for (nogr=1; nogr<=nbgr; nogr++)
906: {
907: if (DEBUGLEVEL)
908: { fprintferr(" ----> Group # %ld/%ld:\n",nogr,nbgr); flusherr(); }
909: init = 0;
910: for (d=1; ; d++)
911: {
912: if (d > 1)
913: {
914: if (DEBUGLEVEL)
915: {
916: fprintferr(" all integer roots are double roots\n");
917: fprintferr(" Working with polynomial #%ld:\n", d); flusherr();
918: }
919: if (d > TSCHMAX) { tschirn(po,r,pr); av1 = avma; }
920: }
921: if (!init)
922: {
923: init = 1;
924: for(;;)
925: {
926: av2=avma; rr = r[d-1]; nbrac = nbracint = 0;
927: for (nocos=1; nocos<=nbcos; nocos++)
928: {
929: ro = get_pol_perm(tau[nogr], ss[nocos], rr,a,nbm,nbv);
930: sp = suffprec(ro); if (sp > 0) break;
931: roint = is_int(ro);
932: if (roint)
933: {
934: nbrac++;
935: if (nbrac >= M)
936: {
937: err(warner, "more than %ld rational integer roots\n", M);
938: avma = av1; init = 0; break;
939: }
940: for (j=1; j<=nbracint; j++)
941: if (gegal(roint,racint[j])) { multi[j]++; break; }
942: if (j > nbracint)
943: {
944: nbracint = j; multi[j]=1; numi[j]=nocos;
945: racint[j] = gerepileupto(av2,roint); av2=avma;
946: }
947: numj[nbrac]=nocos; norac[nbrac]=j;
948: }
949: avma=av2;
950: }
951: if (sp <= 0) break;
952: avma = av1; pr+=sp; moreprec(po,r,pr); av1 = avma;
953: }
954: if (!init) continue;
955:
956: if (DEBUGLEVEL) dbg_rac(0,nbracint,numi,racint,multi);
957: for (i=1; i<=nbracint; i++)
958: if (multi[i]==1)
959: {
960: uu = ss[numi[i]];
961: ro = DEBUGLEVEL? get_pol_perm(SID,uu,rr,a,nbm,nbv): (GEN)NULL;
962: return isin_end(tau[nogr], uu, s0, ro, av1);
963: }
964: }
965: else
966: {
967: nrm = nri = 0;
968: for (l=1; l<=lastnbri; l++)
969: {
970: for(;;)
971: {
972: av2=avma; rr = r[d-1]; nbrac=nrm; nbracint=nri;
973: for (k=1; k<=lastnbrm; k++)
974: if (lastnor[k]==l)
975: {
976: nocos = lastnum[k];
977: ro = get_pol_perm(tau[nogr], ss[nocos], rr,a,nbm,nbv);
978: sp = suffprec(ro); if (sp > 0) break;
979: roint = is_int(ro);
980: if (roint)
981: {
982: nbrac++;
983: for (j=nri+1; j<=nbracint; j++)
984: if (gegal(roint,racint[j])) { multi[j]++; break; }
985: if (j > nbracint)
986: {
987: nbracint = j; multi[j]=1; numi[j]=nocos;
988: racint[j] = gerepileupto(av2,roint); av2=avma;
989: }
990: numj[nbrac]=nocos; norac[nbrac]=j;
991: }
992: avma=av2;
993: }
994: if (sp <= 0) break;
995: avma = av1; pr+=sp; moreprec(po,r,pr); av1 = avma;
996: }
997: if (DEBUGLEVEL) dbg_rac(nri,nbracint,numi,racint,multi);
998: for (i=nri+1; i<=nbracint; i++)
999: if (multi[i]==1)
1000: {
1001: uu = ss[numi[i]];
1002: ro = DEBUGLEVEL? get_pol_perm(SID,uu,rr,a,nbm,nbv): (GEN)NULL;
1003: return isin_end(tau[nogr], uu, s0, ro, av1);
1004: }
1005: avma = av1; nri=nbracint; nrm=nbrac;
1006: }
1007: }
1008: avma = av1; if (!nbracint) break;
1009:
1010: lastnbri=nbracint; lastnbrm=nbrac;
1011: for (j=1; j<=nbrac; j++)
1012: { lastnum[j]=numj[j]; lastnor[j]=norac[j]; }
1013: }
1014: }
1015: return NULL;
1016: }
1017: #undef M
1018:
1019: /* BIBLIOTHEQUE POUR LE DEGRE 8 */
1020:
1021: static long
1022: galoisprim8(GEN po, GEN *r)
1023: {
1024: long rep;
1025:
1026: /* PRIM_8_1: */
1027: rep=isin_G_H(po,r,50,43);
1028: if (rep) return CAR? 37: 43;
1029: /* PRIM_8_2: */
1030: if (!CAR) return 50;
1031: /* PRIM_8_3: */
1032: rep=isin_G_H(po,r,49,48);
1033: if (!rep) return 49;
1034: /* PRIM_8_4: */
1035: rep=isin_G_H(po,r,48,36);
1036: if (!rep) return 48;
1037: /* PRIM_8_5: */
1038: rep=isin_G_H(po,r,36,25);
1039: return rep? 25: 36;
1040: }
1041:
1042: static long
1043: galoisimpodd8(GEN po, GEN *r, long nh)
1044: {
1045: long rep;
1046: /* IMPODD_8_1: */
1047: if (nh!=47) goto IMPODD_8_6;
1048: /* IMPODD_8_2: */
1049: rep=isin_G_H(po,r,47,46);
1050: if (!rep) goto IMPODD_8_5;
1051: /* IMPODD_8_4: */
1052: rep=isin_G_H(po,r,46,28);
1053: if (rep) goto IMPODD_8_7; else return 46;
1054:
1055: IMPODD_8_5:
1056: rep=isin_G_H(po,r,47,35);
1057: if (rep) goto IMPODD_8_9; else return 47;
1058:
1059: IMPODD_8_6:
1060: rep=isin_G_H(po,r,44,40);
1061: if (rep) goto IMPODD_8_10; else goto IMPODD_8_11;
1062:
1063: IMPODD_8_7:
1064: rep=isin_G_H(po,r,28,21);
1065: if (rep) return 21; else goto IMPODD_8_33;
1066:
1067: IMPODD_8_9:
1068: rep=isin_G_H(po,r,35,31);
1069: if (rep) goto IMPODD_8_13; else goto IMPODD_8_14;
1070:
1071: IMPODD_8_10:
1072: rep=isin_G_H(po,r,40,26);
1073: if (rep) goto IMPODD_8_15; else goto IMPODD_8_16;
1074:
1075: IMPODD_8_11:
1076: rep=isin_G_H(po,r,44,38);
1077: if (rep) goto IMPODD_8_17; else goto IMPODD_8_18;
1078:
1079: IMPODD_8_12:
1080: rep=isin_G_H(po,r,16,7);
1081: if (rep) goto IMPODD_8_19; else return 16;
1082:
1083: IMPODD_8_13:
1084: rep=isin_G_H(po,r,31,21);
1085: return rep? 21: 31;
1086:
1087: IMPODD_8_14:
1088: rep=isin_G_H(po,r,35,30);
1089: if (rep) goto IMPODD_8_34; else goto IMPODD_8_20;
1090:
1091: IMPODD_8_15:
1092: rep=isin_G_H(po,r,26,16);
1093: if (rep) goto IMPODD_8_12; else goto IMPODD_8_21;
1094:
1095: IMPODD_8_16:
1096: rep=isin_G_H(po,r,40,23);
1097: if (rep) goto IMPODD_8_22; else return 40;
1098:
1099: IMPODD_8_17:
1100: rep=isin_G_H(po,r,38,31);
1101: if (rep) goto IMPODD_8_13; else return 38;
1102:
1103: IMPODD_8_18:
1104: rep=isin_G_H(po,r,44,35);
1105: if (rep) goto IMPODD_8_9; else return 44;
1106:
1107: IMPODD_8_19:
1108: rep=isin_G_H(po,r,7,1);
1109: return rep? 1: 7;
1110:
1111: IMPODD_8_20:
1112: rep=isin_G_H(po,r,35,28);
1113: if (rep) goto IMPODD_8_7; else goto IMPODD_8_23;
1114:
1115: IMPODD_8_21:
1116: rep=isin_G_H(po,r,26,17);
1117: if (rep) goto IMPODD_8_24; else goto IMPODD_8_25;
1118:
1119: IMPODD_8_22:
1120: rep=isin_G_H(po,r,23,8);
1121: if (rep) goto IMPODD_8_26; else return 23;
1122:
1123: IMPODD_8_23:
1124: rep=isin_G_H(po,r,35,27);
1125: if (rep) goto IMPODD_8_27; else goto IMPODD_8_28;
1126:
1127: IMPODD_8_24:
1128: rep=isin_G_H(po,r,17,7);
1129: if (rep) goto IMPODD_8_19; else return 17;
1130:
1131: IMPODD_8_25:
1132: rep=isin_G_H(po,r,26,15);
1133: if (rep) goto IMPODD_8_29; else return 26;
1134:
1135: IMPODD_8_26:
1136: rep=isin_G_H(po,r,8,1);
1137: return rep? 1: 8;
1138:
1139: IMPODD_8_27:
1140: rep=isin_G_H(po,r,27,16);
1141: if (rep) goto IMPODD_8_12; else return 27;
1142:
1143: IMPODD_8_28:
1144: rep=isin_G_H(po,r,35,26);
1145: if (rep) goto IMPODD_8_15; else return 35;
1146:
1147: IMPODD_8_29:
1148: rep=isin_G_H(po,r,15,7);
1149: if (rep) goto IMPODD_8_19;
1150: /* IMPODD_8_30: */
1151: rep=isin_G_H(po,r,15,6);
1152: if (!rep) goto IMPODD_8_32;
1153: /* IMPODD_8_31: */
1154: rep=isin_G_H(po,r,6,1);
1155: return rep? 1: 6;
1156:
1157: IMPODD_8_32:
1158: rep=isin_G_H(po,r,15,8);
1159: if (rep) goto IMPODD_8_26; else return 15;
1160:
1161: IMPODD_8_33:
1162: rep=isin_G_H(po,r,28,16);
1163: if (rep) goto IMPODD_8_12; else return 28;
1164:
1165: IMPODD_8_34:
1166: rep=isin_G_H(po,r,30,21);
1167: return rep? 21: 30;
1168: }
1169:
1170: static long
1171: galoisimpeven8(GEN po, GEN *r, long nh)
1172: {
1173: long rep;
1174: /* IMPEVEN_8_1: */
1175: if (nh!=45) goto IMPEVEN_8_6;
1176: /* IMPEVEN_8_2: */
1177: rep=isin_G_H(po,r,45,42);
1178: if (!rep) goto IMPEVEN_8_5;
1179: /* IMPEVEN_8_4: */
1180: rep=isin_G_H(po,r,42,34);
1181: if (rep) goto IMPEVEN_8_7; else goto IMPEVEN_8_8;
1182:
1183: IMPEVEN_8_5:
1184: rep=isin_G_H(po,r,45,41);
1185: if (rep) goto IMPEVEN_8_9; else return 45;
1186:
1187: IMPEVEN_8_6:
1188: rep=isin_G_H(po,r,39,32);
1189: if (rep) goto IMPEVEN_8_10; else goto IMPEVEN_8_11;
1190:
1191: IMPEVEN_8_7:
1192: rep=isin_G_H(po,r,34,18);
1193: if (rep) goto IMPEVEN_8_21; else goto IMPEVEN_8_45;
1194:
1195: IMPEVEN_8_8:
1196: rep=isin_G_H(po,r,42,33);
1197: if (rep) goto IMPEVEN_8_14; else return 42;
1198:
1199: IMPEVEN_8_9:
1200: rep=isin_G_H(po,r,41,34);
1201: if (rep) goto IMPEVEN_8_7; else goto IMPEVEN_8_15;
1202:
1203: IMPEVEN_8_10:
1204: rep=isin_G_H(po,r,32,22);
1205: if (rep) goto IMPEVEN_8_16; else goto IMPEVEN_8_17;
1206:
1207: IMPEVEN_8_11:
1208: rep=isin_G_H(po,r,39,29);
1209: if (rep) goto IMPEVEN_8_18; else goto IMPEVEN_8_19;
1210:
1211: IMPEVEN_8_12:
1212: rep=isin_G_H(po,r,14,4);
1213: return rep? 4: 14;
1214:
1215: IMPEVEN_8_14:
1216: rep=isin_G_H(po,r,33,18);
1217: if (rep) goto IMPEVEN_8_21; else goto IMPEVEN_8_22;
1218:
1219: IMPEVEN_8_15:
1220: rep=isin_G_H(po,r,41,33);
1221: if (rep) goto IMPEVEN_8_14; else goto IMPEVEN_8_23;
1222:
1223: IMPEVEN_8_16:
1224: rep=isin_G_H(po,r,22,11);
1225: if (rep) goto IMPEVEN_8_24; else goto IMPEVEN_8_25;
1226:
1227: IMPEVEN_8_17:
1228: rep=isin_G_H(po,r,32,13);
1229: if (rep) goto IMPEVEN_8_26; else goto IMPEVEN_8_27;
1230:
1231: IMPEVEN_8_18:
1232: rep=isin_G_H(po,r,29,22);
1233: if (rep) goto IMPEVEN_8_16; else goto IMPEVEN_8_28;
1234:
1235: IMPEVEN_8_19:
1236: rep=isin_G_H(po,r,39,24);
1237: if (rep) goto IMPEVEN_8_29; else return 39;
1238:
1239: IMPEVEN_8_20:
1240: rep=isin_G_H(po,r,9,4);
1241: if (rep) return 4; else goto IMPEVEN_8_30;
1242:
1243: IMPEVEN_8_21:
1244: rep=isin_G_H(po,r,18,10);
1245: if (rep) goto IMPEVEN_8_31; else goto IMPEVEN_8_32;
1246:
1247: IMPEVEN_8_22:
1248: rep=isin_G_H(po,r,33,13);
1249: if (rep) goto IMPEVEN_8_26; else return 33;
1250:
1251: IMPEVEN_8_23:
1252: rep=isin_G_H(po,r,41,29);
1253: if (rep) goto IMPEVEN_8_18; else goto IMPEVEN_8_33;
1254:
1255: IMPEVEN_8_24:
1256: rep=isin_G_H(po,r,11,5);
1257: if (rep) return 5; else goto IMPEVEN_8_34;
1258:
1259: IMPEVEN_8_25:
1260: rep=isin_G_H(po,r,22,9);
1261: if (rep) goto IMPEVEN_8_20; else return 22;
1262:
1263: IMPEVEN_8_26:
1264: rep=isin_G_H(po,r,13,3);
1265: return rep? 3: 13;
1266:
1267: IMPEVEN_8_27:
1268: rep=isin_G_H(po,r,32,12);
1269: if (rep) goto IMPEVEN_8_35; else return 32;
1270:
1271: IMPEVEN_8_28:
1272: rep=isin_G_H(po,r,29,20);
1273: if (rep) goto IMPEVEN_8_36; else goto IMPEVEN_8_37;
1274:
1275: IMPEVEN_8_29:
1276: rep=isin_G_H(po,r,24,14);
1277: if (rep) goto IMPEVEN_8_12; else goto IMPEVEN_8_38;
1278:
1279: IMPEVEN_8_30:
1280: rep=isin_G_H(po,r,9,3);
1281: if (rep) return 3; else goto IMPEVEN_8_39;
1282:
1283: IMPEVEN_8_31:
1284: rep=isin_G_H(po,r,10,2);
1285: return rep? 2: 10;
1286:
1287: IMPEVEN_8_32:
1288: rep=isin_G_H(po,r,18,9);
1289: if (rep) goto IMPEVEN_8_20; else return 18;
1290:
1291: IMPEVEN_8_33:
1292: rep=isin_G_H(po,r,41,24);
1293: if (rep) goto IMPEVEN_8_29; else return 41;
1294:
1295: IMPEVEN_8_34:
1296: rep=isin_G_H(po,r,11,4);
1297: if (rep) return 4; else goto IMPEVEN_8_44;
1298:
1299: IMPEVEN_8_35:
1300: rep=isin_G_H(po,r,12,5);
1301: return rep? 5: 12;
1302:
1303: IMPEVEN_8_36:
1304: rep=isin_G_H(po,r,20,10);
1305: if (rep) goto IMPEVEN_8_31; else return 20;
1306:
1307: IMPEVEN_8_37:
1308: rep=isin_G_H(po,r,29,19);
1309: if (rep) goto IMPEVEN_8_40; else goto IMPEVEN_8_41;
1310:
1311: IMPEVEN_8_38:
1312: rep=isin_G_H(po,r,24,13);
1313: if (rep) goto IMPEVEN_8_26; else goto IMPEVEN_8_42;
1314:
1315: IMPEVEN_8_39:
1316: rep=isin_G_H(po,r,9,2);
1317: return rep? 2: 9;
1318:
1319: IMPEVEN_8_40:
1320: rep=isin_G_H(po,r,19,10);
1321: if (rep) goto IMPEVEN_8_31; else goto IMPEVEN_8_43;
1322:
1323: IMPEVEN_8_41:
1324: rep=isin_G_H(po,r,29,18);
1325: if (rep) goto IMPEVEN_8_21; else return 29;
1326:
1327: IMPEVEN_8_42:
1328: rep=isin_G_H(po,r,24,9);
1329: if (rep) goto IMPEVEN_8_20; else return 24;
1330:
1331: IMPEVEN_8_43:
1332: rep=isin_G_H(po,r,19,9);
1333: if (rep) goto IMPEVEN_8_20; else return 19;
1334:
1335: IMPEVEN_8_44:
1336: rep=isin_G_H(po,r,11,2);
1337: return rep? 2: 11;
1338:
1339: IMPEVEN_8_45:
1340: rep=isin_G_H(po,r,34,14);
1341: if (rep) goto IMPEVEN_8_12; else return 34;
1342: }
1343:
1344: static long
1345: closure8(GEN po)
1346: {
1347: long nbrac,rep;
1348: GEN r[NMAX];
1349:
1350: r[0]=myroots(po,PRMAX); nbrac=lg(r[0])-1;
1351: if (nbrac!=N) err(talker,"incompatible number of roots in closure8()");
1352: preci(r,PREC);
1353: if (!CAR)
1354: {
1355: /* CLOS_8_1: */
1356: rep=isin_G_H(po,r,50,47);
1357: if (rep) return galoisimpodd8(po,r,47);
1358: /* CLOS_8_2: */
1359: rep=isin_G_H(po,r,50,44);
1360: if (rep) return galoisimpodd8(po,r,44);
1361: }
1362: else
1363: {
1364: /* CLOS_8_3: */
1365: rep=isin_G_H(po,r,49,45);
1366: if (rep) return galoisimpeven8(po,r,45);
1367: /* CLOS_8_4: */
1368: rep=isin_G_H(po,r,49,39);
1369: if (rep) return galoisimpeven8(po,r,39);
1370: }
1371: return galoisprim8(po,r);
1372: }
1373:
1374: static GROUP
1375: initgroup(long n, long nbgr)
1376: {
1377: GROUP t = allocgroup(n,nbgr);
1378: t[1] = SID; return t;
1379: }
1380:
1381: static PERM
1382: data8(long n1, long n2, GROUP *t)
1383: {
1384: switch(n1)
1385: {
1386: case 7: if (n2!=1) break;
1387: *t=initgroup(N,2);
1388: _aff((*t)[2], 1, 2, 3, 4, 6, 5, 8, 7);
1389: return SID;
1390: case 9: if (n2!=4) break;
1391: *t=initgroup(N,2);
1392: _aff((*t)[2], 1, 2, 4, 3, 5, 6, 8, 7);
1393: return SID;
1394: case 10: if (n2!=2) break;
1395: *t=initgroup(N,2);
1396: _aff((*t)[2], 1, 2, 3, 4, 6, 5, 8, 7);
1397: return SID;
1398: case 11:
1399: switch(n2)
1400: {
1401: case 2:
1402: *t=initgroup(N,2);
1403: _aff((*t)[2], 1, 2, 5, 6, 3, 4, 8, 7);
1404: return _cr(1, 3, 5, 8, 2, 4, 6, 7);
1405: case 4:
1406: *t=initgroup(N,1);
1407: return _cr(1, 3, 7, 5, 2, 4, 8, 6);
1408: }break;
1409: case 14: if (n2!=4) break;
1410: *t=initgroup(N,1);
1411: return _cr(1, 2, 4, 3, 5, 6, 8, 7);
1412: case 15: if (n2!=6 && n2!=8) break;
1413: *t=initgroup(N,2);
1414: _aff((*t)[2], 1, 2, 3, 4, 6, 5, 8, 7);
1415: return SID;
1416: case 16: if (n2!=7) break;
1417: *t=initgroup(N,2);
1418: _aff((*t)[2], 1, 2, 3, 4, 5, 6, 8, 7);
1419: return SID;
1420: case 18:
1421: switch(n2)
1422: {
1423: case 9: *t=initgroup(N,3);
1424: _aff((*t)[2], 1, 5, 3, 7, 2, 6, 4, 8);
1425: _aff((*t)[3], 1, 2, 3, 4, 6, 5, 8, 7);
1426: return SID;
1427: case 10: *t=initgroup(N,3);
1428: _aff((*t)[2], 1, 6, 3, 8, 2, 5, 4, 7);
1429: _aff((*t)[3], 1, 5, 3, 7, 2, 6, 4, 8);
1430: return SID;
1431: }break;
1432: case 19: if (n2!=9) break;
1433: *t=initgroup(N,1);
1434: return _cr(1, 5, 3, 8, 2, 6, 4, 7);
1435: case 20: if (n2!=10) break;
1436: *t=initgroup(N,2);
1437: _aff((*t)[2], 1, 2, 3, 4, 5, 6, 8, 7);
1438: return SID;
1439: case 22:
1440: switch(n2)
1441: {
1442: case 9: *t=initgroup(N,6);
1443: _aff((*t)[2], 1, 2, 7, 8, 3, 4, 6, 5);
1444: _aff((*t)[3], 1, 2, 7, 8, 3, 4, 5, 6);
1445: _aff((*t)[4], 1, 2, 5, 6, 3, 4, 8, 7);
1446: _aff((*t)[5], 1, 2, 5, 6, 3, 4, 7, 8);
1447: _aff((*t)[6], 1, 2, 3, 4, 5, 6, 8, 7);
1448: return _cr(1, 3, 5, 7, 2, 4, 6, 8);
1449: case 11: *t=initgroup(N,6);
1450: _aff((*t)[2], 1, 2, 5, 6, 7, 8, 4, 3);
1451: _aff((*t)[3], 1, 2, 5, 6, 7, 8, 3, 4);
1452: _aff((*t)[4], 1, 2, 3, 4, 7, 8, 6, 5);
1453: _aff((*t)[5], 1, 2, 3, 4, 7, 8, 5, 6);
1454: _aff((*t)[6], 1, 2, 3, 4, 5, 6, 8, 7);
1455: return SID;
1456: }break;
1457: case 23: if (n2!=8) break;
1458: *t=initgroup(N,1);
1459: return _cr(1, 2, 3, 4, 6, 5, 8, 7);
1460: case 26: if (n2!=15 && n2!=17) break;
1461: *t=initgroup(N,2);
1462: _aff((*t)[2], 1, 2, 3, 4, 5, 6, 8, 7);
1463: return SID;
1464: case 28: if (n2!=21) break;
1465: *t=initgroup(N,1);
1466: return _cr(1, 2, 3, 4, 7, 8, 5, 6);
1467: case 29: if (n2!=18 && n2!=19) break;
1468: *t=initgroup(N,2);
1469: _aff((*t)[2], 1, 2, 3, 4, 5, 6, 8, 7);
1470: return SID;
1471: case 30: if (n2!=21) break;
1472: *t=initgroup(N,1);
1473: return _cr(1, 2, 3, 4, 7, 8, 5, 6);
1474: case 31: if (n2!=21) break;
1475: *t=initgroup(N,3);
1476: _aff((*t)[2], 1, 2, 3, 4, 7, 8, 5, 6);
1477: _aff((*t)[3], 1, 2, 5, 6, 7, 8, 3, 4);
1478: return SID;
1479: case 32: if (n2!=12 && n2!=13) break;
1480: *t=initgroup(N,2);
1481: _aff((*t)[2], 1, 2, 3, 4, 5, 6, 8, 7);
1482: return SID;
1483: case 33:
1484: switch(n2)
1485: {
1486: case 13: *t=initgroup(N,1);
1487: return _cr(1, 5, 2, 6, 3, 7, 4, 8);
1488: case 18: *t=initgroup(N,1);
1489: return _cr(1, 2, 5, 6, 3, 4, 7, 8);
1490: }break;
1491: case 34:
1492: switch(n2)
1493: {
1494: case 14: *t=initgroup(N,3);
1495: _aff((*t)[2], 1, 2, 3, 4, 5, 8, 6, 7);
1496: _aff((*t)[3], 1, 2, 3, 4, 5, 7, 8, 6);
1497: return _cr(1, 5, 2, 6, 3, 7, 4, 8);
1498: case 18: *t=initgroup(N,1);
1499: return _cr(1, 2, 5, 6, 3, 4, 8, 7);
1500: }break;
1501: case 39: if (n2!=24) break;
1502: *t=initgroup(N,2);
1503: _aff((*t)[2], 1, 2, 3, 4, 5, 6, 8, 7);
1504: return SID;
1505: case 40: if (n2!=23) break;
1506: *t=initgroup(N,2);
1507: _aff((*t)[2], 1, 2, 3, 4, 5, 6, 8, 7);
1508: return SID;
1509: case 41:
1510: switch(n2)
1511: {
1512: case 24: *t=initgroup(N,1);
1513: return _cr(1, 5, 2, 6, 3, 7, 4, 8);
1514: case 29: *t=initgroup(N,1);
1515: return _cr(1, 2, 5, 6, 3, 4, 7, 8);
1516: }break;
1517: case 42: if (n2!=34) break;
1518: *t=initgroup(N,1);
1519: return _cr(1, 2, 3, 4, 5, 6, 8, 7);
1520: case 45: if (n2!=41 && n2!=42) break;
1521: *t=initgroup(N,2);
1522: _aff((*t)[2], 1, 2, 3, 4, 5, 6, 8, 7);
1523: return SID;
1524: case 46: if (n2!=28) break;
1525: *t=initgroup(N,1);
1526: return _cr(1, 2, 5, 6, 3, 4, 7, 8);
1527: case 47: if (n2!=35) break;
1528: *t=initgroup(N,1);
1529: return _cr(1, 2, 5, 6, 3, 4, 7, 8);
1530: case 49: if (n2!=48) break;
1531: *t=initgroup(N,2);
1532: _aff((*t)[2], 1, 2, 3, 4, 5, 6, 8, 7);
1533: return SID;
1534: }
1535: *t=initgroup(N,1); return SID;
1536: }
1537:
1538: static long
1539: galoismodulo8(GEN pol, GEN dpol)
1540: {
1541: long av = avma, res, gr[51];
1542: long **TYP = partitions(8), **GR = (long**)cgeti(49);
1543:
1544: /* List of possible types in group j: GR[j][0] = #GR[j] if
1545: * the group is odd, - #GR[j] if even */
1546: GR[ 1]= _gr( 4, 1,5,15,22);
1547: GR[ 2]= _gr( -3, 1,5,15);
1548: GR[ 3]= _gr( -2, 1,5);
1549: GR[ 4]= _gr( -3, 1,5,15);
1550: GR[ 5]= _gr( -3, 1,5,15);
1551: GR[ 6]= _gr( 5, 1,4,5,15,22);
1552: GR[ 7]= _gr( 5, 1,3,5,15,22);
1553: GR[ 8]= _gr( 5, 1,4,5,15,22);
1554: GR[ 9]= _gr( -4, 1,3,5,15);
1555: GR[10]= _gr( -4, 1,3,5,15);
1556: GR[11]= _gr( -4, 1,3,5,15);
1557: GR[12]= _gr( -5, 1,5,9,15,20);
1558: GR[13]= _gr( -4, 1,5,9,20);
1559: GR[14]= _gr( -4, 1,5,9,15);
1560: GR[15]= _gr( 6, 1,3,4,5,15,22);
1561: GR[16]= _gr( 5, 1,3,5,15,22);
1562: GR[17]= _gr( 7, 1,3,5,11,13,15,22);
1563: GR[18]= _gr( -4, 1,3,5,15);
1564: GR[19]= _gr( -5, 1,3,5,12,15);
1565: GR[20]= _gr( -4, 1,3,5,15);
1566: GR[21]= _gr( 5, 1,3,5,13,15);
1567: GR[22]= _gr( -4, 1,3,5,15);
1568: GR[23]= _gr( 7, 1,4,5,9,15,20,22);
1569: GR[24]= _gr( -6, 1,3,5,9,15,20);
1570: GR[25]= _gr( -3, 1,5,21);
1571: GR[26]= _gr( 8, 1,3,4,5,11,13,15,22);
1572: GR[27]= _gr( 8, 1,2,3,4,5,13,15,22);
1573: GR[28]= _gr( 7, 1,3,5,12,13,15,22);
1574: GR[29]= _gr( -5, 1,3,5,12,15);
1575: GR[30]= _gr( 7, 1,3,4,5,11,13,15);
1576: GR[31]= _gr( 7, 1,2,3,4,5,13,15);
1577: GR[32]= _gr( -6, 1,3,5,9,15,20);
1578: GR[33]= _gr( -6, 1,3,5,9,15,20);
1579: GR[34]= _gr( -5, 1,3,5,9,15);
1580: GR[35]= _gr( 10, 1,2,3,4,5,11,12,13,15,22);
1581: GR[36]= _gr( -5, 1,5,9,20,21);
1582: GR[37]= _gr( -5, 1,5,9,15,21);
1583: GR[38]= _gr( 11, 1,2,3,4,5,9,10,13,15,19,20);
1584: GR[39]= _gr( -7, 1,3,5,9,12,15,20);
1585: GR[40]= _gr( 10, 1,3,4,5,9,11,13,15,20,22);
1586: GR[41]= _gr( -7, 1,3,5,9,12,15,20);
1587: GR[42]= _gr( -8, 1,3,5,6,8,9,15,20);
1588: GR[43]= _gr( 8, 1,4,5,9,15,19,21,22);
1589: GR[44]= _gr( 14, 1,2,3,4,5,9,10,11,12,13,15,19,20,22);
1590: GR[45]= _gr( -9, 1,3,5,6,8,9,12,15,20);
1591: GR[46]= _gr( 10, 1,3,5,6,8,9,12,13,15,22);
1592: GR[47]= _gr( 16, 1,2,3,4,5,6,7,8,9,11,12,13,14,15,20,22);
1593: GR[48]= _gr( -8, 1,3,5,9,12,15,20,21);
1594:
1595: gr[0]=51; res = galmodp(pol,dpol,TYP,gr,GR);
1596: avma=av; if (!res) return 0;
1597: return CAR? 49: 50;
1598: }
1599:
1600: /* BIBLIOTHEQUE POUR LE DEGRE 9 */
1601: static long
1602: galoisprim9(GEN po, GEN *r)
1603: {
1604: long rep;
1605:
1606: if (!CAR)
1607: {
1608: /* PRIM_9_1: */
1609: rep=isin_G_H(po,r,34,26);
1610: if (!rep) return 34;
1611: /* PRIM_9_2: */
1612: rep=isin_G_H(po,r,26,19);
1613: if (!rep) return 26;
1614: /* PRIM_9_3: */
1615: rep=isin_G_H(po,r,19,16);
1616: if (rep) return 16;
1617: /* PRIM_9_4: */
1618: rep=isin_G_H(po,r,19,15);
1619: return rep? 15: 19;
1620: }
1621: /* PRIM_9_5: */
1622: rep=isin_G_H(po,r,33,32);
1623: if (!rep) goto PRIM_9_7;
1624: /* PRIM_9_6: */
1625: rep=isin_G_H(po,r,32,27);
1626: return rep? 27: 32;
1627:
1628: PRIM_9_7:
1629: rep=isin_G_H(po,r,33,23);
1630: if (!rep) return 33;
1631: /* PRIM_9_8: */
1632: rep=isin_G_H(po,r,23,14);
1633: if (!rep) return 23;
1634: /* PRIM_9_9: */
1635: rep=isin_G_H(po,r,14,9);
1636: return rep? 9: 14;
1637: }
1638:
1639: static long
1640: galoisimpodd9(GEN po, GEN *r)
1641: {
1642: long rep;
1643:
1644: /* IMPODD_9_1: */
1645: rep=isin_G_H(po,r,31,29);
1646: if (!rep) goto IMPODD_9_5;
1647: /* IMPODD_9_2: */
1648: rep=isin_G_H(po,r,29,20);
1649: if (!rep) return 29;
1650: IMPODD_9_3:
1651: rep=isin_G_H(po,r,20,12);
1652: if (!rep) return 20;
1653: IMPODD_9_4:
1654: rep=isin_G_H(po,r,12,4);
1655: return rep? 4: 12;
1656:
1657: IMPODD_9_5:
1658: rep=isin_G_H(po,r,31,28);
1659: if (!rep) goto IMPODD_9_9;
1660: /* IMPODD_9_6: */
1661: rep=isin_G_H(po,r,28,22);
1662: if (!rep) return 28;
1663: IMPODD_9_7:
1664: rep=isin_G_H(po,r,22,13);
1665: if (!rep) return 22;
1666: IMPODD_9_8:
1667: rep=isin_G_H(po,r,13,4);
1668: return rep? 4: 13;
1669:
1670: IMPODD_9_9:
1671: rep=isin_G_H(po,r,31,24);
1672: if (!rep) return 31;
1673: /* IMPODD_9_10: */
1674: rep=isin_G_H(po,r,24,22);
1675: if (rep) goto IMPODD_9_7;
1676: /* IMPODD_9_11: */
1677: rep=isin_G_H(po,r,24,20);
1678: if (rep) goto IMPODD_9_3;
1679: /* IMPODD_9_12: */
1680: rep=isin_G_H(po,r,24,18);
1681: if (!rep) return 24;
1682: /* IMPODD_9_13: */
1683: rep=isin_G_H(po,r,18,13);
1684: if (rep) goto IMPODD_9_8;
1685: /* IMPODD_9_14: */
1686: rep=isin_G_H(po,r,18,12);
1687: if (rep) goto IMPODD_9_4;
1688: /* IMPODD_9_15: */
1689: rep=isin_G_H(po,r,18,8);
1690: if (!rep) return 18;
1691: /* IMPODD_9_16: */
1692: rep=isin_G_H(po,r,8,4);
1693: return rep? 4: 8;
1694: }
1695:
1696: static long
1697: galoisimpeven9(GEN po, GEN *r)
1698: {
1699: long rep;
1700:
1701: /* IMPEVEN_9_1: */
1702: rep=isin_G_H(po,r,30,25);
1703: if (!rep) goto IMPEVEN_9_7;
1704: /* IMPEVEN_9_2: */
1705: rep=isin_G_H(po,r,25,17);
1706: if (!rep) return 25;
1707: IMPEVEN_9_3:
1708: rep=isin_G_H(po,r,17,7);
1709: if (!rep) goto IMPEVEN_9_5;
1710: IMPEVEN_9_4:
1711: rep=isin_G_H(po,r,7,2);
1712: return rep? 2: 7;
1713:
1714: IMPEVEN_9_5:
1715: rep=isin_G_H(po,r,17,6);
1716: if (!rep) return 17;
1717: IMPEVEN_9_6:
1718: rep=isin_G_H(po,r,6,1);
1719: return rep? 1: 6;
1720:
1721: IMPEVEN_9_7:
1722: rep=isin_G_H(po,r,30,21);
1723: if (!rep) return 30;
1724: /* IMPEVEN_9_8: */
1725: rep=isin_G_H(po,r,21,17);
1726: if (rep) goto IMPEVEN_9_3;
1727: /* IMPEVEN_9_9: */
1728: rep=isin_G_H(po,r,21,11);
1729: if (!rep) goto IMPEVEN_9_13;
1730: /* IMPEVEN_9_10: */
1731: rep=isin_G_H(po,r,11,7);
1732: if (rep) goto IMPEVEN_9_4;
1733: /* IMPEVEN_9_11: */
1734: rep=isin_G_H(po,r,11,5);
1735: if (!rep) return 11;
1736: /* IMPEVEN_9_12: */
1737: rep=isin_G_H(po,r,5,2);
1738: return rep? 2: 5;
1739:
1740: IMPEVEN_9_13:
1741: rep=isin_G_H(po,r,21,10);
1742: if (!rep) return 21;
1743: /* IMPEVEN_9_14: */
1744: rep=isin_G_H(po,r,10,6);
1745: if (rep) goto IMPEVEN_9_6;
1746: /* IMPEVEN_9_15: */
1747: rep=isin_G_H(po,r,10,3);
1748: if (!rep) return 10;
1749: /* IMPEVEN_9_16: */
1750: rep=isin_G_H(po,r,3,1);
1751: return rep? 1: 3;
1752: }
1753:
1754: static long
1755: closure9(GEN po)
1756: {
1757: long nbrac,rep;
1758: GEN r[NMAX];
1759:
1760: r[0]=myroots(po,PRMAX); nbrac=lg(r[0])-1;
1761: if (nbrac!=N) err(talker,"incompatible number of roots in closure9()");
1762: preci(r,PREC);
1763: if (!CAR)
1764: {
1765: /* CLOS_9_1: */
1766: rep=isin_G_H(po,r,34,31);
1767: if (rep) return galoisimpodd9(po,r);
1768: }
1769: else
1770: {
1771: /* CLOS_9_2: */
1772: rep=isin_G_H(po,r,33,30);
1773: if (rep) return galoisimpeven9(po,r);
1774: }
1775: return galoisprim9(po,r);
1776: }
1777:
1778: static PERM
1779: data9(long n1, long n2, GROUP *t)
1780: {
1781: switch(n1)
1782: {
1783: case 6: if (n2!=1) break;
1784: *t=initgroup(N,3);
1785: _aff((*t)[2], 1, 2, 3, 4, 5, 6, 8, 9, 7);
1786: _aff((*t)[3], 1, 2, 3, 4, 5, 6, 9, 7, 8);
1787: return SID;
1788: case 7: if (n2!=2) break;
1789: *t=initgroup(N,3);
1790: _aff((*t)[2], 1, 2, 3, 4, 5, 6, 8, 9, 7);
1791: _aff((*t)[3], 1, 2, 3, 4, 5, 6, 9, 7, 8);
1792: return SID;
1793: case 8: if (n2!=4) break;
1794: *t=initgroup(N,2);
1795: _aff((*t)[2], 1, 4, 7, 2, 5, 8, 3, 6, 9);
1796: return SID;
1797: case 12: if (n2!=4) break;
1798: *t=initgroup(N,3);
1799: _aff((*t)[2], 1, 2, 3, 4, 5, 6, 8, 9, 7);
1800: _aff((*t)[3], 1, 2, 3, 4, 5, 6, 9, 7, 8);
1801: return SID;
1802: case 13: if (n2!=4) break;
1803: *t=initgroup(N,1);
1804: return _cr(1, 4, 7, 2, 5, 8, 3, 6, 9);
1805: case 14: if (n2!=9) break;
1806: *t=initgroup(N,3);
1807: _aff((*t)[2], 1, 2, 3, 5, 6, 4, 9, 7, 8);
1808: _aff((*t)[3], 1, 2, 3, 6, 4, 5, 8, 9, 7);
1809: return SID;
1810: case 17: if (n2!=6) break;
1811: *t=initgroup(N,2);
1812: _aff((*t)[2], 1, 2, 3, 7, 8, 9, 4, 5, 6);
1813: return SID;
1814: case 21: if (n2!=10) break;
1815: *t=initgroup(N,2);
1816: _aff((*t)[2], 1, 2, 3, 7, 8, 9, 4, 5, 6);
1817: return SID;
1818: case 33: if (n2!=32) break;
1819: *t=initgroup(N,2);
1820: _aff((*t)[2], 1, 2, 3, 4, 5, 6, 7, 9, 8);
1821: return SID;
1822: }
1823: *t=initgroup(N,1); return SID;
1824: }
1825:
1826: static long
1827: galoismodulo9(GEN pol, GEN dpol)
1828: {
1829: long av = avma, res, gr[35];
1830: long **TYP = partitions(9), **GR = (long**) cgeti(33);
1831:
1832: /* 42 TYPES ORDONNES CROISSANT (T[1],...,T[30])*/
1833:
1834: GR[ 1]= _gr( -3, 1,12,30);
1835: GR[ 2]= _gr( -2, 1,12);
1836: GR[ 3]= _gr( -4, 1,5,12,30);
1837: GR[ 4]= _gr( 4, 1,4,12,26);
1838: GR[ 5]= _gr( -3, 1,5,12);
1839: GR[ 6]= _gr( -4, 1,10,12,30);
1840: GR[ 7]= _gr( -3, 1,10,12);
1841: GR[ 8]= _gr( 5, 1,4,5,12,26);
1842: GR[ 9]= _gr( -4, 1,5,12,18);
1843: GR[10]= _gr( -6, 1,5,10,12,25,30);
1844: GR[11]= _gr( -5, 1,5,10,12,25);
1845: GR[12]= _gr( 5, 1,4,10,12,26);
1846: GR[13]= _gr( 5, 1,4,10,12,26);
1847: GR[14]= _gr( -4, 1,5,12,18);
1848: GR[15]= _gr( 5, 1,5,12,18,29);
1849: GR[16]= _gr( 6, 1,4,5,12,18,26);
1850: GR[17]= _gr( -5, 1,6,10,12,30);
1851: GR[18]= _gr( 7, 1,4,5,10,12,25,26);
1852: GR[19]= _gr( 7, 1,4,5,12,18,26,29);
1853: GR[20]= _gr( 9, 1,4,6,9,10,12,24,26,30);
1854: GR[21]= _gr( -7, 1,5,6,10,12,25,30);
1855: GR[22]= _gr( 7, 1,4,6,10,12,26,30);
1856: GR[23]= _gr( -6, 1,5,10,12,18,25);
1857: GR[24]= _gr( 11, 1,4,5,6,9,10,12,24,25,26,30);
1858: GR[25]= _gr( -7, 1,3,6,8,10,12,30);
1859: GR[26]= _gr( 9, 1,4,5,10,12,18,25,26,29);
1860: GR[27]= _gr( -5, 1,5,12,27,30);
1861: GR[28]= _gr( 12, 1,2,3,4,6,7,8,10,11,12,26,30);
1862: GR[29]= _gr( 12, 1,3,4,6,8,9,10,12,15,24,26,30);
1863: GR[30]= _gr(-11, 1,3,5,6,8,10,12,14,17,25,30);
1864: GR[31]= _gr( 19, 1,2,3,4,5,6,7,8,9,10,11,12,14,15,17,24,25,26,30);
1865: GR[32]= _gr( -7, 1,5,10,12,25,27,30);
1866:
1867: gr[0]=35; res = galmodp(pol,dpol,TYP,gr,GR);
1868: avma=av; if (!res) return 0;
1869: return CAR? 33: 34;
1870: }
1871:
1872: /* BIBLIOTHEQUE POUR LE DEGRE 10 */
1873: static long
1874: galoisprim10(GEN po, GEN *r)
1875: {
1876: long rep;
1877: if (CAR)
1878: {
1879: /* PRIM_10_1: */
1880: rep=isin_G_H(po,r,44,31);
1881: if (!rep) return 44;
1882: /* PRIM_10_2: */
1883: rep=isin_G_H(po,r,31,26);
1884: if (!rep) return 31;
1885: /* PRIM_10_3: */
1886: rep=isin_G_H(po,r,26,7);
1887: return rep? 7: 26;
1888: }
1889: else
1890: {
1891: /* PRIM_10_4: */
1892: rep=isin_G_H(po,r,45,35);
1893: if (!rep) return 45;
1894: /* PRIM_10_5: */
1895: rep=isin_G_H(po,r,35,32);
1896: if (!rep) goto PRIM_10_7;
1897: /* PRIM_10_6: */
1898: rep=isin_G_H(po,r,32,13);
1899: return rep? 13: 32;
1900:
1901: PRIM_10_7:
1902: rep=isin_G_H(po,r,35,30);
1903: return rep? 30: 35;
1904: }
1905: }
1906:
1907: static long
1908: galoisimpeven10(GEN po, GEN *r, long nogr)
1909: {
1910: long rep;
1911: if (nogr==42)
1912: {
1913: /* IMPEVEN_10_1: */
1914: rep=isin_G_H(po,r,42,28);
1915: if (!rep) return 42;
1916: /* IMPEVEN_10_2: */
1917: rep=isin_G_H(po,r,28,18);
1918: return rep? 18: 28;
1919: }
1920: else
1921: {
1922: /* IMPEVEN_10_3: */
1923: rep=isin_G_H(po,r,37,34);
1924: if (!rep) goto IMPEVEN_10_5;
1925: /* IMPEVEN_10_4: */
1926: rep=isin_G_H(po,r,34,15);
1927: if (rep) goto IMPEVEN_10_7; else return 34;
1928:
1929: IMPEVEN_10_5:
1930: rep=isin_G_H(po,r,37,24);
1931: if (!rep) return 37;
1932: /* IMPEVEN_10_6: */
1933: rep=isin_G_H(po,r,24,15);
1934: if (!rep) return 24;
1935: IMPEVEN_10_7:
1936: rep=isin_G_H(po,r,15,8);
1937: return rep? 8: 15;
1938: }
1939: }
1940:
1941: static long
1942: galoisimpodd10(GEN po, GEN *r, long nogr)
1943: {
1944: long rep;
1945: if (nogr==43)
1946: {
1947: /* IMPODD_10_1: */
1948: rep=isin_G_H(po,r,43,41);
1949: if (!rep) goto IMPODD_10_3;
1950: /* IMPODD_10_2: */
1951: rep=isin_G_H(po,r,41,40);
1952: if (rep) goto IMPODD_10_4; else goto IMPODD_10_5;
1953:
1954: IMPODD_10_3:
1955: rep=isin_G_H(po,r,43,33);
1956: if (rep) goto IMPODD_10_6; else return 43;
1957:
1958: IMPODD_10_4:
1959: rep=isin_G_H(po,r,40,21);
1960: if (rep) goto IMPODD_10_7; else goto IMPODD_10_8;
1961:
1962: IMPODD_10_5:
1963: rep=isin_G_H(po,r,41,27);
1964: if (rep) goto IMPODD_10_9; else goto IMPODD_10_10;
1965:
1966: IMPODD_10_6:
1967: rep=isin_G_H(po,r,33,27);
1968: if (rep) goto IMPODD_10_9; else return 33;
1969:
1970: IMPODD_10_7:
1971: rep=isin_G_H(po,r,21,10);
1972: if (rep) goto IMPODD_10_12; else goto IMPODD_10_13;
1973:
1974: IMPODD_10_8:
1975: rep=isin_G_H(po,r,40,12);
1976: if (rep) goto IMPODD_10_14; else goto IMPODD_10_15;
1977:
1978: IMPODD_10_9:
1979: rep=isin_G_H(po,r,27,21);
1980: if (rep) goto IMPODD_10_7; else goto IMPODD_10_16;
1981:
1982: IMPODD_10_10:
1983: rep=isin_G_H(po,r,41,22);
1984: if (!rep) return 41;
1985: /* IMPODD_10_11: */
1986: rep=isin_G_H(po,r,22,12);
1987: if (rep) goto IMPODD_10_14; else goto IMPODD_10_18;
1988:
1989: IMPODD_10_12:
1990: rep=isin_G_H(po,r,10,4);
1991: return rep? 4: 10;
1992:
1993: IMPODD_10_13:
1994: rep=isin_G_H(po,r,21,9);
1995: if (rep) goto IMPODD_10_19; else return 21;
1996: IMPODD_10_14:
1997: rep=isin_G_H(po,r,12,4);
1998: return rep? 4: 12;
1999:
2000: IMPODD_10_15:
2001: rep=isin_G_H(po,r,40,11);
2002: if (rep) goto IMPODD_10_20; else return 40;
2003: IMPODD_10_16:
2004: rep=isin_G_H(po,r,27,20);
2005: if (!rep) goto IMPODD_10_21;
2006: /* IMPODD_10_17: */
2007: rep=isin_G_H(po,r,20,10);
2008: if (rep) goto IMPODD_10_12; return 20;
2009:
2010: IMPODD_10_18:
2011: rep=isin_G_H(po,r,22,11);
2012: if (rep) goto IMPODD_10_20; else goto IMPODD_10_23;
2013:
2014: IMPODD_10_19:
2015: rep=isin_G_H(po,r,9,6);
2016: if (rep) goto IMPODD_10_24; else goto IMPODD_10_25;
2017:
2018: IMPODD_10_20:
2019: rep=isin_G_H(po,r,11,3);
2020: if (rep) goto IMPODD_10_26; else return 11;
2021:
2022: IMPODD_10_21:
2023: rep=isin_G_H(po,r,27,19);
2024: if (rep) goto IMPODD_10_27;
2025: /* IMPODD_10_22: */
2026: rep=isin_G_H(po,r,27,17);
2027: if (rep) goto IMPODD_10_28; else return 27;
2028:
2029: IMPODD_10_23:
2030: rep=isin_G_H(po,r,22,5);
2031: if (rep) goto IMPODD_10_29; else return 22;
2032:
2033: IMPODD_10_24:
2034: rep=isin_G_H(po,r,6,2);
2035: if (rep) return 2; else goto IMPODD_10_30;
2036:
2037: IMPODD_10_25:
2038: rep=isin_G_H(po,r,9,3);
2039: if (!rep) return 9;
2040: IMPODD_10_26:
2041: rep=isin_G_H(po,r,3,2);
2042: if (rep) return 2; else goto IMPODD_10_31;
2043:
2044: IMPODD_10_27:
2045: rep=isin_G_H(po,r,19,9);
2046: if (rep) goto IMPODD_10_19; else return 19;
2047:
2048: IMPODD_10_28:
2049: rep=isin_G_H(po,r,17,10);
2050: if (rep) goto IMPODD_10_12; else goto IMPODD_10_32;
2051:
2052: IMPODD_10_29:
2053: rep=isin_G_H(po,r,5,4);
2054: if (rep) return 4; else goto IMPODD_10_33;
2055:
2056: IMPODD_10_30:
2057: rep=isin_G_H(po,r,6,1);
2058: return rep? 1: 6;
2059:
2060: IMPODD_10_31:
2061: rep=isin_G_H(po,r,3,1);
2062: return rep? 1: 3;
2063:
2064: IMPODD_10_32:
2065: rep=isin_G_H(po,r,17,9);
2066: if (rep) goto IMPODD_10_19; else goto IMPODD_10_60;
2067:
2068: IMPODD_10_33:
2069: rep=isin_G_H(po,r,5,3);
2070: if (rep) goto IMPODD_10_26; else return 5;
2071:
2072: IMPODD_10_60:
2073: rep=isin_G_H(po,r,17,5);
2074: if (rep) goto IMPODD_10_29; else return 17;
2075: }
2076: else
2077: {
2078: /* IMPODD_10_34: */
2079: rep=isin_G_H(po,r,39,38);
2080: if (!rep) goto IMPODD_10_36;
2081: /* IMPODD_10_35: */
2082: rep=isin_G_H(po,r,38,25);
2083: if (rep) goto IMPODD_10_37; else goto IMPODD_10_38;
2084:
2085: IMPODD_10_36:
2086: rep=isin_G_H(po,r,39,36);
2087: if (rep) goto IMPODD_10_39; else goto IMPODD_10_40;
2088:
2089: IMPODD_10_37:
2090: rep=isin_G_H(po,r,25,4);
2091: return rep? 4: 25;
2092:
2093: IMPODD_10_38:
2094: rep=isin_G_H(po,r,38,12);
2095: if (rep) goto IMPODD_10_41; else return 38;
2096:
2097: IMPODD_10_39:
2098: rep=isin_G_H(po,r,36,23);
2099: if (rep) goto IMPODD_10_42; else goto IMPODD_10_43;
2100:
2101: IMPODD_10_40:
2102: rep=isin_G_H(po,r,39,29);
2103: if (rep) goto IMPODD_10_44; else goto IMPODD_10_45;
2104:
2105: IMPODD_10_41:
2106: rep=isin_G_H(po,r,12,4);
2107: return rep? 4: 12;
2108:
2109: IMPODD_10_42:
2110: rep=isin_G_H(po,r,23,16);
2111: if (rep) goto IMPODD_10_46; else goto IMPODD_10_47;
2112:
2113: IMPODD_10_43:
2114: rep=isin_G_H(po,r,36,11);
2115: if (rep) goto IMPODD_10_48; else return 36;
2116:
2117: IMPODD_10_44:
2118: rep=isin_G_H(po,r,29,25);
2119: if (rep) goto IMPODD_10_37; else goto IMPODD_10_49;
2120:
2121: IMPODD_10_45:
2122: rep=isin_G_H(po,r,39,22);
2123: if (rep) goto IMPODD_10_50; else return 39;
2124:
2125: IMPODD_10_46:
2126: rep=isin_G_H(po,r,16,2);
2127: return rep? 2: 16;
2128:
2129: IMPODD_10_47:
2130: rep=isin_G_H(po,r,23,14);
2131: if (rep) goto IMPODD_10_51; else goto IMPODD_10_52;
2132:
2133: IMPODD_10_48:
2134: rep=isin_G_H(po,r,11,3);
2135: if (rep) goto IMPODD_10_53; else return 11;
2136:
2137: IMPODD_10_49:
2138: rep=isin_G_H(po,r,29,23);
2139: if (rep) goto IMPODD_10_42; else goto IMPODD_10_54;
2140:
2141: IMPODD_10_50:
2142: rep=isin_G_H(po,r,22,12);
2143: if (rep) goto IMPODD_10_41; else goto IMPODD_10_55;
2144:
2145: IMPODD_10_51:
2146: rep=isin_G_H(po,r,14,1);
2147: return rep? 1: 14;
2148:
2149: IMPODD_10_52:
2150: rep=isin_G_H(po,r,23,3);
2151: if (!rep) return 23;
2152: IMPODD_10_53:
2153: rep=isin_G_H(po,r,3,2);
2154: if (rep) return 2; else goto IMPODD_10_57;
2155:
2156: IMPODD_10_54:
2157: rep=isin_G_H(po,r,29,5);
2158: if (rep) goto IMPODD_10_58; else return 29;
2159:
2160: IMPODD_10_55:
2161: rep=isin_G_H(po,r,22,11);
2162: if (rep) goto IMPODD_10_48;
2163: /* IMPODD_10_56: */
2164: rep=isin_G_H(po,r,22,5);
2165: if (rep) goto IMPODD_10_58; else return 22;
2166:
2167: IMPODD_10_57:
2168: rep=isin_G_H(po,r,3,1);
2169: return rep? 1: 3;
2170:
2171: IMPODD_10_58:
2172: rep=isin_G_H(po,r,5,4);
2173: if (rep) return 4;
2174: /* IMPODD_10_59: */
2175: rep=isin_G_H(po,r,5,3);
2176: if (rep) goto IMPODD_10_53; else return 5;
2177: }
2178: }
2179:
2180: static long
2181: closure10(GEN po)
2182: {
2183: long nbrac,rep;
2184: GEN r[NMAX];
2185:
2186: r[0]=myroots(po,PRMAX); nbrac=lg(r[0])-1;
2187: if (nbrac!=N) err(talker,"incompatible number of roots in closure10()");
2188:
2189: preci(r,PREC);
2190: if (CAR)
2191: {
2192: /* CLOS_10_1: */
2193: rep=isin_G_H(po,r,44,42);
2194: if (rep) return galoisimpeven10(po,r,42);
2195: /* CLOS_10_2: */
2196: rep=isin_G_H(po,r,44,37);
2197: if (rep) return galoisimpeven10(po,r,37);
2198: }
2199: else
2200: {
2201: /* CLOS_10_3: */
2202: rep=isin_G_H(po,r,45,43);
2203: if (rep) return galoisimpodd10(po,r,43);
2204: /* CLOS_10_4: */
2205: rep=isin_G_H(po,r,45,39);
2206: if (rep) return galoisimpodd10(po,r,39);
2207: }
2208: return galoisprim10(po,r);
2209: }
2210:
2211: static PERM
2212: data10(long n1,long n2,GROUP *t)
2213: {
2214: switch(n1)
2215: {
2216: case 6: if (n2!=2) break;
2217: *t=initgroup(N,1);
2218: return _cr(1, 2, 3, 4, 5, 6, 10, 9, 8, 7);
2219: case 9: if (n2!=3 && n2!=6) break;
2220: *t=initgroup(N,2);
2221: _aff((*t)[2], 1, 2, 3, 4, 5, 6, 10, 9, 8, 7);
2222: return SID;
2223: case 10: *t=initgroup(N,2);
2224: _aff((*t)[2], 1, 2, 3, 4, 5, 6, 10, 9, 8, 7);
2225: return SID;
2226: case 14: case 16:*t=initgroup(N,1);
2227: return _cr(1, 3, 5, 7, 9, 2, 4, 6, 8, 10);
2228: case 17: if (n2!=5) break;
2229: *t=initgroup(N,2);
2230: _aff((*t)[2], 1, 2, 3, 4, 5, 6, 10, 9, 8, 7);
2231: return SID;
2232: case 19: case 20: *t=initgroup(N,2);
2233: _aff((*t)[2], 1, 2, 3, 4, 5, 6, 8, 10, 7, 9);
2234: return SID;
2235: case 21: if (n2!=10) break;
2236: *t=initgroup(N,1);
2237: return _cr(1, 2, 3, 4, 5, 6, 8, 10, 7, 9);
2238: case 23: if (n2!=3) break;
2239: *t=initgroup(N,1);
2240: return _cr(1, 3, 5, 7, 9, 2, 4, 6, 8, 10);
2241: case 25: *t=initgroup(N,1);
2242: return _cr(1, 3, 5, 7, 9, 2, 4, 6, 8, 10);
2243: case 26: *t=initgroup(N,2);
2244: _aff((*t)[2], 1, 2, 4, 9, 6, 8, 10, 3, 7, 5);
2245: return _cr(1, 2, 3, 10, 6, 5, 7, 4, 8, 9);
2246: case 27: if (n2!=17 && n2!=21) break;
2247: *t=initgroup(N,2);
2248: _aff((*t)[2], 1, 2, 3, 4, 5, 6, 8, 10, 7, 9);
2249: return SID;
2250: case 28: *t=initgroup(N,2);
2251: _aff((*t)[2], 1, 2, 3, 4, 5, 6, 8, 10, 7, 9);
2252: return SID;
2253: case 29: if (n2!=5) break;
2254: *t=initgroup(N,1);
2255: return _cr(1, 3, 5, 7, 9, 2, 4, 6, 8, 10);
2256: case 32: *t=initgroup(N,2);
2257: _aff((*t)[2], 1, 2, 4, 9, 6, 8, 10, 3, 7, 5);
2258: return _cr(1, 2, 3, 10, 6, 5, 7, 4, 8, 9);
2259: case 36: if (n2!=11) break;
2260: *t=initgroup(N,1);
2261: return _cr(1, 3, 5, 7, 9, 2, 4, 6, 8, 10);
2262: case 38: if (n2!=12) break;
2263: *t=initgroup(N,1);
2264: return _cr(1, 3, 5, 7, 9, 2, 4, 6, 8, 10);
2265: case 39: if (n2!=22) break;
2266: *t=initgroup(N,1);
2267: return _cr(1, 3, 5, 7, 9, 2, 4, 6, 8, 10);
2268: case 40: if (n2!=12) break;
2269: *t=initgroup(N,1);
2270: return _cr(1, 2, 3, 4, 5, 6, 7, 8, 10, 9);
2271: case 41: if (n2!=22 && n2!=40) break;
2272: *t=initgroup(N,2);
2273: _aff((*t)[2], 1, 2, 3, 4, 5, 6, 7, 8, 10, 9);
2274: return SID;
2275: }
2276: *t=initgroup(N,1); return SID;
2277: }
2278:
2279: static long
2280: galoismodulo10(GEN pol, GEN dpol)
2281: {
2282: long av = avma, res, gr[46];
2283: long **TYP = partitions(10), **GR = (long**) cgeti(45);
2284:
2285: GR[ 1]= _gr( 4, 1,6,30,42);
2286: GR[ 2]= _gr( 3, 1,6,30);
2287: GR[ 3]= _gr( 5, 1,5,6,30,42);
2288: GR[ 4]= _gr( 4, 1,5,23,30);
2289: GR[ 5]= _gr( 7, 1,5,6,22,23,30,42);
2290: GR[ 6]= _gr( 5, 1,6,24,30,42);
2291: GR[ 7]= _gr( -4, 1,5,14,30);
2292: GR[ 8]= _gr( -4, 1,3,5,30);
2293: GR[ 9]= _gr( 6, 1,5,6,24,30,42);
2294: GR[10]= _gr( 5, 1,5,23,24,30);
2295: GR[11]= _gr( 7, 1,5,6,11,30,33,42);
2296: GR[12]= _gr( 7, 1,5,6,11,23,30,33);
2297: GR[13]= _gr( 7, 1,4,5,14,23,30,34);
2298: GR[14]= _gr( 8, 1,2,3,4,5,6,30,42);
2299: GR[15]= _gr( -6, 1,3,5,18,22,30);
2300: GR[16]= _gr( 7, 1,3,5,6,17,23,30);
2301: GR[17]= _gr( 8, 1,5,6,22,23,24,30,42);
2302: GR[18]= _gr( -6, 1,5,22,24,30,40);
2303: GR[19]= _gr( 7, 1,5,6,22,24,30,42);
2304: GR[20]= _gr( 6, 1,5,22,23,24,30);
2305: GR[21]= _gr( 9, 1,3,5,6,23,24,26,30,42);
2306: GR[22]= _gr( 11, 1,3,5,6,11,13,22,23,30,33,42);
2307: GR[23]= _gr( 12, 1,2,3,4,5,6,17,18,22,23,30,42);
2308: GR[24]= _gr( -7, 1,3,5,18,22,30,40);
2309: GR[25]= _gr( 8, 1,3,5,18,22,23,30,39);
2310: GR[26]= _gr( -5, 1,5,14,22,30);
2311: GR[27]= _gr( 10, 1,3,5,6,22,23,24,26,30,42);
2312: GR[28]= _gr( -8, 1,3,5,22,24,26,30,40);
2313: GR[29]= _gr( 14, 1,2,3,4,5,6,17,18,22,23,30,39,40,42);
2314: GR[30]= _gr( 8, 1,5,6,14,22,30,39,42);
2315: GR[31]= _gr( -6, 1,5,14,22,30,40);
2316: GR[32]= _gr( 8, 1,4,5,14,22,23,30,34);
2317: GR[33]= _gr( 14, 1,3,5,6,15,17,22,23,24,26,29,30,40,42);
2318: GR[34]= _gr( -9, 1,3,5,11,13,18,22,30,32);
2319: GR[35]= _gr( 12, 1,4,5,6,14,22,23,30,34,39,40,42);
2320: GR[36]= _gr( 18, 1,2,3,4,5,6,11,12,13,17,18,22,23,30,31,32,33,42);
2321: GR[37]= _gr(-12, 1,3,5,11,13,16,18,22,30,32,35,40);
2322: GR[38]= _gr( 18, 1,3,4,5,6,11,13,15,17,18,21,22,23,30,32,33,35,39);
2323: GR[39]= _gr( 24, 1,2,3,4,5,6,11,12,13,15,16,17,18,21,22,23,30,31,32,33,35,39,40,42);
2324: GR[40]= _gr( 14, 1,3,5,6,7,9,11,23,24,26,27,30,33,42);
2325: GR[41]= _gr( 18, 1,3,5,6,7,9,11,13,16,20,22,23,24,26,27,30,33,42);
2326: GR[42]= _gr(-17, 1,3,5,7,9,11,13,16,18,20,22,24,26,27,30,35,40);
2327: GR[43]= _gr( 32, 1,2,3,4,5,6,7,8,9,10,11,12,13,15,16,17,18,19,20,22,23,24,25,26,27,28,29,30,33,35,40,42);
2328: GR[44]= _gr(-22, 1,3,5,7,9,11,13,14,16,18,20,22,24,26,27,30,32,35,36,38,40,41);
2329:
2330: gr[0]=46; res = galmodp(pol,dpol,TYP,gr,GR);
2331: avma=av; if (!res) return 0;
2332: return CAR? 44: 45;
2333: }
2334:
2335: /* BIBLIOTHEQUE POUR LE DEGRE 11 */
2336:
2337: static long
2338: closure11(GEN po)
2339: {
2340: long nbrac,rep;
2341: GEN r[NMAX];
2342:
2343: r[0]=myroots(po,PRMAX); nbrac=lg(r[0])-1;
2344: if (nbrac!=N) err(talker,"incompatible number of roots in closure11()");
2345: preci(r,PREC);
2346: if (CAR)
2347: {
2348: /* EVEN_11_1: */
2349: rep=isin_G_H(po,r,7,6);
2350: if (!rep) return 7;
2351: /* EVEN_11_2: */
2352: rep=isin_G_H(po,r,6,5);
2353: if (!rep) return 6;
2354: /* EVEN_11_3: */
2355: rep=isin_G_H(po,r,5,3);
2356: if (!rep) return 5;
2357: /* EVEN_11_4: */
2358: rep=isin_G_H(po,r,3,1);
2359: return rep? 1: 3;
2360: }
2361: else
2362: {
2363: /* ODD_11_1: */
2364: rep=isin_G_H(po,r,8,4);
2365: if (!rep) return 8;
2366: /* ODD_11_2: */
2367: rep=isin_G_H(po,r,4,2);
2368: return rep? 2: 4;
2369: }
2370: }
2371:
2372: static PERM
2373: data11(long n1, GROUP *t)
2374: {
2375: switch(n1)
2376: {
2377: case 5: *t=initgroup(N,1);
2378: return _cr(1, 2, 3, 7, 8, 6, 11, 5, 9, 4, 10);
2379: case 6: *t=initgroup(N,1);
2380: return _cr(1, 2, 3, 4, 6, 10, 11, 9, 7, 5, 8);
2381: case 7: *t=initgroup(N,2);
2382: _aff((*t)[2], 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 10);
2383: return SID;
2384: }
2385: *t=initgroup(N,1); return SID;
2386: }
2387:
2388: static long
2389: galoismodulo11(GEN pol, GEN dpol)
2390: {
2391: long av = avma, res, gr[6] = {0, 1,1,1,1,1};
2392: long **TYP = (long**) cgeti(9);
2393:
2394: TYP[0] = new_chunk(1);
2395: TYP[1] = _gr(11, 11,0,0,0,0,0,0,0,0,0,0);
2396: if (CAR)
2397: {
2398: TYP[2] = _gr(11, 8,2,1,0,0,0,0,0,0,0,0);
2399: TYP[3] = _gr(11, 6,3,2,0,0,0,0,0,0,0,0);
2400: TYP[4] = _gr(11, 5,5,1,0,0,0,0,0,0,0,0);
2401: TYP[5] = _gr(11, 4,4,1,1,1,0,0,0,0,0,0);
2402: TYP[6] = _gr(11, 3,3,3,1,1,0,0,0,0,0,0);
2403: TYP[7] = _gr(11, 2,2,2,2,1,1,1,0,0,0,0);
2404: TYP[8] = _gr(11, 1,1,1,1,1,1,1,1,1,1,1);
2405: TYP[0][0] = 8;
2406: }
2407: else
2408: {
2409: TYP[2] = _gr(11,10,1,0,0,0,0,0,0,0,0,0);
2410: TYP[3] = _gr(11, 5,5,1,0,0,0,0,0,0,0,0);
2411: TYP[4] = _gr(11, 2,2,2,2,2,1,0,0,0,0,0);
2412: TYP[5] = _gr(11, 1,1,1,1,1,1,1,1,1,1,1);
2413: TYP[0][0] = 5;
2414: }
2415: res = galmodp(pol,dpol,TYP,gr,NULL);
2416: avma=av; if (!res) return 0;
2417: return CAR? 7: 8;
2418: }
2419:
2420: /* return 1 iff we need to read a resolvent */
2421: static long
2422: init_isin(long n1, long n2, GROUP *tau, GROUP *ss, PERM *s0)
2423: {
2424: long fl = 1;
2425: if (DEBUGLEVEL) {
2426: fprintferr("\n*** Entering isin_%ld_G_H_(%ld,%ld)\n",N,n1,n2); flusherr();
2427: }
2428: switch(N)
2429: {
2430: case 8:
2431: if ((n1==47 && n2==46) || (n1==44 && n2==40)) fl=0;
2432: *s0=data8(n1,n2,tau); break;
2433: case 9:
2434: if ((n1==31 && n2==29) || (n1==34 && n2==31) || (n1==33 && n2==30)) fl=0;
2435: *s0=data9(n1,n2,tau); break;
2436: case 10:
2437: if ((n1==45 && (n2==43||n2==39))
2438: || (n1==44 && (n2==42||n2==37))
2439: || (n1==43 && (n2==41||n2==33))
2440: || (n1==42 && n2==28)
2441: || (n1==41 && (n2==40||n2==27||n2==22))
2442: || (n1==40 && (n2==21||n2==11))
2443: || (n1==39 && (n2==38||n2==36||n2==29||n2==22))
2444: || (n1==38 && (n2==25||n2==12))
2445: || (n1==37 && (n2==34||n2==24))
2446: || (n1==36 && (n2==23||n2==11))
2447: || (n1==34 && n2==15)
2448: || (n1==33 && n2==27)
2449: || (n1==29 && (n2==25||n2==23||n2==5))
2450: || (n1==28 && n2==18)
2451: || (n1==27 && (n2==20||n2==19||n2==17))
2452: || (n1==25 && n2==4)
2453: || (n1==24 && n2==15)
2454: || (n1==23 && (n2==16||n2==3))
2455: || (n1==22 && (n2==12||n2==11||n2==5))
2456: || (n1==21 && (n2==10||n2==9))
2457: || (n1==17 && n2==5)
2458: || (n1==16 && n2==2)
2459: || (n1==14 && n2==1)
2460: || (n1==12 && n2==4)
2461: || (n1==11 && n2==3)
2462: || (n1==10 && n2==4)
2463: || (n1== 9 && n2==3)
2464: || (n1== 6 && n2==1)
2465: || (n1== 5 && n2==3)) fl = 0;
2466: *s0=data10(n1,n2,tau); break;
2467: case 11:
2468: *s0=data11(n1,tau); break;
2469: }
2470: *ss = lirecoset(n1,n2,N); return fl;
2471: }
2472:
2473: static long
2474: isin_G_H(GEN po, GEN *r, long n1, long n2)
2475: {
2476: long nbv,nbm,i,j;
2477: PERM s0, ww;
2478: RESOLVANTE a;
2479: GROUP ss,tau;
2480:
2481: if (init_isin(n1,n2, &tau, &ss, &s0))
2482: a = lireresolv(n1,n2,N,&nbv,&nbm);
2483: else
2484: { a = NULL; nbm=n1; nbv=n2; }
2485: ww = check_isin(po,r,nbm,nbv,a,tau,ss,s0);
2486: if (getpreci(r) != PREC) preci(r,PREC);
2487: free(ss); free(tau); if (a) free(a);
2488: if (ww)
2489: {
2490: long z[NMAX+1];
2491:
2492: if (DEBUGLEVEL)
2493: {
2494: fprintferr("\n Output of isin_%ld_G_H(%ld,%ld): %ld",N,n1,n2,n2);
2495: fprintferr("\n Reordering of the roots: "); printperm(ww);
2496: flusherr();
2497: }
2498: for (i=0; i<TSCHMAX; i++)
2499: {
2500: GEN p1 = r[i];
2501: for (j=1; j<=N; j++) z[j]=p1[(int)ww[j]];
2502: for (j=1; j<=N; j++) p1[j]=z[j];
2503: }
2504: free(ww); return n2;
2505: }
2506: if (DEBUGLEVEL)
2507: {
2508: fprintferr(" Output of isin_%ld_G_H(%ld,%ld): not included.\n",N,n1,n2);
2509: flusherr();
2510: }
2511: return 0;
2512: }
2513:
2514: GEN
2515: galoisbig(GEN pol, long prec)
2516: {
2517: GEN dpol, res = cgetg(4,t_VEC);
2518: long *tab,t, av = avma;
2519: long tab8[]={0,
2520: 8,8,8,8,8,16,16,16,16,16, 16,24,24,24,32,32,32,32,32,32,
2521: 32,32,48,48,56,64,64,64,64,64, 64,96,96,96,128,168,168,192,192,192,
2522: 192,288,336,384,576,576,1152,1344,20160,40320};
2523: long tab9[]={0,
2524: 9,9,18,18,18,27,27,36,36,54, 54,54,54,72,72,72,81,108,144,162,
2525: 162,162,216,324,324,432,504,648,648,648, 1296,1512,181440,362880};
2526: long tab10[]={0,
2527: 10,10,20,20,40,50,60,80,100,100, 120,120,120,160,160,160,200,200,200,200,
2528: 200,240,320,320,320,360,400,400,640,720, 720,720,800,960,1440,
2529: 1920,1920,1920,3840,7200,14400,14400,28800,1814400,3628800};
2530: long tab11[]={0, 11,22,55,110,660,7920,19958400,39916800};
2531:
2532: N = lgef(pol)-3; dpol = discsr(pol); CAR = carreparfait(dpol);
2533: prec += 2 * (MEDDEFAULTPREC-2);
2534: PREC = prec;
2535: if (DEBUGLEVEL)
2536: {
2537: fprintferr("Entering galoisbig (prec = %ld)\n",prec);
2538: fprintferr("Working with reduced polynomial #1 = "); bruterr(pol,'g',-1);
2539: fprintferr("\ndiscriminant = "); bruterr(dpol,'g',-1);
2540: fprintferr(CAR? "\nEVEN group\n": "\nODD group\n"); flusherr();
2541: }
2542: PRMAX = prec+5; TSCHMAX = 1; SID[0] = N;
2543: switch(N)
2544: {
2545: case 8: t = galoismodulo8(pol,dpol);
2546: if (!t) t = closure8(pol);
2547: tab=tab8; break;
2548:
2549: case 9: t = galoismodulo9(pol,dpol);
2550: if (!t) t = closure9(pol);
2551: tab=tab9; break;
2552:
2553: case 10: t = galoismodulo10(pol,dpol);
2554: if (!t) t = closure10(pol);
2555: tab=tab10; break;
2556:
2557: case 11: t = galoismodulo11(pol,dpol);
2558: if (!t) t = closure11(pol);
2559: tab=tab11; break;
2560:
2561: default: err(impl,"galois in degree > 11");
2562: }
2563: avma = av;
2564: res[1]=lstoi(tab[t]);
2565: res[2]=lstoi(CAR? 1 : -1);
2566: res[3]=lstoi(t); return res;
2567: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to galois.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / pari / src / modules