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-bordeaux1.fr machine (x86_64 architecture), and agregate them in the final report:

The target is 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 - base5.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.8.0 lcov report (development 16861-9aeb453) Lines: 557 584 95.4 %
Date: 2014-10-08 Functions: 51 51 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 250 314 79.6 %

           Branch data     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                 :            : /*                       BASIC NF OPERATIONS                       */
      17                 :            : /*                          (continued 2)                          */
      18                 :            : /*                                                                 */
      19                 :            : /*******************************************************************/
      20                 :            : #include "pari.h"
      21                 :            : #include "paripriv.h"
      22                 :            : 
      23                 :            : /* must return a t_POL */
      24                 :            : GEN
      25                 :       1092 : eltreltoabs(GEN rnfeq, GEN x)
      26                 :            : {
      27                 :            :   long i, k, v;
      28                 :       1092 :   pari_sp av = avma;
      29                 :            :   GEN T, pol, teta, a, s;
      30                 :            : 
      31                 :       1092 :   pol = gel(rnfeq,1);
      32                 :       1092 :   a = gel(rnfeq,2);
      33                 :       1092 :   k = itos(gel(rnfeq,3));
      34                 :       1092 :   T = gel(rnfeq,4);
      35                 :            : 
      36                 :       1092 :   v = varn(pol);
      37         [ +  + ]:       1092 :   if (varncmp(gvar(x), v) > 0) x = scalarpol(x,v);
      38                 :       1092 :   x = RgX_nffix("eltreltoabs", T, x, 1);
      39                 :            :   /* Mod(X - k a, pol(X)), a root of the polynomial defining base */
      40                 :       1085 :   teta = gadd(pol_x(v), gmulsg(-k,a));
      41                 :       1085 :   s = gen_0;
      42         [ +  + ]:       2968 :   for (i=lg(x)-1; i>1; i--)
      43                 :            :   {
      44                 :       1883 :     GEN c = gel(x,i);
      45         [ +  + ]:       1883 :     if (typ(c) == t_POL) c = RgX_RgXQ_eval(c, a, pol);
      46                 :       1883 :     s = RgX_rem(gadd(c, gmul(teta,s)), pol);
      47                 :            :   }
      48                 :       1085 :   return gerepileupto(av, s);
      49                 :            : }
      50                 :            : GEN
      51                 :        231 : rnfeltreltoabs(GEN rnf,GEN x)
      52                 :            : {
      53                 :        231 :   const char *f = "rnfeltreltoabs";
      54                 :            :   GEN pol;
      55                 :        231 :   checkrnf(rnf);
      56                 :        231 :   pol = rnf_get_polabs(rnf);
      57   [ +  +  +  +  :        231 :   switch(typ(x))
                      + ]
      58                 :            :   {
      59                 :         14 :     case t_INT: return icopy(x);
      60                 :         14 :     case t_FRAC: return gcopy(x);
      61                 :            :     case t_POLMOD:
      62         [ +  + ]:         98 :       if (RgX_equal_var(gel(x,1), pol))
      63                 :            :       { /* already in 'abs' form, unless possibly if nf = Q */
      64         [ +  + ]:         35 :         if (rnf_get_nfdegree(rnf) == 1)
      65                 :            :         {
      66                 :         14 :           GEN y = gel(x,2);
      67                 :         14 :           pari_sp av = avma;
      68                 :         14 :           y = simplify_shallow(liftpol_shallow(y));
      69                 :         14 :           return gerepilecopy(av, mkpolmod(y, pol));
      70                 :            :         }
      71                 :         21 :         return gcopy(x);
      72                 :            :       }
      73                 :         63 :       x = polmod_nffix(f,rnf,x,0);
      74         [ +  + ]:         49 :       if (typ(x) == t_POLMOD) return rnfeltup(rnf,x);
      75                 :         42 :       retmkpolmod(eltreltoabs(rnf_get_map(rnf), x), RgX_copy(pol));
      76                 :            :     case t_POL:
      77         [ +  + ]:         56 :       if (varn(x) == rnf_get_nfvarn(rnf)) return rnfeltup(rnf,x);
      78                 :         35 :       retmkpolmod(eltreltoabs(rnf_get_map(rnf), x), RgX_copy(pol));
      79                 :            :   }
      80                 :        203 :   pari_err_TYPE(f,x); return NULL;
      81                 :            : }
      82                 :            : 
      83                 :            : GEN
      84                 :       2023 : eltabstorel_lift(GEN rnfeq, GEN P)
      85                 :            : {
      86                 :       2023 :   GEN k, T = gel(rnfeq,4), relpol = gel(rnfeq,5);
      87         [ +  + ]:       2023 :   if (is_scalar_t(typ(P))) return P;
      88                 :       1834 :   k = gel(rnfeq,3);
      89                 :       1834 :   P = lift_intern(P);
      90         [ +  + ]:       1834 :   if (signe(k)) P = RgXQX_translate(P, deg1pol_shallow(k, gen_0, varn(T)), T);
      91                 :       1834 :   P = RgXQX_rem(P, relpol, T);
      92                 :       2023 :   return QXQX_to_mod_shallow(P, T);
      93                 :            : }
      94                 :            : /* rnfeq = [pol,a,k,T,relpol], P a t_POL or scalar
      95                 :            :  * Return Mod(P(x + k Mod(y, T(y))), pol(x)) */
      96                 :            : GEN
      97                 :       1974 : eltabstorel(GEN rnfeq, GEN P)
      98                 :            : {
      99                 :       1974 :   GEN T = gel(rnfeq,4), relpol = gel(rnfeq,5);
     100                 :       1974 :   return mkpolmod(eltabstorel_lift(rnfeq,P), QXQX_to_mod_shallow(relpol,T));
     101                 :            : }
     102                 :            : GEN
     103                 :       1358 : rnfeltabstorel(GEN rnf,GEN x)
     104                 :            : {
     105                 :       1358 :   const char *f = "rnfeltabstorel";
     106                 :       1358 :   pari_sp av = avma;
     107                 :            :   GEN pol, T, P;
     108                 :       1358 :   checkrnf(rnf);
     109                 :       1358 :   T = rnf_get_nfpol(rnf);
     110                 :       1358 :   P = rnf_get_pol(rnf);
     111   [ +  +  +  +  :       1358 :   switch(typ(x))
                      + ]
     112                 :            :   {
     113                 :         42 :     case t_INT: return icopy(x);
     114                 :         42 :     case t_FRAC: return gcopy(x);
     115                 :            :     case t_POLMOD:
     116         [ +  + ]:        315 :       if (RgX_equal_var(P, gel(x,1)))
     117                 :            :       {
     118                 :         70 :         x = polmod_nffix(f, rnf, x, 0);
     119                 :         70 :         return gerepilecopy(av, mkpolmod(x,P));
     120                 :            :       }
     121         [ +  + ]:        245 :       if (RgX_equal_var(T, gel(x,1))) { x = Rg_nffix(f, T, x, 0); goto END; }
     122                 :        161 :       pol = rnf_get_polabs(rnf);
     123         [ +  + ]:        161 :       if (!RgX_equal_var(pol, gel(x,1))) pari_err_MODULUS(f, gel(x,1),pol);
     124                 :        119 :       x = gel(x,2);
     125   [ +  +  +  - ]:        119 :       switch(typ(x))
     126                 :            :       {
     127                 :         28 :         case t_INT: return icopy(x);
     128                 :         28 :         case t_FRAC: return gcopy(x);
     129                 :         63 :         case t_POL: break;
     130                 :          0 :         default: pari_err_TYPE(f, x);
     131                 :            :       }
     132                 :         63 :       break;
     133                 :            :     case t_POL:
     134                 :        763 :       pol = rnf_get_polabs(rnf);
     135                 :        763 :       break;
     136                 :            :     default:
     137                 :        196 :       pari_err_TYPE(f,x);
     138                 :          0 :       return NULL;
     139                 :            :   }
     140         [ +  + ]:        826 :   if (!RgX_is_QX(x)) pari_err_TYPE(f,x);
     141         [ +  + ]:        749 :   if (varn(x) != varn(pol))
     142                 :            :   {
     143         [ +  + ]:         70 :     if (varn(x) == varn(T)) { x = Rg_nffix(f,T,x,0); goto END; }
     144                 :         28 :     pari_err_VAR(f, x,pol);
     145                 :            :   }
     146      [ +  +  + ]:        679 :   switch(lg(x))
     147                 :            :   {
     148                 :         42 :     case 2: avma = av; return gen_0;
     149                 :         70 :     case 3: return gerepilecopy(av, gel(x,2));
     150                 :            :   }
     151                 :            : END:
     152                 :       1015 :   return gerepilecopy(av, eltabstorel(rnf_get_map(rnf), x));
     153                 :            : }
     154                 :            : 
     155                 :            : 
     156                 :            : /* x a t_VEC of rnf elements in 'alg' form (t_POL). Assume maximal rank or 0 */
     157                 :            : static GEN
     158                 :        553 : modulereltoabs(GEN rnf, GEN x)
     159                 :            : {
     160                 :        553 :   GEN W=gel(x,1), I=gel(x,2), rnfeq = rnf_get_map(rnf), polabs = gel(rnfeq,1);
     161                 :        553 :   long i, j, k, m, N = lg(W)-1;
     162                 :            :   GEN zknf, czknf, M;
     163                 :            : 
     164         [ +  + ]:        553 :   if (!N) return cgetg(1, t_VEC);
     165                 :        504 :   rnf_get_nfzk(rnf, &zknf,&czknf);
     166                 :        504 :   m = rnf_get_nfdegree(rnf);
     167                 :        504 :   M = cgetg(N*m+1, t_VEC);
     168         [ +  + ]:       1554 :   for (k=i=1; i<=N; i++)
     169                 :            :   {
     170                 :       1064 :     GEN c0, cid, w = gel(W,i), id = gel(I,i);
     171                 :            : 
     172         [ +  + ]:       1064 :     if (lg(id) == 1) continue; /* must be a t_MAT */
     173                 :       1015 :     id = Q_primitive_part(id, &cid);
     174                 :       1015 :     w = Q_primitive_part(eltreltoabs(rnfeq,w), &c0);
     175                 :       1015 :     c0 = mul_content(c0, mul_content(cid,czknf));
     176         [ +  + ]:       1015 :     if (typ(id) == t_INT)
     177         [ +  + ]:       2079 :       for (j=1; j<=m; j++)
     178                 :            :       {
     179                 :       1540 :         GEN z = RgX_rem(gmul(w, gel(zknf,j)), polabs);
     180         [ +  - ]:       1540 :         if (c0) z = RgX_Rg_mul(z, c0);
     181                 :       1540 :         gel(M,k++) = z;
     182                 :            :       }
     183                 :            :     else
     184         [ +  + ]:       2345 :       for (j=1; j<=m; j++)
     185                 :            :       {
     186                 :       1344 :         GEN c, z = Q_primitive_part(RgV_RgC_mul(zknf,gel(id,j)), &c);
     187                 :       1330 :         z = RgX_rem(gmul(w, z), polabs);
     188         [ +  - ]:       1330 :         c = mul_content(c, c0); if (c) z = RgX_Rg_mul(z, c);
     189                 :       1330 :         gel(M,k++) = z;
     190                 :            :       }
     191                 :            :   }
     192                 :        539 :   setlg(M, k); return M;
     193                 :            : }
     194                 :            : 
     195                 :            : /* Z-basis for absolute maximal order, as a t_MAT */
     196                 :            : GEN
     197                 :        154 : rnf_basM(GEN rnf)
     198                 :            : {
     199                 :        154 :   GEN M, d, pol = rnf_get_polabs(rnf);
     200                 :        154 :   long n = degpol(pol);
     201                 :            :   /* t_VEC of t_POL */
     202                 :        154 :   M = Q_remove_denom(modulereltoabs(rnf, rnf_get_zk(rnf)), &d);
     203         [ +  - ]:        154 :   if (d)
     204                 :            :   {
     205                 :        154 :     M = ZM_hnfmodall(RgXV_to_RgM(M,n), d, hnf_MODID|hnf_CENTER);
     206                 :        154 :     M = RgM_Rg_div(M, d);
     207                 :            :   }
     208                 :            :   else
     209                 :          0 :     M = matid(n);
     210                 :        154 :   return M;
     211                 :            : }
     212                 :            : 
     213                 :            : /* only fill in nf[1,3,4,7,8,9] */
     214                 :            : static GEN
     215                 :        133 : makenfabs(GEN rnf)
     216                 :            : {
     217                 :        133 :   GEN nf = rnf_get_nf(rnf), pol = rnf_get_polabs(rnf), NF = zerovec(9);
     218                 :        133 :   GEN M = rnf_basM(rnf);
     219                 :        133 :   gel(NF,1) = pol;
     220                 :        133 :   gel(NF,3) = mulii(powiu(nf_get_disc(nf), rnf_get_degree(rnf)),
     221                 :            :                     idealnorm(nf, rnf_get_disc(rnf)));
     222                 :        133 :   nf_set_multable(NF, M, NULL);
     223                 :        133 :   gel(NF,4) = get_nfindex(nf_get_zk(NF));
     224                 :        133 :   return NF;
     225                 :            : }
     226                 :            : 
     227                 :            : static GEN
     228                 :          7 : makenorms(GEN rnf)
     229                 :            : {
     230                 :          7 :   GEN f = rnf_get_index(rnf);
     231         [ +  - ]:          7 :   return typ(f) == t_INT? gen_1: RgM_det_triangular(f);
     232                 :            : }
     233                 :            : 
     234                 :            : #define NFABS 1
     235                 :            : #define NORMS 2
     236                 :            : GEN
     237                 :        168 : check_and_build_nfabs(GEN rnf) {
     238                 :        168 :   return obj_checkbuild(rnf, NFABS, &makenfabs);
     239                 :            : }
     240                 :            : GEN
     241                 :         98 : check_and_build_norms(GEN rnf) {
     242                 :         98 :   return obj_checkbuild(rnf, NORMS, &makenorms);
     243                 :            : }
     244                 :            : 
     245                 :            : void
     246                 :        105 : nf_nfzk(GEN nf, GEN rnfeq, GEN *zknf, GEN *czknf)
     247                 :            : {
     248                 :        105 :   GEN pol = gel(rnfeq,1), a = gel(rnfeq,2);
     249                 :        105 :   GEN zk = QXV_QXQ_eval(nf_get_zk(nf), a, pol);
     250                 :        105 :   *zknf = Q_primitive_part(zk, czknf);
     251         [ +  + ]:        105 :   if (!*czknf) *czknf = gen_1;
     252                 :        105 : }
     253                 :            : 
     254                 :            : GEN
     255                 :         98 : rnfinit(GEN nf, GEN polrel)
     256                 :            : {
     257                 :         98 :   pari_sp av = avma;
     258                 :            :   GEN rnf, bas, D,d,f, B, rnfeq, basnf,cobasnf;
     259                 :         98 :   nf = checknf(nf);
     260                 :         98 :   bas = rnfallbase(nf,&polrel, &D,&d, &f);
     261                 :         98 :   B = matbasistoalg(nf,gel(bas,1));
     262                 :         98 :   gel(bas,1) = lift_if_rational( RgM_to_RgXV(B,varn(polrel)) );
     263                 :         98 :   rnfeq = nf_rnfeq(nf,polrel);
     264                 :         98 :   nf_nfzk(nf, rnfeq, &basnf, &cobasnf);
     265                 :         98 :   rnf = cgetg(13, t_VEC);
     266                 :         98 :   gel(rnf,1) = polrel;
     267                 :         98 :   gel(rnf,2) = mkvec2(basnf, cobasnf);
     268                 :         98 :   gel(rnf,3) = mkvec2(D, d);
     269                 :         98 :   gel(rnf,4) = f;
     270                 :         98 :   gel(rnf,5) = cgetg(1, t_VEC); /* dummy */
     271                 :         98 :   gel(rnf,6) = cgetg(1, t_VEC); /* dummy */
     272                 :         98 :   gel(rnf,7) = bas;
     273                 :         98 :   gel(rnf,8) = lift_if_rational( RgM_inv(B) );
     274                 :         98 :   gel(rnf,9) = cgetg(1,t_VEC); /* dummy */
     275                 :         98 :   gel(rnf,10)= nf;
     276                 :         98 :   gel(rnf,11)= rnfeq;
     277                 :         98 :   gel(rnf,12)= zerovec(2);
     278                 :         98 :   return gerepilecopy(av, rnf);
     279                 :            : }
     280                 :            : 
     281                 :            : GEN
     282                 :        259 : rnfeltup(GEN rnf, GEN x)
     283                 :            : {
     284                 :        259 :   pari_sp av = avma;
     285                 :            :   GEN zknf, czknf;
     286                 :        259 :   checkrnf(rnf);
     287 [ +  + ][ +  + ]:        259 :   if (typ(x) == t_POLMOD && RgX_equal_var(gel(x,1), rnf_get_polabs(rnf)))
     288                 :         28 :     return gcopy(x);
     289                 :        231 :   rnf_get_nfzk(rnf, &zknf, &czknf);
     290                 :        231 :   x = nfeltup(rnf_get_nf(rnf), x, zknf, czknf);
     291         [ +  + ]:        112 :   if (typ(x) == t_POL) x = mkpolmod(x, rnf_get_polabs(rnf));
     292                 :        140 :   return gerepilecopy(av, x);
     293                 :            : }
     294                 :            : 
     295                 :            : GEN
     296                 :        259 : nfeltup(GEN nf, GEN x, GEN zknf, GEN czknf)
     297                 :            : {
     298                 :            :   GEN c;
     299                 :        259 :   x = nf_to_scalar_or_basis(nf, x);
     300         [ +  + ]:        154 :   if (typ(x) != t_COL) return x;
     301                 :         56 :   x = Q_primitive_part(x, &c);
     302         [ +  + ]:         56 :   if (!RgV_is_ZV(x)) pari_err_TYPE("rnfeltup", x);
     303                 :         42 :   c = mul_content(c, czknf);
     304         [ +  - ]:         42 :   x = RgV_RgC_mul(zknf, x); if (c) x = RgX_Rg_mul(x, c);
     305                 :        140 :   return x;
     306                 :            : }
     307                 :            : 
     308                 :            : static void
     309                 :         49 : fail(const char *f, GEN x)
     310                 :         49 : { pari_err_DOMAIN(f,"element","not in", strtoGENstr("the base field"),x); }
     311                 :            : GEN
     312                 :        427 : rnfeltdown(GEN rnf,GEN x)
     313                 :            : {
     314                 :        427 :   const char *f = "rnfeltdown";
     315                 :        427 :   pari_sp av = avma;
     316                 :            :   GEN z, T;
     317                 :            :   long v;
     318                 :            : 
     319                 :        427 :   checkrnf(rnf);
     320                 :        427 :   T = rnf_get_nfpol(rnf);
     321                 :        427 :   v = varn(T);
     322   [ +  +  +  +  :        427 :   switch(typ(x))
                      + ]
     323                 :            :   { /* directly belonging to base field ? */
     324                 :        112 :     case t_INT: return icopy(x);
     325                 :         35 :     case t_FRAC:return gcopy(x);
     326                 :            :     case t_POLMOD:
     327         [ +  + ]:        168 :       if (RgX_equal_var(gel(x,1), rnf_get_polabs(rnf))) break;
     328                 :        126 :       x = polmod_nffix(f,rnf,x,0);
     329                 :            :       /* x was defined mod the relative polynomial & non constant => fail */
     330         [ +  + ]:        112 :       if (typ(x) == t_POL) fail(f,x);
     331                 :         91 :       return gerepilecopy(av, x);
     332                 :            : 
     333                 :            :     case t_POL:
     334         [ +  + ]:         63 :       if (varn(x) != v) break;
     335                 :         21 :       x = Rg_nffix(f,T,x,0);
     336                 :         14 :       return gerepilecopy(av, x);
     337                 :            :   }
     338                 :            :   /* x defined mod the absolute equation */
     339                 :        133 :   z = rnfeltabstorel(rnf,x);
     340         [ +  + ]:         63 :   switch(typ(z))
     341                 :            :   {
     342                 :            :     case t_INT:
     343                 :         14 :     case t_FRAC: return z;
     344                 :            :   }
     345                 :            :   /* typ(z) = t_POLMOD, varn of both components is rnf_get_varn(rnf) */
     346                 :         49 :   z = gel(z,2);
     347         [ +  + ]:         49 :   if (typ(z) == t_POL)
     348                 :            :   {
     349         [ +  + ]:         42 :     if (lg(z) != 3) fail(f,x);
     350                 :         14 :     z = gel(z,2);
     351                 :            :   }
     352                 :        287 :   return gerepilecopy(av, z);
     353                 :            : }
     354                 :            : 
     355                 :            : /* vector of rnf elt -> matrix of nf elts */
     356                 :            : static GEN
     357                 :        462 : rnfV_to_nfM(GEN rnf, GEN x)
     358                 :            : {
     359                 :        462 :   long i, l = lg(x);
     360                 :        462 :   GEN y = cgetg(l, t_MAT);
     361         [ +  + ]:       1386 :   for (i = 1; i < l; i++) gel(y,i) = rnfalgtobasis(rnf,gel(x,i));
     362                 :        462 :   return y;
     363                 :            : }
     364                 :            : 
     365                 :            : static GEN
     366                 :        756 : rnfprincipaltohnf(GEN rnf,GEN x)
     367                 :            : {
     368                 :        756 :   pari_sp av = avma;
     369                 :        756 :   GEN bas = rnf_get_zk(rnf), nf = rnf_get_nf(rnf);
     370                 :        756 :   x = rnfbasistoalg(rnf,x);
     371                 :        420 :   x = gmul(x, gmodulo(gel(bas,1), rnf_get_pol(rnf)));
     372                 :        420 :   return gerepileupto(av, nfhnf(nf, mkvec2(rnfV_to_nfM(rnf,x), gel(bas,2))));
     373                 :            : }
     374                 :            : 
     375                 :            : /* pseudo-basis for the 0 ideal */
     376                 :            : static GEN
     377                 :        112 : rnfideal0() { retmkvec2(cgetg(1,t_MAT),cgetg(1,t_VEC)); }
     378                 :            : 
     379                 :            : GEN
     380                 :       1302 : rnfidealhnf(GEN rnf, GEN x)
     381                 :            : {
     382                 :            :   GEN z, nf, bas;
     383                 :            : 
     384                 :       1302 :   checkrnf(rnf); nf = rnf_get_nf(rnf);
     385   [ +  +  +  + ]:       1302 :   switch(typ(x))
     386                 :            :   {
     387                 :            :     case t_INT: case t_FRAC:
     388         [ +  + ]:        161 :       if (isintzero(x)) return rnfideal0();
     389                 :        105 :       bas = rnf_get_zk(rnf); z = cgetg(3,t_VEC);
     390                 :        105 :       gel(z,1) = matid(rnf_get_degree(rnf));
     391                 :        105 :       gel(z,2) = gmul(x, gel(bas,2)); return z;
     392                 :            : 
     393                 :            :     case t_VEC:
     394 [ +  + ][ +  - ]:        259 :       if (lg(x) == 3 && typ(gel(x,1)) == t_MAT) return nfhnf(nf, x);
     395                 :        140 :       return rnfidealabstorel(rnf, x);
     396                 :            : 
     397                 :            :     case t_POLMOD: case t_POL: case t_COL:
     398                 :        756 :       return rnfprincipaltohnf(rnf,x);
     399                 :            :   }
     400                 :        126 :   pari_err_TYPE("rnfidealhnf",x);
     401                 :        798 :   return NULL; /* not reached */
     402                 :            : }
     403                 :            : 
     404                 :            : GEN
     405                 :        693 : prodid(GEN nf, GEN I)
     406                 :            : {
     407                 :        693 :   long i, l = lg(I);
     408                 :            :   GEN z;
     409         [ +  + ]:        693 :   if (l == 1) return matid(nf_get_degree(nf));
     410                 :        686 :   z = gel(I,1);
     411         [ +  + ]:       1512 :   for (i=2; i<l; i++) z = idealmul(nf, z, gel(I,i));
     412                 :        693 :   return z;
     413                 :            : }
     414                 :            : 
     415                 :            : static GEN
     416                 :         98 : prodidnorm(GEN nf, GEN I)
     417                 :            : {
     418                 :         98 :   long i, l = lg(I);
     419                 :            :   GEN z;
     420         [ -  + ]:         98 :   if (l == 1) return gen_1;
     421                 :         98 :   z = idealnorm(nf, gel(I,1));
     422         [ +  + ]:        196 :   for (i=2; i<l; i++) z = gmul(z, idealnorm(nf, gel(I,i)));
     423                 :         98 :   return z;
     424                 :            : }
     425                 :            : 
     426                 :            : GEN
     427                 :        196 : rnfidealnormrel(GEN rnf, GEN id)
     428                 :            : {
     429                 :        196 :   pari_sp av = avma;
     430                 :        196 :   GEN nf, z = gel(rnfidealhnf(rnf,id), 2);
     431         [ +  + ]:        112 :   if (lg(z) == 1) return cgetg(1, t_MAT);
     432                 :         91 :   nf = rnf_get_nf(rnf); z = prodid(nf, z);
     433                 :        112 :   return gerepileupto(av, idealmul(nf,z, rnf_get_index(rnf)));
     434                 :            : }
     435                 :            : 
     436                 :            : GEN
     437                 :        203 : rnfidealnormabs(GEN rnf, GEN id)
     438                 :            : {
     439                 :        203 :   pari_sp av = avma;
     440                 :        203 :   GEN nf, z = gel(rnfidealhnf(rnf,id), 2);
     441         [ +  + ]:        119 :   if (lg(z) == 1) return gen_0;
     442                 :         98 :   nf = rnf_get_nf(rnf); z = prodidnorm(nf, z);
     443                 :        119 :   return gerepileupto(av, gmul(z, check_and_build_norms(rnf)));
     444                 :            : }
     445                 :            : 
     446                 :            : GEN
     447                 :        455 : rnfidealreltoabs(GEN rnf,GEN x)
     448                 :            : {
     449                 :        455 :   pari_sp av = avma;
     450                 :            :   long i, l;
     451                 :            :   GEN w;
     452                 :            : 
     453                 :        455 :   x = rnfidealhnf(rnf,x);
     454                 :        287 :   w = gel(x,1); l = lg(w); settyp(w, t_VEC);
     455         [ +  + ]:        770 :   for (i=1; i<l; i++) gel(w,i) = lift_intern( rnfbasistoalg(rnf, gel(w,i)) );
     456                 :        287 :   return gerepilecopy(av, modulereltoabs(rnf, x));
     457                 :            : }
     458                 :            : 
     459                 :            : GEN
     460                 :        343 : rnfidealabstorel(GEN rnf, GEN x)
     461                 :            : {
     462                 :            :   long N, j;
     463                 :        343 :   pari_sp av = avma;
     464                 :            :   GEN A, I, invbas;
     465                 :            : 
     466                 :        343 :   checkrnf(rnf);
     467                 :        343 :   invbas = rnf_get_invzk(rnf);
     468         [ +  + ]:        343 :   if (typ(x) != t_VEC) pari_err_TYPE("rnfidealabstorel",x);
     469                 :        182 :   N = lg(x)-1;
     470         [ +  + ]:        182 :   if (N != rnf_get_absdegree(rnf))
     471                 :            :   {
     472         [ +  + ]:        112 :     if (!N) return rnfideal0();
     473                 :         63 :     pari_err_DIM("rnfidealabstorel");
     474                 :            :   }
     475                 :         70 :   A = cgetg(N+1,t_MAT);
     476                 :         70 :   I = cgetg(N+1,t_VEC);
     477         [ +  + ]:        490 :   for (j=1; j<=N; j++)
     478                 :            :   {
     479                 :        420 :     GEN t = lift_intern( rnfeltabstorel(rnf, gel(x,j)) );
     480                 :        420 :     gel(A,j) = mulmat_pol(invbas, t);
     481                 :        420 :     gel(I,j) = gen_1;
     482                 :            :   }
     483                 :        119 :   return gerepileupto(av, nfhnf(rnf_get_nf(rnf), mkvec2(A,I)));
     484                 :            : }
     485                 :            : 
     486                 :            : GEN
     487                 :        210 : rnfidealdown(GEN rnf,GEN x)
     488                 :            : {
     489                 :        210 :   pari_sp av = avma;
     490                 :            :   GEN I;
     491                 :        210 :   x = rnfidealhnf(rnf,x); I = gel(x,2);
     492         [ +  + ]:        126 :   if (lg(I) == 1) { avma = av; return cgetg(1,t_MAT); }
     493                 :        126 :   return gerepilecopy(av, gel(I,1));
     494                 :            : }
     495                 :            : 
     496                 :            : /* lift ideal x to the relative extension, returns a Z-basis */
     497                 :            : GEN
     498                 :        217 : rnfidealup(GEN rnf,GEN x)
     499                 :            : {
     500                 :        217 :   pari_sp av = avma;
     501                 :            :   long i, n;
     502                 :            :   GEN nf, bas, bas2, I;
     503                 :            : 
     504                 :        217 :   checkrnf(rnf); nf = rnf_get_nf(rnf);
     505                 :        217 :   n = rnf_get_degree(rnf);
     506                 :        217 :   bas = rnf_get_zk(rnf); bas2 = gel(bas,2);
     507                 :            : 
     508                 :        217 :   (void)idealtyp(&x, &I); /* I is junk */
     509                 :        203 :   I = cgetg(n+1,t_VEC);
     510         [ +  + ]:        420 :   for (i=1; i<=n; i++) gel(I,i) = idealmul(nf,x,gel(bas2,i));
     511                 :        112 :   return gerepilecopy(av, modulereltoabs(rnf, mkvec2(gel(bas,1), I)));
     512                 :            : }
     513                 :            : 
     514                 :            : /* x a relative HNF => vector of 2 generators (relative polmods) */
     515                 :            : GEN
     516                 :        252 : rnfidealtwoelement(GEN rnf, GEN x)
     517                 :            : {
     518                 :        252 :   pari_sp av = avma;
     519                 :            :   GEN y, cy, z, NF;
     520                 :            : 
     521                 :        252 :   y = rnfidealreltoabs(rnf,x);
     522                 :        168 :   NF = check_and_build_nfabs(rnf);
     523                 :        168 :   y = matalgtobasis(NF, y); settyp(y, t_MAT);
     524                 :        168 :   y = Q_primitive_part(y, &cy);
     525                 :        168 :   y = ZM_hnf(y);
     526         [ +  + ]:        168 :   if (lg(y) == 1) { avma = av; return mkvec2(gen_0, gen_0); }
     527                 :        140 :   y = idealtwoelt(NF, y);
     528         [ +  + ]:        133 :   if (cy) y = RgV_Rg_mul(y, cy);
     529                 :        133 :   z = rnfeltabstorel(rnf, coltoliftalg(NF, gel(y,2)));
     530                 :        161 :   return gerepilecopy(av, mkvec2(gel(y,1), z));
     531                 :            : }
     532                 :            : 
     533                 :            : GEN
     534                 :         49 : rnfidealmul(GEN rnf,GEN x,GEN y)
     535                 :            : {
     536                 :         49 :   pari_sp av = avma;
     537                 :            :   GEN nf, z, x1, x2, p1, p2, bas;
     538                 :            : 
     539                 :         49 :   y = rnfidealtwoelement(rnf,y);
     540         [ +  + ]:         49 :   if (isintzero(gel(y,1))) { avma = av; return rnfideal0(); }
     541                 :         42 :   nf = rnf_get_nf(rnf);
     542                 :         42 :   bas = rnf_get_zk(rnf);
     543                 :         42 :   x = rnfidealhnf(rnf,x);
     544                 :         42 :   x1 = gmodulo(gmul(gel(bas,1), matbasistoalg(nf,gel(x,1))), rnf_get_pol(rnf));
     545                 :         42 :   x2 = gel(x,2);
     546                 :         42 :   p1 = gmul(gel(y,1), gel(x,1));
     547                 :         42 :   p2 = rnfV_to_nfM(rnf, gmul(gel(y,2), x1));
     548                 :         42 :   z = mkvec2(shallowconcat(p1, p2), shallowconcat(x2, x2));
     549                 :         49 :   return gerepileupto(av, nfhnf(nf,z));
     550                 :            : }
     551                 :            : 
     552                 :            : int
     553                 :        315 : nfissquarefree(GEN nf, GEN x)
     554                 :            : {
     555                 :        315 :   pari_sp av = avma;
     556                 :        315 :   GEN g, y = RgX_deriv(x);
     557         [ +  + ]:        315 :   if (RgX_is_rational(x))
     558                 :         98 :     g = QX_gcd(x, y);
     559                 :            :   else
     560                 :        217 :     g = nfgcd(x, y, nf, NULL);
     561                 :        315 :   avma = av; return (degpol(g) == 0);
     562                 :            : }
     563                 :            : 
     564                 :            : GEN
     565                 :        315 : rnfequationall(GEN A, GEN B, long *pk, GEN *pLPRS)
     566                 :            : {
     567                 :            :   long lA, lB;
     568                 :            :   GEN nf, C;
     569                 :            : 
     570                 :        315 :   A = get_nfpol(A, &nf); lA = lg(A);
     571         [ +  + ]:        315 :   if (!nf) {
     572         [ -  + ]:        126 :     if (lA<=3) pari_err_CONSTPOL("rnfequation");
     573                 :        126 :     RgX_check_ZX(A,"rnfequation");
     574                 :            :   }
     575                 :        315 :   B = RgX_nffix("rnfequation", A,B,1); lB = lg(B);
     576         [ -  + ]:        315 :   if (lB<=3) pari_err_CONSTPOL("rnfequation");
     577                 :        315 :   B = Q_primpart(B);
     578                 :            : 
     579         [ -  + ]:        315 :   if (!nfissquarefree(A,B))
     580                 :          0 :     pari_err_DOMAIN("rnfequation","issquarefree(B)","=",gen_0,B);
     581                 :            : 
     582                 :        315 :   *pk = 0; C = ZX_ZXY_resultant_all(A, B, pk, pLPRS);
     583         [ -  + ]:        315 :   if (gsigne(leading_term(C)) < 0) C = RgX_neg(C);
     584                 :        315 :   *pk = -*pk; return Q_primpart(C);
     585                 :            : }
     586                 :            : 
     587                 :            : GEN
     588                 :        273 : rnfequation0(GEN A, GEN B, long flall)
     589                 :            : {
     590                 :        273 :   pari_sp av = avma;
     591                 :            :   GEN LPRS, C;
     592                 :            :   long k;
     593                 :            : 
     594         [ +  + ]:        273 :   C = rnfequationall(A, B, &k, flall? &LPRS: NULL);
     595         [ +  + ]:        273 :   if (flall)
     596                 :            :   { /* a,b,c root of A,B,C = compositum, c = b + k a */
     597                 :        259 :     GEN a, mH0 = RgX_neg(gel(LPRS,1)), H1 = gel(LPRS,2);
     598                 :        259 :     a = RgXQ_mul(mH0, QXQ_inv(H1, C), C);
     599                 :        259 :     C = mkvec3(C, mkpolmod(a, C), stoi(k));
     600                 :            :   }
     601                 :        273 :   return gerepilecopy(av, C);
     602                 :            : }
     603                 :            : GEN
     604                 :          7 : rnfequation(GEN nf, GEN pol) { return rnfequation0(nf,pol,0); }
     605                 :            : GEN
     606                 :        147 : rnfequation2(GEN nf, GEN pol) { return rnfequation0(nf,pol,1); }
     607                 :            : GEN
     608                 :        140 : nf_rnfeq(GEN nf, GEN relpol)
     609                 :            : {
     610                 :            :   GEN pol, a, k, junk, eq;
     611                 :        140 :   relpol = liftpol_shallow(relpol);
     612                 :        140 :   eq = rnfequation2(nf, relpol);
     613                 :        140 :   pol = gel(eq,1);
     614         [ +  - ]:        140 :   a = gel(eq,2); if (typ(a) == t_POLMOD) a = gel(a,2);
     615                 :        140 :   k = gel(eq,3);
     616                 :        140 :   return mkvec5(pol,a,k,get_nfpol(nf, &junk),relpol);
     617                 :            : }
     618                 :            : /* only allow abstorel */
     619                 :            : GEN
     620                 :          7 : nf_rnfeqsimple(GEN nf, GEN relpol)
     621                 :            : {
     622                 :            :   long sa;
     623                 :          7 :   GEN junk, pol = rnfequationall(nf, relpol, &sa, NULL);
     624                 :          7 :   return mkvec5(pol,gen_0/*dummy*/,stoi(sa),get_nfpol(nf, &junk),relpol);
     625                 :            : }
     626                 :            : 
     627                 :            : static GEN
     628                 :        196 : nftau(long r1, GEN x)
     629                 :            : {
     630                 :        196 :   long i, l = lg(x);
     631         [ +  - ]:        196 :   GEN s = r1? gel(x,1): gmul2n(real_i(gel(x,1)),1);
     632         [ +  + ]:        392 :   for (i=2; i<=r1; i++) s = gadd(s, gel(x,i));
     633         [ -  + ]:        196 :   for (   ; i < l; i++) s = gadd(s, gmul2n(real_i(gel(x,i)),1));
     634                 :        196 :   return s;
     635                 :            : }
     636                 :            : 
     637                 :            : static GEN
     638                 :         28 : initmat(long l)
     639                 :            : {
     640                 :         28 :   GEN x = cgetg(l, t_MAT);
     641                 :            :   long i;
     642         [ +  + ]:        196 :   for (i = 1; i < l; i++) gel(x,i) = cgetg(l, t_COL);
     643                 :         28 :   return x;
     644                 :            : }
     645                 :            : 
     646                 :            : static GEN
     647                 :       1022 : nftocomplex(GEN nf, GEN x)
     648                 :            : {
     649                 :       1022 :   GEN M = nf_get_M(nf);
     650                 :       1022 :   x = nf_to_scalar_or_basis(nf,x);
     651         [ +  + ]:       1022 :   if (typ(x) != t_COL) return const_col(nbrows(M), x);
     652                 :       1022 :   return RgM_RgC_mul(M, x);
     653                 :            : }
     654                 :            : /* assume x a square t_MAT, return a t_VEC of embeddings of its columns */
     655                 :            : static GEN
     656                 :         14 : mattocomplex(GEN nf, GEN x)
     657                 :            : {
     658                 :         14 :   long i,j, l = lg(x);
     659                 :         14 :   GEN v = cgetg(l, t_VEC);
     660         [ +  + ]:         98 :   for (j=1; j<l; j++)
     661                 :            :   {
     662                 :         84 :     GEN c = gel(x,j), b = cgetg(l, t_MAT);
     663         [ +  + ]:        714 :     for (i=1; i<l; i++) gel(b,i) = nftocomplex(nf, gel(c,i));
     664                 :         84 :     b = shallowtrans(b); settyp(b, t_COL);
     665                 :         84 :     gel(v,j) = b;
     666                 :            :   }
     667                 :         14 :   return v;
     668                 :            : }
     669                 :            : 
     670                 :            : static GEN
     671                 :         14 : nf_all_roots(GEN nf, GEN x, long prec)
     672                 :            : {
     673                 :         14 :   long i, j, l = lg(x), ru = lg(nf_get_roots(nf));
     674                 :         14 :   GEN y = cgetg(l, t_POL), v, z;
     675                 :            : 
     676                 :         14 :   x = RgX_to_nfX(nf, x);
     677                 :         14 :   y[1] = x[1];
     678         [ +  + ]:        112 :   for (i=2; i<l; i++) gel(y,i) = nftocomplex(nf, gel(x,i));
     679 [ -  + ][ #  # ]:         14 :   i = gprecision(y); if (i && i <= 3) return NULL;
     680                 :            : 
     681                 :         14 :   v = cgetg(ru, t_VEC);
     682                 :         14 :   z = cgetg(l, t_POL); z[1] = x[1];
     683         [ +  + ]:         42 :   for (i=1; i<ru; i++)
     684                 :            :   {
     685         [ +  + ]:        224 :     for (j = 2; j < l; j++) gel(z,j) = gmael(y,j,i);
     686                 :         28 :     gel(v,i) = cleanroots(z, prec);
     687                 :            :   }
     688                 :         14 :   return v;
     689                 :            : }
     690                 :            : 
     691                 :            : static GEN
     692                 :        357 : rnfscal(GEN m, GEN x, GEN y)
     693                 :            : {
     694                 :        357 :   long i, l = lg(m);
     695                 :        357 :   GEN z = cgetg(l, t_COL);
     696         [ +  + ]:       1071 :   for (i = 1; i < l; i++)
     697                 :        714 :     gel(z,i) = gmul(gconj(shallowtrans(gel(x,i))), gmul(gel(m,i), gel(y,i)));
     698                 :        357 :   return z;
     699                 :            : }
     700                 :            : 
     701                 :            : /* x ideal in HNF */
     702                 :            : static GEN
     703                 :        364 : findmin(GEN nf, GEN x, GEN muf)
     704                 :            : {
     705                 :        364 :   pari_sp av = avma;
     706                 :            :   long e;
     707                 :        364 :   GEN cx, y, m, M = nf_get_M(nf);
     708                 :            : 
     709                 :        364 :   x = Q_primitive_part(x, &cx);
     710         [ +  + ]:        364 :   if (gequal1(gcoeff(x,1,1))) y = M;
     711                 :            :   else
     712                 :            :   {
     713                 :        210 :     GEN G = nf_get_G(nf);
     714                 :        210 :     m = lllfp(RgM_mul(G,x), 0.75, 0);
     715         [ -  + ]:        210 :     if (typ(m) != t_MAT)
     716                 :            :     {
     717                 :          0 :       x = ZM_lll(x, 0.75, LLL_INPLACE);
     718                 :          0 :       m = lllfp(RgM_mul(G,x), 0.75, 0);
     719         [ #  # ]:          0 :       if (typ(m) != t_MAT) pari_err_PREC("rnflllgram");
     720                 :            :     }
     721                 :        210 :     x = ZM_mul(x, m);
     722                 :        210 :     y = RgM_mul(M, x);
     723                 :            :   }
     724                 :        364 :   m = RgM_solve_realimag(y, muf);
     725         [ -  + ]:        364 :   if (!m) return NULL; /* precision problem */
     726         [ +  + ]:        364 :   if (cx) m = RgC_Rg_div(m, cx);
     727                 :        364 :   m = grndtoi(m, &e);
     728         [ -  + ]:        364 :   if (e >= 0) return NULL; /* precision problem */
     729                 :        364 :   m = ZM_ZC_mul(x, m);
     730         [ +  + ]:        364 :   if (cx) m = RgC_Rg_mul(m, cx);
     731                 :        364 :   return gerepileupto(av, m);
     732                 :            : }
     733                 :            : 
     734                 :            : static int
     735                 :        364 : RED(long k, long l, GEN U, GEN mu, GEN MC, GEN nf, GEN I, GEN *Ik_inv)
     736                 :            : {
     737                 :            :   GEN x, xc, ideal;
     738                 :            :   long i;
     739                 :            : 
     740         [ +  + ]:        364 :   if (!*Ik_inv) *Ik_inv = idealinv(nf, gel(I,k));
     741                 :        364 :   ideal = idealmul(nf,gel(I,l), *Ik_inv);
     742                 :        364 :   x = findmin(nf, ideal, gcoeff(mu,k,l));
     743         [ -  + ]:        364 :   if (!x) return 0;
     744         [ +  + ]:        364 :   if (gequal0(x)) return 1;
     745                 :            : 
     746                 :        294 :   xc = nftocomplex(nf,x);
     747                 :        294 :   gel(MC,k) = gsub(gel(MC,k), vecmul(xc,gel(MC,l)));
     748                 :        294 :   gel(U,k) = gsub(gel(U,k), gmul(coltoalg(nf,x), gel(U,l)));
     749                 :        294 :   gcoeff(mu,k,l) = gsub(gcoeff(mu,k,l), xc);
     750         [ +  + ]:       1029 :   for (i=1; i<l; i++)
     751                 :        735 :     gcoeff(mu,k,i) = gsub(gcoeff(mu,k,i), vecmul(xc,gcoeff(mu,l,i)));
     752                 :        364 :   return 1;
     753                 :            : }
     754                 :            : 
     755                 :            : static int
     756                 :         84 : check_0(GEN B)
     757                 :            : {
     758                 :         84 :   long i, l = lg(B);
     759         [ +  + ]:        252 :   for (i = 1; i < l; i++)
     760         [ -  + ]:        168 :     if (gsigne(gel(B,i)) <= 0) return 1;
     761                 :         84 :   return 0;
     762                 :            : }
     763                 :            : 
     764                 :            : static int
     765                 :         98 : do_SWAP(GEN I, GEN MC, GEN MCS, GEN h, GEN mu, GEN B, long kmax, long k,
     766                 :            :         const long alpha, long r1)
     767                 :            : {
     768                 :            :   GEN p1, p2, muf, mufc, Bf, temp;
     769                 :            :   long i, j;
     770                 :            : 
     771                 :         98 :   p1 = nftau(r1, gadd(gel(B,k),
     772                 :        196 :                       gmul(gnorml2(gcoeff(mu,k,k-1)), gel(B,k-1))));
     773                 :         98 :   p2 = nftau(r1, gel(B,k-1));
     774         [ +  + ]:         98 :   if (gcmp(gmulsg(alpha,p1), gmulsg(alpha-1,p2)) > 0) return 0;
     775                 :            : 
     776                 :         14 :   swap(gel(MC,k-1),gel(MC,k));
     777                 :         14 :   swap(gel(h,k-1), gel(h,k));
     778                 :         14 :   swap(gel(I,k-1), gel(I,k));
     779         [ +  + ]:         91 :   for (j=1; j<=k-2; j++) swap(gcoeff(mu,k-1,j),gcoeff(mu,k,j));
     780                 :         14 :   muf = gcoeff(mu,k,k-1);
     781                 :         14 :   mufc = gconj(muf);
     782                 :         14 :   Bf = gadd(gel(B,k), vecmul(real_i(vecmul(muf,mufc)), gel(B,k-1)));
     783         [ -  + ]:         14 :   if (check_0(Bf)) return 1; /* precision problem */
     784                 :            : 
     785                 :         14 :   p1 = vecdiv(gel(B,k-1),Bf);
     786                 :         14 :   gcoeff(mu,k,k-1) = vecmul(mufc,p1);
     787                 :         14 :   temp = gel(MCS,k-1);
     788                 :         14 :   gel(MCS,k-1) = gadd(gel(MCS,k), vecmul(muf,gel(MCS,k-1)));
     789                 :         14 :   gel(MCS,k) = gsub(vecmul(vecdiv(gel(B,k),Bf), temp),
     790                 :         28 :                     vecmul(gcoeff(mu,k,k-1), gel(MCS,k)));
     791                 :         14 :   gel(B,k) = vecmul(gel(B,k),p1);
     792                 :         14 :   gel(B,k-1) = Bf;
     793         [ -  + ]:         14 :   for (i=k+1; i<=kmax; i++)
     794                 :            :   {
     795                 :          0 :     temp = gcoeff(mu,i,k);
     796                 :          0 :     gcoeff(mu,i,k) = gsub(gcoeff(mu,i,k-1), vecmul(muf, gcoeff(mu,i,k)));
     797                 :          0 :     gcoeff(mu,i,k-1) = gadd(temp, vecmul(gcoeff(mu,k,k-1),gcoeff(mu,i,k)));
     798                 :            :   }
     799                 :         98 :   return 1;
     800                 :            : }
     801                 :            : 
     802                 :            : static GEN
     803                 :         14 : rel_T2(GEN nf, GEN pol, long lx, long prec)
     804                 :            : {
     805                 :            :   long ru, i, j, k, l;
     806                 :            :   GEN T2, s, unro, roorder, powreorder;
     807                 :            : 
     808                 :         14 :   roorder = nf_all_roots(nf, pol, prec);
     809         [ -  + ]:         14 :   if (!roorder) return NULL;
     810                 :         14 :   ru = lg(roorder);
     811         [ +  + ]:         98 :   unro = cgetg(lx,t_COL); for (i=1; i<lx; i++) gel(unro,i) = gen_1;
     812                 :         14 :   powreorder = cgetg(lx,t_MAT); gel(powreorder,1) = unro;
     813                 :         14 :   T2 = cgetg(ru, t_VEC);
     814         [ +  + ]:         42 :   for (i = 1; i < ru; i++)
     815                 :            :   {
     816                 :         28 :     GEN ro = gel(roorder,i);
     817                 :         28 :     GEN m = initmat(lx);
     818         [ +  + ]:        168 :     for (k=2; k<lx; k++)
     819                 :            :     {
     820                 :        140 :       GEN c = cgetg(lx, t_COL); gel(powreorder,k) = c;
     821         [ +  + ]:       1232 :       for (j=1; j < lx; j++)
     822                 :       1092 :         gel(c,j) = gmul(gel(ro,j), gmael(powreorder,k-1,j));
     823                 :            :     }
     824         [ +  + ]:        196 :     for (l = 1; l < lx; l++)
     825         [ +  + ]:        882 :       for (k = 1; k <= l; k++)
     826                 :            :       {
     827                 :        714 :         s = gen_0;
     828         [ +  + ]:       6636 :         for (j = 1; j < lx; j++)
     829                 :       5922 :           s = gadd(s, gmul(gconj(gmael(powreorder,k,j)),
     830                 :       5922 :                                  gmael(powreorder,l,j)));
     831         [ +  + ]:        714 :         if (l == k)
     832                 :        168 :           gcoeff(m, l, l) = real_i(s);
     833                 :            :         else
     834                 :            :         {
     835                 :        546 :           gcoeff(m, k, l) = s;
     836                 :        546 :           gcoeff(m, l, k) = gconj(s);
     837                 :            :         }
     838                 :            :       }
     839                 :         28 :     gel(T2,i) = m;
     840                 :            :   }
     841                 :         14 :   return T2;
     842                 :            : }
     843                 :            : 
     844                 :            : /* given a base field nf (e.g main variable y), a polynomial pol with
     845                 :            :  * coefficients in nf    (e.g main variable x), and an order as output
     846                 :            :  * by rnfpseudobasis, outputs a reduced order. */
     847                 :            : GEN
     848                 :         14 : rnflllgram(GEN nf, GEN pol, GEN order,long prec)
     849                 :            : {
     850                 :         14 :   pari_sp av = avma;
     851                 :         14 :   long j, k, l, kmax, r1, lx, count = 0;
     852                 :            :   GEN M, I, h, H, mth, MC, MPOL, MCS, B, mu;
     853                 :         14 :   const long alpha = 10, MAX_COUNT = 4;
     854                 :            : 
     855                 :         14 :   nf = checknf(nf); r1 = nf_get_r1(nf);
     856                 :         14 :   check_ZKmodule(order, "rnflllgram");
     857                 :         14 :   M = gel(order,1);
     858                 :         14 :   I = gel(order,2); lx = lg(I);
     859         [ -  + ]:         14 :   if (lx < 3) return gcopy(order);
     860         [ -  + ]:         14 :   if (lx-1 != degpol(pol)) pari_err_DIM("rnflllgram");
     861                 :         14 :   I = leafcopy(I);
     862                 :         14 :   H = NULL;
     863                 :         14 :   MPOL = matbasistoalg(nf, M);
     864                 :         14 :   MCS = matid(lx-1); /* dummy for gerepile */
     865                 :            : PRECNF:
     866         [ -  + ]:         14 :   if (count == MAX_COUNT)
     867                 :            :   {
     868                 :          0 :     prec = precdbl(prec); count = 0;
     869         [ #  # ]:          0 :     if (DEBUGLEVEL) pari_warn(warnprec,"rnflllgram",prec);
     870                 :          0 :     nf = nfnewprec_shallow(nf,prec);
     871                 :            :   }
     872                 :         14 :   mth = rel_T2(nf, pol, lx, prec);
     873         [ -  + ]:         14 :   if (!mth) { count = MAX_COUNT; goto PRECNF; }
     874                 :         14 :   h = NULL;
     875                 :            : PRECPB:
     876         [ -  + ]:         14 :   if (h)
     877                 :            :   { /* precision problem, recompute. If no progress, increase nf precision */
     878 [ #  # ][ #  # ]:          0 :     if (++count == MAX_COUNT || RgM_isidentity(h)) {count = MAX_COUNT; goto PRECNF;}
     879         [ #  # ]:          0 :     H = H? gmul(H, h): h;
     880                 :          0 :     MPOL = gmul(MPOL, h);
     881                 :            :   }
     882                 :         14 :   h = matid(lx-1);
     883                 :         14 :   MC = mattocomplex(nf, MPOL);
     884                 :         14 :   mu = cgetg(lx,t_MAT);
     885                 :         14 :   B  = cgetg(lx,t_COL);
     886         [ +  + ]:         98 :   for (j=1; j<lx; j++)
     887                 :            :   {
     888                 :         84 :     gel(mu,j) = zerocol(lx - 1);
     889                 :         84 :     gel(B,j) = gen_0;
     890                 :            :   }
     891         [ -  + ]:         14 :   if (DEBUGLEVEL) err_printf("k = ");
     892                 :         14 :   gel(B,1) = real_i(rnfscal(mth,gel(MC,1),gel(MC,1)));
     893                 :         14 :   gel(MCS,1) = gel(MC,1);
     894                 :         14 :   kmax = 1; k = 2;
     895                 :            :   do
     896                 :            :   {
     897                 :         98 :     GEN Ik_inv = NULL;
     898         [ -  + ]:         98 :     if (DEBUGLEVEL) err_printf("%ld ",k);
     899         [ +  + ]:         98 :     if (k > kmax)
     900                 :            :     { /* Incremental Gram-Schmidt */
     901                 :         70 :       kmax = k; gel(MCS,k) = gel(MC,k);
     902         [ +  + ]:        343 :       for (j=1; j<k; j++)
     903                 :            :       {
     904                 :        273 :         gcoeff(mu,k,j) = vecdiv(rnfscal(mth,gel(MCS,j),gel(MC,k)),
     905                 :        273 :                                 gel(B,j));
     906                 :        273 :         gel(MCS,k) = gsub(gel(MCS,k), vecmul(gcoeff(mu,k,j),gel(MCS,j)));
     907                 :            :       }
     908                 :         70 :       gel(B,k) = real_i(rnfscal(mth,gel(MCS,k),gel(MCS,k)));
     909         [ +  - ]:         70 :       if (check_0(gel(B,k))) goto PRECPB;
     910                 :            :     }
     911         [ +  - ]:         98 :     if (!RED(k, k-1, h, mu, MC, nf, I, &Ik_inv)) goto PRECPB;
     912         [ +  + ]:         98 :     if (do_SWAP(I,MC,MCS,h,mu,B,kmax,k,alpha, r1))
     913                 :            :     {
     914         [ +  - ]:         14 :       if (!B[k]) goto PRECPB;
     915         [ +  - ]:         14 :       if (k > 2) k--;
     916                 :            :     }
     917                 :            :     else
     918                 :            :     {
     919         [ +  + ]:        350 :       for (l=k-2; l; l--)
     920         [ +  - ]:        266 :         if (!RED(k, l, h, mu, MC, nf, I, &Ik_inv)) goto PRECPB;
     921                 :         84 :       k++;
     922                 :            :     }
     923         [ -  + ]:         98 :     if (gc_needed(av,2))
     924                 :            :     {
     925         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"rnflllgram");
     926         [ #  # ]:          0 :       gerepileall(av, H?10:9, &nf,&mth,&h,&MPOL,&B,&MC,&MCS,&mu,&I,&H);
     927                 :            :     }
     928                 :            :   }
     929         [ +  + ]:         98 :   while (k < lx);
     930                 :         14 :   MPOL = gmul(MPOL,h);
     931         [ -  + ]:         14 :   if (H) h = gmul(H, h);
     932         [ -  + ]:         14 :   if (DEBUGLEVEL) err_printf("\n");
     933                 :         14 :   MPOL = RgM_to_nfM(nf,MPOL);
     934                 :         14 :   h = RgM_to_nfM(nf,h);
     935                 :         14 :   return gerepilecopy(av, mkvec2(mkvec2(MPOL,I), h));
     936                 :            : }
     937                 :            : 
     938                 :            : GEN
     939                 :          7 : rnfpolred(GEN nf, GEN pol, long prec)
     940                 :            : {
     941                 :          7 :   pari_sp av = avma;
     942                 :          7 :   long i, j, n, v = varn(pol);
     943                 :            :   GEN id, w, I, O, bnf, nfpol;
     944                 :            : 
     945         [ -  + ]:          7 :   if (typ(pol)!=t_POL) pari_err_TYPE("rnfpolred",pol);
     946                 :          7 :   bnf = nf; nf = checknf(bnf);
     947         [ -  + ]:          7 :   bnf = (nf == bnf)? NULL: checkbnf(bnf);
     948         [ -  + ]:          7 :   if (degpol(pol) <= 1) { w = cgetg(2, t_VEC); gel(w,1) = pol_x(v); return w; }
     949                 :          7 :   nfpol = nf_get_pol(nf);
     950                 :            : 
     951                 :          7 :   id = rnfpseudobasis(nf,pol);
     952 [ -  + ][ #  # ]:          7 :   if (bnf && is_pm1( bnf_get_no(bnf) )) /* if bnf is principal */
     953                 :            :   {
     954                 :            :     GEN newI, newO;
     955                 :          0 :     O = gel(id,1);
     956                 :          0 :     I = gel(id,2); n = lg(I)-1;
     957                 :          0 :     newI = cgetg(n+1,t_VEC);
     958                 :          0 :     newO = cgetg(n+1,t_MAT);
     959         [ #  # ]:          0 :     for (j=1; j<=n; j++)
     960                 :            :     {
     961                 :          0 :       GEN al = gen_if_principal(bnf,gel(I,j));
     962                 :          0 :       gel(newI,j) = gen_1;
     963                 :          0 :       gel(newO,j) = nfC_nf_mul(nf, gel(O,j), al);
     964                 :            :     }
     965                 :          0 :     id = mkvec2(newO, newI);
     966                 :            :   }
     967                 :            : 
     968                 :          7 :   id = gel(rnflllgram(nf,pol,id,prec),1);
     969                 :          7 :   O = gel(id,1);
     970                 :          7 :   I = gel(id,2); n = lg(I)-1;
     971                 :          7 :   w = cgetg(n+1,t_VEC);
     972                 :          7 :   pol = lift(pol);
     973         [ +  + ]:         70 :   for (j=1; j<=n; j++)
     974                 :            :   {
     975                 :         63 :     GEN newpol, L, a, Ij = gel(I,j);
     976         [ +  + ]:         63 :     a = RgC_Rg_mul(gel(O,j), (typ(Ij) == t_MAT)? gcoeff(Ij,1,1): Ij);
     977         [ +  + ]:        630 :     for (i=n; i; i--)
     978                 :            :     {
     979                 :        567 :       GEN c = gel(a,i);
     980         [ +  + ]:        567 :       if (typ(c) == t_COL) gel(a,i) = coltoliftalg(nf, c);
     981                 :            :     }
     982                 :         63 :     a = RgV_to_RgX(a, v);
     983                 :         63 :     newpol = RgXQX_red(RgXQ_charpoly(a, pol, v), nfpol);
     984                 :         63 :     newpol = Q_primpart(newpol);
     985                 :            : 
     986                 :         63 :     (void)nfgcd_all(newpol, RgX_deriv(newpol), nfpol, nf_get_index(nf), &newpol);
     987                 :         63 :     L = leading_term(newpol);
     988                 :        126 :     gel(w,j) = (typ(L) == t_POL)? RgXQX_div(newpol, L, nfpol)
     989         [ -  + ]:         63 :                                 : RgX_Rg_div(newpol, L);
     990                 :            :   }
     991                 :          7 :   return gerepilecopy(av,w);
     992                 :            : }

Generated by: LCOV version 1.9