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 - modules - krasner.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.8.0 lcov report (development 16624-25b9976) Lines: 441 448 98.4 %
Date: 2014-06-24 Functions: 35 35 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 198 234 84.6 %

           Branch data     Line data    Source code
       1                 :            : /* Copyright (C) 2009  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                 :            : #include "pari.h"
      15                 :            : #include "paripriv.h"
      16                 :            : 
      17                 :            : /************************************************************/
      18                 :            : /*     Computation of all the extensions of a given         */
      19                 :            : /*               degree of a p-adic field                   */
      20                 :            : /* Xavier Roblot                                            */
      21                 :            : /************************************************************/
      22                 :            : 
      23                 :            : #undef CHECK_EXTENSIONS
      24                 :            : 
      25                 :            : /* cf. Math. Comp, vol. 70, No. 236, pp. 1641-1659 for more details.
      26                 :            :    Note that n is now e (since the e from the paper is always = 1) and l
      27                 :            :    is now f */
      28                 :            : /* Structure for a given type of extension */
      29                 :            : typedef struct {
      30                 :            :   GEN p;
      31                 :            :   long e, f, j;
      32                 :            :   long a, b, c;
      33                 :            :   long v;     /* auxiliary variable */
      34                 :            :   long r;     /* pr = p^r */
      35                 :            :   GEN pr;     /* p-adic precision for poly. reduction */
      36                 :            :   GEN q, qm1; /* p^f, q - 1 */
      37                 :            :   GEN upl;    /* cyclotomic polynomial (in v) generating K^ur (mod pr) */
      38                 :            :   GEN mv;     /* -v mod upl (mod pr) */
      39                 :            :   GEN uplr;   /* upl reduced mod p */
      40                 :            :   GEN frob;   /* Frobenius acting of the root of upl (mod pr) */
      41                 :            :   GEN nbext;  /* number of extensions */
      42                 :            :   GEN roottable; /* table of roots of polynomials over the residue field */
      43                 :            :   GEN pk;     /* powers of p: [p^1, p^2, ..., p^c] */
      44                 :            : } KRASNER_t;
      45                 :            : 
      46                 :            : /* Structure containing the field data (constructed with FieldData) */
      47                 :            : typedef struct {
      48                 :            :   GEN p;
      49                 :            :   GEN top;  /* absolute polynomial with root zq + pi (mod pr) */
      50                 :            :   GEN topr; /* absolute polynomial with root zq + pi (mod p) */
      51                 :            :   GEN eis;  /* relative polynomial with root pi (mod pr) (y=zq) */
      52                 :            :   GEN zq;   /* (q-1)-th root of unity (root of upl) (mod pr) (y=zq+pi) */
      53                 :            :   GEN pi;   /* prime element (mod p) (y=zq+pi)*/
      54                 :            :   GEN ipi;  /* p/pi (mod pr) (y=zq+pi) (used to divide by pi) */
      55                 :            :   GEN pik;  /* [1, pi, ..., pi^(e-1), pi^e / p] (mod pr). Note the last one ! */
      56                 :            :   long cj;  /* number of conjugate fields */
      57                 :            : } FAD_t;
      58                 :            : 
      59                 :            : static long
      60                 :       1195 : ceildiv(ulong a, ulong b)
      61                 :            : {
      62                 :       1195 :   long c = a/b;
      63         [ +  + ]:       1195 :   if (a%b) c++;
      64                 :       1195 :   return c;
      65                 :            : }
      66                 :            : 
      67                 :            : /* Eval P(x) assuming P has positive coefficients and the result is a long */
      68                 :            : static ulong
      69                 :     141087 : ZX_z_eval(GEN P, ulong x)
      70                 :            : {
      71                 :     141087 :   long i, l = lg(P);
      72                 :            :   ulong z;
      73                 :            : 
      74         [ -  + ]:     141087 :   if (typ(P) == t_INT) return itou(P);
      75         [ +  + ]:     141087 :   if (l == 2) return 0;
      76                 :      68806 :   z = itou(gel(P, l-1));
      77         [ +  + ]:     132394 :   for (i = l-2; i > 1; i--) z = z*x + itou(gel(P,i));
      78                 :     141087 :   return z;
      79                 :            : }
      80                 :            : 
      81                 :            : /* Eval P(x, y) assuming P has positive coefficients and the result is a long */
      82                 :            : static ulong
      83                 :      34657 : ZXY_z_eval(GEN P, ulong x, ulong y)
      84                 :            : {
      85                 :      34657 :   long i, l = lg(P);
      86                 :            :   ulong z;
      87                 :            : 
      88         [ -  + ]:      34657 :   if (l == 2) return 0;
      89                 :      34657 :   z = ZX_z_eval(gel(P, l-1), y);
      90         [ +  + ]:     141087 :   for (i = l-2; i > 1; i--) z = z*x + ZX_z_eval(gel(P, i), y);
      91                 :      34657 :   return z;
      92                 :            : }
      93                 :            : 
      94                 :            : /* P an Fq[X], where Fq = Fp[Y]/(T(Y)), a an FpX representing the automorphism
      95                 :            :  * y -> a(y). Return a(P), applying a() coefficientwise. */
      96                 :            : static GEN
      97                 :      31888 : FqX_FpXQ_eval(GEN P, GEN a, GEN T, GEN p)
      98                 :            : {
      99                 :            :   long i, l;
     100                 :      31888 :   GEN Q = cgetg_copy(P, &l);
     101                 :            : 
     102                 :      31888 :   Q[1] = P[1];
     103         [ +  + ]:     146472 :   for (i = 2; i < l; i++)
     104                 :            :   {
     105                 :     114584 :     GEN cf = gel(P, i);
     106         [ +  + ]:     114584 :     if (typ(cf) == t_POL) {
     107      [ +  +  + ]:      77515 :       switch(degpol(cf))
     108                 :            :       {
     109                 :        675 :         case -1: cf = gen_0; break;
     110                 :        398 :         case 0:  cf = gel(cf,2); break;
     111                 :            :         default:
     112                 :      76442 :           cf = FpX_FpXQ_eval(cf, a, T, p);
     113                 :      76442 :           cf = simplify_shallow(cf);
     114                 :      76442 :           break;
     115                 :            :       }
     116                 :            :     }
     117                 :     114584 :     gel(Q, i) = cf;
     118                 :            :   }
     119                 :            : 
     120                 :      31888 :   return Q;
     121                 :            : }
     122                 :            : 
     123                 :            : /* Sieving routines */
     124                 :            : static GEN
     125                 :        355 : InitSieve(long l) { return zero_F2v(l); }
     126                 :            : static long
     127                 :        555 : NextZeroValue(GEN sv, long i)
     128                 :            : {
     129         [ +  + ]:       1350 :   for(; i <= sv[1]; i++)
     130         [ +  + ]:        995 :     if (!F2v_coeff(sv, i)) return i;
     131                 :        555 :   return 0; /* sieve is full or out of the sieve! */
     132                 :            : }
     133                 :            : static void
     134                 :        795 : SetSieveValue(GEN sv, long i)
     135 [ +  - ][ +  - ]:        795 : { if (i >= 1 && i <= sv[1]) F2v_set(sv, i); }
     136                 :            : 
     137                 :            : /* return 1 if the data verify Ore condition and 0 otherwise */
     138                 :            : static long
     139                 :         15 : VerifyOre(GEN p, long e, long j)
     140                 :            : {
     141                 :            :   long nv, b, vb, nb;
     142                 :            : 
     143         [ -  + ]:         15 :   if (j < 0) return 0;
     144                 :         15 :   nv = e * u_pval(e, p);
     145                 :         15 :   b  = j%e;
     146         [ +  + ]:         15 :   if (b == 0) return (j == nv);
     147         [ -  + ]:         10 :   if (j > nv) return 0;
     148                 :            :   /* j < nv */
     149                 :         10 :   vb = u_pval(b, p);
     150                 :         10 :   nb = vb*e;
     151                 :         15 :   return (nb <= j);
     152                 :            : }
     153                 :            : 
     154                 :            : /* Given [K:Q_p] = m and disc(K/Q_p) = p^d, return all decompositions K/K^ur/Q_p
     155                 :            :  * as [e, f, j] with
     156                 :            :  *   K^ur/Q_p unramified of degree f,
     157                 :            :  *   K/K^ur totally ramified of degree e, and discriminant p^(e+j-1);
     158                 :            :  * thus d = f*(e+j-1) and j > 0 iff ramification is wild */
     159                 :            : static GEN
     160                 :          5 : possible_efj_by_d(GEN p, long m, long d)
     161                 :            : {
     162                 :            :   GEN rep, div;
     163                 :            :   long i, ctr, l;
     164                 :            : 
     165         [ -  + ]:          5 :   if (d == 0) return mkvec(mkvecsmall3(1, m, 0)); /* unramified */
     166                 :          5 :   div = divisorsu(ugcd(m, d));
     167                 :          5 :   l = lg(div); ctr = 1;
     168                 :          5 :   rep = cgetg(l, t_VEC);
     169         [ +  + ]:         20 :   for (i = 1; i < l; i++)
     170                 :            :   {
     171                 :         15 :     long f = div[i], e = m/f, j = d/f - e + 1;
     172         [ +  - ]:         15 :     if (VerifyOre(p, e, j)) gel(rep, ctr++) = mkvecsmall3(e, f, j);
     173                 :            :   }
     174                 :          5 :   setlg(rep, ctr); return rep;
     175                 :            : }
     176                 :            : 
     177                 :            : /* return the number of extensions corresponding to (e,f,j) */
     178                 :            : static GEN
     179                 :       1195 : NumberExtensions(KRASNER_t *data)
     180                 :            : {
     181                 :            :   ulong pp, pa;
     182                 :            :   long e, a, b;
     183                 :            :   GEN p, q, s0, p1;
     184                 :            : 
     185                 :       1195 :   e = data->e;
     186                 :       1195 :   p = data->p;
     187                 :       1195 :   q = data->q;
     188                 :       1195 :   a = data->a; /* floor(j/e) <= v_p(e), hence p^a | e */
     189                 :       1195 :   b = data->b; /* j % e */
     190         [ +  + ]:       1195 :   if (is_bigint(p)) /* implies a = 0 */
     191         [ +  - ]:         50 :     return b == 0? utoipos(e): mulsi(e, data->qm1);
     192                 :            : 
     193                 :       1145 :   pp = p[2];
     194      [ +  +  + ]:       1145 :   switch(a)
     195                 :            :   {
     196                 :       1115 :     case 0:  pa = 1;  s0 = utoipos(e); break;
     197                 :         25 :     case 1:  pa = pp; s0 = mului(e, powiu(q, e / pa)); break;
     198                 :            :     default:
     199                 :          5 :       pa = upowuu(pp, a); /* p^a */
     200                 :          5 :       s0 = mulsi(e, powiu(q, (e / pa) * ((pa - 1) / (pp - 1))));
     201                 :            :   }
     202                 :            :   /* s0 = e * q^(e*sum(p^-i, i=1...a)) */
     203         [ +  + ]:       1145 :   if (b == 0) return s0;
     204                 :            : 
     205                 :            :   /* q^floor((b-1)/p^(a+1)) */
     206                 :         40 :   p1 = powiu(q, sdivsi(b-1, muluu(pa, pp)));
     207                 :       1195 :   return mulii(mulii(data->qm1, s0), p1);
     208                 :            : }
     209                 :            : 
     210                 :            : static GEN
     211                 :       2115 : get_topx(KRASNER_t *data, GEN eis)
     212                 :            : {
     213                 :            :   GEN p1, p2, rpl;
     214                 :            :   long j;
     215                 :            :   pari_sp av, lim;
     216                 :            :   /* top poly. is the minimal polynomial of root(pol) + root(upl) */
     217                 :       2115 :   rpl = FqX_translate(FqX_red(eis, data->upl, data->pr),
     218                 :            :                       data->mv, data->upl, data->pr);
     219                 :       2115 :   p1 = p2 = rpl;
     220                 :       2115 :   av = avma; lim = stack_lim(av, 1);
     221         [ +  + ]:      16065 :   for (j = 1; j < data->f; j++)
     222                 :            :   {
     223                 :      13950 :     p1 = FqX_FpXQ_eval(p1, data->frob, data->upl, data->pr);
     224                 :      13950 :     p2 = FqX_mul(p2, p1, data->upl, data->pr);
     225         [ +  + ]:      13950 :     if (low_stack(lim, stack_lim(av, 1))) gerepileall(av, 2, &p1, &p2);
     226                 :            :   }
     227                 :       2115 :   return simplify_shallow(p2); /* ZX */
     228                 :            : }
     229                 :            : 
     230                 :            : /* eis (ZXY): Eisenstein polynomial  over the field defined by upl.
     231                 :            :  * topx (ZX): corresponding absolute equation.
     232                 :            :  * Return the struct FAD corresponding to the field it defines (GENs created
     233                 :            :  * as clones). Assume e > 1. */
     234                 :            : static void
     235                 :        440 : FieldData(KRASNER_t *data, FAD_t *fdata, GEN eis, GEN topx)
     236                 :            : {
     237                 :            :   GEN p1, zq, ipi, cipi, dipi, t, Q;
     238                 :            : 
     239                 :        440 :   fdata->p = data->p;
     240                 :        440 :   t = leafcopy(topx); setvarn(t, data->v);
     241                 :        440 :   fdata->top  = t;
     242                 :        440 :   fdata->topr = FpX_red(t, data->pr);
     243                 :            : 
     244                 :        440 :   zq  = pol_x(data->v);
     245                 :            :   /* FIXME: do as in CycloPol (not so easy) */
     246                 :            :   for(;;)
     247                 :            :   {
     248                 :       2501 :     GEN zq2 = zq;
     249                 :       2501 :     zq = Fq_pow(zq, data->q, fdata->top, data->pr);
     250         [ +  + ]:       2501 :     if (gequal(zq, zq2)) break;
     251                 :       2061 :   }
     252                 :        440 :   fdata->zq  = zq;
     253                 :        440 :   fdata->eis = eis;
     254                 :        440 :   fdata->pi  = Fq_sub(pol_x(data->v), fdata->zq,
     255                 :            :                       FpX_red(fdata->top, data->p), data->p);
     256                 :        440 :   ipi = RgXQ_inv(fdata->pi, fdata->top);
     257                 :        440 :   ipi = Q_remove_denom(ipi, &dipi);
     258                 :        440 :   Q = mulii(data->pr, data->p);
     259                 :        440 :   cipi = Fp_inv(diviiexact(dipi, data->p), Q);
     260                 :        440 :   fdata->ipi = FpX_Fp_mul(ipi, cipi, Q); /* p/pi mod p^(pr+1) */
     261                 :            : 
     262                 :            :   /* Last one is in fact pi^e/p */
     263                 :        440 :   p1 = FpXQ_powers(fdata->pi, data->e, fdata->topr, data->pr);
     264                 :        440 :   gel(p1, data->e+1) = ZX_Z_divexact(gel(p1, data->e+1), data->p);
     265                 :        440 :   fdata->pik  = p1;
     266                 :        440 : }
     267                 :            : 
     268                 :            : /* return pol*ipi/p (mod top, pp) if it has integral coefficient, NULL
     269                 :            :    otherwise. The result is reduced mod top, pp */
     270                 :            : static GEN
     271                 :     250102 : DivideByPi(FAD_t *fdata, GEN pp, GEN ppp, GEN pol)
     272                 :            : {
     273                 :            :   GEN P;
     274                 :            :   long i, l;
     275                 :     250102 :   pari_sp av = avma;
     276                 :            : 
     277                 :            :   /* "pol" is a t_INT or an FpX: signe() works for both */
     278         [ +  + ]:     250102 :   if (!signe(pol)) return pol;
     279                 :            : 
     280                 :     250094 :   P = Fq_mul(pol, fdata->ipi, fdata->top, ppp); /* FpX */
     281                 :     250094 :   l  = lg(P);
     282         [ +  + ]:    1235513 :   for (i = 2; i < l; i++)
     283                 :            :   {
     284                 :            :     GEN r;
     285                 :    1054583 :     gel(P,i) = dvmdii(gel(P,i), fdata->p, &r);
     286         [ +  + ]:    1054583 :     if (r != gen_0) { avma = av; return NULL; }
     287                 :            :   }
     288                 :     250102 :   return FpX_red(P, pp);
     289                 :            : }
     290                 :            : 
     291                 :            : /* return pol# = pol~/pi^vpi(pol~) mod pp where pol~(x) = pol(pi.x + beta)
     292                 :            :  * has coefficients in the field defined by top and pi is a prime element */
     293                 :            : static GEN
     294                 :      34582 : GetSharp(FAD_t *fdata, GEN pp, GEN ppp, GEN pol, GEN beta, long *pl)
     295                 :            : {
     296                 :            :   GEN p1, p2;
     297                 :      34582 :   long i, v, l, d = degpol(pol);
     298                 :      34582 :   pari_sp av = avma;
     299                 :            : 
     300         [ +  + ]:      34582 :   if (!gequal0(beta))
     301                 :      28021 :     p1 = FqX_translate(pol, beta, fdata->topr, pp);
     302                 :            :   else
     303                 :       6561 :     p1 = shallowcopy(pol);
     304                 :      34582 :   p2 = p1;
     305                 :      34582 :   for (v = 0;; v++)
     306                 :            :   {
     307         [ +  + ]:     269496 :     for (i = 0; i <= v; i++)
     308                 :            :     {
     309                 :     193599 :       GEN c = gel(p2, i+2);
     310                 :     193599 :       c = DivideByPi(fdata, pp, ppp, c);
     311         [ +  + ]:     193599 :       if (!c) break;
     312                 :     159017 :       gel(p2, i+2) = c;
     313                 :            :     }
     314         [ +  + ]:     110479 :     if (i <= v) break;
     315                 :      75897 :     p1 = shallowcopy(p2);
     316                 :      75897 :   }
     317         [ -  + ]:      34582 :   if (!v) pari_err_BUG("GetSharp [no division]");
     318                 :            : 
     319         [ +  - ]:      56503 :   for (l = v; l >= 0; l--)
     320                 :            :   {
     321                 :      56503 :     GEN c = gel(p1, l+2);
     322                 :      56503 :     c = DivideByPi(fdata, pp, ppp, c);
     323         [ +  + ]:      56503 :     if (!c) { break; }
     324                 :            :   }
     325                 :            : 
     326         [ +  + ]:      34582 :   *pl = l; if (l < 2) return NULL;
     327                 :            : 
     328                 :            :   /* adjust powers */
     329         [ +  + ]:      25452 :   for (i = v+1; i <= d; i++)
     330                 :       7488 :     gel(p1, i+2) = Fq_mul(gel(p1, i+2),
     331                 :       7488 :                           gel(fdata->pik, i-v+1), fdata->topr, pp);
     332                 :            : 
     333                 :      34582 :   return gerepilecopy(av, normalizepol(p1));
     334                 :            : }
     335                 :            : 
     336                 :            : #ifdef CHECK_EXTENSIONS
     337                 :            : static void
     338                 :            : PrintValuations(GEN pol, GEN mod, GEN p)
     339                 :            : {
     340                 :            :   long i, d = degpol(pol);
     341                 :            :   for (i = 0; i <= d; i++)
     342                 :            :     err_printf("%d ", Z_pval(RgXQ_norm(gel(pol, i+2), mod), p));
     343                 :            : }
     344                 :            : 
     345                 :            : /* Return the degree of pol mod the prime ideal of top */
     346                 :            : static long
     347                 :            : DegreeMod(FAD_t *fdata, GEN pp, GEN ppp, GEN pol)
     348                 :            : {
     349                 :            :   long d = degpol(pol); /* should be > 0 */
     350                 :            :   pari_sp av = avma;
     351                 :            : 
     352                 :            :   do
     353                 :            :   {
     354                 :            :     GEN c = gel(pol, d+2);
     355                 :            :     if (!gequal0(c) && !DivideByPi(fdata, pp, ppp, c))
     356                 :            :       return d;
     357                 :            :   }
     358                 :            :   while (--d >= 1);
     359                 :            :   avma = av; return 0;
     360                 :            : }
     361                 :            : #endif
     362                 :            : 
     363                 :            : /* Compute roots of pol in the residue field. Use table look-up if possible */
     364                 :            : static GEN
     365                 :      34657 : Quick_FqX_roots(KRASNER_t *data, GEN pol)
     366                 :            : {
     367                 :            :   GEN rts;
     368                 :      34657 :   ulong ind = 0;
     369                 :            : 
     370                 :      34657 :   pol = FpXQX_red(pol, data->uplr, data->p);
     371                 :            : 
     372         [ +  - ]:      34657 :   if (data->roottable)
     373                 :            :   {
     374                 :      34657 :     ind = ZXY_z_eval(pol, data->q[2], data->p[2]);
     375         [ +  + ]:      34657 :     if (gel(data->roottable, ind)) return gel(data->roottable, ind);
     376                 :            :   }
     377                 :       1805 :   rts = FqX_roots(pol, data->uplr, data->p);
     378                 :            : 
     379         [ +  - ]:       1805 :   if (ind) gel(data->roottable, ind) = gclone(rts);
     380                 :      34657 :   return rts;
     381                 :            : }
     382                 :            : 
     383                 :            : static void
     384                 :         55 : FreeRootTable(GEN T)
     385                 :            : {
     386         [ +  - ]:         55 :   if (T)
     387                 :            :   {
     388                 :         55 :     long j, l = lg(T);
     389         [ +  + ]:      29815 :     for (j = 1; j < l; j++)
     390         [ +  + ]:      29760 :       if (gel(T,j)) gunclone(gel(T,j));
     391                 :            :   }
     392                 :         55 : }
     393                 :            : 
     394                 :            : /* Return the number of roots of pol congruent to alpha modulo pi working
     395                 :            :    modulo pp (all roots if alpha is NULL); if flag is non-zero, return 1
     396                 :            :    as soon as a root is found. (Note: ppp = pp*p for DivideByPi) */
     397                 :            : static long
     398                 :      51275 : RootCongruents(KRASNER_t *data, FAD_t *fdata, GEN pol, GEN alpha, GEN pp, GEN ppp, long sl, long flag)
     399                 :            : {
     400                 :            :   GEN R;
     401                 :            :   long s, i;
     402                 :            : 
     403         [ +  + ]:      51275 :   if (alpha)
     404                 :            :   { /* FIXME: the data used in GetSharp is not reduced */
     405                 :            :     long l;
     406                 :      34582 :     pol = GetSharp(fdata, pp, ppp, pol, alpha, &l);
     407         [ +  + ]:      34582 :     if (l <= 1) return l;
     408                 :            : #ifdef CHECK_EXTENSIONS
     409                 :            :     if (l != DegreeMod(fdata, pp, ppp, pol))
     410                 :            :       pari_err_BUG("RootCongruents [degree mismatch in RCA]");
     411                 :            : #endif
     412                 :            :     /* decrease precision if sl gets bigger than a multiple of e */
     413                 :      17964 :     sl += l;
     414         [ +  + ]:      17964 :     if (sl >= data->e)
     415                 :            :     {
     416                 :      15613 :       sl -= data->e;
     417                 :      15613 :       ppp = pp;
     418                 :      17964 :       pp = diviiexact(pp, data->p);
     419                 :            :     }
     420                 :            :   }
     421                 :            : 
     422                 :      34657 :   R  = Quick_FqX_roots(data, pol);
     423         [ +  + ]:      64786 :   for (s = 0, i = 1; i < lg(R); i++)
     424                 :            :   {
     425                 :      34582 :     s += RootCongruents(data, fdata, pol, gel(R, i), pp, ppp, sl, flag);
     426 [ +  + ][ +  + ]:      34582 :     if (flag && s) return 1;
     427                 :            :   }
     428                 :      51275 :   return s;
     429                 :            : }
     430                 :            : 
     431                 :            : /* pol is a ZXY defining a polynomial over the field defined by fdata
     432                 :            :    If flag != 0, return 1 as soon as a root is found. Precision are done with
     433                 :            :    a precision of pr. */
     434                 :            : static long
     435                 :      16693 : RootCountingAlgorithm(KRASNER_t *data, FAD_t *fdata, GEN pol, long flag)
     436                 :            : {
     437                 :            :   long j, l, d;
     438                 :      16693 :   GEN P = cgetg_copy(pol, &l);
     439                 :            : 
     440                 :      16693 :   P[1] = pol[1];
     441                 :      16693 :   d = l-3;
     442         [ +  + ]:      71785 :   for (j = 0; j < d; j++)
     443                 :            :   {
     444                 :      55092 :     GEN cf = gel(pol, j+2);
     445         [ +  + ]:      55092 :     if (typ(cf) == t_INT)
     446                 :      25936 :       cf = diviiexact(cf, data->p);
     447                 :            :     else
     448                 :      29156 :       cf = ZX_Z_divexact(cf, data->p);
     449                 :      55092 :     gel(P, j+2) = Fq_mul(cf, gel(fdata->pik, j+1), fdata->topr, data->pr);
     450                 :            :   }
     451                 :      16693 :   gel(P, d+2) = gel(fdata->pik, d+1); /* pik[d] = pi^d/p */
     452                 :            : 
     453                 :      16693 :   return RootCongruents(data, fdata, P, NULL, diviiexact(data->pr, data->p), data->pr, 0, flag);
     454                 :            : }
     455                 :            : 
     456                 :            : /* Return non-zero if the field given by fdata defines a field isomorphic to
     457                 :            :  * the one defined by pol */
     458                 :            : static long
     459                 :       9471 : IsIsomorphic(KRASNER_t *data, FAD_t *fdata, GEN pol)
     460                 :            : {
     461                 :            :   long j, nb;
     462                 :       9471 :   pari_sp av = avma;
     463                 :            : 
     464         [ +  + ]:       9471 :   if (RgX_is_ZX(pol)) return RootCountingAlgorithm(data, fdata, pol, 1);
     465                 :            : 
     466         [ +  + ]:      14157 :   for (j = 1; j <= data->f; j++)
     467                 :            :   {
     468                 :      10696 :     GEN p1 = FqX_FpXQ_eval(pol, fdata->zq, fdata->top, data->pr);
     469                 :      10696 :     nb = RootCountingAlgorithm(data, fdata, p1, 1);
     470         [ +  + ]:      10696 :     if (nb) { avma = av; return nb; }
     471         [ +  + ]:       9953 :     if (j < data->f)
     472                 :       6492 :       pol = FqX_FpXQ_eval(pol, data->frob, data->upl, data->pr);
     473                 :            :   }
     474                 :       9471 :   avma = av; return 0;
     475                 :            : }
     476                 :            : 
     477                 :            : /* Compute the number of conjugates fields of the field given by fdata */
     478                 :            : static void
     479                 :        440 : NbConjugateFields(KRASNER_t *data, FAD_t *fdata)
     480                 :            : {
     481                 :        440 :   GEN pol = fdata->eis;
     482                 :            :   long j, nb;
     483                 :        440 :   pari_sp av = avma;
     484                 :            : 
     485         [ +  + ]:        440 :   if (RgX_is_ZX(pol)) { /* split for efficiency; contains the case f = 1 */
     486                 :        270 :     fdata->cj = data->e / RootCountingAlgorithm(data, fdata, pol, 0);
     487                 :        270 :     avma = av; return;
     488                 :            :   }
     489                 :            : 
     490                 :        170 :   nb = 0;
     491         [ +  + ]:        630 :   for (j = 1; j <= data->f; j++)
     492                 :            :   {
     493                 :        460 :     GEN p1 = FqX_FpXQ_eval(pol, fdata->zq, fdata->top, data->pr);
     494                 :        460 :     nb += RootCountingAlgorithm(data, fdata, p1, 0);
     495         [ +  + ]:        460 :     if (j < data->f)
     496                 :        290 :       pol = FqX_FpXQ_eval(pol, data->frob, data->upl, data->pr);
     497                 :            :   }
     498                 :        170 :   avma = av;
     499                 :        170 :   fdata->cj = data->e * data->f / nb;
     500                 :        440 :   return;
     501                 :            : }
     502                 :            : 
     503                 :            : /* return a minimal list of polynomials generating all the totally
     504                 :            :    ramified extensions of K^ur of degree e and discriminant
     505                 :            :    p^{e + j - 1} in the tamely ramified case */
     506                 :            : static GEN
     507                 :       1120 : TamelyRamifiedCase(KRASNER_t *data)
     508                 :            : {
     509                 :       1120 :   long av = avma, g;
     510                 :       1120 :   GEN rep, p2, topx, m, eis, Xe = gpowgs(pol_x(0), data->e);
     511                 :            : 
     512                 :            : #ifdef CHECK_EXTENSIONS
     513                 :            :   FAD_t fdata;
     514                 :            :   long cnt = 0, nb, j;
     515                 :            :   GEN vpl;
     516                 :            :   err_printf("Number of extensions: %ld\n", itos(data->nbext));
     517                 :            : #endif
     518                 :            : 
     519                 :       1120 :   g   = ugcd(data->e, umodiu(data->qm1, data->e)); /* (e, q-1) */
     520                 :       1120 :   m   = stoi(data->e/g);
     521                 :       1120 :   rep = zerovec(g);
     522                 :            : 
     523                 :       1120 :   eis = gadd(Xe, data->p);
     524                 :       1120 :   topx = get_topx(data, eis);
     525                 :       1120 :   p2 = mkvec2(topx, m);
     526                 :       1120 :   gel(rep, 1) = p2;
     527                 :            : #ifdef CHECK_EXTENSIONS
     528                 :            :   vpl = zerovec(g);
     529                 :            :   gel(vpl, 1) = eis;
     530                 :            :   if (data->e == 1)
     531                 :            :     nb = 1;
     532                 :            :   else
     533                 :            :   {
     534                 :            :     FieldData(data, &fdata, eis, topx);
     535                 :            :     NbConjugateFields(data, &fdata);
     536                 :            :     nb = fdata.cj;
     537                 :            :   }
     538                 :            :   err_printf("Found %ld field(s)\n", nb);
     539                 :            :   cnt += nb;
     540                 :            : #endif
     541                 :            : 
     542         [ +  + ]:       1120 :   if (g > 1)
     543                 :            :   {
     544                 :        355 :     ulong pmodg = umodiu(data->p, g);
     545                 :        355 :     long r = 1, ct = 1;
     546                 :        355 :     GEN sv = InitSieve(g-1);
     547         [ +  + ]:        910 :     while (r)
     548                 :            :     {
     549                 :            :       long gr;
     550                 :        555 :       GEN p1 = FpXQ_powu(pol_x(data->v), r, data->uplr, data->p);
     551                 :        555 :       eis = gadd(Xe, ZX_Z_mul(p1, data->p)); /* Adding a ZX and a ZY (cste coefficient) */
     552                 :        555 :       ct++;
     553                 :        555 :       topx = get_topx(data, eis);
     554                 :        555 :       p2 = mkvec2(topx, m);
     555                 :        555 :       gel(rep, ct) = p2;
     556                 :            : #ifdef CHECK_EXTENSIONS
     557                 :            :       gel(vpl, ct) = eis;
     558                 :            :       FieldData(data, &fdata, eis, topx);
     559                 :            :       for (j = 1; j < ct; j++)
     560                 :            :         if (IsIsomorphic(data, &fdata, gel(vpl, j)))
     561                 :            :           pari_err_BUG("TamelyRamifiedCase [isomorphic fields]");
     562                 :            :       NbConjugateFields(data, &fdata);
     563                 :            :       nb = fdata.cj;
     564                 :            :       err_printf("Found %ld field(s)\n", nb);
     565                 :            :       cnt += nb;
     566                 :            : #endif
     567                 :        555 :       gr = r;
     568                 :            :       do
     569                 :            :       {
     570                 :        795 :         SetSieveValue(sv, gr);
     571                 :        795 :         gr = Fl_mul(gr, pmodg, g);
     572                 :            :       }
     573         [ +  + ]:        795 :       while (gr != r);
     574                 :        555 :       r  = NextZeroValue(sv, r);
     575                 :            :     }
     576                 :        355 :     setlg(rep, ct+1);
     577                 :            :   }
     578                 :            : 
     579                 :            : #ifdef CHECK_EXTENSIONS
     580                 :            :   if (!equaliu(data->nbext, cnt))
     581                 :            :     pari_err_BUG("TamelyRamifiedCase [incorrect #fields]");
     582                 :            : #endif
     583                 :            : 
     584                 :       1120 :   return gerepilecopy(av, rep);
     585                 :            : }
     586                 :            : 
     587                 :            : static long
     588                 :        155 : function_l(GEN p, long a, long b, long i)
     589                 :            : {
     590                 :        155 :   long l = 1 + a - z_pval(i, p);
     591         [ +  + ]:        155 :   if (i < b) l++;
     592                 :        155 :   return (l < 1)? 1: l;
     593                 :            : }
     594                 :            : 
     595                 :            : /* Structure of the coefficients set Omega. Each coefficient is [start, zr]
     596                 :            :  * meaning all the numbers of the form:
     597                 :            :  *   zeta_0 * p^start + ... + zeta_s * p^c (s = c - start)
     598                 :            :  * with zeta_i roots of unity (powers of zq + zero), zeta_0 = 0 is
     599                 :            :  * possible iff zr = 1 */
     600                 :            : static GEN
     601                 :         55 : StructureOmega(KRASNER_t *data, GEN *pnbpol)
     602                 :            : {
     603                 :         55 :   GEN nbpol, O = cgetg(data->e + 1, t_VEC);
     604                 :            :   long i;
     605                 :            : 
     606                 :            :   /* i = 0 */
     607                 :         55 :   gel(O, 1) = mkvecsmall2(1, 0);
     608                 :         55 :   nbpol = mulii(data->qm1, powiu(data->q, data->c - 1));
     609         [ +  + ]:        210 :   for (i = 1; i < data->e; i++)
     610                 :            :   {
     611                 :        155 :     long v_start, zero = 0;
     612                 :            :     GEN nbcf, p1;
     613                 :        155 :     v_start = function_l(data->p, data->a, data->b, i);
     614                 :        155 :     p1 = powiu(data->q, data->c - v_start);
     615         [ +  + ]:        155 :     if (i == data->b)
     616                 :         40 :       nbcf = mulii(p1, data->qm1);
     617                 :            :     else
     618                 :            :     {
     619                 :        115 :       nbcf = mulii(p1, data->q);
     620                 :        115 :       zero = 1;
     621                 :            :     }
     622                 :        155 :     gel(O, i+1) = mkvecsmall2(v_start, zero);
     623                 :        155 :     nbpol = mulii(nbpol, nbcf);
     624                 :            :   }
     625                 :         55 :   *pnbpol = nbpol; return O;
     626                 :            : }
     627                 :            : 
     628                 :            : /* a random element of the finite field */
     629                 :            : static GEN
     630                 :      26136 : RandomFF(KRASNER_t *data)
     631                 :            : {
     632                 :      26136 :   long i, l = data->f + 2, p = itou(data->p);
     633                 :      26136 :   GEN c = cgetg(l, t_POL);
     634                 :      26136 :   c[1] = evalvarn(data->v);
     635         [ +  + ]:      65583 :   for (i = 2; i < l; i++) gel(c, i) = utoi(random_Fl(p));
     636                 :      26136 :   return ZX_renormalize(c, l);
     637                 :            : }
     638                 :            : static GEN
     639                 :       1848 : RandomPol(KRASNER_t *data, GEN Omega)
     640                 :            : {
     641                 :       1848 :   long i, j, l = data->e + 3, end = data->c;
     642                 :       1848 :   GEN pol = cgetg(l, t_POL);
     643                 :       1848 :   pol[1] = evalsigne(1) | evalvarn(0);
     644         [ +  + ]:       8692 :   for (i = 1; i <= data->e; i++)
     645                 :            :   {
     646                 :       6844 :     GEN c, cf = gel(Omega, i);
     647                 :       6844 :     long st = cf[1], zr = cf[2];
     648                 :            :     /* c = sum_{st <= j <= end} x_j p^j, where x_j are random Fq mod (p,upl)
     649                 :            :      * If (!zr), insist on x_st != 0 */
     650                 :            :     for (;;) {
     651                 :       8724 :       c = RandomFF(data);
     652 [ +  + ][ +  + ]:       8724 :       if (zr || signe(c)) break;
     653                 :       1880 :     }
     654         [ +  + ]:      24256 :     for (j = 1; j <= end-st; j++)
     655                 :      17412 :       c = ZX_add(c, ZX_Z_mul(RandomFF(data), gel(data->pk, j)));
     656                 :       6844 :     c = ZX_Z_mul(c, gel(data->pk, st));
     657                 :       6844 :     c = FpX_red(c, data->pr);
     658      [ +  +  + ]:       6844 :     switch(degpol(c))
     659                 :            :     {
     660                 :        396 :       case -1: c = gen_0; break;
     661                 :       3949 :       case  0: c = gel(c,2); break;
     662                 :            :     }
     663                 :       6844 :     gel(pol, i+1) = c;
     664                 :            :   }
     665                 :       1848 :   gel(pol, i+1) = gen_1; /* monic */
     666                 :       1848 :   return pol;
     667                 :            : }
     668                 :            : 
     669                 :            : static void
     670                 :        440 : CloneFieldData(FAD_t *fdata)
     671                 :            : {
     672                 :        440 :  fdata->top = gclone(fdata->top);
     673                 :        440 :  fdata->topr= gclone(fdata->topr);
     674                 :        440 :  fdata->zq  = gclone(fdata->zq);
     675                 :        440 :  fdata->eis = gclone(fdata->eis);
     676                 :        440 :  fdata->pi  = gclone(fdata->pi);
     677                 :        440 :  fdata->ipi = gclone(fdata->ipi);
     678                 :        440 :  fdata->pik = gclone(fdata->pik);
     679                 :        440 : }
     680                 :            : static void
     681                 :        440 : FreeFieldData(FAD_t *fdata)
     682                 :            : {
     683                 :        440 :   gunclone(fdata->top);
     684                 :        440 :   gunclone(fdata->topr);
     685                 :        440 :   gunclone(fdata->zq);
     686                 :        440 :   gunclone(fdata->eis);
     687                 :        440 :   gunclone(fdata->pi);
     688                 :        440 :   gunclone(fdata->ipi);
     689                 :        440 :   gunclone(fdata->pik);
     690                 :        440 : }
     691                 :            : 
     692                 :            : static GEN
     693                 :         55 : WildlyRamifiedCase(KRASNER_t *data)
     694                 :            : {
     695                 :         55 :   long nbext, ct, fd, nb = 0, j;
     696                 :            :   GEN nbpol, rpl, rep, Omega;
     697                 :            :   FAD_t **vfd;
     698                 :            :   pari_timer T;
     699                 :         55 :   pari_sp av = avma, av2;
     700                 :            : 
     701                 :            :   /* Omega = vector giving the structure of the set Omega */
     702                 :            :   /* nbpol = number of polynomials to consider = |Omega| */
     703                 :         55 :   Omega = StructureOmega(data, &nbpol);
     704                 :         55 :   nbext = itos_or_0(data->nbext);
     705 [ +  - ][ -  + ]:         55 :   if (!nbext || (nbext & ~LGBITS))
     706                 :          0 :     pari_err_OVERFLOW("padicfields [too many extensions]");
     707                 :            : 
     708         [ -  + ]:         55 :   if (DEBUGLEVEL>0) {
     709                 :          0 :     err_printf("There are %ld extensions to find and %Ps polynomials to consider\n", nbext, nbpol);
     710                 :          0 :     timer_start(&T);
     711                 :            :   }
     712                 :            : 
     713                 :         55 :   vfd = (FAD_t**)new_chunk(nbext);
     714         [ +  + ]:       1145 :   for (j = 0; j < nbext; j++) vfd[j] = (FAD_t*)new_chunk(sizeof(FAD_t));
     715                 :            : 
     716                 :         55 :   ct = 0;
     717                 :         55 :   fd = 0;
     718                 :         55 :   av2 = avma;
     719                 :            : 
     720         [ +  + ]:       1903 :   while (fd < nbext)
     721                 :            :   { /* Jump randomly among the polynomials : seems best... */
     722                 :       1848 :     rpl = RandomPol(data, Omega);
     723         [ -  + ]:       1848 :     if (DEBUGLEVEL>3) err_printf("considering polynomial %Ps\n", rpl);
     724                 :            : #ifdef CHECK_EXTENSIONS
     725                 :            :     {
     726                 :            :       GEN disc = poldisc0(rpl, 0);
     727                 :            :       long e = data->e, f = data->f, j = data->j;
     728                 :            :       disc = RgXQ_norm(disc, data->upl);
     729                 :            :       if (Z_pval(disc, data->p) != f*(e+j-1))
     730                 :            :         pari_err_BUG("WildlyRamifiedCase [incorrect discriminant]");
     731                 :            :     }
     732                 :            : #endif
     733                 :            : 
     734         [ +  + ]:       9911 :     for (j = 0; j < ct; j++)
     735                 :            :     {
     736                 :       9471 :       nb = IsIsomorphic(data, vfd[j], rpl);
     737         [ +  + ]:       9471 :       if (nb) break;
     738                 :            :     }
     739         [ +  + ]:       1848 :     if (!nb)
     740                 :            :     {
     741                 :        440 :       GEN topx = get_topx(data, rpl);
     742                 :        440 :       FAD_t *fdata = (FAD_t*)vfd[ct];
     743                 :        440 :       FieldData(data, fdata, rpl, topx);
     744                 :        440 :       CloneFieldData(fdata);
     745                 :        440 :       NbConjugateFields(data, fdata);
     746                 :        440 :       nb = fdata->cj;
     747                 :        440 :       fd += nb;
     748                 :        440 :       ct++;
     749         [ -  + ]:        440 :       if (DEBUGLEVEL>1)
     750         [ #  # ]:          0 :         err_printf("%ld more extension%s\t(%ld/%ld, %ldms)\n",
     751                 :            :                    nb, (nb == 1)? "": "s", fd, nbext, timer_delay(&T));
     752                 :            :     }
     753                 :       1848 :     avma = av2;
     754                 :            :   }
     755                 :            : 
     756                 :         55 :   rep = cgetg(ct+1, t_VEC);
     757         [ +  + ]:        495 :   for (j = 0; j < ct; j++)
     758                 :            :   {
     759                 :        440 :     GEN topx = ZX_copy(((FAD_t*)vfd[j])->top);
     760                 :            :     GEN p1;
     761                 :        440 :     setvarn(topx, 0);
     762                 :        440 :     p1 = mkvec2(topx, stoi(((FAD_t*)vfd[j])->cj));
     763                 :        440 :     gel(rep, j+1) = p1;
     764                 :        440 :     FreeFieldData((FAD_t*)vfd[j]);
     765                 :            :   }
     766                 :         55 :   FreeRootTable(data->roottable);
     767                 :         55 :   return gerepileupto(av, rep);
     768                 :            : }
     769                 :            : 
     770                 :            : /* return the minimal polynomial (mod pr) of an element nu of (F_q)^x
     771                 :            :  * where q = p^f that is l-maximal for all primes l dividing g = (e,q-1). */
     772                 :            : static GEN
     773                 :       1175 : CycloPol(KRASNER_t *d)
     774                 :            : {
     775                 :       1175 :   long v = d->v, e = d->e, f = d->f;
     776                 :       1175 :   GEN T, z, fa, p = d->p;
     777                 :            : 
     778                 :            :   /* v - primroot(p) */
     779         [ +  + ]:       1175 :   if (d->f == 1)
     780                 :        360 :     return deg1pol_shallow(gen_1, Fp_neg(pgener_Fp(p), d->pr), v);
     781                 :            : 
     782                 :        815 :   T = init_Fq(d->p, d->f, v);
     783                 :        815 :   fa = factoru( ugcd(e, umodiu(subiu(powiu(p,f),1), e)) );
     784                 :        815 :   z = gener_FpXQ_local(T, d->p, zv_to_ZV(gel(fa,1)));
     785                 :        815 :   z = ZpXQ_sqrtnlift(scalarpol(gen_1,varn(T)), d->qm1, z, T, d->p, d->r);
     786                 :       1175 :   return FpX_red(ZXQ_charpoly(z, T, v), d->pr);
     787                 :            : }
     788                 :            : 
     789                 :            : /* return [ p^1, p^2, ..., p^c ] */
     790                 :            : static GEN
     791                 :         55 : get_pk(KRASNER_t *data)
     792                 :            : {
     793                 :         55 :   long i, l = data->c + 1;
     794                 :         55 :   GEN pk = cgetg(l, t_VEC), p = data->p;
     795                 :         55 :   gel(pk, 1) = p;
     796         [ +  + ]:        210 :   for (i = 2; i <= data->c; i++) gel(pk, i) = mulii(gel(pk, i-1), p);
     797                 :         55 :   return pk;
     798                 :            : }
     799                 :            : 
     800                 :            : /* Compute an absolute polynomial for all the totally ramified
     801                 :            :    extensions of Q_p(z) of degree e and discriminant p^{e + j - 1}
     802                 :            :    where z is a root of upl defining an unramified extension of Q_p */
     803                 :            : /* See padicfields for the meaning of flag */
     804                 :            : static GEN
     805                 :       1195 : GetRamifiedPol(GEN p, GEN efj, long flag)
     806                 :            : {
     807                 :       1195 :   long e = efj[1], f = efj[2], j = efj[3], i, l;
     808                 :       1195 :   const long v = 1;
     809                 :            :   GEN L, pols;
     810                 :            :   KRASNER_t data;
     811                 :       1195 :   pari_sp av = avma;
     812                 :            : 
     813         [ -  + ]:       1195 :   if (DEBUGLEVEL>1)
     814                 :          0 :     err_printf("  Computing extensions with decomposition [e, f, j] = [%ld, %ld, %ld]\n", e,f,j);
     815                 :       1195 :   data.p   = p;
     816                 :       1195 :   data.e   = e;
     817                 :       1195 :   data.f   = f;
     818                 :       1195 :   data.j   = j;
     819                 :       1195 :   data.a   = j/e;
     820                 :       1195 :   data.b   = j%e;
     821                 :       1195 :   data.c   = (e+2*j)/e+1;
     822                 :       1195 :   data.q   = powiu(p, f);
     823                 :       1195 :   data.qm1 = subis(data.q, 1);
     824                 :       1195 :   data.v   = v;
     825                 :       1195 :   data.r   = 1 + ceildiv(2*j + 3, e); /* enough precision */
     826                 :       1195 :   data.pr  = powiu(p, data.r);
     827                 :       1195 :   data.nbext = NumberExtensions(&data);
     828                 :            : 
     829         [ +  + ]:       1195 :   if (flag == 2) return data.nbext;
     830                 :            : 
     831                 :       1175 :   data.upl   = CycloPol(&data);
     832                 :            :   /* mv = -v mod upl. If f = 1, then upl = v + c, hence mv = c */
     833                 :       1535 :   data.mv    = f == 1? gel(data.upl, 2)
     834         [ +  + ]:       1175 :                      : FpX_neg(pol_x(v), data.pr);
     835                 :       1175 :   data.uplr  = FpX_red(data.upl, data.p);
     836                 :       1175 :   data.frob  = FpXQ_pow(pol_x(v), p, data.upl, data.pr);
     837         [ -  + ]:       1175 :   if (DEBUGLEVEL>1) err_printf("  Unramified part %Ps\n", data.upl);
     838                 :       1175 :   data.roottable = NULL;
     839         [ +  + ]:       1175 :   if (j)
     840                 :            :   {
     841         [ +  - ]:         55 :     if (lgefint(data.q) == 3)
     842                 :            :     {
     843                 :         55 :       ulong npol = upowuu(data.q[2], e+1);
     844 [ +  - ][ +  - ]:         55 :       if (npol && npol < (1<<19)) data.roottable = const_vec(npol, NULL);
     845                 :            :     }
     846                 :         55 :     data.pk = get_pk(&data);
     847                 :         55 :     L = WildlyRamifiedCase(&data);
     848                 :            :   }
     849                 :            :   else
     850                 :       1120 :     L = TamelyRamifiedCase(&data);
     851                 :            : 
     852                 :       1175 :   pols = cgetg_copy(L, &l);
     853         [ +  + ]:       1175 :   if (flag == 1)
     854                 :            :   {
     855                 :       1165 :     GEN E = utoipos(e), F = utoipos(f), D = utoi(f*(e+j-1));
     856         [ +  + ]:       3270 :     for (i = 1; i < l; i++)
     857                 :            :     {
     858                 :       2105 :       GEN T = gel(L,i);
     859                 :       2105 :       gel(pols, i) = mkvec5(ZX_copy(gel(T, 1)), E,F,D, icopy(gel(T, 2)));
     860                 :            :     }
     861                 :            :   }
     862                 :            :   else
     863                 :            :   {
     864         [ +  + ]:         20 :     for (i = 1; i < l; i++)
     865                 :            :     {
     866                 :         10 :       GEN T = gel(L,i);
     867                 :         10 :       gel(pols, i) = ZX_copy(gel(T,1));
     868                 :            :     }
     869                 :            :   }
     870                 :       1195 :   return gerepileupto(av, pols);
     871                 :            : }
     872                 :            : 
     873                 :            : static GEN
     874                 :        335 : possible_efj(GEN p, long m)
     875                 :            : { /* maximal possible discriminant valuation d <= m * (1+v_p(m)) - 1 */
     876                 :            :   /* 1) [j = 0, tame] d = m - f with f | m and v_p(f) = v_p(m), or
     877                 :            :    * 2) [j > 0, wild] d >= m, j <= v_p(e)*e   */
     878                 :        335 :   ulong m1, pve, pp = p[2]; /* pp used only if v > 0 */
     879                 :        335 :   long ve, v = u_pvalrem(m, p, &m1);
     880                 :        335 :   GEN L, D = divisorsu(m1);
     881                 :        335 :   long i, taum1 = lg(D)-1, nb = 0;
     882                 :            : 
     883         [ +  + ]:        335 :   if (v) {
     884         [ +  + ]:         15 :     for (pve = 1,ve = 1; ve <= v; ve++) { pve *= pp; nb += pve * ve; }
     885                 :          5 :     nb = itos_or_0(muluu(nb, zv_sum(D)));
     886 [ +  - ][ -  + ]:          5 :     if (!nb || is_bigint( mului(pve, sqru(v)) ) )
     887                 :          0 :       pari_err_OVERFLOW("padicfields [too many ramification possibilities]");
     888                 :            :   }
     889                 :        335 :   nb += taum1; /* upper bound for the number of possible triples [e,f,j] */
     890                 :            : 
     891                 :        335 :   L = cgetg(nb + 1, t_VEC);
     892                 :            :   /* 1) tame */
     893         [ +  + ]:       1475 :   for (nb=1, i=1; i < lg(D); i++)
     894                 :            :   {
     895                 :       1140 :     long e = D[i], f = m / e;
     896                 :       1140 :     gel(L, nb++) = mkvecsmall3(e, f, 0);
     897                 :            :   }
     898                 :            :   /* 2) wild */
     899                 :            :   /* Ore's condition: either
     900                 :            :    * 1) j = v_p(e) * e, or
     901                 :            :    * 2) j = a e + b, with 0 < b < e and v_p(b) <= a < v_p(e) */
     902         [ +  + ]:        345 :   for (pve = 1, ve = 1; ve <= v; ve++)
     903                 :            :   {
     904                 :         10 :     pve *= pp; /* = p^ve */
     905         [ +  + ]:         20 :     for (i = 1; i < lg(D); i++)
     906                 :            :     {
     907                 :         10 :       long a,b, e = D[i] * pve, f = m / e;
     908         [ +  + ]:         30 :       for (b = 1; b < e; b++)
     909         [ +  + ]:         50 :         for (a = u_lval(b, pp); a < ve; a++)
     910                 :         30 :           gel(L, nb++) = mkvecsmall3(e, f,  a*e + b);
     911                 :         10 :       gel(L, nb++) = mkvecsmall3(e, f, ve*e);
     912                 :            :     }
     913                 :            :   }
     914                 :        335 :   setlg(L, nb); return L;
     915                 :            : }
     916                 :            : 
     917                 :            : static GEN
     918                 :        340 : pols_from_efj(pari_sp av, GEN EFJ, GEN p, long flag)
     919                 :            : {
     920                 :            :   long i, l;
     921                 :        340 :   GEN L = cgetg_copy(EFJ, &l);
     922 [ -  + ][ #  # ]:        340 :   if (l == 1) { avma = av; return flag == 2? gen_0: cgetg(1, t_VEC); }
     923         [ +  + ]:       1535 :   for (i = 1; i < l; i++) gel(L,i) = GetRamifiedPol(p, gel(EFJ,i), flag);
     924         [ +  + ]:        340 :   if (flag == 2) return gerepileuptoint(av, ZV_sum(L));
     925                 :        340 :   return gerepilecopy(av, shallowconcat1(L));
     926                 :            : }
     927                 :            : 
     928                 :            : /* return a minimal list of polynomials generating all the extensions of
     929                 :            :    Q_p of given degree N; if N is a t_VEC [n,d], return extensions of degree n
     930                 :            :    and discriminant p^d. */
     931                 :            : /* Return only the polynomials if flag = 0 (default), also the ramification
     932                 :            :    degree, the residual degree and the discriminant if flag = 1 and only the
     933                 :            :    number of extensions if flag = 2 */
     934                 :            : GEN
     935                 :        340 : padicfields0(GEN p, GEN N, long flag)
     936                 :            : {
     937                 :        340 :   pari_sp av = avma;
     938                 :        340 :   long m = 0, d = -1;
     939                 :            :   GEN L;
     940                 :            : 
     941         [ -  + ]:        340 :   if (typ(p) != t_INT) pari_err_TYPE("padicfields",p);
     942                 :            :   /* be nice to silly users */
     943         [ -  + ]:        340 :   if (!BPSW_psp(p)) pari_err_PRIME("padicfields",p);
     944      [ +  +  - ]:        340 :   switch(typ(N))
     945                 :            :   {
     946                 :            :     case t_VEC:
     947         [ -  + ]:          5 :       if (lg(N) != 3) pari_err_TYPE("padicfields",N);
     948                 :          5 :       d = gtos(gel(N,2));
     949                 :          5 :       N = gel(N,1); /* fall through */
     950                 :            :     case t_INT:
     951                 :        340 :       m = itos(N);
     952         [ -  + ]:        340 :       if (m <= 0) pari_err_DOMAIN("padicfields", "degree", "<=", gen_0,N);
     953                 :        340 :       break;
     954                 :            :     default:
     955                 :          0 :       pari_err_TYPE("padicfields",N);
     956                 :            :   }
     957         [ +  + ]:        340 :   if (d >= 0) return padicfields(p, m, d, flag);
     958                 :        335 :   L = possible_efj(p, m);
     959                 :        340 :   return pols_from_efj(av, L, p, flag);
     960                 :            : }
     961                 :            : 
     962                 :            : GEN
     963                 :          5 : padicfields(GEN p, long m, long d, long flag)
     964                 :            : {
     965                 :          5 :   long av = avma;
     966                 :          5 :   GEN L = possible_efj_by_d(p, m, d);
     967                 :          5 :   return pols_from_efj(av, L, p, flag);
     968                 :            : }

Generated by: LCOV version 1.9