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 : /**************************************************************/
16 : /* */
17 : /* NUMBER FIELDS */
18 : /* */
19 : /**************************************************************/
20 : #include "pari.h"
21 : #include "paripriv.h"
22 :
23 : #define DEBUGLEVEL DEBUGLEVEL_nf
24 :
25 : int new_galois_format = 0;
26 :
27 : /* v a t_VEC, lg(v) = 13, sanity check for true rnf */
28 : static int
29 426246 : v13checkrnf(GEN v)
30 426246 : { return typ(gel(v,6)) == t_VEC; }
31 : static int
32 51926 : rawcheckbnf(GEN v) { return typ(v)==t_VEC && lg(v)==11; }
33 : static int
34 51072 : rawchecknf(GEN v) { return typ(v)==t_VEC && lg(v)==10; }
35 : /* v a t_VEC, lg(v) = 11, sanity check for true bnf */
36 : static int
37 42749 : v11checkbnf(GEN v) { return rawchecknf(bnf_get_nf(v)); }
38 : /* v a t_VEC, lg(v) = 13, sanity check for true nf and true bnf */
39 : static int
40 938 : v13checkgchar(GEN v) { return rawchecknf(gchar_get_nf(v)) && rawcheckbnf(gchar_get_bnf(v)); }
41 : /* v a t_VEC, lg(v) = 10, sanity check for true nf */
42 : static int
43 217203 : v10checknf(GEN v) { return typ(gel(v,1))==t_POL; }
44 : /* v a t_VEC, lg(v) = 9, sanity check for true gal */
45 : static int
46 665 : v9checkgal(GEN v)
47 665 : { GEN x = gel(v,2); return typ(x) == t_VEC && lg(x) == 4; }
48 :
49 : int
50 437239 : checkrnf_i(GEN rnf)
51 437239 : { return (typ(rnf)==t_VEC && lg(rnf)==13 && v13checkrnf(rnf)); }
52 :
53 : void
54 425525 : checkrnf(GEN rnf)
55 425525 : { if (!checkrnf_i(rnf)) pari_err_TYPE("checkrnf",rnf); }
56 :
57 : GEN
58 5390296 : checkbnf_i(GEN X)
59 : {
60 5390296 : if (typ(X) == t_VEC)
61 5390123 : switch (lg(X))
62 : {
63 5373610 : case 11:
64 5373610 : if (typ(gel(X,6)) != t_INT) return NULL; /* pre-2.2.4 format */
65 5373610 : if (lg(gel(X,10)) != 4) return NULL; /* pre-2.8.1 format */
66 5373610 : return X;
67 15995 : case 7: return checkbnf_i(bnr_get_bnf(X));
68 : }
69 691 : return NULL;
70 : }
71 :
72 : GEN
73 92642985 : checknf_i(GEN X)
74 : {
75 92642985 : if (typ(X)==t_VEC)
76 91993349 : switch(lg(X))
77 : {
78 91490875 : case 10: return X;
79 486484 : case 11: return checknf_i(bnf_get_nf(X));
80 2891 : case 7: return checknf_i(bnr_get_bnf(X));
81 8918 : case 3: if (typ(gel(X,2)) == t_POLMOD) return checknf_i(gel(X,1));
82 : }
83 662728 : return NULL;
84 : }
85 :
86 : GEN
87 3391297 : checkbnf(GEN x)
88 : {
89 3391297 : GEN bnf = checkbnf_i(x);
90 3391292 : if (!bnf) pari_err_TYPE("checkbnf [please apply bnfinit()]",x);
91 3391271 : return bnf;
92 : }
93 :
94 : GEN
95 89462940 : checknf(GEN x)
96 : {
97 89462940 : GEN nf = checknf_i(x);
98 89463149 : if (!nf) pari_err_TYPE("checknf [please apply nfinit()]",x);
99 89463096 : return nf;
100 : }
101 :
102 : GEN
103 1981204 : checkbnr_i(GEN bnr)
104 : {
105 1981204 : if (typ(bnr)!=t_VEC || lg(bnr)!=7 || !checkbnf_i(bnr_get_bnf(bnr)))
106 84 : return NULL;
107 1981112 : return bnr;
108 : }
109 : void
110 1797952 : checkbnr(GEN bnr)
111 : {
112 1797952 : if (!checkbnr_i(bnr))
113 14 : pari_err_TYPE("checkbnr [please apply bnrinit()]",bnr);
114 1797930 : }
115 :
116 : void
117 0 : checksqmat(GEN x, long N)
118 : {
119 0 : if (typ(x)!=t_MAT) pari_err_TYPE("checksqmat",x);
120 0 : if (lg(x) == 1 || lgcols(x) != N+1) pari_err_DIM("checksqmat");
121 0 : }
122 :
123 : GEN
124 1791347 : checkbid_i(GEN bid)
125 : {
126 : GEN f;
127 1791347 : if (typ(bid)!=t_VEC || lg(bid)!=6 || typ(bid_get_U(bid)) != t_VEC)
128 269908 : return NULL;
129 1521439 : f = bid_get_mod(bid);
130 1521439 : if (typ(f)!=t_VEC || lg(f)!=3) return NULL;
131 1521439 : return bid;
132 : }
133 : void
134 1521439 : checkbid(GEN bid)
135 : {
136 1521439 : if (!checkbid_i(bid)) pari_err_TYPE("checkbid",bid);
137 1521432 : }
138 : void
139 24136 : checkabgrp(GEN v)
140 : {
141 24136 : if (typ(v) == t_VEC) switch(lg(v))
142 : {
143 21735 : case 4: if (typ(gel(v,3)) != t_VEC) break;
144 24136 : case 3: if (typ(gel(v,2)) != t_VEC) break;
145 24108 : if (typ(gel(v,1)) != t_INT) break;
146 24108 : return;/*OK*/
147 0 : default: break;
148 : }
149 28 : pari_err_TYPE("checkabgrp",v);
150 : }
151 :
152 : GEN
153 618742 : checknfelt_mod(GEN nf, GEN x, const char *s)
154 : {
155 618742 : GEN T = gel(x,1), a = gel(x,2), Tnf = nf_get_pol(nf);
156 618743 : if (!RgX_equal_var(T, Tnf)) pari_err_MODULUS(s, T, Tnf);
157 618609 : return a;
158 : }
159 :
160 : int
161 6793 : check_ZKmodule_i(GEN M)
162 : {
163 6793 : return (typ(M) ==t_VEC && lg(M) >= 3
164 6793 : && typ(gel(M,1)) == t_MAT
165 6793 : && typ(gel(M,2)) == t_VEC
166 13586 : && lgcols(M) == lg(gel(M,2)));
167 : }
168 : void
169 6737 : check_ZKmodule(GEN M, const char *s)
170 6737 : { if (!check_ZKmodule_i(M)) pari_err_TYPE(s, M); }
171 :
172 : static long
173 126511 : typv6(GEN x)
174 : {
175 126511 : if (typ(gel(x,1)) == t_VEC && lg(gel(x,3)) == 3)
176 : {
177 23632 : GEN t = gel(x,3);
178 23632 : if (typ(t) != t_VEC) return typ_NULL;
179 23632 : t = gel(x,5);
180 23632 : switch(typ(gel(x,5)))
181 : {
182 455 : case t_VEC: return typ_BID;
183 23177 : case t_MAT: return typ_BIDZ;
184 0 : default: return typ_NULL;
185 : }
186 : }
187 102879 : if (typ(gel(x,2)) == t_COL && typ(gel(x,3)) == t_INT) return typ_PRID;
188 2527 : if (typ(gel(x,1)) == t_INT && typ(gel(x,2)) == t_VEC) return typ_QUA;
189 196 : return typ_NULL;
190 : }
191 :
192 : GEN
193 28525 : get_bnf(GEN x, long *t)
194 : {
195 28525 : switch(typ(x))
196 : {
197 56 : case t_POL: *t = typ_POL; return NULL;
198 56 : case t_QUAD: *t = typ_Q ; return NULL;
199 27902 : case t_VEC:
200 27902 : switch(lg(x))
201 : {
202 2247 : case 5: if (typ(gel(x,1)) != t_INT) break;
203 2191 : *t = typ_QUA; return NULL;
204 14735 : case 6: *t = typv6(x); return NULL;
205 2380 : case 7: *t = typ_BNR;
206 2380 : x = bnr_get_bnf(x);
207 2380 : if (!rawcheckbnf(x)) break;
208 2324 : return x;
209 84 : case 9:
210 84 : if (!v9checkgal(x)) break;
211 84 : *t = typ_GAL; return NULL;
212 602 : case 10:
213 602 : if (!v10checknf(x)) break;
214 602 : *t = typ_NF; return NULL;
215 483 : case 11:
216 483 : if (!v11checkbnf(x)) break;
217 483 : *t = typ_BNF; return x;
218 245 : case 13:
219 245 : if (v13checkgchar(x)) { *t = typ_GCHAR; return gchar_get_bnf(x); }
220 56 : if (!v13checkrnf(x)) break;
221 56 : *t = typ_RNF; return NULL;
222 266 : case 17: *t = typ_ELL; return NULL;
223 : }
224 6972 : break;
225 112 : case t_COL:
226 112 : if (get_prid(x)) { *t = typ_MODPR; return NULL; }
227 56 : break;
228 : }
229 7427 : *t = typ_NULL; return NULL;
230 : }
231 :
232 : GEN
233 116578 : get_nf(GEN x, long *t)
234 : {
235 116578 : switch(typ(x))
236 : {
237 133 : case t_POL : *t = typ_POL; return NULL;
238 133 : case t_QUAD: *t = typ_Q ; return NULL;
239 113589 : case t_VEC:
240 113589 : switch(lg(x))
241 : {
242 140 : case 3:
243 140 : if (typ(gel(x,2)) != t_POLMOD) break;
244 140 : return get_nf(gel(x,1),t);
245 133 : case 5:
246 133 : if (typ(gel(x,1)) != t_INT) break;
247 0 : *t = typ_QUA; return NULL;
248 99554 : case 6: *t = typv6(x); return NULL;
249 7301 : case 7:
250 7301 : x = bnr_get_bnf(x);
251 7301 : if (!rawcheckbnf(x) || !rawchecknf(x = bnf_get_nf(x))) break;
252 7168 : *t = typ_BNR; return x;
253 574 : case 9:
254 574 : if (!v9checkgal(x)) break;
255 574 : *t = typ_GAL; return NULL;
256 1617 : case 10:
257 1617 : if (!v10checknf(x)) break;
258 1617 : *t = typ_NF; return x;
259 217 : case 11:
260 217 : if (!rawchecknf(x = bnf_get_nf(x))) break;
261 217 : *t = typ_BNF; return x;
262 434 : case 13:
263 434 : if (v13checkgchar(x)) { *t = typ_GCHAR; return gchar_get_nf(x); }
264 406 : if (!v13checkrnf(x)) break;
265 406 : *t = typ_RNF; return NULL;
266 3486 : case 17: *t = typ_ELL; return NULL;
267 : }
268 399 : break;
269 147 : case t_QFB: *t = typ_QFB; return NULL;
270 266 : case t_COL:
271 266 : if (get_prid(x)) { *t = typ_MODPR; return NULL; }
272 133 : break;
273 : }
274 2842 : *t = typ_NULL; return NULL;
275 : }
276 :
277 : long
278 269871 : nftyp(GEN x)
279 : {
280 269871 : switch(typ(x))
281 : {
282 28 : case t_POL : return typ_POL;
283 7 : case t_QUAD: return typ_Q;
284 269829 : case t_VEC:
285 269829 : switch(lg(x))
286 : {
287 259 : case 13:
288 259 : if (v13checkgchar(x)) return typ_GCHAR;
289 252 : if (!v13checkrnf(x)) break;
290 245 : return typ_RNF;
291 214984 : case 10:
292 214984 : if (!v10checknf(x)) break;
293 214977 : return typ_NF;
294 259 : case 11:
295 259 : if (!v11checkbnf(x)) break;
296 259 : return typ_BNF;
297 42021 : case 7:
298 42021 : x = bnr_get_bnf(x);
299 42021 : if (!rawcheckbnf(x) || !v11checkbnf(x)) break;
300 42007 : return typ_BNR;
301 12222 : case 6:
302 12222 : return typv6(x);
303 7 : case 9:
304 7 : if (!v9checkgal(x)) break;
305 0 : return typ_GAL;
306 7 : case 17: return typ_ELL;
307 : }
308 : }
309 112 : return typ_NULL;
310 : }
311 :
312 : /*************************************************************************/
313 : /** **/
314 : /** GALOIS GROUP **/
315 : /** **/
316 : /*************************************************************************/
317 :
318 : GEN
319 7628 : tschirnhaus(GEN x)
320 : {
321 7628 : pari_sp av = avma, av2;
322 7628 : long a, v = varn(x);
323 7628 : GEN u, y = cgetg(5,t_POL);
324 :
325 7628 : if (typ(x)!=t_POL) pari_err_TYPE("tschirnhaus",x);
326 7628 : if (lg(x) < 4) pari_err_CONSTPOL("tschirnhaus");
327 7628 : if (v) { u = leafcopy(x); setvarn(u,0); x=u; }
328 7628 : y[1] = evalsigne(1)|evalvarn(0);
329 : do
330 : {
331 8287 : a = random_bits(2); if (a==0) a = 1; gel(y,4) = stoi(a);
332 8287 : a = random_bits(3); if (a>=4) a -= 8; gel(y,3) = stoi(a);
333 8287 : a = random_bits(3); if (a>=4) a -= 8; gel(y,2) = stoi(a);
334 8287 : u = RgXQ_charpoly(y,x,v); av2 = avma;
335 : }
336 8287 : while (degpol(RgX_gcd(u,RgX_deriv(u)))); /* while u not separable */
337 7628 : if (DEBUGLEVEL>1)
338 0 : err_printf("Tschirnhaus transform. New pol: %Ps",u);
339 7628 : set_avma(av2); return gc_upto(av,u);
340 : }
341 :
342 : /* Assume pol in Z[X], monic of degree n. Find L in Z such that
343 : * POL = L^(-n) pol(L x) is monic in Z[X]. Return POL and set *ptk = L.
344 : * No GC. */
345 : GEN
346 845711 : ZX_Z_normalize(GEN pol, GEN *ptk)
347 : {
348 845711 : long i,j, sk, n = degpol(pol); /* > 0 */
349 : GEN k, fa, P, E, a, POL;
350 :
351 845702 : if (ptk) *ptk = gen_1;
352 845702 : if (!n) return pol;
353 845695 : a = pol + 2; k = gel(a,n-1); /* a[i] = coeff of degree i */
354 1627421 : for (i = n-2; i >= 0; i--)
355 : {
356 1371391 : k = gcdii(k, gel(a,i));
357 1371297 : if (is_pm1(k)) return pol;
358 : }
359 256030 : sk = signe(k);
360 256030 : if (!sk) return pol; /* monomial! */
361 253944 : fa = absZ_factor_limit(k, 0); k = gen_1;
362 253951 : P = gel(fa,1);
363 253951 : E = gel(fa,2);
364 253951 : POL = leafcopy(pol); a = POL+2;
365 546839 : for (i = lg(P)-1; i > 0; i--)
366 : {
367 292887 : GEN p = gel(P,i), pv, pvj;
368 292887 : long vmin = itos(gel(E,i));
369 : /* find v_p(k) = min floor( v_p(a[i]) / (n-i)) */
370 1210250 : for (j=n-1; j>=0; j--)
371 : {
372 : long v;
373 917357 : if (!signe(gel(a,j))) continue;
374 789056 : v = Z_pval(gel(a,j), p) / (n - j);
375 789061 : if (v < vmin) vmin = v;
376 : }
377 292893 : if (!vmin) continue;
378 19658 : pvj = pv = powiu(p,vmin); k = mulii(k, pv);
379 : /* a[j] /= p^(v*(n-j)) */
380 79110 : for (j=n-1; j>=0; j--)
381 : {
382 59462 : if (j < n-1) pvj = mulii(pvj, pv);
383 59463 : gel(a,j) = diviiexact(gel(a,j), pvj);
384 : }
385 : }
386 253952 : if (ptk) *ptk = k;
387 253952 : return POL;
388 : }
389 :
390 : /* Assume pol != 0 in Z[X]. Find C in Q, L in Z such that POL = C pol(x/L) monic
391 : * in Z[X]. Return POL and set *pL = L. Wasteful (but correct) if pol is not
392 : * primitive: better if caller used Q_primpart already. No GC. */
393 : GEN
394 843037 : ZX_primitive_to_monic(GEN pol, GEN *pL)
395 : {
396 843037 : long i,j, n = degpol(pol);
397 843034 : GEN lc = leading_coeff(pol), L, fa, P, E, a, POL;
398 :
399 843030 : if (is_pm1(lc))
400 : {
401 840141 : if (pL) *pL = gen_1;
402 840141 : return signe(lc) < 0? ZX_neg(pol): pol;
403 : }
404 2891 : if (signe(lc) < 0)
405 35 : POL = ZX_neg(pol);
406 : else
407 2856 : POL = leafcopy(pol);
408 2891 : a = POL+2; lc = gel(a,n);
409 2891 : fa = absZ_factor_limit(lc,0); L = gen_1;
410 2891 : P = gel(fa,1);
411 2891 : E = gel(fa,2);
412 5971 : for (i = lg(P)-1; i > 0; i--)
413 : {
414 3080 : GEN p = gel(P,i), pk, pku;
415 3080 : long v, j0, e = itos(gel(E,i)), k = e/n, d = k*n - e;
416 :
417 3080 : if (d < 0) { k++; d += n; }
418 : /* k = ceil(e[i] / n); find d, k such that p^d pol(x / p^k) monic */
419 17311 : for (j=n-1; j>0; j--)
420 : {
421 14231 : if (!signe(gel(a,j))) continue;
422 8834 : v = Z_pval(gel(a,j), p);
423 8932 : while (v + d < k * j) { k++; d += n; }
424 : }
425 3080 : pk = powiu(p,k); j0 = d/k;
426 3080 : L = mulii(L, pk);
427 :
428 3080 : pku = powiu(p,d - k*j0);
429 : /* a[j] *= p^(d - kj) */
430 7329 : for (j=j0; j>=0; j--)
431 : {
432 4249 : if (j < j0) pku = mulii(pku, pk);
433 4249 : gel(a,j) = mulii(gel(a,j), pku);
434 : }
435 3080 : j0++;
436 3080 : pku = powiu(p,k*j0 - d);
437 : /* a[j] /= p^(kj - d) */
438 19222 : for (j=j0; j<=n; j++)
439 : {
440 16142 : if (j > j0) pku = mulii(pku, pk);
441 16142 : gel(a,j) = diviiexact(gel(a,j), pku);
442 : }
443 : }
444 2891 : if (pL) *pL = L;
445 2891 : return POL;
446 : }
447 : /* Assume pol != 0 in Z[X]. Find C,L in Q such that POL = C pol(x/L)
448 : * monic in Z[X]. Return POL and set *pL = L.
449 : * Wasteful (but correct) if pol is not primitive: better if caller used
450 : * Q_primpart already. No GC. */
451 : GEN
452 842720 : ZX_Q_normalize(GEN pol, GEN *pL)
453 : {
454 842720 : GEN lc, POL = ZX_primitive_to_monic(pol, &lc);
455 842715 : POL = ZX_Z_normalize(POL, pL);
456 842678 : if (pL) *pL = gdiv(lc, *pL);
457 842736 : return POL;
458 : }
459 :
460 : GEN
461 6683521 : ZX_Q_mul(GEN A, GEN z)
462 : {
463 6683521 : pari_sp av = avma;
464 6683521 : long i, l = lg(A);
465 : GEN d, n, Ad, B, u;
466 6683521 : if (typ(z)==t_INT) return ZX_Z_mul(A,z);
467 5627126 : n = gel(z, 1); d = gel(z, 2);
468 5627126 : Ad = RgX_to_RgC(FpX_red(A, d), l-2);
469 5627130 : u = gcdii(d, FpV_factorback(Ad, NULL, d));
470 5627129 : B = cgetg(l, t_POL);
471 5627128 : B[1] = A[1];
472 5627128 : if (equali1(u))
473 : {
474 6084533 : for(i=2; i<l; i++)
475 3943522 : gel(B, i) = mkfrac(mulii(n, gel(A,i)), d);
476 : } else
477 : {
478 20566531 : for(i=2; i<l; i++)
479 : {
480 17080415 : GEN di = gcdii(gel(Ad, i-1), u);
481 17080413 : GEN ni = mulii(n, diviiexact(gel(A,i), di));
482 17080402 : if (equalii(d, di))
483 3882278 : gel(B, i) = ni;
484 : else
485 13198141 : gel(B, i) = mkfrac(ni, diviiexact(d, di));
486 : }
487 : }
488 5627127 : return gc_GEN(av, B);
489 : }
490 :
491 : /* T != 0 in Z[x], returns a monic polynomial U in Z[x] generating the
492 : * same field: there exist C in Q, L in Z such that U(x) = C T(x/L).
493 : * Set *L = NULL if L = 1, and to L otherwise. No garbage collecting. */
494 : GEN
495 0 : ZX_to_monic(GEN T, GEN *L)
496 : {
497 0 : GEN lc = leading_coeff(T);
498 0 : if (is_pm1(lc)) { *L = gen_1; return signe(lc) > 0? T: ZX_neg(T); }
499 0 : return ZX_primitive_to_monic(Q_primpart(T), L);
500 : }
501 :
502 : GEN
503 42 : poltomonic(GEN T, GEN *L)
504 : {
505 42 : pari_sp av = avma;
506 42 : if (typ(T) != t_POL || !RgX_is_QX(T)) pari_err_TYPE("poltomonic", T);
507 42 : if (degpol(T) < 0) pari_err_ROOTS0("poltomonic");
508 35 : T = ZX_Q_normalize(Q_primpart(T), L); return gc_all(av, L? 2: 1, &T, L);
509 : }
510 :
511 : GEN
512 8897 : ZXX_Q_mul(GEN A, GEN z)
513 : {
514 : long i, l;
515 : GEN B;
516 8897 : if (typ(z)==t_INT) return ZXX_Z_mul(A,z);
517 8365 : B = cgetg_copy(A, &l);
518 8365 : B[1] = A[1];
519 116767 : for (i=2; i<l; i++)
520 : {
521 108402 : GEN Ai = gel(A,i);
522 108402 : gel(B,i) = typ(Ai)==t_POL ? ZX_Q_mul(Ai, z): gmul(Ai, z);
523 : }
524 8365 : return B;
525 : }
526 :
527 : /* Evaluate pol in s using nfelt arithmetic and Horner rule */
528 : GEN
529 11151 : nfpoleval(GEN nf, GEN pol, GEN s)
530 : {
531 11151 : pari_sp av=avma;
532 11151 : long i=lg(pol)-1;
533 : GEN res;
534 11151 : if (i==1) return gen_0;
535 11151 : res = nf_to_scalar_or_basis(nf, gel(pol,i));
536 27944 : for (i-- ; i>=2; i--)
537 16793 : res = nfadd(nf, nfmul(nf, s, res), gel(pol,i));
538 11151 : return gc_upto(av, res);
539 : }
540 :
541 : static GEN
542 96138 : QX_table_nfpoleval(GEN nf, GEN pol, GEN m)
543 : {
544 96138 : pari_sp av = avma;
545 96138 : long i = lg(pol)-1;
546 : GEN res, den;
547 96138 : if (i==1) return gen_0;
548 96138 : pol = Q_remove_denom(pol, &den);
549 96138 : res = scalarcol_shallow(gel(pol,i), nf_get_degree(nf));
550 399480 : for (i-- ; i>=2; i--)
551 303342 : res = ZC_Z_add(ZM_ZC_mul(m, res), gel(pol,i));
552 96138 : if (den) res = RgC_Rg_div(res, den);
553 96138 : return gc_upto(av, res);
554 : }
555 :
556 : GEN
557 8824 : FpX_FpC_nfpoleval(GEN nf, GEN pol, GEN a, GEN p)
558 : {
559 8824 : pari_sp av=avma;
560 8824 : long i=lg(pol)-1, n=nf_get_degree(nf);
561 : GEN res, Ma;
562 8824 : if (i==1) return zerocol(n);
563 8824 : Ma = FpM_red(zk_multable(nf, a), p);
564 8824 : res = scalarcol(gel(pol,i),n);
565 70246 : for (i-- ; i>=2; i--)
566 : {
567 61422 : res = FpM_FpC_mul(Ma, res, p);
568 61422 : gel(res,1) = Fp_add(gel(res,1), gel(pol,i), p);
569 : }
570 8824 : return gc_upto(av, res);
571 : }
572 :
573 : /* compute s(x), not stack clean */
574 : static GEN
575 96357 : ZC_galoisapply(GEN nf, GEN s, GEN x)
576 : {
577 96357 : x = nf_to_scalar_or_alg(nf, x);
578 96355 : if (typ(x) != t_POL) return scalarcol(x, nf_get_degree(nf));
579 96138 : return QX_table_nfpoleval(nf, x, zk_multable(nf, s));
580 : }
581 :
582 : /* true nf; S = automorphism in basis form, return an FpC = S(z) mod p */
583 : GEN
584 6276 : zk_galoisapplymod(GEN nf, GEN z, GEN S, GEN p)
585 : {
586 : GEN den, pe, pe1, denpe, R;
587 :
588 6276 : z = nf_to_scalar_or_alg(nf, z);
589 6276 : if (typ(z) != t_POL) return z;
590 6276 : if (gequalX(z)) return FpC_red(S, p); /* common, e.g. modpr_genFq */
591 5877 : z = Q_remove_denom(z,&den);
592 5877 : denpe = pe = NULL;
593 5877 : pe1 = p;
594 5877 : if (den)
595 : {
596 5450 : ulong e = Z_pvalrem(den, p, &den);
597 5450 : if (e) { pe = powiu(p, e); pe1 = mulii(pe, p); }
598 5450 : denpe = Zp_inv(den, p, e+1);
599 : }
600 5877 : R = FpX_FpC_nfpoleval(nf, FpX_red(z, pe1), FpC_red(S, pe1), pe1);
601 5877 : if (denpe) R = FpC_Fp_mul(R, denpe, pe1);
602 5877 : if (pe) R = gdivexact(R, pe);
603 5877 : return R;
604 : }
605 :
606 : /* true nf */
607 : static GEN
608 7 : pr_make(GEN nf, GEN p, GEN u, GEN e, GEN f)
609 : {
610 7 : GEN t = FpM_deplin(zk_multable(nf, u), p);
611 7 : t = zk_scalar_or_multable(nf, t);
612 7 : return mkvec5(p, u, e, f, t);
613 : }
614 : static GEN
615 7 : pr_galoisapply(GEN nf, GEN pr, GEN aut)
616 : {
617 7 : GEN p = pr_get_p(pr), u = zk_galoisapplymod(nf, pr_get_gen(pr), aut, p);
618 7 : return pr_make(nf, p, u, gel(pr,3), gel(pr,4));
619 : }
620 : static GEN
621 0 : pr_galoismatrixapply(GEN nf, GEN pr, GEN M)
622 : {
623 0 : GEN p = pr_get_p(pr), u = FpC_red(ZM_ZC_mul(M, pr_get_gen(pr)), p);
624 0 : return pr_make(nf, p, u, gel(pr,3), gel(pr,4));
625 : }
626 :
627 : static GEN
628 7 : vecgaloisapply(GEN nf, GEN aut, GEN x)
629 21 : { pari_APPLY_same(galoisapply(nf, aut, gel(x,i))); }
630 : static GEN
631 0 : vecgaloismatrixapply(GEN nf, GEN aut, GEN x)
632 0 : { pari_APPLY_same(nfgaloismatrixapply(nf, aut, gel(x,i))); }
633 :
634 : /* x: famat or standard algebraic number, aut automorphism in ZC form
635 : * simplified from general galoisapply */
636 : static GEN
637 49 : elt_galoisapply(GEN nf, GEN aut, GEN x)
638 : {
639 49 : pari_sp av = avma;
640 49 : switch(typ(x))
641 : {
642 7 : case t_INT: return icopy(x);
643 7 : case t_FRAC: return gcopy(x);
644 7 : case t_POLMOD: x = gel(x,2); /* fall through */
645 14 : case t_POL: {
646 14 : GEN y = basistoalg(nf, ZC_galoisapply(nf, aut, x));
647 14 : return gc_upto(av,y);
648 : }
649 7 : case t_COL:
650 7 : return gc_upto(av, ZC_galoisapply(nf, aut, x));
651 14 : case t_MAT:
652 14 : switch(lg(x)) {
653 7 : case 1: return cgetg(1, t_MAT);
654 7 : case 3: retmkmat2(vecgaloisapply(nf,aut,gel(x,1)), ZC_copy(gel(x,2)));
655 : }
656 : }
657 0 : pari_err_TYPE("galoisapply",x);
658 : return NULL; /* LCOV_EXCL_LINE */
659 : }
660 : /* M automorphism in matrix form */
661 : static GEN
662 0 : elt_galoismatrixapply(GEN nf, GEN M, GEN x)
663 : {
664 0 : if (typ(x) == t_MAT)
665 0 : switch(lg(x)) {
666 0 : case 1: return cgetg(1, t_MAT);
667 0 : case 3: retmkmat2(vecgaloismatrixapply(nf,M,gel(x,1)), ZC_copy(gel(x,2)));
668 : }
669 0 : return nfgaloismatrixapply(nf, M, x);
670 : }
671 :
672 : GEN
673 127568 : galoisapply(GEN nf, GEN aut, GEN x)
674 : {
675 127568 : pari_sp av = avma;
676 : long lx;
677 : GEN y;
678 :
679 127568 : nf = checknf(nf);
680 127569 : switch(typ(x))
681 : {
682 378 : case t_INT: return icopy(x);
683 7 : case t_FRAC: return gcopy(x);
684 :
685 35 : case t_POLMOD: x = gel(x,2); /* fall through */
686 1442 : case t_POL:
687 1442 : aut = algtobasis(nf, aut);
688 1442 : y = basistoalg(nf, ZC_galoisapply(nf, aut, x));
689 1442 : return gc_upto(av,y);
690 :
691 56 : case t_VEC:
692 56 : aut = algtobasis(nf, aut);
693 56 : switch(lg(x))
694 : {
695 7 : case 6:
696 7 : if (pr_is_inert(x)) { set_avma(av); return gcopy(x); }
697 7 : return gc_GEN(av, pr_galoisapply(nf, x, aut));
698 49 : case 3: y = cgetg(3,t_VEC);
699 49 : gel(y,1) = galoisapply(nf, aut, gel(x,1));
700 49 : gel(y,2) = elt_galoisapply(nf, aut, gel(x,2));
701 49 : return gc_upto(av, y);
702 : }
703 0 : break;
704 :
705 89608 : case t_COL:
706 89608 : aut = algtobasis(nf, aut);
707 89609 : return gc_upto(av, ZC_galoisapply(nf, aut, x));
708 :
709 36078 : case t_MAT: /* ideal */
710 36078 : lx = lg(x); if (lx==1) return cgetg(1,t_MAT);
711 36078 : if (nbrows(x) != nf_get_degree(nf)) break;
712 36078 : y = RgM_mul(nfgaloismatrix(nf,aut), x);
713 36078 : return gc_upto(av, idealhnf_shallow(nf,y));
714 : }
715 0 : pari_err_TYPE("galoisapply",x);
716 : return NULL; /* LCOV_EXCL_LINE */
717 : }
718 :
719 : /* M automorphism in galoismatrix form */
720 : GEN
721 13916 : nfgaloismatrixapply(GEN nf, GEN M, GEN x)
722 : {
723 13916 : pari_sp av = avma;
724 : long lx;
725 : GEN y;
726 :
727 13916 : nf = checknf(nf);
728 13916 : switch(typ(x))
729 : {
730 735 : case t_INT: return icopy(x);
731 0 : case t_FRAC: return gcopy(x);
732 :
733 0 : case t_POLMOD: x = gel(x,2); /* fall through */
734 0 : case t_POL:
735 0 : x = algtobasis(nf, x);
736 0 : return gc_upto(av, basistoalg(nf, RgM_RgC_mul(M, x)));
737 :
738 0 : case t_VEC:
739 0 : switch(lg(x))
740 : {
741 0 : case 6:
742 0 : if (pr_is_inert(x)) { set_avma(av); return gcopy(x); }
743 0 : return gc_GEN(av, pr_galoismatrixapply(nf, x, M));
744 0 : case 3: y = cgetg(3,t_VEC);
745 0 : gel(y,1) = nfgaloismatrixapply(nf, M, gel(x,1));
746 0 : gel(y,2) = elt_galoismatrixapply(nf, M, gel(x,2));
747 0 : return gc_upto(av, y);
748 : }
749 0 : break;
750 :
751 6027 : case t_COL: return RgM_RgC_mul(M, x);
752 :
753 7154 : case t_MAT: /* ideal */
754 7154 : lx = lg(x); if (lx==1) return cgetg(1,t_MAT);
755 7154 : if (nbrows(x) != nf_get_degree(nf)) break;
756 7154 : return gc_upto(av, idealhnf_shallow(nf,RgM_mul(M, x)));
757 : }
758 0 : pari_err_TYPE("galoisapply",x);
759 : return NULL; /* LCOV_EXCL_LINE */
760 : }
761 :
762 : /* compute action of automorphism s on nf.zk */
763 : GEN
764 96459 : nfgaloismatrix(GEN nf, GEN s)
765 : {
766 96459 : pari_sp av2, av = avma;
767 : GEN zk, D, M, H, m;
768 : long k, n;
769 :
770 96459 : nf = checknf(nf);
771 96459 : zk = nf_get_zkprimpart(nf); n = lg(zk)-1;
772 96459 : M = cgetg(n+1, t_MAT);
773 96459 : gel(M,1) = col_ei(n, 1); /* s(1) = 1 */
774 96459 : if (n == 1) return M;
775 96459 : av2 = avma;
776 96459 : if (typ(s) != t_COL) s = algtobasis(nf, s);
777 96459 : D = nf_get_zkden(nf);
778 96459 : H = RgV_to_RgM(zk, n);
779 96460 : if (n == 2)
780 : {
781 63434 : GEN t = gel(H,2); /* D * s(w_2) */
782 63434 : t = ZC_Z_add(ZC_Z_mul(s, gel(t,2)), gel(t,1));
783 63434 : gel(M,2) = gc_upto(av2, gdiv(t, D));
784 63434 : return M;
785 : }
786 33026 : m = zk_multable(nf, s);
787 33026 : gel(M,2) = s; /* M[,k] = s(x^(k-1)) */
788 143471 : for (k = 3; k <= n; k++) gel(M,k) = ZM_ZC_mul(m, gel(M,k-1));
789 33026 : M = ZM_mul(M, H);
790 33025 : if (!equali1(D)) M = ZM_Z_divexact(M, D);
791 33025 : return gc_upto(av, M);
792 : }
793 :
794 : static GEN
795 8190 : get_aut(GEN nf, GEN gal, GEN aut, GEN g)
796 : {
797 8190 : return aut ? gel(aut, g[1]): poltobasis(nf, galoispermtopol(gal, g));
798 : }
799 :
800 : static GEN
801 1491 : idealquasifrob(GEN nf, GEN gal, GEN grp, GEN pr, GEN subg, GEN *S, GEN aut)
802 : {
803 1491 : pari_sp av = avma;
804 1491 : long i, n = nf_get_degree(nf), f = pr_get_f(pr);
805 1491 : GEN pi = pr_get_gen(pr);
806 5680 : for (i=1; i<=n; i++)
807 : {
808 5680 : GEN g = gel(grp,i);
809 5680 : if ((!subg && perm_orderu(g) == (ulong)f)
810 5194 : || (subg && perm_relorder(g, subg)==f))
811 : {
812 1956 : *S = get_aut(nf, gal, aut, g);
813 1956 : if (ZC_prdvd(ZC_galoisapply(nf, *S, pi), pr)) return g;
814 465 : set_avma(av);
815 : }
816 : }
817 0 : pari_err_BUG("idealquasifrob [Frobenius not found]");
818 : return NULL;/*LCOV_EXCL_LINE*/
819 : }
820 :
821 : GEN
822 1379 : nfgaloispermtobasis(GEN nf, GEN gal)
823 : {
824 1379 : GEN grp = gal_get_group(gal);
825 1379 : long i, n = lg(grp)-1;
826 1379 : GEN aut = cgetg(n+1, t_VEC);
827 15323 : for(i=1; i<=n; i++)
828 : {
829 13944 : pari_sp av = avma;
830 13944 : GEN g = gel(grp, i);
831 13944 : GEN vec = poltobasis(nf, galoispermtopol(gal, g));
832 13944 : gel(aut, g[1]) = gc_upto(av, vec);
833 : }
834 1379 : return aut;
835 : }
836 :
837 : static void
838 2513 : gal_check_pol(const char *f, GEN x, GEN y)
839 2513 : { if (!RgX_equal_var(x,y)) pari_err_MODULUS(f,x,y); }
840 :
841 : /* true nf */
842 : GEN
843 98 : idealfrobenius_aut(GEN nf, GEN gal, GEN pr, GEN aut)
844 : {
845 98 : pari_sp av = avma;
846 98 : GEN S=NULL, g=NULL; /*-Wall*/
847 : GEN T, p, a, b, modpr;
848 : long f, n, s;
849 98 : f = pr_get_f(pr); n = nf_get_degree(nf);
850 98 : if (f==1) { set_avma(av); return identity_perm(n); }
851 98 : g = idealquasifrob(nf, gal, gal_get_group(gal), pr, NULL, &S, aut);
852 98 : if (f==2) return gc_leaf(av, g);
853 42 : modpr = zk_to_Fq_init(nf,&pr,&T,&p);
854 42 : a = pol_x(nf_get_varn(nf));
855 42 : b = nf_to_Fq(nf, zk_galoisapplymod(nf, modpr_genFq(modpr), S, p), modpr);
856 84 : for (s = 1; s < f-1; s++)
857 : {
858 42 : a = Fq_pow(a, p, T, p);
859 42 : if (ZX_equal(a, b)) break;
860 : }
861 42 : g = perm_powu(g, Fl_inv(s, f));
862 42 : return gc_upto(av, g);
863 : }
864 :
865 : GEN
866 105 : idealfrobenius(GEN nf, GEN gal, GEN pr)
867 : {
868 105 : nf = checknf(nf);
869 105 : checkgal(gal);
870 105 : checkprid(pr);
871 105 : gal_check_pol("idealfrobenius",nf_get_pol(nf),gal_get_pol(gal));
872 105 : if (pr_get_e(pr)>1) pari_err_DOMAIN("idealfrobenius","pr.e", ">", gen_1,pr);
873 98 : return idealfrobenius_aut(nf, gal, pr, NULL);
874 : }
875 :
876 : /* true nf */
877 : GEN
878 616 : idealramfrobenius_aut(GEN nf, GEN gal, GEN pr, GEN ram, GEN aut)
879 : {
880 616 : pari_sp av = avma;
881 616 : GEN S=NULL, g=NULL; /*-Wall*/
882 : GEN T, p, a, b, modpr;
883 : GEN isog, deco;
884 : long f, n, s;
885 616 : f = pr_get_f(pr); n = nf_get_degree(nf);
886 616 : if (f==1) { set_avma(av); return identity_perm(n); }
887 399 : modpr = zk_to_Fq_init(nf,&pr,&T,&p);
888 399 : deco = group_elts(gel(ram,1), nf_get_degree(nf));
889 399 : isog = group_set(gel(ram,2), nf_get_degree(nf));
890 399 : g = idealquasifrob(nf, gal, deco, pr, isog, &S, aut);
891 399 : a = pol_x(nf_get_varn(nf));
892 399 : b = nf_to_Fq(nf, zk_galoisapplymod(nf, modpr_genFq(modpr), S, p), modpr);
893 854 : for (s=0; !ZX_equal(a, b); s++)
894 455 : a = Fq_pow(a, p, T, p);
895 399 : g = perm_powu(g, Fl_inv(s, f));
896 399 : return gc_upto(av, g);
897 : }
898 :
899 : GEN
900 0 : idealramfrobenius(GEN nf, GEN gal, GEN pr, GEN ram)
901 : {
902 0 : return idealramfrobenius_aut(nf, gal, pr, ram, NULL);
903 : }
904 :
905 : static GEN
906 1834 : idealinertiagroup(GEN nf, GEN gal, GEN aut, GEN pr)
907 : {
908 1834 : long i, n = nf_get_degree(nf);
909 1834 : GEN p, T, modpr = zk_to_Fq_init(nf,&pr,&T,&p);
910 1834 : GEN b = modpr_genFq(modpr);
911 1834 : long e = pr_get_e(pr), coprime = ugcd(e, pr_get_f(pr)) == 1;
912 1834 : GEN grp = gal_get_group(gal), pi = pr_get_gen(pr);
913 1834 : pari_sp ltop = avma;
914 7893 : for (i=1; i<=n; i++)
915 : {
916 7893 : GEN iso = gel(grp,i);
917 7893 : if (perm_orderu(iso) == (ulong)e)
918 : {
919 3329 : GEN S = get_aut(nf, gal, aut, iso);
920 3329 : if (ZC_prdvd(ZC_galoisapply(nf, S, pi), pr)
921 2352 : && (coprime || gequalX(nf_to_Fq(nf, galoisapply(nf,S,b), modpr))))
922 1834 : return iso;
923 1495 : set_avma(ltop);
924 : }
925 : }
926 0 : pari_err_BUG("idealinertiagroup [no isotropic element]");
927 : return NULL;/*LCOV_EXCL_LINE*/
928 : }
929 :
930 : static GEN
931 1911 : idealramgroupstame(GEN nf, GEN gal, GEN aut, GEN pr)
932 : {
933 1911 : pari_sp av = avma;
934 : GEN iso, frob, giso, isog, S, res;
935 1911 : long e = pr_get_e(pr), f = pr_get_f(pr);
936 1911 : GEN grp = gal_get_group(gal);
937 1911 : if (e == 1)
938 : {
939 77 : if (f==1)
940 0 : return cgetg(1,t_VEC);
941 77 : frob = idealquasifrob(nf, gal, grp, pr, NULL, &S, aut);
942 77 : set_avma(av);
943 77 : res = cgetg(2, t_VEC);
944 77 : gel(res, 1) = cyclicgroup(frob, f);
945 77 : return res;
946 : }
947 1834 : res = cgetg(3, t_VEC);
948 1834 : av = avma;
949 1834 : iso = idealinertiagroup(nf, gal, aut, pr);
950 1834 : set_avma(av);
951 1834 : giso = cyclicgroup(iso, e);
952 1834 : gel(res, 2) = giso;
953 1834 : if (f==1)
954 : {
955 917 : gel(res, 1) = giso;
956 917 : return res;
957 : }
958 917 : av = avma;
959 917 : isog = group_set(giso, nf_get_degree(nf));
960 917 : frob = idealquasifrob(nf, gal, grp, pr, isog, &S, aut);
961 917 : set_avma(av);
962 917 : gel(res, 1) = dicyclicgroup(iso,frob,e,f);
963 917 : return res;
964 : }
965 :
966 : /* true nf, p | e */
967 : static GEN
968 497 : idealramgroupswild(GEN nf, GEN gal, GEN aut, GEN pr)
969 : {
970 497 : pari_sp av2, av = avma;
971 497 : GEN p, T, idx, g, gbas, pi, pibas, Dpi, modpr = zk_to_Fq_init(nf,&pr,&T,&p);
972 497 : long bound, i, vDpi, vDg, n = nf_get_degree(nf);
973 497 : long e = pr_get_e(pr);
974 497 : long f = pr_get_f(pr);
975 : ulong nt,rorder;
976 497 : GEN pg, ppi, grp = gal_get_group(gal);
977 :
978 : /* G_i = {s: v(s(pi) - pi) > i} trivial for i > bound;
979 : * v_pr(Diff) = sum_{i = 0}^{bound} (#G_i - 1) >= e-1 + bound*(p-1)*/
980 497 : bound = (idealval(nf, nf_get_diff(nf), pr) - (e-1)) / (itou(p)-1);
981 497 : (void) u_pvalrem(n,p,&nt);
982 497 : rorder = e*f*(n/nt);
983 497 : idx = const_vecsmall(n,-1);
984 497 : pg = NULL;
985 497 : vDg = 0;
986 497 : if (f == 1)
987 154 : g = gbas = NULL;
988 : else
989 : {
990 : GEN Dg;
991 343 : g = nf_to_scalar_or_alg(nf, modpr_genFq(modpr));
992 343 : if (!gequalX(g)) /* p | nf.index */
993 : {
994 7 : g = Q_remove_denom(g, &Dg);
995 7 : vDg = Z_pval(Dg,p);
996 7 : pg = powiu(p, vDg + 1);
997 7 : g = FpX_red(g, pg);
998 : }
999 343 : gbas = nf_to_scalar_or_basis(nf, g);
1000 : }
1001 497 : pi = nf_to_scalar_or_alg(nf, pr_get_gen(pr));
1002 497 : pi = Q_remove_denom(pi, &Dpi);
1003 497 : vDpi = Dpi ? Z_pval(Dpi, p): 0;
1004 497 : ppi = powiu(p, vDpi + (bound + e)/e);
1005 497 : pi = FpX_red(pi, ppi);
1006 497 : pibas = nf_to_scalar_or_basis(nf, pi);
1007 497 : av2 = avma;
1008 4704 : for (i = 2; i <= n; i++)
1009 : {
1010 4207 : GEN S, Spi, piso, iso = gel(grp, i);
1011 4207 : long j, o, ix = iso[1];
1012 4207 : if (idx[ix] >= 0 || rorder % (o = (long)perm_orderu(iso))) continue;
1013 :
1014 2905 : piso = iso;
1015 2905 : S = get_aut(nf, gal, aut, iso);
1016 2905 : Spi = FpX_FpC_nfpoleval(nf, pi, FpC_red(S, ppi), ppi);
1017 : /* Computation made knowing that the valuation is <= bound + 1. Correct
1018 : * to maximal value if reduction mod ppi altered this */
1019 2905 : idx[ix] = minss(bound+1, idealval(nf, gsub(Spi,pibas), pr) - e*vDpi);
1020 2905 : if (idx[ix] == 0) idx[ix] = -1;
1021 2457 : else if (g)
1022 : {
1023 1848 : GEN Sg = pg? FpX_FpC_nfpoleval(nf, g, FpC_red(S, pg), pg): S;
1024 1848 : if (vDg)
1025 42 : { if (nfval(nf, gsub(Sg, gbas), pr) - e*vDg <= 0) idx[ix] = 0; }
1026 : else /* same, more efficient */
1027 1806 : { if (!ZC_prdvd(gsub(Sg, gbas), pr)) idx[ix] = 0; }
1028 : }
1029 5488 : for (j = 2; j < o; j++)
1030 : {
1031 2583 : piso = perm_mul(piso,iso);
1032 2583 : if (ugcd(j,o)==1) idx[ piso[1] ] = idx[ix];
1033 : }
1034 2905 : set_avma(av2);
1035 : }
1036 497 : return gc_leaf(av, idx);
1037 : }
1038 :
1039 : GEN
1040 2408 : idealramgroups_aut(GEN nf, GEN gal, GEN pr, GEN aut)
1041 : {
1042 2408 : pari_sp av = avma;
1043 : GEN tbl, idx, res, set, sub;
1044 : long i, j, e, n, maxm, p;
1045 : ulong et;
1046 2408 : nf = checknf(nf);
1047 2408 : checkgal(gal);
1048 2408 : checkprid(pr);
1049 2408 : gal_check_pol("idealramgroups",nf_get_pol(nf),gal_get_pol(gal));
1050 2408 : e = pr_get_e(pr); n = nf_get_degree(nf);
1051 2408 : p = itos(pr_get_p(pr));
1052 2408 : if (e%p) return idealramgroupstame(nf, gal, aut, pr);
1053 497 : (void) u_lvalrem(e,p,&et);
1054 497 : idx = idealramgroupswild(nf, gal, aut, pr);
1055 497 : sub = galoissubgroups(gal);
1056 497 : tbl = subgroups_tableset(sub, n);
1057 497 : maxm = vecsmall_max(idx)+1;
1058 497 : res = cgetg(maxm+1,t_VEC);
1059 497 : set = zero_F2v(n); F2v_set(set,1);
1060 2499 : for(i=maxm; i>0; i--)
1061 : {
1062 : long ix;
1063 20468 : for(j=1;j<=n;j++)
1064 18466 : if (idx[j]==i-1)
1065 3521 : F2v_set(set,j);
1066 2002 : ix = tableset_find_index(tbl, set);
1067 2002 : if (ix==0) pari_err_BUG("idealramgroups");
1068 2002 : gel(res,i) = gel(sub, ix);
1069 : }
1070 497 : return gc_GEN(av, res);
1071 : }
1072 :
1073 : GEN
1074 126 : idealramgroups(GEN nf, GEN gal, GEN pr)
1075 : {
1076 126 : return idealramgroups_aut(nf, gal, pr, NULL);
1077 : }
1078 :
1079 : /* x = relative polynomial nf = absolute nf, bnf = absolute bnf */
1080 : GEN
1081 112 : get_bnfpol(GEN x, GEN *bnf, GEN *nf)
1082 : {
1083 112 : *bnf = checkbnf_i(x);
1084 112 : *nf = checknf_i(x);
1085 112 : if (*nf) x = nf_get_pol(*nf);
1086 112 : if (typ(x) != t_POL) pari_err_TYPE("get_bnfpol",x);
1087 112 : return x;
1088 : }
1089 :
1090 : GEN
1091 678690 : get_nfpol(GEN x, GEN *nf)
1092 : {
1093 678690 : if (typ(x) == t_POL) { *nf = NULL; return x; }
1094 390940 : *nf = checknf(x); return nf_get_pol(*nf);
1095 : }
1096 :
1097 : static GEN
1098 539 : incl_disc(GEN nfa, GEN a, int nolocal)
1099 : {
1100 : GEN d;
1101 539 : if (nfa) return nf_get_disc(nfa);
1102 469 : if (nolocal) return NULL;
1103 462 : d = ZX_disc(a);
1104 462 : if (!signe(d)) pari_err_IRREDPOL("nfisincl",a);
1105 455 : return d;
1106 : }
1107 :
1108 : static int
1109 49 : badp(GEN fa, GEN db, long q)
1110 : {
1111 49 : GEN P = gel(fa,1), E = gel(fa,2);
1112 49 : long i, l = lg(P);
1113 105 : for (i = 1; i < l; i++)
1114 56 : if (mod2(gel(E,i)) && !dvdii(db, powiu(gel(P,i),q))) return 1;
1115 49 : return 0;
1116 : }
1117 :
1118 : /* is isomorphism / inclusion (a \subset b) compatible with what we know about
1119 : * basic invariants ? (degree, signature, discriminant); test for isomorphism
1120 : * if fliso is set and for inclusion otherwise */
1121 : static int
1122 287 : tests_OK(GEN a, GEN nfa, GEN b, GEN nfb, long fliso)
1123 : {
1124 : GEN da2, da, db, fa, P, U;
1125 287 : long i, l, q, m = degpol(a), n = degpol(b);
1126 :
1127 287 : if (m <= 0) pari_err_IRREDPOL("nfisincl",a);
1128 287 : if (n <= 0) pari_err_IRREDPOL("nfisincl",b);
1129 280 : q = n / m; /* relative degree */
1130 280 : if (fliso) { if (n != m) return 0; } else { if (n % m) return 0; }
1131 280 : if (m == 1) return 1;
1132 :
1133 : /*local test expensive if n^2 >> m^4 <=> q = n/m >> m */
1134 273 : db = incl_disc(nfb, b, q > m);
1135 273 : da = db? incl_disc(nfa, a, 0): NULL;
1136 266 : if (nfa && nfb) /* both nf structures available */
1137 : {
1138 7 : long r1a = nf_get_r1(nfa), r1b = nf_get_r1(nfb);
1139 0 : return fliso ? (r1a == r1b && equalii(da, db))
1140 7 : : (r1b <= r1a * q && dvdii(db, powiu(da, q)));
1141 : }
1142 259 : if (!db) return 1;
1143 252 : if (fliso) return issquare(gdiv(da,db));
1144 :
1145 203 : if (nfa)
1146 : {
1147 7 : P = nf_get_ramified_primes(nfa); l = lg(P);
1148 14 : for (i = 1; i < l; i++)
1149 7 : if (Z_pval(db, gel(P,i)) < q * Z_pval(da, gel(P,i))) return 0;
1150 7 : return 1;
1151 : }
1152 196 : else if (nfb)
1153 : {
1154 28 : P = nf_get_ramified_primes(nfb); l = lg(P);
1155 56 : for (i = 1; i < l; i++)
1156 : {
1157 28 : GEN p = gel(P,i);
1158 28 : long va = Z_pval(nfdisc(mkvec2(a, mkvec(p))), p);
1159 28 : if (va && Z_pval(db, gel(P,i)) < va * q) return 0;
1160 : }
1161 28 : return 1;
1162 : }
1163 : /* da = dK A^2, db = dL B^2, dL = dK^q * N(D)
1164 : * da = da1 * da2, da2 maximal s.t. (da2, db) = 1: let p a prime divisor of
1165 : * da2 then p \nmid da1 * dK and p | A => v_p(da) = v_p(da2) is even */
1166 168 : da2 = Z_ppo(da, db);
1167 168 : if (!is_pm1(da2))
1168 : { /* replace da by da1 all of whose prime divisors divide db */
1169 126 : da2 = absi_shallow(da2);
1170 126 : if (!Z_issquare(da2)) return 0;
1171 14 : da = diviiexact(da, da2);
1172 : }
1173 56 : if (is_pm1(da)) return 1;
1174 49 : fa = absZ_factor_limit_strict(da, 0, &U);
1175 49 : if (badp(fa, db, q)) return 0;
1176 49 : if (U && mod2(gel(U,2)) && expi(gel(U,1)) < 150)
1177 : { /* cofactor is small, finish */
1178 0 : fa = absZ_factor(gel(U,1));
1179 0 : if (badp(fa, db, q)) return 0;
1180 : }
1181 49 : return 1;
1182 : }
1183 :
1184 : GEN
1185 77 : nfisisom(GEN a, GEN b)
1186 : {
1187 77 : pari_sp av = avma;
1188 : long i, va, vb, lx;
1189 : GEN nfa, nfb, y, la, lb;
1190 77 : int newvar, sw = 0;
1191 :
1192 77 : a = get_nfpol(a, &nfa);
1193 77 : b = get_nfpol(b, &nfb);
1194 77 : if (!nfa) { a = Q_primpart(a); RgX_check_ZX(a, "nfisisom"); }
1195 77 : if (!nfb) { b = Q_primpart(b); RgX_check_ZX(b, "nfisisom"); }
1196 77 : if (ZX_equal(a, b))
1197 : {
1198 21 : y = galoisconj(nfb? nfb: b, NULL); settyp(y, t_VEC);
1199 21 : return gc_GEN(av,y);
1200 : }
1201 56 : if (nfa && !nfb) { swap(a,b); nfb = nfa; nfa = NULL; sw = 1; }
1202 56 : if (!tests_OK(a, nfa, b, nfb, 1)) { set_avma(av); return gen_0; }
1203 :
1204 49 : if (nfb) lb = gen_1; else nfb = b = ZX_Q_normalize(b,&lb);
1205 49 : if (nfa) la = gen_1; else nfa = a = ZX_Q_normalize(a,&la);
1206 49 : va = varn(a); vb = varn(b); newvar = (varncmp(vb,va) <= 0);
1207 49 : if (newvar) { a = leafcopy(a); setvarn(a, fetch_var_higher()); }
1208 49 : y = lift_shallow(nfroots(nfb,a));
1209 49 : if (newvar) (void)delete_var();
1210 49 : lx = lg(y); if (lx==1) { set_avma(av); return gen_0; }
1211 49 : if (sw) { vb = va; b = leafcopy(b); setvarn(b, vb); }
1212 308 : for (i=1; i<lx; i++)
1213 : {
1214 259 : GEN t = gel(y,i);
1215 259 : if (typ(t) == t_POL) setvarn(t, vb); else t = scalarpol(t, vb);
1216 259 : if (lb != gen_1) t = RgX_unscale(t, lb);
1217 259 : if (la != gen_1) t = RgX_Rg_div(t, la);
1218 259 : gel(y,i) = sw? RgXQ_reverse(t, b): t;
1219 : }
1220 49 : settyp(y, t_VEC); return gc_GEN(av,y);
1221 : }
1222 :
1223 : static GEN
1224 7343 : partmap_reverse(GEN a, GEN b, GEN t, GEN la, GEN lb, long v)
1225 : {
1226 7343 : pari_sp av = avma;
1227 7343 : GEN rnf = rnfequation2(a, t), z;
1228 7343 : if (!RgX_equal(b, gel(rnf,1)))
1229 7 : { setvarn(b,v); pari_err_IRREDPOL("nfisincl", b); }
1230 7336 : z = liftpol_shallow(gel(rnf, 2));
1231 7336 : setvarn(z, v);
1232 7336 : if (!isint1(lb)) z = RgX_unscale(z, lb);
1233 7336 : if (!isint1(la)) z = RgX_Rg_div(z, la);
1234 7336 : return gc_GEN(av, z);
1235 : }
1236 :
1237 : static GEN
1238 8084 : partmap_reverse_frac(GEN a, GEN b, GEN t, GEN la, GEN lb, long v)
1239 : {
1240 8084 : pari_sp av = avma;
1241 8084 : long k = 0;
1242 : GEN N, D, G, L, de;
1243 8084 : GEN C = ZX_ZXY_resultant_all(a, Q_remove_denom(t,&de), &k, &L);
1244 8085 : if (k || degpol(b) != degpol(C))
1245 0 : { setvarn(b,v); pari_err_IRREDPOL("nfisincl", b); }
1246 8085 : L = Q_primpart(L);
1247 8085 : N = gel(L,1); if (!signe(N)) { set_avma(av); return pol_0(v); }
1248 8078 : D = gel(L,2);
1249 8078 : N = RgX_neg(N); setvarn(N, v); setvarn(D, v);
1250 8078 : G = QX_gcd(N,D);
1251 8078 : if (degpol(G)) { N = RgX_div(N,G); D = RgX_div(D,G); }
1252 8078 : if (!isint1(lb)) { N = RgX_unscale(N, lb); D = RgX_unscale(D, lb); }
1253 8078 : if (!isint1(la)) D = RgX_Rg_mul(D, la);
1254 8078 : return gc_GEN(av, mkrfrac(N,D));
1255 : }
1256 :
1257 : GEN
1258 8084 : partmap_reverse_frac_worker(GEN t, GEN a, GEN b, GEN la, GEN lb, long v)
1259 8084 : { return partmap_reverse_frac(a, b, t, la, lb, v); }
1260 :
1261 : static GEN
1262 7224 : nfisincl_from_fact(GEN a, long da, GEN b, GEN la, GEN lb, long vb, GEN y,
1263 : long flag)
1264 : {
1265 7224 : long i, k, l = lg(y), db = degpol(b), d = db / da;
1266 7224 : GEN x = cgetg(l, t_VEC);
1267 7623 : for (i= k = 1; i < l; i++)
1268 : {
1269 7441 : GEN t = gel(y,i);
1270 7441 : if (degpol(t) != d) continue;
1271 7343 : gel(x, k++) = partmap_reverse(a, b, t, la, lb, vb);
1272 7336 : if (flag) return gel(x,1);
1273 : }
1274 182 : if (k==1) return gen_0;
1275 91 : setlg(x, k);
1276 91 : gen_sort_inplace(x, (void*)&cmp_RgX, &cmp_nodata, NULL);
1277 91 : return x;
1278 : }
1279 :
1280 : static GEN
1281 1232 : nfisincl_from_fact_frac(GEN a, GEN b, GEN la, GEN lb, long vb, GEN y)
1282 : {
1283 1232 : long i, k, l = lg(y), d = degpol(b) / degpol(a);
1284 1232 : GEN worker, x = cgetg(l, t_VEC);
1285 9317 : for (i = k = 1; i < l; i++)
1286 : {
1287 8085 : GEN t = gel(y,i);
1288 8085 : if (degpol(t) != d) continue;
1289 8085 : gel(x, k++) = t;
1290 : }
1291 1232 : if (k==1) return gen_0;
1292 1232 : worker = snm_closure(is_entry("_partmap_reverse_frac_worker"),
1293 : mkvec5(a,b,la,lb,stoi(vb)));
1294 1232 : setlg(x, k); return gen_parapply(worker, x);
1295 : }
1296 :
1297 : GEN
1298 7336 : nfisincl0(GEN fa, GEN fb, long flag)
1299 : {
1300 7336 : pari_sp av = avma;
1301 : long vb;
1302 : GEN a, b, nfa, nfb, x, y, la, lb;
1303 : int newvar;
1304 7336 : if (flag < 0 || flag > 3) pari_err_FLAG("nfisincl");
1305 :
1306 7336 : a = get_nfpol(fa, &nfa);
1307 7336 : b = get_nfpol(fb, &nfb);
1308 7336 : if (!nfa) { a = Q_primpart(a); RgX_check_ZX(a, "nsisincl"); }
1309 7336 : if (!nfb) { b = Q_primpart(b); RgX_check_ZX(b, "nsisincl"); }
1310 7336 : if (ZX_equal(a, b) && flag<=1)
1311 : {
1312 21 : if (flag==1)
1313 : {
1314 7 : x = pol_x(varn(b));
1315 7 : return degpol(b) > 1 ? x: RgX_rem(x,b);
1316 : }
1317 14 : x = galoisconj(fb, NULL); settyp(x, t_VEC);
1318 14 : return gc_GEN(av,x);
1319 : }
1320 7315 : if (flag==0 && !tests_OK(a, nfa, b, nfb, 0)) { set_avma(av); return gen_0; }
1321 :
1322 7196 : if (nfb) lb = gen_1; else nfb = b = ZX_Q_normalize(b,&lb);
1323 7196 : if (nfa) la = gen_1; else nfa = a = ZX_Q_normalize(a,&la);
1324 7196 : vb = varn(b); newvar = (varncmp(varn(a),vb) <= 0);
1325 7196 : if (newvar) { b = leafcopy(b); setvarn(b, fetch_var_higher()); }
1326 7196 : y = lift_shallow(gel(nffactor(nfa,b),1));
1327 7196 : if (flag==2)
1328 0 : x = nfisincl_from_fact_frac(a, b, la, lb, vb, y);
1329 : else
1330 7196 : x = nfisincl_from_fact(nfa, degpol(a), b, la, lb, vb, y, flag);
1331 7189 : if (newvar) (void)delete_var();
1332 7189 : return gc_GEN(av,x);
1333 : }
1334 :
1335 : GEN
1336 112 : nfisincl(GEN fa, GEN fb) { return nfisincl0(fa, fb, 0); }
1337 :
1338 : static GEN
1339 8092 : RgF_to_Flxq(GEN F, GEN T, ulong p)
1340 : {
1341 : GEN N, D, iD;
1342 8092 : if (typ(F)==t_POL) return RgX_to_Flx(F, p);
1343 8085 : N = RgX_to_Flx(gel(F,1), p); D = RgX_to_Flx(gel(F,2), p);
1344 8085 : iD = Flxq_invsafe(D, T, p);
1345 8085 : if (!iD) return NULL;
1346 8078 : return Flxq_mul(N, iD, T, p);
1347 : }
1348 :
1349 : #define pari_APPLY_abort(EXPR)\
1350 : { \
1351 : long i, _l; \
1352 : GEN _y = cgetg_copy(x, &_l);\
1353 : for (i=1; i<_l; i++) \
1354 : { GEN _z = EXPR;\
1355 : if (!_z) return _z;\
1356 : gel(_y,i) = _z;\
1357 : } return _y;\
1358 : }
1359 :
1360 : static GEN
1361 1239 : RgFV_to_FlxqV(GEN x, GEN T, ulong p)
1362 9324 : { pari_APPLY_abort(RgF_to_Flxq(gel(x,i), T, p)) }
1363 :
1364 : static GEN
1365 1232 : nfsplitting_auto(GEN g, GEN R)
1366 : {
1367 : pari_sp av;
1368 : forprime_t T;
1369 1232 : long i, d = degpol(g);
1370 : ulong p;
1371 1232 : GEN P, K, N, G, q, den = Q_denom(R), Rp, Gp;
1372 1232 : u_forprime_init(&T, d*maxss(expu(d)-3, 2), ULONG_MAX);
1373 1232 : av = avma;
1374 79408 : for(;; set_avma(av))
1375 : {
1376 80640 : p = u_forprime_next(&T);
1377 80640 : if (dvdiu(den,p)) continue;
1378 80640 : Gp = ZX_to_Flx(g, p);
1379 80640 : if (!Flx_is_totally_split(Gp, p)) continue;
1380 1239 : P = Flx_roots(Gp, p);
1381 1239 : Rp = RgFV_to_FlxqV(R, Gp, p);
1382 1239 : if (Rp) break;
1383 7 : if (DEBUGLEVEL) err_printf("nfsplitting_auto: bad p : %lu\n",p);
1384 : }
1385 1232 : if (d == 1) return mkvec3(g, mkcol(gel(Rp,1)), utoi(p));
1386 1225 : K = Flm_Flc_invimage(FlxV_to_Flm(Rp, d), vecsmall_ei(d, 2), p);
1387 1225 : if (!K) pari_err_BUG("nfsplitting_auto");
1388 1225 : N = Flm_transpose(FlxV_Flv_multieval(Rp, P, p));
1389 1225 : q = perm_inv(vecsmall_indexsort(gel(N,1)));
1390 1225 : G = cgetg(d+1, t_COL);
1391 35707 : for (i=1; i<=d; i++)
1392 : {
1393 34482 : GEN r = perm_mul(vecsmall_indexsort(gel(N,i)), q);
1394 34482 : gel(G,i) = FlxV_Flc_mul(Rp, vecsmallpermute(K, r), p);
1395 : }
1396 1225 : return mkvec3(g, G, utoi(p));
1397 : }
1398 :
1399 : static GEN
1400 1421 : nfsplitting_composite(GEN P)
1401 : {
1402 1421 : GEN F = gel(ZX_factor(P), 1), Q = NULL;
1403 1421 : long i, n = lg(F)-1;
1404 2849 : for (i = 1; i <= n; i++)
1405 : {
1406 1428 : GEN Fi = gel(F, i);
1407 1428 : if (degpol(Fi) == 1) continue;
1408 1400 : Q = Q ? veclast(compositum(Q, Fi)): Fi;
1409 : }
1410 1421 : return Q ? Q: pol_x(varn(P));
1411 : }
1412 : GEN
1413 1435 : nfsplitting0(GEN T0, GEN D, long flag)
1414 : {
1415 1435 : pari_sp av = avma;
1416 : long d, Ds, v;
1417 1435 : GEN T, F, K, N = NULL, lT = NULL;
1418 1435 : if (flag < 0 || flag > 3) pari_err_FLAG("nfsplitting");
1419 1435 : T = T0 = get_nfpol(T0, &K);
1420 1428 : if (!K)
1421 : {
1422 : GEN c;
1423 1407 : if (typ(T) != t_POL) pari_err_TYPE("nfsplitting",T);
1424 1407 : T = Q_primitive_part(T, &c);
1425 1407 : lT = leading_coeff(T); if (isint1(lT)) lT = NULL;
1426 1407 : if (flag && (c || lT)) pari_err_TYPE("nfsplitting", T0);
1427 1400 : RgX_check_ZX(T,"nfsplitting");
1428 : }
1429 1421 : T = nfsplitting_composite(T);
1430 1421 : if (flag && !ZX_equal(T, T0)) pari_err_IRREDPOL("nfsplitting", T0);
1431 1407 : d = degpol(T); v = varn(T);
1432 1407 : if (d <= 1 && !flag) { set_avma(av); return pol_x(v); }
1433 1379 : if (!K) {
1434 1358 : if (lT) T = polredbest(T,0);
1435 1358 : K = T;
1436 : }
1437 1379 : if (D)
1438 1239 : { if (typ(D) != t_INT || signe(D) < 1) pari_err_TYPE("nfsplitting",D); }
1439 140 : else if (d <= 7 ||
1440 35 : (d <= 11 && pari_is_dir(stack_strcat(pari_datadir, "/galdata"))))
1441 126 : D = gel(polgalois(T,DEFAULTPREC), 1);
1442 : else
1443 14 : D = mpfact(d);
1444 1379 : Ds = itos_or_0(D);
1445 1379 : T = leafcopy(T); setvarn(T, fetch_var_higher());
1446 1379 : for(F = T;;)
1447 1659 : {
1448 3038 : GEN P = gel(nffactor(K, F), 1), Q = veclast(P);
1449 3038 : if (degpol(gel(P,1)) == degpol(Q))
1450 : {
1451 1288 : if (!flag) break;
1452 1260 : P = liftall_shallow(P);
1453 1260 : if (flag==1)
1454 28 : N = nfisincl_from_fact(K, d, F, gen_1, gen_1, v, P, flag);
1455 : else
1456 1232 : N = nfisincl_from_fact_frac(T0, F, gen_1, gen_1, v, P);
1457 1260 : break;
1458 : }
1459 1750 : F = rnfequation(K,Q);
1460 1750 : if (degpol(F) == Ds && !flag) break;
1461 : }
1462 1379 : if (umodiu(D,degpol(F)))
1463 : {
1464 14 : char *sD = itostr(D);
1465 14 : pari_warn(warner,stack_strcat("ignoring incorrect degree bound ",sD));
1466 : }
1467 1379 : setvarn(F, v); (void)delete_var();
1468 1379 : if (flag) F = flag == 3? nfsplitting_auto(F, N): mkvec2(F, N);
1469 1379 : return gc_GEN(av, F);
1470 : }
1471 :
1472 : GEN
1473 0 : nfsplitting(GEN T, GEN D) { return nfsplitting0(T, D, 0); }
1474 :
1475 : /*************************************************************************/
1476 : /** **/
1477 : /** INITALG **/
1478 : /** **/
1479 : /*************************************************************************/
1480 : typedef struct {
1481 : GEN T;
1482 : GEN ro; /* roots of T */
1483 : long r1;
1484 : GEN basden;
1485 : long prec;
1486 : long extraprec; /* possibly -1 = irrelevant or not computed */
1487 : GEN M, G; /* possibly NULL = irrelevant or not computed */
1488 : } nffp_t;
1489 :
1490 : static GEN
1491 242556 : get_roots(GEN x, long r1, long prec)
1492 : {
1493 : long i, ru;
1494 : GEN z;
1495 242556 : if (typ(x) != t_POL)
1496 : {
1497 0 : z = leafcopy(x);
1498 0 : ru = (lg(z)-1 + r1) >> 1;
1499 : }
1500 : else
1501 : {
1502 242556 : long n = degpol(x);
1503 242556 : z = (r1 == n)? ZX_realroots_irred(x, prec): QX_complex_roots(x,prec);
1504 242570 : ru = (n+r1)>>1;
1505 : }
1506 525240 : for (i=r1+1; i<=ru; i++) gel(z,i) = gel(z, (i<<1)-r1);
1507 242570 : z[0]=evaltyp(t_VEC)|_evallg(ru+1); return z;
1508 : }
1509 :
1510 : GEN
1511 0 : nf_get_allroots(GEN nf)
1512 : {
1513 0 : return embed_roots(nf_get_roots(nf), nf_get_r1(nf));
1514 : }
1515 :
1516 : /* For internal use. compute trace(x mod pol), sym=polsym(pol,deg(pol)-1) */
1517 : static GEN
1518 393550 : quicktrace(GEN x, GEN sym)
1519 : {
1520 393550 : GEN p1 = gen_0;
1521 : long i;
1522 :
1523 393550 : if (typ(x) != t_POL) return gmul(x, gel(sym,1));
1524 393550 : if (signe(x))
1525 : {
1526 393550 : sym--;
1527 2892671 : for (i=lg(x)-1; i>1; i--)
1528 2499170 : p1 = gadd(p1, gmul(gel(x,i),gel(sym,i)));
1529 : }
1530 393501 : return p1;
1531 : }
1532 :
1533 : static GEN
1534 85311 : get_Tr(GEN mul, GEN x, GEN basden)
1535 : {
1536 85311 : GEN t, bas = gel(basden,1), den = gel(basden,2);
1537 85311 : long i, j, n = lg(bas)-1;
1538 85311 : GEN T = cgetg(n+1,t_MAT), TW = cgetg(n+1,t_COL), sym = polsym(x, n-1);
1539 :
1540 85310 : gel(TW,1) = utoipos(n);
1541 269389 : for (i=2; i<=n; i++)
1542 : {
1543 184079 : t = quicktrace(gel(bas,i), sym);
1544 184076 : if (den && gel(den,i)) t = diviiexact(t,gel(den,i));
1545 184078 : gel(TW,i) = t; /* tr(w[i]) */
1546 : }
1547 85310 : gel(T,1) = TW;
1548 269393 : for (i=2; i<=n; i++)
1549 : {
1550 184083 : gel(T,i) = cgetg(n+1,t_COL); gcoeff(T,1,i) = gel(TW,i);
1551 741212 : for (j=2; j<=i; j++) /* Tr(W[i]W[j]) */
1552 557129 : gcoeff(T,i,j) = gcoeff(T,j,i) = ZV_dotproduct(gel(mul,j+(i-1)*n), TW);
1553 : }
1554 85310 : return T;
1555 : }
1556 :
1557 : /* return [bas[i]*denom(bas[i]), denom(bas[i])], denom 1 is given as NULL */
1558 : static GEN
1559 206300 : get_bas_den(GEN bas)
1560 : {
1561 206300 : GEN b,d,den, dbas = leafcopy(bas);
1562 206302 : long i, l = lg(bas);
1563 206302 : int power = 1;
1564 206302 : den = cgetg(l,t_VEC);
1565 957614 : for (i=1; i<l; i++)
1566 : {
1567 751321 : b = Q_remove_denom(gel(bas,i), &d);
1568 751301 : gel(dbas,i) = b;
1569 751301 : gel(den,i) = d; if (d) power = 0;
1570 : }
1571 206293 : if (power) den = NULL; /* power basis */
1572 206293 : return mkvec2(dbas, den);
1573 : }
1574 :
1575 : GEN
1576 557003 : nf_multable_worker(GEN ij, GEN w, GEN invbas, GEN T)
1577 : {
1578 557003 : pari_sp av = avma;
1579 557003 : long i = ij[1], j = ij[2];
1580 557003 : GEN z = (i == j)? ZXQ_sqr(gel(w,i), T): ZXQ_mul(gel(w,i),gel(w,j), T);
1581 556988 : z = ZM_ZX_mul(invbas, z); /* integral column */
1582 556607 : return gc_upto(av,z);
1583 : }
1584 :
1585 : /* return multiplication table for S->basis */
1586 : static GEN
1587 85306 : nf_multable(nfmaxord_t *S, GEN invbas)
1588 : {
1589 : pari_timer ti;
1590 : struct pari_mt pt;
1591 85306 : GEN T = S->T, den = gel(S->basden,2);
1592 85306 : long n = degpol(T), l = n*(n-1)>>1, k, pending = 0;
1593 85309 : GEN worker = snm_closure(is_entry("_nf_multable_worker"),
1594 85309 : mkvec3(gel(S->basden,1), invbas, T));
1595 85311 : GEN W = mkvec(mkvecsmall2(1,n)), w = gel(W,1);
1596 85310 : GEN mul = cgetg(n*n+1,t_MAT);
1597 85310 : if (DEBUGLEVEL>=3) timer_start(&ti);
1598 : /* i = 1 split for efficiency, assume w[1] = 1 */
1599 354701 : for (k=1; k<=n; k++)
1600 269392 : gel(mul,k) = gel(mul,1+(k-1)*n) = col_ei(n, k);
1601 85309 : mt_queue_start_lim(&pt, worker, l);
1602 651828 : for (k = 1; k <= l || pending; k++)
1603 : {
1604 566520 : pari_sp av = avma;
1605 : long workid;
1606 : GEN done;
1607 566520 : if (k <= l && w[2]++ == n) w[2] = ++w[1];
1608 566520 : mt_queue_submit(&pt, w[1]*n+w[2]-1, k<=l? W: NULL);
1609 566523 : done = mt_queue_get(&pt, &workid, &pending);
1610 566522 : if (done)
1611 : {
1612 557129 : long i = workid/n, j = (workid%n)+1;
1613 557129 : if (den)
1614 : {
1615 352410 : GEN d = mul_denom(gel(den,i), gel(den,j));
1616 352403 : if (d) done = gc_upto(av, ZC_Z_divexact(done, d));
1617 : }
1618 557127 : gel(mul,j+(i-1)*n) = gel(mul,i+(j-1)*n) = done;
1619 : }
1620 : }
1621 85308 : if (DEBUGLEVEL>=3) timer_printf(&ti,"nf_multable");
1622 85308 : mt_queue_end(&pt); return mul;
1623 : }
1624 :
1625 : /* as get_Tr, mul_table not precomputed */
1626 : static GEN
1627 28809 : make_Tr(nfmaxord_t *S)
1628 : {
1629 28809 : GEN T = S->T, w = gel(S->basden,1), den = gel(S->basden,2);
1630 28809 : long i,j, n = degpol(T);
1631 28809 : GEN c, t, d, M = cgetg(n+1,t_MAT), sym = polsym(T, n-1);
1632 :
1633 : /* W[i] = w[i]/den[i]; assume W[1] = 1, case i = 1 split for efficiency */
1634 28809 : c = cgetg(n+1,t_COL); gel(M,1) = c;
1635 28810 : gel(c, 1) = utoipos(n);
1636 86095 : for (j=2; j<=n; j++)
1637 : {
1638 57285 : pari_sp av = avma;
1639 57285 : t = quicktrace(gel(w,j), sym);
1640 57282 : if (den)
1641 : {
1642 36578 : d = gel(den,j);
1643 36578 : if (d) t = diviiexact(t, d);
1644 : }
1645 57278 : gel(c,j) = gc_INT(av, t);
1646 : }
1647 86088 : for (i=2; i<=n; i++)
1648 : {
1649 57286 : c = cgetg(n+1,t_COL); gel(M,i) = c;
1650 209473 : for (j=1; j<i ; j++) gel(c,j) = gcoeff(M,i,j);
1651 209463 : for ( ; j<=n; j++)
1652 : {
1653 152185 : pari_sp av = avma;
1654 152185 : t = (i == j)? ZXQ_sqr(gel(w,i), T): ZXQ_mul(gel(w,i),gel(w,j), T);
1655 152188 : t = quicktrace(t, sym);
1656 152169 : if (den)
1657 : {
1658 119027 : d = mul_denom(gel(den,i),gel(den,j));
1659 119029 : if (d) t = diviiexact(t, d);
1660 : }
1661 152169 : gel(c,j) = gc_INT(av, t); /* Tr (W[i]W[j]) */
1662 : }
1663 : }
1664 28802 : return M;
1665 : }
1666 :
1667 : /* [bas[i]/den[i]]= integer basis. roo = real part of the roots */
1668 : static void
1669 269390 : make_M(nffp_t *F, int trunc)
1670 : {
1671 269390 : GEN bas = gel(F->basden,1), den = gel(F->basden,2), ro = F->ro;
1672 : GEN m, d, M;
1673 269390 : long i, j, l = lg(ro), n = lg(bas);
1674 269390 : M = cgetg(n,t_MAT);
1675 269387 : gel(M,1) = const_col(l-1, gen_1); /* bas[1] = 1 */
1676 940305 : for (j=2; j<n; j++) gel(M,j) = cgetg(l,t_COL);
1677 871589 : for (i=1; i<l; i++)
1678 : {
1679 602237 : GEN r = gel(ro,i), ri;
1680 602237 : ri = (gexpo(r) > 1)? ginv(r): NULL;
1681 2923792 : for (j=2; j<n; j++) gcoeff(M,i,j) = RgX_cxeval(gel(bas,j), r, ri);
1682 : }
1683 269352 : if (den)
1684 533532 : for (j=2; j<n; j++)
1685 : {
1686 414184 : d = gel(den,j); if (!d) continue;
1687 350105 : m = gel(M,j);
1688 1751863 : for (i=1; i<l; i++) gel(m,i) = gdiv(gel(m,i), d);
1689 : }
1690 :
1691 269345 : if (trunc && gprecision(M) > F->prec)
1692 : {
1693 18340 : M = gprec_w(M, F->prec);
1694 18340 : F->ro = gprec_w(ro,F->prec);
1695 : }
1696 269345 : F->M = M;
1697 269345 : }
1698 :
1699 : /* return G real such that G~ * G = T_2 */
1700 : static void
1701 269378 : make_G(nffp_t *F)
1702 : {
1703 269378 : GEN G, M = F->M;
1704 269378 : long i, j, k, r1 = F->r1, l = lg(M);
1705 :
1706 269378 : if (r1 == l-1) { F->G = M; return; }
1707 220938 : G = cgetg(l, t_MAT);
1708 1023402 : for (j = 1; j < l; j++)
1709 : {
1710 802501 : GEN g, m = gel(M,j);
1711 802501 : gel(G,j) = g = cgetg(l, t_COL);
1712 1334690 : for (k = i = 1; i <= r1; i++) gel(g,k++) = gel(m,i);
1713 2654302 : for ( ; k < l; i++)
1714 : {
1715 1851842 : GEN r = gel(m,i);
1716 1851842 : if (typ(r) == t_COMPLEX)
1717 : {
1718 1513782 : GEN a = gel(r,1), b = gel(r,2);
1719 1513782 : gel(g,k++) = mpadd(a, b);
1720 1513759 : gel(g,k++) = mpsub(a, b);
1721 : }
1722 : else
1723 : {
1724 338060 : gel(g,k++) = r;
1725 338060 : gel(g,k++) = r;
1726 : }
1727 : }
1728 : }
1729 220901 : F->G = G;
1730 : }
1731 :
1732 : static long
1733 301993 : prec_fix(long prec)
1734 : {
1735 : #ifndef LONG_IS_64BIT
1736 : /* make sure that default accuracy is the same on 32/64bit */
1737 43214 : if (odd(prec2lg(prec))) prec+=EXTRAPRECWORD;
1738 : #endif
1739 301993 : return prec;
1740 : }
1741 : static void
1742 269382 : make_M_G(nffp_t *F, int trunc)
1743 : {
1744 : long n, eBD, prec;
1745 269382 : if (F->extraprec < 0)
1746 : { /* not initialized yet; compute roots so that absolute accuracy
1747 : * of M & G >= prec */
1748 : double er;
1749 269361 : n = degpol(F->T);
1750 269360 : eBD = 1 + gexpo(gel(F->basden,1));
1751 269358 : er = F->ro? (1+gexpo(F->ro)): fujiwara_bound(F->T);
1752 269359 : if (er < 0) er = 0;
1753 269359 : F->extraprec = nbits2extraprec(n*er + eBD + log2(n));
1754 : }
1755 269380 : prec = prec_fix(F->prec + F->extraprec);
1756 269380 : if (!F->ro || gprecision(gel(F->ro,1)) < prec)
1757 242557 : F->ro = get_roots(F->T, F->r1, prec);
1758 :
1759 269391 : make_M(F, trunc);
1760 269379 : make_G(F);
1761 269370 : }
1762 :
1763 : static void
1764 177549 : nffp_init(nffp_t *F, nfmaxord_t *S, long prec)
1765 : {
1766 177549 : F->T = S->T;
1767 177549 : F->r1 = S->r1;
1768 177549 : F->basden = S->basden;
1769 177549 : F->ro = NULL;
1770 177549 : F->extraprec = -1;
1771 177549 : F->prec = prec;
1772 177549 : }
1773 :
1774 : /* let bas a t_VEC of QX giving a Z-basis of O_K. Return the index of the
1775 : * basis. Assume bas[1] = 1 and that the leading coefficient of elements
1776 : * of bas are of the form 1/b for a t_INT b */
1777 : static GEN
1778 2597 : get_nfindex(GEN bas)
1779 : {
1780 2597 : pari_sp av = avma;
1781 2597 : long n = lg(bas)-1, i;
1782 : GEN D, d, mat;
1783 :
1784 : /* assume bas[1] = 1 */
1785 2597 : D = gel(bas,1);
1786 2597 : if (! is_pm1(simplify_shallow(D))) pari_err_TYPE("get_nfindex", D);
1787 2597 : D = gen_1;
1788 12418 : for (i = 2; i <= n; i++)
1789 : { /* after nfbasis, basis is upper triangular! */
1790 9828 : GEN B = gel(bas,i), lc;
1791 9828 : if (degpol(B) != i-1) break;
1792 9821 : lc = gel(B, i+1);
1793 9821 : switch (typ(lc))
1794 : {
1795 4013 : case t_INT: continue;
1796 5808 : case t_FRAC: if (is_pm1(gel(lc,1)) ) {D = mulii(D, gel(lc,2)); continue;}
1797 0 : default: pari_err_TYPE("get_nfindex", B);
1798 : }
1799 : }
1800 2597 : if (i <= n)
1801 : { /* not triangular after all */
1802 7 : bas = vecslice(bas,i,n);
1803 7 : bas = Q_remove_denom(bas, &d);
1804 7 : if (!d) return D;
1805 7 : mat = RgV_to_RgM(bas, n);
1806 7 : mat = rowslice(mat, i,n);
1807 7 : D = mulii(D, diviiexact(powiu(d, n-i+1), absi_shallow(ZM_det(mat))));
1808 : }
1809 2597 : return gc_INT(av, D);
1810 : }
1811 : /* make sure all components of S are initialized */
1812 : static void
1813 170600 : nfmaxord_complete(nfmaxord_t *S)
1814 : {
1815 170600 : if (!S->dT) S->dT = ZX_disc(S->T);
1816 170600 : if (!S->index)
1817 : {
1818 2597 : if (S->dK) /* fast */
1819 0 : S->index = sqrti( diviiexact(S->dT, S->dK) );
1820 : else
1821 2597 : S->index = get_nfindex(S->basis);
1822 : }
1823 170600 : if (!S->dK) S->dK = diviiexact(S->dT, sqri(S->index));
1824 170600 : if (S->r1 < 0) S->r1 = ZX_sturm_irred(S->T);
1825 170608 : if (!S->basden) S->basden = get_bas_den(S->basis);
1826 170604 : }
1827 :
1828 : GEN
1829 85304 : nfmaxord_to_nf(nfmaxord_t *S, GEN ro, long prec)
1830 : {
1831 85304 : GEN nf = cgetg(10,t_VEC);
1832 85305 : GEN T = S->T, Tr, D, w, A, dA, MDI, mat = cgetg(9,t_VEC);
1833 85304 : long n = degpol(T);
1834 : nffp_t F;
1835 85304 : nfmaxord_complete(S);
1836 85304 : nffp_init(&F,S,prec);
1837 85304 : F.ro = ro;
1838 85304 : make_M_G(&F, 0);
1839 :
1840 85307 : gel(nf,1) = S->T;
1841 85307 : gel(nf,2) = mkvec2s(S->r1, (n - S->r1)>>1);
1842 85309 : gel(nf,3) = S->dK;
1843 85309 : gel(nf,4) = S->index;
1844 85309 : gel(nf,5) = mat;
1845 85309 : if (gprecision(gel(F.ro,1)) > prec) F.ro = gprec_wtrunc(F.ro, prec);
1846 85307 : gel(nf,6) = F.ro;
1847 85307 : w = S->basis;
1848 85307 : if (!is_pm1(S->index)) w = Q_remove_denom(w, NULL);
1849 85308 : gel(nf,7) = w;
1850 85308 : gel(nf,8) = ZM_inv(RgV_to_RgM(w,n), NULL);
1851 85309 : gel(nf,9) = nf_multable(S, nf_get_invzk(nf));
1852 85309 : gel(mat,1) = F.M;
1853 85309 : gel(mat,2) = F.G;
1854 :
1855 85309 : Tr = get_Tr(gel(nf,9), T, S->basden);
1856 85310 : gel(mat,6) = A = ZM_inv(Tr, &dA); /* dA T^-1, primitive */
1857 85310 : A = ZM_hnfmodid(A, dA);
1858 : /* CAVEAT: nf is not complete yet, but the fields needed for
1859 : * idealtwoelt, zk_scalar_or_multable and idealinv are present ! */
1860 85312 : MDI = idealtwoelt(nf, A);
1861 85311 : gel(MDI,2) = zk_scalar_or_multable(nf, gel(MDI,2));
1862 85308 : gel(mat,7) = MDI;
1863 85308 : if (is_pm1(S->index))
1864 : { /* principal ideal (T'), whose norm is |dK| */
1865 49653 : D = zk_scalar_or_multable(nf, ZX_deriv(T));
1866 49653 : if (typ(D) == t_MAT) D = ZM_hnfmod(D, absi_shallow(S->dK));
1867 : }
1868 : else
1869 : {
1870 35655 : GEN c = diviiexact(dA, gcoeff(A,1,1));
1871 35655 : D = idealHNF_inv_Z(nf, A); /* (A\cap Z) / A */
1872 35657 : if (!is_pm1(c)) D = ZM_Z_mul(D, c);
1873 : }
1874 85311 : gel(mat,3) = RM_round_maxrank(F.G);
1875 85309 : gel(mat,4) = Tr;
1876 85309 : gel(mat,5) = D;
1877 85309 : w = S->dKP; if (!w) { w = gel(absZ_factor(S->dK), 1); settyp(w, t_VEC); }
1878 85309 : gel(mat,8) = w; return nf;
1879 : }
1880 :
1881 : static GEN
1882 3367 : primes_certify(GEN dK, GEN dKP)
1883 : {
1884 3367 : long i, l = lg(dKP);
1885 3367 : GEN v, w, D = dK;
1886 3367 : v = vectrunc_init(l);
1887 3367 : w = vectrunc_init(l);
1888 10465 : for (i = 1; i < l; i++)
1889 : {
1890 7098 : GEN p = gel(dKP,i);
1891 7098 : vectrunc_append(isprime(p)? w: v, p);
1892 7098 : (void)Z_pvalrem(D, p, &D);
1893 : }
1894 3367 : if (!is_pm1(D))
1895 : {
1896 0 : D = absi_shallow(D);
1897 0 : vectrunc_append(isprime(D)? w: v, D);
1898 : }
1899 3367 : return mkvec2(v,w);
1900 : }
1901 : GEN
1902 3367 : nfcertify(GEN nf)
1903 : {
1904 3367 : pari_sp av = avma;
1905 : GEN vw;
1906 3367 : nf = checknf(nf);
1907 3367 : vw = primes_certify(nf_get_disc(nf), nf_get_ramified_primes(nf));
1908 3367 : return gc_GEN(av, gel(vw,1));
1909 : }
1910 :
1911 : /* set *pro to roots of S->T */
1912 : static GEN
1913 73891 : get_red_G(nfmaxord_t *S, GEN *pro)
1914 : {
1915 73891 : pari_sp av = avma;
1916 73891 : GEN G, u, u0 = NULL;
1917 73891 : long prec, n = degpol(S->T);
1918 : nffp_t F;
1919 :
1920 73891 : prec = nbits2prec(n+32);
1921 73891 : nffp_init(&F, S, prec);
1922 : for (;;)
1923 : {
1924 73891 : F.prec = prec; make_M_G(&F, 0); G = F.G;
1925 73886 : if (u0) G = RgM_mul(G, u0);
1926 73886 : if (DEBUGLEVEL)
1927 0 : err_printf("get_red_G: starting LLL, prec = %ld (%ld + %ld)\n",
1928 0 : prec + F.extraprec, prec, F.extraprec);
1929 73886 : if ((u = lllfp(G, 0.99, LLL_KEEP_FIRST)))
1930 : {
1931 73893 : if (lg(u)-1 == n) break;
1932 : /* singular ==> loss of accuracy */
1933 0 : if (u0) u0 = gc_upto(av, RgM_mul(u0,u));
1934 0 : else u0 = gc_GEN(av, u);
1935 : }
1936 0 : prec = precdbl(prec) + nbits2extraprec(gexpo(u0));
1937 0 : F.ro = NULL;
1938 0 : if (DEBUGLEVEL) pari_warn(warnprec,"get_red_G", prec);
1939 : }
1940 73893 : if (u0) u = RgM_mul(u0,u);
1941 73892 : *pro = F.ro; return u;
1942 : }
1943 :
1944 : /* Compute an LLL-reduced basis for the integer basis of nf(T).
1945 : * set *pro = roots of x if computed [NULL if not computed] */
1946 : static void
1947 103385 : set_LLL_basis(nfmaxord_t *S, GEN *pro, long flag, double DELTA)
1948 : {
1949 103385 : GEN B = S->basis;
1950 103385 : long N = degpol(S->T);
1951 103385 : if (S->r1 < 0)
1952 : {
1953 18179 : S->r1 = ZX_sturm_irred(S->T);
1954 18179 : if (odd(N - S->r1)) pari_err_IRREDPOL("set_LLL_basis", S->T);
1955 : }
1956 103378 : if (!S->basden) S->basden = get_bas_den(B);
1957 103378 : *pro = NULL; if (flag & nf_NOLLL) return;
1958 102699 : if (S->r1 == N) {
1959 28809 : pari_sp av = avma;
1960 28809 : GEN u = ZM_lll(make_Tr(S), DELTA, LLL_GRAM|LLL_KEEP_FIRST|LLL_IM);
1961 28811 : B = gc_upto(av, RgV_RgM_mul(B, u));
1962 : }
1963 : else
1964 73890 : B = RgV_RgM_mul(B, get_red_G(S, pro));
1965 102701 : S->basis = B;
1966 102701 : S->basden = get_bas_den(B);
1967 : }
1968 :
1969 : /* = 1 iff |a| > |b| or equality and a > 0 */
1970 : static int
1971 128468 : cmpii_polred(GEN a, GEN b)
1972 : {
1973 128468 : int fl = abscmpii(a, b);
1974 : long sa, sb;
1975 128468 : if (fl) return fl;
1976 106837 : sa = signe(a);
1977 106837 : sb = signe(b);
1978 106837 : if (sa == sb) return 0;
1979 929 : return sa == 1? 1: -1;
1980 : }
1981 : static int
1982 30324 : ZX_cmp(GEN x, GEN y)
1983 30324 : { return gen_cmp_RgX((void*)cmpii_polred, x, y); }
1984 : /* current best: ZX x of discriminant *dx, is ZX y better than x ?
1985 : * (if so update *dx); both x and y are monic */
1986 : static int
1987 52054 : ZX_is_better(GEN y, GEN x, GEN *dx)
1988 : {
1989 : pari_sp av;
1990 : int cmp;
1991 : GEN d;
1992 52054 : if (!*dx) *dx = ZX_disc(x);
1993 52054 : av = avma; d = ZX_disc(y);
1994 52054 : cmp = abscmpii(d, *dx);
1995 52054 : if (cmp < 0) { *dx = d; return 1; }
1996 47544 : return gc_bool(av, cmp? 0: (ZX_cmp(y, x) < 0));
1997 : }
1998 :
1999 : static void polredbest_aux(nfmaxord_t *S, GEN *pro, GEN *px, GEN *pdx, GEN *pa);
2000 : /* Seek a simpler, polynomial pol defining the same number field as
2001 : * x (assumed to be monic at this point) */
2002 : static GEN
2003 280 : nfpolred(nfmaxord_t *S, GEN *pro)
2004 : {
2005 280 : GEN x = S->T, dx, b, rev;
2006 280 : long n = degpol(x), v = varn(x);
2007 :
2008 280 : if (n == 1) {
2009 98 : S->T = pol_x(v);
2010 98 : *pro = NULL;
2011 98 : return scalarpol_shallow(negi(gel(x,2)), v);
2012 : }
2013 182 : polredbest_aux(S, pro, &x, &dx, &b);
2014 182 : if (x == S->T) return NULL; /* no improvement */
2015 147 : if (DEBUGLEVEL>1) err_printf("xbest = %Ps\n",x);
2016 :
2017 : /* update T */
2018 147 : rev = QXQ_reverse(b, S->T);
2019 147 : S->basis = QXV_QXQ_eval(S->basis, rev, x);
2020 147 : S->index = sqrti( diviiexact(dx,S->dK) );
2021 147 : S->basden = get_bas_den(S->basis);
2022 147 : S->dT = dx;
2023 147 : S->T = x;
2024 147 : *pro = NULL; /* reset */
2025 147 : return rev;
2026 : }
2027 :
2028 : /* Either nf type or ZX or [monic ZX, data], where data is either an integral
2029 : * basis (deprecated), or listP data (nfbasis input format) to specify
2030 : * a set of primes at with the basis order must be maximal.
2031 : * 1) nf type (or unrecognized): return t_VEC
2032 : * 2) ZX or [ZX, listP]: return t_POL
2033 : * 3) [ZX, order basis]: return 0 (deprecated)
2034 : * incorrect: return -1 */
2035 : static long
2036 87348 : nf_input_type(GEN x)
2037 : {
2038 87348 : GEN T, V, DKP = NULL;
2039 : long i, d, v;
2040 87348 : switch(typ(x))
2041 : {
2042 80705 : case t_POL: return t_POL;
2043 6643 : case t_VEC:
2044 6643 : switch(lg(x))
2045 : {
2046 2849 : case 4: DKP = gel(x,3);
2047 6615 : case 3: break;
2048 28 : default: return t_VEC; /* nf or incorrect */
2049 : }
2050 6615 : T = gel(x,1); V = gel(x,2);
2051 6615 : if (typ(T) != t_POL) return -1;
2052 6615 : switch(typ(V))
2053 : {
2054 210 : case t_INT: case t_MAT: return t_POL;
2055 6405 : case t_VEC: case t_COL:
2056 6405 : if (RgV_is_ZV(V)) return t_POL;
2057 3514 : break;
2058 0 : default: return -1;
2059 : }
2060 3514 : d = degpol(T); v = varn(T);
2061 3514 : if (d<1 || !RgX_is_ZX(T) || !isint1(gel(T,d+2)) || lg(V)-1!=d) return -1;
2062 21504 : for (i = 1; i <= d; i++)
2063 : { /* check integer basis */
2064 18011 : GEN c = gel(V,i);
2065 18011 : switch(typ(c))
2066 : {
2067 35 : case t_INT: break;
2068 17976 : case t_POL: if (varn(c) == v && RgX_is_QX(c) && degpol(c) < d) break;
2069 : /* fall through */
2070 14 : default: return -1;
2071 : }
2072 : }
2073 3493 : if (DKP && (typ(DKP) != t_VEC || !RgV_is_ZV(DKP))) return -1;
2074 3493 : return 0;
2075 : }
2076 0 : return t_VEC; /* nf or incorrect */
2077 : }
2078 :
2079 : /* cater for obsolete nf_PARTIALFACT flag */
2080 : static void
2081 3920 : nfinit_basic_partial(nfmaxord_t *S, GEN T)
2082 : {
2083 3920 : if (typ(T) == t_POL) { nfmaxord(S, mkvec2(T,utoipos(500000)), 0); }
2084 14 : else nfinit_basic(S, T);
2085 3920 : }
2086 : static void
2087 14343 : nfinit_basic_flag(nfmaxord_t *S, GEN x, long flag)
2088 : {
2089 14343 : if (flag & nf_PARTIALFACT)
2090 35 : nfinit_basic_partial(S, x);
2091 : else
2092 14308 : nfinit_basic(S, x);
2093 14336 : }
2094 :
2095 : /* true nf */
2096 : static GEN
2097 91840 : nf_basden(GEN nf)
2098 : {
2099 91840 : GEN zkD = nf_get_zkprimpart(nf), D = nf_get_zkden(nf);
2100 91840 : D = equali1(D)? NULL: const_vec(lg(zkD)-1, D);
2101 91840 : return mkvec2(zkD, D);
2102 : }
2103 : void
2104 87348 : nfinit_basic(nfmaxord_t *S, GEN T)
2105 : {
2106 87348 : switch (nf_input_type(T))
2107 : {
2108 83803 : case t_POL: nfmaxord(S, T, 0); return;
2109 28 : case t_VEC:
2110 : { /* nf, bnf, bnr */
2111 28 : GEN nf = checknf(T);
2112 28 : S->T = S->T0 = nf_get_pol(nf);
2113 28 : S->basis = nf_get_zk(nf); /* probably useless */
2114 28 : S->basden = nf_basden(nf);
2115 28 : S->index = nf_get_index(nf);
2116 28 : S->dK = nf_get_disc(nf);
2117 28 : S->dKP = nf_get_ramified_primes(nf);
2118 28 : S->dT = mulii(S->dK, sqri(S->index));
2119 28 : S->r1 = nf_get_r1(nf); break;
2120 : }
2121 3493 : case 0: /* monic integral polynomial + integer basis (+ ramified primes)*/
2122 3493 : S->T = S->T0 = gel(T,1);
2123 3493 : S->basis = gel(T,2);
2124 3493 : S->basden = NULL;
2125 3493 : S->index = NULL;
2126 3493 : S->dK = NULL;
2127 3493 : S->dKP = NULL;
2128 3493 : if (lg(T) == 4)
2129 : {
2130 2849 : GEN v = gel(T,3); if (typ(v) == t_COL) v = shallowtrans(v);
2131 2849 : S->dKP = v;
2132 : }
2133 3493 : S->dT = NULL;
2134 3493 : S->r1 = -1; break;
2135 20 : default: /* -1 */
2136 20 : pari_err_TYPE("nfinit_basic", T);
2137 : }
2138 3521 : S->dTP = S->dTE = S->dKE = NULL;
2139 3521 : S->unscale = gen_1;
2140 : }
2141 :
2142 : GEN
2143 85302 : nfinit_complete(nfmaxord_t *S, long flag, long prec)
2144 : {
2145 85302 : GEN nf, unscale = S->unscale, rev = NULL;
2146 :
2147 85302 : if (!ZX_is_irred(S->T)) pari_err_IRREDPOL("nfinit",S->T);
2148 85299 : if (!(flag & nf_RED) && !ZX_is_monic(S->T0))
2149 : {
2150 49 : pari_warn(warner,"nonmonic polynomial. Result of the form [nf,c]");
2151 49 : flag |= nf_RED | nf_ORIG;
2152 : }
2153 85299 : if (!(flag & nf_RED) && !isint1(unscale))
2154 : { /* implies lc(x0) = 1 and L := 1/unscale is integral */
2155 4515 : long d = degpol(S->T0);
2156 4515 : GEN L = ginv(unscale); /* x = L^(-deg(x)) x0(L X) */
2157 4515 : GEN f = powiu(L, (d*(d-1)) >> 1);
2158 4514 : S->T = S->T0; /* restore original user-supplied x0, unscale data */
2159 4514 : S->unscale = gen_1;
2160 4514 : S->dT = gmul(S->dT, sqri(f));
2161 4515 : S->basis = RgXV_unscale(S->basis, unscale);
2162 4514 : S->index = gmul(S->index, f);
2163 : }
2164 85299 : nfmaxord_complete(S); /* more expensive after set_LLL_basis */
2165 85304 : if (flag & nf_RED)
2166 : {
2167 : GEN ro;
2168 : /* lie to polred: more efficient to update *after* modreverse, than to
2169 : * unscale in the polred subsystem */
2170 280 : S->unscale = gen_1;
2171 280 : rev = nfpolred(S, &ro);
2172 280 : nf = nfmaxord_to_nf(S, ro, prec);
2173 280 : S->unscale = unscale; /* restore */
2174 : }
2175 : else
2176 : {
2177 85024 : GEN ro; set_LLL_basis(S, &ro, flag, 0.99);
2178 85024 : nf = nfmaxord_to_nf(S, ro, prec);
2179 : }
2180 85309 : if (flag & nf_ORIG)
2181 : {
2182 84 : if (!rev)
2183 : { /* no improvement */
2184 28 : long v = varn(S->T);
2185 28 : rev = degpol(S->T) == 1? pol_0(v): pol_x(v);
2186 : }
2187 84 : if (!isint1(unscale)) rev = RgX_Rg_div(rev, unscale);
2188 84 : nf = mkvec2(nf, mkpolmod(rev, S->T));
2189 : }
2190 85309 : return nf;
2191 : }
2192 : /* Initialize the number field defined by the polynomial x (in variable v)
2193 : * flag & nf_RED: try a polred first.
2194 : * flag & nf_ORIG: return [nfinit(x), Mod(a,red)], where
2195 : * Mod(a,red) = Mod(v,x) (i.e return the base change). */
2196 : GEN
2197 11714 : nfinit0(GEN x, long flag,long prec)
2198 : {
2199 11714 : const pari_sp av = avma;
2200 : nfmaxord_t S;
2201 11714 : if (flag < 0 || flag > 7) pari_err_FLAG("nfinit");
2202 11714 : if (checkrnf_i(x)) return rnf_build_nfabs(x, prec);
2203 11693 : nfinit_basic(&S, x);
2204 11672 : return gc_GEN(av, nfinit_complete(&S, flag, prec));
2205 : }
2206 : GEN
2207 182 : nfinitred(GEN x, long prec) { return nfinit0(x, nf_RED, prec); }
2208 : GEN
2209 0 : nfinitred2(GEN x, long prec) { return nfinit0(x, nf_RED|nf_ORIG, prec); }
2210 : GEN
2211 7311 : nfinit(GEN x, long prec) { return nfinit0(x, 0, prec); }
2212 :
2213 : /* assume x a bnr/bnf/nf */
2214 : long
2215 1281270 : nf_get_prec(GEN x)
2216 : {
2217 1281270 : GEN nf = checknf(x), ro = nf_get_roots(nf);
2218 1281265 : return (typ(ro)==t_VEC)? precision(gel(ro,1)): DEFAULTPREC;
2219 : }
2220 :
2221 : /* true nf */
2222 : GEN
2223 91812 : nfnewprec_shallow(GEN nf, long prec)
2224 : {
2225 91812 : GEN m, NF = leafcopy(nf);
2226 : nffp_t F;
2227 :
2228 91812 : F.T = nf_get_pol(nf);
2229 91812 : F.ro = NULL;
2230 91812 : F.r1 = nf_get_r1(nf);
2231 91812 : F.basden = nf_basden(nf);
2232 91812 : F.extraprec = -1;
2233 91812 : F.prec = prec; make_M_G(&F, 0);
2234 91811 : gel(NF,5) = m = leafcopy(gel(NF,5));
2235 91812 : gel(m,1) = F.M;
2236 91812 : gel(m,2) = F.G;
2237 91812 : gel(NF,6) = F.ro; return NF;
2238 : }
2239 :
2240 : /* true rnf */
2241 : GEN
2242 56 : rnfnewprec_shallow(GEN rnf, long prec)
2243 : {
2244 56 : GEN RNF = leafcopy(rnf);
2245 56 : gel(RNF,10) = nfnewprec_shallow(gel(RNF,10), prec);
2246 56 : if (obj_check(RNF, rnf_NFABS)) rnfcomplete(RNF);
2247 56 : return RNF;
2248 : }
2249 : GEN
2250 0 : rnfnewprec(GEN rnf, long prec)
2251 : {
2252 0 : pari_sp av = avma;
2253 0 : checkrnf(rnf);
2254 0 : return gc_GEN(av, rnfnewprec_shallow(rnf, prec));
2255 : }
2256 :
2257 : GEN
2258 161 : nfnewprec(GEN nf, long prec)
2259 : {
2260 161 : pari_sp av = avma;
2261 : GEN z;
2262 161 : switch(nftyp(nf))
2263 : {
2264 56 : default: pari_err_TYPE("nfnewprec", nf);
2265 0 : case typ_RNF: z = rnfnewprec_shallow(nf,prec); break;
2266 14 : case typ_BNF: z = bnfnewprec_shallow(nf,prec); break;
2267 84 : case typ_NF: z = nfnewprec_shallow(nf, prec); break;
2268 7 : case typ_BNR: return bnrnewprec(nf,prec);
2269 : }
2270 98 : return gc_GEN(av, z);
2271 : }
2272 :
2273 : /********************************************************************/
2274 : /** **/
2275 : /** POLRED **/
2276 : /** **/
2277 : /********************************************************************/
2278 : GEN
2279 0 : embednorm_T2(GEN x, long r1)
2280 : {
2281 0 : pari_sp av = avma;
2282 0 : GEN p = RgV_sumpart(x, r1);
2283 0 : GEN q = RgV_sumpart2(x,r1+1, lg(x)-1);
2284 0 : if (q != gen_0) p = gadd(p, gmul2n(q,1));
2285 0 : return avma == av? gcopy(p): gc_upto(av, p);
2286 : }
2287 :
2288 : /* simplified version of gnorm for scalar, noncomplex inputs, without GC */
2289 : static GEN
2290 167484 : real_norm(GEN x)
2291 : {
2292 167484 : switch(typ(x))
2293 : {
2294 0 : case t_INT: return sqri(x);
2295 167484 : case t_REAL: return sqrr(x);
2296 0 : case t_FRAC: return sqrfrac(x);
2297 : }
2298 0 : pari_err_TYPE("real_norm", x);
2299 : return NULL;/*LCOV_EXCL_LINE*/
2300 : }
2301 : /* simplified version of gnorm, without GC */
2302 : static GEN
2303 33954981 : complex_norm(GEN x)
2304 : {
2305 33954981 : return typ(x) == t_COMPLEX? cxnorm(x): real_norm(x);
2306 : }
2307 : /* return T2(x), argument r1 needed in case x has components whose type
2308 : * is unexpected, e.g. all of them t_INT for embed(gen_1) */
2309 : GEN
2310 72148 : embed_T2(GEN x, long r1)
2311 : {
2312 72148 : pari_sp av = avma;
2313 72148 : long i, l = lg(x);
2314 72148 : GEN c, s = NULL, t = NULL;
2315 72148 : if (typ(gel(x,1)) == t_INT) return muliu(gel(x,1), 2*(l-1)-r1);
2316 239632 : for (i = 1; i <= r1; i++)
2317 : {
2318 167484 : c = real_norm(gel(x,i));
2319 167489 : s = s? gadd(s, c): c;
2320 : }
2321 206154 : for (; i < l; i++)
2322 : {
2323 134007 : c = complex_norm(gel(x,i));
2324 134007 : t = t? gadd(t, c): c;
2325 : }
2326 72147 : if (t) { t = gmul2n(t,1); s = s? gadd(s,t): t; }
2327 72147 : return gc_upto(av, s);
2328 : }
2329 : /* return N(x) */
2330 : GEN
2331 17957270 : embed_norm(GEN x, long r1)
2332 : {
2333 17957270 : pari_sp av = avma;
2334 17957270 : long i, l = lg(x);
2335 17957270 : GEN c, s = NULL, t = NULL;
2336 17957270 : if (typ(gel(x,1)) == t_INT) return powiu(gel(x,1), 2*(l-1)-r1);
2337 46561814 : for (i = 1; i <= r1; i++)
2338 : {
2339 28731824 : c = gel(x,i);
2340 28731824 : s = s? gmul(s, c): c;
2341 : }
2342 51650754 : for (; i < l; i++)
2343 : {
2344 33820951 : c = complex_norm(gel(x,i));
2345 33820288 : t = t? gmul(t, c): c;
2346 : }
2347 17829803 : if (t) s = s? gmul(s,t): t;
2348 17829957 : return gc_upto(av, s);
2349 : }
2350 :
2351 : typedef struct {
2352 : long r1, v, prec;
2353 : GEN ZKembed; /* embeddings of fincke-pohst-reduced Zk basis */
2354 : GEN u; /* matrix giving fincke-pohst-reduced Zk basis */
2355 : GEN M; /* embeddings of initial (LLL-reduced) Zk basis */
2356 : GEN bound; /* T2 norm of the polynomial defining nf */
2357 : long expo_best_disc; /* expo(disc(x)), best generator so far */
2358 : } CG_data;
2359 :
2360 : /* characteristic pol of x (given by embeddings) */
2361 : static GEN
2362 264469 : get_pol(CG_data *d, GEN x)
2363 : {
2364 : long e;
2365 264469 : GEN g = grndtoi(roots_to_pol_r1(x, d->v, d->r1), &e);
2366 264469 : return (e > -5)? NULL: g;
2367 : }
2368 :
2369 : /* characteristic pol of x (given as vector on (w_i)) */
2370 : static GEN
2371 100461 : get_polchar(CG_data *d, GEN x)
2372 100461 : { return get_pol(d, RgM_RgC_mul(d->ZKembed,x)); }
2373 :
2374 : /* Choose a canonical polynomial in the pair { Pmin_a, Pmin_{-a} }, i.e.
2375 : * { z(X), (-1)^(deg z) z(-Z) } and keeping the smallest wrt cmpii_polred
2376 : * Either leave z alone (return 1) or set z <- (-1)^n z(-X). In place. */
2377 : int
2378 89776 : ZX_canon_neg(GEN z)
2379 : {
2380 : long i, s;
2381 131995 : for (i = lg(z)-2; i >= 2; i -= 2)
2382 : { /* examine the odd (resp. even) part of z if deg(z) even (resp. odd). */
2383 127851 : s = signe(gel(z,i));
2384 127851 : if (!s) continue;
2385 : /* non trivial */
2386 85632 : if (s < 0) break; /* z(X) < (-1)^n z(-X) */
2387 :
2388 210576 : for (; i>=2; i-=2) gel(z,i) = negi(gel(z,i));
2389 36402 : return 1;
2390 : }
2391 53374 : return 0;
2392 : }
2393 : /* return a defining polynomial for Q(alpha), v = embeddings of alpha.
2394 : * Return NULL on failure: discriminant too large or non primitive */
2395 : static GEN
2396 136483 : try_polmin(CG_data *d, nfmaxord_t *S, GEN v, long flag, GEN *ai)
2397 : {
2398 136483 : const long best = flag & nf_ABSOLUTE;
2399 : long ed;
2400 136483 : pari_sp av = avma;
2401 : GEN g;
2402 136483 : if (best)
2403 : {
2404 135916 : ed = expo(embed_disc(v, d->r1, LOWDEFAULTPREC));
2405 135916 : set_avma(av); if (d->expo_best_disc < ed) return NULL;
2406 : }
2407 : else
2408 567 : ed = 0;
2409 82401 : g = get_pol(d, v);
2410 : /* accuracy too low, compute algebraically */
2411 82402 : if (!g) { set_avma(av); g = ZXQ_charpoly(*ai, S->T, varn(S->T)); }
2412 82402 : g = ZX_radical(g);
2413 82401 : if (best && degpol(g) != degpol(S->T)) return gc_NULL(av);
2414 30500 : g = gc_GEN(av, g);
2415 30501 : d->expo_best_disc = ed;
2416 30501 : if (flag & nf_ORIG)
2417 : {
2418 27225 : if (ZX_canon_neg(g)) *ai = RgX_neg(*ai);
2419 27225 : if (!isint1(S->unscale)) *ai = RgX_unscale(*ai, S->unscale);
2420 : }
2421 : else
2422 3276 : (void)ZX_canon_neg(g);
2423 30500 : if (DEBUGLEVEL>3) err_printf("polred: generator %Ps\n", g);
2424 30500 : return g;
2425 : }
2426 :
2427 : /* does x generate the correct field ? */
2428 : static GEN
2429 100461 : chk_gen(void *data, GEN x)
2430 : {
2431 100461 : pari_sp av = avma, av1;
2432 100461 : GEN h, g = get_polchar((CG_data*)data,x);
2433 100459 : if (!g) pari_err_PREC("chk_gen");
2434 100459 : av1 = avma;
2435 100459 : h = ZX_gcd(g, ZX_deriv(g));
2436 100461 : if (degpol(h)) return gc_NULL(av);
2437 56092 : if (DEBUGLEVEL>3) err_printf(" generator: %Ps\n",g);
2438 56092 : set_avma(av1); return gc_upto(av, g);
2439 : }
2440 :
2441 : static long
2442 32613 : chk_gen_prec(long N, long bit)
2443 32613 : { return prec_fix(nbits2prec(10 + (long)log2((double)N) + bit)); }
2444 :
2445 : /* v = [P,A] two vectors (of ZX and ZV resp.) of same length; remove duplicate
2446 : * polynomials in P, updating A, in place. Among elements having the same
2447 : * characteristic pol, choose the smallest according to ZV_abscmp */
2448 : static void
2449 14000 : remove_duplicates(GEN v)
2450 : {
2451 14000 : GEN x, a, P = gel(v,1), A = gel(v,2);
2452 14000 : long k, i, l = lg(P);
2453 14000 : pari_sp av = avma;
2454 :
2455 14000 : if (l < 2) return;
2456 14000 : (void)sort_factor_pol(mkvec2(P, A), cmpii);
2457 14000 : x = gel(P,1); a = gel(A,1);
2458 54103 : for (k=1,i=2; i<l; i++)
2459 40103 : if (ZX_equal(gel(P,i), x))
2460 : {
2461 19747 : if (ZV_abscmp(gel(A,i), a) < 0) a = gel(A,i);
2462 : }
2463 : else
2464 : {
2465 20356 : gel(A,k) = a;
2466 20356 : gel(P,k) = x;
2467 20356 : k++;
2468 20356 : x = gel(P,i); a = gel(A,i);
2469 : }
2470 14000 : l = k+1;
2471 14000 : gel(A,k) = a; setlg(A,l);
2472 14000 : gel(P,k) = x; setlg(P,l); set_avma(av);
2473 : }
2474 :
2475 : static void
2476 18361 : polred_init(nfmaxord_t *S, nffp_t *F, CG_data *d)
2477 : {
2478 18361 : long e, prec, n = degpol(S->T);
2479 : double log2rho;
2480 : GEN ro;
2481 18361 : set_LLL_basis(S, &ro, 0, 0.9999);
2482 : /* || polchar ||_oo < 2^e ~ 2 (n * rho)^n, rho = max modulus of root */
2483 18354 : log2rho = ro ? (double)gexpo(ro): fujiwara_bound(S->T);
2484 18354 : e = n * (long)(log2rho + log2((double)n)) + 1;
2485 18354 : if (e < 0) e = 0; /* can occur if n = 1 */
2486 18354 : prec = chk_gen_prec(n, e);
2487 18354 : nffp_init(F,S,prec);
2488 18354 : F->ro = ro;
2489 18354 : make_M_G(F, 1);
2490 :
2491 18354 : d->v = varn(S->T);
2492 18354 : d->expo_best_disc = -1;
2493 18354 : d->ZKembed = NULL;
2494 18354 : d->M = NULL;
2495 18354 : d->u = NULL;
2496 18354 : d->r1= S->r1;
2497 18354 : }
2498 : static GEN
2499 14273 : findmindisc(GEN y)
2500 : {
2501 14273 : GEN x = gel(y,1), dx = NULL;
2502 14273 : long i, l = lg(y);
2503 35980 : for (i = 2; i < l; i++)
2504 : {
2505 21707 : GEN yi = gel(y,i);
2506 21707 : if (ZX_is_better(yi,x,&dx)) x = yi;
2507 : }
2508 14273 : return x;
2509 : }
2510 : /* filter [y,b] from polred_aux: keep a single polynomial of degree n in y
2511 : * [ the best wrt discriminant ordering ], but keep all imprimitive
2512 : * polynomials */
2513 : static void
2514 4095 : filter(GEN y, GEN b, long n)
2515 : {
2516 : GEN x, a, dx;
2517 4095 : long i, k = 1, l = lg(y);
2518 4095 : a = x = dx = NULL;
2519 34645 : for (i = 1; i < l; i++)
2520 : {
2521 30550 : GEN yi = gel(y,i), ai = gel(b,i);
2522 30550 : if (degpol(yi) == n)
2523 : {
2524 30396 : if (!dx) dx = ZX_disc(yi); else if (!ZX_is_better(yi,x,&dx)) continue;
2525 5661 : x = yi; a = ai; continue;
2526 : }
2527 154 : gel(y,k) = yi;
2528 154 : gel(b,k) = ai; k++;
2529 : }
2530 4095 : if (dx)
2531 : {
2532 3998 : gel(y,k) = x;
2533 3998 : gel(b,k) = a; k++;
2534 : }
2535 4095 : setlg(y, k);
2536 4095 : setlg(b, k);
2537 4095 : }
2538 :
2539 : static GEN
2540 4130 : polred_aux(nfmaxord_t *S, GEN *pro, long flag)
2541 : { /* only keep polynomials of max degree and best discriminant */
2542 4130 : const long best = flag & nf_ABSOLUTE;
2543 4130 : const long orig = flag & nf_ORIG;
2544 4130 : GEN M, b, y, x = S->T;
2545 4130 : long maxi, i, j, k, v = varn(x), n = lg(S->basis)-1;
2546 : nffp_t F;
2547 : CG_data d;
2548 :
2549 4130 : if (n == 1)
2550 : {
2551 28 : if (!best)
2552 : {
2553 14 : GEN X = pol_x(v);
2554 14 : return orig? mkmat2(mkcol(X),mkcol(gen_1)): mkvec(X);
2555 : }
2556 : else
2557 14 : return orig? trivial_fact(): cgetg(1,t_VEC);
2558 : }
2559 :
2560 4102 : polred_init(S, &F, &d);
2561 4095 : if (pro) *pro = F.ro;
2562 4095 : M = F.M;
2563 4095 : if (best)
2564 : {
2565 4046 : if (!S->dT) S->dT = ZX_disc(S->T);
2566 4046 : d.expo_best_disc = expi(S->dT);
2567 : }
2568 :
2569 : /* n + 2 sum_{1 <= i <= n} n-i = n + n(n-1) = n*n */
2570 4095 : y = cgetg(n*n + 1, t_VEC);
2571 4095 : b = cgetg(n*n + 1, t_COL);
2572 4095 : k = 1;
2573 4095 : if (!best) { gel(y,1) = pol_x(v); gel(b,1) = gen_0; k++; }
2574 26985 : for (i = 2; i <= n; i++)
2575 : {
2576 : GEN ch, ai;
2577 22890 : ai = gel(S->basis,i);
2578 22890 : ch = try_polmin(&d, S, gel(M,i), flag, &ai);
2579 22890 : if (ch) { gel(y,k) = ch; gel(b,k) = ai; k++; }
2580 : }
2581 4095 : maxi = minss(n, 3);
2582 15966 : for (i = 1; i <= maxi; i++)
2583 68668 : for (j = i+1; j <= n; j++)
2584 : {
2585 : GEN ch, ai, v;
2586 56797 : ai = gadd(gel(S->basis,i), gel(S->basis,j));
2587 56797 : v = RgV_add(gel(M,i), gel(M,j));
2588 : /* defining polynomial for Q(w_i+w_j) */
2589 56796 : ch = try_polmin(&d, S, v, flag, &ai);
2590 56798 : if (ch) { gel(y,k) = ch; gel(b,k) = ai; k++; }
2591 :
2592 56798 : ai = gsub(gel(S->basis,i), gel(S->basis,j));
2593 56797 : v = RgV_sub(gel(M,i), gel(M,j));
2594 : /* defining polynomial for Q(w_i-w_j) */
2595 56797 : ch = try_polmin(&d, S, v, flag, &ai);
2596 56796 : if (ch) { gel(y,k) = ch; gel(b,k) = ai; k++; }
2597 : }
2598 4094 : setlg(y, k);
2599 4095 : setlg(b, k); filter(y, b, n);
2600 4095 : if (!orig) return gen_sort_uniq(y, (void*)cmpii, &gen_cmp_RgX);
2601 3465 : settyp(y, t_COL);
2602 3465 : (void)sort_factor_pol(mkmat2(y, b), cmpii);
2603 3465 : return mkmat2(b, y);
2604 : }
2605 :
2606 : /* FIXME: obsolete */
2607 : static GEN
2608 70 : Polred(GEN x, long flag, GEN fa)
2609 : {
2610 70 : pari_sp av = avma;
2611 : nfmaxord_t S;
2612 70 : if (fa)
2613 0 : nfinit_basic(&S, mkvec2(x,fa));
2614 : else
2615 70 : nfinit_basic_flag(&S, x, flag);
2616 63 : return gc_GEN(av, polred_aux(&S, NULL, flag));
2617 : }
2618 :
2619 : /* finds "best" polynomial in polred_aux list, defaulting to S->T if none of
2620 : * them is primitive. *px a ZX, characteristic polynomial of Mod(*pb,S->T),
2621 : * *pdx its discriminant if pdx != NULL. Set *pro = polroots(S->T) */
2622 : static void
2623 4067 : polredbest_aux(nfmaxord_t *S, GEN *pro, GEN *px, GEN *pdx, GEN *pb)
2624 : {
2625 4067 : GEN y, dx, x = S->T; /* default value */
2626 : long i, l;
2627 4067 : y = polred_aux(S, pro, pb? nf_ORIG|nf_ABSOLUTE: nf_ABSOLUTE);
2628 4060 : dx = S->dT;
2629 4060 : if (pb)
2630 : {
2631 3451 : GEN a, b = deg1pol_shallow(S->unscale, gen_0, varn(x));
2632 3451 : a = gel(y,1); l = lg(a);
2633 3451 : y = gel(y,2);
2634 6798 : for (i=1; i<l; i++)
2635 : {
2636 3347 : GEN yi = gel(y,i);
2637 3347 : if (ZX_is_better(yi,x,&dx)) { x = yi; b = gel(a,i); }
2638 : }
2639 3451 : *pb = b;
2640 : }
2641 : else
2642 : {
2643 609 : l = lg(y);
2644 1211 : for (i=1; i<l; i++)
2645 : {
2646 602 : GEN yi = gel(y,i);
2647 602 : if (ZX_is_better(yi,x,&dx)) x = yi;
2648 : }
2649 : }
2650 4060 : if (pdx) { if (!dx) dx = ZX_disc(x); *pdx = dx; }
2651 4060 : *px = x;
2652 4060 : }
2653 : static GEN
2654 3885 : polredbest_i(GEN T, long flag)
2655 : {
2656 : nfmaxord_t S;
2657 : GEN a;
2658 3885 : nfinit_basic_partial(&S, T);
2659 3885 : polredbest_aux(&S, NULL, &T, NULL, flag? &a: NULL);
2660 3878 : if (flag == 2)
2661 350 : T = mkvec2(T, a);
2662 3528 : else if (flag == 1)
2663 : {
2664 2919 : GEN b = (S.T0 == T)? pol_x(varn(T)): QXQ_reverse(a, S.T0);
2665 : /* charpoly(Mod(a,T0)) = T; charpoly(Mod(b,T)) = S.x */
2666 2919 : if (degpol(T) == 1) b = grem(b,T);
2667 2919 : T = mkvec2(T, mkpolmod(b,T));
2668 : }
2669 3878 : return T;
2670 : }
2671 : GEN
2672 3528 : polredbest(GEN T, long flag)
2673 : {
2674 3528 : pari_sp av = avma;
2675 3528 : if (flag < 0 || flag > 1) pari_err_FLAG("polredbest");
2676 3528 : return gc_GEN(av, polredbest_i(T, flag));
2677 : }
2678 : GEN
2679 21 : polredord(GEN x)
2680 : {
2681 21 : pari_sp av = avma;
2682 : GEN v, lt;
2683 : long i, n, vx;
2684 :
2685 21 : if (typ(x) != t_POL) pari_err_TYPE("polredord",x);
2686 21 : x = Q_primpart(x); RgX_check_ZX(x,"polredord");
2687 21 : n = degpol(x); if (n <= 0) pari_err_CONSTPOL("polredord");
2688 21 : if (n == 1) return gc_GEN(av, mkvec(x));
2689 14 : lt = leading_coeff(x); vx = varn(x);
2690 14 : if (is_pm1(lt))
2691 : {
2692 7 : if (signe(lt) < 0) x = ZX_neg(x);
2693 7 : v = pol_x_powers(n, vx);
2694 : }
2695 : else
2696 : { GEN L;
2697 : /* basis for Dedekind order */
2698 7 : v = cgetg(n+1, t_VEC);
2699 7 : gel(v,1) = scalarpol_shallow(lt, vx);
2700 14 : for (i = 2; i <= n; i++)
2701 7 : gel(v,i) = RgX_Rg_add(RgX_mulXn(gel(v,i-1), 1), gel(x,n+3-i));
2702 7 : gel(v,1) = pol_1(vx);
2703 7 : x = ZX_Q_normalize(x, &L);
2704 7 : v = gsubst(v, vx, monomial(ginv(L),1,vx));
2705 14 : for (i=2; i <= n; i++)
2706 7 : if (Q_denom(gel(v,i)) == gen_1) gel(v,i) = pol_xn(i-1, vx);
2707 : }
2708 14 : return gc_upto(av, polred(mkvec2(x, v)));
2709 : }
2710 :
2711 : /* DEPRECATED: backward compatibility */
2712 : GEN
2713 56 : polred0(GEN x, long flag)
2714 : {
2715 56 : long fl = 0;
2716 56 : if (flag & 1) fl |= nf_PARTIALFACT;
2717 56 : if (flag & 2) fl |= nf_ORIG;
2718 56 : return Polred(x, fl, NULL);
2719 : }
2720 :
2721 : GEN
2722 14 : polred(GEN x) { return Polred(x, 0, NULL); }
2723 : GEN
2724 0 : smallpolred(GEN x) { return Polred(x, nf_PARTIALFACT, NULL); }
2725 : GEN
2726 0 : factoredpolred(GEN x, GEN fa) { return Polred(x, 0, fa); }
2727 : GEN
2728 0 : polred2(GEN x) { return Polred(x, nf_ORIG, NULL); }
2729 : GEN
2730 0 : smallpolred2(GEN x) { return Polred(x, nf_PARTIALFACT|nf_ORIG, NULL); }
2731 : GEN
2732 0 : factoredpolred2(GEN x, GEN fa) { return Polred(x, nf_PARTIALFACT, fa); }
2733 :
2734 : /********************************************************************/
2735 : /** **/
2736 : /** POLREDABS **/
2737 : /** **/
2738 : /********************************************************************/
2739 : /* set V[k] := matrix of multiplication by nk.zk[k] */
2740 : static GEN
2741 22708 : set_mulid(GEN V, GEN M, GEN Mi, long r1, long r2, long N, long k)
2742 : {
2743 22708 : GEN v, Mk = cgetg(N+1, t_MAT);
2744 : long i, e;
2745 35374 : for (i = 1; i < k; i++) gel(Mk,i) = gmael(V, i, k);
2746 147931 : for ( ; i <=N; i++)
2747 : {
2748 125223 : v = vecmul(gel(M,k), gel(M,i));
2749 125222 : v = RgM_RgC_mul(Mi, split_realimag(v, r1, r2));
2750 125223 : gel(Mk,i) = grndtoi(v, &e);
2751 125223 : if (e > -5) return NULL;
2752 : }
2753 22708 : gel(V,k) = Mk; return Mk;
2754 : }
2755 :
2756 : static GEN
2757 13084 : ZM_image_shallow(GEN M, long *pr)
2758 : {
2759 : long j, k, r;
2760 13084 : GEN y, d = ZM_pivots(M, &k);
2761 13084 : r = lg(M)-1 - k;
2762 13084 : y = cgetg(r+1,t_MAT);
2763 58947 : for (j=k=1; j<=r; k++)
2764 45863 : if (d[k]) gel(y,j++) = gel(M,k);
2765 13084 : *pr = r; return y;
2766 : }
2767 :
2768 : /* U = base change matrix, R = Cholesky form of the quadratic form [matrix
2769 : * Q from algo 2.7.6] */
2770 : static GEN
2771 14266 : chk_gen_init(FP_chk_fun *chk, GEN R, GEN U)
2772 : {
2773 14266 : CG_data *d = (CG_data*)chk->data;
2774 : GEN P, V, D, inv, bound, S, M;
2775 14266 : long N = lg(U)-1, r1 = d->r1, r2 = (N-r1)>>1;
2776 14266 : long i, j, prec, firstprim = 0, skipfirst = 0;
2777 : pari_sp av;
2778 :
2779 14266 : d->u = U;
2780 14266 : d->ZKembed = M = RgM_mul(d->M, U);
2781 :
2782 14266 : av = avma; bound = d->bound;
2783 14266 : D = cgetg(N+1, t_VECSMALL);
2784 95851 : for (i = 1; i <= N; i++)
2785 : {
2786 81592 : pari_sp av2 = avma;
2787 81592 : P = get_pol(d, gel(M,i));
2788 81592 : if (!P) pari_err_PREC("chk_gen_init");
2789 81585 : P = gc_GEN(av2, ZX_radical(P));
2790 81585 : D[i] = degpol(P);
2791 81585 : if (D[i] == N)
2792 : { /* primitive element */
2793 57609 : GEN B = embed_T2(gel(M,i), r1);
2794 57609 : if (!firstprim) firstprim = i; /* index of first primitive element */
2795 57609 : if (DEBUGLEVEL>2) err_printf("chk_gen_init: generator %Ps\n",P);
2796 57609 : if (gcmp(B,bound) < 0) bound = gc_leaf(av2, B);
2797 : }
2798 : else
2799 : {
2800 23976 : if (DEBUGLEVEL>2) err_printf("chk_gen_init: subfield %Ps\n",P);
2801 23976 : if (firstprim)
2802 : { /* cycle basis vectors so that primitive elements come last */
2803 2878 : GEN u = d->u, e = M;
2804 2878 : GEN te = gel(e,i), tu = gel(u,i), tR = gel(R,i);
2805 2878 : long tS = D[i];
2806 8873 : for (j = i; j > firstprim; j--)
2807 : {
2808 5995 : u[j] = u[j-1];
2809 5995 : e[j] = e[j-1];
2810 5995 : R[j] = R[j-1];
2811 5995 : D[j] = D[j-1];
2812 : }
2813 2878 : gel(u,firstprim) = tu;
2814 2878 : gel(e,firstprim) = te;
2815 2878 : gel(R,firstprim) = tR;
2816 2878 : D[firstprim] = tS; firstprim++;
2817 : }
2818 : }
2819 : }
2820 14259 : if (!firstprim)
2821 : { /* try (a little) to find primitive elements to improve bound */
2822 28 : GEN x = cgetg(N+1, t_VECSMALL);
2823 28 : if (DEBUGLEVEL>1)
2824 0 : err_printf("chk_gen_init: difficult field, trying random elements\n");
2825 308 : for (i = 0; i < 10; i++)
2826 : {
2827 : GEN e, B;
2828 3010 : for (j = 1; j <= N; j++) x[j] = (long)random_Fl(7) - 3;
2829 280 : e = RgM_zc_mul(M, x);
2830 280 : B = embed_T2(e, r1);
2831 280 : if (gcmp(B,bound) >= 0) continue;
2832 16 : P = get_pol(d, e); if (!P) pari_err_PREC( "chk_gen_init");
2833 16 : if (!ZX_is_squarefree(P)) continue;
2834 16 : if (DEBUGLEVEL>2) err_printf("chk_gen_init: generator %Ps\n",P);
2835 16 : bound = B ;
2836 : }
2837 : }
2838 :
2839 14259 : if (firstprim != 1)
2840 : {
2841 13984 : inv = ginv( split_realimag(M, r1, r2) ); /*TODO: use QR?*/
2842 13984 : V = gel(inv,1);
2843 54615 : for (i = 2; i <= r1+r2; i++) V = gadd(V, gel(inv,i));
2844 : /* V corresponds to 1_Z */
2845 13984 : V = grndtoi(V, &j);
2846 13984 : if (j > -5) pari_err_BUG("precision too low in chk_gen_init");
2847 13984 : S = mkmat(V); /* 1 */
2848 :
2849 13984 : V = cgetg(N+1, t_VEC);
2850 35864 : for (i = 1; i <= N; i++,skipfirst++)
2851 : { /* S = Q-basis of subfield generated by nf.zk[1..i-1] */
2852 : GEN Mx, M2;
2853 35864 : long j, k, h, rkM, dP = D[i];
2854 :
2855 35864 : if (dP == N) break; /* primitive */
2856 22708 : Mx = set_mulid(V, M, inv, r1, r2, N, i);
2857 22708 : if (!Mx) break; /* prec. problem. Stop */
2858 22708 : if (dP == 1) continue;
2859 9462 : rkM = lg(S)-1;
2860 9462 : M2 = cgetg(N+1, t_MAT); /* we will add to S the elts of M2 */
2861 9462 : gel(M2,1) = col_ei(N, i); /* nf.zk[i] */
2862 9462 : k = 2;
2863 19073 : for (h = 1; h < dP; h++)
2864 : {
2865 : long r; /* add to M2 the elts of S * nf.zk[i] */
2866 39867 : for (j = 1; j <= rkM; j++) gel(M2,k++) = ZM_ZC_mul(Mx, gel(S,j));
2867 13084 : setlg(M2, k); k = 1;
2868 13084 : S = ZM_image_shallow(shallowconcat(S,M2), &r);
2869 13912 : if (r == rkM) break;
2870 10439 : if (r > rkM)
2871 : {
2872 10439 : rkM = r;
2873 10439 : if (rkM == N) break;
2874 : }
2875 : }
2876 9462 : if (rkM == N) break;
2877 : /* Q(w[1],...,w[i-1]) is a strict subfield of nf */
2878 : }
2879 : }
2880 : /* x_1,...,x_skipfirst generate a strict subfield [unless N=skipfirst=1] */
2881 14259 : chk->skipfirst = skipfirst;
2882 14259 : if (DEBUGLEVEL>2) err_printf("chk_gen_init: skipfirst = %ld\n",skipfirst);
2883 :
2884 : /* should be DEF + gexpo( max_k C^n_k (bound/k)^(k/2) ) */
2885 14259 : bound = gc_leaf(av, bound);
2886 14259 : prec = chk_gen_prec(N, (gexpo(bound)*N)/2);
2887 14259 : if (DEBUGLEVEL)
2888 0 : err_printf("chk_gen_init: new prec = %ld (initially %ld)\n", prec, d->prec);
2889 14259 : if (prec > d->prec) pari_err_BUG("polredabs (precision problem)");
2890 14259 : if (prec < d->prec) d->ZKembed = gprec_w(M, prec);
2891 14259 : return bound;
2892 : }
2893 :
2894 : static GEN
2895 14273 : polredabs_i(GEN x, nfmaxord_t *S, GEN *u, long flag)
2896 : {
2897 14273 : FP_chk_fun chk = { &chk_gen, &chk_gen_init, NULL, NULL, 0 };
2898 : nffp_t F;
2899 : CG_data d;
2900 : GEN v, y, a;
2901 : long i, l;
2902 :
2903 14273 : nfinit_basic_flag(S, x, flag);
2904 14273 : x = S->T0;
2905 14273 : if (degpol(x) == 1)
2906 : {
2907 14 : long vx = varn(x);
2908 14 : *u = NULL;
2909 14 : return mkvec2(mkvec( pol_x(vx) ),
2910 14 : mkvec( deg1pol_shallow(gen_1, negi(gel(S->T,2)), vx) ));
2911 : }
2912 14259 : chk.data = (void*)&d;
2913 14259 : polred_init(S, &F, &d);
2914 14259 : d.bound = embed_T2(F.ro, d.r1);
2915 14259 : if (realprec(d.bound) > F.prec) d.bound = rtor(d.bound, F.prec);
2916 : for (;;)
2917 21 : {
2918 14280 : GEN R = R_from_QR(F.G, F.prec);
2919 14280 : if (R)
2920 : {
2921 14266 : d.prec = F.prec;
2922 14266 : d.M = F.M;
2923 14266 : v = fincke_pohst(mkvec(R),NULL,-1, 0, &chk);
2924 14266 : if (v) break;
2925 : }
2926 21 : F.prec = precdbl(F.prec);
2927 21 : F.ro = NULL;
2928 21 : make_M_G(&F, 1);
2929 21 : if (DEBUGLEVEL) pari_warn(warnprec,"polredabs0",F.prec);
2930 : }
2931 14259 : y = gel(v,1);
2932 14259 : a = gel(v,2); l = lg(a);
2933 69972 : for (i = 1; i < l; i++) /* normalize wrt z -> -z */
2934 55713 : if (ZX_canon_neg(gel(y,i)) && (flag & (nf_ORIG|nf_RAW)))
2935 525 : gel(a,i) = ZC_neg(gel(a,i));
2936 14259 : *u = d.u; return v;
2937 : }
2938 :
2939 : GEN
2940 14000 : polredabs0(GEN x, long flag)
2941 : {
2942 14000 : pari_sp av = avma;
2943 : GEN Y, A, u, v;
2944 : nfmaxord_t S;
2945 : long i, l;
2946 :
2947 14000 : v = polredabs_i(x, &S, &u, flag);
2948 14000 : remove_duplicates(v);
2949 14000 : Y = gel(v,1);
2950 14000 : A = gel(v,2);
2951 14000 : l = lg(A); if (l == 1) pari_err_BUG("polredabs (missing vector)");
2952 14000 : if (DEBUGLEVEL) err_printf("Found %ld minimal polynomials.\n",l-1);
2953 14000 : if (!(flag & nf_ALL))
2954 : {
2955 14000 : GEN y = findmindisc(Y);
2956 28259 : for (i = 1; i < l; i++)
2957 28259 : if (ZX_equal(gel(Y,i), y)) break;
2958 14000 : Y = mkvec(gel(Y,i));
2959 14000 : A = mkvec(gel(A,i)); l = 2;
2960 : }
2961 14273 : if (flag & (nf_RAW|nf_ORIG)) for (i = 1; i < l; i++)
2962 : {
2963 273 : GEN y = gel(Y,i), a = gel(A,i);
2964 273 : if (u) a = RgV_RgC_mul(S.basis, ZM_ZC_mul(u, a));
2965 273 : if (flag & nf_ORIG)
2966 : {
2967 266 : a = QXQ_reverse(a, S.T);
2968 266 : if (!isint1(S.unscale)) a = gdiv(a, S.unscale); /* not RgX_Rg_div */
2969 266 : a = mkpolmod(a,y);
2970 : }
2971 273 : gel(Y,i) = mkvec2(y, a);
2972 : }
2973 14000 : return gc_GEN(av, (flag & nf_ALL)? Y: gel(Y,1));
2974 : }
2975 :
2976 : GEN
2977 0 : polredabsall(GEN x, long flun) { return polredabs0(x, flun | nf_ALL); }
2978 : GEN
2979 13426 : polredabs(GEN x) { return polredabs0(x,0); }
2980 : GEN
2981 0 : polredabs2(GEN x) { return polredabs0(x,nf_ORIG); }
2982 :
2983 : /* relative polredabs/best. Returns relative polynomial by default (flag = 0)
2984 : * flag & nf_ORIG: + element (base change)
2985 : * flag & nf_ABSOLUTE: absolute polynomial */
2986 : static GEN
2987 637 : rnfpolred_i(GEN nf, GEN R, long flag, long best)
2988 : {
2989 637 : const char *f = best? "rnfpolredbest": "rnfpolredabs";
2990 637 : const long abs = ((flag & nf_ORIG) && (flag & nf_ABSOLUTE));
2991 637 : GEN listP = NULL, red, pol, A, P, T, rnfeq;
2992 637 : pari_sp av = avma;
2993 637 : long even = 0;
2994 :
2995 637 : if (typ(R) == t_VEC) {
2996 14 : if (lg(R) != 3) pari_err_TYPE(f,R);
2997 14 : listP = gel(R,2);
2998 14 : R = gel(R,1);
2999 : }
3000 637 : if (typ(R) != t_POL) pari_err_TYPE(f,R);
3001 637 : nf = checknf(nf);
3002 637 : T = nf_get_pol(nf);
3003 637 : R = RgX_nffix(f, T, R, 0);
3004 637 : if (best || (flag & nf_PARTIALFACT))
3005 : {
3006 364 : rnfeq = abs? nf_rnfeq(nf, R): nf_rnfeqsimple(nf, R);
3007 364 : pol = gel(rnfeq,1);
3008 364 : if (listP) pol = mkvec2(pol, listP);
3009 357 : red = best? polredbest_i(pol, abs? 1: 2)
3010 364 : : polredabs0(pol, (abs? nf_ORIG: nf_RAW)|nf_PARTIALFACT);
3011 364 : P = gel(red,1);
3012 364 : A = gel(red,2);
3013 : }
3014 : else
3015 : {
3016 : nfmaxord_t S;
3017 : GEN rnf, u, v, y, a;
3018 : long i, j, l;
3019 : pari_timer ti;
3020 273 : if (DEBUGLEVEL>1) timer_start(&ti);
3021 273 : rnf = rnfinit(nf, R);
3022 273 : rnfeq = rnf_get_map(rnf);
3023 273 : pol = rnf_zkabs(rnf);
3024 273 : if (DEBUGLEVEL>1) timer_printf(&ti, "absolute basis");
3025 273 : v = polredabs_i(pol, &S, &u, nf_ORIG);
3026 273 : pol = gel(pol,1);
3027 273 : y = gel(v,1); P = findmindisc(y);
3028 273 : a = gel(v,2);
3029 273 : l = lg(y); A = cgetg(l, t_VEC);
3030 1897 : for (i = j = 1; i < l; i++)
3031 1624 : if (ZX_equal(gel(y,i),P)) gel(A,j++) = gel(a,i);
3032 273 : setlg(A,j); /* mod(A[i], pol) are all roots of P in Q[X]/(pol) */
3033 273 : even = j > 2 && !odd(degpol(P)) && !odd(ZX_deflate_order(P));
3034 1365 : for (i = 1; i < j; i++)
3035 : {
3036 1092 : GEN t = gel(A,i);
3037 1092 : if (u) t = ZM_ZC_mul(u,t);
3038 1092 : gel(A,i) = RgV_RgC_mul(S.basis, t);
3039 : }
3040 : }
3041 637 : if (DEBUGLEVEL>1) err_printf("reduced absolute generator: %Ps\n",P);
3042 637 : if (flag & nf_ABSOLUTE)
3043 : {
3044 14 : if (flag & nf_ORIG)
3045 : {
3046 7 : GEN a = gel(rnfeq,2); /* Mod(a,pol) root of T */
3047 7 : GEN k = gel(rnfeq,3); /* Mod(variable(R),R) + k*a root of pol */
3048 7 : if (typ(A) == t_VEC) A = gel(A,1); /* any root will do */
3049 7 : a = RgX_RgXQ_eval(a, lift_shallow(A), P); /* Mod(a, P) root of T */
3050 7 : P = mkvec3(P, mkpolmod(a,P), gsub(A, gmul(k,a)));
3051 : }
3052 14 : return gc_GEN(av, P);
3053 : }
3054 623 : if (typ(A) != t_VEC)
3055 : {
3056 357 : A = eltabstorel_lift(rnfeq, A);
3057 357 : P = lift_if_rational( RgXQ_charpoly(A, R, varn(R)) );
3058 : }
3059 : else
3060 : { /* canonical factor */
3061 266 : long i, l = lg(A), v = varn(R);
3062 266 : GEN besta = NULL;
3063 1316 : for (i = 1; i < l; i++)
3064 : {
3065 1050 : GEN a = eltabstorel_lift(rnfeq, gel(A,i));
3066 1050 : GEN p = lift_if_rational( RgXQ_charpoly(a, R, v) );
3067 1050 : if (even)
3068 : {
3069 532 : GEN q = RgX_unscale(p, gen_m1);
3070 532 : if (cmp_universal(q, p) < 0) { p = q; a = gneg(a); }
3071 : }
3072 1050 : if (i == 1 || cmp_universal(p, P) < 0) { P = p; besta = a; }
3073 : }
3074 266 : A = besta;
3075 : }
3076 623 : if (flag & nf_ORIG) P = mkvec2(P, mkpolmod(RgXQ_reverse(A,R),P));
3077 623 : return gc_GEN(av, P);
3078 : }
3079 : GEN
3080 280 : rnfpolredabs(GEN nf, GEN R, long flag)
3081 280 : { return rnfpolred_i(nf,R,flag, 0); }
3082 : GEN
3083 357 : rnfpolredbest(GEN nf, GEN R, long flag)
3084 : {
3085 357 : if (flag < 0 || flag > 3) pari_err_FLAG("rnfpolredbest");
3086 357 : return rnfpolred_i(nf,R,flag, 1);
3087 : }
|
