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; either version 2 of the License, or (at your option) any later
8 : version. It is distributed in the hope that it will be useful, but WITHOUT
9 : ANY WARRANTY WHATSOEVER.
10 :
11 : Check the License for details. You should have received a copy of it, along
12 : with the package; see the file 'COPYING'. If not, write to the Free Software
13 : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
14 :
15 : #include "pari.h"
16 : #include "paripriv.h"
17 :
18 : #define DEBUGLEVEL DEBUGLEVEL_padicfields
19 :
20 : /************************************************************/
21 : /* Computation of all the extensions of a given */
22 : /* degree of a p-adic field */
23 : /* Xavier Roblot */
24 : /************************************************************/
25 : /* cf. Math. Comp, vol. 70, No. 236, pp. 1641-1659 for more details.
26 : Note that n is now e (since the e from the paper is always = 1) and l
27 : is now f */
28 : /* Structure for a given type of extension */
29 : typedef struct {
30 : GEN p;
31 : long e, f, j;
32 : long a, b, c;
33 : long v; /* auxiliary variable */
34 : long r; /* pr = p^r */
35 : GEN pr; /* p^r = p-adic precision for poly. reduction */
36 : GEN prm1; /* p^(r-1) */
37 : GEN q, qm1; /* p^f, q - 1 */
38 : GEN T; /* polynomial defining K^ur */
39 : GEN frob; /* Frobenius acting of the root of T (mod pr) */
40 : GEN u; /* suitable root of unity (expressed in terms of the root of T) */
41 : GEN nbext; /* number of extensions */
42 : GEN roottable; /* table of roots of polynomials over the residue field */
43 : GEN pk; /* powers of p: [p^1, p^2, ..., p^c] */
44 : } KRASNER_t;
45 :
46 : /* Structure containing the field data (constructed with FieldData) */
47 : typedef struct {
48 : GEN p;
49 : GEN top; /* absolute polynomial of a = z + pi (mod pr) */
50 : GEN topr; /* top mod p */
51 : GEN z; /* root of T in terms of a (mod pr) */
52 : GEN eis; /* relative polynomial of pi in terms of z (mod pr) */
53 : GEN pi; /* prime element in terms of a */
54 : GEN ipi; /* p/pi in terms of a (mod pr) (used to divide by pi) */
55 : GEN pik; /* [1, pi, ..., pi^(e-1), pi^e/p] in terms of a (mod pr).
56 : Note the last one is different! */
57 : long cj; /* number of conjugate fields */
58 : } FAD_t;
59 :
60 : /* Eval P(x) assuming P has positive coefficients and the result is a long */
61 : static ulong
62 169393 : ZX_z_eval(GEN P, ulong x)
63 : {
64 169393 : long i, l = lg(P);
65 : ulong z;
66 :
67 169393 : if (typ(P) == t_INT) return itou(P);
68 64463 : if (l == 2) return 0;
69 36995 : z = itou(gel(P, l-1));
70 95340 : for (i = l-2; i > 1; i--) z = z*x + itou(gel(P,i));
71 36995 : return z;
72 : }
73 :
74 : /* Eval P(x, y) assuming P has positive coefficients and the result is a long */
75 : static ulong
76 40495 : ZXY_z_eval(GEN P, ulong x, ulong y)
77 : {
78 40495 : long i, l = lg(P);
79 : ulong z;
80 :
81 40495 : if (l == 2) return 0;
82 40495 : z = ZX_z_eval(gel(P, l-1), y);
83 169393 : for (i = l-2; i > 1; i--) z = z*x + ZX_z_eval(gel(P, i), y);
84 40495 : return z;
85 : }
86 :
87 : /* a(x) mod (T,p) */
88 : static GEN
89 130186 : _eval(GEN a, GEN x, GEN T, GEN p)
90 : {
91 : long d;
92 130186 : if (typ(x) != t_POL) return x;
93 87094 : d = degpol(x);
94 87094 : if (d <= 0) return d? gen_0: gel(x,2);
95 85638 : x = FpX_FpXQ_eval(x, a, T, p);
96 85638 : return simplify_shallow(x);
97 : }
98 : /* x an Fq[X], where Fq = Fp[Y]/(T(Y)), a an FpX representing the automorphism
99 : * y -> a(y). Return a(x), applying a() coefficientwise. */
100 : static GEN
101 36806 : FqX_FpXQ_eval(GEN x, GEN a, GEN T, GEN p)
102 166992 : { pari_APPLY_pol_normalized(_eval(a, gel(x,i), T, p)); }
103 :
104 : /* Sieving routines */
105 : static GEN
106 497 : InitSieve(long l) { return zero_F2v(l); }
107 : static long
108 777 : NextZeroValue(GEN sv, long i)
109 : {
110 1890 : for(; i <= sv[1]; i++)
111 1393 : if (!F2v_coeff(sv, i)) return i;
112 497 : return 0; /* sieve is full or out of the sieve! */
113 : }
114 : static void
115 1113 : SetSieveValue(GEN sv, long i)
116 1113 : { if (i >= 1 && i <= sv[1]) F2v_set(sv, i); }
117 :
118 : /* return 1 if the data verify Ore condition and 0 otherwise */
119 : static long
120 21 : VerifyOre(GEN p, long e, long j)
121 : {
122 : long nv, b, vb, nb;
123 :
124 21 : if (j < 0) return 0;
125 21 : nv = e * u_pval(e, p);
126 21 : b = j%e;
127 21 : if (b == 0) return (j == nv);
128 14 : if (j > nv) return 0;
129 : /* j < nv */
130 14 : vb = u_pval(b, p);
131 14 : nb = vb*e;
132 14 : return (nb <= j);
133 : }
134 :
135 : /* Given [K:Q_p] = m and disc(K/Q_p) = p^d, return all decompositions K/K^ur/Q_p
136 : * as [e, f, j] with
137 : * K^ur/Q_p unramified of degree f,
138 : * K/K^ur totally ramified of degree e and discriminant p^(e+j-1);
139 : * thus d = f*(e+j-1) and j > 0 iff ramification is wild */
140 : static GEN
141 7 : possible_efj_by_d(GEN p, long m, long d)
142 : {
143 : GEN rep, div;
144 : long i, ctr, l;
145 :
146 7 : if (d == 0) return mkvec(mkvecsmall3(1, m, 0)); /* unramified */
147 7 : div = divisorsu(ugcd(m, d));
148 7 : l = lg(div); ctr = 1;
149 7 : rep = cgetg(l, t_VEC);
150 28 : for (i = 1; i < l; i++)
151 : {
152 21 : long f = div[i], e = m/f, j = d/f - e + 1;
153 21 : if (VerifyOre(p, e, j)) gel(rep, ctr++) = mkvecsmall3(e, f, j);
154 : }
155 7 : setlg(rep, ctr); return rep;
156 : }
157 :
158 : /* return the number of extensions corresponding to (e,f,j) */
159 : static GEN
160 1743 : NumberExtensions(KRASNER_t *data)
161 : {
162 : ulong pp, pa;
163 : long e, a, b;
164 : GEN p, q, s0, p1;
165 :
166 1743 : e = data->e;
167 1743 : p = data->p;
168 1743 : q = data->q;
169 1743 : a = data->a; /* floor(j/e) <= v_p(e), hence p^a | e */
170 1743 : b = data->b; /* j % e */
171 1743 : if (is_bigint(p)) /* implies a = 0 */
172 70 : return b == 0? utoipos(e): mulsi(e, data->qm1);
173 :
174 1673 : pp = p[2];
175 1673 : switch(a)
176 : {
177 1617 : case 0: pa = 1; s0 = utoipos(e); break;
178 49 : case 1: pa = pp; s0 = mului(e, powiu(q, e / pa)); break;
179 7 : default:
180 7 : pa = upowuu(pp, a); /* p^a */
181 7 : s0 = mulsi(e, powiu(q, (e / pa) * ((pa - 1) / (pp - 1))));
182 : }
183 : /* s0 = e * q^(e*sum(p^-i, i=1...a)) */
184 1673 : if (b == 0) return s0;
185 :
186 : /* q^floor((b-1)/p^(a+1)) */
187 98 : p1 = powiu(q, sdivsi(b-1, muluu(pa, pp)));
188 98 : return mulii(mulii(data->qm1, s0), p1);
189 : }
190 :
191 : static GEN
192 3213 : get_topx(KRASNER_t *data, GEN eis)
193 : {
194 : GEN p1, p2, rpl, c;
195 : pari_sp av;
196 : long j;
197 : /* top poly. is the minimal polynomial of root(T) + root(eis) */
198 3213 : if (data->f == 1) return eis;
199 1953 : c = FpX_neg(pol_x(data->v),data->pr);
200 1953 : rpl = FqX_Fq_translate(eis, c, data->T, data->pr);
201 1953 : p1 = p2 = rpl; av = avma;
202 21525 : for (j = 1; j < data->f; j++)
203 : {
204 : /* compute conjugate polynomials using the Frobenius */
205 19572 : p1 = FqX_FpXQ_eval(p1, data->frob, data->T, data->pr);
206 19572 : p2 = FqX_mul(p2, p1, data->T, data->pr);
207 19572 : if (gc_needed(av,2)) (void)gc_all(av, 2, &p1,&p2);
208 : }
209 1953 : return simplify_shallow(p2); /* ZX */
210 : }
211 :
212 : /* eis (ZXY): Eisenstein polynomial over the field defined by T.
213 : * topx (ZX): absolute equation of root(T) + root(eis).
214 : * Return the struct FAD corresponding to the field it defines (GENs created
215 : * as clones). Assume e > 1. */
216 : static void
217 854 : FieldData(KRASNER_t *data, FAD_t *fdata, GEN eis, GEN topx)
218 : {
219 : GEN p1, p2, p3, z, ipi, cipi, dipi, t, Q;
220 :
221 854 : fdata->p = data->p;
222 854 : t = leafcopy(topx); setvarn(t, data->v);
223 854 : fdata->top = t;
224 854 : fdata->topr = FpX_red(t, data->pr);
225 :
226 854 : if (data->f == 1) z = gen_0;
227 : else
228 : { /* Compute a root of T in K(top) using Hensel's lift */
229 238 : z = pol_x(data->v);
230 238 : p1 = FpX_deriv(data->T, data->p);
231 : /* First lift to a root mod p */
232 : for (;;) {
233 560 : p2 = FpX_FpXQ_eval(data->T, z, fdata->top, data->p);
234 560 : if (gequal0(p2)) break;
235 322 : p3 = FpX_FpXQ_eval(p1, z, fdata->top, data->p);
236 322 : z = FpX_sub(z, FpXQ_div(p2, p3, fdata->top, data->p), data->p);
237 : }
238 : /* Then a root mod p^r */
239 238 : z = ZpX_ZpXQ_liftroot(data->T, z, fdata->top, data->p, data->r);
240 : }
241 :
242 854 : fdata->z = z;
243 854 : fdata->eis = eis;
244 854 : fdata->pi = Fq_sub(pol_x(data->v), fdata->z,
245 : FpX_red(fdata->top, data->p), data->p);
246 854 : ipi = RgXQ_inv(fdata->pi, fdata->top);
247 854 : ipi = Q_remove_denom(ipi, &dipi);
248 854 : Q = mulii(data->pr, data->p);
249 854 : cipi = Fp_inv(diviiexact(dipi, data->p), Q);
250 854 : fdata->ipi = FpX_Fp_mul(ipi, cipi, Q); /* p/pi mod p^(pr+1) */
251 :
252 : /* Last one is set to pi^e/p (so we compute pi^e with one extra precision) */
253 854 : p2 = mulii(data->pr, data->p);
254 854 : p1 = FpXQ_powers(fdata->pi, data->e, fdata->topr, p2);
255 854 : gel(p1, data->e+1) = ZX_Z_divexact(gel(p1, data->e+1), data->p);
256 854 : fdata->pik = p1;
257 854 : }
258 :
259 : /* return pol*ipi/p (mod top, pp) if it has integral coefficient, NULL
260 : otherwise. The result is reduced mod top, pp */
261 : static GEN
262 307468 : DivideByPi(FAD_t *fdata, GEN pp, GEN ppp, GEN pol)
263 : {
264 : GEN P;
265 : long i, l;
266 307468 : pari_sp av = avma;
267 :
268 : /* "pol" is a t_INT or an FpX: signe() works for both */
269 307468 : if (!signe(pol)) return pol;
270 :
271 300384 : P = Fq_mul(pol, fdata->ipi, fdata->top, ppp); /* FpX */
272 300384 : l = lg(P);
273 1562631 : for (i = 2; i < l; i++)
274 : {
275 : GEN r;
276 1343377 : gel(P,i) = dvmdii(gel(P,i), fdata->p, &r);
277 1343377 : if (r != gen_0) return gc_NULL(av);
278 : }
279 219254 : return FpX_red(P, pp);
280 : }
281 :
282 : /* return pol# = pol~/pi^vpi(pol~) mod pp where pol~(x) = pol(pi.x + beta)
283 : * has coefficients in the field defined by top and pi is a prime element */
284 : static GEN
285 40565 : GetSharp(FAD_t *fdata, GEN pp, GEN ppp, GEN pol, GEN beta, long *pl)
286 : {
287 : GEN p1, p2;
288 40565 : long i, v, l, d = degpol(pol);
289 40565 : pari_sp av = avma;
290 :
291 40565 : if (!gequal0(beta))
292 31927 : p1 = FqX_Fq_translate(pol, beta, fdata->topr, pp);
293 : else
294 8638 : p1 = shallowcopy(pol);
295 40565 : p2 = p1;
296 132930 : for (v = 0;; v++)
297 : {
298 334103 : for (i = 0; i <= v; i++)
299 : {
300 241738 : GEN c = gel(p2, i+2);
301 241738 : c = DivideByPi(fdata, pp, ppp, c);
302 241738 : if (!c) break;
303 201173 : gel(p2, i+2) = c;
304 : }
305 132930 : if (i <= v) break;
306 92365 : p1 = shallowcopy(p2);
307 : }
308 40565 : if (!v) pari_err_BUG("GetSharp [no division]");
309 :
310 65730 : for (l = v; l >= 0; l--)
311 : {
312 65730 : GEN c = gel(p1, l+2);
313 65730 : c = DivideByPi(fdata, pp, ppp, c);
314 65730 : if (!c) { break; }
315 : }
316 :
317 40565 : *pl = l; if (l < 2) return NULL;
318 :
319 : /* adjust powers */
320 31955 : for (i = v+1; i <= d; i++)
321 10458 : gel(p1, i+2) = Fq_mul(gel(p1, i+2),
322 10458 : gel(fdata->pik, i-v+1), fdata->topr, pp);
323 :
324 21497 : return gc_GEN(av, normalizepol(p1));
325 : }
326 :
327 : /* Compute roots of pol in the residue field. Use table look-up if possible */
328 : static GEN
329 40495 : Quick_FqX_roots(KRASNER_t *data, GEN pol)
330 : {
331 : GEN rts;
332 40495 : ulong ind = 0;
333 :
334 40495 : if (data->f == 1)
335 22414 : pol = FpXY_evalx(pol, gen_0, data->p);
336 : else
337 18081 : pol = FqX_red(pol, data->T, data->p);
338 40495 : if (data->roottable)
339 : {
340 : GEN r;
341 40495 : ind = ZXY_z_eval(pol, data->q[2], data->p[2]);
342 40495 : r = gel(data->roottable, ind); if (r) return r;
343 : }
344 2856 : rts = FqX_roots(pol, data->T, data->p);
345 2856 : if (ind) gel(data->roottable, ind) = gclone(rts);
346 2856 : return rts;
347 : }
348 :
349 : static void
350 133 : FreeRootTable(GEN T)
351 : {
352 133 : if (T)
353 : {
354 133 : long j, l = lg(T);
355 590373 : for (j = 1; j < l; j++) guncloneNULL(gel(T,j));
356 : }
357 133 : }
358 :
359 : /* Return the number of roots of pol congruent to alpha modulo pi working
360 : modulo pp (all roots if alpha is NULL); if flag is nonzero, return 1
361 : as soon as a root is found. (Note: ppp = pp*p for DivideByPi) */
362 : static long
363 59563 : RootCongruents(KRASNER_t *data, FAD_t *fdata, GEN pol, GEN alpha, GEN pp, GEN ppp, long sl, long flag)
364 : {
365 : GEN R;
366 : long s, i;
367 :
368 59563 : if (alpha)
369 : {
370 : long l;
371 40565 : pol = GetSharp(fdata, pp, ppp, pol, alpha, &l);
372 40565 : if (l <= 1) return l;
373 : /* decrease precision if sl gets bigger than a multiple of e */
374 21497 : sl += l;
375 21497 : if (sl >= data->e)
376 : {
377 18249 : sl -= data->e;
378 18249 : ppp = pp;
379 18249 : pp = diviiexact(pp, data->p);
380 : }
381 : }
382 :
383 40495 : R = Quick_FqX_roots(data, pol);
384 75390 : for (s = 0, i = 1; i < lg(R); i++)
385 : {
386 40565 : s += RootCongruents(data, fdata, pol, gel(R, i), pp, ppp, sl, flag);
387 40565 : if (flag && s) return 1;
388 : }
389 34825 : return s;
390 : }
391 :
392 : /* pol is a ZXY defining a polynomial over the field defined by fdata
393 : If flag != 0, return 1 as soon as a root is found. Computations are done with
394 : a precision of pr. */
395 : static long
396 18998 : RootCountingAlgorithm(KRASNER_t *data, FAD_t *fdata, GEN pol, long flag)
397 : {
398 18998 : pari_sp av = avma;
399 : long j, l, d;
400 18998 : GEN P = cgetg_copy(pol, &l);
401 :
402 18998 : P[1] = pol[1];
403 18998 : d = l-3;
404 84693 : for (j = 0; j < d; j++)
405 : {
406 65695 : GEN cf = gel(pol, j+2);
407 65695 : if (typ(cf) == t_INT)
408 38430 : cf = diviiexact(cf, data->p);
409 : else
410 27265 : cf = ZX_Z_divexact(cf, data->p);
411 65695 : gel(P, j+2) = Fq_mul(cf, gel(fdata->pik, j+1), fdata->topr, data->pr);
412 : }
413 18998 : gel(P, d+2) = gel(fdata->pik, d+1); /* pik[d] = pi^d/p */
414 18998 : d = RootCongruents(data, fdata, P, NULL, data->prm1, data->pr, 0, flag);
415 18998 : return gc_long(av, d);
416 : }
417 :
418 : /* Return nonzero if the field given by fdata defines a field isomorphic to
419 : * the one defined by pol */
420 : static long
421 11662 : IsIsomorphic(KRASNER_t *data, FAD_t *fdata, GEN pol)
422 : {
423 : long j, nb;
424 11662 : pari_sp av = avma;
425 :
426 11662 : if (RgX_is_ZX(pol)) return RootCountingAlgorithm(data, fdata, pol, 1);
427 :
428 13545 : for (j = 1; j <= data->f; j++)
429 : {
430 10108 : GEN p1 = FqX_FpXQ_eval(pol, fdata->z, fdata->top, data->pr);
431 10108 : nb = RootCountingAlgorithm(data, fdata, p1, 1);
432 10108 : if (nb) return gc_long(av, nb);
433 9513 : if (j < data->f)
434 6076 : pol = FqX_FpXQ_eval(pol, data->frob, data->T, data->pr);
435 : }
436 3437 : return gc_long(av,0);
437 : }
438 :
439 : /* Compute the number of conjugates fields of the field given by fdata */
440 : static void
441 854 : NbConjugateFields(KRASNER_t *data, FAD_t *fdata)
442 : {
443 854 : GEN pol = fdata->eis;
444 : long j, nb;
445 854 : pari_sp av = avma;
446 :
447 854 : if (RgX_is_ZX(pol)) { /* split for efficiency; contains the case f = 1 */
448 616 : fdata->cj = data->e / RootCountingAlgorithm(data, fdata, pol, 0);
449 616 : return;
450 : }
451 :
452 238 : nb = 0;
453 882 : for (j = 1; j <= data->f; j++)
454 : { /* Transform to pol. in z to pol. in a */
455 644 : GEN p1 = FqX_FpXQ_eval(pol, fdata->z, fdata->top, data->pr);
456 644 : nb += RootCountingAlgorithm(data, fdata, p1, 0);
457 : /* Look at the roots of conjugates polynomials */
458 644 : if (j < data->f)
459 406 : pol = FqX_FpXQ_eval(pol, data->frob, data->T, data->pr);
460 : }
461 238 : fdata->cj = data->e * data->f / nb;
462 238 : set_avma(av);
463 : }
464 :
465 : /* return a minimal list of polynomials generating all the totally
466 : ramified extensions of K^ur of degree e and discriminant
467 : p^{e + j - 1} in the tamely ramified case */
468 : static GEN
469 1582 : TamelyRamifiedCase(KRASNER_t *data)
470 : {
471 1582 : long av = avma;
472 1582 : long g = ugcdui(data->e, data->qm1); /* (e, q-1) */
473 1582 : GEN rep, eis, Xe = gpowgs(pol_x(0), data->e), m = stoi(data->e / g);
474 :
475 1582 : rep = zerovec(g);
476 1582 : eis = gadd(Xe, data->p);
477 1582 : gel(rep, 1) = mkvec2(get_topx(data,eis), m);
478 1582 : if (g > 1)
479 : {
480 497 : ulong pmodg = umodiu(data->p, g);
481 497 : long r = 1, ct = 1;
482 497 : GEN sv = InitSieve(g-1);
483 : /* let Frobenius act to get a minimal set of polynomials over Q_p */
484 1274 : while (r)
485 : {
486 : long gr;
487 1554 : GEN p1 = (typ(data->u) == t_INT)?
488 777 : mulii(Fp_powu(data->u, r, data->p), data->p):
489 588 : ZX_Z_mul(FpXQ_powu(data->u, r, data->T, data->p), data->p);
490 777 : eis = gadd(Xe, p1); /* add cst coef */
491 777 : ct++;
492 777 : gel(rep, ct) = mkvec2(get_topx(data,eis), m);
493 777 : gr = r;
494 1113 : do { SetSieveValue(sv, gr); gr = Fl_mul(gr, pmodg, g); } while (gr != r);
495 777 : r = NextZeroValue(sv, r);
496 : }
497 497 : setlg(rep, ct+1);
498 : }
499 1582 : return gc_GEN(av, rep);
500 : }
501 :
502 : static long
503 399 : function_l(GEN p, long a, long b, long i)
504 : {
505 399 : long l = 1 + a - z_pval(i, p);
506 399 : if (i < b) l++;
507 399 : return (l < 1)? 1: l;
508 : }
509 :
510 : /* Structure of the coefficients set Omega. Each coefficient is [start, zr]
511 : * meaning all the numbers of the form:
512 : * zeta_0 * p^start + ... + zeta_s * p^c (s = c - start)
513 : * with zeta_i roots of unity (powers of zq + zero), zeta_0 = 0 is
514 : * possible iff zr = 1 */
515 : static GEN
516 133 : StructureOmega(KRASNER_t *data, GEN *pnbpol)
517 : {
518 133 : GEN nbpol, O = cgetg(data->e + 1, t_VEC);
519 : long i;
520 :
521 : /* i = 0 */
522 133 : gel(O, 1) = mkvecsmall2(1, 0);
523 133 : nbpol = mulii(data->qm1, powiu(data->q, data->c - 1));
524 532 : for (i = 1; i < data->e; i++)
525 : {
526 399 : long v_start, zero = 0;
527 : GEN nbcf, p1;
528 399 : v_start = function_l(data->p, data->a, data->b, i);
529 399 : p1 = powiu(data->q, data->c - v_start);
530 399 : if (i == data->b)
531 98 : nbcf = mulii(p1, data->qm1);
532 : else
533 : {
534 301 : nbcf = mulii(p1, data->q);
535 301 : zero = 1;
536 : }
537 399 : gel(O, i+1) = mkvecsmall2(v_start, zero);
538 399 : nbpol = mulii(nbpol, nbcf);
539 : }
540 133 : *pnbpol = nbpol; return O;
541 : }
542 :
543 : /* a random element of the finite field */
544 : static GEN
545 37450 : RandomFF(KRASNER_t *data)
546 : {
547 37450 : long i, l = data->f + 2, p = itou(data->p);
548 37450 : GEN c = cgetg(l, t_POL);
549 37450 : c[1] = evalvarn(data->v);
550 86919 : for (i = 2; i < l; i++) gel(c, i) = utoi(random_Fl(p));
551 37450 : return ZX_renormalize(c, l);
552 : }
553 : static GEN
554 2709 : RandomPol(KRASNER_t *data, GEN Omega)
555 : {
556 2709 : long i, j, l = data->e + 3, end = data->c;
557 2709 : GEN pol = cgetg(l, t_POL);
558 2709 : pol[1] = evalsigne(1) | evalvarn(0);
559 13230 : for (i = 1; i <= data->e; i++)
560 : {
561 10521 : GEN c, cf = gel(Omega, i);
562 10521 : long st = cf[1], zr = cf[2];
563 : /* c = sum_{st <= j <= end} x_j p^j, where x_j are random Fq mod (p,upl)
564 : * If (!zr), insist on x_st != 0 */
565 : for (;;) {
566 13027 : c = RandomFF(data);
567 13027 : if (zr || signe(c)) break;
568 : }
569 34944 : for (j = 1; j <= end-st; j++)
570 24423 : c = ZX_add(c, ZX_Z_mul(RandomFF(data), gel(data->pk, j)));
571 10521 : c = ZX_Z_mul(c, gel(data->pk, st));
572 10521 : c = FpX_red(c, data->pr);
573 10521 : switch(degpol(c))
574 : {
575 672 : case -1: c = gen_0; break;
576 7770 : case 0: c = gel(c,2); break;
577 : }
578 10521 : gel(pol, i+1) = c;
579 : }
580 2709 : gel(pol, i+1) = gen_1; /* monic */
581 2709 : return pol;
582 : }
583 :
584 : static void
585 854 : CloneFieldData(FAD_t *fdata)
586 : {
587 854 : fdata->top = gclone(fdata->top);
588 854 : fdata->topr= gclone(fdata->topr);
589 854 : fdata->z = gclone(fdata->z);
590 854 : fdata->eis = gclone(fdata->eis);
591 854 : fdata->pi = gclone(fdata->pi);
592 854 : fdata->ipi = gclone(fdata->ipi);
593 854 : fdata->pik = gclone(fdata->pik);
594 854 : }
595 : static void
596 854 : FreeFieldData(FAD_t *fdata)
597 : {
598 854 : gunclone(fdata->top);
599 854 : gunclone(fdata->topr);
600 854 : gunclone(fdata->z);
601 854 : gunclone(fdata->eis);
602 854 : gunclone(fdata->pi);
603 854 : gunclone(fdata->ipi);
604 854 : gunclone(fdata->pik);
605 854 : }
606 :
607 : static GEN
608 133 : WildlyRamifiedCase(KRASNER_t *data)
609 : {
610 133 : long nbext, ct, fd, nb = 0, j;
611 : GEN nbpol, rpl, rep, Omega;
612 : FAD_t **vfd;
613 : pari_timer T;
614 133 : pari_sp av = avma, av2;
615 :
616 : /* Omega = vector giving the structure of the set Omega */
617 : /* nbpol = number of polynomials to consider = |Omega| */
618 133 : Omega = StructureOmega(data, &nbpol);
619 133 : nbext = itos_or_0(data->nbext);
620 133 : if (!nbext || (nbext & ~LGBITS))
621 0 : pari_err_OVERFLOW("padicfields [too many extensions]");
622 :
623 133 : if (DEBUGLEVEL>0) {
624 0 : err_printf("There are %ld extensions to find and %Ps polynomials to consider\n", nbext, nbpol);
625 0 : timer_start(&T);
626 : }
627 :
628 133 : vfd = (FAD_t**)new_chunk(nbext);
629 2541 : for (j = 0; j < nbext; j++) vfd[j] = (FAD_t*)new_chunk(sizeof(FAD_t));
630 :
631 133 : ct = 0;
632 133 : fd = 0;
633 133 : av2 = avma;
634 :
635 2842 : while (fd < nbext)
636 : { /* Jump randomly among the polynomials : seems best... */
637 2709 : rpl = RandomPol(data, Omega);
638 2709 : if (DEBUGLEVEL>3) err_printf("considering polynomial %Ps\n", rpl);
639 12516 : for (j = 0; j < ct; j++)
640 : {
641 11662 : nb = IsIsomorphic(data, vfd[j], rpl);
642 11662 : if (nb) break;
643 : }
644 2709 : if (!nb)
645 : {
646 854 : GEN topx = get_topx(data, rpl);
647 854 : FAD_t *f = (FAD_t*)vfd[ct];
648 854 : FieldData(data, f, rpl, topx);
649 854 : CloneFieldData(f);
650 854 : NbConjugateFields(data, f);
651 854 : nb = f->cj;
652 854 : fd += nb;
653 854 : ct++;
654 854 : if (DEBUGLEVEL>1)
655 0 : err_printf("%ld more extension%s\t(%ld/%ld, %ldms)\n",
656 : nb, (nb == 1)? "": "s", fd, nbext, timer_delay(&T));
657 : }
658 2709 : set_avma(av2);
659 : }
660 :
661 133 : rep = cgetg(ct+1, t_VEC);
662 987 : for (j = 0; j < ct; j++)
663 : {
664 854 : FAD_t *f = (FAD_t*)vfd[j];
665 854 : GEN topx = ZX_copy(f->top);
666 854 : setvarn(topx, 0);
667 854 : gel(rep, j+1) = mkvec2(topx, stoi(f->cj));
668 854 : FreeFieldData(f);
669 : }
670 133 : return gc_upto(av, rep);
671 : }
672 :
673 : /* return the minimal polynomial T of a generator of K^ur and the expression (mod pr)
674 : * in terms of T of a root of unity u such that u is l-maximal for all primes l
675 : * dividing g = (e,q-1). */
676 : static void
677 1715 : setUnramData(KRASNER_t *d)
678 : {
679 1715 : if (d->f == 1)
680 : {
681 560 : d->T = pol_x(d->v);
682 560 : d->u = pgener_Fp(d->p);
683 560 : d->frob = pol_x(d->v);
684 : }
685 : else
686 : {
687 1155 : GEN L, z, T, p = d->p;
688 1155 : d->T = T = init_Fq(p, d->f, d->v);
689 1155 : L = gel(factoru(ugcdui(d->e, d->qm1)), 1);
690 1155 : z = gener_FpXQ_local(T, p, zv_to_ZV(L));
691 1155 : d->u = ZpXQ_sqrtnlift(pol_1(d->v), d->qm1, z, T, p, d->r);
692 1155 : d->frob = ZpX_ZpXQ_liftroot(T, FpXQ_pow(pol_x(d->v), p, T, p), T, p, d->r);
693 : }
694 1715 : }
695 :
696 : /* return [ p^1, p^2, ..., p^c ] */
697 : static GEN
698 133 : get_pk(KRASNER_t *data)
699 : {
700 133 : long i, l = data->c + 1;
701 133 : GEN pk = cgetg(l, t_VEC), p = data->p;
702 133 : gel(pk, 1) = p;
703 455 : for (i = 2; i <= data->c; i++) gel(pk, i) = mulii(gel(pk, i-1), p);
704 133 : return pk;
705 : }
706 :
707 : /* Compute an absolute polynomial for all the totally ramified
708 : extensions of Q_p(z) of degree e and discriminant p^{e + j - 1}
709 : where z is a root of upl defining an unramified extension of Q_p */
710 : /* See padicfields for the meaning of flag */
711 : static GEN
712 1743 : GetRamifiedPol(GEN p, GEN efj, long flag)
713 : {
714 1743 : long e = efj[1], f = efj[2], j = efj[3], i, l;
715 1743 : const long v = 1;
716 : GEN L, pols;
717 : KRASNER_t data;
718 1743 : pari_sp av = avma;
719 :
720 1743 : if (DEBUGLEVEL>1)
721 0 : err_printf(" Computing extensions with decomposition [e, f, j] = [%ld, %ld, %ld]\n", e,f,j);
722 1743 : data.p = p;
723 1743 : data.e = e;
724 1743 : data.f = f;
725 1743 : data.j = j;
726 1743 : data.a = j/e;
727 1743 : data.b = j%e;
728 1743 : data.c = (e+2*j)/e+1;
729 1743 : data.q = powiu(p, f);
730 1743 : data.qm1 = subiu(data.q, 1);
731 1743 : data.v = v;
732 1743 : data.r = 1 + (long)ceildivuu(2*j + 3, e); /* enough precision */
733 1743 : data.pr = powiu(p, data.r);
734 1743 : data.prm1= diviiexact(data.pr, p);
735 1743 : data.nbext = NumberExtensions(&data);
736 :
737 1743 : if (flag == 2) return data.nbext;
738 :
739 1715 : setUnramData(&data);
740 1715 : if (DEBUGLEVEL>1)
741 0 : err_printf(" Unramified part %Ps\n", data.T);
742 1715 : data.roottable = NULL;
743 1715 : if (j)
744 : {
745 133 : if (lgefint(data.q) == 3)
746 : {
747 133 : ulong npol = upowuu(data.q[2], e+1);
748 133 : if (npol && npol < (1<<19)) data.roottable = const_vec(npol, NULL);
749 : }
750 133 : data.pk = get_pk(&data);
751 133 : L = WildlyRamifiedCase(&data);
752 133 : FreeRootTable(data.roottable);
753 : }
754 : else
755 1582 : L = TamelyRamifiedCase(&data);
756 :
757 1715 : pols = cgetg_copy(L, &l);
758 1715 : if (flag == 1)
759 : {
760 1631 : GEN E = utoipos(e), F = utoipos(f), D = utoi(f*(e+j-1));
761 4578 : for (i = 1; i < l; i++)
762 : {
763 2947 : GEN T = gel(L,i);
764 2947 : gel(pols, i) = mkvec5(ZX_copy(gel(T, 1)), E,F,D, icopy(gel(T, 2)));
765 : }
766 : }
767 : else
768 : {
769 350 : for (i = 1; i < l; i++)
770 : {
771 266 : GEN T = gel(L,i);
772 266 : gel(pols, i) = ZX_copy(gel(T,1));
773 : }
774 : }
775 1715 : return gc_upto(av, pols);
776 : }
777 :
778 : static GEN
779 483 : possible_efj(GEN p, long m)
780 : { /* maximal possible discriminant valuation d <= m * (1+v_p(m)) - 1 */
781 : /* 1) [j = 0, tame] d = m - f with f | m and v_p(f) = v_p(m), or
782 : * 2) [j > 0, wild] d >= m, j <= v_p(e)*e */
783 483 : ulong m1, pve, pp = p[2]; /* pp used only if v > 0 */
784 483 : long ve, v = u_pvalrem(m, p, &m1);
785 483 : GEN L, D = divisorsu(m1);
786 483 : long i, taum1 = lg(D)-1, nb = 0;
787 :
788 483 : if (v) {
789 49 : for (pve = 1,ve = 1; ve <= v; ve++) { pve *= pp; nb += pve * ve; }
790 21 : nb = itos_or_0(muluu(nb, zv_sum(D)));
791 21 : if (!nb || is_bigint( mului(pve, sqru(v)) ) )
792 0 : pari_err_OVERFLOW("padicfields [too many ramification possibilities]");
793 : }
794 483 : nb += taum1; /* upper bound for the number of possible triples [e,f,j] */
795 :
796 483 : L = cgetg(nb + 1, t_VEC);
797 : /* 1) tame */
798 2093 : for (nb=1, i=1; i < lg(D); i++)
799 : {
800 1610 : long e = D[i], f = m / e;
801 1610 : gel(L, nb++) = mkvecsmall3(e, f, 0);
802 : }
803 : /* 2) wild */
804 : /* Ore's condition: either
805 : * 1) j = v_p(e) * e, or
806 : * 2) j = a e + b, with 0 < b < e and v_p(b) <= a < v_p(e) */
807 511 : for (pve = 1, ve = 1; ve <= v; ve++)
808 : {
809 28 : pve *= pp; /* = p^ve */
810 56 : for (i = 1; i < lg(D); i++)
811 : {
812 28 : long a,b, e = D[i] * pve, f = m / e;
813 98 : for (b = 1; b < e; b++)
814 154 : for (a = u_lval(b, pp); a < ve; a++)
815 84 : gel(L, nb++) = mkvecsmall3(e, f, a*e + b);
816 28 : gel(L, nb++) = mkvecsmall3(e, f, ve*e);
817 : }
818 : }
819 483 : setlg(L, nb); return L;
820 : }
821 :
822 : static GEN
823 490 : pols_from_efj(pari_sp av, GEN EFJ, GEN p, long flag)
824 : {
825 : long i, l;
826 490 : GEN L = cgetg_copy(EFJ, &l);
827 490 : if (l == 1) { set_avma(av); return flag == 2? gen_0: cgetg(1, t_VEC); }
828 2233 : for (i = 1; i < l; i++) gel(L,i) = GetRamifiedPol(p, gel(EFJ,i), flag);
829 490 : if (flag == 2) return gc_INT(av, ZV_sum(L));
830 483 : return gc_GEN(av, shallowconcat1(L));
831 : }
832 :
833 : /* return a minimal list of polynomials generating all the extensions of
834 : Q_p of given degree N; if N is a t_VEC [n,d], return extensions of degree n
835 : and discriminant p^d. */
836 : /* Return only the polynomials if flag = 0 (default), also the ramification
837 : degree, the residual degree and the discriminant if flag = 1 and only the
838 : number of extensions if flag = 2 */
839 : GEN
840 490 : padicfields0(GEN p, GEN N, long flag)
841 : {
842 490 : pari_sp av = avma;
843 490 : long m = 0, d = -1;
844 : GEN L;
845 :
846 490 : if (typ(p) != t_INT) pari_err_TYPE("padicfields",p);
847 : /* be nice to silly users */
848 490 : if (!BPSW_psp(p)) pari_err_PRIME("padicfields",p);
849 490 : switch(typ(N))
850 : {
851 7 : case t_VEC:
852 7 : if (lg(N) != 3) pari_err_TYPE("padicfields",N);
853 7 : d = gtos(gel(N,2));
854 7 : N = gel(N,1); /* fall through */
855 490 : case t_INT:
856 490 : m = itos(N);
857 490 : if (m <= 0) pari_err_DOMAIN("padicfields", "degree", "<=", gen_0,N);
858 490 : break;
859 0 : default:
860 0 : pari_err_TYPE("padicfields",N);
861 : }
862 490 : if (d >= 0) return padicfields(p, m, d, flag);
863 483 : L = possible_efj(p, m);
864 483 : return pols_from_efj(av, L, p, flag);
865 : }
866 :
867 : GEN
868 7 : padicfields(GEN p, long m, long d, long flag)
869 : {
870 7 : long av = avma;
871 7 : GEN L = possible_efj_by_d(p, m, d);
872 7 : return pols_from_efj(av, L, p, flag);
873 : }
|
