1 /* Copyright (C) 2016 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 /*******************************************************************/
19 /** **/
20 /** Isomorphisms between finite fields **/
21 /** **/
22 /*******************************************************************/
23 static void
err_Flxq(const char * s,GEN P,ulong l)24 err_Flxq(const char *s, GEN P, ulong l)
25 {
26 if (!uisprime(l)) pari_err_PRIME(s, utoi(l));
27 pari_err_IRREDPOL(s, Flx_to_ZX(get_Flx_mod(P)));
28 }
29 static void
err_FpXQ(const char * s,GEN P,GEN l)30 err_FpXQ(const char *s, GEN P, GEN l)
31 {
32 if (!BPSW_psp(l)) pari_err_PRIME(s, l);
33 pari_err_IRREDPOL(s, get_FpX_mod(P));
34 }
35
36 /* compute the reciprocical isomorphism of S mod T,p, i.e. V such that
37 V(S)=X mod T,p*/
38 GEN
Flxq_ffisom_inv(GEN S,GEN T,ulong p)39 Flxq_ffisom_inv(GEN S,GEN T, ulong p)
40 {
41 pari_sp ltop = avma;
42 long n = get_Flx_degree(T);
43 GEN M = Flxq_matrix_pow(S,n,n,T,p);
44 GEN V = Flm_Flc_invimage(M, vecsmall_ei(n, 2), p);
45 if (!V) err_Flxq("Flxq_ffisom_inv", T, p);
46 return gerepileupto(ltop, Flv_to_Flx(V, get_Flx_var(T)));
47 }
48
49 GEN
FpXQ_ffisom_inv(GEN S,GEN T,GEN p)50 FpXQ_ffisom_inv(GEN S,GEN T, GEN p)
51 {
52 pari_sp ltop = avma;
53 long n = get_FpX_degree(T);
54 GEN M = FpXQ_matrix_pow(S,n,n,T,p);
55 GEN V = FpM_FpC_invimage(M, col_ei(n, 2), p);
56 if (!V) err_FpXQ("Flxq_ffisom_inv", T, p);
57 return gerepilecopy(ltop, RgV_to_RgX(V, get_FpX_var(T)));
58 }
59
60 /* Let M the matrix of the Frobenius automorphism of Fp[X]/(T). Compute M^d
61 * TODO: use left-right binary (tricky!) */
62 GEN
Flm_Frobenius_pow(GEN M,long d,GEN T,ulong p)63 Flm_Frobenius_pow(GEN M, long d, GEN T, ulong p)
64 {
65 pari_sp ltop=avma;
66 long i,l = get_Flx_degree(T);
67 GEN R, W = gel(M,2);
68 for (i = 2; i <= d; ++i) W = Flm_Flc_mul(M,W,p);
69 R=Flxq_matrix_pow(Flv_to_Flx(W,get_Flx_var(T)),l,l,T,p);
70 return gerepileupto(ltop,R);
71 }
72
73 GEN
FpM_Frobenius_pow(GEN M,long d,GEN T,GEN p)74 FpM_Frobenius_pow(GEN M, long d, GEN T, GEN p)
75 {
76 pari_sp ltop=avma;
77 long i,l = get_FpX_degree(T);
78 GEN R, W = gel(M,2);
79 for (i = 2; i <= d; ++i) W = FpM_FpC_mul(M,W,p);
80 R=FpXQ_matrix_pow(RgV_to_RgX(W, get_FpX_var(T)),l,l,T,p);
81 return gerepilecopy(ltop,R);
82 }
83
84 /* Essentially we want to compute FqM_ker(MA-pol_x(v),U,l)
85 * To avoid use of matrix in Fq we compute FpM_ker(U(MA),l) then recover the
86 * eigenvalue by Galois action */
87 static GEN
Flx_Flm_Flc_eval(GEN U,GEN MA,GEN a,ulong p)88 Flx_Flm_Flc_eval(GEN U, GEN MA, GEN a, ulong p)
89 {
90 long i, l = lg(U);
91 GEN b = Flv_Fl_mul(a, uel(U, l-1), p);
92 for (i=l-2; i>=2; i--)
93 b = Flv_add(Flm_Flc_mul(MA, b, p), Flv_Fl_mul(a, uel(U, i), p), p);
94 return b;
95 }
96
97 static GEN
Flx_intersect_ker(GEN P,GEN MA,GEN U,ulong p)98 Flx_intersect_ker(GEN P, GEN MA, GEN U, ulong p)
99 {
100 pari_sp ltop = avma;
101 long i, vp = get_Flx_var(P), vu = get_Flx_var(U), r = get_Flx_degree(U);
102 GEN V, A, R;
103 ulong ib0;
104 pari_timer T;
105 if (DEBUGLEVEL>=4) timer_start(&T);
106 V = Flx_div(Flx_Fl_add(monomial_Flx(1, get_Flx_degree(P), vu), p-1, p), U, p);
107 do
108 {
109 A = Flx_Flm_Flc_eval(V, MA, random_Flv(lg(MA)-1, p), p);
110 } while (zv_equal0(A));
111 if (DEBUGLEVEL>=4) timer_printf(&T,"matrix polcyclo");
112 /*The formula is
113 * a_{r-1} = -\phi(a_0)/b_0
114 * a_{i-1} = \phi(a_i)+b_ia_{r-1} i=r-1 to 1
115 * Where a_0=A[1] and b_i=U[i+2] */
116 ib0 = Fl_inv(Fl_neg(U[2], p), p);
117 R = cgetg(r+1,t_MAT);
118 gel(R,1) = A;
119 gel(R,r) = Flm_Flc_mul(MA, Flv_Fl_mul(A,ib0, p), p);
120 for(i=r-1; i>1; i--)
121 {
122 gel(R,i) = Flm_Flc_mul(MA,gel(R,i+1),p);
123 Flv_add_inplace(gel(R,i), Flv_Fl_mul(gel(R,r), U[i+2], p), p);
124 }
125 return gerepileupto(ltop, Flm_to_FlxX(Flm_transpose(R),vp,vu));
126 }
127
128 static GEN
FpX_FpM_FpC_eval(GEN U,GEN MA,GEN a,GEN p)129 FpX_FpM_FpC_eval(GEN U, GEN MA, GEN a, GEN p)
130 {
131 long i, l = lg(U);
132 GEN b = FpC_Fp_mul(a, gel(U, l-1), p);
133 for (i=l-2; i>=2; i--)
134 b = FpC_add(FpM_FpC_mul(MA, b, p), FpC_Fp_mul(a, gel(U, i), p), p);
135 return b;
136 }
137
138 static GEN
FpX_intersect_ker(GEN P,GEN MA,GEN U,GEN l)139 FpX_intersect_ker(GEN P, GEN MA, GEN U, GEN l)
140 {
141 pari_sp ltop = avma;
142 long i, vp = get_FpX_var(P), vu = get_FpX_var(U), r = get_FpX_degree(U);
143 GEN V, A, R, ib0;
144 pari_timer T;
145 if (DEBUGLEVEL>=4) timer_start(&T);
146 V = FpX_div(FpX_Fp_sub(pol_xn(get_FpX_degree(P), vu), gen_1, l), U, l);
147 do
148 {
149 A = FpX_FpM_FpC_eval(V, MA, random_FpC(lg(MA)-1, l), l);
150 } while (ZV_equal0(A));
151 if (DEBUGLEVEL>=4) timer_printf(&T,"matrix polcyclo");
152 /*The formula is
153 * a_{r-1} = -\phi(a_0)/b_0
154 * a_{i-1} = \phi(a_i)+b_ia_{r-1} i=r-1 to 1
155 * Where a_0=A[1] and b_i=U[i+2] */
156 ib0 = Fp_inv(negi(gel(U,2)),l);
157 R = cgetg(r+1,t_MAT);
158 gel(R,1) = A;
159 gel(R,r) = FpM_FpC_mul(MA, FpC_Fp_mul(A,ib0,l), l);
160 for(i=r-1;i>1;i--)
161 gel(R,i) = FpC_add(FpM_FpC_mul(MA,gel(R,i+1),l),
162 FpC_Fp_mul(gel(R,r), gel(U,i+2), l),l);
163 return gerepilecopy(ltop,RgM_to_RgXX(shallowtrans(R),vp,vu));
164 }
165
166 /* n must divide both the degree of P and Q. Compute SP and SQ such
167 * that the subfield of FF_l[X]/(P) generated by SP and the subfield of
168 * FF_l[X]/(Q) generated by SQ are isomorphic of degree n. P and Q do
169 * not need to be of the same variable; if MA, resp. MB, is not NULL, must be
170 * the matrix of the Frobenius map in FF_l[X]/(P), resp. FF_l[X]/(Q).
171 * Implementation choice: we assume the prime p is large so we handle
172 * Frobenius as matrices. */
173 void
Flx_ffintersect(GEN P,GEN Q,long n,ulong l,GEN * SP,GEN * SQ,GEN MA,GEN MB)174 Flx_ffintersect(GEN P, GEN Q, long n, ulong l,GEN *SP, GEN *SQ, GEN MA, GEN MB)
175 {
176 pari_sp ltop = avma;
177 long vp = get_Flx_var(P), vq = get_Flx_var(Q);
178 long np = get_Flx_degree(P), nq = get_Flx_degree(Q), e;
179 ulong pg;
180 GEN A, B, Ap, Bp;
181 if (np<=0) pari_err_IRREDPOL("FpX_ffintersect", P);
182 if (nq<=0) pari_err_IRREDPOL("FpX_ffintersect", Q);
183 if (n<=0 || np%n || nq%n)
184 pari_err_TYPE("FpX_ffintersect [bad degrees]",stoi(n));
185 e = u_lvalrem(n, l, &pg);
186 if(!MA) MA = Flx_matFrobenius(P,l);
187 if(!MB) MB = Flx_matFrobenius(Q,l);
188 A = Ap = pol0_Flx(vp);
189 B = Bp = pol0_Flx(vq);
190 if (pg > 1)
191 {
192 pari_timer T;
193 GEN ipg = utoipos(pg);
194 if (l%pg == 1)
195 { /* more efficient special case */
196 ulong L, z, An, Bn;
197 z = Fl_neg(rootsof1_Fl(pg, l), l);
198 if (DEBUGLEVEL>=4) timer_start(&T);
199 A = Flm_ker(Flm_Fl_add(MA, z, l),l);
200 if (lg(A)!=2) err_Flxq("FpX_ffintersect",P,l);
201 A = Flv_to_Flx(gel(A,1),vp);
202
203 B = Flm_ker(Flm_Fl_add(MB, z, l),l);
204 if (lg(B)!=2) err_Flxq("FpX_ffintersect",Q,l);
205 B = Flv_to_Flx(gel(B,1),vq);
206
207 if (DEBUGLEVEL>=4) timer_printf(&T, "FpM_ker");
208 An = Flxq_powu(A,pg,P,l)[2];
209 Bn = Flxq_powu(B,pg,Q,l)[2];
210 if (!Bn) pari_err_IRREDPOL("FpX_ffintersect", mkvec2(P,Q));
211 z = Fl_div(An,Bn,l);
212 L = Fl_sqrtn(z, pg, l, NULL);
213 if (L==ULONG_MAX) pari_err_IRREDPOL("FpX_ffintersect", mkvec2(P,Q));
214 if (DEBUGLEVEL>=4) timer_printf(&T, "Fp_sqrtn");
215 B = Flx_Fl_mul(B,L,l);
216 }
217 else
218 {
219 GEN L, An, Bn, z, U;
220 U = gmael(Flx_factor(ZX_to_Flx(polcyclo(pg, fetch_var()),l),l),1,1);
221 A = Flx_intersect_ker(P, MA, U, l);
222 B = Flx_intersect_ker(Q, MB, U, l);
223 if (DEBUGLEVEL>=4) timer_start(&T);
224 An = gel(FlxYqq_pow(A,ipg,P,U,l),2);
225 Bn = gel(FlxYqq_pow(B,ipg,Q,U,l),2);
226 if (DEBUGLEVEL>=4) timer_printf(&T,"pows [P,Q]");
227 z = Flxq_div(An,Bn,U,l);
228 L = Flxq_sqrtn(z,ipg,U,l,NULL);
229 if (!L) pari_err_IRREDPOL("FpX_ffintersect", mkvec2(P,Q));
230 if (DEBUGLEVEL>=4) timer_printf(&T,"FpXQ_sqrtn");
231 B = FlxqX_Flxq_mul(B,L,U,l);
232 A = FlxY_evalx(A,0,l);
233 B = FlxY_evalx(B,0,l);
234 (void)delete_var();
235 }
236 }
237 if (e)
238 {
239 GEN VP, VQ, Ay, By;
240 ulong lmun = l-1;
241 long j;
242 MA = Flm_Fl_add(MA,lmun,l);
243 MB = Flm_Fl_add(MB,lmun,l);
244 Ay = pol1_Flx(vp);
245 By = pol1_Flx(vq);
246 VP = vecsmall_ei(np, 1);
247 VQ = np == nq? VP: vecsmall_ei(nq, 1); /* save memory */
248 for(j=0;j<e;j++)
249 {
250 if (j)
251 {
252 Ay = Flxq_mul(Ay,Flxq_powu(Ap,lmun,P,l),P,l);
253 VP = Flx_to_Flv(Ay,np);
254 }
255 Ap = Flm_Flc_invimage(MA,VP,l);
256 if (!Ap) err_Flxq("FpX_ffintersect",P,l);
257 Ap = Flv_to_Flx(Ap,vp);
258
259 if (j)
260 {
261 By = Flxq_mul(By,Flxq_powu(Bp,lmun,Q,l),Q,l);
262 VQ = Flx_to_Flv(By,nq);
263 }
264 Bp = Flm_Flc_invimage(MB,VQ,l);
265 if (!Bp) err_Flxq("FpX_ffintersect",Q,l);
266 Bp = Flv_to_Flx(Bp,vq);
267 }
268 }
269 *SP = Flx_add(A,Ap,l);
270 *SQ = Flx_add(B,Bp,l);
271 gerepileall(ltop,2,SP,SQ);
272 }
273
274 /* Let l be a prime number, P, Q in Z[X]; both are irreducible modulo l and
275 * degree(P) divides degree(Q). Output a monomorphism between F_l[X]/(P) and
276 * F_l[X]/(Q) as a polynomial R such that Q | P(R) mod l. If P and Q have the
277 * same degree, it is of course an isomorphism. */
278 GEN
Flx_ffisom(GEN P,GEN Q,ulong l)279 Flx_ffisom(GEN P,GEN Q,ulong l)
280 {
281 pari_sp av = avma;
282 GEN SP, SQ, R;
283 Flx_ffintersect(P,Q,get_Flx_degree(P),l,&SP,&SQ,NULL,NULL);
284 R = Flxq_ffisom_inv(SP,P,l);
285 return gerepileupto(av, Flx_Flxq_eval(R,SQ,Q,l));
286 }
287
288 void
FpX_ffintersect(GEN P,GEN Q,long n,GEN l,GEN * SP,GEN * SQ,GEN MA,GEN MB)289 FpX_ffintersect(GEN P, GEN Q, long n, GEN l, GEN *SP, GEN *SQ, GEN MA, GEN MB)
290 {
291 pari_sp ltop = avma;
292 long vp, vq, np, nq, e;
293 ulong pg;
294 GEN A, B, Ap, Bp;
295 if (lgefint(l)==3)
296 {
297 ulong pp = l[2];
298 GEN Pp = ZX_to_Flx(P,pp), Qp = ZX_to_Flx(Q,pp);
299 GEN MAp = MA ? ZM_to_Flm(MA, pp): NULL;
300 GEN MBp = MB ? ZM_to_Flm(MB, pp): NULL;
301 Flx_ffintersect(Pp, Qp, n, pp, SP, SQ, MAp, MBp);
302 *SP = Flx_to_ZX(*SP); *SQ = Flx_to_ZX(*SQ);
303 gerepileall(ltop,2,SP,SQ);
304 return;
305 }
306 vp = get_FpX_var(P); np = get_FpX_degree(P);
307 vq = get_FpX_var(Q); nq = get_FpX_degree(Q);
308 if (np<=0) pari_err_IRREDPOL("FpX_ffintersect", P);
309 if (nq<=0) pari_err_IRREDPOL("FpX_ffintersect", Q);
310 if (n<=0 || np%n || nq%n)
311 pari_err_TYPE("FpX_ffintersect [bad degrees]",stoi(n));
312 e = u_pvalrem(n, l, &pg);
313 if(!MA) MA = FpX_matFrobenius(P, l);
314 if(!MB) MB = FpX_matFrobenius(Q, l);
315 A = Ap = pol_0(vp);
316 B = Bp = pol_0(vq);
317 if (pg > 1)
318 {
319 GEN ipg = utoipos(pg);
320 pari_timer T;
321 if (umodiu(l,pg) == 1)
322 /* No need to use relative extension, so don't. (Well, now we don't
323 * in the other case either, but this special case is more efficient) */
324 {
325 GEN L, An, Bn, z;
326 z = negi( rootsof1u_Fp(pg, l) );
327 if (DEBUGLEVEL>=4) timer_start(&T);
328 A = FpM_ker(RgM_Rg_add_shallow(MA, z),l);
329 if (lg(A)!=2) err_FpXQ("FpX_ffintersect",P,l);
330 A = RgV_to_RgX(gel(A,1),vp);
331
332 B = FpM_ker(RgM_Rg_add_shallow(MB, z),l);
333 if (lg(B)!=2) err_FpXQ("FpX_ffintersect",Q,l);
334 B = RgV_to_RgX(gel(B,1),vq);
335
336 if (DEBUGLEVEL>=4) timer_printf(&T, "FpM_ker");
337 An = gel(FpXQ_pow(A,ipg,P,l),2);
338 Bn = gel(FpXQ_pow(B,ipg,Q,l),2);
339 if (!signe(Bn)) pari_err_IRREDPOL("FpX_ffintersect", mkvec2(P,Q));
340 z = Fp_div(An,Bn,l);
341 L = Fp_sqrtn(z,ipg,l,NULL);
342 if (!L) pari_err_IRREDPOL("FpX_ffintersect", mkvec2(P,Q));
343 if (DEBUGLEVEL>=4) timer_printf(&T, "Fp_sqrtn");
344 B = FpX_Fp_mul(B,L,l);
345 }
346 else
347 {
348 GEN L, An, Bn, z, U;
349 U = gmael(FpX_factor(polcyclo(pg,fetch_var()),l),1,1);
350 A = FpX_intersect_ker(P, MA, U, l);
351 B = FpX_intersect_ker(Q, MB, U, l);
352 if (DEBUGLEVEL>=4) timer_start(&T);
353 An = gel(FpXYQQ_pow(A,ipg,P,U,l),2);
354 Bn = gel(FpXYQQ_pow(B,ipg,Q,U,l),2);
355 if (DEBUGLEVEL>=4) timer_printf(&T,"pows [P,Q]");
356 if (!signe(Bn)) pari_err_IRREDPOL("FpX_ffintersect", mkvec2(P,Q));
357 z = Fq_div(An,Bn,U,l);
358 L = Fq_sqrtn(z,ipg,U,l,NULL);
359 if (!L) pari_err_IRREDPOL("FpX_ffintersect", mkvec2(P,Q));
360 if (DEBUGLEVEL>=4) timer_printf(&T,"FpXQ_sqrtn");
361 B = FqX_Fq_mul(B,L,U,l);
362 A = FpXY_evalx(A,gen_0,l);
363 B = FpXY_evalx(B,gen_0,l);
364 (void)delete_var();
365 }
366 }
367 if (e)
368 {
369 GEN VP, VQ, Ay, By, lmun = subiu(l,1);
370 long j;
371 MA = RgM_Rg_add_shallow(MA,gen_m1);
372 MB = RgM_Rg_add_shallow(MB,gen_m1);
373 Ay = pol_1(vp);
374 By = pol_1(vq);
375 VP = col_ei(np, 1);
376 VQ = np == nq? VP: col_ei(nq, 1); /* save memory */
377 for(j=0;j<e;j++)
378 {
379 if (j)
380 {
381 Ay = FpXQ_mul(Ay,FpXQ_pow(Ap,lmun,P,l),P,l);
382 VP = RgX_to_RgC(Ay,np);
383 }
384 Ap = FpM_FpC_invimage(MA,VP,l);
385 if (!Ap) err_FpXQ("FpX_ffintersect",P,l);
386 Ap = RgV_to_RgX(Ap,vp);
387
388 if (j)
389 {
390 By = FpXQ_mul(By,FpXQ_pow(Bp,lmun,Q,l),Q,l);
391 VQ = RgX_to_RgC(By,nq);
392 }
393 Bp = FpM_FpC_invimage(MB,VQ,l);
394 if (!Bp) err_FpXQ("FpX_ffintersect",Q,l);
395 Bp = RgV_to_RgX(Bp,vq);
396 }
397 }
398 *SP = FpX_add(A,Ap,l);
399 *SQ = FpX_add(B,Bp,l);
400 gerepileall(ltop,2,SP,SQ);
401 }
402 /* Let l be a prime number, P, Q in Z[X]; both are irreducible modulo l and
403 * degree(P) divides degree(Q). Output a monomorphism between F_l[X]/(P) and
404 * F_l[X]/(Q) as a polynomial R such that Q | P(R) mod l. If P and Q have the
405 * same degree, it is of course an isomorphism. */
406 GEN
FpX_ffisom(GEN P,GEN Q,GEN p)407 FpX_ffisom(GEN P, GEN Q, GEN p)
408 {
409 pari_sp av = avma;
410 GEN SP, SQ, R;
411 if (lgefint(p)==3)
412 {
413 ulong pp = p[2];
414 GEN R = Flx_ffisom(ZX_to_Flx(P,pp), ZX_to_Flx(Q,pp), pp);
415 return gerepileupto(av, Flx_to_ZX(R));
416 }
417 FpX_ffintersect(P,Q,get_FpX_degree(P),p,&SP,&SQ,NULL,NULL);
418 R = FpXQ_ffisom_inv(SP,P,p);
419 return gerepileupto(av, FpX_FpXQ_eval(R,SQ,Q,p));
420 }
421
422 /* Let l be a prime number, P a ZX irreducible modulo l, MP the matrix of the
423 * Frobenius automorphism of F_l[X]/(P).
424 * Factor P over the subfield of F_l[X]/(P) of index d. */
425 static GEN
FpX_factorgalois(GEN P,GEN l,long d,long w,GEN MP)426 FpX_factorgalois(GEN P, GEN l, long d, long w, GEN MP)
427 {
428 pari_sp ltop = avma;
429 GEN R, V, Tl, z, M;
430 long v = get_FpX_var(P), n = get_FpX_degree(P);
431 long k, m = n/d;
432
433 /* x - y */
434 if (m == 1) return deg1pol_shallow(gen_1, deg1pol_shallow(subis(l,1), gen_0, w), v);
435 M = FpM_Frobenius_pow(MP,d,P,l);
436
437 Tl = leafcopy(P); setvarn(Tl,w);
438 V = cgetg(m+1,t_VEC);
439 gel(V,1) = pol_x(w);
440 z = gel(M,2);
441 gel(V,2) = RgV_to_RgX(z,w);
442 for(k=3;k<=m;k++)
443 {
444 z = FpM_FpC_mul(M,z,l);
445 gel(V,k) = RgV_to_RgX(z,w);
446 }
447 R = FqV_roots_to_pol(V,Tl,l,v);
448 return gerepileupto(ltop,R);
449 }
450 /* same: P is an Flx, MP an Flm */
451 static GEN
Flx_factorgalois(GEN P,ulong l,long d,long w,GEN MP)452 Flx_factorgalois(GEN P, ulong l, long d, long w, GEN MP)
453 {
454 pari_sp ltop = avma;
455 GEN R, V, Tl, z, M;
456 long k, n = get_Flx_degree(P), m = n/d;
457 long v = get_Flx_var(P);
458
459 if (m == 1) {
460 R = polx_Flx(v);
461 gel(R,2) = z = polx_Flx(w); z[3] = l - 1; /* - y */
462 gel(R,3) = pol1_Flx(w);
463 return R; /* x - y */
464 }
465 M = Flm_Frobenius_pow(MP,d,P,l);
466
467 Tl = leafcopy(P); Tl[1] = w;
468 V = cgetg(m+1,t_VEC);
469 gel(V,1) = polx_Flx(w);
470 z = gel(M,2);
471 gel(V,2) = Flv_to_Flx(z,w);
472 for(k=3;k<=m;k++)
473 {
474 z = Flm_Flc_mul(M,z,l);
475 gel(V,k) = Flv_to_Flx(z,w);
476 }
477 R = FlxqV_roots_to_pol(V,Tl,l,v);
478 return gerepileupto(ltop,R);
479 }
480
481 GEN
Flx_factorff_irred(GEN P,GEN Q,ulong p)482 Flx_factorff_irred(GEN P, GEN Q, ulong p)
483 {
484 pari_sp ltop = avma, av;
485 GEN SP, SQ, MP, MQ, M, FP, FQ, E, V, IR, res;
486 long np = get_Flx_degree(P), nq = get_Flx_degree(Q), d = ugcd(np,nq);
487 long i, vp = get_Flx_var(P), vq = get_Flx_var(Q);
488 if (d==1) retmkcol(Flx_to_FlxX(P, vq));
489 FQ = Flx_matFrobenius(Q,p);
490 av = avma;
491 FP = Flx_matFrobenius(P,p);
492 Flx_ffintersect(P,Q,d,p,&SP,&SQ, FP, FQ);
493 E = Flx_factorgalois(P,p,d,vq, FP);
494 E = FlxX_to_Flm(E,np);
495 MP= Flxq_matrix_pow(SP,np,d,P,p);
496 IR= gel(Flm_indexrank(MP,p),1);
497 E = rowpermute(E, IR);
498 M = rowpermute(MP,IR);
499 M = Flm_inv(M,p);
500 MQ= Flxq_matrix_pow(SQ,nq,d,Q,p);
501 M = Flm_mul(MQ,M,p);
502 M = Flm_mul(M,E,p);
503 M = gerepileupto(av,M);
504 V = cgetg(d+1,t_VEC);
505 gel(V,1) = M;
506 for(i=2;i<=d;i++)
507 gel(V,i) = Flm_mul(FQ,gel(V,i-1),p);
508 res = cgetg(d+1,t_COL);
509 for(i=1;i<=d;i++)
510 gel(res,i) = Flm_to_FlxX(gel(V,i),vp,vq);
511 return gerepileupto(ltop,res);
512 }
513
514 /* P,Q irreducible over F_p. Factor P over FF_p[X] / Q [factors are ordered as
515 * a Frobenius cycle] */
516 GEN
FpX_factorff_irred(GEN P,GEN Q,GEN p)517 FpX_factorff_irred(GEN P, GEN Q, GEN p)
518 {
519 pari_sp ltop = avma, av;
520 GEN res;
521 long np = get_FpX_degree(P), nq = get_FpX_degree(Q), d = ugcd(np,nq);
522 if (d==1) return mkcolcopy(P);
523
524 if (lgefint(p)==3)
525 {
526 ulong pp = p[2];
527 GEN F = Flx_factorff_irred(ZX_to_Flx(P,pp), ZX_to_Flx(Q,pp), pp);
528 long i, lF = lg(F);
529 res = cgetg(lF, t_COL);
530 for(i=1; i<lF; i++)
531 gel(res,i) = FlxX_to_ZXX(gel(F,i));
532 }
533 else
534 {
535 GEN SP, SQ, MP, MQ, M, FP, FQ, E, V, IR;
536 long i, vp = get_FpX_var(P), vq = get_FpX_var(Q);
537 FQ = FpX_matFrobenius(Q,p);
538 av = avma;
539 FP = FpX_matFrobenius(P,p);
540 FpX_ffintersect(P,Q,d,p,&SP,&SQ,FP,FQ);
541
542 E = FpX_factorgalois(P,p,d,vq,FP);
543 E = RgXX_to_RgM(E,np);
544 MP= FpXQ_matrix_pow(SP,np,d,P,p);
545 IR= gel(FpM_indexrank(MP,p),1);
546 E = rowpermute(E, IR);
547 M = rowpermute(MP,IR);
548 M = FpM_inv(M,p);
549 MQ= FpXQ_matrix_pow(SQ,nq,d,Q,p);
550 M = FpM_mul(MQ,M,p);
551 M = FpM_mul(M,E,p);
552 M = gerepileupto(av,M);
553 V = cgetg(d+1,t_VEC);
554 gel(V,1) = M;
555 for(i=2;i<=d;i++)
556 gel(V,i) = FpM_mul(FQ,gel(V,i-1),p);
557 res = cgetg(d+1,t_COL);
558 for(i=1;i<=d;i++)
559 gel(res,i) = RgM_to_RgXX(gel(V,i),vp,vq);
560 }
561 return gerepilecopy(ltop,res);
562 }
563
564 /* not memory-clean, as Flx_factorff_i, returning only linear factors */
565 static GEN
Flx_rootsff_i(GEN P,GEN T,ulong p)566 Flx_rootsff_i(GEN P, GEN T, ulong p)
567 {
568 GEN V, F = gel(Flx_factor(P,p), 1);
569 long i, lfact = 1, nmax = lgpol(P), n = lg(F), dT = get_Flx_degree(T);
570
571 V = cgetg(nmax,t_COL);
572 for(i=1;i<n;i++)
573 {
574 GEN R, Fi = gel(F,i);
575 long di = degpol(Fi), j, r;
576 if (dT % di) continue;
577 R = Flx_factorff_irred(gel(F,i),T,p);
578 r = lg(R);
579 for (j=1; j<r; j++,lfact++)
580 gel(V,lfact) = Flx_neg(gmael(R,j, 2), p);
581 }
582 setlg(V,lfact);
583 gen_sort_inplace(V, (void*) &cmp_Flx, &cmp_nodata, NULL);
584 return V;
585 }
586 GEN
Flx_rootsff(GEN P,GEN T,ulong p)587 Flx_rootsff(GEN P, GEN T, ulong p)
588 {
589 pari_sp av = avma;
590 return gerepilecopy(av, Flx_rootsff_i(P, T, p));
591 }
592
593 /* dummy implementation */
594 static GEN
F2x_rootsff_i(GEN P,GEN T)595 F2x_rootsff_i(GEN P, GEN T)
596 {
597 return FlxC_to_F2xC(Flx_rootsff_i(F2x_to_Flx(P), F2x_to_Flx(T), 2UL));
598 }
599
600 /* not memory-clean, as FpX_factorff_i, returning only linear factors */
601 static GEN
FpX_rootsff_i(GEN P,GEN T,GEN p)602 FpX_rootsff_i(GEN P, GEN T, GEN p)
603 {
604 GEN V, F;
605 long i, lfact, nmax, n, dT;
606 if (lgefint(p)==3)
607 {
608 ulong pp = p[2];
609 GEN V = Flx_rootsff_i(ZX_to_Flx(P,pp), ZXT_to_FlxT(T,pp), pp);
610 return FlxC_to_ZXC(V);
611 }
612 F = gel(FpX_factor(P,p), 1);
613 lfact = 1; nmax = lgpol(P); n = lg(F); dT = get_FpX_degree(T);
614
615 V = cgetg(nmax,t_COL);
616 for(i=1;i<n;i++)
617 {
618 GEN R, Fi = gel(F,i);
619 long di = degpol(Fi), j, r;
620 if (dT % di) continue;
621 R = FpX_factorff_irred(gel(F,i),T,p);
622 r = lg(R);
623 for (j=1; j<r; j++,lfact++)
624 gel(V,lfact) = Fq_to_FpXQ(Fq_neg(gmael(R,j, 2), T, p), T, p);
625 }
626 setlg(V,lfact);
627 gen_sort_inplace(V, (void*) &cmp_RgX, &cmp_nodata, NULL);
628 return V;
629 }
630 GEN
FpX_rootsff(GEN P,GEN T,GEN p)631 FpX_rootsff(GEN P, GEN T, GEN p)
632 {
633 pari_sp av = avma;
634 return gerepilecopy(av, FpX_rootsff_i(P, T, p));
635 }
636
637 static GEN
Flx_factorff_i(GEN P,GEN T,ulong p)638 Flx_factorff_i(GEN P, GEN T, ulong p)
639 {
640 GEN V, E, F = Flx_factor(P, p);
641 long i, lfact = 1, nmax = lgpol(P), n = lgcols(F);
642
643 V = cgetg(nmax,t_VEC);
644 E = cgetg(nmax,t_VECSMALL);
645 for(i=1;i<n;i++)
646 {
647 GEN R = Flx_factorff_irred(gmael(F,1,i),T,p), e = gmael(F,2,i);
648 long j, r = lg(R);
649 for (j=1; j<r; j++,lfact++)
650 {
651 gel(V,lfact) = gel(R,j);
652 gel(E,lfact) = e;
653 }
654 }
655 setlg(V,lfact);
656 setlg(E,lfact); return sort_factor_pol(mkvec2(V,E), cmp_Flx);
657 }
658
659 static long
simpleff_to_nbfact(GEN F,long dT)660 simpleff_to_nbfact(GEN F, long dT)
661 {
662 long i, l = lg(F), k = 0;
663 for (i = 1; i < l; i++) k += ugcd(uel(F,i), dT);
664 return k;
665 }
666
667 static long
Flx_nbfactff(GEN P,GEN T,ulong p)668 Flx_nbfactff(GEN P, GEN T, ulong p)
669 {
670 pari_sp av = avma;
671 GEN F = gel(Flx_degfact(P, p), 1);
672 long s = simpleff_to_nbfact(F, get_Flx_degree(T));
673 return gc_long(av,s);
674 }
675
676 /* dummy implementation */
677 static GEN
F2x_factorff_i(GEN P,GEN T)678 F2x_factorff_i(GEN P, GEN T)
679 {
680 GEN M = Flx_factorff_i(F2x_to_Flx(P), F2x_to_Flx(T), 2);
681 return mkvec2(FlxXC_to_F2xXC(gel(M,1)), gel(M,2));
682 }
683
684 /* not memory-clean */
685 static GEN
FpX_factorff_i(GEN P,GEN T,GEN p)686 FpX_factorff_i(GEN P, GEN T, GEN p)
687 {
688 GEN V, E, F = FpX_factor(P,p);
689 long i, lfact = 1, nmax = lgpol(P), n = lgcols(F);
690
691 V = cgetg(nmax,t_VEC);
692 E = cgetg(nmax,t_VECSMALL);
693 for(i=1;i<n;i++)
694 {
695 GEN R = FpX_factorff_irred(gmael(F,1,i),T,p), e = gmael(F,2,i);
696 long j, r = lg(R);
697 for (j=1; j<r; j++,lfact++)
698 {
699 gel(V,lfact) = gel(R,j);
700 gel(E,lfact) = e;
701 }
702 }
703 setlg(V,lfact);
704 setlg(E,lfact); return sort_factor_pol(mkvec2(V,E), cmp_RgX);
705 }
706
707 static long
FpX_nbfactff(GEN P,GEN T,GEN p)708 FpX_nbfactff(GEN P, GEN T, GEN p)
709 {
710 pari_sp av = avma;
711 GEN F = gel(FpX_degfact(P, p), 1);
712 long s = simpleff_to_nbfact(F, get_FpX_degree(T));
713 return gc_long(av,s);
714 }
715
716 GEN
FpX_factorff(GEN P,GEN T,GEN p)717 FpX_factorff(GEN P, GEN T, GEN p)
718 {
719 pari_sp av = avma;
720 return gerepilecopy(av, FpX_factorff_i(P, T, p));
721 }
722
723 /***********************************************************************/
724 /** **/
725 /** Factorisation over finite fields **/
726 /** **/
727 /***********************************************************************/
728
729 static GEN
FlxqXQ_halfFrobenius_i(GEN a,GEN xp,GEN Xp,GEN S,GEN T,ulong p)730 FlxqXQ_halfFrobenius_i(GEN a, GEN xp, GEN Xp, GEN S, GEN T, ulong p)
731 {
732 GEN ap2 = FlxqXQ_powu(a, p>>1, S, T, p);
733 GEN V = FlxqXQ_autsum(mkvec3(xp, Xp, ap2), get_Flx_degree(T), S, T, p);
734 return gel(V,3);
735 }
736
737 GEN
FlxqXQ_halfFrobenius(GEN a,GEN S,GEN T,ulong p)738 FlxqXQ_halfFrobenius(GEN a, GEN S, GEN T, ulong p)
739 {
740 long vT = get_Flx_var(T);
741 GEN xp, Xp;
742 T = Flx_get_red(T, p);
743 S = FlxqX_get_red(S, T, p);
744 xp = Flx_Frobenius(T, p);
745 Xp = FlxqXQ_powu(polx_FlxX(get_FlxqX_var(S), vT), p, S, T, p);
746 return FlxqXQ_halfFrobenius_i(a, xp, Xp, S, T, p);
747 }
748
749 static GEN
FpXQXQ_halfFrobenius_i(GEN a,GEN xp,GEN Xp,GEN S,GEN T,GEN p)750 FpXQXQ_halfFrobenius_i(GEN a, GEN xp, GEN Xp, GEN S, GEN T, GEN p)
751 {
752 GEN ap2 = FpXQXQ_pow(a, shifti(p,-1), S, T, p);
753 GEN V = FpXQXQ_autsum(mkvec3(xp, Xp, ap2), get_FpX_degree(T), S, T, p);
754 return gel(V, 3);
755 }
756
757 GEN
FpXQXQ_halfFrobenius(GEN a,GEN S,GEN T,GEN p)758 FpXQXQ_halfFrobenius(GEN a, GEN S, GEN T, GEN p)
759 {
760 pari_sp av = avma;
761 GEN z;
762 if (lgefint(p)==3)
763 {
764 ulong pp = p[2];
765 long v = get_FpX_var(T);
766 GEN Tp = ZXT_to_FlxT(T,pp), Sp = ZXXT_to_FlxXT(S, pp, v);
767 z = FlxX_to_ZXX(FlxqXQ_halfFrobenius(ZXX_to_FlxX(a,pp,v),Sp,Tp,pp));
768 }
769 else
770 {
771 GEN xp, Xp;
772 T = FpX_get_red(T, p);
773 S = FpXQX_get_red(S, T, p);
774 xp = FpX_Frobenius(T, p);
775 Xp = FpXQXQ_pow(pol_x(get_FpXQX_var(S)), p, S, T, p);
776 z = FpXQXQ_halfFrobenius_i(a, xp, Xp, S, T, p);
777 }
778 return gerepilecopy(av, z);
779 }
780
781 static GEN
FlxqXQ_Frobenius(GEN xp,GEN Xp,GEN f,GEN T,ulong p)782 FlxqXQ_Frobenius(GEN xp, GEN Xp, GEN f, GEN T, ulong p)
783 {
784 ulong dT = get_Flx_degree(T), df = get_FlxqX_degree(f);
785 GEN q = powuu(p,dT);
786 if (expi(q) >= expu(dT)*(long)usqrt(df))
787 return gel(FlxqXQ_autpow(mkvec2(xp, Xp), dT, f, T, p), 2);
788 else
789 return FlxqXQ_pow(pol_x(get_FlxqX_var(f)), q, f, T, p);
790 }
791
792 GEN
FlxqX_Frobenius(GEN S,GEN T,ulong p)793 FlxqX_Frobenius(GEN S, GEN T, ulong p)
794 {
795 pari_sp av = avma;
796 GEN X = polx_FlxX(get_FlxqX_var(S), get_Flx_var(T));
797 GEN xp = Flx_Frobenius(T, p);
798 GEN Xp = FlxqXQ_powu(X, p, S, T, p);
799 GEN Xq = FlxqXQ_Frobenius(xp, Xp, S, T, p);
800 return gerepilecopy(av, Xq);
801 }
802
803 static GEN
FpXQXQ_Frobenius(GEN xp,GEN Xp,GEN f,GEN T,GEN p)804 FpXQXQ_Frobenius(GEN xp, GEN Xp, GEN f, GEN T, GEN p)
805 {
806 ulong dT = get_FpX_degree(T), df = get_FpXQX_degree(f);
807 GEN q = powiu(p, dT);
808 if (expi(q) >= expu(dT)*(long)usqrt(df))
809 return gel(FpXQXQ_autpow(mkvec2(xp, Xp), dT, f, T, p), 2);
810 else
811 return FpXQXQ_pow(pol_x(get_FpXQX_var(f)), q, f, T, p);
812 }
813
814 GEN
FpXQX_Frobenius(GEN S,GEN T,GEN p)815 FpXQX_Frobenius(GEN S, GEN T, GEN p)
816 {
817 pari_sp av = avma;
818 GEN X = pol_x(get_FpXQX_var(S));
819 GEN xp = FpX_Frobenius(T, p);
820 GEN Xp = FpXQXQ_pow(X, p, S, T, p);
821 GEN Xq = FpXQXQ_Frobenius(xp, Xp, S, T, p);
822 return gerepilecopy(av, Xq);
823 }
824
825 static GEN
F2xqXQ_Frobenius(GEN xp,GEN Xp,GEN f,GEN T)826 F2xqXQ_Frobenius(GEN xp, GEN Xp, GEN f, GEN T)
827 {
828 ulong dT = get_F2x_degree(T), df = get_F2xqX_degree(f);
829 if (dT >= expu(dT)*usqrt(df))
830 return gel(F2xqXQ_autpow(mkvec2(xp, Xp), dT, f, T), 2);
831 else
832 {
833 long v = get_F2xqX_var(f), vT = get_F2x_var(T);
834 return F2xqXQ_pow(polx_F2xX(v,vT), int2n(dT), f, T);
835 }
836 }
837
838 static GEN
FlxqX_split_part(GEN f,GEN T,ulong p)839 FlxqX_split_part(GEN f, GEN T, ulong p)
840 {
841 long n = degpol(f);
842 GEN z, Xq, X = polx_FlxX(varn(f),get_Flx_var(T));
843 if (n <= 1) return f;
844 f = FlxqX_red(f, T, p);
845 Xq = FlxqX_Frobenius(f, T, p);
846 z = FlxX_sub(Xq, X , p);
847 return FlxqX_gcd(z, f, T, p);
848 }
849
850 GEN
FpXQX_split_part(GEN f,GEN T,GEN p)851 FpXQX_split_part(GEN f, GEN T, GEN p)
852 {
853 if(lgefint(p)==3)
854 {
855 ulong pp=p[2];
856 GEN Tp = ZXT_to_FlxT(T, pp);
857 GEN z = FlxqX_split_part(ZXX_to_FlxX(f, pp, get_Flx_var(T)), Tp, pp);
858 return FlxX_to_ZXX(z);
859 } else
860 {
861 long n = degpol(f);
862 GEN z, X = pol_x(varn(f));
863 if (n <= 1) return f;
864 f = FpXQX_red(f, T, p);
865 z = FpXQX_Frobenius(f, T, p);
866 z = FpXX_sub(z, X , p);
867 return FpXQX_gcd(z, f, T, p);
868 }
869 }
870
871 long
FpXQX_nbroots(GEN f,GEN T,GEN p)872 FpXQX_nbroots(GEN f, GEN T, GEN p)
873 {
874 pari_sp av = avma;
875 GEN z = FpXQX_split_part(f, T, p);
876 return gc_long(av, degpol(z));
877 }
878
879 long
FqX_nbroots(GEN f,GEN T,GEN p)880 FqX_nbroots(GEN f, GEN T, GEN p)
881 { return T ? FpXQX_nbroots(f, T, p): FpX_nbroots(f, p); }
882
883 long
FlxqX_nbroots(GEN f,GEN T,ulong p)884 FlxqX_nbroots(GEN f, GEN T, ulong p)
885 {
886 pari_sp av = avma;
887 GEN z = FlxqX_split_part(f, T, p);
888 return gc_long(av, degpol(z));
889 }
890
891 static GEN
FlxqX_Berlekamp_ker_i(GEN Xq,GEN S,GEN T,ulong p)892 FlxqX_Berlekamp_ker_i(GEN Xq, GEN S, GEN T, ulong p)
893 {
894 long j, N = get_FlxqX_degree(S);
895 GEN Q = FlxqXQ_matrix_pow(Xq,N,N,S,T,p);
896 for (j=1; j<=N; j++)
897 gcoeff(Q,j,j) = Flx_Fl_add(gcoeff(Q,j,j), p-1, p);
898 return FlxqM_ker(Q,T,p);
899 }
900
901 static GEN
FpXQX_Berlekamp_ker_i(GEN Xq,GEN S,GEN T,GEN p)902 FpXQX_Berlekamp_ker_i(GEN Xq, GEN S, GEN T, GEN p)
903 {
904 long j,N = get_FpXQX_degree(S);
905 GEN Q = FpXQXQ_matrix_pow(Xq,N,N,S,T,p);
906 for (j=1; j<=N; j++)
907 gcoeff(Q,j,j) = Fq_sub(gcoeff(Q,j,j), gen_1, T, p);
908 return FqM_ker(Q,T,p);
909 }
910
911 static long
isabsolutepol(GEN f)912 isabsolutepol(GEN f)
913 {
914 long i, l = lg(f);
915 for(i=2; i<l; i++)
916 {
917 GEN c = gel(f,i);
918 if (typ(c) == t_POL && degpol(c) > 0) return 0;
919 }
920 return 1;
921 }
922
923 #define set_irred(i) { if ((i)>ir) swap(t[i],t[ir]); ir++;}
924
925 static long
FlxqX_split_Berlekamp(GEN * t,GEN xp,GEN T,ulong p)926 FlxqX_split_Berlekamp(GEN *t, GEN xp, GEN T, ulong p)
927 {
928 GEN u = *t, a,b,vker,pol;
929 long vu = varn(u), vT = get_Flx_var(T), dT = get_Flx_degree(T);
930 long d, i, ir, L, la, lb;
931 GEN S, X, Xp, Xq;
932 if (degpol(u)==1) return 1;
933 T = Flx_get_red(T, p);
934 S = FlxqX_get_red(u, T, p);
935 X = polx_FlxX(get_FlxqX_var(S),get_Flx_var(T));
936 Xp = FlxqXQ_powu(X, p, S, T, p);
937 Xq = FlxqXQ_Frobenius(xp, Xp, S, T, p);
938 vker = FlxqX_Berlekamp_ker_i(Xq, S, T, p);
939 vker = Flm_to_FlxV(vker,u[1]);
940 d = lg(vker)-1;
941 ir = 0;
942 /* t[i] irreducible for i < ir, still to be treated for i < L */
943 for (L=1; L<d; )
944 {
945 pol= scalarpol(random_Flx(dT,vT,p),vu);
946 for (i=2; i<=d; i++)
947 pol = FlxX_add(pol, FlxqX_Flxq_mul(gel(vker,i),
948 random_Flx(dT,vT,p), T, p), p);
949 pol = FlxqX_red(pol,T,p);
950 for (i=ir; i<L && L<d; i++)
951 {
952 a = t[i]; la = degpol(a);
953 if (la == 1) { set_irred(i); }
954 else
955 {
956 pari_sp av = avma;
957 GEN S = FlxqX_get_red(a, T, p);
958 b = FlxqX_rem(pol, S, T,p);
959 if (degpol(b)<=0) { set_avma(av); continue; }
960 b = FlxqXQ_halfFrobenius_i(b, xp, FlxqX_rem(Xp, S, T, p), S, T, p);
961 if (degpol(b)<=0) { set_avma(av); continue; }
962 gel(b,2) = Flxq_sub(gel(b,2), gen_1,T,p);
963 b = FlxqX_gcd(a,b, T,p); lb = degpol(b);
964 if (lb && lb < la)
965 {
966 b = FlxqX_normalize(b, T,p);
967 t[L] = FlxqX_div(a,b,T,p);
968 t[i]= b; L++;
969 }
970 else set_avma(av);
971 }
972 }
973 }
974 return d;
975 }
976
977 static long
FpXQX_split_Berlekamp(GEN * t,GEN T,GEN p)978 FpXQX_split_Berlekamp(GEN *t, GEN T, GEN p)
979 {
980 GEN u = *t, a, b, vker, pol;
981 GEN X, xp, Xp, Xq, S;
982 long vu = varn(u), vT = get_FpX_var(T), dT = get_FpX_degree(T);
983 long d, i, ir, L, la, lb;
984 if (degpol(u)==1) return 1;
985 T = FpX_get_red(T, p);
986 xp = FpX_Frobenius(T, p);
987 S = FpXQX_get_red(u, T, p);
988 X = pol_x(get_FpXQX_var(S));
989 Xp = FpXQXQ_pow(X, p, S, T, p);
990 Xq = FpXQXQ_Frobenius(xp, Xp, S, T, p);
991 vker = FpXQX_Berlekamp_ker_i(Xq, S, T, p);
992 vker = RgM_to_RgXV(vker,vu);
993 d = lg(vker)-1;
994 ir = 0;
995 /* t[i] irreducible for i < ir, still to be treated for i < L */
996 for (L=1; L<d; )
997 {
998 pol= scalarpol(random_FpX(dT,vT,p),vu);
999 for (i=2; i<=d; i++)
1000 pol = FqX_add(pol, FqX_Fq_mul(gel(vker,i),
1001 random_FpX(dT,vT,p), T, p), T, p);
1002 pol = FpXQX_red(pol,T,p);
1003 for (i=ir; i<L && L<d; i++)
1004 {
1005 a = t[i]; la = degpol(a);
1006 if (la == 1) { set_irred(i); }
1007 else
1008 {
1009 pari_sp av = avma;
1010 GEN S = FpXQX_get_red(a, T, p);
1011 b = FqX_rem(pol, S, T,p);
1012 if (degpol(b)<=0) { set_avma(av); continue; }
1013 b = FpXQXQ_halfFrobenius_i(b, xp, FpXQX_rem(Xp, S, T, p), S, T, p);
1014 if (degpol(b)<=0) { set_avma(av); continue; }
1015 gel(b,2) = Fq_sub(gel(b,2), gen_1,T,p);
1016 b = FqX_gcd(a,b, T,p); lb = degpol(b);
1017 if (lb && lb < la)
1018 {
1019 b = FpXQX_normalize(b, T,p);
1020 t[L] = FqX_div(a,b,T,p);
1021 t[i]= b; L++;
1022 }
1023 else set_avma(av);
1024 }
1025 }
1026 }
1027 return d;
1028 }
1029
1030 static GEN
F2xqX_quad_roots(GEN P,GEN T)1031 F2xqX_quad_roots(GEN P, GEN T)
1032 {
1033 GEN b= gel(P,3), c = gel(P,2);
1034 if (lgpol(b))
1035 {
1036 GEN z, d = F2xq_div(c, F2xq_sqr(b,T),T);
1037 if (F2xq_trace(d,T))
1038 return cgetg(1, t_COL);
1039 z = F2xq_mul(b, F2xq_Artin_Schreier(d, T), T);
1040 return mkcol2(z, F2x_add(b, z));
1041 }
1042 else
1043 return mkcol(F2xq_sqrt(c, T));
1044 }
1045
1046 /* Assume p>2 and x monic */
1047 static GEN
FlxqX_quad_roots(GEN x,GEN T,ulong p)1048 FlxqX_quad_roots(GEN x, GEN T, ulong p)
1049 {
1050 GEN s, D, nb, b = gel(x,3), c = gel(x,2);
1051 D = Flx_sub(Flxq_sqr(b,T,p), Flx_mulu(c,4,p), p);
1052 nb = Flx_neg(b,p);
1053 if (lgpol(D)==0)
1054 return mkcol(Flx_halve(nb, p));
1055 s = Flxq_sqrt(D,T,p);
1056 if (!s) return cgetg(1, t_COL);
1057 s = Flx_halve(Flx_add(s,nb,p),p);
1058 return mkcol2(s, Flx_sub(nb,s,p));
1059 }
1060
1061 static GEN
FpXQX_quad_roots(GEN x,GEN T,GEN p)1062 FpXQX_quad_roots(GEN x, GEN T, GEN p)
1063 {
1064 GEN s, D, nb, b = gel(x,3), c = gel(x,2);
1065 if (absequaliu(p, 2))
1066 {
1067 GEN f2 = ZXX_to_F2xX(x, get_FpX_var(T));
1068 s = F2xqX_quad_roots(f2, ZX_to_F2x(get_FpX_mod(T)));
1069 return F2xC_to_ZXC(s);
1070 }
1071 D = Fq_sub(Fq_sqr(b,T,p), Fq_Fp_mul(c,utoi(4),T,p), T,p);
1072 nb = Fq_neg(b,T,p);
1073 if (signe(D)==0)
1074 return mkcol(Fq_to_FpXQ(Fq_halve(nb,T, p),T,p));
1075 s = Fq_sqrt(D,T,p);
1076 if (!s) return cgetg(1, t_COL);
1077 s = Fq_halve(Fq_add(s,nb,T,p),T, p);
1078 return mkcol2(Fq_to_FpXQ(s,T,p), Fq_to_FpXQ(Fq_sub(nb,s,T,p),T,p));
1079 }
1080
1081 static GEN
F2xqX_Frobenius_deflate(GEN S,GEN T)1082 F2xqX_Frobenius_deflate(GEN S, GEN T)
1083 {
1084 GEN F = RgX_deflate(S, 2);
1085 long i, l = lg(F);
1086 for (i=2; i<l; i++)
1087 gel(F,i) = F2xq_sqrt(gel(F,i), T);
1088 return F;
1089 }
1090
1091 static GEN
F2xX_to_F2x(GEN x)1092 F2xX_to_F2x(GEN x)
1093 {
1094 long l=nbits2lg(lgpol(x));
1095 GEN z=cgetg(l,t_VECSMALL);
1096 long i,j,k;
1097 z[1]=x[1];
1098 for(i=2, k=1,j=BITS_IN_LONG;i<lg(x);i++,j++)
1099 {
1100 if (j==BITS_IN_LONG)
1101 {
1102 j=0; k++; z[k]=0;
1103 }
1104 if (lgpol(gel(x,i)))
1105 z[k]|=1UL<<j;
1106 }
1107 return F2x_renormalize(z,l);
1108 }
1109
1110 static GEN
F2xqX_easyroots(GEN f,GEN T)1111 F2xqX_easyroots(GEN f, GEN T)
1112 {
1113 if (F2xY_degreex(f) <= 0) return F2x_rootsff_i(F2xX_to_F2x(f), T);
1114 if (degpol(f)==1) return mkcol(constant_coeff(f));
1115 if (degpol(f)==2) return F2xqX_quad_roots(f,T);
1116 return NULL;
1117 }
1118
1119 /* Adapted from Shoup NTL */
1120 GEN
F2xqX_factor_squarefree(GEN f,GEN T)1121 F2xqX_factor_squarefree(GEN f, GEN T)
1122 {
1123 pari_sp av = avma;
1124 GEN r, t, v, tv;
1125 long i, q, n = degpol(f);
1126 GEN u = const_vec(n+1, pol1_F2xX(varn(f), get_F2x_var(T)));
1127 for(q = 1;;q *= 2)
1128 {
1129 r = F2xqX_gcd(f, F2xX_deriv(f), T);
1130 if (degpol(r) == 0)
1131 {
1132 gel(u, q) = F2xqX_normalize(f, T);
1133 break;
1134 }
1135 t = F2xqX_div(f, r, T);
1136 if (degpol(t) > 0)
1137 {
1138 long j;
1139 for(j = 1;;j++)
1140 {
1141 v = F2xqX_gcd(r, t, T);
1142 tv = F2xqX_div(t, v, T);
1143 if (degpol(tv) > 0)
1144 gel(u, j*q) = F2xqX_normalize(tv, T);
1145 if (degpol(v) <= 0) break;
1146 r = F2xqX_div(r, v, T);
1147 t = v;
1148 }
1149 if (degpol(r) == 0) break;
1150 }
1151 f = F2xqX_Frobenius_deflate(r, T);
1152 }
1153 for (i = n; i; i--)
1154 if (degpol(gel(u,i))) break;
1155 setlg(u,i+1); return gerepilecopy(av, u);
1156 }
1157
1158 long
F2xqX_ispower(GEN f,long k,GEN T,GEN * pt_r)1159 F2xqX_ispower(GEN f, long k, GEN T, GEN *pt_r)
1160 {
1161 pari_sp av = avma;
1162 GEN lc, F;
1163 long i, l, n = degpol(f);
1164 if (n % k) return 0;
1165 lc = F2xq_sqrtn(leading_coeff(f), stoi(k), T, NULL);
1166 if (!lc) return gc_long(av,0);
1167 F = F2xqX_factor_squarefree(f, T); l = lg(F)-1;
1168 for(i=1; i<=l; i++)
1169 if (i%k && degpol(gel(F,i))) return gc_long(av,0);
1170 if (pt_r)
1171 {
1172 long v = varn(f);
1173 GEN r = scalarpol(lc, v), s = pol1_F2xX(v, T[1]);
1174 for(i=l; i>=1; i--)
1175 {
1176 if (i%k) continue;
1177 s = F2xqX_mul(s, gel(F,i), T);
1178 r = F2xqX_mul(r, s, T);
1179 }
1180 *pt_r = gerepileupto(av, r);
1181 } else set_avma(av);
1182 return 1;
1183 }
1184
1185 static void
F2xqX_roots_edf(GEN Sp,GEN xp,GEN Xp,GEN T,GEN V,long idx)1186 F2xqX_roots_edf(GEN Sp, GEN xp, GEN Xp, GEN T, GEN V, long idx)
1187 {
1188 pari_sp btop;
1189 long n = degpol(Sp);
1190 GEN S, f, ff;
1191 long dT = get_F2x_degree(T);
1192 GEN R = F2xqX_easyroots(Sp, T);
1193 if (R)
1194 {
1195 long i, l = lg(R)-1;
1196 for (i=0; i<l; i++)
1197 gel(V, idx+i) = gel(R,1+i);
1198 return;
1199 }
1200 S = F2xqX_get_red(Sp, T);
1201 Xp = F2xqX_rem(Xp, S, T);
1202 btop = avma;
1203 while (1)
1204 {
1205 GEN a = random_F2xqX(degpol(Sp), varn(Sp), T);
1206 GEN R = gel(F2xqXQ_auttrace(mkvec3(xp, Xp, a), dT, S, T), 3);
1207 f = F2xqX_gcd(R, Sp, T);
1208 if (degpol(f) > 0 && degpol(f) < n) break;
1209 set_avma(btop);
1210 }
1211 f = gerepileupto(btop, F2xqX_normalize(f, T));
1212 ff = F2xqX_div(Sp, f, T);
1213 F2xqX_roots_edf(f, xp, Xp, T, V, idx);
1214 F2xqX_roots_edf(ff,xp, Xp, T, V, idx+degpol(f));
1215 }
1216
1217 static GEN
F2xqX_roots_ddf(GEN f,GEN xp,GEN T)1218 F2xqX_roots_ddf(GEN f, GEN xp, GEN T)
1219 {
1220 GEN X, Xp, Xq, g, V;
1221 long n;
1222 GEN R = F2xqX_easyroots(f, T);
1223 if (R) return R;
1224 X = pol_x(varn(f));
1225 Xp = F2xqXQ_sqr(X, f, T);
1226 Xq = F2xqXQ_Frobenius(xp, Xp, f, T);
1227 g = F2xqX_gcd(F2xX_add(Xq, X), f, T);
1228 n = degpol(g);
1229 if (n==0) return cgetg(1, t_COL);
1230 g = F2xqX_normalize(g, T);
1231 V = cgetg(n+1,t_COL);
1232 F2xqX_roots_edf(g, xp, Xp, T, V, 1);
1233 return V;
1234 }
1235 static GEN
F2xqX_roots_i(GEN S,GEN T)1236 F2xqX_roots_i(GEN S, GEN T)
1237 {
1238 GEN M;
1239 S = F2xqX_red(S, T);
1240 if (!signe(S)) pari_err_ROOTS0("F2xqX_roots");
1241 if (degpol(S)==0) return cgetg(1, t_COL);
1242 S = F2xqX_normalize(S, T);
1243 M = F2xqX_easyroots(S, T);
1244 if (!M)
1245 {
1246 GEN xp = F2x_Frobenius(T);
1247 GEN F, V = F2xqX_factor_squarefree(S, T);
1248 long i, j, l = lg(V);
1249 F = cgetg(l, t_VEC);
1250 for (i=1, j=1; i < l; i++)
1251 if (degpol(gel(V,i)))
1252 gel(F, j++) = F2xqX_roots_ddf(gel(V,i), xp, T);
1253 setlg(F,j); M = shallowconcat1(F);
1254 }
1255 gen_sort_inplace(M, (void*) &cmp_Flx, &cmp_nodata, NULL);
1256 return M;
1257 }
1258
1259 static GEN
FlxqX_easyroots(GEN f,GEN T,ulong p)1260 FlxqX_easyroots(GEN f, GEN T, ulong p)
1261 {
1262 if (FlxY_degreex(f) <= 0) return Flx_rootsff_i(FlxX_to_Flx(f), T, p);
1263 if (degpol(f)==1) return mkcol(Flx_neg(constant_coeff(f), p));
1264 if (degpol(f)==2) return FlxqX_quad_roots(f,T,p);
1265 return NULL;
1266 }
1267
1268 static GEN
FlxqX_invFrobenius(GEN xp,GEN T,ulong p)1269 FlxqX_invFrobenius(GEN xp, GEN T, ulong p)
1270 {
1271 return Flxq_autpow(xp, get_Flx_degree(T)-1, T, p);
1272 }
1273
1274 static GEN
FlxqX_Frobenius_deflate(GEN S,GEN ixp,GEN T,ulong p)1275 FlxqX_Frobenius_deflate(GEN S, GEN ixp, GEN T, ulong p)
1276 {
1277 GEN F = RgX_deflate(S, p);
1278 long i, l = lg(F);
1279 if (typ(ixp)==t_INT)
1280 for (i=2; i<l; i++)
1281 gel(F,i) = Flxq_pow(gel(F,i), ixp, T, p);
1282 else
1283 {
1284 long n = brent_kung_optpow(get_Flx_degree(T)-1, l-2, 1);
1285 GEN V = Flxq_powers(ixp, n, T, p);
1286 for (i=2; i<l; i++)
1287 gel(F,i) = Flx_FlxqV_eval(gel(F,i), V, T, p);
1288 }
1289 return F;
1290 }
1291
1292 /* Adapted from Shoup NTL */
1293 static GEN
FlxqX_factor_squarefree_i(GEN f,GEN xp,GEN T,ulong p)1294 FlxqX_factor_squarefree_i(GEN f, GEN xp, GEN T, ulong p)
1295 {
1296 pari_sp av = avma;
1297 GEN r, t, v, tv;
1298 long i, q, n = degpol(f);
1299 GEN u = const_vec(n+1, pol1_FlxX(varn(f),get_Flx_var(T)));
1300 GEN ixp = NULL;
1301 for(q = 1;;q *= p)
1302 {
1303 r = FlxqX_gcd(f, FlxX_deriv(f, p), T, p);
1304 if (degpol(r) == 0)
1305 {
1306 gel(u, q) = FlxqX_normalize(f, T, p);
1307 break;
1308 }
1309 t = FlxqX_div(f, r, T, p);
1310 if (degpol(t) > 0)
1311 {
1312 long j;
1313 for(j = 1;;j++)
1314 {
1315 v = FlxqX_gcd(r, t, T, p);
1316 tv = FlxqX_div(t, v, T, p);
1317 if (degpol(tv) > 0)
1318 gel(u, j*q) = FlxqX_normalize(tv, T, p);
1319 if (degpol(v) <= 0) break;
1320 r = FlxqX_div(r, v, T, p);
1321 t = v;
1322 }
1323 if (degpol(r) == 0) break;
1324 }
1325 if (!xp) xp = Flx_Frobenius(T, p);
1326 if (!ixp) ixp = FlxqX_invFrobenius(xp, T, p);
1327 f = FlxqX_Frobenius_deflate(r, ixp, T, p);
1328 }
1329 for (i = n; i; i--)
1330 if (degpol(gel(u,i))) break;
1331 setlg(u,i+1); return gerepilecopy(av, u);
1332 }
1333
1334 GEN
FlxqX_factor_squarefree(GEN f,GEN T,ulong p)1335 FlxqX_factor_squarefree(GEN f, GEN T, ulong p)
1336 {
1337 return FlxqX_factor_squarefree_i(f, NULL, T, p);
1338 }
1339
1340 long
FlxqX_ispower(GEN f,ulong k,GEN T,ulong p,GEN * pt_r)1341 FlxqX_ispower(GEN f, ulong k, GEN T, ulong p, GEN *pt_r)
1342 {
1343 pari_sp av = avma;
1344 GEN lc, F;
1345 long i, l, n = degpol(f), v = varn(f);
1346 if (n % k) return 0;
1347 lc = Flxq_sqrtn(leading_coeff(f), stoi(k), T, p, NULL);
1348 if (!lc) return gc_long(av,0);
1349 F = FlxqX_factor_squarefree_i(f, NULL, T, p); l = lg(F)-1;
1350 for(i=1; i<=l; i++)
1351 if (i%k && degpol(gel(F,i))) return gc_long(av,0);
1352 if (pt_r)
1353 {
1354 GEN r = scalarpol(lc, v), s = pol1_FlxX(v, T[1]);
1355 for(i=l; i>=1; i--)
1356 {
1357 if (i%k) continue;
1358 s = FlxqX_mul(s, gel(F,i), T, p);
1359 r = FlxqX_mul(r, s, T, p);
1360 }
1361 *pt_r = gerepileupto(av, r);
1362 } else set_avma(av);
1363 return 1;
1364 }
1365
1366 static GEN
FlxqX_roots_split(GEN Sp,GEN xp,GEN Xp,GEN S,GEN T,ulong p)1367 FlxqX_roots_split(GEN Sp, GEN xp, GEN Xp, GEN S, GEN T, ulong p)
1368 {
1369 pari_sp btop = avma;
1370 long n = degpol(Sp);
1371 GEN f;
1372 long vT = get_Flx_var(T), dT = get_Flx_degree(T);
1373 pari_timer ti;
1374 if (DEBUGLEVEL >= 7) timer_start(&ti);
1375 while (1)
1376 {
1377 GEN a = deg1pol(pol1_Flx(vT), random_Flx(dT, vT, p), varn(Sp));
1378 GEN R = FlxqXQ_halfFrobenius_i(a, xp, Xp, S, T, p);
1379 if (DEBUGLEVEL >= 7) timer_printf(&ti, "FlxqXQ_halfFrobenius");
1380 f = FlxqX_gcd(FlxX_Flx_sub(R, pol1_Flx(vT), p), Sp, T, p);
1381 if (degpol(f) > 0 && degpol(f) < n) break;
1382 set_avma(btop);
1383 }
1384 return gerepileupto(btop, FlxqX_normalize(f, T, p));
1385 }
1386
1387 static void
FlxqX_roots_edf(GEN Sp,GEN xp,GEN Xp,GEN T,ulong p,GEN V,long idx)1388 FlxqX_roots_edf(GEN Sp, GEN xp, GEN Xp, GEN T, ulong p, GEN V, long idx)
1389 {
1390 GEN S, f, ff;
1391 GEN R = FlxqX_easyroots(Sp, T, p);
1392 if (R)
1393 {
1394 long i, l = lg(R)-1;
1395 for (i=0; i<l; i++)
1396 gel(V, idx+i) = gel(R,1+i);
1397 return;
1398 }
1399 S = FlxqX_get_red(Sp, T, p);
1400 Xp = FlxqX_rem(Xp, S, T, p);
1401 f = FlxqX_roots_split(Sp, xp, Xp, S, T, p);
1402 ff = FlxqX_div(Sp, f, T, p);
1403 FlxqX_roots_edf(f, xp, Xp, T, p, V, idx);
1404 FlxqX_roots_edf(ff,xp, Xp, T, p, V, idx+degpol(f));
1405 }
1406
1407 static GEN
FlxqX_roots_ddf(GEN f,GEN xp,GEN T,ulong p)1408 FlxqX_roots_ddf(GEN f, GEN xp, GEN T, ulong p)
1409 {
1410 GEN X, Xp, Xq, g, V;
1411 long n;
1412 GEN R = FlxqX_easyroots(f, T, p);
1413 if (R) return R;
1414 X = pol_x(varn(f));
1415 Xp = FlxqXQ_powu(X, p, f, T, p);
1416 Xq = FlxqXQ_Frobenius(xp, Xp, f, T, p);
1417 g = FlxqX_gcd(FlxX_sub(Xq, X, p), f, T, p);
1418 n = degpol(g);
1419 if (n==0) return cgetg(1, t_COL);
1420 g = FlxqX_normalize(g, T, p);
1421 V = cgetg(n+1,t_COL);
1422 FlxqX_roots_edf(g, xp, Xp, T, p, V, 1);
1423 return V;
1424 }
1425
1426 /* do not handle p==2 */
1427 static GEN
FlxqX_roots_i(GEN S,GEN T,ulong p)1428 FlxqX_roots_i(GEN S, GEN T, ulong p)
1429 {
1430 GEN M;
1431 S = FlxqX_red(S, T, p);
1432 if (!signe(S)) pari_err_ROOTS0("FlxqX_roots");
1433 if (degpol(S)==0) return cgetg(1, t_COL);
1434 S = FlxqX_normalize(S, T, p);
1435 M = FlxqX_easyroots(S, T, p);
1436 if (!M)
1437 {
1438 GEN xp = Flx_Frobenius(T, p);
1439 GEN F, V = FlxqX_factor_squarefree_i(S, xp, T, p);
1440 long i, j, l = lg(V);
1441 F = cgetg(l, t_VEC);
1442 for (i=1, j=1; i < l; i++)
1443 if (degpol(gel(V,i)))
1444 gel(F, j++) = FlxqX_roots_ddf(gel(V,i), xp, T, p);
1445 setlg(F,j); M = shallowconcat1(F);
1446 }
1447 gen_sort_inplace(M, (void*) &cmp_Flx, &cmp_nodata, NULL);
1448 return M;
1449 }
1450
1451 static GEN
FpXQX_easyroots(GEN f,GEN T,GEN p)1452 FpXQX_easyroots(GEN f, GEN T, GEN p)
1453 {
1454 if (isabsolutepol(f)) return FpX_rootsff_i(simplify_shallow(f), T, p);
1455 if (degpol(f)==1) return mkcol(Fq_to_FpXQ(Fq_neg(constant_coeff(f),T,p),T,p));
1456 if (degpol(f)==2) return FpXQX_quad_roots(f,T,p);
1457 return NULL;
1458 }
1459
1460 /* Adapted from Shoup NTL */
1461 static GEN
FpXQX_factor_Yun(GEN f,GEN T,GEN p)1462 FpXQX_factor_Yun(GEN f, GEN T, GEN p)
1463 {
1464 pari_sp av = avma;
1465 GEN r, t, v, tv;
1466 long j, n = degpol(f);
1467 GEN u = const_vec(n+1, pol_1(varn(f)));
1468 r = FpXQX_gcd(f, FpXX_deriv(f, p), T, p);
1469 t = FpXQX_div(f, r, T, p);
1470 for (j = 1;;j++)
1471 {
1472 v = FpXQX_gcd(r, t, T, p);
1473 tv = FpXQX_div(t, v, T, p);
1474 if (degpol(tv) > 0)
1475 gel(u, j) = FpXQX_normalize(tv, T, p);
1476 if (degpol(v) <= 0) break;
1477 r = FpXQX_div(r, v, T, p);
1478 t = v;
1479 }
1480 setlg(u, j+1); return gerepilecopy(av, u);
1481 }
1482
1483 GEN
FpXQX_factor_squarefree(GEN f,GEN T,GEN p)1484 FpXQX_factor_squarefree(GEN f, GEN T, GEN p)
1485 {
1486 if (lgefint(p)==3)
1487 {
1488 pari_sp av = avma;
1489 ulong pp = p[2];
1490 GEN M;
1491 long vT = get_FpX_var(T);
1492 if (pp==2)
1493 {
1494 M = F2xqX_factor_squarefree(ZXX_to_F2xX(f, vT), ZX_to_F2x(get_FpX_mod(T)));
1495 return gerepileupto(av, F2xXC_to_ZXXC(M));
1496 }
1497 M = FlxqX_factor_squarefree(ZXX_to_FlxX(f, pp, vT), ZXT_to_FlxT(T, pp), pp);
1498 return gerepileupto(av, FlxXC_to_ZXXC(M));
1499 }
1500 return FpXQX_factor_Yun(f, T, p);
1501 }
1502
1503 long
FpXQX_ispower(GEN f,ulong k,GEN T,GEN p,GEN * pt_r)1504 FpXQX_ispower(GEN f, ulong k, GEN T, GEN p, GEN *pt_r)
1505 {
1506 pari_sp av = avma;
1507 GEN lc, F;
1508 long i, l, n = degpol(f), v = varn(f);
1509 if (n % k) return 0;
1510 if (lgefint(p)==3)
1511 {
1512 ulong pp = p[2];
1513 GEN fp = ZXX_to_FlxX(f, pp, varn(T));
1514 if (!FlxqX_ispower(fp, k, ZX_to_Flx(T,pp), pp, pt_r)) return gc_long(av,0);
1515 if (pt_r) *pt_r = gerepileupto(av, FlxX_to_ZXX(*pt_r));
1516 else set_avma(av);
1517 return 1;
1518 }
1519 lc = FpXQ_sqrtn(leading_coeff(f), stoi(k), T, p, NULL);
1520 if (!lc) return gc_long(av,0);
1521 F = FpXQX_factor_Yun(f, T, p); l = lg(F)-1;
1522 for(i=1; i <= l; i++)
1523 if (i%k && degpol(gel(F,i))) return gc_long(av,0);
1524 if (pt_r)
1525 {
1526 GEN r = scalarpol(lc, v), s = pol_1(v);
1527 for(i=l; i>=1; i--)
1528 {
1529 if (i%k) continue;
1530 s = FpXQX_mul(s, gel(F,i), T, p);
1531 r = FpXQX_mul(r, s, T, p);
1532 }
1533 *pt_r = gerepileupto(av, r);
1534 } else set_avma(av);
1535 return 1;
1536 }
1537
1538 long
FqX_ispower(GEN f,ulong k,GEN T,GEN p,GEN * pt_r)1539 FqX_ispower(GEN f, ulong k, GEN T, GEN p, GEN *pt_r)
1540 { return T ? FpXQX_ispower(f, k, T, p, pt_r): FpX_ispower(f, k, p, pt_r); }
1541
1542 static GEN
FpXQX_roots_split(GEN Sp,GEN xp,GEN Xp,GEN S,GEN T,GEN p)1543 FpXQX_roots_split(GEN Sp, GEN xp, GEN Xp, GEN S, GEN T, GEN p)
1544 {
1545 pari_sp btop = avma;
1546 long n = degpol(Sp);
1547 GEN f;
1548 long vT = get_FpX_var(T), dT = get_FpX_degree(T);
1549 pari_timer ti;
1550 if (DEBUGLEVEL >= 7) timer_start(&ti);
1551 while (1)
1552 {
1553 GEN a = deg1pol(pol_1(vT), random_FpX(dT, vT, p), varn(Sp));
1554 GEN R = FpXQXQ_halfFrobenius_i(a, xp, Xp, S, T, p);
1555 if (DEBUGLEVEL >= 7) timer_printf(&ti, "FpXQXQ_halfFrobenius");
1556 f = FpXQX_gcd(FqX_Fq_sub(R, pol_1(vT), T, p), Sp, T, p);
1557 if (degpol(f) > 0 && degpol(f) < n) break;
1558 set_avma(btop);
1559 }
1560 return gerepileupto(btop, FpXQX_normalize(f, T, p));
1561 }
1562
1563 static void
FpXQX_roots_edf(GEN Sp,GEN xp,GEN Xp,GEN T,GEN p,GEN V,long idx)1564 FpXQX_roots_edf(GEN Sp, GEN xp, GEN Xp, GEN T, GEN p, GEN V, long idx)
1565 {
1566 GEN S, f, ff;
1567 GEN R = FpXQX_easyroots(Sp, T, p);
1568 if (R)
1569 {
1570 long i, l = lg(R)-1;
1571 for (i=0; i<l; i++)
1572 gel(V, idx+i) = gel(R,1+i);
1573 return;
1574 }
1575 S = FpXQX_get_red(Sp, T, p);
1576 Xp = FpXQX_rem(Xp, S, T, p);
1577 f = FpXQX_roots_split(Sp, xp, Xp, S, T, p);
1578 ff = FpXQX_div(Sp, f, T, p);
1579 FpXQX_roots_edf(f, xp, Xp, T, p, V, idx);
1580 FpXQX_roots_edf(ff,xp, Xp, T, p, V, idx+degpol(f));
1581 }
1582
1583 static GEN
FpXQX_roots_ddf(GEN f,GEN xp,GEN T,GEN p)1584 FpXQX_roots_ddf(GEN f, GEN xp, GEN T, GEN p)
1585 {
1586 GEN X, Xp, Xq, g, V;
1587 long n;
1588 GEN R = FpXQX_easyroots(f, T, p);
1589 if (R) return R;
1590 X = pol_x(varn(f));
1591 Xp = FpXQXQ_pow(X, p, f, T, p);
1592 Xq = FpXQXQ_Frobenius(xp, Xp, f, T, p);
1593 g = FpXQX_gcd(FpXX_sub(Xq, X, p), f, T, p);
1594 n = degpol(g);
1595 if (n==0) return cgetg(1, t_COL);
1596 g = FpXQX_normalize(g, T, p);
1597 V = cgetg(n+1,t_COL);
1598 FpXQX_roots_edf(g, xp, Xp, T, p, V, 1);
1599 return V;
1600 }
1601
1602 /* do not handle small p */
1603 static GEN
FpXQX_roots_i(GEN S,GEN T,GEN p)1604 FpXQX_roots_i(GEN S, GEN T, GEN p)
1605 {
1606 GEN F, M;
1607 if (lgefint(p)==3)
1608 {
1609 ulong pp = p[2];
1610 if (pp == 2)
1611 {
1612 GEN V = F2xqX_roots_i(ZXX_to_F2xX(S,get_FpX_var(T)), ZX_to_F2x(get_FpX_mod(T)));
1613 return F2xC_to_ZXC(V);
1614 }
1615 else
1616 {
1617 GEN V = FlxqX_roots_i(ZXX_to_FlxX(S,pp,get_FpX_var(T)), ZXT_to_FlxT(T,pp), pp);
1618 return FlxC_to_ZXC(V);
1619 }
1620 }
1621 S = FpXQX_red(S, T, p);
1622 if (!signe(S)) pari_err_ROOTS0("FpXQX_roots");
1623 if (degpol(S)==0) return cgetg(1, t_COL);
1624 S = FpXQX_normalize(S, T, p);
1625 M = FpXQX_easyroots(S, T, p);
1626 if (!M)
1627 {
1628 GEN xp = FpX_Frobenius(T, p);
1629 GEN V = FpXQX_factor_Yun(S, T, p);
1630 long i, j, l = lg(V);
1631 F = cgetg(l, t_VEC);
1632 for (i=1, j=1; i < l; i++)
1633 if (degpol(gel(V,i)))
1634 gel(F, j++) = FpXQX_roots_ddf(gel(V,i), xp, T, p);
1635 setlg(F,j); M = shallowconcat1(F);
1636 }
1637 gen_sort_inplace(M, (void*) &cmp_RgX, &cmp_nodata, NULL);
1638 return M;
1639 }
1640
1641 GEN
F2xqX_roots(GEN x,GEN T)1642 F2xqX_roots(GEN x, GEN T)
1643 {
1644 pari_sp av = avma;
1645 return gerepilecopy(av, F2xqX_roots_i(x, T));
1646 }
1647
1648 GEN
FlxqX_roots(GEN x,GEN T,ulong p)1649 FlxqX_roots(GEN x, GEN T, ulong p)
1650 {
1651 pari_sp av = avma;
1652 if (p==2)
1653 {
1654 GEN V = F2xqX_roots_i(FlxX_to_F2xX(x), Flx_to_F2x(get_Flx_mod(T)));
1655 return gerepileupto(av, F2xC_to_FlxC(V));
1656 }
1657 return gerepilecopy(av, FlxqX_roots_i(x, T, p));
1658 }
1659
1660 GEN
FpXQX_roots(GEN x,GEN T,GEN p)1661 FpXQX_roots(GEN x, GEN T, GEN p)
1662 {
1663 pari_sp av = avma;
1664 return gerepilecopy(av, FpXQX_roots_i(x, T, p));
1665 }
1666
1667 static GEN
FE_concat(GEN F,GEN E,long l)1668 FE_concat(GEN F, GEN E, long l)
1669 {
1670 setlg(E,l); E = shallowconcat1(E);
1671 setlg(F,l); F = shallowconcat1(F); return mkvec2(F,E);
1672 }
1673
1674 static GEN
F2xqX_factor_2(GEN f,GEN T)1675 F2xqX_factor_2(GEN f, GEN T)
1676 {
1677 long v = varn(f), vT = get_F2x_var(T);
1678 GEN r = F2xqX_quad_roots(f, T);
1679 switch(lg(r)-1)
1680 {
1681 case 0:
1682 return mkvec2(mkcolcopy(f), mkvecsmall(1));
1683 case 1:
1684 return mkvec2(mkcol(deg1pol_shallow(pol1_F2x(vT), gel(r,1), v)), mkvecsmall(2));
1685 default: /* 2 */
1686 {
1687 GEN f1 = deg1pol_shallow(pol1_F2x(vT), gel(r,1), v);
1688 GEN f2 = deg1pol_shallow(pol1_F2x(vT), gel(r,2), v);
1689 GEN t = mkcol2(f1, f2), E = mkvecsmall2(1, 1);
1690 sort_factor_pol(mkvec2(t, E), cmp_Flx);
1691 return mkvec2(t, E);
1692 }
1693 }
1694 }
1695
1696 static GEN
FlxqX_factor_2(GEN f,GEN T,ulong p)1697 FlxqX_factor_2(GEN f, GEN T, ulong p)
1698 {
1699 long v = varn(f), vT = get_Flx_var(T);
1700 GEN r = FlxqX_quad_roots(f, T, p);
1701 switch(lg(r)-1)
1702 {
1703 case 0:
1704 return mkvec2(mkcolcopy(f), mkvecsmall(1));
1705 case 1:
1706 return mkvec2(mkcol(deg1pol_shallow(pol1_Flx(vT),
1707 Flx_neg(gel(r,1), p), v)), mkvecsmall(2));
1708 default: /* 2 */
1709 {
1710 GEN f1 = deg1pol_shallow(pol1_Flx(vT), Flx_neg(gel(r,1), p), v);
1711 GEN f2 = deg1pol_shallow(pol1_Flx(vT), Flx_neg(gel(r,2), p), v);
1712 GEN t = mkcol2(f1, f2), E = mkvecsmall2(1, 1);
1713 sort_factor_pol(mkvec2(t, E), cmp_Flx);
1714 return mkvec2(t, E);
1715 }
1716 }
1717 }
1718
1719 static GEN
FpXQX_factor_2(GEN f,GEN T,GEN p)1720 FpXQX_factor_2(GEN f, GEN T, GEN p)
1721 {
1722 long v = varn(f);
1723 GEN r = FpXQX_quad_roots(f, T, p);
1724 switch(lg(r)-1)
1725 {
1726 case 0:
1727 return mkvec2(mkcolcopy(f), mkvecsmall(1));
1728 case 1:
1729 return mkvec2(mkcol(deg1pol_shallow(gen_1, Fq_neg(gel(r,1), T, p), v)),
1730 mkvecsmall(2));
1731 default: /* 2 */
1732 {
1733 GEN f1 = deg1pol_shallow(gen_1, Fq_neg(gel(r,1), T, p), v);
1734 GEN f2 = deg1pol_shallow(gen_1, Fq_neg(gel(r,2), T, p), v);
1735 GEN t = mkcol2(f1, f2), E = mkvecsmall2(1, 1);
1736 sort_factor_pol(mkvec2(t, E), cmp_RgX);
1737 return mkvec2(t, E);
1738 }
1739 }
1740 }
1741
1742 static GEN
F2xqX_ddf_Shoup(GEN S,GEN Xq,GEN T)1743 F2xqX_ddf_Shoup(GEN S, GEN Xq, GEN T)
1744 {
1745 pari_sp av = avma;
1746 GEN b, g, h, F, f, Sr, xq;
1747 long i, j, n, v, vT, dT, bo, ro;
1748 long B, l, m;
1749 pari_timer ti;
1750 n = get_F2xqX_degree(S); v = get_F2xqX_var(S);
1751 vT = get_F2x_var(T); dT = get_F2x_degree(T);
1752 if (n == 0) return cgetg(1, t_VEC);
1753 if (n == 1) return mkvec(get_F2xqX_mod(S));
1754 B = n/2;
1755 l = usqrt(B);
1756 m = (B+l-1)/l;
1757 S = F2xqX_get_red(S, T);
1758 b = cgetg(l+2, t_VEC);
1759 gel(b, 1) = polx_F2xX(v, vT);
1760 gel(b, 2) = Xq;
1761 bo = brent_kung_optpow(n, l-1, 1);
1762 ro = l<=1 ? 0: (bo-1)/(l-1) + ((n-1)/bo);
1763 if (DEBUGLEVEL>=7) timer_start(&ti);
1764 if (dT <= ro)
1765 for (i = 3; i <= l+1; i++)
1766 gel(b, i) = F2xqXQ_pow(gel(b, i-1), int2n(dT), S, T);
1767 else
1768 {
1769 xq = F2xqXQ_powers(gel(b, 2), bo, S, T);
1770 if (DEBUGLEVEL>=7) timer_printf(&ti,"F2xqX_ddf_Shoup: xq baby");
1771 for (i = 3; i <= l+1; i++)
1772 gel(b, i) = F2xqX_F2xqXQV_eval(gel(b, i-1), xq, S, T);
1773 }
1774 if (DEBUGLEVEL>=7) timer_printf(&ti,"F2xqX_ddf_Shoup: baby");
1775 xq = F2xqXQ_powers(gel(b, l+1), brent_kung_optpow(n, m-1, 1), S, T);
1776 if (DEBUGLEVEL>=7) timer_printf(&ti,"F2xqX_ddf_Shoup: xq giant");
1777 g = cgetg(m+1, t_VEC);
1778 gel(g, 1) = gel(xq, 2);
1779 for(i = 2; i <= m; i++)
1780 gel(g, i) = F2xqX_F2xqXQV_eval(gel(g, i-1), xq, S, T);
1781 if (DEBUGLEVEL>=7) timer_printf(&ti,"F2xqX_ddf_Shoup: giant");
1782 h = cgetg(m+1, t_VEC);
1783 for (j = 1; j <= m; j++)
1784 {
1785 pari_sp av = avma;
1786 GEN gj = gel(g, j);
1787 GEN e = F2xX_add(gj, gel(b, 1));
1788 for (i = 2; i <= l; i++)
1789 e = F2xqXQ_mul(e, F2xX_add(gj, gel(b, i)), S, T);
1790 gel(h, j) = gerepileupto(av, e);
1791 }
1792 if (DEBUGLEVEL>=7) timer_printf(&ti,"F2xqX_ddf_Shoup: diff");
1793 Sr = get_F2xqX_mod(S);
1794 F = cgetg(m+1, t_VEC);
1795 for (j = 1; j <= m; j++)
1796 {
1797 GEN u = F2xqX_gcd(Sr, gel(h,j), T);
1798 if (degpol(u))
1799 {
1800 u = F2xqX_normalize(u, T);
1801 Sr = F2xqX_div(Sr, u, T);
1802 }
1803 gel(F,j) = u;
1804 }
1805 if (DEBUGLEVEL>=7) timer_printf(&ti,"F2xqX_ddf_Shoup: F");
1806 f = const_vec(n, pol1_F2xX(v, vT));
1807 for (j = 1; j <= m; j++)
1808 {
1809 GEN e = gel(F, j);
1810 for (i=l-1; i >= 0; i--)
1811 {
1812 GEN u = F2xqX_gcd(e, F2xX_add(gel(g, j), gel(b, i+1)), T);
1813 if (degpol(u))
1814 {
1815 gel(f, l*j-i) = u = F2xqX_normalize(u, T);
1816 e = F2xqX_div(e, u, T);
1817 }
1818 if (!degpol(e)) break;
1819 }
1820 }
1821 if (DEBUGLEVEL>=7) timer_printf(&ti,"F2xqX_ddf_Shoup: f");
1822 if (degpol(Sr)) gel(f, degpol(Sr)) = Sr;
1823 return gerepilecopy(av, f);
1824 }
1825
1826 static GEN
F2xqX_ddf_i(GEN f,GEN T,GEN X,GEN xp)1827 F2xqX_ddf_i(GEN f, GEN T, GEN X, GEN xp)
1828 {
1829 GEN Xp, Xq;
1830 if (!get_F2xqX_degree(f)) return cgetg(1,t_VEC);
1831 f = F2xqX_get_red(f, T);
1832 Xp = F2xqXQ_sqr(X, f, T);
1833 Xq = F2xqXQ_Frobenius(xp, Xp, f, T);
1834 return F2xqX_ddf_Shoup(f, Xq, T);
1835 }
1836 static void
F2xqX_ddf_init(GEN * S,GEN * T,GEN * xp,GEN * X)1837 F2xqX_ddf_init(GEN *S, GEN *T, GEN *xp, GEN *X)
1838 {
1839 *T = F2x_get_red(*T);
1840 *S = F2xqX_normalize(get_F2xqX_mod(*S), *T);
1841 *xp = F2x_Frobenius(*T);
1842 *X = polx_F2xX(get_F2xqX_var(*S), get_F2x_var(*T));
1843 }
1844 GEN
F2xqX_degfact(GEN S,GEN T)1845 F2xqX_degfact(GEN S, GEN T)
1846 {
1847 GEN xp, X, V;
1848 long i, l;
1849 F2xqX_ddf_init(&S,&T,&xp,&X);
1850 V = F2xqX_factor_squarefree(S, T); l = lg(V);
1851 for (i=1; i < l; i++) gel(V,i) = F2xqX_ddf_i(gel(V,i), T, X, xp);
1852 return vddf_to_simplefact(V, degpol(S));
1853 }
1854 GEN
F2xqX_ddf(GEN S,GEN T)1855 F2xqX_ddf(GEN S, GEN T)
1856 {
1857 GEN xp, X;
1858 F2xqX_ddf_init(&S,&T,&xp,&X);
1859 return ddf_to_ddf2( F2xqX_ddf_i(S, T, X, xp) );
1860 }
1861
1862 static void
F2xqX_edf_simple(GEN Sp,GEN xp,GEN Xp,GEN Sq,long d,GEN T,GEN V,long idx)1863 F2xqX_edf_simple(GEN Sp, GEN xp, GEN Xp, GEN Sq, long d, GEN T, GEN V, long idx)
1864 {
1865 long v = varn(Sp), n = degpol(Sp), r = n/d;
1866 GEN S, f, ff;
1867 long dT = get_F2x_degree(T);
1868 if (r==1) { gel(V, idx) = Sp; return; }
1869 S = F2xqX_get_red(Sp, T);
1870 Xp = F2xqX_rem(Xp, S, T);
1871 Sq = F2xqXQV_red(Sq, S, T);
1872 while (1)
1873 {
1874 pari_sp btop = avma;
1875 long l;
1876 GEN w0 = random_F2xqX(n, v, T), g = w0;
1877 for (l=1; l<d; l++) /* sum_{0<i<d} w^(q^i), result in (F_q)^r */
1878 g = F2xX_add(w0, F2xqX_F2xqXQV_eval(g, Sq, S, T));
1879 w0 = g;
1880 for (l=1; l<dT; l++) /* sum_{0<i<k} w^(2^i), result in (F_2)^r */
1881 g = F2xX_add(w0, F2xqXQ_sqr(g,S,T));
1882 f = F2xqX_gcd(g, Sp, T);
1883 if (degpol(f) > 0 && degpol(f) < n) break;
1884 set_avma(btop);
1885 }
1886 f = F2xqX_normalize(f, T);
1887 ff = F2xqX_div(Sp, f , T);
1888 F2xqX_edf_simple(f, xp, Xp, Sq, d, T, V, idx);
1889 F2xqX_edf_simple(ff, xp, Xp, Sq, d, T, V, idx+degpol(f)/d);
1890 }
1891
1892 static GEN
F2xqX_factor_Shoup(GEN S,GEN xp,GEN T)1893 F2xqX_factor_Shoup(GEN S, GEN xp, GEN T)
1894 {
1895 long i, n, s = 0;
1896 GEN X, Xp, Xq, Sq, D, V;
1897 long vT = get_F2x_var(T);
1898 pari_timer ti;
1899 n = get_F2xqX_degree(S);
1900 S = F2xqX_get_red(S, T);
1901 if (DEBUGLEVEL>=6) timer_start(&ti);
1902 X = polx_F2xX(get_F2xqX_var(S), vT);
1903 Xp = F2xqXQ_sqr(X, S, T);
1904 Xq = F2xqXQ_Frobenius(xp, Xp, S, T);
1905 Sq = F2xqXQ_powers(Xq, n-1, S, T);
1906 if (DEBUGLEVEL>=6) timer_printf(&ti,"F2xqX_Frobenius");
1907 D = F2xqX_ddf_Shoup(S, Xq, T);
1908 if (DEBUGLEVEL>=6) timer_printf(&ti,"F2xqX_ddf_Shoup");
1909 s = ddf_to_nbfact(D);
1910 V = cgetg(s+1, t_COL);
1911 for (i = 1, s = 1; i <= n; i++)
1912 {
1913 GEN Di = gel(D,i);
1914 long ni = degpol(Di), ri = ni/i;
1915 if (ni == 0) continue;
1916 Di = F2xqX_normalize(Di, T);
1917 if (ni == i) { gel(V, s++) = Di; continue; }
1918 F2xqX_edf_simple(Di, xp, Xp, Sq, i, T, V, s);
1919 if (DEBUGLEVEL>=6) timer_printf(&ti,"F2xqX_edf(%ld)",i);
1920 s += ri;
1921 }
1922 return V;
1923 }
1924
1925 static GEN
F2xqX_factor_Cantor(GEN f,GEN T)1926 F2xqX_factor_Cantor(GEN f, GEN T)
1927 {
1928 GEN xp, E, F, V;
1929 long i, j, l;
1930 T = F2x_get_red(T);
1931 f = F2xqX_normalize(f, T);
1932 switch(degpol(f))
1933 {
1934 case -1: retmkmat2(mkcol(f), mkvecsmall(1));
1935 case 0: return trivial_fact();
1936 case 1: retmkmat2(mkcol(f), mkvecsmall(1));
1937 case 2: return F2xqX_factor_2(f, T);
1938 }
1939 if (F2xY_degreex(f) <= 0) return F2x_factorff_i(F2xX_to_F2x(f), T);
1940 xp = F2x_Frobenius(T);
1941 V = F2xqX_factor_squarefree(f, T);
1942 l = lg(V);
1943 F = cgetg(l, t_VEC);
1944 E = cgetg(l, t_VEC);
1945 for (i=1, j=1; i < l; i++)
1946 if (degpol(gel(V,i)))
1947 {
1948 GEN Fj = F2xqX_factor_Shoup(gel(V,i), xp, T);
1949 gel(F, j) = Fj;
1950 gel(E, j) = const_vecsmall(lg(Fj)-1, i);
1951 j++;
1952 }
1953 return sort_factor_pol(FE_concat(F,E,j), cmp_Flx);
1954 }
1955
1956 static GEN
FlxqX_Berlekamp_i(GEN f,GEN T,ulong p)1957 FlxqX_Berlekamp_i(GEN f, GEN T, ulong p)
1958 {
1959 long lfact, d = degpol(f), j, k, lV;
1960 GEN E, t, V, xp;
1961 switch(d)
1962 {
1963 case -1: retmkmat2(mkcolcopy(f), mkvecsmall(1));
1964 case 0: return trivial_fact();
1965 }
1966 T = Flx_get_red(T, p);
1967 f = FlxqX_normalize(f, T, p);
1968 if (FlxY_degreex(f) <= 0) return Flx_factorff_i(FlxX_to_Flx(f), T, p);
1969 if (degpol(f)==2) return FlxqX_factor_2(f, T, p);
1970 xp = Flx_Frobenius(T, p);
1971 V = FlxqX_factor_squarefree_i(f, xp, T, p); lV = lg(V);
1972
1973 /* to hold factors and exponents */
1974 t = cgetg(d+1,t_VEC);
1975 E = cgetg(d+1, t_VECSMALL);
1976 lfact = 1;
1977 for (k=1; k<lV ; k++)
1978 {
1979 if (degpol(gel(V,k))==0) continue;
1980 gel(t,lfact) = FlxqX_normalize(gel(V, k), T,p);
1981 d = FlxqX_split_Berlekamp(&gel(t,lfact), xp, T, p);
1982 for (j = 0; j < d; j++) E[lfact+j] = k;
1983 lfact += d;
1984 }
1985 setlg(t, lfact);
1986 setlg(E, lfact);
1987 return sort_factor_pol(mkvec2(t, E), cmp_Flx);
1988 }
1989
1990 static GEN
FpXQX_Berlekamp_i(GEN f,GEN T,GEN p)1991 FpXQX_Berlekamp_i(GEN f, GEN T, GEN p)
1992 {
1993 long lfact, d = degpol(f), j, k, lV;
1994 GEN E, t, V;
1995 switch(d)
1996 {
1997 case -1: retmkmat2(mkcolcopy(f), mkvecsmall(1));
1998 case 0: return trivial_fact();
1999 }
2000 T = FpX_get_red(T, p);
2001 f = FpXQX_normalize(f, T, p);
2002 if (isabsolutepol(f)) return FpX_factorff_i(simplify_shallow(f), T, p);
2003 if (degpol(f)==2) return FpXQX_factor_2(f, T, p);
2004 V = FpXQX_factor_Yun(f, T, p); lV = lg(V);
2005
2006 /* to hold factors and exponents */
2007 t = cgetg(d+1,t_VEC);
2008 E = cgetg(d+1, t_VECSMALL);
2009 lfact = 1;
2010 for (k=1; k<lV ; k++)
2011 {
2012 if (degpol(gel(V,k))==0) continue;
2013 gel(t,lfact) = FpXQX_normalize(gel(V, k), T,p);
2014 d = FpXQX_split_Berlekamp(&gel(t,lfact), T, p);
2015 for (j = 0; j < d; j++) E[lfact+j] = k;
2016 lfact += d;
2017 }
2018 setlg(t, lfact);
2019 setlg(E, lfact);
2020 return sort_factor_pol(mkvec2(t, E), cmp_RgX);
2021 }
2022
2023 long
FlxqX_ddf_degree(GEN S,GEN XP,GEN T,ulong p)2024 FlxqX_ddf_degree(GEN S, GEN XP, GEN T, ulong p)
2025 {
2026 pari_sp av = avma;
2027 GEN X, b, g, xq, q;
2028 long i, j, n, v, B, l, m, bo, ro;
2029 pari_timer ti;
2030 hashtable h;
2031
2032 n = get_FlxqX_degree(S); v = get_FlxqX_var(S);
2033 X = polx_FlxX(v,get_Flx_var(T));
2034 if (gequal(X,XP)) return 1;
2035 B = n/2;
2036 l = usqrt(B);
2037 m = (B+l-1)/l;
2038 T = Flx_get_red(T, p);
2039 S = FlxqX_get_red(S, T, p);
2040 hash_init_GEN(&h, l+2, gequal, 1);
2041 hash_insert_long(&h, X, 0);
2042 hash_insert_long(&h, XP, 1);
2043 bo = brent_kung_optpow(n, l-1, 1);
2044 ro = l<=1 ? 0: (bo-1)/(l-1) + ((n-1)/bo);
2045 q = powuu(p, get_Flx_degree(T));
2046 if (DEBUGLEVEL>=7) timer_start(&ti);
2047 b = XP;
2048 if (expi(q) > ro)
2049 {
2050 xq = FlxqXQ_powers(b, brent_kung_optpow(n, l-1, 1), S, T, p);
2051 if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf_degree: xq baby");
2052 } else xq = NULL;
2053 for (i = 3; i <= l+1; i++)
2054 {
2055 b = xq ? FlxqX_FlxqXQV_eval(b, xq, S, T, p)
2056 : FlxqXQ_pow(b, q, S, T, p);
2057 if (gequal(b,X)) return gc_long(av,i-1);
2058 hash_insert_long(&h, b, i-1);
2059 }
2060 if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf_degree: baby");
2061 g = b;
2062 xq = FlxqXQ_powers(g, brent_kung_optpow(n, m, 1), S, T, p);
2063 if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf_degree: xq giant");
2064 for(i = 2; i <= m+1; i++)
2065 {
2066 g = FlxqX_FlxqXQV_eval(g, xq, S, T, p);
2067 if (hash_haskey_long(&h, g, &j)) return gc_long(av, l*i-j);
2068 }
2069 return gc_long(av,n);
2070 }
2071
2072 static GEN
FlxqX_ddf_Shoup(GEN S,GEN Xq,GEN T,ulong p)2073 FlxqX_ddf_Shoup(GEN S, GEN Xq, GEN T, ulong p)
2074 {
2075 pari_sp av = avma;
2076 GEN b, g, h, F, f, Sr, xq, q;
2077 long i, j, n, v, vT, bo, ro;
2078 long B, l, m;
2079 pari_timer ti;
2080 n = get_FlxqX_degree(S); v = get_FlxqX_var(S);
2081 vT = get_Flx_var(T);
2082 if (n == 0) return cgetg(1, t_VEC);
2083 if (n == 1) return mkvec(get_FlxqX_mod(S));
2084 B = n/2;
2085 l = usqrt(B);
2086 m = (B+l-1)/l;
2087 S = FlxqX_get_red(S, T, p);
2088 b = cgetg(l+2, t_VEC);
2089 gel(b, 1) = polx_FlxX(v, vT);
2090 gel(b, 2) = Xq;
2091 bo = brent_kung_optpow(n, l-1, 1);
2092 ro = l<=1 ? 0: (bo-1)/(l-1) + ((n-1)/bo);
2093 q = powuu(p, get_Flx_degree(T));
2094 if (DEBUGLEVEL>=7) timer_start(&ti);
2095 if (expi(q) <= ro)
2096 for (i = 3; i <= l+1; i++)
2097 gel(b, i) = FlxqXQ_pow(gel(b, i-1), q, S, T, p);
2098 else
2099 {
2100 xq = FlxqXQ_powers(gel(b, 2), bo, S, T, p);
2101 if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf_Shoup: xq baby");
2102 for (i = 3; i <= l+1; i++)
2103 gel(b, i) = FlxqX_FlxqXQV_eval(gel(b, i-1), xq, S, T, p);
2104 }
2105 if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf_Shoup: baby");
2106 xq = FlxqXQ_powers(gel(b, l+1), brent_kung_optpow(n, m-1, 1), S, T, p);
2107 if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf_Shoup: xq giant");
2108 g = cgetg(m+1, t_VEC);
2109 gel(g, 1) = gel(xq, 2);
2110 for(i = 2; i <= m; i++)
2111 gel(g, i) = FlxqX_FlxqXQV_eval(gel(g, i-1), xq, S, T, p);
2112 if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf_Shoup: giant");
2113 h = cgetg(m+1, t_VEC);
2114 for (j = 1; j <= m; j++)
2115 {
2116 pari_sp av = avma;
2117 GEN gj = gel(g, j);
2118 GEN e = FlxX_sub(gj, gel(b, 1), p);
2119 for (i = 2; i <= l; i++)
2120 e = FlxqXQ_mul(e, FlxX_sub(gj, gel(b, i), p), S, T, p);
2121 gel(h, j) = gerepileupto(av, e);
2122 }
2123 if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf_Shoup: diff");
2124 Sr = get_FlxqX_mod(S);
2125 F = cgetg(m+1, t_VEC);
2126 for (j = 1; j <= m; j++)
2127 {
2128 GEN u = FlxqX_gcd(Sr, gel(h, j), T, p);
2129 if (degpol(u))
2130 {
2131 u = FlxqX_normalize(u, T, p);
2132 Sr = FlxqX_div(Sr, u, T, p);
2133 }
2134 gel(F,j) = u;
2135 }
2136 if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf_Shoup: F");
2137 f = const_vec(n, pol1_FlxX(v, vT));
2138 for (j = 1; j <= m; j++)
2139 {
2140 GEN e = gel(F, j);
2141 for (i=l-1; i >= 0; i--)
2142 {
2143 GEN u = FlxqX_gcd(e, FlxX_sub(gel(g, j), gel(b, i+1), p), T, p);
2144 if (degpol(u))
2145 {
2146 gel(f, l*j-i) = u = FlxqX_normalize(u, T, p);
2147 e = FlxqX_div(e, u, T, p);
2148 }
2149 if (!degpol(e)) break;
2150 }
2151 }
2152 if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf_Shoup: f");
2153 if (degpol(Sr)) gel(f, degpol(Sr)) = Sr;
2154 return gerepilecopy(av, f);
2155 }
2156
2157 static GEN
FlxqX_ddf_i(GEN f,GEN T,ulong p)2158 FlxqX_ddf_i(GEN f, GEN T, ulong p)
2159 {
2160 GEN Xq;
2161 if (!get_FlxqX_degree(f)) return cgetg(1, t_VEC);
2162 f = FlxqX_get_red(f, T, p);
2163 Xq = FlxqX_Frobenius(f, T, p);
2164 return FlxqX_ddf_Shoup(f, Xq, T, p);
2165 }
2166 GEN
FlxqX_ddf(GEN S,GEN T,ulong p)2167 FlxqX_ddf(GEN S, GEN T, ulong p)
2168 {
2169 T = Flx_get_red(T, p);
2170 S = FlxqX_normalize(get_FlxqX_mod(S), T, p);
2171 return ddf_to_ddf2( FlxqX_ddf_i(S, T, p) );
2172 }
2173 GEN
FlxqX_degfact(GEN S,GEN T,ulong p)2174 FlxqX_degfact(GEN S, GEN T, ulong p)
2175 {
2176 GEN V;
2177 long i, l;
2178 T = Flx_get_red(T, p);
2179 S = FlxqX_normalize(get_FlxqX_mod(S), T, p);
2180 V = FlxqX_factor_squarefree(S, T, p); l = lg(V);
2181 for (i=1; i < l; i++) gel(V,i) = FlxqX_ddf_i(gel(V,i), T, p);
2182 return vddf_to_simplefact(V, degpol(S));
2183 }
2184
2185 static void
FlxqX_edf_rec(GEN S,GEN xp,GEN Xp,GEN hp,GEN t,long d,GEN T,ulong p,GEN V,long idx)2186 FlxqX_edf_rec(GEN S, GEN xp, GEN Xp, GEN hp, GEN t, long d, GEN T, ulong p, GEN V, long idx)
2187 {
2188 GEN Sp = get_FlxqX_mod(S);
2189 GEN u1, u2, f1, f2;
2190 GEN h;
2191 h = FlxqX_get_red(hp, T, p);
2192 t = FlxqX_rem(t, S, T, p);
2193 Xp = FlxqX_rem(Xp, h, T, p);
2194 u1 = FlxqX_roots_split(hp, xp, Xp, h, T, p);
2195 f1 = FlxqX_gcd(FlxqX_FlxqXQ_eval(u1, t, S, T, p), Sp, T, p);
2196 f1 = FlxqX_normalize(f1, T, p);
2197 u2 = FlxqX_div(hp, u1, T, p);
2198 f2 = FlxqX_div(Sp, f1, T, p);
2199 if (degpol(u1)==1)
2200 gel(V, idx) = f1;
2201 else
2202 FlxqX_edf_rec(FlxqX_get_red(f1, T, p), xp, Xp, u1, t, d, T, p, V, idx);
2203 idx += degpol(f1)/d;
2204 if (degpol(u2)==1)
2205 gel(V, idx) = f2;
2206 else
2207 FlxqX_edf_rec(FlxqX_get_red(f2, T, p), xp, Xp, u2, t, d, T, p, V, idx);
2208 }
2209
2210 static void
FlxqX_edf(GEN Sp,GEN xp,GEN Xp,GEN Xq,long d,GEN T,ulong p,GEN V,long idx)2211 FlxqX_edf(GEN Sp, GEN xp, GEN Xp, GEN Xq, long d, GEN T, ulong p, GEN V, long idx)
2212 {
2213 long n = degpol(Sp), r = n/d, vS = varn(Sp), vT = get_Flx_var(T);
2214 GEN S, h, t;
2215 pari_timer ti;
2216 if (r==1) { gel(V, idx) = Sp; return; }
2217 S = FlxqX_get_red(Sp, T, p);
2218 Xp = FlxqX_rem(Xp, S, T, p);
2219 Xq = FlxqX_rem(Xq, S, T, p);
2220 if (DEBUGLEVEL>=7) timer_start(&ti);
2221 do
2222 {
2223 GEN g = random_FlxqX(n, vS, T, p);
2224 t = gel(FlxqXQ_auttrace(mkvec2(Xq, g), d, S, T, p), 2);
2225 if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_edf: FlxqXQ_auttrace");
2226 h = FlxqXQ_minpoly(t, S, T, p);
2227 if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_edf: FlxqXQ_minpoly");
2228 } while (degpol(h) != r);
2229 Xp = FlxqXQ_powu(polx_FlxX(vS, vT), p, h, T, p);
2230 FlxqX_edf_rec(S, xp, Xp, h, t, d, T, p, V, idx);
2231 }
2232
2233 static void
FlxqX_edf_simple(GEN Sp,GEN xp,GEN Xp,GEN Xq,long d,GEN T,ulong p,GEN V,long idx)2234 FlxqX_edf_simple(GEN Sp, GEN xp, GEN Xp, GEN Xq, long d, GEN T, ulong p, GEN V, long idx)
2235 {
2236 long v = varn(Sp), n = degpol(Sp), r = n/d;
2237 GEN S, f, ff;
2238 long vT = get_Flx_var(T), dT = get_Flx_degree(T);
2239 if (r==1) { gel(V, idx) = Sp; return; }
2240 S = FlxqX_get_red(Sp, T, p);
2241 Xp = FlxqX_rem(Xp, S, T, p);
2242 Xq = FlxqX_rem(Xq, S, T, p);
2243 while (1)
2244 {
2245 pari_sp btop = avma;
2246 long i;
2247 GEN g = random_FlxqX(n, v, T, p);
2248 GEN t = gel(FlxqXQ_auttrace(mkvec2(Xq, g), d, S, T, p), 2);
2249 if (lgpol(t) == 0) continue;
2250 for(i=1; i<=10; i++)
2251 {
2252 pari_sp btop2 = avma;
2253 GEN r = random_Flx(dT, vT, p);
2254 GEN R = FlxqXQ_halfFrobenius_i(FlxX_Flx_add(t, r, p), xp, Xp, S, T, p);
2255 f = FlxqX_gcd(FlxX_Flx_sub(R, pol1_Flx(vT), p), Sp, T, p);
2256 if (degpol(f) > 0 && degpol(f) < n) break;
2257 set_avma(btop2);
2258 }
2259 if (degpol(f) > 0 && degpol(f) < n) break;
2260 set_avma(btop);
2261 }
2262 f = FlxqX_normalize(f, T, p);
2263 ff = FlxqX_div(Sp, f , T, p);
2264 FlxqX_edf_simple(f, xp, Xp, Xq, d, T, p, V, idx);
2265 FlxqX_edf_simple(ff, xp, Xp, Xq, d, T, p, V, idx+degpol(f)/d);
2266 }
2267
2268 static GEN
FlxqX_factor_Shoup(GEN S,GEN xp,GEN T,ulong p)2269 FlxqX_factor_Shoup(GEN S, GEN xp, GEN T, ulong p)
2270 {
2271 long i, n, s = 0;
2272 GEN X, Xp, Xq, D, V;
2273 long dT = get_Flx_degree(T), vT = get_Flx_var(T);
2274 long e = expi(powuu(p, dT));
2275 pari_timer ti;
2276 n = get_FlxqX_degree(S);
2277 S = FlxqX_get_red(S, T, p);
2278 if (DEBUGLEVEL>=6) timer_start(&ti);
2279 X = polx_FlxX(get_FlxqX_var(S), vT);
2280 Xp = FlxqXQ_powu(X, p, S, T, p);
2281 Xq = FlxqXQ_Frobenius(xp, Xp, S, T, p);
2282 if (DEBUGLEVEL>=6) timer_printf(&ti,"FlxqX_Frobenius");
2283 D = FlxqX_ddf_Shoup(S, Xq, T, p);
2284 if (DEBUGLEVEL>=6) timer_printf(&ti,"FlxqX_ddf_Shoup");
2285 s = ddf_to_nbfact(D);
2286 V = cgetg(s+1, t_COL);
2287 for (i = 1, s = 1; i <= n; i++)
2288 {
2289 GEN Di = gel(D,i);
2290 long ni = degpol(Di), ri = ni/i;
2291 if (ni == 0) continue;
2292 Di = FlxqX_normalize(Di, T, p);
2293 if (ni == i) { gel(V, s++) = Di; continue; }
2294 if (ri <= e*expu(e))
2295 FlxqX_edf(Di, xp, Xp, Xq, i, T, p, V, s);
2296 else
2297 FlxqX_edf_simple(Di, xp, Xp, Xq, i, T, p, V, s);
2298 if (DEBUGLEVEL>=6) timer_printf(&ti,"FlxqX_edf(%ld)",i);
2299 s += ri;
2300 }
2301 return V;
2302 }
2303
2304 static GEN
FlxqX_factor_Cantor(GEN f,GEN T,ulong p)2305 FlxqX_factor_Cantor(GEN f, GEN T, ulong p)
2306 {
2307 GEN xp, E, F, V;
2308 long i, j, l;
2309 T = Flx_get_red(T, p);
2310 f = FlxqX_normalize(f, T, p);
2311 switch(degpol(f))
2312 {
2313 case -1: retmkmat2(mkcol(f), mkvecsmall(1));
2314 case 0: return trivial_fact();
2315 case 1: retmkmat2(mkcol(f), mkvecsmall(1));
2316 case 2: return FlxqX_factor_2(f, T, p);
2317 }
2318 if (FlxY_degreex(f) <= 0) return Flx_factorff_i(FlxX_to_Flx(f), T, p);
2319 xp = Flx_Frobenius(T, p);
2320 V = FlxqX_factor_squarefree_i(f, xp, get_Flx_mod(T), p);
2321 l = lg(V);
2322 F = cgetg(l, t_VEC);
2323 E = cgetg(l, t_VEC);
2324 for (i=1, j=1; i < l; i++)
2325 if (degpol(gel(V,i)))
2326 {
2327 GEN Fj = FlxqX_factor_Shoup(gel(V,i), xp, T, p);
2328 gel(F, j) = Fj;
2329 gel(E, j) = const_vecsmall(lg(Fj)-1, i);
2330 j++;
2331 }
2332 return sort_factor_pol(FE_concat(F,E,j), cmp_Flx);
2333 }
2334
2335 long
FlxqX_nbfact_Frobenius(GEN S,GEN Xq,GEN T,ulong p)2336 FlxqX_nbfact_Frobenius(GEN S, GEN Xq, GEN T, ulong p)
2337 {
2338 pari_sp av = avma;
2339 GEN u = get_FlxqX_mod(S);
2340 long s;
2341 if (FlxY_degreex(u) <= 0)
2342 s = Flx_nbfactff(FlxX_to_Flx(u), T, p);
2343 else
2344 s = ddf_to_nbfact(FlxqX_ddf_Shoup(S, Xq, T, p));
2345 return gc_long(av,s);
2346 }
2347
2348 long
FlxqX_nbfact(GEN S,GEN T,ulong p)2349 FlxqX_nbfact(GEN S, GEN T, ulong p)
2350 {
2351 pari_sp av = avma;
2352 GEN u = get_FlxqX_mod(S);
2353 long s;
2354 if (FlxY_degreex(u) <= 0)
2355 s = Flx_nbfactff(FlxX_to_Flx(u), T, p);
2356 else
2357 s = ddf_to_nbfact(FlxqX_ddf_Shoup(S, FlxqX_Frobenius(S, T, p), T, p));
2358 return gc_long(av,s);
2359 }
2360
2361 GEN
FlxqX_factor(GEN x,GEN T,ulong p)2362 FlxqX_factor(GEN x, GEN T, ulong p)
2363 {
2364 pari_sp av = avma;
2365 return gerepilecopy(av, FlxqX_factor_Cantor(x, T, p));
2366 }
2367
2368 GEN
F2xqX_factor(GEN x,GEN T)2369 F2xqX_factor(GEN x, GEN T)
2370 {
2371 pari_sp av = avma;
2372 return gerepilecopy(av, F2xqX_factor_Cantor(x, T));
2373 }
2374
2375 long
FpXQX_ddf_degree(GEN S,GEN XP,GEN T,GEN p)2376 FpXQX_ddf_degree(GEN S, GEN XP, GEN T, GEN p)
2377 {
2378 pari_sp av = avma;
2379 GEN X, b, g, xq, q;
2380 long i, j, n, v, B, l, m, bo, ro;
2381 pari_timer ti;
2382 hashtable h;
2383
2384 n = get_FpXQX_degree(S); v = get_FpXQX_var(S);
2385 X = pol_x(v);
2386 if (gequal(X,XP)) return 1;
2387 B = n/2;
2388 l = usqrt(B);
2389 m = (B+l-1)/l;
2390 T = FpX_get_red(T, p);
2391 S = FpXQX_get_red(S, T, p);
2392 hash_init_GEN(&h, l+2, gequal, 1);
2393 hash_insert_long(&h, X, 0);
2394 hash_insert_long(&h, simplify_shallow(XP), 1);
2395 bo = brent_kung_optpow(n, l-1, 1);
2396 ro = l<=1 ? 0: (bo-1)/(l-1) + ((n-1)/bo);
2397 q = powiu(p, get_FpX_degree(T));
2398 if (DEBUGLEVEL>=7) timer_start(&ti);
2399 b = XP;
2400 if (expi(q) > ro)
2401 {
2402 xq = FpXQXQ_powers(b, brent_kung_optpow(n, l-1, 1), S, T, p);
2403 if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf_degree: xq baby");
2404 } else xq = NULL;
2405 for (i = 3; i <= l+1; i++)
2406 {
2407 b = xq ? FpXQX_FpXQXQV_eval(b, xq, S, T, p)
2408 : FpXQXQ_pow(b, q, S, T, p);
2409 if (gequal(b,X)) return gc_long(av,i-1);
2410 hash_insert_long(&h, simplify_shallow(b), i-1);
2411 }
2412 if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf_degree: baby");
2413 g = b;
2414 xq = FpXQXQ_powers(g, brent_kung_optpow(n, m, 1), S, T, p);
2415 if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf_degree: xq giant");
2416 for(i = 2; i <= m+1; i++)
2417 {
2418 g = FpXQX_FpXQXQV_eval(g, xq, S, T, p);
2419 if (hash_haskey_long(&h, simplify_shallow(g), &j)) return gc_long(av,l*i-j);
2420 }
2421 return gc_long(av,n);
2422 }
2423
2424 static GEN
FpXQX_ddf_Shoup(GEN S,GEN Xq,GEN T,GEN p)2425 FpXQX_ddf_Shoup(GEN S, GEN Xq, GEN T, GEN p)
2426 {
2427 pari_sp av = avma;
2428 GEN b, g, h, F, f, Sr, xq, q;
2429 long i, j, n, v, bo, ro;
2430 long B, l, m;
2431 pari_timer ti;
2432 n = get_FpXQX_degree(S); v = get_FpXQX_var(S);
2433 if (n == 0) return cgetg(1, t_VEC);
2434 if (n == 1) return mkvec(get_FpXQX_mod(S));
2435 B = n/2;
2436 l = usqrt(B);
2437 m = (B+l-1)/l;
2438 S = FpXQX_get_red(S, T, p);
2439 b = cgetg(l+2, t_VEC);
2440 gel(b, 1) = pol_x(v);
2441 gel(b, 2) = Xq;
2442 bo = brent_kung_optpow(n, l-1, 1);
2443 ro = l<=1 ? 0: (bo-1)/(l-1) + ((n-1)/bo);
2444 q = powiu(p, get_FpX_degree(T));
2445 if (DEBUGLEVEL>=7) timer_start(&ti);
2446 if (expi(q) <= ro)
2447 for (i = 3; i <= l+1; i++)
2448 gel(b, i) = FpXQXQ_pow(gel(b, i-1), q, S, T, p);
2449 else
2450 {
2451 xq = FpXQXQ_powers(gel(b, 2), bo, S, T, p);
2452 if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf_Shoup: xq baby");
2453 for (i = 3; i <= l+1; i++)
2454 gel(b, i) = FpXQX_FpXQXQV_eval(gel(b, i-1), xq, S, T, p);
2455 }
2456 if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf_Shoup: baby");
2457 xq = FpXQXQ_powers(gel(b, l+1), brent_kung_optpow(n, m-1, 1), S, T, p);
2458 if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf_Shoup: xq giant");
2459 g = cgetg(m+1, t_VEC);
2460 gel(g, 1) = gel(xq, 2);
2461 for(i = 2; i <= m; i++)
2462 gel(g, i) = FpXQX_FpXQXQV_eval(gel(g, i-1), xq, S, T, p);
2463 if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf_Shoup: giant");
2464 h = cgetg(m+1, t_VEC);
2465 for (j = 1; j <= m; j++)
2466 {
2467 pari_sp av = avma;
2468 GEN gj = gel(g, j);
2469 GEN e = FpXX_sub(gj, gel(b, 1), p);
2470 for (i = 2; i <= l; i++)
2471 e = FpXQXQ_mul(e, FpXX_sub(gj, gel(b, i), p), S, T, p);
2472 gel(h, j) = gerepileupto(av, e);
2473 }
2474 if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf_Shoup: diff");
2475 Sr = get_FpXQX_mod(S);
2476 F = cgetg(m+1, t_VEC);
2477 for (j = 1; j <= m; j++)
2478 {
2479 GEN u = FpXQX_gcd(Sr, gel(h,j), T, p);
2480 if (degpol(u))
2481 {
2482 u = FpXQX_normalize(u, T, p);
2483 Sr = FpXQX_div(Sr, u, T, p);
2484 }
2485 gel(F,j) = u;
2486 }
2487 if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf_Shoup: F");
2488 f = const_vec(n, pol_1(v));
2489 for (j = 1; j <= m; j++)
2490 {
2491 GEN e = gel(F, j);
2492 for (i=l-1; i >= 0; i--)
2493 {
2494 GEN u = FpXQX_gcd(e, FpXX_sub(gel(g, j), gel(b, i+1), p), T, p);
2495 if (degpol(u))
2496 {
2497 gel(f, l*j-i) = u = FpXQX_normalize(u, T, p);
2498 e = FpXQX_div(e, u, T, p);
2499 }
2500 if (!degpol(e)) break;
2501 }
2502 }
2503 if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf_Shoup: f");
2504 if (degpol(Sr)) gel(f, degpol(Sr)) = Sr;
2505 return gerepilecopy(av, f);
2506 }
2507
2508 static GEN
FpXQX_ddf_i(GEN f,GEN T,GEN p)2509 FpXQX_ddf_i(GEN f, GEN T, GEN p)
2510 {
2511 GEN Xq;
2512 if (!get_FpXQX_degree(f)) return cgetg(1,t_VEC);
2513 f = FpXQX_get_red(f, T, p);
2514 Xq = FpXQX_Frobenius(f, T, p);
2515 return FpXQX_ddf_Shoup(f, Xq, T, p);
2516 }
2517
2518 static GEN
FpXQX_ddf_raw(GEN f,GEN T,GEN p)2519 FpXQX_ddf_raw(GEN f, GEN T, GEN p)
2520 {
2521 if (lgefint(p)==3)
2522 {
2523 ulong pp = p[2];
2524 GEN M;
2525 long vT = get_FpX_var(T);
2526 if (pp==2)
2527 {
2528 M = F2xqX_ddf(ZXX_to_F2xX(f, vT), ZX_to_F2x(get_FpX_mod(T)));
2529 return mkvec2(F2xXC_to_ZXXC(gel(M,1)), gel(M,2));
2530 }
2531 M = FlxqX_ddf(ZXX_to_FlxX(f, pp, vT), ZXT_to_FlxT(T, pp), pp);
2532 return mkvec2(FlxXC_to_ZXXC(gel(M,1)), gel(M,2));
2533 }
2534 T = FpX_get_red(T, p);
2535 f = FpXQX_normalize(get_FpXQX_mod(f), T, p);
2536 return ddf_to_ddf2( FpXQX_ddf_i(f, T, p) );
2537 }
2538
2539 GEN
FpXQX_ddf(GEN x,GEN T,GEN p)2540 FpXQX_ddf(GEN x, GEN T, GEN p)
2541 { pari_sp av = avma; return gerepilecopy(av, FpXQX_ddf_raw(x,T,p)); }
2542
2543 static GEN
FpXQX_degfact_raw(GEN f,GEN T,GEN p)2544 FpXQX_degfact_raw(GEN f, GEN T, GEN p)
2545 {
2546 GEN V;
2547 long i,l;
2548 if (lgefint(p)==3)
2549 {
2550 ulong pp = p[2];
2551 long vT = get_FpX_var(T);
2552 if (pp==2)
2553 return F2xqX_degfact(ZXX_to_F2xX(f, vT), ZX_to_F2x(get_FpX_mod(T)));
2554 else
2555 return FlxqX_degfact(ZXX_to_FlxX(f, pp, vT), ZXT_to_FlxT(T, pp), pp);
2556 }
2557 T = FpX_get_red(T, p);
2558 f = FpXQX_normalize(get_FpXQX_mod(f), T, p);
2559 V = FpXQX_factor_Yun(f, T, p); l = lg(V);
2560 for (i=1; i < l; i++) gel(V,i) = FpXQX_ddf_i(gel(V,i), T, p);
2561 return vddf_to_simplefact(V, degpol(f));
2562 }
2563
2564 GEN
FpXQX_degfact(GEN x,GEN T,GEN p)2565 FpXQX_degfact(GEN x, GEN T, GEN p)
2566 { pari_sp av = avma; return gerepilecopy(av, FpXQX_degfact_raw(x,T,p)); }
2567
2568 static void
FpXQX_edf_rec(GEN S,GEN xp,GEN Xp,GEN hp,GEN t,long d,GEN T,GEN p,GEN V,long idx)2569 FpXQX_edf_rec(GEN S, GEN xp, GEN Xp, GEN hp, GEN t, long d, GEN T, GEN p, GEN V, long idx)
2570 {
2571 GEN Sp = get_FpXQX_mod(S);
2572 GEN u1, u2, f1, f2;
2573 GEN h;
2574 h = FpXQX_get_red(hp, T, p);
2575 t = FpXQX_rem(t, S, T, p);
2576 Xp = FpXQX_rem(Xp, h, T, p);
2577 u1 = FpXQX_roots_split(hp, xp, Xp, h, T, p);
2578 f1 = FpXQX_gcd(FpXQX_FpXQXQ_eval(u1, t, S, T, p), Sp, T, p);
2579 f1 = FpXQX_normalize(f1, T, p);
2580 u2 = FpXQX_div(hp, u1, T, p);
2581 f2 = FpXQX_div(Sp, f1, T, p);
2582 if (degpol(u1)==1)
2583 gel(V, idx) = f1;
2584 else
2585 FpXQX_edf_rec(FpXQX_get_red(f1, T, p), xp, Xp, u1, t, d, T, p, V, idx);
2586 idx += degpol(f1)/d;
2587 if (degpol(u2)==1)
2588 gel(V, idx) = f2;
2589 else
2590 FpXQX_edf_rec(FpXQX_get_red(f2, T, p), xp, Xp, u2, t, d, T, p, V, idx);
2591 }
2592
2593 static void
FpXQX_edf(GEN Sp,GEN xp,GEN Xp,GEN Xq,long d,GEN T,GEN p,GEN V,long idx)2594 FpXQX_edf(GEN Sp, GEN xp, GEN Xp, GEN Xq, long d, GEN T, GEN p, GEN V, long idx)
2595 {
2596 long n = degpol(Sp), r = n/d, vS = varn(Sp);
2597 GEN S, h, t;
2598 pari_timer ti;
2599 if (r==1) { gel(V, idx) = Sp; return; }
2600 S = FpXQX_get_red(Sp, T, p);
2601 Xp = FpXQX_rem(Xp, S, T, p);
2602 Xq = FpXQX_rem(Xq, S, T, p);
2603 if (DEBUGLEVEL>=7) timer_start(&ti);
2604 do
2605 {
2606 GEN g = random_FpXQX(n, vS, T, p);
2607 t = gel(FpXQXQ_auttrace(mkvec2(Xq, g), d, S, T, p), 2);
2608 if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_edf: FpXQXQ_auttrace");
2609 h = FpXQXQ_minpoly(t, S, T, p);
2610 if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_edf: FpXQXQ_minpoly");
2611 } while (degpol(h) != r);
2612 Xp = FpXQXQ_pow(pol_x(vS), p, h, T, p);
2613 FpXQX_edf_rec(S, xp, Xp, h, t, d, T, p, V, idx);
2614 }
2615
2616 static void
FpXQX_edf_simple(GEN Sp,GEN xp,GEN Xp,GEN Xq,long d,GEN T,GEN p,GEN V,long idx)2617 FpXQX_edf_simple(GEN Sp, GEN xp, GEN Xp, GEN Xq, long d, GEN T, GEN p, GEN V, long idx)
2618 {
2619 long v = varn(Sp), n = degpol(Sp), r = n/d;
2620 GEN S, f, ff;
2621 long vT = get_FpX_var(T), dT = get_FpX_degree(T);
2622 if (r==1) { gel(V, idx) = Sp; return; }
2623 S = FpXQX_get_red(Sp, T, p);
2624 Xp = FpXQX_rem(Xp, S, T, p);
2625 Xq = FpXQX_rem(Xq, S, T, p);
2626 while (1)
2627 {
2628 pari_sp btop = avma;
2629 long i;
2630 GEN g = random_FpXQX(n, v, T, p);
2631 GEN t = gel(FpXQXQ_auttrace(mkvec2(Xq, g), d, S, T, p), 2);
2632 if (lgpol(t) == 0) continue;
2633 for(i=1; i<=10; i++)
2634 {
2635 pari_sp btop2 = avma;
2636 GEN r = random_FpX(dT, vT, p);
2637 GEN R = FpXQXQ_halfFrobenius_i(FqX_Fq_add(t, r, T, p), xp, Xp, S, T, p);
2638 f = FpXQX_gcd(FqX_Fq_add(R, gen_m1, T, p), Sp, T, p);
2639 if (degpol(f) > 0 && degpol(f) < n) break;
2640 set_avma(btop2);
2641 }
2642 if (degpol(f) > 0 && degpol(f) < n) break;
2643 set_avma(btop);
2644 }
2645 f = FpXQX_normalize(f, T, p);
2646 ff = FpXQX_div(Sp, f , T, p);
2647 FpXQX_edf_simple(f, xp, Xp, Xq, d, T, p, V, idx);
2648 FpXQX_edf_simple(ff, xp, Xp, Xq, d, T, p, V, idx+degpol(f)/d);
2649 }
2650
2651 static GEN
FpXQX_factor_Shoup(GEN S,GEN xp,GEN T,GEN p)2652 FpXQX_factor_Shoup(GEN S, GEN xp, GEN T, GEN p)
2653 {
2654 long i, n, s = 0, dT = get_FpX_degree(T), e = expi(powiu(p, dT));
2655 GEN X, Xp, Xq, D, V;
2656 pari_timer ti;
2657 n = get_FpXQX_degree(S);
2658 S = FpXQX_get_red(S, T, p);
2659 if (DEBUGLEVEL>=6) timer_start(&ti);
2660 X = pol_x(get_FpXQX_var(S));
2661 Xp = FpXQXQ_pow(X, p, S, T, p);
2662 Xq = FpXQXQ_Frobenius(xp, Xp, S, T, p);
2663 if (DEBUGLEVEL>=6) timer_printf(&ti,"FpXQX_Frobenius");
2664 D = FpXQX_ddf_Shoup(S, Xq, T, p);
2665 if (DEBUGLEVEL>=6) timer_printf(&ti,"FpXQX_ddf_Shoup");
2666 s = ddf_to_nbfact(D);
2667 V = cgetg(s+1, t_COL);
2668 for (i = 1, s = 1; i <= n; i++)
2669 {
2670 GEN Di = gel(D,i);
2671 long ni = degpol(Di), ri = ni/i;
2672 if (ni == 0) continue;
2673 Di = FpXQX_normalize(Di, T, p);
2674 if (ni == i) { gel(V, s++) = Di; continue; }
2675 if (ri <= e*expu(e))
2676 FpXQX_edf(Di, xp, Xp, Xq, i, T, p, V, s);
2677 else
2678 FpXQX_edf_simple(Di, xp, Xp, Xq, i, T, p, V, s);
2679 if (DEBUGLEVEL>=6) timer_printf(&ti,"FpXQX_edf(%ld)",i);
2680 s += ri;
2681 }
2682 return V;
2683 }
2684
2685 static GEN
FpXQX_factor_Cantor(GEN f,GEN T,GEN p)2686 FpXQX_factor_Cantor(GEN f, GEN T, GEN p)
2687 {
2688 GEN xp, E, F, V;
2689 long i, j, l;
2690 T = FpX_get_red(T, p);
2691 f = FpXQX_normalize(f, T, p);
2692 switch(degpol(f))
2693 {
2694 case -1: retmkmat2(mkcol(f), mkvecsmall(1));
2695 case 0: return trivial_fact();
2696 case 1: retmkmat2(mkcol(f), mkvecsmall(1));
2697 case 2: return FpXQX_factor_2(f, T, p);
2698 }
2699 if (isabsolutepol(f)) return FpX_factorff_i(simplify_shallow(f), T, p);
2700 xp = FpX_Frobenius(T, p);
2701 V = FpXQX_factor_Yun(f, T, p);
2702 l = lg(V);
2703 F = cgetg(l, t_VEC);
2704 E = cgetg(l, t_VEC);
2705 for (i=1, j=1; i < l; i++)
2706 if (degpol(gel(V,i)))
2707 {
2708 GEN Fj = FpXQX_factor_Shoup(gel(V,i), xp, T, p);
2709 gel(E,j) = const_vecsmall(lg(Fj)-1, i);
2710 gel(F,j) = Fj; j++;
2711 }
2712 return sort_factor_pol(FE_concat(F,E,j), cmp_RgX);
2713 }
2714
2715 long
FpXQX_nbfact_Frobenius(GEN S,GEN Xq,GEN T,GEN p)2716 FpXQX_nbfact_Frobenius(GEN S, GEN Xq, GEN T, GEN p)
2717 {
2718 pari_sp av = avma;
2719 GEN u = get_FpXQX_mod(S);
2720 long s;
2721 if (lgefint(p)==3)
2722 {
2723 ulong pp = p[2];
2724 long vT = get_FpX_var(T);
2725 GEN Sp = ZXXT_to_FlxXT(S,pp,vT), Xqp = ZXX_to_FlxX(Xq,pp,vT);
2726 s = FlxqX_nbfact_Frobenius(Sp, Xqp, ZXT_to_FlxT(T,pp), pp);
2727 }
2728 else if (isabsolutepol(u))
2729 s = FpX_nbfactff(simplify_shallow(u), T, p);
2730 else
2731 s = ddf_to_nbfact(FpXQX_ddf_Shoup(S, Xq, T, p));
2732 return gc_long(av,s);
2733 }
2734
2735 long
FpXQX_nbfact(GEN S,GEN T,GEN p)2736 FpXQX_nbfact(GEN S, GEN T, GEN p)
2737 {
2738 pari_sp av = avma;
2739 GEN u = get_FpXQX_mod(S);
2740 long s;
2741 if (lgefint(p)==3)
2742 {
2743 ulong pp = p[2];
2744 long vT = get_FpX_var(T);
2745 s = FlxqX_nbfact(ZXXT_to_FlxXT(S,pp,vT), ZXT_to_FlxT(T,pp), pp);
2746 }
2747 else if (isabsolutepol(u))
2748 s = FpX_nbfactff(simplify_shallow(u), T, p);
2749 else
2750 s = ddf_to_nbfact(FpXQX_ddf_Shoup(S, FpXQX_Frobenius(S, T, p), T, p));
2751 return gc_long(av,s);
2752 }
2753 long
FqX_nbfact(GEN u,GEN T,GEN p)2754 FqX_nbfact(GEN u, GEN T, GEN p)
2755 { return T ? FpXQX_nbfact(u, T, p): FpX_nbfact(u, p); }
2756
2757 static GEN
FpXQX_factor_Berlekamp_i(GEN f,GEN T,GEN p)2758 FpXQX_factor_Berlekamp_i(GEN f, GEN T, GEN p)
2759 {
2760 if (lgefint(p)==3)
2761 {
2762 ulong pp = p[2];
2763 GEN M;
2764 long vT = get_FpX_var(T);
2765 if (pp==2)
2766 {
2767 M = F2xqX_factor_Cantor(ZXX_to_F2xX(f, vT), ZX_to_F2x(get_FpX_mod(T)));
2768 return mkvec2(F2xXC_to_ZXXC(gel(M,1)), gel(M,2));
2769 }
2770 M = FlxqX_Berlekamp_i(ZXX_to_FlxX(f, pp, vT), ZXT_to_FlxT(T, pp), pp);
2771 return mkvec2(FlxXC_to_ZXXC(gel(M,1)), gel(M,2));
2772 }
2773 return FpXQX_Berlekamp_i(f, T, p);
2774 }
2775 GEN
FpXQX_factor_Berlekamp(GEN x,GEN T,GEN p)2776 FpXQX_factor_Berlekamp(GEN x, GEN T, GEN p)
2777 { pari_sp av = avma; return gerepilecopy(av, FpXQX_factor_Berlekamp_i(x,T,p)); }
2778
2779 static GEN
FpXQX_factor_i(GEN f,GEN T,GEN p)2780 FpXQX_factor_i(GEN f, GEN T, GEN p)
2781 {
2782 if (lgefint(p)==3)
2783 {
2784 ulong pp = p[2];
2785 GEN M;
2786 long vT = get_FpX_var(T);
2787 if (pp==2)
2788 {
2789 M = F2xqX_factor_Cantor(ZXX_to_F2xX(f, vT), ZX_to_F2x(get_FpX_mod(T)));
2790 return mkvec2(F2xXC_to_ZXXC(gel(M,1)), gel(M,2));
2791 }
2792 M = FlxqX_factor_Cantor(ZXX_to_FlxX(f, pp, vT), ZXT_to_FlxT(T, pp), pp);
2793 return mkvec2(FlxXC_to_ZXXC(gel(M,1)), gel(M,2));
2794 }
2795 return FpXQX_factor_Cantor(f, T, p);
2796 }
2797 GEN
FpXQX_factor(GEN x,GEN T,GEN p)2798 FpXQX_factor(GEN x, GEN T, GEN p)
2799 { pari_sp av = avma; return gerepilecopy(av, FpXQX_factor_i(x,T,p)); }
2800
2801 long
FlxqX_is_squarefree(GEN P,GEN T,ulong p)2802 FlxqX_is_squarefree(GEN P, GEN T, ulong p)
2803 {
2804 pari_sp av = avma;
2805 GEN z = FlxqX_gcd(P, FlxX_deriv(P, p), T, p);
2806 return gc_long(av, degpol(z)==0);
2807 }
2808
2809 long
FqX_is_squarefree(GEN P,GEN T,GEN p)2810 FqX_is_squarefree(GEN P, GEN T, GEN p)
2811 {
2812 pari_sp av = avma;
2813 GEN z = FqX_gcd(P, FqX_deriv(P, T, p), T, p);
2814 return gc_long(av, degpol(z)==0);
2815 }
2816
2817 /* as RgX_to_FpXQ(FqX_to_FFX), leaving alone t_FFELT */
2818 static GEN
RgX_to_FFX(GEN x,GEN ff)2819 RgX_to_FFX(GEN x, GEN ff)
2820 {
2821 long i, lx;
2822 GEN p = FF_p_i(ff), T = FF_mod(ff), y = cgetg_copy(x,&lx);
2823 y[1] = x[1]; if (degpol(T) == 1) T = NULL;
2824 for (i = 2; i < lx; i++)
2825 {
2826 GEN c = gel(x,i);
2827 gel(y,i) = typ(c) == t_FFELT? c: Fq_to_FF(Rg_to_Fq(c,T,p), ff);
2828 }
2829 return y;
2830 }
2831
2832 #define code(t1,t2) ((t1 << 6) | t2)
2833 /* Check types and replace F by a monic normalized FpX having the same roots
2834 * Don't bother to make constant polynomials monic */
2835 static GEN
factmod_init(GEN f,GEN * pD,GEN * pT,GEN * pp)2836 factmod_init(GEN f, GEN *pD, GEN *pT, GEN *pp)
2837 {
2838 const char *s = "factormod";
2839 GEN T, p, D = *pD;
2840 if (typ(f) != t_POL) pari_err_TYPE(s,f);
2841 if (!D)
2842 {
2843 long pa, t = RgX_type(f, pp, pT, &pa);
2844 if (t == t_FFELT) return f;
2845 *pD = gen_0;
2846 if (t != t_INTMOD && t != code(t_POLMOD,t_INTMOD)) pari_err_TYPE(s,f);
2847 return RgX_to_FqX(f, *pT, *pp);
2848 }
2849 if (typ(D) == t_FFELT) { *pD = NULL; *pT = D; return RgX_to_FFX(f,D); }
2850 if (!ff_parse_Tp(D, &T, &p, 1)) pari_err_TYPE(s,D);
2851 if (T && varncmp(varn(T), varn(f)) <= 0)
2852 pari_err_PRIORITY(s, T, "<=", varn(f));
2853 *pT = T; *pp = p; return RgX_to_FqX(f, T, p);
2854 }
2855 #undef code
2856
2857 int
ff_parse_Tp(GEN Tp,GEN * T,GEN * p,long red)2858 ff_parse_Tp(GEN Tp, GEN *T, GEN *p, long red)
2859 {
2860 long t = typ(Tp);
2861 *T = *p = NULL;
2862 if (t == t_INT) { *p = Tp; return cmpiu(*p, 1) > 0; }
2863 if (t != t_VEC || lg(Tp) != 3) return 0;
2864 *T = gel(Tp,1);
2865 *p = gel(Tp,2);
2866 if (typ(*p) != t_INT)
2867 {
2868 if (typ(*T) != t_INT) return 0;
2869 swap(*T, *p); /* support both [T,p] and [p,T] */
2870 }
2871 if (red) *T = RgX_to_FpX(*T, *p);
2872 return cmpiu(*p, 1) > 0 && typ(*T) == t_POL && RgX_is_ZX(*T);
2873 }
2874
2875 static GEN
to_Fq(GEN x,GEN T,GEN p)2876 to_Fq(GEN x, GEN T, GEN p)
2877 {
2878 long i, lx, tx = typ(x);
2879 GEN y;
2880
2881 if (tx == t_INT)
2882 y = mkintmod(x,p);
2883 else
2884 {
2885 if (tx != t_POL) pari_err_TYPE("to_Fq",x);
2886 y = cgetg_copy(x,&lx); y[1] = x[1];
2887 for (i=2; i<lx; i++) gel(y,i) = mkintmod(gel(x,i), p);
2888 }
2889 return mkpolmod(y, T);
2890 }
2891 static GEN
to_Fq_pol(GEN x,GEN T,GEN p)2892 to_Fq_pol(GEN x, GEN T, GEN p)
2893 {
2894 long i, lx = lg(x);
2895 if (lx == 2)
2896 {
2897 GEN y = cgetg(3,t_POL); y[1]=x[1];
2898 gel(y,2) = mkintmod(gen_0,p); return y;
2899 }
2900 for (i = 2; i < lx; i++) gel(x,i) = to_Fq(gel(x,i),T,p);
2901 return x;
2902 }
2903 static GEN
to_Fq_fact(GEN fa,GEN T,GEN p)2904 to_Fq_fact(GEN fa, GEN T, GEN p)
2905 {
2906 GEN P = gel(fa,1);
2907 long j, l = lg(P);
2908 p = icopy(p); T = FpX_to_mod(T, p);
2909 for (j=1; j<l; j++) gel(P,j) = to_Fq_pol(gel(P,j), T,p);
2910 return fa;
2911 }
2912 static GEN
to_FqC(GEN P,GEN T,GEN p)2913 to_FqC(GEN P, GEN T, GEN p)
2914 {
2915 long j, l = lg(P);
2916 p = icopy(p); T = FpX_to_mod(T, p);
2917 for (j=1; j<l; j++) gel(P,j) = to_Fq(gel(P,j), T,p);
2918 return P;
2919 }
2920
2921 GEN
factmod(GEN f,GEN D)2922 factmod(GEN f, GEN D)
2923 {
2924 pari_sp av;
2925 GEN y, F, P, E, T, p;
2926 f = factmod_init(f, &D, &T,&p);
2927 if (!D) return FFX_factor(f, T);
2928 av = avma;
2929 F = FqX_factor(f, T, p); P = gel(F,1); E = gel(F,2);
2930 if (!T)
2931 {
2932 y = cgetg(3, t_MAT);
2933 gel(y,1) = FpXC_to_mod(P, p);
2934 gel(y,2) = Flc_to_ZC(E); return gerepileupto(av, y);
2935 }
2936 F = gerepilecopy(av, mkmat2(simplify_shallow(P), Flc_to_ZC(E)));
2937 return to_Fq_fact(F, T, p);
2938 }
2939 GEN
simplefactmod(GEN f,GEN D)2940 simplefactmod(GEN f, GEN D)
2941 {
2942 pari_sp av = avma;
2943 GEN T, p;
2944 f = factmod_init(f, &D, &T,&p);
2945 if (lg(f) <= 3) { set_avma(av); return trivial_fact(); }
2946 f = D? FqX_degfact(f, T, p): FFX_degfact(f, T);
2947 return gerepileupto(av, Flm_to_ZM(f));
2948 }
2949 static GEN
sqf_to_fact(GEN f)2950 sqf_to_fact(GEN f)
2951 {
2952 long i, j, l = lg(f);
2953 GEN P = cgetg(l, t_COL), E = cgetg(l, t_COL);
2954 for (i = j = 1; i < l; i++)
2955 if (degpol(gel(f,i)))
2956 {
2957 gel(P,j) = gel(f,i);
2958 gel(E,j) = utoi(i); j++;
2959 }
2960 setlg(P,j);
2961 setlg(E,j); return mkvec2(P,E);
2962 }
2963
2964 GEN
factormodSQF(GEN f,GEN D)2965 factormodSQF(GEN f, GEN D)
2966 {
2967 pari_sp av = avma;
2968 GEN F, T, p;
2969 f = factmod_init(f, &D, &T,&p);
2970 if (lg(f) <= 3) { set_avma(av); return trivial_fact(); }
2971 if (!D)
2972 F = sqf_to_fact(FFX_factor_squarefree(f, T));
2973 else
2974 {
2975 F = sqf_to_fact(FqX_factor_squarefree(f,T,p));
2976 gel(F,1) = FqXC_to_mod(gel(F,1), T,p);
2977 }
2978 settyp(F,t_MAT); return gerepilecopy(av, F);
2979 }
2980 GEN
factormodDDF(GEN f,GEN D)2981 factormodDDF(GEN f, GEN D)
2982 {
2983 pari_sp av = avma;
2984 GEN F, T, p;
2985 f = factmod_init(f, &D, &T,&p);
2986 if (lg(f) <= 3) { set_avma(av); return trivial_fact(); }
2987 if (!D) return FFX_ddf(f, T);
2988 F = FqX_ddf(f,T,p);
2989 gel(F,1) = FqXC_to_mod(gel(F,1), T,p);
2990 gel(F,2) = Flc_to_ZC(gel(F,2));
2991 settyp(F, t_MAT); return gerepilecopy(av, F);
2992 }
2993
2994 GEN
factormod0(GEN f,GEN p,long flag)2995 factormod0(GEN f, GEN p, long flag)
2996 {
2997 if (flag == 0) return factmod(f,p);
2998 if (flag != 1) pari_err_FLAG("factormod");
2999 return simplefactmod(f,p);
3000 }
3001 GEN
polrootsmod(GEN f,GEN D)3002 polrootsmod(GEN f, GEN D)
3003 {
3004 pari_sp av;
3005 GEN y, T, p;
3006 f = factmod_init(f, &D, &T,&p);
3007 if (!D) return FFX_roots(f, T);
3008 av = avma; y = FqX_roots(f, T, p);
3009 if (!T) return gerepileupto(av, FpC_to_mod(y,p));
3010 y = gerepilecopy(av, simplify_shallow(y));
3011 return to_FqC(y, T, p);
3012 }
3013
3014 GEN /* OBSOLETE */
rootmod0(GEN f,GEN p,long flag)3015 rootmod0(GEN f, GEN p, long flag) { (void)flag; return polrootsmod(f,p); }
3016 GEN /* OBSOLETE */
factorff(GEN f,GEN p,GEN T)3017 factorff(GEN f, GEN p, GEN T)
3018 {
3019 pari_sp av = avma;
3020 GEN D = (p && T)? mkvec2(T,p): NULL;
3021 return gerepileupto(av, factmod(f,D));
3022 }
3023 GEN /* OBSOLETE */
polrootsff(GEN f,GEN p,GEN T)3024 polrootsff(GEN f, GEN p, GEN T)
3025 {
3026 pari_sp av = avma;
3027 GEN D = (p && T)? mkvec2(T,p): NULL;
3028 return gerepileupto(av, polrootsmod(f, D));
3029 }
3030