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