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