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