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