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

Generated by: LCOV version 1.11