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