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