Code coverage tests

This page documents the degree to which the PARI/GP source code is tested by our public test suite, distributed with the source distribution in directory src/test/. This is measured by the gcov utility; we then process gcov output using the lcov frond-end.

We test a few variants depending on Configure flags on the pari.math.u-bordeaux.fr machine (x86_64 architecture), and agregate them in the final report:

The target is to exceed 90% coverage for all mathematical modules (given that branches depending on DEBUGLEVEL or DEBUGMEM are not covered). This script is run to produce the results below.

LCOV - code coverage report
Current view: top level - basemath - base1.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.12.1 lcov report (development 25406-bf255ab81b) Lines: 1615 1688 95.7 %
Date: 2020-06-04 05:59:24 Functions: 122 138 88.4 %
Legend: Lines: hit not hit

          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. It is distributed in the hope that it will be useful, but WITHOUT
       8             : ANY WARRANTY WHATSOEVER.
       9             : 
      10             : Check the License for details. You should have received a copy of it, along
      11             : with the package; see the file 'COPYING'. If not, write to the Free Software
      12             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      13             : 
      14             : /**************************************************************/
      15             : /*                                                            */
      16             : /*                        NUMBER FIELDS                       */
      17             : /*                                                            */
      18             : /**************************************************************/
      19             : #include "pari.h"
      20             : #include "paripriv.h"
      21             : 
      22             : int new_galois_format = 0;
      23             : 
      24             : /* v a t_VEC, lg(v) = 13, sanity check for true rnf */
      25             : static int
      26      271075 : v13checkrnf(GEN v)
      27      271075 : { return typ(gel(v,6)) == t_VEC; }
      28             : static int
      29       10584 : rawcheckbnf(GEN v) { return typ(v)==t_VEC && lg(v)==11; }
      30             : static int
      31       10934 : rawchecknf(GEN v) { return typ(v)==t_VEC && lg(v)==10; }
      32             : /* v a t_VEC, lg(v) = 11, sanity check for true bnf */
      33             : static int
      34        4067 : v11checkbnf(GEN v) { return rawchecknf(bnf_get_nf(v)); }
      35             : /* v a t_VEC, lg(v) = 10, sanity check for true nf */
      36             : static int
      37       38703 : v10checknf(GEN v) { return typ(gel(v,1))==t_POL; }
      38             : /* v a t_VEC, lg(v) = 9, sanity check for true gal */
      39             : static int
      40         637 : v9checkgal(GEN v)
      41         637 : { GEN x = gel(v,2); return typ(x) == t_VEC && lg(x) == 4; }
      42             : 
      43             : int
      44      275831 : checkrnf_i(GEN rnf)
      45      275831 : { return (typ(rnf)==t_VEC && lg(rnf)==13 && v13checkrnf(rnf)); }
      46             : 
      47             : void
      48      270501 : checkrnf(GEN rnf)
      49      270501 : { if (!checkrnf_i(rnf)) pari_err_TYPE("checkrnf",rnf); }
      50             : 
      51             : GEN
      52     1235804 : checkbnf_i(GEN X)
      53             : {
      54     1235804 :   if (typ(X) == t_VEC)
      55     1235286 :     switch (lg(X))
      56             :     {
      57     1232493 :       case 11:
      58     1232493 :         if (typ(gel(X,6)) != t_INT) return NULL; /* pre-2.2.4 format */
      59     1232493 :         if (lg(gel(X,10)) != 4) return NULL; /* pre-2.8.1 format */
      60     1232493 :         return X;
      61        1778 :       case 7: return checkbnf_i(bnr_get_bnf(X));
      62             :     }
      63        1533 :   return NULL;
      64             : }
      65             : 
      66             : GEN
      67    56467553 : checknf_i(GEN X)
      68             : {
      69    56467553 :   if (typ(X)==t_VEC)
      70    56467024 :     switch(lg(X))
      71             :     {
      72    56234111 :       case 10: return X;
      73      228890 :       case 11: return checknf_i(bnf_get_nf(X));
      74         182 :       case 7:  return checknf_i(bnr_get_bnf(X));
      75        1869 :       case 3: if (typ(gel(X,2)) == t_POLMOD) return checknf_i(gel(X,1));
      76             :     }
      77        4363 :   return NULL;
      78             : }
      79             : 
      80             : GEN
      81     1232304 : checkbnf(GEN x)
      82             : {
      83     1232304 :   GEN bnf = checkbnf_i(x);
      84     1232304 :   if (!bnf) pari_err_TYPE("checkbnf [please apply bnfinit()]",x);
      85     1232290 :   return bnf;
      86             : }
      87             : 
      88             : GEN
      89    55531734 : checknf(GEN x)
      90             : {
      91    55531734 :   GEN nf = checknf_i(x);
      92    55531703 :   if (!nf) pari_err_TYPE("checknf [please apply nfinit()]",x);
      93    55531663 :   return nf;
      94             : }
      95             : 
      96             : void
      97      484189 : checkbnr(GEN bnr)
      98             : {
      99      484189 :   if (typ(bnr)!=t_VEC || lg(bnr)!=7)
     100           7 :     pari_err_TYPE("checkbnr [please apply bnrinit()]",bnr);
     101      484182 :   (void)checkbnf(bnr_get_bnf(bnr));
     102      484175 : }
     103             : 
     104             : void
     105           0 : checkbnrgen(GEN bnr)
     106             : {
     107           0 :   checkbnr(bnr);
     108           0 :   if (lg(bnr_get_clgp(bnr))<=3)
     109           0 :     pari_err_TYPE("checkbnrgen [apply bnrinit(,,1), not bnrinit()]",bnr);
     110           0 : }
     111             : 
     112             : void
     113           0 : checksqmat(GEN x, long N)
     114             : {
     115           0 :   if (typ(x)!=t_MAT) pari_err_TYPE("checksqmat",x);
     116           0 :   if (lg(x) == 1 || lgcols(x) != N+1) pari_err_DIM("checksqmat");
     117           0 : }
     118             : 
     119             : GEN
     120      338819 : checkbid_i(GEN bid)
     121             : {
     122             :   GEN f;
     123      338819 :   if (typ(bid)!=t_VEC || lg(bid)!=6 || typ(bid_get_U(bid)) != t_VEC)
     124       42798 :     return NULL;
     125      296021 :   f = bid_get_mod(bid);
     126      296021 :   if (typ(f)!=t_VEC || lg(f)!=3) return NULL;
     127      296021 :   return bid;
     128             : }
     129             : void
     130      294698 : checkbid(GEN bid)
     131             : {
     132      294698 :   if (!checkbid_i(bid)) pari_err_TYPE("checkbid",bid);
     133      294691 : }
     134             : void
     135       17416 : checkabgrp(GEN v)
     136             : {
     137       17416 :   if (typ(v) == t_VEC) switch(lg(v))
     138             :   {
     139       17269 :     case 4: if (typ(gel(v,3)) != t_VEC) break;
     140       17416 :     case 3: if (typ(gel(v,2)) != t_VEC) break;
     141       17388 :             if (typ(gel(v,1)) != t_INT) break;
     142       17388 :             return;/*OK*/
     143           0 :     default: break;
     144             :   }
     145          28 :   pari_err_TYPE("checkabgrp",v);
     146             : }
     147             : 
     148             : GEN
     149      182746 : checknfelt_mod(GEN nf, GEN x, const char *s)
     150             : {
     151      182746 :   GEN T = gel(x,1), a = gel(x,2), Tnf = nf_get_pol(nf);
     152      182744 :   if (!RgX_equal_var(T, Tnf)) pari_err_MODULUS(s, T, Tnf);
     153      182690 :   return a;
     154             : }
     155             : 
     156             : void
     157        8694 : check_ZKmodule(GEN x, const char *s)
     158             : {
     159        8694 :   if (typ(x) != t_VEC || lg(x) < 3) pari_err_TYPE(s,x);
     160        8694 :   if (typ(gel(x,1)) != t_MAT) pari_err_TYPE(s,gel(x,1));
     161        8694 :   if (typ(gel(x,2)) != t_VEC) pari_err_TYPE(s,gel(x,2));
     162        8694 :   if (lg(gel(x,2)) != lgcols(x)) pari_err_DIM(s);
     163        8694 : }
     164             : 
     165             : static long
     166      110649 : typv6(GEN x)
     167             : {
     168      110649 :   if (typ(gel(x,1)) == t_VEC && lg(gel(x,3)) == 3)
     169             :   {
     170       12544 :     GEN t = gel(x,3);
     171       12544 :     if (typ(t) != t_VEC) return typ_NULL;
     172       12544 :     t = gel(x,5);
     173       12544 :     switch(typ(gel(x,5)))
     174             :     {
     175         378 :       case t_VEC: return typ_BID;
     176       12166 :       case t_MAT: return typ_BIDZ;
     177           0 :       default: return typ_NULL;
     178             :     }
     179             :   }
     180       98105 :   if (typ(gel(x,2)) == t_COL && typ(gel(x,3)) == t_INT) return typ_PRID;
     181         196 :   return typ_NULL;
     182             : }
     183             : 
     184             : GEN
     185       19390 : get_bnf(GEN x, long *t)
     186             : {
     187       19390 :   switch(typ(x))
     188             :   {
     189          56 :     case t_POL: *t = typ_POL;  return NULL;
     190          56 :     case t_QUAD: *t = typ_Q  ; return NULL;
     191       18774 :     case t_VEC:
     192       18774 :       switch(lg(x))
     193             :       {
     194        4445 :         case 5: if (typ(gel(x,1)) != t_INT) break;
     195        4389 :                 *t = typ_QUA; return NULL;
     196        6132 :         case 6: *t = typv6(x); return NULL;
     197         196 :         case 7:  *t = typ_BNR;
     198         196 :           x = bnr_get_bnf(x);
     199         196 :           if (!rawcheckbnf(x)) break;
     200         140 :           return x;
     201          77 :         case 9:
     202          77 :           if (!v9checkgal(x)) break;
     203          77 :           *t = typ_GAL; return NULL;
     204         399 :         case 10:
     205         399 :           if (!v10checknf(x)) break;
     206         399 :           *t = typ_NF; return NULL;
     207         343 :         case 11:
     208         343 :           if (!v11checkbnf(x)) break;
     209         343 :           *t = typ_BNF; return x;
     210          56 :         case 13:
     211          56 :           if (!v13checkrnf(x)) break;
     212          56 :           *t = typ_RNF; return NULL;
     213         266 :         case 17: *t = typ_ELL; return NULL;
     214             :       }
     215        6972 :       break;
     216         112 :     case t_COL:
     217         112 :       if (get_prid(x)) { *t = typ_MODPR; return NULL; }
     218          56 :       break;
     219             :   }
     220        7420 :   *t = typ_NULL; return NULL;
     221             : }
     222             : 
     223             : GEN
     224      114842 : get_nf(GEN x, long *t)
     225             : {
     226      114842 :   switch(typ(x))
     227             :   {
     228         133 :     case t_POL : *t = typ_POL; return NULL;
     229         133 :     case t_QUAD: *t = typ_Q  ; return NULL;
     230      111895 :     case t_VEC:
     231      111895 :       switch(lg(x))
     232             :       {
     233         133 :         case 3:
     234         133 :           if (typ(gel(x,2)) != t_POLMOD) break;
     235         133 :           return get_nf(gel(x,1),t);
     236         266 :         case 5:
     237         266 :           if (typ(gel(x,1)) != t_INT) break;
     238         133 :           *t = typ_QUA; return NULL;
     239       98945 :         case 6: *t = typv6(x); return NULL;
     240        6804 :         case 7:
     241        6804 :           x = bnr_get_bnf(x);
     242        6804 :           if (!rawcheckbnf(x) || !rawchecknf(x = bnf_get_nf(x))) break;
     243        6671 :           *t = typ_BNR; return x;
     244         553 :         case 9:
     245         553 :           if (!v9checkgal(x)) break;
     246         553 :           *t = typ_GAL; return NULL;
     247        1050 :         case 10:
     248        1050 :           if (!v10checknf(x)) break;
     249        1050 :           *t = typ_NF; return x;
     250         196 :         case 11:
     251         196 :           if (!rawchecknf(x = bnf_get_nf(x))) break;
     252         196 :           *t = typ_BNF; return x;
     253         350 :         case 13:
     254         350 :           if (!v13checkrnf(x)) break;
     255         350 :           *t = typ_RNF; return NULL;
     256        3465 :         case 17: *t = typ_ELL; return NULL;
     257             :       }
     258         399 :       break;
     259         266 :     case t_COL:
     260         266 :       if (get_prid(x)) { *t = typ_MODPR; return NULL; }
     261         133 :       break;
     262             :   }
     263        2947 :   *t = typ_NULL; return NULL;
     264             : }
     265             : 
     266             : long
     267       46795 : nftyp(GEN x)
     268             : {
     269       46795 :   switch(typ(x))
     270             :   {
     271          21 :     case t_POL : return typ_POL;
     272           7 :     case t_QUAD: return typ_Q;
     273       46760 :     case t_VEC:
     274       46760 :       switch(lg(x))
     275             :       {
     276         161 :         case 13:
     277         161 :           if (!v13checkrnf(x)) break;
     278         161 :           return typ_RNF;
     279       37254 :         case 10:
     280       37254 :           if (!v10checknf(x)) break;
     281       37247 :           return typ_NF;
     282         154 :         case 11:
     283         154 :           if (!v11checkbnf(x)) break;
     284         154 :           return typ_BNF;
     285        3584 :         case 7:
     286        3584 :           x = bnr_get_bnf(x);
     287        3584 :           if (!rawcheckbnf(x) || !v11checkbnf(x)) break;
     288        3570 :           return typ_BNR;
     289        5572 :         case 6:
     290        5572 :           return typv6(x);
     291           7 :         case 9:
     292           7 :           if (!v9checkgal(x)) break;
     293           0 :           return typ_GAL;
     294           7 :         case 17: return typ_ELL;
     295             :       }
     296          14 :   }
     297          56 :   return typ_NULL;
     298             : }
     299             : 
     300             : /*************************************************************************/
     301             : /**                                                                     **/
     302             : /**                           GALOIS GROUP                              **/
     303             : /**                                                                     **/
     304             : /*************************************************************************/
     305             : 
     306             : GEN
     307        3178 : tschirnhaus(GEN x)
     308             : {
     309        3178 :   pari_sp av = avma, av2;
     310        3178 :   long a, v = varn(x);
     311        3178 :   GEN u, y = cgetg(5,t_POL);
     312             : 
     313        3178 :   if (typ(x)!=t_POL) pari_err_TYPE("tschirnhaus",x);
     314        3178 :   if (lg(x) < 4) pari_err_CONSTPOL("tschirnhaus");
     315        3178 :   if (v) { u = leafcopy(x); setvarn(u,0); x=u; }
     316        3178 :   y[1] = evalsigne(1)|evalvarn(0);
     317             :   do
     318             :   {
     319        3283 :     a = random_bits(2); if (a==0) a  = 1; gel(y,4) = stoi(a);
     320        3283 :     a = random_bits(3); if (a>=4) a -= 8; gel(y,3) = stoi(a);
     321        3283 :     a = random_bits(3); if (a>=4) a -= 8; gel(y,2) = stoi(a);
     322        3283 :     u = RgXQ_charpoly(y,x,v); av2 = avma;
     323             :   }
     324        3283 :   while (degpol(RgX_gcd(u,RgX_deriv(u)))); /* while u not separable */
     325        3178 :   if (DEBUGLEVEL>1)
     326           0 :     err_printf("Tschirnhaus transform. New pol: %Ps",u);
     327        3178 :   set_avma(av2); return gerepileupto(av,u);
     328             : }
     329             : 
     330             : /* Assume pol in Z[X], monic of degree n. Find L in Z such that
     331             :  * POL = L^(-n) pol(L x) is monic in Z[X]. Return POL and set *ptk = L.
     332             :  * No GC. */
     333             : GEN
     334       29326 : ZX_Z_normalize(GEN pol, GEN *ptk)
     335             : {
     336       29326 :   long i,j, sk, n = degpol(pol); /* > 0 */
     337             :   GEN k, fa, P, E, a, POL;
     338             : 
     339       29326 :   if (ptk) *ptk = gen_1;
     340       29326 :   if (!n) return pol;
     341       29319 :   a = pol + 2; k = gel(a,n-1); /* a[i] = coeff of degree i */
     342       77624 :   for (i = n-2; i >= 0; i--)
     343             :   {
     344       67011 :     k = gcdii(k, gel(a,i));
     345       67011 :     if (is_pm1(k)) return pol;
     346             :   }
     347       10613 :   sk = signe(k);
     348       10613 :   if (!sk) return pol; /* monomial! */
     349        9171 :   fa = absZ_factor_limit(k, 0); k = gen_1;
     350        9171 :   P = gel(fa,1);
     351        9171 :   E = gel(fa,2);
     352        9171 :   POL = leafcopy(pol); a = POL+2;
     353       21902 :   for (i = lg(P)-1; i > 0; i--)
     354             :   {
     355       12731 :     GEN p = gel(P,i), pv, pvj;
     356       12731 :     long vmin = itos(gel(E,i));
     357             :     /* find v_p(k) = min floor( v_p(a[i]) / (n-i)) */
     358       65942 :     for (j=n-1; j>=0; j--)
     359             :     {
     360             :       long v;
     361       53211 :       if (!signe(gel(a,j))) continue;
     362       30935 :       v = Z_pval(gel(a,j), p) / (n - j);
     363       30935 :       if (v < vmin) vmin = v;
     364             :     }
     365       12731 :     if (!vmin) continue;
     366        1587 :     pvj = pv = powiu(p,vmin); k = mulii(k, pv);
     367             :     /* a[j] /= p^(v*(n-j)) */
     368       10166 :     for (j=n-1; j>=0; j--)
     369             :     {
     370        8579 :       if (j < n-1) pvj = mulii(pvj, pv);
     371        8579 :       gel(a,j) = diviiexact(gel(a,j), pvj);
     372             :     }
     373             :   }
     374        9171 :   if (ptk) *ptk = k;
     375        9171 :   return POL;
     376             : }
     377             : 
     378             : /* Assume pol != 0 in Z[X]. Find C in Q, L in Z such that POL = C pol(x/L) monic
     379             :  * in Z[X]. Return POL and set *pL = L. Wasteful (but correct) if pol is not
     380             :  * primitive: better if caller used Q_primpart already. No GC. */
     381             : GEN
     382       28948 : ZX_primitive_to_monic(GEN pol, GEN *pL)
     383             : {
     384       28948 :   long i,j, n = degpol(pol);
     385       28948 :   GEN lc = leading_coeff(pol), L, fa, P, E, a, POL;
     386             : 
     387       28948 :   if (is_pm1(lc))
     388             :   {
     389       28647 :     if (pL) *pL = gen_1;
     390       28647 :     return signe(lc) < 0? ZX_neg(pol): pol;
     391             :   }
     392         301 :   if (signe(lc) < 0)
     393          35 :     POL = ZX_neg(pol);
     394             :   else
     395         266 :     POL = leafcopy(pol);
     396         301 :   a = POL+2; lc = gel(a,n);
     397         301 :   fa = Z_factor_limit(lc,0); L = gen_1;
     398         301 :   P = gel(fa,1);
     399         301 :   E = gel(fa,2);
     400         735 :   for (i = lg(P)-1; i > 0; i--)
     401             :   {
     402         434 :     GEN p = gel(P,i), pk, pku;
     403         434 :     long v, j0, e = itos(gel(E,i)), k = e/n, d = k*n - e;
     404             : 
     405         434 :     if (d < 0) { k++; d += n; }
     406             :     /* k = ceil(e[i] / n); find d, k such that  p^d pol(x / p^k) monic */
     407        1757 :     for (j=n-1; j>0; j--)
     408             :     {
     409        1323 :       if (!signe(gel(a,j))) continue;
     410        1071 :       v = Z_pval(gel(a,j), p);
     411        1141 :       while (v + d < k * j) { k++; d += n; }
     412             :     }
     413         434 :     pk = powiu(p,k); j0 = d/k;
     414         434 :     L = mulii(L, pk);
     415             : 
     416         434 :     pku = powiu(p,d - k*j0);
     417             :     /* a[j] *= p^(d - kj) */
     418        1897 :     for (j=j0; j>=0; j--)
     419             :     {
     420        1463 :       if (j < j0) pku = mulii(pku, pk);
     421        1463 :       gel(a,j) = mulii(gel(a,j), pku);
     422             :     }
     423         434 :     j0++;
     424         434 :     pku = powiu(p,k*j0 - d);
     425             :     /* a[j] /= p^(kj - d) */
     426        1162 :     for (j=j0; j<=n; j++)
     427             :     {
     428         728 :       if (j > j0) pku = mulii(pku, pk);
     429         728 :       gel(a,j) = diviiexact(gel(a,j), pku);
     430             :     }
     431             :   }
     432         301 :   if (pL) *pL = L;
     433         301 :   return POL;
     434             : }
     435             : /* Assume pol != 0 in Z[X]. Find C,L in Q such that POL = C pol(x/L)
     436             :  * monic in Z[X]. Return POL and set *pL = L.
     437             :  * Wasteful (but correct) if pol is not primitive: better if caller used
     438             :  * Q_primpart already. No GC. */
     439             : GEN
     440       28661 : ZX_Q_normalize(GEN pol, GEN *pL)
     441             : {
     442       28661 :   GEN lc, POL = ZX_primitive_to_monic(pol, &lc);
     443       28661 :   POL = ZX_Z_normalize(POL, pL);
     444       28661 :   if (pL) *pL = gdiv(lc, *pL);
     445       28661 :   return POL;
     446             : }
     447             : 
     448             : GEN
     449     4400806 : ZX_Q_mul(GEN A, GEN z)
     450             : {
     451     4400806 :   pari_sp av = avma;
     452     4400806 :   long i, l = lg(A);
     453             :   GEN d, n, Ad, B, u;
     454     4400806 :   if (typ(z)==t_INT) return ZX_Z_mul(A,z);
     455     3852121 :   n = gel(z, 1); d = gel(z, 2);
     456     3852121 :   Ad = RgX_to_RgC(FpX_red(A, d), l-2);
     457     3852121 :   u = gcdii(d, FpV_factorback(Ad, NULL, d));
     458     3852121 :   B = cgetg(l, t_POL);
     459     3852121 :   B[1] = A[1];
     460     3852121 :   if (equali1(u))
     461             :   {
     462     3681177 :     for(i=2; i<l; i++)
     463     2383644 :       gel(B, i) = mkfrac(mulii(n, gel(A,i)), d);
     464             :   } else
     465             :   {
     466    18254313 :     for(i=2; i<l; i++)
     467             :     {
     468    15699725 :       GEN di = gcdii(gel(Ad, i-1), u);
     469    15699725 :       GEN ni = mulii(n, diviiexact(gel(A,i), di));
     470    15699725 :       if (equalii(d, di))
     471     3793179 :         gel(B, i) = ni;
     472             :       else
     473    11906546 :         gel(B, i) = mkfrac(ni, diviiexact(d, di));
     474             :     }
     475             :   }
     476     3852121 :   return gerepilecopy(av, B);
     477             : }
     478             : 
     479             : /* pol != 0 in Z[x], returns a monic polynomial POL in Z[x] generating the
     480             :  * same field: there exist C in Q, L in Z such that POL(x) = C pol(x/L).
     481             :  * Set *L = NULL if L = 1, and to L otherwise. No garbage collecting. */
     482             : GEN
     483           0 : ZX_to_monic(GEN pol, GEN *L)
     484             : {
     485           0 :   long n = lg(pol)-1;
     486           0 :   GEN lc = gel(pol,n);
     487           0 :   if (is_pm1(lc)) { *L = gen_1; return signe(lc) > 0? pol: ZX_neg(pol); }
     488           0 :   return ZX_primitive_to_monic(Q_primpart(pol), L);
     489             : }
     490             : 
     491             : /* Evaluate pol in s using nfelt arithmetic and Horner rule */
     492             : GEN
     493       11151 : nfpoleval(GEN nf, GEN pol, GEN s)
     494             : {
     495       11151 :   pari_sp av=avma;
     496       11151 :   long i=lg(pol)-1;
     497             :   GEN res;
     498       11151 :   if (i==1) return gen_0;
     499       11151 :   res = nf_to_scalar_or_basis(nf, gel(pol,i));
     500       27944 :   for (i-- ; i>=2; i--)
     501       16793 :     res = nfadd(nf, nfmul(nf, s, res), gel(pol,i));
     502       11151 :   return gerepileupto(av, res);
     503             : }
     504             : 
     505             : static GEN
     506       37919 : QX_table_nfpoleval(GEN nf, GEN pol, GEN m)
     507             : {
     508       37919 :   pari_sp av = avma;
     509       37919 :   long i = lg(pol)-1;
     510             :   GEN res, den;
     511       37919 :   if (i==1) return gen_0;
     512       37919 :   pol = Q_remove_denom(pol, &den);
     513       37919 :   res = scalarcol_shallow(gel(pol,i), nf_get_degree(nf));
     514      138502 :   for (i-- ; i>=2; i--)
     515      100583 :     res = ZC_Z_add(ZM_ZC_mul(m, res), gel(pol,i));
     516       37919 :   if (den) res = RgC_Rg_div(res, den);
     517       37919 :   return gerepileupto(av, res);
     518             : }
     519             : 
     520             : GEN
     521        8134 : FpX_FpC_nfpoleval(GEN nf, GEN pol, GEN a, GEN p)
     522             : {
     523        8134 :   pari_sp av=avma;
     524        8134 :   long i=lg(pol)-1, n=nf_get_degree(nf);
     525             :   GEN res, Ma;
     526        8134 :   if (i==1) return zerocol(n);
     527        8134 :   Ma = FpM_red(zk_multable(nf, a), p);
     528        8134 :   res = scalarcol(gel(pol,i),n);
     529       64162 :   for (i-- ; i>=2; i--)
     530             :   {
     531       56028 :     res = FpM_FpC_mul(Ma, res, p);
     532       56028 :     gel(res,1) = Fp_add(gel(res,1), gel(pol,i), p);
     533             :   }
     534        8134 :   return gerepileupto(av, res);
     535             : }
     536             : 
     537             : /* compute s(x), not stack clean */
     538             : static GEN
     539       38108 : ZC_galoisapply(GEN nf, GEN s, GEN x)
     540             : {
     541       38108 :   x = nf_to_scalar_or_alg(nf, x);
     542       38108 :   if (typ(x) != t_POL) return scalarcol(x, nf_get_degree(nf));
     543       37919 :   return QX_table_nfpoleval(nf, x, zk_multable(nf, s));
     544             : }
     545             : 
     546             : /* true nf; S = automorphism in basis form, return an FpC = S(z) mod p */
     547             : GEN
     548        5565 : zk_galoisapplymod(GEN nf, GEN z, GEN S, GEN p)
     549             : {
     550             :   GEN den, pe, pe1, denpe, R;
     551             : 
     552        5565 :   z = nf_to_scalar_or_alg(nf, z);
     553        5565 :   if (typ(z) != t_POL) return z;
     554        5565 :   if (gequalX(z)) return FpC_red(S, p); /* common, e.g. modpr_genFq */
     555        5187 :   z = Q_remove_denom(z,&den);
     556        5187 :   denpe = pe = NULL;
     557        5187 :   pe1 = p;
     558        5187 :   if (den)
     559             :   {
     560        4802 :     ulong e = Z_pvalrem(den, p, &den);
     561        4802 :     if (e) { pe = powiu(p, e); pe1 = mulii(pe, p); }
     562        4802 :     denpe = Fp_inv(den, pe1);
     563             :   }
     564        5187 :   R = FpX_FpC_nfpoleval(nf, FpX_red(z, pe1), FpC_red(S, pe1), pe1);
     565        5187 :   if (denpe) R = FpC_Fp_mul(R, denpe, pe1);
     566        5187 :   if (pe) R = gdivexact(R, pe);
     567        5187 :   return R;
     568             : }
     569             : 
     570             : /* true nf */
     571             : static GEN
     572           7 : pr_galoisapply(GEN nf, GEN pr, GEN aut)
     573             : {
     574             :   GEN p, t, u;
     575           7 :   if (typ(pr_get_tau(pr)) == t_INT) return pr; /* inert */
     576           7 :   p = pr_get_p(pr);
     577           7 :   u = zk_galoisapplymod(nf, pr_get_gen(pr), aut, p);
     578           7 :   t = FpM_deplin(zk_multable(nf, u), p);
     579           7 :   t = zk_scalar_or_multable(nf, t);
     580           7 :   return mkvec5(p, u, gel(pr,3), gel(pr,4), t);
     581             : }
     582             : 
     583             : static GEN
     584           7 : vecgaloisapply(GEN nf, GEN aut, GEN v)
     585             : {
     586             :   long i, l;
     587           7 :   GEN V = cgetg_copy(v, &l);
     588          21 :   for (i = 1; i < l; i++) gel(V,i) = galoisapply(nf, aut, gel(v,i));
     589           7 :   return V;
     590             : }
     591             : 
     592             : /* x: famat or standard algebraic number, aut automorphism in ZC form
     593             :  * simplified from general galoisapply */
     594             : static GEN
     595          49 : elt_galoisapply(GEN nf, GEN aut, GEN x)
     596             : {
     597          49 :   pari_sp av = avma;
     598          49 :   switch(typ(x))
     599             :   {
     600           7 :     case t_INT:  return icopy(x);
     601           7 :     case t_FRAC: return gcopy(x);
     602           7 :     case t_POLMOD: x = gel(x,2); /* fall through */
     603          14 :     case t_POL: {
     604          14 :       GEN y = basistoalg(nf, ZC_galoisapply(nf, aut, x));
     605          14 :       return gerepileupto(av,y);
     606             :     }
     607           7 :     case t_COL:
     608           7 :       return gerepileupto(av, ZC_galoisapply(nf, aut, x));
     609          14 :     case t_MAT:
     610          14 :       switch(lg(x)) {
     611           7 :         case 1: return cgetg(1, t_MAT);
     612           7 :         case 3: retmkmat2(vecgaloisapply(nf,aut,gel(x,1)), ZC_copy(gel(x,2)));
     613             :       }
     614             :   }
     615           0 :   pari_err_TYPE("galoisapply",x);
     616             :   return NULL; /* LCOV_EXCL_LINE */
     617             : }
     618             : 
     619             : GEN
     620       70350 : galoisapply(GEN nf, GEN aut, GEN x)
     621             : {
     622       70350 :   pari_sp av = avma;
     623             :   long lx;
     624             :   GEN y;
     625             : 
     626       70350 :   nf = checknf(nf);
     627       70350 :   switch(typ(x))
     628             :   {
     629         364 :     case t_INT:  return icopy(x);
     630           7 :     case t_FRAC: return gcopy(x);
     631             : 
     632          35 :     case t_POLMOD: x = gel(x,2); /* fall through */
     633        1288 :     case t_POL:
     634        1288 :       aut = algtobasis(nf, aut);
     635        1288 :       y = basistoalg(nf, ZC_galoisapply(nf, aut, x));
     636        1288 :       return gerepileupto(av,y);
     637             : 
     638          56 :     case t_VEC:
     639          56 :       aut = algtobasis(nf, aut);
     640          56 :       switch(lg(x))
     641             :       {
     642           7 :         case 6: return gerepilecopy(av, pr_galoisapply(nf, x, aut));
     643          49 :         case 3: y = cgetg(3,t_VEC);
     644          49 :           gel(y,1) = galoisapply(nf, aut, gel(x,1));
     645          49 :           gel(y,2) = elt_galoisapply(nf, aut, gel(x,2));
     646          49 :           return gerepileupto(av, y);
     647             :       }
     648           0 :       break;
     649             : 
     650       31682 :     case t_COL:
     651       31682 :       aut = algtobasis(nf, aut);
     652       31682 :       return gerepileupto(av, ZC_galoisapply(nf, aut, x));
     653             : 
     654       36953 :     case t_MAT: /* ideal */
     655       36953 :       lx = lg(x); if (lx==1) return cgetg(1,t_MAT);
     656       36953 :       if (nbrows(x) != nf_get_degree(nf)) break;
     657       36953 :       y = RgM_mul(nfgaloismatrix(nf,aut), x);
     658       36953 :       return gerepileupto(av, idealhnf_shallow(nf,y));
     659             :   }
     660           0 :   pari_err_TYPE("galoisapply",x);
     661             :   return NULL; /* LCOV_EXCL_LINE */
     662             : }
     663             : 
     664             : /* compute action of automorphism s on nf.zk */
     665             : GEN
     666       50855 : nfgaloismatrix(GEN nf, GEN s)
     667             : {
     668       50855 :   pari_sp av2, av = avma;
     669             :   GEN zk, D, M, H, m;
     670             :   long k, n;
     671             : 
     672       50855 :   nf = checknf(nf);
     673       50855 :   zk = nf_get_zkprimpart(nf); n = lg(zk)-1;
     674       50855 :   M = cgetg(n+1, t_MAT);
     675       50855 :   gel(M,1) = col_ei(n, 1); /* s(1) = 1 */
     676       50855 :   if (n == 1) return M;
     677       50855 :   av2 = avma;
     678       50855 :   if (typ(s) != t_COL) s = algtobasis(nf, s);
     679       50855 :   D = nf_get_zkden(nf);
     680       50855 :   H = RgV_to_RgM(zk, n);
     681       50855 :   if (n == 2)
     682             :   {
     683       46354 :     GEN t = gel(H,2); /* D * s(w_2) */
     684       46354 :     t = ZC_Z_add(ZC_Z_mul(s, gel(t,2)), gel(t,1));
     685       46354 :     gel(M,2) = gerepileupto(av2, gdiv(t, D));
     686       46354 :     return M;
     687             :   }
     688        4501 :   m = zk_multable(nf, s);
     689        4501 :   gel(M,2) = s; /* M[,k] = s(x^(k-1)) */
     690       22428 :   for (k = 3; k <= n; k++) gel(M,k) = ZM_ZC_mul(m, gel(M,k-1));
     691        4501 :   M = ZM_mul(M, H);
     692        4501 :   if (!equali1(D)) M = ZM_Z_divexact(M, D);
     693        4501 :   return gerepileupto(av, M);
     694             : }
     695             : 
     696             : static GEN
     697        8022 : get_aut(GEN nf, GEN gal, GEN aut, GEN g)
     698             : {
     699        8022 :   return aut ? gel(aut, g[1]): poltobasis(nf, galoispermtopol(gal, g));
     700             : }
     701             : 
     702             : static GEN
     703        1435 : idealquasifrob(GEN nf, GEN gal, GEN grp, GEN pr, GEN subg, GEN *S, GEN aut)
     704             : {
     705        1435 :   pari_sp av = avma;
     706        1435 :   long i, n = nf_get_degree(nf), f = pr_get_f(pr);
     707        1435 :   GEN pi = pr_get_gen(pr);
     708        5439 :   for (i=1; i<=n; i++)
     709             :   {
     710        5439 :     GEN g = gel(grp,i);
     711        5439 :     if ((!subg && perm_order(g)==f)
     712        5082 :       || (subg && perm_relorder(g, subg)==f))
     713             :     {
     714        1827 :       *S = get_aut(nf, gal, aut, g);
     715        1827 :       if (ZC_prdvd(ZC_galoisapply(nf, *S, pi), pr)) return g;
     716         392 :       set_avma(av);
     717             :     }
     718             :   }
     719           0 :   pari_err_BUG("idealquasifrob [Frobenius not found]");
     720             :   return NULL;/*LCOV_EXCL_LINE*/
     721             : }
     722             : 
     723             : GEN
     724        1379 : nfgaloispermtobasis(GEN nf, GEN gal)
     725             : {
     726        1379 :   GEN grp = gal_get_group(gal);
     727        1379 :   long i, n = lg(grp)-1;
     728        1379 :   GEN aut = cgetg(n+1, t_VEC);
     729       15323 :   for(i=1; i<=n; i++)
     730             :   {
     731       13944 :     pari_sp av = avma;
     732       13944 :     GEN g = gel(grp, i);
     733       13944 :     GEN vec = poltobasis(nf, galoispermtopol(gal, g));
     734       13944 :     gel(aut, g[1]) = gerepileupto(av, vec);
     735             :   }
     736        1379 :   return aut;
     737             : }
     738             : 
     739             : static void
     740        2457 : gal_check_pol(const char *f, GEN x, GEN y)
     741        2457 : { if (!RgX_equal_var(x,y)) pari_err_MODULUS(f,x,y); }
     742             : 
     743             : /* true nf */
     744             : GEN
     745          56 : idealfrobenius_aut(GEN nf, GEN gal, GEN pr, GEN aut)
     746             : {
     747          56 :   pari_sp av = avma;
     748          56 :   GEN S=NULL, g=NULL; /*-Wall*/
     749             :   GEN T, p, a, b, modpr;
     750             :   long f, n, s;
     751          56 :   f = pr_get_f(pr); n = nf_get_degree(nf);
     752          56 :   if (f==1) { set_avma(av); return identity_perm(n); }
     753          56 :   g = idealquasifrob(nf, gal, gal_get_group(gal), pr, NULL, &S, aut);
     754          56 :   if (f==2) return gerepileuptoleaf(av, g);
     755          21 :   modpr = zk_to_Fq_init(nf,&pr,&T,&p);
     756          21 :   a = pol_x(nf_get_varn(nf));
     757          21 :   b = nf_to_Fq(nf, zk_galoisapplymod(nf, modpr_genFq(modpr), S, p), modpr);
     758          42 :   for (s = 1; s < f-1; s++)
     759             :   {
     760          21 :     a = Fq_pow(a, p, T, p);
     761          21 :     if (ZX_equal(a, b)) break;
     762             :   }
     763          21 :   g = perm_pow(g, Fl_inv(s, f));
     764          21 :   return gerepileupto(av, g);
     765             : }
     766             : 
     767             : GEN
     768          63 : idealfrobenius(GEN nf, GEN gal, GEN pr)
     769             : {
     770          63 :   nf = checknf(nf);
     771          63 :   checkgal(gal);
     772          63 :   checkprid(pr);
     773          63 :   gal_check_pol("idealfrobenius",nf_get_pol(nf),gal_get_pol(gal));
     774          63 :   if (pr_get_e(pr)>1) pari_err_DOMAIN("idealfrobenius","pr.e", ">", gen_1,pr);
     775          56 :   return idealfrobenius_aut(nf, gal, pr, NULL);
     776             : }
     777             : 
     778             : /* true nf */
     779             : GEN
     780         616 : idealramfrobenius_aut(GEN nf, GEN gal, GEN pr, GEN ram, GEN aut)
     781             : {
     782         616 :   pari_sp av = avma;
     783         616 :   GEN S=NULL, g=NULL; /*-Wall*/
     784             :   GEN T, p, a, b, modpr;
     785             :   GEN isog, deco;
     786             :   long f, n, s;
     787         616 :   f = pr_get_f(pr); n = nf_get_degree(nf);
     788         616 :   if (f==1) { set_avma(av); return identity_perm(n); }
     789         399 :   modpr = zk_to_Fq_init(nf,&pr,&T,&p);
     790         399 :   deco = group_elts(gel(ram,1), nf_get_degree(nf));
     791         399 :   isog = group_set(gel(ram,2),  nf_get_degree(nf));
     792         399 :   g = idealquasifrob(nf, gal, deco, pr, isog, &S, aut);
     793         399 :   a = pol_x(nf_get_varn(nf));
     794         399 :   b = nf_to_Fq(nf, zk_galoisapplymod(nf, modpr_genFq(modpr), S, p), modpr);
     795         854 :   for (s=0; !ZX_equal(a, b); s++)
     796         455 :     a = Fq_pow(a, p, T, p);
     797         399 :   g = perm_pow(g, Fl_inv(s, f));
     798         399 :   return gerepileupto(av, g);
     799             : }
     800             : 
     801             : GEN
     802           0 : idealramfrobenius(GEN nf, GEN gal, GEN pr, GEN ram)
     803             : {
     804           0 :   return idealramfrobenius_aut(nf, gal, pr, ram, NULL);
     805             : }
     806             : 
     807             : static GEN
     808        1834 : idealinertiagroup(GEN nf, GEN gal, GEN aut, GEN pr)
     809             : {
     810        1834 :   long i, n = nf_get_degree(nf);
     811        1834 :   GEN p, T, modpr = zk_to_Fq_init(nf,&pr,&T,&p);
     812        1834 :   GEN b = modpr_genFq(modpr);
     813        1834 :   long e = pr_get_e(pr), coprime = ugcd(e, pr_get_f(pr)) == 1;
     814        1834 :   GEN grp = gal_get_group(gal), pi = pr_get_gen(pr);
     815        1834 :   pari_sp ltop = avma;
     816        7854 :   for (i=1; i<=n; i++)
     817             :   {
     818        7854 :     GEN iso = gel(grp,i);
     819        7854 :     if (perm_order(iso) == e)
     820             :     {
     821        3290 :       GEN S = get_aut(nf, gal, aut, iso);
     822        3290 :       if (ZC_prdvd(ZC_galoisapply(nf, S, pi), pr)
     823        2352 :           && (coprime || gequalX(nf_to_Fq(nf, galoisapply(nf,S,b), modpr))))
     824        1834 :           return iso;
     825        1456 :       set_avma(ltop);
     826             :     }
     827             :   }
     828           0 :   pari_err_BUG("idealinertiagroup [no isotropic element]");
     829             :   return NULL;/*LCOV_EXCL_LINE*/
     830             : }
     831             : 
     832             : static GEN
     833        1897 : idealramgroupstame(GEN nf, GEN gal, GEN aut, GEN pr)
     834             : {
     835        1897 :   pari_sp av = avma;
     836             :   GEN iso, frob, giso, isog, S, res;
     837        1897 :   long e = pr_get_e(pr), f = pr_get_f(pr);
     838        1897 :   GEN grp = gal_get_group(gal);
     839        1897 :   if (e == 1)
     840             :   {
     841          63 :     if (f==1)
     842           0 :       return cgetg(1,t_VEC);
     843          63 :     frob = idealquasifrob(nf, gal, grp, pr, NULL, &S, aut);
     844          63 :     set_avma(av);
     845          63 :     res = cgetg(2, t_VEC);
     846          63 :     gel(res, 1) = cyclicgroup(frob, f);
     847          63 :     return res;
     848             :   }
     849        1834 :   res = cgetg(3, t_VEC);
     850        1834 :   av = avma;
     851        1834 :   iso = idealinertiagroup(nf, gal, aut, pr);
     852        1834 :   set_avma(av);
     853        1834 :   giso = cyclicgroup(iso, e);
     854        1834 :   gel(res, 2) = giso;
     855        1834 :   if (f==1)
     856             :   {
     857         917 :     gel(res, 1) = giso;
     858         917 :     return res;
     859             :   }
     860         917 :   av = avma;
     861         917 :   isog = group_set(giso, nf_get_degree(nf));
     862         917 :   frob = idealquasifrob(nf, gal, grp, pr, isog, &S, aut);
     863         917 :   set_avma(av);
     864         917 :   gel(res, 1) = dicyclicgroup(iso,frob,e,f);
     865         917 :   return res;
     866             : }
     867             : 
     868             : /* true nf, p | e */
     869             : static GEN
     870         497 : idealramgroupswild(GEN nf, GEN gal, GEN aut, GEN pr)
     871             : {
     872         497 :   pari_sp av2, av = avma;
     873         497 :   GEN p, T, idx, g, gbas, pi, pibas, Dpi, modpr = zk_to_Fq_init(nf,&pr,&T,&p);
     874         497 :   long bound, i, vDpi, vDg, n = nf_get_degree(nf);
     875         497 :   long e = pr_get_e(pr);
     876         497 :   long f = pr_get_f(pr);
     877             :   ulong nt,rorder;
     878         497 :   GEN pg, ppi, grp = gal_get_group(gal);
     879             : 
     880             :   /* G_i = {s: v(s(pi) - pi) > i} trivial for i > bound;
     881             :    * v_pr(Diff) = sum_{i = 0}^{bound} (#G_i - 1) >= e-1 + bound*(p-1)*/
     882         497 :   bound = (idealval(nf, nf_get_diff(nf), pr) - (e-1)) / (itou(p)-1);
     883         497 :   (void) u_pvalrem(n,p,&nt);
     884         497 :   rorder = e*f*(n/nt);
     885         497 :   idx = const_vecsmall(n,-1);
     886         497 :   pg = NULL;
     887         497 :   vDg = 0;
     888         497 :   if (f == 1)
     889         154 :     g = gbas = NULL;
     890             :   else
     891             :   {
     892             :     GEN Dg;
     893         343 :     g = nf_to_scalar_or_alg(nf, modpr_genFq(modpr));
     894         343 :     if (!gcmpX(g)) /* p | nf.index */
     895             :     {
     896           7 :       g = Q_remove_denom(g, &Dg);
     897           7 :       vDg = Z_pval(Dg,p);
     898           7 :       pg = powiu(p, vDg + 1);
     899           7 :       g = FpX_red(g, pg);
     900             :     }
     901         343 :     gbas = nf_to_scalar_or_basis(nf, g);
     902             :   }
     903         497 :   pi = nf_to_scalar_or_alg(nf, pr_get_gen(pr));
     904         497 :   pi = Q_remove_denom(pi, &Dpi);
     905         497 :   vDpi = Dpi ? Z_pval(Dpi, p): 0;
     906         497 :   ppi = powiu(p, vDpi + (bound + e)/e);
     907         497 :   pi = FpX_red(pi, ppi);
     908         497 :   pibas = nf_to_scalar_or_basis(nf, pi);
     909         497 :   av2 = avma;
     910        4704 :   for (i = 2; i <= n; i++)
     911             :   {
     912        4207 :     GEN S, Spi, piso, iso = gel(grp, i);
     913        4207 :     long j, o, ix = iso[1];
     914        4207 :     if (idx[ix] >= 0 || rorder % (o = perm_order(iso))) continue;
     915             : 
     916        2905 :     piso = iso;
     917        2905 :     S = get_aut(nf, gal, aut, iso);
     918        2905 :     Spi = FpX_FpC_nfpoleval(nf, pi, FpC_red(S, ppi), ppi);
     919             :     /* Computation made knowing that the valuation is <= bound + 1. Correct
     920             :      * to maximal value if reduction mod ppi altered this */
     921        2905 :     idx[ix] = minss(bound+1, idealval(nf, gsub(Spi,pibas), pr) - e*vDpi);
     922        2905 :     if (idx[ix] == 0) idx[ix] = -1;
     923        2457 :     else if (g)
     924             :     {
     925        1848 :       GEN Sg = pg? FpX_FpC_nfpoleval(nf, g, FpC_red(S, pg), pg): S;
     926        1848 :       if (vDg)
     927          42 :       { if (nfval(nf, gsub(Sg, gbas), pr) - e*vDg <= 0) idx[ix] = 0; }
     928             :       else /* same, more efficient */
     929        1806 :       { if (!ZC_prdvd(gsub(Sg, gbas), pr)) idx[ix] = 0; }
     930             :     }
     931        5488 :     for (j = 2; j < o; j++)
     932             :     {
     933        2583 :       piso = perm_mul(piso,iso);
     934        2583 :       if (ugcd(j,o)==1) idx[ piso[1] ] = idx[ix];
     935             :     }
     936        2905 :     set_avma(av2);
     937             :   }
     938         497 :   return gerepileuptoleaf(av, idx);
     939             : }
     940             : 
     941             : GEN
     942        2394 : idealramgroups_aut(GEN nf, GEN gal, GEN pr, GEN aut)
     943             : {
     944        2394 :   pari_sp av = avma;
     945             :   GEN tbl, idx, res, set, sub;
     946             :   long i, j, e, n, maxm, p;
     947             :   ulong et;
     948        2394 :   nf = checknf(nf);
     949        2394 :   checkgal(gal);
     950        2394 :   checkprid(pr);
     951        2394 :   gal_check_pol("idealramgroups",nf_get_pol(nf),gal_get_pol(gal));
     952        2394 :   e = pr_get_e(pr); n = nf_get_degree(nf);
     953        2394 :   p = itos(pr_get_p(pr));
     954        2394 :   if (e%p) return idealramgroupstame(nf, gal, aut, pr);
     955         497 :   (void) u_lvalrem(e,p,&et);
     956         497 :   idx = idealramgroupswild(nf, gal, aut, pr);
     957         497 :   sub = group_subgroups(galois_group(gal));
     958         497 :   tbl = subgroups_tableset(sub, n);
     959         497 :   maxm = vecsmall_max(idx)+1;
     960         497 :   res = cgetg(maxm+1,t_VEC);
     961         497 :   set = zero_F2v(n); F2v_set(set,1);
     962        2499 :   for(i=maxm; i>0; i--)
     963             :   {
     964             :     long ix;
     965       20468 :     for(j=1;j<=n;j++)
     966       18466 :       if (idx[j]==i-1)
     967        3521 :         F2v_set(set,j);
     968        2002 :     ix = tableset_find_index(tbl, set);
     969        2002 :     if (ix==0) pari_err_BUG("idealramgroups");
     970        2002 :     gel(res,i) = gel(sub, ix);
     971             :   }
     972         497 :   return gerepilecopy(av, res);
     973             : }
     974             : 
     975             : GEN
     976         112 : idealramgroups(GEN nf, GEN gal, GEN pr)
     977             : {
     978         112 :   return idealramgroups_aut(nf, gal, pr, NULL);
     979             : }
     980             : 
     981             : /* x = relative polynomial nf = absolute nf, bnf = absolute bnf */
     982             : GEN
     983         112 : get_bnfpol(GEN x, GEN *bnf, GEN *nf)
     984             : {
     985         112 :   *bnf = checkbnf_i(x);
     986         112 :   *nf  = checknf_i(x);
     987         112 :   if (*nf) x = nf_get_pol(*nf);
     988         112 :   if (typ(x) != t_POL) pari_err_TYPE("get_bnfpol",x);
     989         112 :   return x;
     990             : }
     991             : 
     992             : GEN
     993       73672 : get_nfpol(GEN x, GEN *nf)
     994             : {
     995       73672 :   if (typ(x) == t_POL) { *nf = NULL; return x; }
     996       48618 :   *nf = checknf(x); return nf_get_pol(*nf);
     997             : }
     998             : 
     999             : static GEN
    1000        1785 : incl_disc(GEN nfa, GEN a, int nolocal)
    1001             : {
    1002             :   GEN d;
    1003        1785 :   if (nfa) return nf_get_disc(nfa);
    1004        1701 :   if (nolocal) return NULL;
    1005        1498 :   d = ZX_disc(a);
    1006        1498 :   if (!signe(d)) pari_err_IRREDPOL("nfisincl",a);
    1007        1491 :   return d;
    1008             : }
    1009             : 
    1010             : /* is isomorphism / inclusion (a \subset b) compatible with what we know about
    1011             :  * basic invariants ? (degree, signature, discriminant); test for isomorphism
    1012             :  * if fliso is set and for inclusion otherwise */
    1013             : static int
    1014        1008 : tests_OK(GEN a, GEN nfa, GEN b, GEN nfb, long fliso)
    1015             : {
    1016             :   GEN da2, da, db, fa, P, E, U;
    1017        1008 :   long i, l, nP, q, m = degpol(a), n = degpol(b);
    1018             : 
    1019        1008 :   if (m <= 0) pari_err_IRREDPOL("nfisincl",a);
    1020        1008 :   if (n <= 0) pari_err_IRREDPOL("nfisincl",b);
    1021        1001 :   q = n / m; /* relative degree */
    1022        1001 :   if (fliso) { if (n != m) return 0; } else { if (n % m) return 0; }
    1023        1001 :   if (m == 1) return 1;
    1024             : 
    1025             :   /*local test expensive if n^2 >> m^4 <=> q = n/m >> m */
    1026         994 :   db = incl_disc(nfb, b, q > m);
    1027         994 :   da = db? incl_disc(nfa, a, 0): NULL;
    1028         987 :   if (nfa && nfb) /* both nf structures available */
    1029             :   {
    1030           7 :     long r1a = nf_get_r1(nfa), r1b = nf_get_r1(nfb);
    1031           0 :     return fliso ? (r1a == r1b && equalii(da, db))
    1032           7 :                  : (r1b <= r1a * q && dvdii(db, powiu(da, q)));
    1033             :   }
    1034         980 :   if (!db) return 1;
    1035         777 :   if (fliso) return issquare(gdiv(da,db));
    1036             : 
    1037         735 :   if (nfa)
    1038             :   {
    1039           7 :     P = nf_get_ramified_primes(nfa); l = lg(P);
    1040          14 :     for (i = 1; i < l; i++)
    1041           7 :       if (Z_pval(db, gel(P,i)) < q * Z_pval(da, gel(P,i))) return 0;
    1042           7 :     return 1;
    1043             :   }
    1044         728 :   else if (nfb)
    1045             :   {
    1046          28 :     P = nf_get_ramified_primes(nfb); l = lg(P);
    1047          56 :     for (i = 1; i < l; i++)
    1048             :     {
    1049          28 :       GEN p = gel(P,i);
    1050          28 :       long va = Z_pval(nfdisc(mkvec2(a, mkvec(p))), p);
    1051          28 :       if (va && Z_pval(db, gel(P,i)) < va * q) return 0;
    1052             :     }
    1053          28 :     return 1;
    1054             :   }
    1055             :   /* da = dK A^2, db = dL B^2, dL = dK^q * N(D)
    1056             :    * da = da1 * da2, da2 maximal s.t. (da2, db) = 1: let p a prime divisor of
    1057             :    * da2 then p \nmid da1 * dK and p | A => v_p(da) = v_p(da2) is even */
    1058         700 :   da2 = Z_ppo(da, db);
    1059         700 :   if (!is_pm1(da2))
    1060             :   { /* replace da by da1 all of whose prime divisors divide db */
    1061         126 :     da2 = absi_shallow(da2);
    1062         126 :     if (!Z_issquare(da2)) return 0;
    1063          14 :     da = diviiexact(da, da2);
    1064             :   }
    1065         588 :   if (is_pm1(da)) return 1;
    1066         581 :   fa = absZ_factor_limit(da, 0);
    1067         581 :   P = gel(fa,1);
    1068         581 :   E = gel(fa,2); nP = lg(P) - 1;
    1069         588 :   for (i=1; i<nP; i++) /* all but last factor (primes) */
    1070           7 :     if (mod2(gel(E,i)) && !dvdii(db, powiu(gel(P,i),q))) return 0;
    1071         581 :   U = gel(P,nP); /* unknown */
    1072         581 :   if (mod2(gel(E,i)) && expi(U) < 150)
    1073             :   { /* "unfactored" cofactor is small, finish */
    1074         490 :     if (abscmpiu(U, maxprime()) > 0)
    1075             :     {
    1076           0 :       fa = Z_factor(U);
    1077           0 :       P = gel(fa,1);
    1078           0 :       E = gel(fa,2);
    1079             :     }
    1080             :     else
    1081             :     {
    1082         490 :       P = mkvec(U);
    1083         490 :       E = mkvec(gen_1);
    1084             :     }
    1085         490 :     nP = lg(P) - 1;
    1086         980 :     for (i=1; i<=nP; i++)
    1087         490 :       if (mod2(gel(E,i)) && !dvdii(db, powiu(gel(P,i),q))) return 0;
    1088             :   }
    1089         581 :   return 1;
    1090             : }
    1091             : 
    1092             : GEN
    1093          49 : nfisisom(GEN a, GEN b)
    1094             : {
    1095          49 :   pari_sp av = avma;
    1096             :   long i, va, vb, lx;
    1097             :   GEN nfa, nfb, y, la, lb;
    1098          49 :   int newvar, sw = 0;
    1099             : 
    1100          49 :   a = get_nfpol(a, &nfa);
    1101          49 :   b = get_nfpol(b, &nfb);
    1102          49 :   if (!nfa) { a = Q_primpart(a); RgX_check_ZX(a, "nfisisom"); }
    1103          49 :   if (!nfb) { b = Q_primpart(b); RgX_check_ZX(b, "nfisisom"); }
    1104          49 :   if (nfa && !nfb) { swap(a,b); nfb = nfa; nfa = NULL; sw = 1; }
    1105          49 :   if (!tests_OK(a, nfa, b, nfb, 1)) { set_avma(av); return gen_0; }
    1106             : 
    1107          42 :   if (nfb) lb = gen_1; else nfb = b = ZX_Q_normalize(b,&lb);
    1108          42 :   if (nfa) la = gen_1; else nfa = a = ZX_Q_normalize(a,&la);
    1109          42 :   va = varn(a); vb = varn(b); newvar = (varncmp(vb,va) <= 0);
    1110          42 :   if (newvar) { a = leafcopy(a); setvarn(a, fetch_var_higher()); }
    1111          42 :   y = lift_shallow(nfroots(nfb,a));
    1112          42 :   if (newvar) (void)delete_var();
    1113          42 :   lx = lg(y); if (lx==1) { set_avma(av); return gen_0; }
    1114          42 :   if (sw) { vb = va; b = leafcopy(b); setvarn(b, vb); }
    1115         126 :   for (i=1; i<lx; i++)
    1116             :   {
    1117          84 :     GEN t = gel(y,i);
    1118          84 :     if (typ(t) == t_POL) setvarn(t, vb); else t = scalarpol(t, vb);
    1119          84 :     if (lb != gen_1) t = RgX_unscale(t, lb);
    1120          84 :     if (la != gen_1) t = RgX_Rg_div(t, la);
    1121          84 :     gel(y,i) = sw? RgXQ_reverse(t, b): t;
    1122             :   }
    1123          42 :   return gerepilecopy(av,y);
    1124             : }
    1125             : 
    1126             : static GEN
    1127         987 : partmap_reverse(GEN a, GEN b, GEN t, GEN la, GEN lb, long v)
    1128             : {
    1129         987 :   pari_sp av = avma;
    1130         987 :   GEN rnf = rnfequation2(a, t), z;
    1131         987 :   if (!RgX_equal(b, gel(rnf,1)))
    1132           7 :     { setvarn(b,v); pari_err_IRREDPOL("nfisincl", b); }
    1133         980 :   z = liftpol_shallow(gel(rnf, 2));
    1134         980 :   setvarn(z, v);
    1135         980 :   if (!isint1(lb)) z = RgX_unscale(z, lb);
    1136         980 :   if (!isint1(la)) z = RgX_Rg_div(z, la);
    1137         980 :   return gerepilecopy(av, z);
    1138             : }
    1139             : 
    1140             : GEN
    1141         973 : nfisincl0(GEN fa, GEN fb, long flag)
    1142             : {
    1143         973 :   pari_sp av = avma;
    1144             :   long i, k, vb, lx;
    1145             :   long da, db, d;
    1146             :   GEN a, b, nfa, nfb, x, y, la, lb;
    1147             :   int newvar;
    1148         973 :   if (flag < 0 || flag > 1) pari_err_FLAG("nfisincl");
    1149         973 :   a = get_nfpol(fa, &nfa);
    1150         973 :   b = get_nfpol(fb, &nfb);
    1151         973 :   da = degpol(a); db = degpol(b);
    1152         973 :   if (!nfa) { a = Q_primpart(a); RgX_check_ZX(a, "nsisincl"); }
    1153         973 :   if (!nfb) { b = Q_primpart(b); RgX_check_ZX(b, "nsisincl"); }
    1154         973 :   if (ZX_equal(a, b))
    1155             :   {
    1156          14 :     if (flag==1)
    1157             :     {
    1158           7 :       x = pol_x(varn(b));
    1159           7 :       return degpol(b) > 1 ? x: RgX_rem(x,b);
    1160             :     }
    1161           7 :     x = galoisconj(fb, NULL); settyp(x, t_VEC);
    1162           7 :     return gerepilecopy(av,x);
    1163             :   }
    1164         959 :   if (!tests_OK(a, nfa, b, nfb, 0)) { set_avma(av); return gen_0; }
    1165             : 
    1166         840 :   if (nfb) lb = gen_1; else nfb = b = ZX_Q_normalize(b,&lb);
    1167         840 :   if (nfa) la = gen_1; else nfa = a = ZX_Q_normalize(a,&la);
    1168         840 :   vb = varn(b); newvar = (varncmp(varn(a),vb) <= 0);
    1169         840 :   if (newvar) { b = leafcopy(b); setvarn(b, fetch_var_higher()); }
    1170         840 :   y = lift_shallow(gel(nffactor(nfa,b),1));
    1171         840 :   lx = lg(y);
    1172         840 :   da = degpol(a); db = degpol(b); d = db/da;
    1173         840 :   x = cgetg(lx, t_VEC);
    1174        1211 :   for (i=1, k=1; i<lx; i++)
    1175             :   {
    1176        1057 :     GEN t = gel(y,i);
    1177        1057 :     if (degpol(t)!=d) continue;
    1178         987 :     gel(x, k++) = partmap_reverse(a, b, t, la, lb, vb);
    1179         980 :     if (flag==1) break;
    1180             :   }
    1181         833 :   if (newvar) (void)delete_var();
    1182         833 :   if (k==1) { set_avma(av); return gen_0; }
    1183         770 :   if (flag==1) return gerepilecopy(av,gel(x,1));
    1184          91 :   setlg(x, k);
    1185          91 :   gen_sort_inplace(x, (void*)&cmp_RgX, &cmp_nodata, NULL);
    1186          91 :   return gerepilecopy(av,x);
    1187             : }
    1188             : 
    1189             : GEN
    1190         105 : nfisincl(GEN fa, GEN fb) { return nfisincl0(fa, fb, 0); }
    1191             : 
    1192             : static GEN
    1193           7 : lastel(GEN x) { return gel(x, lg(x)-1); }
    1194             : 
    1195             : static GEN
    1196         140 : nfsplitting_composite(GEN P)
    1197             : {
    1198         140 :   GEN F = gel(ZX_factor(P), 1), Q = NULL;
    1199         140 :   long i, n = lg(F)-1;
    1200         280 :   for (i = 1; i <= n; i++)
    1201             :   {
    1202         140 :     GEN Fi = gel(F, i);
    1203         140 :     if (degpol(Fi) == 1) continue;
    1204         126 :     Q = Q ? lastel(compositum(Q, Fi)): Fi;
    1205             :   }
    1206         140 :   return Q ? Q: pol_x(varn(P));
    1207             : }
    1208             : GEN
    1209         147 : nfsplitting(GEN T, GEN D)
    1210             : {
    1211         147 :   pari_sp av = avma;
    1212             :   long d, v;
    1213             :   GEN F, K;
    1214         147 :   T = get_nfpol(T,&K);
    1215         140 :   if (!K)
    1216             :   {
    1217         133 :     if (typ(T) != t_POL) pari_err_TYPE("nfsplitting",T);
    1218         133 :     T = Q_primpart(T);
    1219         133 :     RgX_check_ZX(T,"nfsplitting");
    1220             :   }
    1221         140 :   T = nfsplitting_composite(T);
    1222         140 :   d = degpol(T);
    1223         140 :   if (d<=1) return pol_x(varn(T));
    1224         112 :   if (!K) {
    1225         105 :     if (!isint1(leading_coeff(T))) K = T = polredbest(T,0);
    1226         105 :     K = T;
    1227             :   }
    1228         112 :   if (D)
    1229             :   {
    1230          21 :     if (typ(D) != t_INT || signe(D) < 1) pari_err_TYPE("nfsplitting",D);
    1231             :   }
    1232             :   else
    1233             :   {
    1234          91 :     char *data = stack_strcat(pari_datadir, "/galdata");
    1235          91 :     long dmax = pari_is_dir(data)? 11: 7;
    1236          91 :     D = (d <= dmax)? gel(polgalois(T,DEFAULTPREC), 1): mpfact(d);
    1237             :   }
    1238         112 :   d = itos_or_0(D);
    1239         112 :   v = varn(T);
    1240         112 :   T = leafcopy(T); setvarn(T, fetch_var_higher());
    1241         112 :   for(F = T;;)
    1242          35 :   {
    1243         147 :     GEN P = gel(nffactor(K, F), 1), Q = gel(P,lg(P)-1);
    1244         147 :     if (degpol(gel(P,1)) == degpol(Q)) break;
    1245         119 :     F = rnfequation(K,Q);
    1246         119 :     if (degpol(F) == d) break;
    1247             :   }
    1248         112 :   if (umodiu(D,degpol(F)))
    1249             :   {
    1250           7 :     char *sD = itostr(D);
    1251           7 :     pari_warn(warner,stack_strcat("ignoring incorrect degree bound ",sD));
    1252             :   }
    1253         112 :   (void)delete_var();
    1254         112 :   setvarn(F,v);
    1255         112 :   return gerepilecopy(av, F);
    1256             : }
    1257             : 
    1258             : /*************************************************************************/
    1259             : /**                                                                     **/
    1260             : /**                               INITALG                               **/
    1261             : /**                                                                     **/
    1262             : /*************************************************************************/
    1263             : typedef struct {
    1264             :   GEN T;
    1265             :   GEN ro; /* roots of T */
    1266             :   long r1;
    1267             :   GEN basden;
    1268             :   long prec;
    1269             :   long extraprec; /* possibly -1 = irrelevant or not computed */
    1270             :   GEN M, G; /* possibly NULL = irrelevant or not computed */
    1271             : } nffp_t;
    1272             : 
    1273             : static GEN
    1274       34551 : get_roots(GEN x, long r1, long prec)
    1275             : {
    1276             :   long i, ru;
    1277             :   GEN z;
    1278       34551 :   if (typ(x) != t_POL)
    1279             :   {
    1280           0 :     z = leafcopy(x);
    1281           0 :     ru = (lg(z)-1 + r1) >> 1;
    1282             :   }
    1283             :   else
    1284             :   {
    1285       34551 :     long n = degpol(x);
    1286       34551 :     z = (r1 == n)? ZX_realroots_irred(x, prec): QX_complex_roots(x,prec);
    1287       34552 :     ru = (n+r1)>>1;
    1288             :   }
    1289       79978 :   for (i=r1+1; i<=ru; i++) gel(z,i) = gel(z, (i<<1)-r1);
    1290       34552 :   z[0]=evaltyp(t_VEC)|evallg(ru+1); return z;
    1291             : }
    1292             : 
    1293             : GEN
    1294           0 : nf_get_allroots(GEN nf)
    1295             : {
    1296           0 :   return embed_roots(nf_get_roots(nf), nf_get_r1(nf));
    1297             : }
    1298             : 
    1299             : /* For internal use. compute trace(x mod pol), sym=polsym(pol,deg(pol)-1) */
    1300             : GEN
    1301      111678 : quicktrace(GEN x, GEN sym)
    1302             : {
    1303      111678 :   GEN p1 = gen_0;
    1304             :   long i;
    1305             : 
    1306      111678 :   if (typ(x) != t_POL) return gmul(x, gel(sym,1));
    1307      111678 :   if (signe(x))
    1308             :   {
    1309      111678 :     sym--;
    1310     1438976 :     for (i=lg(x)-1; i>1; i--)
    1311     1327298 :       p1 = gadd(p1, gmul(gel(x,i),gel(sym,i)));
    1312             :   }
    1313      111678 :   return p1;
    1314             : }
    1315             : 
    1316             : static GEN
    1317       19421 : get_Tr(GEN mul, GEN x, GEN basden)
    1318             : {
    1319       19421 :   GEN t, bas = gel(basden,1), den = gel(basden,2);
    1320       19421 :   long i, j, n = lg(bas)-1;
    1321       19421 :   GEN T = cgetg(n+1,t_MAT), TW = cgetg(n+1,t_COL), sym = polsym(x, n-1);
    1322             : 
    1323       19421 :   gel(TW,1) = utoipos(n);
    1324       60420 :   for (i=2; i<=n; i++)
    1325             :   {
    1326       40999 :     t = quicktrace(gel(bas,i), sym);
    1327       40999 :     if (den && gel(den,i)) t = diviiexact(t,gel(den,i));
    1328       40999 :     gel(TW,i) = t; /* tr(w[i]) */
    1329             :   }
    1330       19421 :   gel(T,1) = TW;
    1331       60420 :   for (i=2; i<=n; i++)
    1332             :   {
    1333       40999 :     gel(T,i) = cgetg(n+1,t_COL); gcoeff(T,1,i) = gel(TW,i);
    1334      239820 :     for (j=2; j<=i; j++) /* Tr(W[i]W[j]) */
    1335      198821 :       gcoeff(T,i,j) = gcoeff(T,j,i) = ZV_dotproduct(gel(mul,j+(i-1)*n), TW);
    1336             :   }
    1337       19421 :   return T;
    1338             : }
    1339             : 
    1340             : /* return [bas[i]*denom(bas[i]), denom(bas[i])], denom 1 is given as NULL */
    1341             : static GEN
    1342       42951 : get_bas_den(GEN bas)
    1343             : {
    1344       42951 :   GEN b,d,den, dbas = leafcopy(bas);
    1345       42951 :   long i, l = lg(bas);
    1346       42951 :   int power = 1;
    1347       42951 :   den = cgetg(l,t_VEC);
    1348      188731 :   for (i=1; i<l; i++)
    1349             :   {
    1350      145781 :     b = Q_remove_denom(gel(bas,i), &d);
    1351      145780 :     gel(dbas,i) = b;
    1352      145780 :     gel(den,i) = d; if (d) power = 0;
    1353             :   }
    1354       42950 :   if (power) den = NULL; /* power basis */
    1355       42950 :   return mkvec2(dbas, den);
    1356             : }
    1357             : 
    1358             : /* return multiplication table for S->basis */
    1359             : static GEN
    1360       19421 : nf_multable(nfmaxord_t *S, GEN invbas)
    1361             : {
    1362       19421 :   GEN T = S->T, w = gel(S->basden,1), den = gel(S->basden,2);
    1363       19421 :   long i,j, n = degpol(T);
    1364       19421 :   GEN mul = cgetg(n*n+1,t_MAT);
    1365             : 
    1366             :   /* i = 1 split for efficiency, assume w[1] = 1 */
    1367       79841 :   for (j=1; j<=n; j++)
    1368       60420 :     gel(mul,j) = gel(mul,1+(j-1)*n) = col_ei(n, j);
    1369       60420 :   for (i=2; i<=n; i++)
    1370      239820 :     for (j=i; j<=n; j++)
    1371             :     {
    1372      198821 :       pari_sp av = avma;
    1373      198821 :       GEN z = (i == j)? ZXQ_sqr(gel(w,i), T): ZXQ_mul(gel(w,i),gel(w,j), T);
    1374      198821 :       z = ZM_ZX_mul(invbas, z); /* integral column */
    1375      198821 :       if (den)
    1376             :       {
    1377      134470 :         GEN d = mul_denom(gel(den,i), gel(den,j));
    1378      134469 :         if (d) z = ZC_Z_divexact(z, d);
    1379             :       }
    1380      198821 :       gel(mul,j+(i-1)*n) = gel(mul,i+(j-1)*n) = gerepileupto(av,z);
    1381             :     }
    1382       19421 :   return mul;
    1383             : }
    1384             : 
    1385             : /* as get_Tr, mul_table not precomputed */
    1386             : static GEN
    1387        6464 : make_Tr(nfmaxord_t *S)
    1388             : {
    1389        6464 :   GEN T = S->T, w = gel(S->basden,1), den = gel(S->basden,2);
    1390        6464 :   long i,j, n = degpol(T);
    1391        6464 :   GEN c, t, d, M = cgetg(n+1,t_MAT), sym = polsym(T, n-1);
    1392             : 
    1393             :   /* W[i] = w[i]/den[i]; assume W[1] = 1, case i = 1 split for efficiency */
    1394        6464 :   c = cgetg(n+1,t_COL); gel(M,1) = c;
    1395        6464 :   gel(c, 1) = utoipos(n);
    1396       18616 :   for (j=2; j<=n; j++)
    1397             :   {
    1398       12152 :     pari_sp av = avma;
    1399       12152 :     t = quicktrace(gel(w,j), sym);
    1400       12152 :     if (den)
    1401             :     {
    1402        7427 :       d = gel(den,j);
    1403        7427 :       if (d) t = diviiexact(t, d);
    1404             :     }
    1405       12152 :     gel(c,j) = gerepileuptoint(av, t);
    1406             :   }
    1407       18616 :   for (i=2; i<=n; i++)
    1408             :   {
    1409       12152 :     c = cgetg(n+1,t_COL); gel(M,i) = c;
    1410       70273 :     for (j=1; j<i ; j++) gel(c,j) = gcoeff(M,i,j);
    1411       70273 :     for (   ; j<=n; j++)
    1412             :     {
    1413       58121 :       pari_sp av = avma;
    1414       58121 :       t = (i == j)? ZXQ_sqr(gel(w,i), T): ZXQ_mul(gel(w,i),gel(w,j), T);
    1415       58121 :       t = quicktrace(t, sym);
    1416       58121 :       if (den)
    1417             :       {
    1418       48461 :         d = mul_denom(gel(den,i),gel(den,j));
    1419       48461 :         if (d) t = diviiexact(t, d);
    1420             :       }
    1421       58121 :       gel(c,j) = gerepileuptoint(av, t); /* Tr (W[i]W[j]) */
    1422             :     }
    1423             :   }
    1424        6464 :   return M;
    1425             : }
    1426             : 
    1427             : /* [bas[i]/den[i]]= integer basis. roo = real part of the roots */
    1428             : static void
    1429       38088 : make_M(nffp_t *F, int trunc)
    1430             : {
    1431       38088 :   GEN bas = gel(F->basden,1), den = gel(F->basden,2), ro = F->ro;
    1432             :   GEN m, d, M;
    1433       38088 :   long i, j, l = lg(ro), n = lg(bas);
    1434       38088 :   M = cgetg(n,t_MAT);
    1435       38088 :   gel(M,1) = const_col(l-1, gen_1); /* bas[1] = 1 */
    1436      134211 :   for (j=2; j<n; j++) gel(M,j) = cgetg(l,t_COL);
    1437      118479 :   for (i=1; i<l; i++)
    1438             :   {
    1439       80391 :     GEN r = gel(ro,i), ri;
    1440       80391 :     ri = (gexpo(r) > 1)? ginv(r): NULL;
    1441      633949 :     for (j=2; j<n; j++) gcoeff(M,i,j) = RgX_cxeval(gel(bas,j), r, ri);
    1442             :   }
    1443       38088 :   if (den)
    1444       67052 :     for (j=2; j<n; j++)
    1445             :     {
    1446       56700 :       d = gel(den,j); if (!d) continue;
    1447       47094 :       m = gel(M,j);
    1448      398761 :       for (i=1; i<l; i++) gel(m,i) = gdiv(gel(m,i), d);
    1449             :     }
    1450             : 
    1451       38088 :   if (trunc && gprecision(M) > F->prec)
    1452             :   {
    1453        3715 :     M     = gprec_w(M, F->prec);
    1454        3715 :     F->ro = gprec_w(ro,F->prec);
    1455             :   }
    1456       38088 :   F->M = M;
    1457       38088 : }
    1458             : 
    1459             : /* return G real such that G~ * G = T_2 */
    1460             : static void
    1461       38088 : make_G(nffp_t *F)
    1462             : {
    1463       38088 :   GEN G, M = F->M;
    1464       38088 :   long i, j, k, r1 = F->r1, l = lg(M);
    1465             : 
    1466       38088 :   if (r1 == l-1) { F->G = M; return; }
    1467       30679 :   G = cgetg(l, t_MAT);
    1468      144167 :   for (j = 1; j < l; j++)
    1469             :   {
    1470      113488 :     GEN g, m = gel(M,j);
    1471      113488 :     gel(G,j) = g = cgetg(l, t_COL);
    1472      158590 :     for (k = i = 1; i <= r1; i++) gel(g,k++) = gel(m,i);
    1473      561730 :     for (     ; k < l; i++)
    1474             :     {
    1475      448242 :       GEN r = gel(m,i);
    1476      448242 :       if (typ(r) == t_COMPLEX)
    1477             :       {
    1478      394422 :         GEN a = gel(r,1), b = gel(r,2);
    1479      394422 :         gel(g,k++) = mpadd(a, b);
    1480      394422 :         gel(g,k++) = mpsub(a, b);
    1481             :       }
    1482             :       else
    1483             :       {
    1484       53820 :         gel(g,k++) = r;
    1485       53820 :         gel(g,k++) = r;
    1486             :       }
    1487             :     }
    1488             :   }
    1489       30679 :   F->G = G;
    1490             : }
    1491             : 
    1492             : static void
    1493       38087 : make_M_G(nffp_t *F, int trunc)
    1494             : {
    1495             :   long n, eBD, prec;
    1496       38087 :   if (F->extraprec < 0)
    1497             :   { /* not initialized yet; compute roots so that absolute accuracy
    1498             :      * of M & G >= prec */
    1499             :     double er;
    1500       38068 :     n = degpol(F->T);
    1501       38068 :     eBD = 1 + gexpo(gel(F->basden,1));
    1502       38068 :     er  = F->ro? (1+gexpo(F->ro)): fujiwara_bound(F->T);
    1503       38067 :     if (er < 0) er = 0;
    1504       38067 :     F->extraprec = nbits2extraprec(n*er + eBD + log2(n));
    1505             :   }
    1506       38086 :   prec = F->prec + F->extraprec;
    1507             : #ifndef LONG_IS_64BIT
    1508             :   /* make sure that default accuracy is the same on 32/64bit */
    1509        5448 :   if (odd(prec)) prec += EXTRAPRECWORD;
    1510             : #endif
    1511       38086 :   if (!F->ro || gprecision(gel(F->ro,1)) < prec)
    1512       34550 :     F->ro = get_roots(F->T, F->r1, prec);
    1513             : 
    1514       38088 :   make_M(F, trunc);
    1515       38088 :   make_G(F);
    1516       38088 : }
    1517             : 
    1518             : static void
    1519       36542 : nffp_init(nffp_t *F, nfmaxord_t *S, long prec)
    1520             : {
    1521       36542 :   F->T  = S->T;
    1522       36542 :   F->r1 = S->r1;
    1523       36542 :   F->basden = S->basden;
    1524       36542 :   F->ro = NULL;
    1525       36542 :   F->extraprec = -1;
    1526       36542 :   F->prec = prec;
    1527       36542 : }
    1528             : 
    1529             : /* let bas a t_VEC of QX giving a Z-basis of O_K. Return the index of the
    1530             :  * basis. Assume bas[1] = 1 and that the leading coefficient of elements
    1531             :  * of bas are of the form 1/b for a t_INT b */
    1532             : static GEN
    1533        1442 : get_nfindex(GEN bas)
    1534             : {
    1535        1442 :   pari_sp av = avma;
    1536        1442 :   long n = lg(bas)-1, i;
    1537             :   GEN D, d, mat;
    1538             : 
    1539             :   /* assume bas[1] = 1 */
    1540        1442 :   D = gel(bas,1);
    1541        1442 :   if (! is_pm1(simplify_shallow(D))) pari_err_TYPE("get_nfindex", D);
    1542        1442 :   D = gen_1;
    1543        7553 :   for (i = 2; i <= n; i++)
    1544             :   { /* after nfbasis, basis is upper triangular! */
    1545        6118 :     GEN B = gel(bas,i), lc;
    1546        6118 :     if (degpol(B) != i-1) break;
    1547        6111 :     lc = gel(B, i+1);
    1548        6111 :     switch (typ(lc))
    1549             :     {
    1550        2401 :       case t_INT: continue;
    1551        3710 :       case t_FRAC: if (is_pm1(gel(lc,1)) ) {D = mulii(D, gel(lc,2)); continue;}
    1552           0 :       default: pari_err_TYPE("get_nfindex", B);
    1553             :     }
    1554             :   }
    1555        1442 :   if (i <= n)
    1556             :   { /* not triangular after all */
    1557           7 :     bas = vecslice(bas,i,n);
    1558           7 :     bas = Q_remove_denom(bas, &d);
    1559           7 :     if (!d) return D;
    1560           7 :     mat = RgV_to_RgM(bas, n);
    1561           7 :     mat = rowslice(mat, i,n);
    1562           7 :     D = mulii(D, diviiexact(powiu(d, n-i+1), absi_shallow(ZM_det(mat))));
    1563             :   }
    1564        1442 :   return gerepileuptoint(av, D);
    1565             : }
    1566             : /* make sure all components of S are initialized */
    1567             : static void
    1568       38841 : nfmaxord_complete(nfmaxord_t *S)
    1569             : {
    1570       38841 :   if (!S->dT) S->dT = ZX_disc(S->T);
    1571       38841 :   if (!S->index)
    1572             :   {
    1573        1442 :     if (S->dK) /* fast */
    1574           0 :       S->index = sqrti( diviiexact(S->dT, S->dK) );
    1575             :     else
    1576        1442 :       S->index = get_nfindex(S->basis);
    1577             :   }
    1578       38841 :   if (!S->dK) S->dK = diviiexact(S->dT, sqri(S->index));
    1579       38841 :   if (S->r1 < 0) S->r1 = ZX_sturm_irred(S->T);
    1580       38841 :   if (!S->basden) S->basden = get_bas_den(S->basis);
    1581       38841 : }
    1582             : 
    1583             : GEN
    1584       19420 : nfmaxord_to_nf(nfmaxord_t *S, GEN ro, long prec)
    1585             : {
    1586       19420 :   GEN nf = cgetg(10,t_VEC);
    1587       19420 :   GEN T = S->T, Tr, D, w, A, dA, MDI, mat = cgetg(9,t_VEC);
    1588       19420 :   long n = degpol(T);
    1589             :   nffp_t F;
    1590       19420 :   nfmaxord_complete(S);
    1591       19420 :   nffp_init(&F,S,prec);
    1592       19420 :   F.ro = ro;
    1593       19420 :   make_M_G(&F, 0);
    1594             : 
    1595       19421 :   gel(nf,1) = S->T;
    1596       19421 :   gel(nf,2) = mkvec2s(S->r1, (n - S->r1)>>1);
    1597       19421 :   gel(nf,3) = S->dK;
    1598       19421 :   gel(nf,4) = S->index;
    1599       19421 :   gel(nf,5) = mat;
    1600       19421 :   gel(nf,6) = F.ro;
    1601       19421 :   w = S->basis;
    1602       19421 :   if (!is_pm1(S->index)) w = Q_remove_denom(w, NULL);
    1603       19421 :   gel(nf,7) = w;
    1604       19421 :   gel(nf,8) = ZM_inv(RgV_to_RgM(w,n), NULL);
    1605       19421 :   gel(nf,9) = nf_multable(S, nf_get_invzk(nf));
    1606       19421 :   gel(mat,1) = F.M;
    1607       19421 :   gel(mat,2) = F.G;
    1608             : 
    1609       19421 :   Tr = get_Tr(gel(nf,9), T, S->basden);
    1610       19421 :   gel(mat,6) = A = ZM_inv(Tr, &dA); /* dA T^-1, primitive */
    1611       19421 :   A = ZM_hnfmodid(A, dA);
    1612             :   /* CAVEAT: nf is not complete yet, but the fields needed for
    1613             :    * idealtwoelt, zk_scalar_or_multable and idealinv are present ! */
    1614       19421 :   MDI = idealtwoelt(nf, A);
    1615       19421 :   gel(MDI,2) = zk_scalar_or_multable(nf, gel(MDI,2));
    1616       19421 :   gel(mat,7) = MDI;
    1617       19421 :   if (is_pm1(S->index))
    1618             :   { /* principal ideal (T'), whose norm is |dK| */
    1619       15473 :     D = zk_scalar_or_multable(nf, ZX_deriv(T));
    1620       15473 :     if (typ(D) == t_MAT) D = ZM_hnfmod(D, absi_shallow(S->dK));
    1621             :   }
    1622             :   else
    1623             :   {
    1624        3948 :     GEN c = diviiexact(dA, gcoeff(A,1,1));
    1625        3948 :     D = idealHNF_inv_Z(nf, A); /* (A\cap Z) / A */
    1626        3948 :     if (!is_pm1(c)) D = ZM_Z_mul(D, c);
    1627             :   }
    1628       19421 :   gel(mat,3) = RM_round_maxrank(F.G);
    1629       19421 :   gel(mat,4) = Tr;
    1630       19421 :   gel(mat,5) = D;
    1631       19421 :   gel(mat,8) = shallowtrans(S->dKP? S->dKP: gel(absZ_factor(S->dK), 1));
    1632       19421 :   return nf;
    1633             : }
    1634             : 
    1635             : static GEN
    1636         539 : primes_certify(GEN dK, GEN dKP)
    1637             : {
    1638         539 :   long i, l = lg(dKP);
    1639         539 :   GEN v, w, D = dK;
    1640         539 :   v = vectrunc_init(l);
    1641         539 :   w = vectrunc_init(l);
    1642        1652 :   for (i = 1; i < l; i++)
    1643             :   {
    1644        1113 :     GEN p = gel(dKP,i);
    1645        1113 :     vectrunc_append(isprime(p)? w: v, p);
    1646        1113 :     (void)Z_pvalrem(D, p, &D);
    1647             :   }
    1648         539 :   if (!is_pm1(D))
    1649             :   {
    1650           0 :     if (signe(D) < 0) D = negi(D);
    1651           0 :     vectrunc_append(isprime(D)? w: v, D);
    1652             :   }
    1653         539 :   return mkvec2(v,w);
    1654             : }
    1655             : GEN
    1656         224 : nfcertify(GEN nf)
    1657             : {
    1658         224 :   pari_sp av = avma;
    1659             :   GEN vw;
    1660         224 :   nf = checknf(nf);
    1661         224 :   vw = primes_certify(nf_get_disc(nf), nf_get_ramified_primes(nf));
    1662         224 :   return gerepilecopy(av, gel(vw,1));
    1663             : }
    1664             : 
    1665             : /* set *pro to roots of S->T */
    1666             : static GEN
    1667       14896 : get_red_G(nfmaxord_t *S, GEN *pro)
    1668             : {
    1669       14896 :   GEN G, u, u0 = NULL;
    1670             :   pari_sp av;
    1671       14896 :   long i, prec, n = degpol(S->T);
    1672             :   nffp_t F;
    1673             : 
    1674       14896 :   prec = nbits2prec(n+32);
    1675       14896 :   nffp_init(&F, S, prec);
    1676       14896 :   av = avma;
    1677       14896 :   for (i=1; ; i++)
    1678             :   {
    1679       14896 :     F.prec = prec; make_M_G(&F, 0); G = F.G;
    1680       14896 :     if (u0) G = RgM_mul(G, u0);
    1681       14896 :     if (DEBUGLEVEL)
    1682           0 :       err_printf("get_red_G: starting LLL, prec = %ld (%ld + %ld)\n",
    1683           0 :                   prec + F.extraprec, prec, F.extraprec);
    1684       14896 :     if ((u = lllfp(G, 0.99, LLL_KEEP_FIRST)))
    1685             :     {
    1686       14896 :       if (lg(u)-1 == n) break;
    1687             :       /* singular ==> loss of accuracy */
    1688           0 :       if (u0) u0 = gerepileupto(av, RgM_mul(u0,u));
    1689           0 :       else    u0 = gerepilecopy(av, u);
    1690             :     }
    1691           0 :     prec = precdbl(prec) + nbits2extraprec(gexpo(u0));
    1692           0 :     F.ro = NULL;
    1693           0 :     if (DEBUGLEVEL) pari_warn(warnprec,"get_red_G", prec);
    1694             :   }
    1695       14896 :   if (u0) u = RgM_mul(u0,u);
    1696       14896 :   *pro = F.ro; return u;
    1697             : }
    1698             : 
    1699             : /* Compute an LLL-reduced basis for the integer basis of nf(T).
    1700             :  * set *pro = roots of x if computed [NULL if not computed] */
    1701             : static void
    1702       21360 : set_LLL_basis(nfmaxord_t *S, GEN *pro, double DELTA)
    1703             : {
    1704       21360 :   GEN B = S->basis;
    1705       21360 :   if (S->r1 < 0) S->r1 = ZX_sturm_irred(S->T);
    1706       21360 :   if (!S->basden) S->basden = get_bas_den(B);
    1707       21360 :   if (S->r1 == degpol(S->T)) {
    1708        6464 :     pari_sp av = avma;
    1709        6464 :     GEN u = ZM_lll(make_Tr(S), DELTA, LLL_GRAM|LLL_KEEP_FIRST|LLL_IM);
    1710        6464 :     B = gerepileupto(av, RgV_RgM_mul(B, u));
    1711        6464 :     *pro = NULL;
    1712             :   }
    1713             :   else
    1714       14896 :     B = RgV_RgM_mul(B, get_red_G(S, pro));
    1715       21360 :   S->basis = B;
    1716       21360 :   S->basden = get_bas_den(B);
    1717       21359 : }
    1718             : 
    1719             : /* = 1 iff |a| > |b| or equality and a > 0 */
    1720             : static int
    1721       30420 : cmpii_polred(GEN a, GEN b)
    1722             : {
    1723       30420 :   int fl = abscmpii(a, b);
    1724             :   long sa, sb;
    1725       30420 :   if (fl) return fl;
    1726       26286 :   sa = signe(a);
    1727       26286 :   sb = signe(b);
    1728       26286 :   if (sa == sb) return 0;
    1729          21 :   return sa == 1? 1: -1;
    1730             : }
    1731             : static int
    1732        6298 : ZX_cmp(GEN x, GEN y)
    1733        6298 : {  return gen_cmp_RgX((void*)cmpii_polred, x, y); }
    1734             : /* current best: ZX x of discriminant *dx, is ZX y better than x ?
    1735             :  * (if so update *dx); both x and y are monic */
    1736             : static int
    1737       22711 : ZX_is_better(GEN y, GEN x, GEN *dx)
    1738             : {
    1739       22711 :   GEN d = ZX_disc(y);
    1740             :   int cmp;
    1741       22711 :   if (!*dx) *dx = ZX_disc(x);
    1742       22711 :   cmp = abscmpii(d, *dx);
    1743       22711 :   if (cmp < 0) { *dx = d; return 1; }
    1744       21138 :   return cmp? 0: (ZX_cmp(y, x) < 0);
    1745             : }
    1746             : 
    1747             : static void polredbest_aux(nfmaxord_t *S, GEN *pro, GEN *px, GEN *pdx, GEN *pa);
    1748             : /* Seek a simpler, polynomial pol defining the same number field as
    1749             :  * x (assumed to be monic at this point) */
    1750             : static GEN
    1751         287 : nfpolred(nfmaxord_t *S, GEN *pro)
    1752             : {
    1753         287 :   GEN x = S->T, dx, b, rev;
    1754         287 :   long n = degpol(x), v = varn(x);
    1755             : 
    1756         287 :   if (n == 1) {
    1757          98 :     S->T = pol_x(v);
    1758          98 :     *pro = NULL;
    1759          98 :     return scalarpol_shallow(negi(gel(x,2)), v);
    1760             :   }
    1761         189 :   polredbest_aux(S, pro, &x, &dx, &b);
    1762         189 :   if (x == S->T) return NULL; /* no improvement */
    1763         161 :   if (DEBUGLEVEL>1) err_printf("xbest = %Ps\n",x);
    1764             : 
    1765             :   /* update T */
    1766         161 :   rev = QXQ_reverse(b, S->T);
    1767         161 :   S->basis = QXV_QXQ_eval(S->basis, rev, x);
    1768         161 :   S->index = sqrti( diviiexact(dx,S->dK) );
    1769         161 :   S->basden = get_bas_den(S->basis);
    1770         161 :   S->dT = dx;
    1771         161 :   S->T = x;
    1772         161 :   *pro = NULL; /* reset */
    1773         161 :   return rev;
    1774             : }
    1775             : 
    1776             : /* Either nf type or ZX or [monic ZX, data], where data is either an integral
    1777             :  * basis (deprecated), or listP data (nfbasis input format) to specify
    1778             :  * a set of primes at with the basis order must be maximal.
    1779             :  * 1) nf type (or unrecognized): return t_VEC
    1780             :  * 2) ZX or [ZX, listP]: return t_POL
    1781             :  * 3) [ZX, order basis]: return 0 (deprecated)
    1782             :  * incorrect: return -1 */
    1783             : static long
    1784       17622 : nf_input_type(GEN x)
    1785             : {
    1786       17622 :   GEN T, V, DKP = NULL;
    1787             :   long i, d, v;
    1788       17622 :   switch(typ(x))
    1789             :   {
    1790       15704 :     case t_POL: return t_POL;
    1791        1918 :     case t_VEC:
    1792        1918 :       switch(lg(x))
    1793             :       {
    1794        1568 :         case 4: DKP = gel(x,3);
    1795        1890 :         case 3: break;
    1796          28 :         default: return t_VEC; /* nf or incorrect */
    1797             :       }
    1798        1890 :       T = gel(x,1); V = gel(x,2);
    1799        1890 :       if (typ(T) != t_POL) return -1;
    1800        1890 :       switch(typ(V))
    1801             :       {
    1802         224 :         case t_INT: case t_MAT: return t_POL;
    1803        1666 :         case t_VEC: case t_COL:
    1804        1666 :           if (RgV_is_ZV(V)) return t_POL;
    1805        1624 :           break;
    1806           0 :         default: return -1;
    1807             :       }
    1808        1624 :       d = degpol(T); v = varn(T);
    1809        1624 :       if (d<1 || !RgX_is_ZX(T) || !isint1(gel(T,d+2)) || lg(V)-1!=d) return -1;
    1810       10171 :       for (i = 1; i <= d; i++)
    1811             :       { /* check integer basis */
    1812        8568 :         GEN c = gel(V,i);
    1813        8568 :         switch(typ(c))
    1814             :         {
    1815          28 :           case t_INT: break;
    1816        8540 :           case t_POL: if (varn(c) == v && RgX_is_QX(c) && degpol(c) < d) break;
    1817             :           /* fall through */
    1818          14 :           default: return -1;
    1819             :         }
    1820             :       }
    1821        1603 :       if (DKP && (typ(DKP) != t_VEC || !RgV_is_ZV(DKP))) return -1;
    1822        1603 :       return 0;
    1823             :   }
    1824           0 :   return t_VEC; /* nf or incorrect */
    1825             : }
    1826             : 
    1827             : /* cater for obsolete nf_PARTIALFACT flag */
    1828             : static void
    1829        2030 : nfinit_basic_partial(nfmaxord_t *S, GEN T)
    1830             : {
    1831        2030 :   if (typ(T) == t_POL) { nfmaxord(S, mkvec2(T,utoipos(500000)), 0); }
    1832         161 :   else nfinit_basic(S, T);
    1833        2030 : }
    1834             : /* true nf */
    1835             : static GEN
    1836        1553 : nf_basden(GEN nf)
    1837             : {
    1838        1553 :   GEN zkD = nf_get_zkprimpart(nf), D = nf_get_zkden(nf);
    1839        1553 :   D = equali1(D)? NULL: const_vec(lg(zkD)-1, D);
    1840        1553 :   return mkvec2(zkD, D);
    1841             : }
    1842             : void
    1843       17622 : nfinit_basic(nfmaxord_t *S, GEN T)
    1844             : {
    1845       17622 :   switch (nf_input_type(T))
    1846             :   {
    1847       15970 :     case t_POL: nfmaxord(S, T, 0); return;
    1848          28 :     case t_VEC:
    1849             :     { /* nf, bnf, bnr */
    1850          28 :       GEN nf = checknf(T);
    1851          28 :       S->T = S->T0 = nf_get_pol(nf);
    1852          28 :       S->basis = nf_get_zk(nf); /* probably useless */
    1853          28 :       S->basden = nf_basden(nf);
    1854          28 :       S->index = nf_get_index(nf);
    1855          28 :       S->dK = nf_get_disc(nf);
    1856          28 :       S->dKP = nf_get_ramified_primes(nf);
    1857          28 :       S->dT = mulii(S->dK, sqri(S->index));
    1858          28 :       S->r1 = nf_get_r1(nf); break;
    1859             :     }
    1860        1603 :     case 0: /* monic integral polynomial + integer basis (+ ramified primes)*/
    1861        1603 :       S->T = S->T0 = gel(T,1);
    1862        1603 :       S->basis = gel(T,2);
    1863        1603 :       S->basden = NULL;
    1864        1603 :       S->index = NULL;
    1865        1603 :       S->dK = NULL;
    1866        1603 :       S->dKP = lg(T) == 4? gel(T,3): NULL;
    1867        1603 :       S->dT = NULL;
    1868        1603 :       S->r1 = -1; break;
    1869          21 :     default: /* -1 */
    1870          21 :       pari_err_TYPE("nfinit_basic", T);
    1871             :   }
    1872        1631 :   S->dTP = S->dTE = S->dKE = NULL;
    1873        1631 :   S->unscale = gen_1;
    1874             : }
    1875             : 
    1876             : GEN
    1877       19421 : nfinit_complete(nfmaxord_t *S, long flag, long prec)
    1878             : {
    1879             :   GEN nf, unscale;
    1880             : 
    1881       19421 :   if (!ZX_is_irred(S->T)) pari_err_IRREDPOL("nfinit",S->T);
    1882       19421 :   if (!(flag & nf_RED) && !ZX_is_monic(S->T0))
    1883             :   {
    1884          56 :     pari_warn(warner,"non-monic polynomial. Result of the form [nf,c]");
    1885          56 :     flag |= nf_RED | nf_ORIG;
    1886             :   }
    1887       19421 :   unscale = S->unscale;
    1888       19421 :   if (!(flag & nf_RED) && !isint1(unscale))
    1889             :   { /* implies lc(x0) = 1 and L := 1/unscale is integral */
    1890         308 :     long d = degpol(S->T0);
    1891         308 :     GEN L = ginv(unscale); /* x = L^(-deg(x)) x0(L X) */
    1892         308 :     GEN f= powiu(L, (d*(d-1)) >> 1);
    1893         308 :     S->T = S->T0; /* restore original user-supplied x0, unscale data */
    1894         308 :     S->unscale = gen_1;
    1895         308 :     S->dT    = gmul(S->dT, sqri(f));
    1896         308 :     S->basis   = RgXV_unscale(S->basis, unscale);
    1897         308 :     S->index = gmul(S->index, f);
    1898             :   }
    1899       19421 :   nfmaxord_complete(S); /* more expensive after set_LLL_basis */
    1900       19421 :   if (flag & nf_RED)
    1901             :   {
    1902             :     GEN ro, rev;
    1903             :     /* lie to polred: more efficient to update *after* modreverse, than to
    1904             :      * unscale in the polred subsystem */
    1905         287 :     S->unscale = gen_1;
    1906         287 :     rev = nfpolred(S, &ro);
    1907         287 :     nf = nfmaxord_to_nf(S, ro, prec);
    1908         287 :     if (flag & nf_ORIG)
    1909             :     {
    1910          77 :       if (!rev) rev = pol_x(varn(S->T)); /* no improvement */
    1911          77 :       if (!isint1(unscale)) rev = RgX_Rg_div(rev, unscale);
    1912          77 :       nf = mkvec2(nf, mkpolmod(rev, S->T));
    1913             :     }
    1914         287 :     S->unscale = unscale; /* restore */
    1915             :   } else {
    1916       19134 :     GEN ro; set_LLL_basis(S, &ro, 0.99);
    1917       19133 :     nf = nfmaxord_to_nf(S, ro, prec);
    1918             :   }
    1919       19421 :   return nf;
    1920             : }
    1921             : /* Initialize the number field defined by the polynomial x (in variable v)
    1922             :  * flag & nf_RED:     try a polred first.
    1923             :  * flag & nf_ORIG
    1924             :  *    do a polred and return [nfinit(x), Mod(a,red)], where
    1925             :  *    Mod(a,red) = Mod(v,x) (i.e return the base change). */
    1926             : GEN
    1927        5330 : nfinitall(GEN x, long flag, long prec)
    1928             : {
    1929        5330 :   const pari_sp av = avma;
    1930             :   nfmaxord_t S;
    1931             :   GEN nf;
    1932             : 
    1933        5330 :   if (checkrnf_i(x)) return rnf_build_nfabs(x, prec);
    1934        5323 :   nfinit_basic(&S, x);
    1935        5302 :   nf = nfinit_complete(&S, flag, prec);
    1936        5302 :   return gerepilecopy(av, nf);
    1937             : }
    1938             : 
    1939             : GEN
    1940           0 : nfinitred(GEN x, long prec)  { return nfinitall(x, nf_RED, prec); }
    1941             : GEN
    1942           0 : nfinitred2(GEN x, long prec) { return nfinitall(x, nf_RED|nf_ORIG, prec); }
    1943             : GEN
    1944        2446 : nfinit(GEN x, long prec)     { return nfinitall(x, 0, prec); }
    1945             : 
    1946             : GEN
    1947        2884 : nfinit0(GEN x, long flag,long prec)
    1948             : {
    1949        2884 :   switch(flag)
    1950             :   {
    1951        2667 :     case 0:
    1952        2667 :     case 1: return nfinitall(x,0,prec);
    1953         196 :     case 2: case 4: return nfinitall(x,nf_RED,prec);
    1954          21 :     case 3: case 5: return nfinitall(x,nf_RED|nf_ORIG,prec);
    1955           0 :     default: pari_err_FLAG("nfinit");
    1956             :   }
    1957             :   return NULL; /* LCOV_EXCL_LINE */
    1958             : }
    1959             : 
    1960             : /* assume x a bnr/bnf/nf */
    1961             : long
    1962      306046 : nf_get_prec(GEN x)
    1963             : {
    1964      306046 :   GEN nf = checknf(x), ro = nf_get_roots(nf);
    1965      306046 :   return (typ(ro)==t_VEC)? precision(gel(ro,1)): DEFAULTPREC;
    1966             : }
    1967             : 
    1968             : /* true nf */
    1969             : GEN
    1970        1525 : nfnewprec_shallow(GEN nf, long prec)
    1971             : {
    1972        1525 :   GEN m, NF = leafcopy(nf);
    1973             :   nffp_t F;
    1974             : 
    1975        1525 :   F.T  = nf_get_pol(nf);
    1976        1525 :   F.ro = NULL;
    1977        1525 :   F.r1 = nf_get_r1(nf);
    1978        1525 :   F.basden = nf_basden(nf);
    1979        1525 :   F.extraprec = -1;
    1980        1525 :   F.prec = prec; make_M_G(&F, 1);
    1981        1525 :   gel(NF,5) = m = leafcopy(gel(NF,5));
    1982        1525 :   gel(m,1) = F.M;
    1983        1525 :   gel(m,2) = F.G;
    1984        1525 :   gel(NF,6) = F.ro; return NF;
    1985             : }
    1986             : 
    1987             : GEN
    1988          70 : nfnewprec(GEN nf, long prec)
    1989             : {
    1990             :   GEN z;
    1991          70 :   switch(nftyp(nf))
    1992             :   {
    1993          49 :     default: pari_err_TYPE("nfnewprec", nf);
    1994          14 :     case typ_BNF: z = bnfnewprec(nf,prec); break;
    1995           7 :     case typ_BNR: z = bnrnewprec(nf,prec); break;
    1996           0 :     case typ_NF: {
    1997           0 :       pari_sp av = avma;
    1998           0 :       z = gerepilecopy(av, nfnewprec_shallow(checknf(nf), prec));
    1999           0 :       break;
    2000             :     }
    2001             :   }
    2002          21 :   return z;
    2003             : }
    2004             : 
    2005             : /********************************************************************/
    2006             : /**                                                                **/
    2007             : /**                           POLRED                               **/
    2008             : /**                                                                **/
    2009             : /********************************************************************/
    2010             : GEN
    2011           0 : embednorm_T2(GEN x, long r1)
    2012             : {
    2013           0 :   pari_sp av = avma;
    2014           0 :   GEN p = RgV_sumpart(x, r1);
    2015           0 :   GEN q = RgV_sumpart2(x,r1+1, lg(x)-1);
    2016           0 :   if (q != gen_0) p = gadd(p, gmul2n(q,1));
    2017           0 :   return avma == av? gcopy(p): gerepileupto(av, p);
    2018             : }
    2019             : 
    2020             : /* simplified version of gnorm for scalar, non-complex inputs, without GC */
    2021             : static GEN
    2022       12054 : real_norm(GEN x)
    2023             : {
    2024       12054 :   switch(typ(x))
    2025             :   {
    2026           0 :     case t_INT:  return sqri(x);
    2027       12054 :     case t_REAL: return sqrr(x);
    2028           0 :     case t_FRAC: return sqrfrac(x);
    2029             :   }
    2030           0 :   pari_err_TYPE("real_norm", x);
    2031             :   return NULL;/*LCOV_EXCL_LINE*/
    2032             : }
    2033             : /* simplified version of gnorm, without GC */
    2034             : static GEN
    2035     4484564 : complex_norm(GEN x)
    2036             : {
    2037     4484564 :   return typ(x) == t_COMPLEX? cxnorm(x): real_norm(x);
    2038             : }
    2039             : /* return T2(x), argument r1 needed in case x has components whose type
    2040             :  * is unexpected, e.g. all of them t_INT for embed(gen_1) */
    2041             : GEN
    2042        3634 : embed_T2(GEN x, long r1)
    2043             : {
    2044        3634 :   pari_sp av = avma;
    2045        3634 :   long i, l = lg(x);
    2046        3634 :   GEN c, s = NULL, t = NULL;
    2047        3634 :   if (typ(gel(x,1)) == t_INT) return muliu(gel(x,1), 2*(l-1)-r1);
    2048       15688 :   for (i = 1; i <= r1; i++)
    2049             :   {
    2050       12054 :     c = real_norm(gel(x,i));
    2051       12054 :     s = s? gadd(s, c): c;
    2052             :   }
    2053       13303 :   for (; i < l; i++)
    2054             :   {
    2055        9669 :     c = complex_norm(gel(x,i));
    2056        9669 :     t = t? gadd(t, c): c;
    2057             :   }
    2058        3634 :   if (t) { t = gmul2n(t,1); s = s? gadd(s,t): t; }
    2059        3634 :   return gerepileupto(av, s);
    2060             : }
    2061             : /* return N(x) */
    2062             : GEN
    2063     3159122 : embed_norm(GEN x, long r1)
    2064             : {
    2065     3159122 :   pari_sp av = avma;
    2066     3159122 :   long i, l = lg(x);
    2067     3159122 :   GEN c, s = NULL, t = NULL;
    2068     3159122 :   if (typ(gel(x,1)) == t_INT) return powiu(gel(x,1), 2*(l-1)-r1);
    2069     7803463 :   for (i = 1; i <= r1; i++)
    2070             :   {
    2071     4649552 :     c = gel(x,i);
    2072     4649552 :     s = s? gmul(s, c): c;
    2073             :   }
    2074     7628806 :   for (; i < l; i++)
    2075             :   {
    2076     4474895 :     c = complex_norm(gel(x,i));
    2077     4474895 :     t = t? gmul(t, c): c;
    2078             :   }
    2079     3153911 :   if (t) s = s? gmul(s,t): t;
    2080     3153911 :   return gerepileupto(av, s);
    2081             : }
    2082             : 
    2083             : typedef struct {
    2084             :   long r1, v, prec;
    2085             :   GEN ZKembed; /* embeddings of fincke-pohst-reduced Zk basis */
    2086             :   GEN u; /* matrix giving fincke-pohst-reduced Zk basis */
    2087             :   GEN M; /* embeddings of initial (LLL-reduced) Zk basis */
    2088             :   GEN bound; /* T2 norm of the polynomial defining nf */
    2089             :   long expo_best_disc; /* expo(disc(x)), best generator so far */
    2090             : } CG_data;
    2091             : 
    2092             : /* characteristic pol of x (given by embeddings) */
    2093             : static GEN
    2094       58331 : get_pol(CG_data *d, GEN x)
    2095             : {
    2096             :   long e;
    2097       58331 :   GEN g = grndtoi(roots_to_pol_r1(x, d->v, d->r1), &e);
    2098       58331 :   return (e > -5)? NULL: g;
    2099             : }
    2100             : 
    2101             : /* characteristic pol of x (given as vector on (w_i)) */
    2102             : static GEN
    2103       32314 : get_polchar(CG_data *d, GEN x)
    2104       32314 : { return get_pol(d, RgM_RgC_mul(d->ZKembed,x)); }
    2105             : 
    2106             : /* Choose a canonical polynomial in the pair { Pmin_a, Pmin_{-a} }, i.e.
    2107             :  * { z(X), (-1)^(deg z) z(-Z) } and keeping the smallest wrt cmpii_polred
    2108             :  * Either leave z alone (return 1) or set z <- (-1)^n z(-X). In place. */
    2109             : static int
    2110       30517 : ZX_canon_neg(GEN z)
    2111             : {
    2112             :   long i, s;
    2113      119355 :   for (i = lg(z)-2; i >= 2; i -= 2)
    2114             :   { /* examine the odd (resp. even) part of z if deg(z) even (resp. odd). */
    2115      113433 :     s = signe(gel(z,i));
    2116      113433 :     if (!s) continue;
    2117             :     /* non trivial */
    2118       24595 :     if (s < 0) break; /* z(X) < (-1)^n z(-X) */
    2119             : 
    2120      103623 :     for (; i>=2; i-=2) gel(z,i) = negi(gel(z,i));
    2121       10762 :     return 1;
    2122             :   }
    2123       19755 :   return 0;
    2124             : }
    2125             : /* return a defining polynomial for Q(alpha), v = embeddings of alpha.
    2126             :  * Return NULL on failure: discriminant too large or non primitive */
    2127             : static GEN
    2128       36274 : try_polmin(CG_data *d, nfmaxord_t *S, GEN v, long flag, GEN *ai)
    2129             : {
    2130       36274 :   const long best = flag & nf_ABSOLUTE;
    2131             :   long ed;
    2132       36274 :   pari_sp av = avma;
    2133             :   GEN g;
    2134       36274 :   if (best)
    2135             :   {
    2136       35399 :     ed = expo(embed_disc(v, d->r1, LOWDEFAULTPREC));
    2137       35399 :     set_avma(av); if (d->expo_best_disc < ed) return NULL;
    2138             :   }
    2139             :   else
    2140         875 :     ed = 0;
    2141       20362 :   g = get_pol(d, v);
    2142             :   /* accuracy too low, compute algebraically */
    2143       20362 :   if (!g) { set_avma(av); g = ZXQ_charpoly(*ai, S->T, varn(S->T)); }
    2144       20362 :   g = ZX_radical(g);
    2145       20362 :   if (best && degpol(g) != degpol(S->T)) return gc_NULL(av);
    2146        7982 :   g = gerepilecopy(av, g);
    2147        7982 :   d->expo_best_disc = ed;
    2148        7982 :   if (flag & nf_ORIG)
    2149             :   {
    2150        3479 :     if (ZX_canon_neg(g)) *ai = RgX_neg(*ai);
    2151        3479 :     if (!isint1(S->unscale)) *ai = RgX_unscale(*ai, S->unscale);
    2152             :   }
    2153             :   else
    2154        4503 :     (void)ZX_canon_neg(g);
    2155        7982 :   if (DEBUGLEVEL>3) err_printf("polred: generator %Ps\n", g);
    2156        7982 :   return g;
    2157             : }
    2158             : 
    2159             : /* does x generate the correct field ? */
    2160             : static GEN
    2161       32314 : chk_gen(void *data, GEN x)
    2162             : {
    2163       32314 :   pari_sp av = avma, av1;
    2164       32314 :   GEN h, g = get_polchar((CG_data*)data,x);
    2165       32314 :   if (!g) pari_err_PREC("chk_gen");
    2166       32314 :   av1 = avma;
    2167       32314 :   h = ZX_gcd(g, ZX_deriv(g));
    2168       32314 :   if (degpol(h)) return gc_NULL(av);
    2169       22584 :   if (DEBUGLEVEL>3) err_printf("  generator: %Ps\n",g);
    2170       22584 :   set_avma(av1); return gerepileupto(av, g);
    2171             : }
    2172             : 
    2173             : static long
    2174        3220 : chk_gen_prec(long N, long bit)
    2175        3220 : { return nbits2prec(10 + (long)log2((double)N) + bit); }
    2176             : 
    2177             : /* v = [P,A] two vectors (of ZX and ZV resp.) of same length; remove duplicate
    2178             :  * polynomials in P, updating A, in place. Among elements having the same
    2179             :  * characteristic pol, choose the smallest according to ZV_abscmp */
    2180             : static void
    2181         861 : remove_duplicates(GEN v)
    2182             : {
    2183         861 :   GEN x, a, P = gel(v,1), A = gel(v,2);
    2184         861 :   long k, i, l = lg(P);
    2185         861 :   pari_sp av = avma;
    2186             : 
    2187         861 :   if (l < 2) return;
    2188         861 :   (void)sort_factor_pol(mkvec2(P, A), cmpii);
    2189         861 :   x = gel(P,1); a = gel(A,1);
    2190       21765 :   for  (k=1,i=2; i<l; i++)
    2191       20904 :     if (ZX_equal(gel(P,i), x))
    2192             :     {
    2193        4523 :       if (ZV_abscmp(gel(A,i), a) < 0) a = gel(A,i);
    2194             :     }
    2195             :     else
    2196             :     {
    2197       16381 :       gel(A,k) = a;
    2198       16381 :       gel(P,k) = x;
    2199       16381 :       k++;
    2200       16381 :       x = gel(P,i); a = gel(A,i);
    2201             :     }
    2202         861 :   l = k+1;
    2203         861 :   gel(A,k) = a; setlg(A,l);
    2204         861 :   gel(P,k) = x; setlg(P,l); set_avma(av);
    2205             : }
    2206             : 
    2207             : static void
    2208        2226 : polred_init(nfmaxord_t *S, nffp_t *F, CG_data *d)
    2209             : {
    2210        2226 :   long e, prec, n = degpol(S->T);
    2211             :   double log2rho;
    2212             :   GEN ro;
    2213        2226 :   set_LLL_basis(S, &ro, 0.9999);
    2214             :   /* || polchar ||_oo < 2^e ~ 2 (n * rho)^n, rho = max modulus of root */
    2215        2226 :   log2rho = ro ? (double)gexpo(ro): fujiwara_bound(S->T);
    2216        2226 :   e = n * (long)(log2rho + log2((double)n)) + 1;
    2217        2226 :   if (e < 0) e = 0; /* can occur if n = 1 */
    2218        2226 :   prec = chk_gen_prec(n, e);
    2219        2226 :   nffp_init(F,S,prec);
    2220        2226 :   F->ro = ro;
    2221        2226 :   make_M_G(F, 1);
    2222             : 
    2223        2226 :   d->v = varn(S->T);
    2224        2226 :   d->expo_best_disc = -1;
    2225        2226 :   d->ZKembed = NULL;
    2226        2226 :   d->M = NULL;
    2227        2226 :   d->u = NULL;
    2228        2226 :   d->r1= S->r1;
    2229        2226 : }
    2230             : static GEN
    2231        1001 : findmindisc(GEN y)
    2232             : {
    2233        1001 :   GEN x = gel(y,1), dx = NULL;
    2234        1001 :   long i, l = lg(y);
    2235       15898 :   for (i = 2; i < l; i++)
    2236             :   {
    2237       14897 :     GEN yi = gel(y,i);
    2238       14897 :     if (ZX_is_better(yi,x,&dx)) x = yi;
    2239             :   }
    2240        1001 :   return x;
    2241             : }
    2242             : /* filter [y,b] from polred_aux: keep a single polynomial of degree n in y
    2243             :  * [ the best wrt discriminant ordering ], but keep all non-primitive
    2244             :  * polynomials */
    2245             : static void
    2246        1232 : filter(GEN y, GEN b, long n)
    2247             : {
    2248             :   GEN x, a, dx;
    2249        1232 :   long i, k = 1, l = lg(y);
    2250        1232 :   a = x = dx = NULL;
    2251        9277 :   for (i = 1; i < l; i++)
    2252             :   {
    2253        8045 :     GEN yi = gel(y,i), ai = gel(b,i);
    2254        8045 :     if (degpol(yi) == n)
    2255             :     {
    2256        7877 :       pari_sp av = avma;
    2257        7877 :       if (!dx) dx = ZX_disc(yi);
    2258        6645 :       else if (!ZX_is_better(yi,x,&dx)) { set_avma(av); continue; }
    2259        1883 :       x = yi; a = ai; continue;
    2260             :     }
    2261         168 :     gel(y,k) = yi;
    2262         168 :     gel(b,k) = ai; k++;
    2263             :   }
    2264        1232 :   if (dx)
    2265             :   {
    2266        1232 :     gel(y,k) = x;
    2267        1232 :     gel(b,k) = a; k++;
    2268             :   }
    2269        1232 :   setlg(y, k);
    2270        1232 :   setlg(b, k);
    2271        1232 : }
    2272             : 
    2273             : static GEN
    2274        1260 : polred_aux(nfmaxord_t *S, GEN *pro, long flag)
    2275             : { /* only keep polynomials of max degree and best discriminant */
    2276        1260 :   const long best = flag & nf_ABSOLUTE;
    2277        1260 :   const long orig = flag & nf_ORIG;
    2278        1260 :   GEN M, b, y, x = S->T;
    2279        1260 :   long maxi, i, j, k, v = varn(x), n = lg(S->basis)-1;
    2280             :   nffp_t F;
    2281             :   CG_data d;
    2282             : 
    2283        1260 :   if (n == 1)
    2284             :   {
    2285          28 :     if (!best)
    2286             :     {
    2287          14 :       GEN X = pol_x(v);
    2288          14 :       return orig? mkmat2(mkcol(X),mkcol(gen_1)): mkvec(X);
    2289             :     }
    2290             :     else
    2291          14 :       return orig? trivial_fact(): cgetg(1,t_VEC);
    2292             :   }
    2293             : 
    2294        1232 :   polred_init(S, &F, &d);
    2295        1232 :   if (pro) *pro = F.ro;
    2296        1232 :   M = F.M;
    2297        1232 :   if (best)
    2298             :   {
    2299        1169 :     if (!S->dT) S->dT = ZX_disc(S->T);
    2300        1169 :     d.expo_best_disc = expi(S->dT);
    2301             :   }
    2302             : 
    2303             :   /* n + 2 sum_{1 <= i <= n} n-i = n + n(n-1) = n*n */
    2304        1232 :   y = cgetg(n*n + 1, t_VEC);
    2305        1232 :   b = cgetg(n*n + 1, t_COL);
    2306        1232 :   k = 1;
    2307        1232 :   if (!best) { gel(y,1) = pol_x(v); gel(b,1) = gen_0; k++; }
    2308        7392 :   for (i = 2; i <= n; i++)
    2309             :   {
    2310             :     GEN ch, ai;
    2311        6160 :     ai = gel(S->basis,i);
    2312        6160 :     ch = try_polmin(&d, S, gel(M,i), flag, &ai);
    2313        6160 :     if (ch) { gel(y,k) = ch; gel(b,k) = ai; k++; }
    2314             :   }
    2315        1232 :   maxi = minss(n, 3);
    2316        4655 :   for (i = 1; i <= maxi; i++)
    2317       18480 :     for (j = i+1; j <= n; j++)
    2318             :     {
    2319             :       GEN ch, ai, v;
    2320       15057 :       ai = gadd(gel(S->basis,i), gel(S->basis,j));
    2321       15057 :       v = RgV_add(gel(M,i), gel(M,j));
    2322             :       /* defining polynomial for Q(w_i+w_j) */
    2323       15057 :       ch = try_polmin(&d, S, v, flag, &ai);
    2324       15057 :       if (ch) { gel(y,k) = ch; gel(b,k) = ai; k++; }
    2325             : 
    2326       15057 :       ai = gsub(gel(S->basis,i), gel(S->basis,j));
    2327       15057 :       v = RgV_sub(gel(M,i), gel(M,j));
    2328             :       /* defining polynomial for Q(w_i-w_j) */
    2329       15057 :       ch = try_polmin(&d, S, v, flag, &ai);
    2330       15057 :       if (ch) { gel(y,k) = ch; gel(b,k) = ai; k++; }
    2331             :     }
    2332        1232 :   setlg(y, k);
    2333        1232 :   setlg(b, k); filter(y, b, n);
    2334        1232 :   if (!orig) return gen_sort_uniq(y, (void*)cmpii, &gen_cmp_RgX);
    2335         525 :   settyp(y, t_COL);
    2336         525 :   (void)sort_factor_pol(mkmat2(y, b), cmpii);
    2337         525 :   return mkmat2(b, y);
    2338             : }
    2339             : 
    2340             : /* FIXME: obsolete */
    2341             : static GEN
    2342          84 : Polred(GEN x, long flag, GEN fa)
    2343             : {
    2344          84 :   pari_sp av = avma;
    2345             :   nfmaxord_t S;
    2346          84 :   if (fa)
    2347          14 :     nfinit_basic(&S, mkvec2(x,fa));
    2348          70 :   else if (flag & nf_PARTIALFACT)
    2349          28 :     nfinit_basic_partial(&S, x);
    2350             :   else
    2351          42 :     nfinit_basic(&S, x);
    2352          77 :   return gerepilecopy(av, polred_aux(&S, NULL, flag));
    2353             : }
    2354             : 
    2355             : /* finds "best" polynomial in polred_aux list, defaulting to S->T if none of
    2356             :  * them is primitive. *px is the ZX, characteristic polynomial of Mod(*pb,S->T),
    2357             :  * *pdx its discriminant if pdx != NULL. Set *pro = polroots(S->T) */
    2358             : static void
    2359        1183 : polredbest_aux(nfmaxord_t *S, GEN *pro, GEN *px, GEN *pdx, GEN *pb)
    2360             : {
    2361        1183 :   GEN y, dx, x = S->T; /* default value */
    2362             :   long i, l;
    2363        1183 :   y = polred_aux(S, pro, pb? nf_ORIG|nf_ABSOLUTE: nf_ABSOLUTE);
    2364        1183 :   dx = S->dT;
    2365        1183 :   if (pb)
    2366             :   {
    2367         511 :     GEN a, b = deg1pol_shallow(S->unscale, gen_0, varn(x));
    2368         511 :     a = gel(y,1); l = lg(a);
    2369         511 :     y = gel(y,2);
    2370        1015 :     for (i=1; i<l; i++)
    2371             :     {
    2372         504 :       GEN yi = gel(y,i);
    2373         504 :       pari_sp av = avma;
    2374         504 :       if (ZX_is_better(yi,x,&dx)) { x = yi; b = gel(a,i); } else set_avma(av);
    2375             :     }
    2376         511 :     *pb = b;
    2377             :   }
    2378             :   else
    2379             :   {
    2380         672 :     l = lg(y);
    2381        1337 :     for (i=1; i<l; i++)
    2382             :     {
    2383         665 :       GEN yi = gel(y,i);
    2384         665 :       pari_sp av = avma;
    2385         665 :       if (ZX_is_better(yi,x,&dx)) x = yi; else set_avma(av);
    2386             :     }
    2387             :   }
    2388        1183 :   if (pdx) { if (!dx) dx = ZX_disc(x); *pdx = dx; }
    2389        1183 :   *px = x;
    2390        1183 : }
    2391             : static GEN
    2392         994 : polredbest_i(GEN T0, long flag)
    2393             : {
    2394         994 :   GEN T = T0, a;
    2395             :   nfmaxord_t S;
    2396         994 :   nfinit_basic_partial(&S, T);
    2397         994 :   polredbest_aux(&S, NULL, &T, NULL, flag? &a: NULL);
    2398         994 :   if (flag == 2)
    2399         294 :     T = mkvec2(T, a);
    2400         700 :   else if (flag == 1)
    2401             :   {
    2402          28 :     GEN b = (T0 == T)? pol_x(varn(T)): QXQ_reverse(a, T0);
    2403             :     /* charpoly(Mod(a,T0)) = T; charpoly(Mod(b,T)) = S.x */
    2404          28 :     if (degpol(T) == 1) b = grem(b,T);
    2405          28 :     T = mkvec2(T, mkpolmod(b,T));
    2406             :   }
    2407         994 :   return T;
    2408             : }
    2409             : GEN
    2410         693 : polredbest(GEN T, long flag)
    2411             : {
    2412         693 :   pari_sp av = avma;
    2413         693 :   if (flag < 0 || flag > 1) pari_err_FLAG("polredbest");
    2414         693 :   return gerepilecopy(av, polredbest_i(T, flag));
    2415             : }
    2416             : /* DEPRECATED: backward compatibility */
    2417             : GEN
    2418          70 : polred0(GEN x, long flag, GEN fa)
    2419             : {
    2420          70 :   long fl = 0;
    2421          70 :   if (flag & 1) fl |= nf_PARTIALFACT;
    2422          70 :   if (flag & 2) fl |= nf_ORIG;
    2423          70 :   return Polred(x, fl, fa);
    2424             : }
    2425             : 
    2426             : GEN
    2427          21 : polredord(GEN x)
    2428             : {
    2429          21 :   pari_sp av = avma;
    2430             :   GEN v, lt;
    2431             :   long i, n, vx;
    2432             : 
    2433          21 :   if (typ(x) != t_POL) pari_err_TYPE("polredord",x);
    2434          21 :   x = Q_primpart(x); RgX_check_ZX(x,"polredord");
    2435          21 :   n = degpol(x); if (n <= 0) pari_err_CONSTPOL("polredord");
    2436          21 :   if (n == 1) return gerepilecopy(av, mkvec(x));
    2437          14 :   lt = leading_coeff(x); vx = varn(x);
    2438          14 :   if (is_pm1(lt))
    2439             :   {
    2440           7 :     if (signe(lt) < 0) x = ZX_neg(x);
    2441           7 :     v = pol_x_powers(n, vx);
    2442             :   }
    2443             :   else
    2444             :   { GEN L;
    2445             :     /* basis for Dedekind order */
    2446           7 :     v = cgetg(n+1, t_VEC);
    2447           7 :     gel(v,1) = scalarpol_shallow(lt, vx);
    2448          14 :     for (i = 2; i <= n; i++)
    2449           7 :       gel(v,i) = RgX_Rg_add(RgX_mulXn(gel(v,i-1), 1), gel(x,n+3-i));
    2450           7 :     gel(v,1) = pol_1(vx);
    2451           7 :     x = ZX_Q_normalize(x, &L);
    2452           7 :     v = gsubst(v, vx, monomial(ginv(L),1,vx));
    2453          14 :     for (i=2; i <= n; i++)
    2454           7 :       if (Q_denom(gel(v,i)) == gen_1) gel(v,i) = pol_xn(i-1, vx);
    2455             :   }
    2456          14 :   return gerepileupto(av, polred(mkvec2(x, v)));
    2457             : }
    2458             : 
    2459             : GEN
    2460          14 : polred(GEN x) { return Polred(x, 0, NULL); }
    2461             : GEN
    2462           0 : smallpolred(GEN x) { return Polred(x, nf_PARTIALFACT, NULL); }
    2463             : GEN
    2464           0 : factoredpolred(GEN x, GEN fa) { return Polred(x, 0, fa); }
    2465             : GEN
    2466           0 : polred2(GEN x) { return Polred(x, nf_ORIG, NULL); }
    2467             : GEN
    2468           0 : smallpolred2(GEN x) { return Polred(x, nf_PARTIALFACT|nf_ORIG, NULL); }
    2469             : GEN
    2470           0 : factoredpolred2(GEN x, GEN fa) { return Polred(x, nf_PARTIALFACT, fa); }
    2471             : 
    2472             : /********************************************************************/
    2473             : /**                                                                **/
    2474             : /**                           POLREDABS                            **/
    2475             : /**                                                                **/
    2476             : /********************************************************************/
    2477             : /* set V[k] := matrix of multiplication by nk.zk[k] */
    2478             : static GEN
    2479        2793 : set_mulid(GEN V, GEN M, GEN Mi, long r1, long r2, long N, long k)
    2480             : {
    2481        2793 :   GEN v, Mk = cgetg(N+1, t_MAT);
    2482             :   long i, e;
    2483        7553 :   for (i = 1; i < k; i++) gel(Mk,i) = gmael(V, i, k);
    2484       21399 :   for (     ; i <=N; i++)
    2485             :   {
    2486       18606 :     v = vecmul(gel(M,k), gel(M,i));
    2487       18606 :     v = RgM_RgC_mul(Mi, split_realimag(v, r1, r2));
    2488       18606 :     gel(Mk,i) = grndtoi(v, &e);
    2489       18606 :     if (e > -5) return NULL;
    2490             :   }
    2491        2793 :   gel(V,k) = Mk; return Mk;
    2492             : }
    2493             : 
    2494             : static GEN
    2495        2582 : ZM_image_shallow(GEN M, long *pr)
    2496             : {
    2497             :   long j, k, r;
    2498        2582 :   GEN y, d = ZM_pivots(M, &k);
    2499        2582 :   r = lg(M)-1 - k;
    2500        2582 :   y = cgetg(r+1,t_MAT);
    2501       16884 :   for (j=k=1; j<=r; k++)
    2502       14302 :     if (d[k]) gel(y,j++) = gel(M,k);
    2503        2582 :   *pr = r; return y;
    2504             : }
    2505             : 
    2506             : /* U = base change matrix, R = Cholesky form of the quadratic form [matrix
    2507             :  * Q from algo 2.7.6] */
    2508             : static GEN
    2509        1002 : chk_gen_init(FP_chk_fun *chk, GEN R, GEN U)
    2510             : {
    2511        1002 :   CG_data *d = (CG_data*)chk->data;
    2512             :   GEN P, V, D, inv, bound, S, M;
    2513        1002 :   long N = lg(U)-1, r1 = d->r1, r2 = (N-r1)>>1;
    2514        1002 :   long i, j, prec, firstprim = 0, skipfirst = 0;
    2515             :   pari_sp av;
    2516             : 
    2517        1002 :   d->u = U;
    2518        1002 :   d->ZKembed = M = RgM_mul(d->M, U);
    2519             : 
    2520        1002 :   av = avma; bound = d->bound;
    2521        1002 :   D = cgetg(N+1, t_VECSMALL);
    2522        6625 :   for (i = 1; i <= N; i++)
    2523             :   {
    2524        5631 :     pari_sp av2 = avma;
    2525        5631 :     P = get_pol(d, gel(M,i));
    2526        5631 :     if (!P) pari_err_PREC("chk_gen_init");
    2527        5623 :     P = gerepilecopy(av2, ZX_radical(P));
    2528        5623 :     D[i] = degpol(P);
    2529        5623 :     if (D[i] == N)
    2530             :     { /* primitive element */
    2531        2430 :       GEN B = embed_T2(gel(M,i), r1);
    2532        2430 :       if (!firstprim) firstprim = i; /* index of first primitive element */
    2533        2430 :       if (DEBUGLEVEL>2) err_printf("chk_gen_init: generator %Ps\n",P);
    2534        2430 :       if (gcmp(B,bound) < 0) bound = gerepileuptoleaf(av2, B);
    2535             :     }
    2536             :     else
    2537             :     {
    2538        3193 :       if (DEBUGLEVEL>2) err_printf("chk_gen_init: subfield %Ps\n",P);
    2539        3193 :       if (firstprim)
    2540             :       { /* cycle basis vectors so that primitive elements come last */
    2541         392 :         GEN u = d->u, e = M;
    2542         392 :         GEN te = gel(e,i), tu = gel(u,i), tR = gel(R,i);
    2543         392 :         long tS = D[i];
    2544        1077 :         for (j = i; j > firstprim; j--)
    2545             :         {
    2546         685 :           u[j] = u[j-1];
    2547         685 :           e[j] = e[j-1];
    2548         685 :           R[j] = R[j-1];
    2549         685 :           D[j] = D[j-1];
    2550             :         }
    2551         392 :         gel(u,firstprim) = tu;
    2552         392 :         gel(e,firstprim) = te;
    2553         392 :         gel(R,firstprim) = tR;
    2554         392 :         D[firstprim] = tS; firstprim++;
    2555             :       }
    2556             :     }
    2557             :   }
    2558         994 :   if (!firstprim)
    2559             :   { /* try (a little) to find primitive elements to improve bound */
    2560          21 :     GEN x = cgetg(N+1, t_VECSMALL);
    2561          21 :     if (DEBUGLEVEL>1)
    2562           0 :       err_printf("chk_gen_init: difficult field, trying random elements\n");
    2563         231 :     for (i = 0; i < 10; i++)
    2564             :     {
    2565             :       GEN e, B;
    2566        2310 :       for (j = 1; j <= N; j++) x[j] = (long)random_Fl(7) - 3;
    2567         210 :       e = RgM_zc_mul(M, x);
    2568         210 :       B = embed_T2(e, r1);
    2569         210 :       if (gcmp(B,bound) >= 0) continue;
    2570          24 :       P = get_pol(d, e); if (!P) pari_err_PREC( "chk_gen_init");
    2571          24 :       if (!ZX_is_squarefree(P)) continue;
    2572          24 :       if (DEBUGLEVEL>2) err_printf("chk_gen_init: generator %Ps\n",P);
    2573          24 :       bound = B ;
    2574             :     }
    2575             :   }
    2576             : 
    2577         994 :   if (firstprim != 1)
    2578             :   {
    2579         994 :     inv = ginv( split_realimag(M, r1, r2) ); /*TODO: use QR?*/
    2580         994 :     V = gel(inv,1);
    2581        3423 :     for (i = 2; i <= r1+r2; i++) V = gadd(V, gel(inv,i));
    2582             :     /* V corresponds to 1_Z */
    2583         994 :     V = grndtoi(V, &j);
    2584         994 :     if (j > -5) pari_err_BUG("precision too low in chk_gen_init");
    2585         994 :     S = mkmat(V); /* 1 */
    2586             : 
    2587         994 :     V = cgetg(N+1, t_VEC);
    2588        3325 :     for (i = 1; i <= N; i++,skipfirst++)
    2589             :     { /* S = Q-basis of subfield generated by nf.zk[1..i-1] */
    2590             :       GEN Mx, M2;
    2591        3325 :       long j, k, h, rkM, dP = D[i];
    2592             : 
    2593        3325 :       if (dP == N) break; /* primitive */
    2594        2793 :       Mx = set_mulid(V, M, inv, r1, r2, N, i);
    2595        2793 :       if (!Mx) break; /* prec. problem. Stop */
    2596        2793 :       if (dP == 1) continue;
    2597        1939 :       rkM = lg(S)-1;
    2598        1939 :       M2 = cgetg(N+1, t_MAT); /* we will add to S the elts of M2 */
    2599        1939 :       gel(M2,1) = col_ei(N, i); /* nf.zk[i] */
    2600        1939 :       k = 2;
    2601        3234 :       for (h = 1; h < dP; h++)
    2602             :       {
    2603             :         long r; /* add to M2 the elts of S * nf.zk[i]  */
    2604       11921 :         for (j = 1; j <= rkM; j++) gel(M2,k++) = ZM_ZC_mul(Mx, gel(S,j));
    2605        2582 :         setlg(M2, k); k = 1;
    2606        2582 :         S = ZM_image_shallow(shallowconcat(S,M2), &r);
    2607        3044 :         if (r == rkM) break;
    2608        1757 :         if (r > rkM)
    2609             :         {
    2610        1757 :           rkM = r;
    2611        1757 :           if (rkM == N) break;
    2612             :         }
    2613             :       }
    2614        1939 :       if (rkM == N) break;
    2615             :       /* Q(w[1],...,w[i-1]) is a strict subfield of nf */
    2616             :     }
    2617             :   }
    2618             :   /* x_1,...,x_skipfirst generate a strict subfield [unless N=skipfirst=1] */
    2619         994 :   chk->skipfirst = skipfirst;
    2620         994 :   if (DEBUGLEVEL>2) err_printf("chk_gen_init: skipfirst = %ld\n",skipfirst);
    2621             : 
    2622             :   /* should be DEF + gexpo( max_k C^n_k (bound/k)^(k/2) ) */
    2623         994 :   bound = gerepileuptoleaf(av, bound);
    2624         994 :   prec = chk_gen_prec(N, (gexpo(bound)*N)/2);
    2625         994 :   if (DEBUGLEVEL)
    2626           0 :     err_printf("chk_gen_init: new prec = %ld (initially %ld)\n", prec, d->prec);
    2627         994 :   if (prec > d->prec) pari_err_BUG("polredabs (precision problem)");
    2628         994 :   if (prec < d->prec) d->ZKembed = gprec_w(M, prec);
    2629         994 :   return bound;
    2630             : }
    2631             : 
    2632             : static GEN
    2633        1008 : polredabs_i(GEN x, nfmaxord_t *S, GEN *u, long flag)
    2634             : {
    2635        1008 :   FP_chk_fun chk = { &chk_gen, &chk_gen_init, NULL, NULL, 0 };
    2636             :   nffp_t F;
    2637             :   CG_data d;
    2638             :   GEN v, y, a;
    2639             :   long i, l;
    2640             : 
    2641        1008 :   nfinit_basic_partial(S, x);
    2642        1008 :   x = S->T0;
    2643        1008 :   if (degpol(x) == 1)
    2644             :   {
    2645          14 :     long vx = varn(x);
    2646          14 :     *u = NULL;
    2647          14 :     return mkvec2(mkvec( pol_x(vx) ),
    2648          14 :                   mkvec( deg1pol_shallow(gen_1, negi(gel(S->T,2)), vx) ));
    2649             :   }
    2650         994 :   if (!(flag & nf_PARTIALFACT) && S->dK && S->dKP)
    2651             :   {
    2652         315 :     GEN vw = primes_certify(S->dK, S->dKP);
    2653         315 :     v = gel(vw,1); l = lg(v);
    2654         315 :     if (l != 1)
    2655             :     { /* fix integral basis */
    2656          14 :       GEN w = gel(vw,2);
    2657          28 :       for (i = 1; i < l; i++)
    2658          14 :         w = ZV_union_shallow(w, gel(Z_factor(gel(v,i)),1));
    2659          14 :       nfinit_basic(S, mkvec2(S->T0,w));
    2660             :     }
    2661             :   }
    2662             : 
    2663         994 :   chk.data = (void*)&d;
    2664         994 :   polred_init(S, &F, &d);
    2665         994 :   d.bound = embed_T2(F.ro, d.r1);
    2666         994 :   if (realprec(d.bound) > F.prec) d.bound = rtor(d.bound, F.prec);
    2667             :   for (;;)
    2668          20 :   {
    2669        1014 :     GEN R = R_from_QR(F.G, F.prec);
    2670        1014 :     if (R)
    2671             :     {
    2672        1002 :       d.prec = F.prec;
    2673        1002 :       d.M    = F.M;
    2674        1002 :       v = fincke_pohst(mkvec(R),NULL,-1, 0, &chk);
    2675        1002 :       if (v) break;
    2676             :     }
    2677          20 :     F.prec = precdbl(F.prec);
    2678          20 :     F.ro = NULL;
    2679          20 :     make_M_G(&F, 1);
    2680          20 :     if (DEBUGLEVEL) pari_warn(warnprec,"polredabs0",F.prec);
    2681             :   }
    2682         994 :   y = gel(v,1);
    2683         994 :   a = gel(v,2); l = lg(a);
    2684       23529 :   for (i = 1; i < l; i++) /* normalize wrt z -> -z */
    2685       22535 :     if (ZX_canon_neg(gel(y,i)) && (flag & (nf_ORIG|nf_RAW)))
    2686        1465 :       gel(a,i) = ZC_neg(gel(a,i));
    2687         994 :   *u = d.u; return v;
    2688             : }
    2689             : 
    2690             : GEN
    2691         861 : polredabs0(GEN x, long flag)
    2692             : {
    2693         861 :   pari_sp av = avma;
    2694             :   GEN Y, A, u, v;
    2695             :   nfmaxord_t S;
    2696             :   long i, l;
    2697             : 
    2698         861 :   v = polredabs_i(x, &S, &u, flag);
    2699         861 :   remove_duplicates(v);
    2700         861 :   Y = gel(v,1);
    2701         861 :   A = gel(v,2);
    2702         861 :   l = lg(A); if (l == 1) pari_err_BUG("polredabs (missing vector)");
    2703         861 :   if (DEBUGLEVEL) err_printf("Found %ld minimal polynomials.\n",l-1);
    2704         861 :   if (!(flag & nf_ALL))
    2705             :   {
    2706         854 :     GEN y = findmindisc(Y);
    2707       11712 :     for (i = 1; i < l; i++)
    2708       11712 :       if (ZX_equal(gel(Y,i), y)) break;
    2709         854 :     Y = mkvec(gel(Y,i));
    2710         854 :     A = mkvec(gel(A,i)); l = 2;
    2711             :   }
    2712        1596 :   if (flag & (nf_RAW|nf_ORIG)) for (i = 1; i < l; i++)
    2713             :   {
    2714         735 :     GEN y = gel(Y,i), a = gel(A,i);
    2715         735 :     if (u) a = RgV_RgC_mul(S.basis, ZM_ZC_mul(u, a));
    2716         735 :     if (flag & nf_ORIG)
    2717             :     {
    2718         728 :       a = QXQ_reverse(a, S.T);
    2719         728 :       if (!isint1(S.unscale)) a = gdiv(a, S.unscale); /* not RgX_Rg_div */
    2720         728 :       a = mkpolmod(a,y);
    2721             :     }
    2722         735 :     gel(Y,i) = mkvec2(y, a);
    2723             :   }
    2724         861 :   return gerepilecopy(av, (flag & nf_ALL)? Y: gel(Y,1));
    2725             : }
    2726             : 
    2727             : GEN
    2728           0 : polredabsall(GEN x, long flun) { return polredabs0(x, flun | nf_ALL); }
    2729             : GEN
    2730           0 : polredabs(GEN x) { return polredabs0(x,0); }
    2731             : GEN
    2732           0 : polredabs2(GEN x) { return polredabs0(x,nf_ORIG); }
    2733             : 
    2734             : /* relative polredabs/best. Returns relative polynomial by default (flag = 0)
    2735             :  * flag & nf_ORIG: + element (base change)
    2736             :  * flag & nf_ABSOLUTE: absolute polynomial */
    2737             : static GEN
    2738         455 : rnfpolred_i(GEN nf, GEN R, long flag, long best)
    2739             : {
    2740         455 :   const char *f = best? "rnfpolredbest": "rnfpolredabs";
    2741         455 :   const long abs = ((flag & nf_ORIG) && (flag & nf_ABSOLUTE));
    2742         455 :   GEN listP = NULL, red, pol, A, P, T, rnfeq;
    2743         455 :   pari_sp av = avma;
    2744             : 
    2745         455 :   if (typ(R) == t_VEC) {
    2746          14 :     if (lg(R) != 3) pari_err_TYPE(f,R);
    2747          14 :     listP = gel(R,2);
    2748          14 :     R = gel(R,1);
    2749             :   }
    2750         455 :   if (typ(R) != t_POL) pari_err_TYPE(f,R);
    2751         455 :   nf = checknf(nf);
    2752         455 :   T = nf_get_pol(nf);
    2753         455 :   R = RgX_nffix(f, T, R, 0);
    2754         455 :   if (best || (flag & nf_PARTIALFACT))
    2755             :   {
    2756         308 :     rnfeq = abs? nf_rnfeq(nf, R): nf_rnfeqsimple(nf, R);
    2757         308 :     pol = gel(rnfeq,1);
    2758         308 :     if (listP) pol = mkvec2(pol, listP);
    2759         301 :     red = best? polredbest_i(pol, abs? 1: 2)
    2760         308 :               : polredabs0(pol, (abs? nf_ORIG: nf_RAW)|nf_PARTIALFACT);
    2761         308 :     P = gel(red,1);
    2762         308 :     A = gel(red,2);
    2763             :   }
    2764             :   else
    2765             :   {
    2766             :     nfmaxord_t S;
    2767             :     GEN rnf, u, v, y, a;
    2768             :     long i, j, l;
    2769             :     pari_timer ti;
    2770         147 :     if (DEBUGLEVEL>1) timer_start(&ti);
    2771         147 :     rnf = rnfinit(nf, R);
    2772         147 :     rnfeq = rnf_get_map(rnf);
    2773         147 :     pol = rnf_zkabs(rnf);
    2774         147 :     if (DEBUGLEVEL>1) timer_printf(&ti, "absolute basis");
    2775         147 :     v = polredabs_i(pol, &S, &u, nf_ORIG);
    2776         147 :     pol = gel(pol,1);
    2777         147 :     y = gel(v,1); P = findmindisc(y);
    2778         147 :     a = gel(v,2);
    2779         147 :     l = lg(y); A = cgetg(l, t_VEC);
    2780         931 :     for (i = j = 1; i < l; i++)
    2781         784 :       if (ZX_equal(gel(y,i),P))
    2782             :       {
    2783         672 :         GEN t = gel(a,i);
    2784         672 :         if (u) t = RgV_RgC_mul(S.basis, ZM_ZC_mul(u,t));
    2785         672 :         gel(A,j++) = t;
    2786             :       }
    2787         147 :     setlg(A,j); /* mod(A[i], pol) are all roots of P in Q[X]/(pol) */
    2788             :   }
    2789         455 :   if (DEBUGLEVEL>1) err_printf("reduced absolute generator: %Ps\n",P);
    2790         455 :   if (flag & nf_ABSOLUTE)
    2791             :   {
    2792          14 :     if (flag & nf_ORIG)
    2793             :     {
    2794           7 :       GEN a = gel(rnfeq,2); /* Mod(a,pol) root of T */
    2795           7 :       GEN k = gel(rnfeq,3); /* Mod(variable(R),R) + k*a root of pol */
    2796           7 :       if (typ(A) == t_VEC) A = gel(A,1); /* any root will do */
    2797           7 :       a = RgX_RgXQ_eval(a, lift_shallow(A), P); /* Mod(a, P) root of T */
    2798           7 :       P = mkvec3(P, mkpolmod(a,P), gsub(A, gmul(k,a)));
    2799             :     }
    2800          14 :     return gerepilecopy(av, P);
    2801             :   }
    2802         441 :   if (typ(A) != t_VEC)
    2803             :   {
    2804         301 :     A = eltabstorel_lift(rnfeq, A);
    2805         301 :     P = lift_if_rational( RgXQ_charpoly(A, R, varn(R)) );
    2806             :   }
    2807             :   else
    2808             :   { /* canonical factor */
    2809         140 :     long i, l = lg(A), v = varn(R);
    2810         140 :     GEN besta = NULL;
    2811         770 :     for (i = 1; i < l; i++)
    2812             :     {
    2813         630 :       GEN a = eltabstorel_lift(rnfeq, gel(A,i));
    2814         630 :       GEN p = lift_if_rational( RgXQ_charpoly(a, R, v) );
    2815         630 :       p = lift_if_rational(p);
    2816         630 :       if (i == 1 || cmp_universal(p, P) < 0) { P = p; besta = a; }
    2817             :     }
    2818         140 :     A = besta;
    2819             :   }
    2820         441 :   if (flag & nf_ORIG) P = mkvec2(P, mkpolmod(RgXQ_reverse(A,R),P));
    2821         441 :   return gerepilecopy(av, P);
    2822             : }
    2823             : GEN
    2824         154 : rnfpolredabs(GEN nf, GEN R, long flag)
    2825         154 : { return rnfpolred_i(nf,R,flag, 0); }
    2826             : GEN
    2827         301 : rnfpolredbest(GEN nf, GEN R, long flag)
    2828             : {
    2829         301 :   if (flag < 0 || flag > 3) pari_err_FLAG("rnfpolredbest");
    2830         301 :   return rnfpolred_i(nf,R,flag, 1);
    2831             : }

Generated by: LCOV version 1.13