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