Code coverage tests

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

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

The target is 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 19230-c71492b) Lines: 441 448 98.4 %
Date: 2016-07-30 07:10:28 Functions: 35 35 100.0 %
Legend: Lines: hit not hit

          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        1673 : ceildiv(ulong a, ulong b)
      61             : {
      62        1673 :   long c = a/b;
      63        1673 :   if (a%b) c++;
      64        1673 :   return c;
      65             : }
      66             : 
      67             : /* Eval P(x) assuming P has positive coefficients and the result is a long */
      68             : static ulong
      69      183533 : ZX_z_eval(GEN P, ulong x)
      70             : {
      71      183533 :   long i, l = lg(P);
      72             :   ulong z;
      73             : 
      74      183533 :   if (typ(P) == t_INT) return itou(P);
      75      183533 :   if (l == 2) return 0;
      76       91168 :   z = itou(gel(P, l-1));
      77       91168 :   for (i = l-2; i > 1; i--) z = z*x + itou(gel(P,i));
      78       91168 :   return z;
      79             : }
      80             : 
      81             : /* Eval P(x, y) assuming P has positive coefficients and the result is a long */
      82             : static ulong
      83       45997 : ZXY_z_eval(GEN P, ulong x, ulong y)
      84             : {
      85       45997 :   long i, l = lg(P);
      86             :   ulong z;
      87             : 
      88       45997 :   if (l == 2) return 0;
      89       45997 :   z = ZX_z_eval(gel(P, l-1), y);
      90       45997 :   for (i = l-2; i > 1; i--) z = z*x + ZX_z_eval(gel(P, i), y);
      91       45997 :   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       43148 : FqX_FpXQ_eval(GEN P, GEN a, GEN T, GEN p)
      98             : {
      99             :   long i, l;
     100       43148 :   GEN Q = cgetg_copy(P, &l);
     101             : 
     102       43148 :   Q[1] = P[1];
     103      194320 :   for (i = 2; i < l; i++)
     104             :   {
     105      151172 :     GEN cf = gel(P, i);
     106      151172 :     if (typ(cf) == t_POL) {
     107      102438 :       switch(degpol(cf))
     108             :       {
     109         952 :         case -1: cf = gen_0; break;
     110         567 :         case 0:  cf = gel(cf,2); break;
     111             :         default:
     112      100919 :           cf = FpX_FpXQ_eval(cf, a, T, p);
     113      100919 :           cf = simplify_shallow(cf);
     114      100919 :           break;
     115             :       }
     116             :     }
     117      151172 :     gel(Q, i) = cf;
     118             :   }
     119             : 
     120       43148 :   return Q;
     121             : }
     122             : 
     123             : /* Sieving routines */
     124             : static GEN
     125         497 : InitSieve(long l) { return zero_F2v(l); }
     126             : static long
     127         777 : NextZeroValue(GEN sv, long i)
     128             : {
     129        1890 :   for(; i <= sv[1]; i++)
     130        1393 :     if (!F2v_coeff(sv, i)) return i;
     131         497 :   return 0; /* sieve is full or out of the sieve! */
     132             : }
     133             : static void
     134        1113 : SetSieveValue(GEN sv, long i)
     135        1113 : { 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          21 : VerifyOre(GEN p, long e, long j)
     140             : {
     141             :   long nv, b, vb, nb;
     142             : 
     143          21 :   if (j < 0) return 0;
     144          21 :   nv = e * u_pval(e, p);
     145          21 :   b  = j%e;
     146          21 :   if (b == 0) return (j == nv);
     147          14 :   if (j > nv) return 0;
     148             :   /* j < nv */
     149          14 :   vb = u_pval(b, p);
     150          14 :   nb = vb*e;
     151          14 :   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           7 : possible_efj_by_d(GEN p, long m, long d)
     161             : {
     162             :   GEN rep, div;
     163             :   long i, ctr, l;
     164             : 
     165           7 :   if (d == 0) return mkvec(mkvecsmall3(1, m, 0)); /* unramified */
     166           7 :   div = divisorsu(ugcd(m, d));
     167           7 :   l = lg(div); ctr = 1;
     168           7 :   rep = cgetg(l, t_VEC);
     169          28 :   for (i = 1; i < l; i++)
     170             :   {
     171          21 :     long f = div[i], e = m/f, j = d/f - e + 1;
     172          21 :     if (VerifyOre(p, e, j)) gel(rep, ctr++) = mkvecsmall3(e, f, j);
     173             :   }
     174           7 :   setlg(rep, ctr); return rep;
     175             : }
     176             : 
     177             : /* return the number of extensions corresponding to (e,f,j) */
     178             : static GEN
     179        1673 : NumberExtensions(KRASNER_t *data)
     180             : {
     181             :   ulong pp, pa;
     182             :   long e, a, b;
     183             :   GEN p, q, s0, p1;
     184             : 
     185        1673 :   e = data->e;
     186        1673 :   p = data->p;
     187        1673 :   q = data->q;
     188        1673 :   a = data->a; /* floor(j/e) <= v_p(e), hence p^a | e */
     189        1673 :   b = data->b; /* j % e */
     190        1673 :   if (is_bigint(p)) /* implies a = 0 */
     191          70 :     return b == 0? utoipos(e): mulsi(e, data->qm1);
     192             : 
     193        1603 :   pp = p[2];
     194        1603 :   switch(a)
     195             :   {
     196        1561 :     case 0:  pa = 1;  s0 = utoipos(e); break;
     197          35 :     case 1:  pa = pp; s0 = mului(e, powiu(q, e / pa)); break;
     198             :     default:
     199           7 :       pa = upowuu(pp, a); /* p^a */
     200           7 :       s0 = mulsi(e, powiu(q, (e / pa) * ((pa - 1) / (pp - 1))));
     201             :   }
     202             :   /* s0 = e * q^(e*sum(p^-i, i=1...a)) */
     203        1603 :   if (b == 0) return s0;
     204             : 
     205             :   /* q^floor((b-1)/p^(a+1)) */
     206          56 :   p1 = powiu(q, sdivsi(b-1, muluu(pa, pp)));
     207          56 :   return mulii(mulii(data->qm1, s0), p1);
     208             : }
     209             : 
     210             : static GEN
     211        2961 : get_topx(KRASNER_t *data, GEN eis)
     212             : {
     213             :   GEN p1, p2, rpl;
     214             :   long j;
     215             :   pari_sp av;
     216             :   /* top poly. is the minimal polynomial of root(pol) + root(upl) */
     217        2961 :   rpl = FqX_translate(FqX_red(eis, data->upl, data->pr),
     218             :                       data->mv, data->upl, data->pr);
     219        2961 :   p1 = p2 = rpl;
     220        2961 :   av = avma;
     221       22491 :   for (j = 1; j < data->f; j++)
     222             :   {
     223       19530 :     p1 = FqX_FpXQ_eval(p1, data->frob, data->upl, data->pr);
     224       19530 :     p2 = FqX_mul(p2, p1, data->upl, data->pr);
     225       19530 :     if (gc_needed(av, 1)) gerepileall(av, 2, &p1, &p2);
     226             :   }
     227        2961 :   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         616 : FieldData(KRASNER_t *data, FAD_t *fdata, GEN eis, GEN topx)
     236             : {
     237             :   GEN p1, zq, ipi, cipi, dipi, t, Q;
     238             : 
     239         616 :   fdata->p = data->p;
     240         616 :   t = leafcopy(topx); setvarn(t, data->v);
     241         616 :   fdata->top  = t;
     242         616 :   fdata->topr = FpX_red(t, data->pr);
     243             : 
     244         616 :   zq  = pol_x(data->v);
     245             :   /* FIXME: do as in CycloPol (not so easy) */
     246             :   for(;;)
     247             :   {
     248        3493 :     GEN zq2 = zq;
     249        3493 :     zq = Fq_pow(zq, data->q, fdata->top, data->pr);
     250        3493 :     if (gequal(zq, zq2)) break;
     251        2877 :   }
     252         616 :   fdata->zq  = zq;
     253         616 :   fdata->eis = eis;
     254         616 :   fdata->pi  = Fq_sub(pol_x(data->v), fdata->zq,
     255             :                       FpX_red(fdata->top, data->p), data->p);
     256         616 :   ipi = RgXQ_inv(fdata->pi, fdata->top);
     257         616 :   ipi = Q_remove_denom(ipi, &dipi);
     258         616 :   Q = mulii(data->pr, data->p);
     259         616 :   cipi = Fp_inv(diviiexact(dipi, data->p), Q);
     260         616 :   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         616 :   p1 = FpXQ_powers(fdata->pi, data->e, fdata->topr, data->pr);
     264         616 :   gel(p1, data->e+1) = ZX_Z_divexact(gel(p1, data->e+1), data->p);
     265         616 :   fdata->pik  = p1;
     266         616 : }
     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      325612 : DivideByPi(FAD_t *fdata, GEN pp, GEN ppp, GEN pol)
     272             : {
     273             :   GEN P;
     274             :   long i, l;
     275      325612 :   pari_sp av = avma;
     276             : 
     277             :   /* "pol" is a t_INT or an FpX: signe() works for both */
     278      325612 :   if (!signe(pol)) return pol;
     279             : 
     280      325458 :   P = Fq_mul(pol, fdata->ipi, fdata->top, ppp); /* FpX */
     281      325458 :   l  = lg(P);
     282     1595069 :   for (i = 2; i < l; i++)
     283             :   {
     284             :     GEN r;
     285     1361479 :     gel(P,i) = dvmdii(gel(P,i), fdata->p, &r);
     286     1361479 :     if (r != gen_0) { avma = av; return NULL; }
     287             :   }
     288      233590 :   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       45934 : GetSharp(FAD_t *fdata, GEN pp, GEN ppp, GEN pol, GEN beta, long *pl)
     295             : {
     296             :   GEN p1, p2;
     297       45934 :   long i, v, l, d = degpol(pol);
     298       45934 :   pari_sp av = avma;
     299             : 
     300       45934 :   if (!gequal0(beta))
     301       37387 :     p1 = FqX_translate(pol, beta, fdata->topr, pp);
     302             :   else
     303        8547 :     p1 = shallowcopy(pol);
     304       45934 :   p2 = p1;
     305      145215 :   for (v = 0;; v++)
     306             :   {
     307      351792 :     for (i = 0; i <= v; i++)
     308             :     {
     309      252511 :       GEN c = gel(p2, i+2);
     310      252511 :       c = DivideByPi(fdata, pp, ppp, c);
     311      252511 :       if (!c) break;
     312      206577 :       gel(p2, i+2) = c;
     313             :     }
     314      145215 :     if (i <= v) break;
     315       99281 :     p1 = shallowcopy(p2);
     316       99281 :   }
     317       45934 :   if (!v) pari_err_BUG("GetSharp [no division]");
     318             : 
     319       73101 :   for (l = v; l >= 0; l--)
     320             :   {
     321       73101 :     GEN c = gel(p1, l+2);
     322       73101 :     c = DivideByPi(fdata, pp, ppp, c);
     323       73101 :     if (!c) { break; }
     324             :   }
     325             : 
     326       45934 :   *pl = l; if (l < 2) return NULL;
     327             : 
     328             :   /* adjust powers */
     329       34104 :   for (i = v+1; i <= d; i++)
     330       19348 :     gel(p1, i+2) = Fq_mul(gel(p1, i+2),
     331        9674 :                           gel(fdata->pik, i-v+1), fdata->topr, pp);
     332             : 
     333       24430 :   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       45997 : Quick_FqX_roots(KRASNER_t *data, GEN pol)
     366             : {
     367             :   GEN rts;
     368       45997 :   ulong ind = 0;
     369             : 
     370       45997 :   pol = FpXQX_red(pol, data->uplr, data->p);
     371             : 
     372       45997 :   if (data->roottable)
     373             :   {
     374       45997 :     ind = ZXY_z_eval(pol, data->q[2], data->p[2]);
     375       45997 :     if (gel(data->roottable, ind)) return gel(data->roottable, ind);
     376             :   }
     377        2562 :   rts = FpXQX_roots(pol, data->uplr, data->p);
     378             : 
     379        2562 :   if (ind) gel(data->roottable, ind) = gclone(rts);
     380        2562 :   return rts;
     381             : }
     382             : 
     383             : static void
     384          77 : FreeRootTable(GEN T)
     385             : {
     386          77 :   if (T)
     387             :   {
     388          77 :     long j, l = lg(T);
     389       41741 :     for (j = 1; j < l; j++)
     390       41664 :       if (gel(T,j)) gunclone(gel(T,j));
     391             :   }
     392          77 : }
     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       67501 : 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       67501 :   if (alpha)
     404             :   { /* FIXME: the data used in GetSharp is not reduced */
     405             :     long l;
     406       45934 :     pol = GetSharp(fdata, pp, ppp, pol, alpha, &l);
     407       45934 :     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       24430 :     sl += l;
     414       24430 :     if (sl >= data->e)
     415             :     {
     416       21441 :       sl -= data->e;
     417       21441 :       ppp = pp;
     418       21441 :       pp = diviiexact(pp, data->p);
     419             :     }
     420             :   }
     421             : 
     422       45997 :   R  = Quick_FqX_roots(data, pol);
     423       86310 :   for (s = 0, i = 1; i < lg(R); i++)
     424             :   {
     425       45934 :     s += RootCongruents(data, fdata, pol, gel(R, i), pp, ppp, sl, flag);
     426       45934 :     if (flag && s) return 1;
     427             :   }
     428       40376 :   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       21567 : RootCountingAlgorithm(KRASNER_t *data, FAD_t *fdata, GEN pol, long flag)
     436             : {
     437             :   long j, l, d;
     438       21567 :   GEN P = cgetg_copy(pol, &l);
     439             : 
     440       21567 :   P[1] = pol[1];
     441       21567 :   d = l-3;
     442       90447 :   for (j = 0; j < d; j++)
     443             :   {
     444       68880 :     GEN cf = gel(pol, j+2);
     445       68880 :     if (typ(cf) == t_INT)
     446       32438 :       cf = diviiexact(cf, data->p);
     447             :     else
     448       36442 :       cf = ZX_Z_divexact(cf, data->p);
     449       68880 :     gel(P, j+2) = Fq_mul(cf, gel(fdata->pik, j+1), fdata->topr, data->pr);
     450             :   }
     451       21567 :   gel(P, d+2) = gel(fdata->pik, d+1); /* pik[d] = pi^d/p */
     452             : 
     453       21567 :   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       11823 : IsIsomorphic(KRASNER_t *data, FAD_t *fdata, GEN pol)
     460             : {
     461             :   long j, nb;
     462       11823 :   pari_sp av = avma;
     463             : 
     464       11823 :   if (RgX_is_ZX(pol)) return RootCountingAlgorithm(data, fdata, pol, 1);
     465             : 
     466       18144 :   for (j = 1; j <= data->f; j++)
     467             :   {
     468       13846 :     GEN p1 = FqX_FpXQ_eval(pol, fdata->zq, fdata->top, data->pr);
     469       13846 :     nb = RootCountingAlgorithm(data, fdata, p1, 1);
     470       13846 :     if (nb) { avma = av; return nb; }
     471       13020 :     if (j < data->f)
     472        8722 :       pol = FqX_FpXQ_eval(pol, data->frob, data->upl, data->pr);
     473             :   }
     474        4298 :   avma = av; return 0;
     475             : }
     476             : 
     477             : /* Compute the number of conjugates fields of the field given by fdata */
     478             : static void
     479         616 : NbConjugateFields(KRASNER_t *data, FAD_t *fdata)
     480             : {
     481         616 :   GEN pol = fdata->eis;
     482             :   long j, nb;
     483         616 :   pari_sp av = avma;
     484             : 
     485         616 :   if (RgX_is_ZX(pol)) { /* split for efficiency; contains the case f = 1 */
     486         378 :     fdata->cj = data->e / RootCountingAlgorithm(data, fdata, pol, 0);
     487         378 :     avma = av; return;
     488             :   }
     489             : 
     490         238 :   nb = 0;
     491         882 :   for (j = 1; j <= data->f; j++)
     492             :   {
     493         644 :     GEN p1 = FqX_FpXQ_eval(pol, fdata->zq, fdata->top, data->pr);
     494         644 :     nb += RootCountingAlgorithm(data, fdata, p1, 0);
     495         644 :     if (j < data->f)
     496         406 :       pol = FqX_FpXQ_eval(pol, data->frob, data->upl, data->pr);
     497             :   }
     498         238 :   avma = av;
     499         238 :   fdata->cj = data->e * data->f / nb;
     500         238 :   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        1568 : TamelyRamifiedCase(KRASNER_t *data)
     508             : {
     509        1568 :   long av = avma, g;
     510        1568 :   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        1568 :   g   = ugcd(data->e, umodiu(data->qm1, data->e)); /* (e, q-1) */
     520        1568 :   m   = stoi(data->e/g);
     521        1568 :   rep = zerovec(g);
     522             : 
     523        1568 :   eis = gadd(Xe, data->p);
     524        1568 :   topx = get_topx(data, eis);
     525        1568 :   p2 = mkvec2(topx, m);
     526        1568 :   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        1568 :   if (g > 1)
     543             :   {
     544         497 :     ulong pmodg = umodiu(data->p, g);
     545         497 :     long r = 1, ct = 1;
     546         497 :     GEN sv = InitSieve(g-1);
     547        1771 :     while (r)
     548             :     {
     549             :       long gr;
     550         777 :       GEN p1 = FpXQ_powu(pol_x(data->v), r, data->uplr, data->p);
     551         777 :       eis = gadd(Xe, ZX_Z_mul(p1, data->p)); /* Adding a ZX and a ZY (cste coefficient) */
     552         777 :       ct++;
     553         777 :       topx = get_topx(data, eis);
     554         777 :       p2 = mkvec2(topx, m);
     555         777 :       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         777 :       gr = r;
     568             :       do
     569             :       {
     570        1113 :         SetSieveValue(sv, gr);
     571        1113 :         gr = Fl_mul(gr, pmodg, g);
     572             :       }
     573        1113 :       while (gr != r);
     574         777 :       r  = NextZeroValue(sv, r);
     575             :     }
     576         497 :     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        1568 :   return gerepilecopy(av, rep);
     585             : }
     586             : 
     587             : static long
     588         217 : function_l(GEN p, long a, long b, long i)
     589             : {
     590         217 :   long l = 1 + a - z_pval(i, p);
     591         217 :   if (i < b) l++;
     592         217 :   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          77 : StructureOmega(KRASNER_t *data, GEN *pnbpol)
     602             : {
     603          77 :   GEN nbpol, O = cgetg(data->e + 1, t_VEC);
     604             :   long i;
     605             : 
     606             :   /* i = 0 */
     607          77 :   gel(O, 1) = mkvecsmall2(1, 0);
     608          77 :   nbpol = mulii(data->qm1, powiu(data->q, data->c - 1));
     609         294 :   for (i = 1; i < data->e; i++)
     610             :   {
     611         217 :     long v_start, zero = 0;
     612             :     GEN nbcf, p1;
     613         217 :     v_start = function_l(data->p, data->a, data->b, i);
     614         217 :     p1 = powiu(data->q, data->c - v_start);
     615         217 :     if (i == data->b)
     616          56 :       nbcf = mulii(p1, data->qm1);
     617             :     else
     618             :     {
     619         161 :       nbcf = mulii(p1, data->q);
     620         161 :       zero = 1;
     621             :     }
     622         217 :     gel(O, i+1) = mkvecsmall2(v_start, zero);
     623         217 :     nbpol = mulii(nbpol, nbcf);
     624             :   }
     625          77 :   *pnbpol = nbpol; return O;
     626             : }
     627             : 
     628             : /* a random element of the finite field */
     629             : static GEN
     630       33446 : RandomFF(KRASNER_t *data)
     631             : {
     632       33446 :   long i, l = data->f + 2, p = itou(data->p);
     633       33446 :   GEN c = cgetg(l, t_POL);
     634       33446 :   c[1] = evalvarn(data->v);
     635       33446 :   for (i = 2; i < l; i++) gel(c, i) = utoi(random_Fl(p));
     636       33446 :   return ZX_renormalize(c, l);
     637             : }
     638             : static GEN
     639        2352 : RandomPol(KRASNER_t *data, GEN Omega)
     640             : {
     641        2352 :   long i, j, l = data->e + 3, end = data->c;
     642        2352 :   GEN pol = cgetg(l, t_POL);
     643        2352 :   pol[1] = evalsigne(1) | evalvarn(0);
     644       10948 :   for (i = 1; i <= data->e; i++)
     645             :   {
     646        8596 :     GEN c, cf = gel(Omega, i);
     647        8596 :     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       11151 :       c = RandomFF(data);
     652       11151 :       if (zr || signe(c)) break;
     653        2555 :     }
     654       30891 :     for (j = 1; j <= end-st; j++)
     655       22295 :       c = ZX_add(c, ZX_Z_mul(RandomFF(data), gel(data->pk, j)));
     656        8596 :     c = ZX_Z_mul(c, gel(data->pk, st));
     657        8596 :     c = FpX_red(c, data->pr);
     658        8596 :     switch(degpol(c))
     659             :     {
     660         546 :       case -1: c = gen_0; break;
     661        5236 :       case  0: c = gel(c,2); break;
     662             :     }
     663        8596 :     gel(pol, i+1) = c;
     664             :   }
     665        2352 :   gel(pol, i+1) = gen_1; /* monic */
     666        2352 :   return pol;
     667             : }
     668             : 
     669             : static void
     670         616 : CloneFieldData(FAD_t *fdata)
     671             : {
     672         616 :  fdata->top = gclone(fdata->top);
     673         616 :  fdata->topr= gclone(fdata->topr);
     674         616 :  fdata->zq  = gclone(fdata->zq);
     675         616 :  fdata->eis = gclone(fdata->eis);
     676         616 :  fdata->pi  = gclone(fdata->pi);
     677         616 :  fdata->ipi = gclone(fdata->ipi);
     678         616 :  fdata->pik = gclone(fdata->pik);
     679         616 : }
     680             : static void
     681         616 : FreeFieldData(FAD_t *fdata)
     682             : {
     683         616 :   gunclone(fdata->top);
     684         616 :   gunclone(fdata->topr);
     685         616 :   gunclone(fdata->zq);
     686         616 :   gunclone(fdata->eis);
     687         616 :   gunclone(fdata->pi);
     688         616 :   gunclone(fdata->ipi);
     689         616 :   gunclone(fdata->pik);
     690         616 : }
     691             : 
     692             : static GEN
     693          77 : WildlyRamifiedCase(KRASNER_t *data)
     694             : {
     695          77 :   long nbext, ct, fd, nb = 0, j;
     696             :   GEN nbpol, rpl, rep, Omega;
     697             :   FAD_t **vfd;
     698             :   pari_timer T;
     699          77 :   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          77 :   Omega = StructureOmega(data, &nbpol);
     704          77 :   nbext = itos_or_0(data->nbext);
     705          77 :   if (!nbext || (nbext & ~LGBITS))
     706           0 :     pari_err_OVERFLOW("padicfields [too many extensions]");
     707             : 
     708          77 :   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          77 :   vfd = (FAD_t**)new_chunk(nbext);
     714          77 :   for (j = 0; j < nbext; j++) vfd[j] = (FAD_t*)new_chunk(sizeof(FAD_t));
     715             : 
     716          77 :   ct = 0;
     717          77 :   fd = 0;
     718          77 :   av2 = avma;
     719             : 
     720        2506 :   while (fd < nbext)
     721             :   { /* Jump randomly among the polynomials : seems best... */
     722        2352 :     rpl = RandomPol(data, Omega);
     723        2352 :     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       12439 :     for (j = 0; j < ct; j++)
     735             :     {
     736       11823 :       nb = IsIsomorphic(data, vfd[j], rpl);
     737       11823 :       if (nb) break;
     738             :     }
     739        2352 :     if (!nb)
     740             :     {
     741         616 :       GEN topx = get_topx(data, rpl);
     742         616 :       FAD_t *fdata = (FAD_t*)vfd[ct];
     743         616 :       FieldData(data, fdata, rpl, topx);
     744         616 :       CloneFieldData(fdata);
     745         616 :       NbConjugateFields(data, fdata);
     746         616 :       nb = fdata->cj;
     747         616 :       fd += nb;
     748         616 :       ct++;
     749         616 :       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        2352 :     avma = av2;
     754             :   }
     755             : 
     756          77 :   rep = cgetg(ct+1, t_VEC);
     757         693 :   for (j = 0; j < ct; j++)
     758             :   {
     759         616 :     GEN topx = ZX_copy(((FAD_t*)vfd[j])->top);
     760             :     GEN p1;
     761         616 :     setvarn(topx, 0);
     762         616 :     p1 = mkvec2(topx, stoi(((FAD_t*)vfd[j])->cj));
     763         616 :     gel(rep, j+1) = p1;
     764         616 :     FreeFieldData((FAD_t*)vfd[j]);
     765             :   }
     766          77 :   FreeRootTable(data->roottable);
     767          77 :   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        1645 : CycloPol(KRASNER_t *d)
     774             : {
     775        1645 :   long v = d->v, e = d->e;
     776        1645 :   GEN T, z, fa, p = d->p;
     777             : 
     778             :   /* v - primroot(p) */
     779        1645 :   if (d->f == 1)
     780         504 :     return deg1pol_shallow(gen_1, Fp_neg(pgener_Fp(p), d->pr), v);
     781             : 
     782        1141 :   T = init_Fq(d->p, d->f, v);
     783        1141 :   fa = factoru( ugcd(e, umodiu(d->qm1, e)) );
     784        1141 :   z = gener_FpXQ_local(T, d->p, zv_to_ZV(gel(fa,1)));
     785        1141 :   z = ZpXQ_sqrtnlift(scalarpol(gen_1,varn(T)), d->qm1, z, T, d->p, d->r);
     786        1141 :   return FpX_red(ZXQ_charpoly(z, T, v), d->pr);
     787             : }
     788             : 
     789             : /* return [ p^1, p^2, ..., p^c ] */
     790             : static GEN
     791          77 : get_pk(KRASNER_t *data)
     792             : {
     793          77 :   long i, l = data->c + 1;
     794          77 :   GEN pk = cgetg(l, t_VEC), p = data->p;
     795          77 :   gel(pk, 1) = p;
     796          77 :   for (i = 2; i <= data->c; i++) gel(pk, i) = mulii(gel(pk, i-1), p);
     797          77 :   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        1673 : GetRamifiedPol(GEN p, GEN efj, long flag)
     806             : {
     807        1673 :   long e = efj[1], f = efj[2], j = efj[3], i, l;
     808        1673 :   const long v = 1;
     809             :   GEN L, pols;
     810             :   KRASNER_t data;
     811        1673 :   pari_sp av = avma;
     812             : 
     813        1673 :   if (DEBUGLEVEL>1)
     814           0 :     err_printf("  Computing extensions with decomposition [e, f, j] = [%ld, %ld, %ld]\n", e,f,j);
     815        1673 :   data.p   = p;
     816        1673 :   data.e   = e;
     817        1673 :   data.f   = f;
     818        1673 :   data.j   = j;
     819        1673 :   data.a   = j/e;
     820        1673 :   data.b   = j%e;
     821        1673 :   data.c   = (e+2*j)/e+1;
     822        1673 :   data.q   = powiu(p, f);
     823        1673 :   data.qm1 = subis(data.q, 1);
     824        1673 :   data.v   = v;
     825        1673 :   data.r   = 1 + ceildiv(2*j + 3, e); /* enough precision */
     826        1673 :   data.pr  = powiu(p, data.r);
     827        1673 :   data.nbext = NumberExtensions(&data);
     828             : 
     829        1673 :   if (flag == 2) return data.nbext;
     830             : 
     831        1645 :   data.upl   = CycloPol(&data);
     832             :   /* mv = -v mod upl. If f = 1, then upl = v + c, hence mv = c */
     833        2149 :   data.mv    = f == 1? gel(data.upl, 2)
     834        2149 :                      : FpX_neg(pol_x(v), data.pr);
     835        1645 :   data.uplr  = FpX_red(data.upl, data.p);
     836        1645 :   data.frob  = FpXQ_pow(pol_x(v), p, data.upl, data.pr);
     837        1645 :   if (DEBUGLEVEL>1) err_printf("  Unramified part %Ps\n", data.upl);
     838        1645 :   data.roottable = NULL;
     839        1645 :   if (j)
     840             :   {
     841          77 :     if (lgefint(data.q) == 3)
     842             :     {
     843          77 :       ulong npol = upowuu(data.q[2], e+1);
     844          77 :       if (npol && npol < (1<<19)) data.roottable = const_vec(npol, NULL);
     845             :     }
     846          77 :     data.pk = get_pk(&data);
     847          77 :     L = WildlyRamifiedCase(&data);
     848             :   }
     849             :   else
     850        1568 :     L = TamelyRamifiedCase(&data);
     851             : 
     852        1645 :   pols = cgetg_copy(L, &l);
     853        1645 :   if (flag == 1)
     854             :   {
     855        1631 :     GEN E = utoipos(e), F = utoipos(f), D = utoi(f*(e+j-1));
     856        4578 :     for (i = 1; i < l; i++)
     857             :     {
     858        2947 :       GEN T = gel(L,i);
     859        2947 :       gel(pols, i) = mkvec5(ZX_copy(gel(T, 1)), E,F,D, icopy(gel(T, 2)));
     860             :     }
     861             :   }
     862             :   else
     863             :   {
     864          28 :     for (i = 1; i < l; i++)
     865             :     {
     866          14 :       GEN T = gel(L,i);
     867          14 :       gel(pols, i) = ZX_copy(gel(T,1));
     868             :     }
     869             :   }
     870        1645 :   return gerepileupto(av, pols);
     871             : }
     872             : 
     873             : static GEN
     874         469 : 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         469 :   ulong m1, pve, pp = p[2]; /* pp used only if v > 0 */
     879         469 :   long ve, v = u_pvalrem(m, p, &m1);
     880         469 :   GEN L, D = divisorsu(m1);
     881         469 :   long i, taum1 = lg(D)-1, nb = 0;
     882             : 
     883         469 :   if (v) {
     884           7 :     for (pve = 1,ve = 1; ve <= v; ve++) { pve *= pp; nb += pve * ve; }
     885           7 :     nb = itos_or_0(muluu(nb, zv_sum(D)));
     886           7 :     if (!nb || is_bigint( mului(pve, sqru(v)) ) )
     887           0 :       pari_err_OVERFLOW("padicfields [too many ramification possibilities]");
     888             :   }
     889         469 :   nb += taum1; /* upper bound for the number of possible triples [e,f,j] */
     890             : 
     891         469 :   L = cgetg(nb + 1, t_VEC);
     892             :   /* 1) tame */
     893        2065 :   for (nb=1, i=1; i < lg(D); i++)
     894             :   {
     895        1596 :     long e = D[i], f = m / e;
     896        1596 :     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         483 :   for (pve = 1, ve = 1; ve <= v; ve++)
     903             :   {
     904          14 :     pve *= pp; /* = p^ve */
     905          28 :     for (i = 1; i < lg(D); i++)
     906             :     {
     907          14 :       long a,b, e = D[i] * pve, f = m / e;
     908          42 :       for (b = 1; b < e; b++)
     909          70 :         for (a = u_lval(b, pp); a < ve; a++)
     910          42 :           gel(L, nb++) = mkvecsmall3(e, f,  a*e + b);
     911          14 :       gel(L, nb++) = mkvecsmall3(e, f, ve*e);
     912             :     }
     913             :   }
     914         469 :   setlg(L, nb); return L;
     915             : }
     916             : 
     917             : static GEN
     918         476 : pols_from_efj(pari_sp av, GEN EFJ, GEN p, long flag)
     919             : {
     920             :   long i, l;
     921         476 :   GEN L = cgetg_copy(EFJ, &l);
     922         476 :   if (l == 1) { avma = av; return flag == 2? gen_0: cgetg(1, t_VEC); }
     923         476 :   for (i = 1; i < l; i++) gel(L,i) = GetRamifiedPol(p, gel(EFJ,i), flag);
     924         476 :   if (flag == 2) return gerepileuptoint(av, ZV_sum(L));
     925         469 :   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         476 : padicfields0(GEN p, GEN N, long flag)
     936             : {
     937         476 :   pari_sp av = avma;
     938         476 :   long m = 0, d = -1;
     939             :   GEN L;
     940             : 
     941         476 :   if (typ(p) != t_INT) pari_err_TYPE("padicfields",p);
     942             :   /* be nice to silly users */
     943         476 :   if (!BPSW_psp(p)) pari_err_PRIME("padicfields",p);
     944         476 :   switch(typ(N))
     945             :   {
     946             :     case t_VEC:
     947           7 :       if (lg(N) != 3) pari_err_TYPE("padicfields",N);
     948           7 :       d = gtos(gel(N,2));
     949           7 :       N = gel(N,1); /* fall through */
     950             :     case t_INT:
     951         476 :       m = itos(N);
     952         476 :       if (m <= 0) pari_err_DOMAIN("padicfields", "degree", "<=", gen_0,N);
     953         476 :       break;
     954             :     default:
     955           0 :       pari_err_TYPE("padicfields",N);
     956             :   }
     957         476 :   if (d >= 0) return padicfields(p, m, d, flag);
     958         469 :   L = possible_efj(p, m);
     959         469 :   return pols_from_efj(av, L, p, flag);
     960             : }
     961             : 
     962             : GEN
     963           7 : padicfields(GEN p, long m, long d, long flag)
     964             : {
     965           7 :   long av = avma;
     966           7 :   GEN L = possible_efj_by_d(p, m, d);
     967           7 :   return pols_from_efj(av, L, p, flag);
     968             : }

Generated by: LCOV version 1.11