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

Generated by: LCOV version 1.11