Line data Source code
1 : /* Copyright (C) 2007 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_fflog
19 :
20 : /* Not so fast arithmetic with polynomials over F_2 */
21 :
22 : /***********************************************************************/
23 : /** **/
24 : /** F2x **/
25 : /** **/
26 : /***********************************************************************/
27 : /* F2x objects are defined as follows:
28 : An F2x is a t_VECSMALL:
29 : x[0] = codeword
30 : x[1] = evalvarn(variable number) (signe is not stored).
31 : x[2] = a_0...a_31 x[3] = a_32..a_63, etc. on 32bit
32 : x[2] = a_0...a_63 x[3] = a_64..a_127, etc. on 64bit
33 :
34 : where the a_i are bits.
35 :
36 : signe(x) is not valid. Use lgpol(x)!=0 instead.
37 : Note: pol0_F2x=pol0_Flx and pol1_F2x=pol1_Flx
38 : */
39 :
40 : INLINE long
41 264 : F2x_degreespec(GEN x, long l)
42 : {
43 264 : return (l==0)?-1:l*BITS_IN_LONG-bfffo(x[l-1])-1;
44 : }
45 :
46 : INLINE long
47 268784776 : F2x_degree_lg(GEN x, long l)
48 : {
49 268784776 : return (l==2)?-1:bit_accuracy(l)-bfffo(x[l-1])-1;
50 : }
51 :
52 : long
53 81087817 : F2x_degree(GEN x)
54 : {
55 81087817 : return F2x_degree_lg(x, lg(x));
56 : }
57 :
58 : GEN
59 63 : monomial_F2x(long d, long vs)
60 : {
61 63 : long l=nbits2lg(d+1);
62 63 : GEN z = zero_zv(l-1);
63 63 : z[1] = vs;
64 63 : F2x_set(z,d);
65 63 : return z;
66 : }
67 :
68 : GEN
69 1350789 : F2x_to_ZX(GEN x)
70 : {
71 1350789 : long l = 3+F2x_degree(x), lx = lg(x);
72 1350785 : GEN z = cgetg(l,t_POL);
73 : long i, j ,k;
74 2699642 : for (i=2, k=2; i<lx; i++)
75 4595669 : for (j=0; j<BITS_IN_LONG && k<l; j++,k++)
76 3246811 : gel(z,k) = (x[i]&(1UL<<j))?gen_1:gen_0;
77 1350784 : z[1]=evalsigne(l>=3)|x[1];
78 1350784 : return z;
79 : }
80 :
81 : GEN
82 131895 : F2x_to_Flx(GEN x)
83 : {
84 131895 : long l = 3+F2x_degree(x), lx = lg(x);
85 131895 : GEN z = cgetg(l,t_VECSMALL);
86 : long i, j, k;
87 131900 : z[1] = x[1];
88 296172 : for (i=2, k=2; i<lx; i++)
89 4524384 : for (j=0; j<BITS_IN_LONG && k<l; j++,k++)
90 4360112 : z[k] = (x[i]>>j)&1UL;
91 131900 : return z;
92 : }
93 :
94 : GEN
95 378 : F2x_to_F2xX(GEN z, long sv)
96 : {
97 378 : long i, d = F2x_degree(z);
98 378 : GEN x = cgetg(d+3,t_POL);
99 6769 : for (i=0; i<=d; i++)
100 6391 : gel(x,i+2) = F2x_coeff(z,i) ? pol1_F2x(sv): pol0_F2x(sv);
101 378 : x[1] = evalsigne(d+1!=0)| z[1]; return x;
102 : }
103 :
104 : GEN
105 213079 : Z_to_F2x(GEN x, long sv)
106 : {
107 213079 : return mpodd(x) ? pol1_F2x(sv): pol0_F2x(sv);
108 : }
109 :
110 : GEN
111 3164637 : ZX_to_F2x(GEN x)
112 : {
113 3164637 : long lx = lg(x), l = nbits2lg(lx-2);
114 3164636 : GEN z = cgetg(l,t_VECSMALL);
115 : long i, j, k;
116 3164681 : z[1] = ((ulong)x[1])&VARNBITS;
117 11305519 : for (i=2, k=1,j=BITS_IN_LONG; i<lx; i++,j++)
118 : {
119 8140831 : if (j==BITS_IN_LONG)
120 : {
121 3145940 : j=0; z[++k]=0;
122 : }
123 8140831 : if (mpodd(gel(x,i)))
124 6123181 : z[k] |= 1UL<<j;
125 : }
126 3164688 : return F2x_renormalize(z,l);
127 : }
128 :
129 : GEN
130 156351 : Flx_to_F2x(GEN x)
131 : {
132 156351 : long lx = lg(x), l = nbits2lg(lx-2);
133 156349 : GEN z = cgetg(l,t_VECSMALL);
134 : long i, j, k;
135 156353 : z[1] = x[1];
136 4733475 : for (i=2, k=1, j=BITS_IN_LONG; i<lx; i++,j++)
137 : {
138 4577122 : if (j==BITS_IN_LONG)
139 : {
140 182743 : j=0; z[++k] = 0;
141 : }
142 4577122 : if (x[i]&1UL)
143 2345334 : z[k] |= 1UL<<j;
144 : }
145 156353 : return F2x_renormalize(z,l);
146 : }
147 :
148 : GEN
149 1555108 : F2x_to_F2v(GEN x, long N)
150 : {
151 1555108 : long i, l = lg(x);
152 1555108 : long n = nbits2lg(N);
153 1555108 : GEN z = cgetg(n,t_VECSMALL);
154 1555114 : z[1] = N;
155 3341585 : for (i=2; i<l ; i++) z[i]=x[i];
156 1646351 : for ( ; i<n; i++) z[i]=0;
157 1555114 : return z;
158 : }
159 :
160 : GEN
161 1400 : RgX_to_F2x(GEN x)
162 : {
163 1400 : long l=nbits2lg(lgpol(x));
164 1400 : GEN z=cgetg(l,t_VECSMALL);
165 : long i,j,k;
166 1400 : z[1]=((ulong)x[1])&VARNBITS;
167 4277 : for(i=2, k=1,j=BITS_IN_LONG;i<lg(x);i++,j++)
168 : {
169 2877 : if (j==BITS_IN_LONG)
170 : {
171 1386 : j=0; k++; z[k]=0;
172 : }
173 2877 : if (Rg_to_F2(gel(x,i)))
174 1407 : z[k]|=1UL<<j;
175 : }
176 1400 : return F2x_renormalize(z,l);
177 : }
178 :
179 : /* If x is a POLMOD, assume modulus is a multiple of T. */
180 : GEN
181 1164228 : Rg_to_F2xq(GEN x, GEN T)
182 : {
183 1164228 : long ta, tx = typ(x), v = get_F2x_var(T);
184 : GEN a, b;
185 1164228 : if (is_const_t(tx))
186 : {
187 1163059 : if (tx == t_FFELT) return FF_to_F2xq(x);
188 246062 : return Rg_to_F2(x)? pol1_F2x(v): pol0_F2x(v);
189 : }
190 1169 : switch(tx)
191 : {
192 0 : case t_POLMOD:
193 0 : b = gel(x,1);
194 0 : a = gel(x,2); ta = typ(a);
195 0 : if (is_const_t(ta)) return Rg_to_F2(a)? pol1_F2x(v): pol0_F2x(v);
196 0 : b = RgX_to_F2x(b); if (b[1] != v) break;
197 0 : a = RgX_to_F2x(a); if (F2x_equal(b,T)) return a;
198 0 : if (lgpol(F2x_rem(b,T))==0) return F2x_rem(a, T);
199 0 : break;
200 1169 : case t_POL:
201 1169 : x = RgX_to_F2x(x);
202 1169 : if (x[1] != v) break;
203 1169 : return F2x_rem(x, T);
204 0 : case t_RFRAC:
205 0 : a = Rg_to_F2xq(gel(x,1), T);
206 0 : b = Rg_to_F2xq(gel(x,2), T);
207 0 : return F2xq_div(a,b, T);
208 : }
209 0 : pari_err_TYPE("Rg_to_F2xq",x);
210 : return NULL; /* LCOV_EXCL_LINE */
211 : }
212 :
213 : ulong
214 13370 : F2x_eval(GEN P, ulong x)
215 : {
216 13370 : if (lgpol(P)==0) return 0;
217 9694 : if (odd(x))
218 : {
219 2851 : long i, lP = lg(P);
220 2851 : ulong c = 0;
221 5702 : for (i=2; i<lP; i++)
222 2851 : c ^= P[i];
223 2851 : return thuemorseu(c);
224 : }
225 6843 : else return F2x_coeff(P,0);
226 : }
227 :
228 : GEN
229 31021868 : F2x_add(GEN x, GEN y)
230 : {
231 : long i,lz;
232 : GEN z;
233 31021868 : long lx=lg(x);
234 31021868 : long ly=lg(y);
235 31021868 : if (ly>lx) swapspec(x,y, lx,ly);
236 31021868 : lz = lx; z = cgetg(lz, t_VECSMALL); z[1]=x[1];
237 62778429 : for (i=2; i<ly; i++) z[i] = x[i]^y[i];
238 38599408 : for ( ; i<lx; i++) z[i] = x[i];
239 31030879 : return F2x_renormalize(z, lz);
240 : }
241 :
242 : static GEN
243 73287 : F2x_addspec(GEN x, GEN y, long lx, long ly)
244 : {
245 : long i,lz;
246 : GEN z;
247 :
248 73287 : if (ly>lx) swapspec(x,y, lx,ly);
249 73287 : lz = lx+2; z = cgetg(lz, t_VECSMALL) + 2;
250 205589 : for (i=0; i<ly-3; i+=4)
251 : {
252 132302 : z[i] = x[i]^y[i];
253 132302 : z[i+1] = x[i+1]^y[i+1];
254 132302 : z[i+2] = x[i+2]^y[i+2];
255 132302 : z[i+3] = x[i+3]^y[i+3];
256 : }
257 132603 : for (; i<ly; i++)
258 59316 : z[i] = x[i]^y[i];
259 631504 : for ( ; i<lx; i++) z[i] = x[i];
260 73287 : z -= 2; z[1] = 0; return F2x_renormalize(z, lz);
261 : }
262 :
263 : GEN
264 189927 : F2x_1_add(GEN y)
265 : {
266 : GEN z;
267 : long lz, i;
268 189927 : if (!lgpol(y))
269 90415 : return pol1_F2x(y[1]);
270 99512 : lz=lg(y);
271 99512 : z=cgetg(lz,t_VECSMALL);
272 99512 : z[1] = y[1];
273 99512 : z[2] = y[2]^1UL;
274 99512 : for(i=3;i<lz;i++)
275 0 : z[i] = y[i];
276 99512 : if (lz==3) z = F2x_renormalize(z,lz);
277 99512 : return z;
278 : }
279 :
280 : INLINE void
281 163375512 : F2x_addshiftipspec(GEN x, GEN y, long ny, ulong db)
282 : {
283 : long i;
284 163375512 : if (db)
285 : {
286 138844793 : ulong dc=BITS_IN_LONG-db;
287 138844793 : ulong r=0, yi;
288 217481918 : for(i=0; i<ny-3; i+=4)
289 : {
290 78637125 : yi = uel(y,i); x[i] ^= (yi<<db)|r; r = yi>>dc;
291 78637125 : yi = uel(y,i+1); x[i+1] ^= (yi<<db)|r; r = yi>>dc;
292 78637125 : yi = uel(y,i+2); x[i+2] ^= (yi<<db)|r; r = yi>>dc;
293 78637125 : yi = uel(y,i+3); x[i+3] ^= (yi<<db)|r; r = yi>>dc;
294 : }
295 274168178 : for( ; i<ny; i++)
296 : {
297 135323385 : ulong yi = uel(y,i); x[i] ^= (yi<<db)|r; r = yi>>dc;
298 : }
299 138844793 : if (r) x[i] ^= r;
300 : }
301 : else
302 : {
303 27361214 : for(i=0; i<ny-3; i+=4)
304 : {
305 2830495 : x[i] ^= y[i];
306 2830495 : x[i+1] ^= y[i+1];
307 2830495 : x[i+2] ^= y[i+2];
308 2830495 : x[i+3] ^= y[i+3];
309 : }
310 51868230 : for( ; i<ny; i++)
311 27337511 : x[i] ^= y[i];
312 : }
313 163375512 : }
314 :
315 : INLINE void
316 135741420 : F2x_addshiftip(GEN x, GEN y, ulong d)
317 : {
318 135741420 : ulong db, dl=dvmduBIL(d, &db);
319 135741407 : F2x_addshiftipspec(x+2+dl, y+2, lgpol(y), db);
320 135708849 : }
321 :
322 : static GEN
323 20094191 : F2x_mul1(ulong x, ulong y)
324 : {
325 20094191 : ulong x1=(x&HIGHMASK)>>BITS_IN_HALFULONG;
326 20094191 : ulong x2=x&LOWMASK;
327 20094191 : ulong y1=(y&HIGHMASK)>>BITS_IN_HALFULONG;
328 20094191 : ulong y2=y&LOWMASK;
329 : ulong r1,r2,rr;
330 : GEN z;
331 : ulong i;
332 20094191 : rr=r1=r2=0UL;
333 20094191 : if (x2)
334 618310401 : for(i=0;i<BITS_IN_HALFULONG;i++)
335 598255366 : if (x2&(1UL<<i))
336 : {
337 52214328 : r2^=y2<<i;
338 52214328 : rr^=y1<<i;
339 : }
340 20094191 : if (x1)
341 3476459 : for(i=0;i<BITS_IN_HALFULONG;i++)
342 3355166 : if (x1&(1UL<<i))
343 : {
344 914568 : r1^=y1<<i;
345 914568 : rr^=y2<<i;
346 : }
347 20094191 : r2^=(rr&LOWMASK)<<BITS_IN_HALFULONG;
348 20094191 : r1^=(rr&HIGHMASK)>>BITS_IN_HALFULONG;
349 20094191 : z=cgetg((r1?4:3),t_VECSMALL);
350 20094437 : z[2]=r2;
351 20094437 : if (r1) z[3]=r1;
352 20094437 : return z;
353 : }
354 :
355 : static GEN
356 3819678 : F2x_mulspec_basecase(GEN x, GEN y, long nx, long ny)
357 : {
358 : long l, i, j;
359 : GEN z;
360 3819678 : l = nx + ny;
361 3819678 : z = zero_Flv(l+1);
362 4431773 : for(i=0; i < ny-1; i++)
363 : {
364 612114 : GEN zi = z+2+i;
365 612114 : ulong yi = uel(y,i);
366 612114 : if (yi)
367 33648479 : for(j=0; j < BITS_IN_LONG; j++)
368 33036649 : if (yi&(1UL<<j)) F2x_addshiftipspec(zi,x,nx,j);
369 : }
370 : {
371 3819659 : GEN zi = z+2+i;
372 3819659 : ulong yi = uel(y,i);
373 3819659 : long c = BITS_IN_LONG-bfffo(yi);
374 26640875 : for(j=0; j < c; j++)
375 22821350 : if (yi&(1UL<<j)) F2x_addshiftipspec(zi,x,nx,j);
376 : }
377 3819525 : return F2x_renormalize(z, l+2);
378 : }
379 :
380 : static GEN
381 46908 : F2x_addshift(GEN x, GEN y, long d)
382 : {
383 46908 : GEN xd,yd,zd = (GEN)avma;
384 46908 : long a,lz,ny = lgpol(y), nx = lgpol(x);
385 46908 : long vs = x[1];
386 46908 : if (nx == 0) return y;
387 46908 : x += 2; y += 2; a = ny-d;
388 46908 : if (a <= 0)
389 : {
390 3255 : lz = (a>nx)? ny+2: nx+d+2;
391 3255 : (void)new_chunk(lz); xd = x+nx; yd = y+ny;
392 37981 : while (xd > x) *--zd = *--xd;
393 3255 : x = zd + a;
394 4577 : while (zd > x) *--zd = 0;
395 : }
396 : else
397 : {
398 43653 : xd = new_chunk(d); yd = y+d;
399 43653 : x = F2x_addspec(x,yd,nx,a);
400 43653 : lz = (a>nx)? ny+2: lg(x)+d;
401 895711 : x += 2; while (xd > x) *--zd = *--xd;
402 : }
403 525815 : while (yd > y) *--zd = *--yd;
404 46908 : *--zd = vs;
405 46908 : *--zd = evaltyp(t_VECSMALL) | evallg(lz); return zd;
406 : }
407 :
408 : /* shift polynomial + GC; do not set evalvarn. Cf Flx_shiftip */
409 : static GEN
410 23946311 : F2x_shiftip(pari_sp av, GEN x, long v)
411 : {
412 23946311 : long i, lx = lg(x), ly;
413 : GEN y;
414 23946311 : if (!v || lx==2) return gc_leaf(av, x);
415 29401 : ly = lx + v;
416 29401 : (void)new_chunk(ly); /* check that result fits */
417 29401 : x += lx; y = (GEN)av;
418 136059 : for (i = 2; i<lx; i++) *--y = *--x;
419 164794 : for (i = 0; i< v; i++) *--y = 0;
420 29401 : y -= 2; y[0] = evaltyp(t_VECSMALL) | evallg(ly);
421 29401 : return gc_const((pari_sp)y, y);
422 : }
423 :
424 : static GEN
425 264 : F2x_to_int(GEN a, long na, long da, long bs)
426 : {
427 264 : const long BIL = BITS_IN_LONG;
428 : GEN z, zs;
429 : long i,j,k,m;
430 264 : long lz = nbits2lg(1+da*bs);
431 264 : z = cgeti(lz); z[1] = evalsigne(1)|evallgefint(lz);
432 264 : zs = int_LSW(z); *zs = 0;
433 16185 : for (i=0, k=2, m=0; i<na; i++)
434 1022781 : for (j=0; j<BIL; j++, m+=bs)
435 : {
436 1007121 : if (m >= BIL)
437 : {
438 202089 : k++; if (k>=lz) break;
439 201828 : zs = int_nextW(zs);
440 201828 : *zs = 0;
441 201828 : m -= BIL;
442 : }
443 1006860 : *zs |= ((a[i]>>j)&1UL)<<m;
444 : }
445 264 : return int_normalize(z,0);
446 : }
447 :
448 : static GEN
449 132 : int_to_F2x(GEN x, long d, long bs)
450 : {
451 132 : const long BIL = BITS_IN_LONG;
452 132 : long lx = lgefint(x), lz = nbits2lg(d+1);
453 : long i,j,k,m;
454 132 : GEN xs = int_LSW(x);
455 132 : GEN z = cgetg(lz, t_VECSMALL);
456 132 : z[1] = 0;
457 15924 : for (k=2, i=2, m=0; k < lx; i++)
458 : {
459 15792 : z[i] = 0;
460 1022217 : for (j=0; j<BIL; j++, m+=bs)
461 : {
462 1006557 : if (m >= BIL)
463 : {
464 202005 : if (++k==lx) break;
465 201873 : xs = int_nextW(xs);
466 201873 : m -= BIL;
467 : }
468 1006425 : if ((*xs>>m)&1UL)
469 449712 : z[i]|=1UL<<j;
470 : }
471 : }
472 132 : return F2x_renormalize(z,lz);
473 : }
474 :
475 : static GEN
476 132 : F2x_mulspec_mulii(GEN a, GEN b, long na, long nb)
477 : {
478 132 : long da = F2x_degreespec(a,na), db = F2x_degreespec(b,nb);
479 132 : long bs = expu(1 + maxss(da, db))+1;
480 132 : GEN A = F2x_to_int(a,na,da,bs);
481 132 : GEN B = F2x_to_int(b,nb,db,bs);
482 132 : GEN z = mulii(A,B);
483 132 : return int_to_F2x(z,da+db,bs);
484 : }
485 :
486 : /* fast product (Karatsuba) of polynomials a,b. These are not real GENs, a+2,
487 : * b+2 were sent instead. na, nb = number of terms of a, b.
488 : * Only c, c0, c1, c2 are genuine GEN.
489 : */
490 : static GEN
491 28418985 : F2x_mulspec(GEN a, GEN b, long na, long nb)
492 : {
493 : GEN a0,c,c0;
494 28418985 : long n0, n0a, i, v = 0;
495 : pari_sp av;
496 28526846 : while (na && !a[0]) { a++; na-=1; v++; }
497 28446931 : while (nb && !b[0]) { b++; nb-=1; v++; }
498 28418985 : if (na < nb) swapspec(a,b, na,nb);
499 28418985 : if (!nb) return pol0_F2x(0);
500 :
501 23945882 : av = avma;
502 23945882 : if (na == 1)
503 20094169 : return F2x_shiftip(av, F2x_mul1(*a,*b), v);
504 3851713 : if (na < F2x_MUL_KARATSUBA_LIMIT)
505 3819668 : return F2x_shiftip(av, F2x_mulspec_basecase(a, b, na, nb), v);
506 32045 : if (nb >= F2x_MUL_MULII_LIMIT)
507 132 : return F2x_shiftip(av, F2x_mulspec_mulii(a, b, na, nb), v);
508 31913 : i=(na>>1); n0=na-i; na=i;
509 31913 : a0=a+n0; n0a=n0;
510 31998 : while (n0a && !a[n0a-1]) n0a--;
511 :
512 31913 : if (nb > n0)
513 : {
514 : GEN b0,c1,c2;
515 : long n0b;
516 :
517 14817 : nb -= n0; b0 = b+n0; n0b = n0;
518 14824 : while (n0b && !b[n0b-1]) n0b--;
519 14817 : c = F2x_mulspec(a,b,n0a,n0b);
520 14817 : c0 = F2x_mulspec(a0,b0,na,nb);
521 :
522 14817 : c2 = F2x_addspec(a0,a,na,n0a);
523 14817 : c1 = F2x_addspec(b0,b,nb,n0b);
524 :
525 14817 : c1 = F2x_mul(c1,c2);
526 14817 : c2 = F2x_add(c0,c);
527 :
528 14817 : c2 = F2x_add(c1,c2);
529 14817 : c0 = F2x_addshift(c0,c2,n0);
530 : }
531 : else
532 : {
533 17096 : c = F2x_mulspec(a,b,n0a,nb);
534 17274 : c0 = F2x_mulspec(a0,b,na,nb);
535 : }
536 32091 : c0 = F2x_addshift(c0,c,n0);
537 32091 : return F2x_shiftip(av,c0, v);
538 : }
539 :
540 : GEN
541 28354845 : F2x_mul(GEN x, GEN y)
542 : {
543 28354845 : GEN z = F2x_mulspec(x+2,y+2, lgpol(x),lgpol(y));
544 28355092 : z[1] = x[1]; return z;
545 : }
546 :
547 : GEN
548 9100207 : F2x_sqr(GEN x)
549 : {
550 9100207 : const ulong sq[]={0,1,4,5,16,17,20,21,64,65,68,69,80,81,84,85};
551 : long i,ii,j,jj;
552 9100207 : long lx=lg(x), lz=2+((lx-2)<<1);
553 : GEN z;
554 9100207 : z = cgetg(lz, t_VECSMALL); z[1]=x[1];
555 18327460 : for (j=2,jj=2;j<lx;j++,jj++)
556 : {
557 9201372 : ulong x1=((ulong)x[j]&HIGHMASK)>>BITS_IN_HALFULONG;
558 9201372 : ulong x2=(ulong)x[j]&LOWMASK;
559 9201372 : z[jj]=0;
560 9201372 : if (x2)
561 76880567 : for(i=0,ii=0;i<BITS_IN_HALFULONG;i+=4,ii+=8)
562 67745343 : z[jj]|=sq[(x2>>i)&15UL]<<ii;
563 9201372 : z[++jj]=0;
564 9201372 : if (x1)
565 6336343 : for(i=0,ii=0;i<BITS_IN_HALFULONG;i+=4,ii+=8)
566 5515896 : z[jj]|=sq[(x1>>i)&15UL]<<ii;
567 : }
568 9126088 : return F2x_renormalize(z, lz);
569 : }
570 :
571 : static GEN
572 175557 : F2x_pow2n(GEN x, long n)
573 : {
574 : long i;
575 526720 : for(i=1;i<=n;i++)
576 351072 : x = F2x_sqr(x);
577 175648 : return x;
578 : }
579 :
580 : int
581 35562 : F2x_issquare(GEN x)
582 : {
583 35562 : const ulong mask = (ULONG_MAX/3UL)*2;
584 35562 : ulong i, lx = lg(x);
585 71124 : for (i=2; i<lx; i++)
586 35562 : if ((x[i]&mask)) return 0;
587 35562 : return 1;
588 : }
589 :
590 : /* Assume x is a perfect square */
591 : GEN
592 248745 : F2x_sqrt(GEN x)
593 : {
594 248745 : const ulong sq[]={0,1,4,5,2,3,6,7,8,9,12,13,10,11,14,15};
595 : long i,ii,j,jj;
596 248745 : long lx=lg(x), lz=2+((lx-1)>>1);
597 : GEN z;
598 248745 : z = cgetg(lz, t_VECSMALL); z[1]=x[1];
599 497543 : for (j=2,jj=2;jj<lz;j++,jj++)
600 : {
601 248790 : ulong x2=x[j++];
602 248790 : z[jj]=0;
603 248790 : if (x2)
604 2096899 : for(i=0,ii=0;ii<BITS_IN_HALFULONG;i+=8,ii+=4)
605 : {
606 1848120 : ulong rl = (x2>>i)&15UL, rh = (x2>>(i+4))&15UL;
607 1848120 : z[jj]|=sq[rl|(rh<<1)]<<ii;
608 : }
609 248790 : if (j<lx)
610 : {
611 357 : x2 = x[j];
612 357 : if (x2)
613 2286 : for(i=0,ii=0;ii<BITS_IN_HALFULONG;i+=8,ii+=4)
614 : {
615 1944 : ulong rl = (x2>>i)&15UL, rh = (x2>>(i+4))&15UL;
616 1944 : z[jj]|=(sq[rl|(rh<<1)]<<ii)<<BITS_IN_HALFULONG;
617 : }
618 : }
619 : }
620 248753 : return F2x_renormalize(z, lz);
621 : }
622 :
623 : static GEN
624 1108 : F2x_shiftneg(GEN y, ulong d)
625 : {
626 1108 : long db, dl=dvmdsBIL(d, &db);
627 1108 : long i, ly = lg(y), lx = ly-dl;
628 : GEN x;
629 1108 : if (lx <= 2) return zero_F2x(y[1]);
630 1092 : x = cgetg(lx, t_VECSMALL);
631 1092 : x[1] = y[1];
632 1092 : if (db)
633 : {
634 1092 : ulong dc=BITS_IN_LONG-db;
635 1092 : ulong r=0;
636 2184 : for(i=lx-1; i>=2; i--)
637 : {
638 1092 : x[i] = (((ulong)y[i+dl])>>db)|r;
639 1092 : r = ((ulong)y[i+dl])<<dc;
640 : }
641 : }
642 : else
643 0 : for(i=2; i<lx; i++)
644 0 : x[i] = y[i+dl];
645 1092 : return F2x_renormalize(x,lx);
646 : }
647 :
648 : static GEN
649 274944 : F2x_shiftpos(GEN y, ulong d)
650 : {
651 274944 : long db, dl=dvmdsBIL(d, &db);
652 274920 : long i, ly = lg(y), lx = ly+dl+(!!db);
653 274920 : GEN x = cgetg(lx, t_VECSMALL);
654 274978 : x[1] = y[1]; for(i=0; i<dl; i++) x[i+2] = 0;
655 274887 : if (db)
656 : {
657 274843 : ulong dc=BITS_IN_LONG-db;
658 274843 : ulong r=0;
659 554052 : for(i=2; i<ly; i++)
660 : {
661 279209 : x[i+dl] = (((ulong)y[i])<<db)|r;
662 279209 : r = ((ulong)y[i])>>dc;
663 : }
664 274843 : x[i+dl] = r;
665 : }
666 : else
667 58 : for(i=2; i<ly; i++)
668 14 : x[i+dl] = y[i];
669 274887 : return F2x_renormalize(x,lx);
670 : }
671 :
672 : GEN
673 276037 : F2x_shift(GEN y, long d)
674 : {
675 276037 : return d<0 ? F2x_shiftneg(y,-d): F2x_shiftpos(y,d);
676 : }
677 :
678 : #define F2x_recip2(pk,m) u = ((u&m)<<pk)|((u&(~m))>>pk);
679 : #define F2x_recipu(pk) F2x_recip2(pk,((~0UL)/((1UL<<pk)+1)))
680 :
681 : static ulong
682 42 : F2x_recip1(ulong u)
683 : {
684 42 : u = (u<<BITS_IN_HALFULONG)|(u>>BITS_IN_HALFULONG);
685 : #ifdef LONG_IS_64BIT
686 36 : F2x_recipu(16);
687 : #endif
688 42 : F2x_recipu(8);
689 42 : F2x_recipu(4);
690 42 : F2x_recipu(2);
691 42 : F2x_recipu(1);
692 42 : return u;
693 : }
694 :
695 : static GEN
696 0 : F2x_recip_raw(GEN x)
697 : {
698 : long i, l;
699 0 : GEN y = cgetg_copy(x,&l);
700 0 : y[1] = x[1];
701 0 : for (i=0; i<l-2; i++)
702 0 : uel(y,l-1-i) = F2x_recip1(uel(x,2+i));
703 0 : return y;
704 : }
705 :
706 : GEN
707 0 : F2x_recip(GEN x)
708 : {
709 0 : long lb = remsBIL(F2x_degree(x)+1);
710 0 : GEN y = F2x_recip_raw(x);
711 0 : if (lb) y = F2x_shiftneg(y,BITS_IN_LONG-lb);
712 0 : return y;
713 : }
714 :
715 : GEN
716 83 : F2xn_red(GEN f, long n)
717 : {
718 : GEN g;
719 : long i, dl, db, l;
720 83 : if (F2x_degree(f) < n) return zv_copy(f);
721 0 : dl = dvmdsBIL(n, &db); l = 2 + dl + (db>0);
722 0 : g = cgetg(l, t_VECSMALL);
723 0 : g[1] = f[1];
724 0 : for (i=2; i<l; i++)
725 0 : uel(g,i) = uel(f,i);
726 0 : if (db) uel(g,l-1) = uel(f,l-1)&((1UL<<db)-1);
727 0 : return F2x_renormalize(g, l);
728 : }
729 :
730 : static GEN
731 46 : F2xn_mul(GEN a, GEN b, long n) { return F2xn_red(F2x_mul(a, b), n); }
732 :
733 : static ulong
734 42 : F2xn_inv_basecase1(ulong x)
735 : {
736 : ulong u, v, w;
737 : long i;
738 42 : u = x>>1;
739 42 : v = (u&1UL)|2UL;
740 42 : w = u&v; w ^= w >> 1; v = (w&1UL)|(v<<1);
741 42 : w = u&v; w ^= w >> 2; w ^= w >> 1; v = (w&1UL)|(v<<1);
742 42 : w = u&v; w ^= w >> 2; w ^= w >> 1; v = (w&1UL)|(v<<1);
743 210 : for (i=1;i<=4;i++)
744 168 : { w = u&v; w ^= w >> 4; w ^= w >> 2; w ^= w >> 1; v = (w&1UL)|(v<<1); }
745 378 : for (i=1;i<=8;i++)
746 336 : { w = u&v; w ^= w >> 8; w ^= w >> 4; w ^= w >> 2; w ^= w >> 1;
747 336 : v = (w&1UL)|(v<<1); }
748 714 : for (i=1;i<=16;i++)
749 672 : { w = u&v; w ^= w >> 16; w ^= w >> 8; w ^= w >> 4; w ^= w >> 2; w ^= w >> 1;
750 672 : v = (w&1UL)|(v<<1); }
751 : #ifdef LONG_IS_64BIT
752 1188 : for (i=1; i<=32; i++)
753 1152 : { w = u&v; w ^= w >> 32; w ^= w >> 16; w ^= w >> 8; w ^= w >> 4; w ^= w >> 2;
754 1152 : w ^= w >> 1; v = (w&1UL)|(v<<1); }
755 : #endif
756 42 : return (F2x_recip1(v)<<1) | 1UL;
757 : }
758 :
759 : static GEN
760 42 : F2xn_inv1(GEN v, long e)
761 : {
762 42 : ulong mask = e==BITS_IN_LONG ? -1UL: ((1UL<<e)-1);
763 42 : return mkvecsmall2(v[1],F2xn_inv_basecase1(uel(v,2))&mask);
764 : }
765 :
766 : static GEN
767 28 : F2xn_div1(GEN g, GEN f, long e)
768 : {
769 28 : GEN fi = F2xn_inv1(f, e);
770 28 : return g ? F2xn_mul(g, fi, e): fi;
771 : }
772 :
773 : GEN
774 42 : F2xn_div(GEN g, GEN f, long e)
775 : {
776 42 : pari_sp av = avma, av2;
777 : ulong mask;
778 : GEN W;
779 42 : long n=1;
780 42 : if (lg(f)<=2) pari_err_INV("Flxn_inv",f);
781 42 : if (e <= BITS_IN_LONG) return F2xn_div1(g, f, e);
782 14 : W = F2xn_inv1(f, BITS_IN_LONG);
783 14 : mask = quadratic_prec_mask(divsBIL(e+BITS_IN_LONG-1));
784 14 : n = BITS_IN_LONG;
785 14 : av2 = avma;
786 30 : for (;mask>1;)
787 : {
788 : GEN u, fr;
789 16 : long n2 = n;
790 16 : n<<=1; if (mask & 1) n--;
791 16 : mask >>= 1;
792 16 : fr = F2xn_red(f, n);
793 16 : if (mask>1 || !g)
794 : {
795 9 : u = F2x_shift(F2xn_mul(W, fr, n), -n2);
796 9 : W = F2x_add(W, F2x_shift(F2xn_mul(u, W, n-n2), n2));
797 : } else
798 : {
799 7 : GEN y = F2xn_mul(g, W, n), yt = F2xn_red(y, n-n2);
800 7 : u = F2xn_mul(yt, F2x_shift(F2xn_mul(fr, W, n), -n2), n-n2);
801 7 : W = F2x_add(y, F2x_shift(u, n2));
802 : }
803 16 : if (gc_needed(av2,2))
804 : {
805 0 : if(DEBUGMEM>1) pari_warn(warnmem,"F2xn_inv, e = %ld", n);
806 0 : W = gc_upto(av2, W);
807 : }
808 : }
809 14 : return gc_upto(av, F2xn_red(W,e));
810 : }
811 :
812 : GEN
813 28 : F2xn_inv(GEN f, long e)
814 28 : { return F2xn_div(NULL, f, e); }
815 :
816 : GEN
817 218673 : F2x_get_red(GEN T)
818 : {
819 218673 : return T;
820 : }
821 :
822 : /* separate from F2x_divrem for maximal speed. */
823 : GEN
824 48969353 : F2x_rem(GEN x, GEN y)
825 : {
826 : long dx,dy;
827 48969353 : long lx=lg(x);
828 48969353 : dy = F2x_degree(y); if (!dy) return pol0_F2x(x[1]);
829 46363739 : dx = F2x_degree_lg(x,lx);
830 46331800 : x = F2x_copy(x);
831 159360916 : while (dx>=dy)
832 : {
833 113126763 : F2x_addshiftip(x,y,dx-dy);
834 115894003 : while (lx>2 && x[lx-1]==0) lx--;
835 113109524 : dx = F2x_degree_lg(x,lx);
836 : }
837 46234153 : return F2x_renormalize(x, lx);
838 : }
839 :
840 : GEN
841 11707335 : F2x_divrem(GEN x, GEN y, GEN *pr)
842 : {
843 11707335 : long dx, dy, dz, lx = lg(x), vs = x[1];
844 : GEN z;
845 :
846 11707335 : dy = F2x_degree(y);
847 11706573 : if (dy<0) pari_err_INV("F2x_divrem",y);
848 11706671 : if (pr == ONLY_REM) return F2x_rem(x, y);
849 11706671 : if (!dy)
850 : {
851 2357587 : z = F2x_copy(x);
852 2357558 : if (pr && pr != ONLY_DIVIDES) *pr = pol0_F2x(vs);
853 2357558 : return z;
854 : }
855 9349084 : dx = F2x_degree_lg(x,lx);
856 9350097 : dz = dx-dy;
857 9350097 : if (dz < 0)
858 : {
859 14 : if (pr == ONLY_DIVIDES) return dx < 0? F2x_copy(x): NULL;
860 14 : z = pol0_F2x(vs);
861 14 : if (pr) *pr = F2x_copy(x);
862 14 : return z;
863 : }
864 9350083 : z = zero_zv(lg(x)-lg(y)+2); z[1] = vs;
865 9351223 : x = F2x_copy(x);
866 30601716 : while (dx>=dy)
867 : {
868 21252073 : F2x_set(z,dx-dy);
869 21253538 : F2x_addshiftip(x,y,dx-dy);
870 22809411 : while (lx>2 && x[lx-1]==0) lx--;
871 21243633 : dx = F2x_degree_lg(x,lx);
872 : }
873 9349643 : z = F2x_renormalize(z, lg(z));
874 9350745 : if (!pr) { cgiv(x); return z; }
875 8095009 : x = F2x_renormalize(x, lx);
876 8095010 : if (pr == ONLY_DIVIDES) {
877 0 : if (lg(x) == 2) { cgiv(x); return z; }
878 0 : return gc_NULL((pari_sp)(z + lg(z)));
879 : }
880 8095010 : *pr = x; return z;
881 : }
882 :
883 : long
884 35365 : F2x_valrem(GEN x, GEN *Z)
885 : {
886 35365 : long v, v2, i, l=lg(x);
887 : GEN y;
888 35365 : if (l==2) { *Z = F2x_copy(x); return LONG_MAX; }
889 35368 : for (i=2; i<l && x[i]==0; i++) /*empty*/;
890 35365 : v = i-2;
891 35365 : v2 = (i < l)? vals(x[i]): 0;
892 35367 : if (v+v2 == 0) { *Z = x; return 0; }
893 11275 : l -= i-2;
894 11275 : y = cgetg(l, t_VECSMALL); y[1] = x[1];
895 11275 : if (v2 == 0)
896 6 : for (i=2; i<l; i++) uel(y,i) = uel(x,i+v);
897 11272 : else if (l == 3)
898 11251 : y[2] = uel(x,2+v) >> v2;
899 : else
900 : {
901 21 : const ulong sh = BITS_IN_LONG - v2;
902 21 : ulong r = uel(x,2+v);
903 42 : for (i=3; i<l; i++)
904 : {
905 21 : uel(y,i-1) = (uel(x,i+v)<< sh) | (r >> v2);
906 21 : r = uel(x,i+v);
907 : }
908 21 : uel(y,l-1) = r >> v2;
909 21 : (void)F2x_renormalize(y,l);
910 : }
911 11275 : *Z = y; return (v << TWOPOTBITS_IN_LONG) + v2;
912 : }
913 :
914 : GEN
915 0 : F2x_deflate(GEN x, long d)
916 : {
917 : GEN y;
918 0 : long i,id, dy, dx = F2x_degree(x);
919 0 : if (d <= 1) return F2x_copy(x);
920 0 : if (dx < 0) return F2x_copy(x);
921 0 : dy = dx/d; /* dy+1 coefficients + 1 extra word for variable */
922 0 : y = zero_zv(nbits2lg(dy+1)-1); y[1] = x[1];
923 0 : for (i=id=0; i<=dy; i++,id+=d)
924 0 : if (F2x_coeff(x,id)) F2x_set(y, i);
925 0 : return y;
926 : }
927 :
928 : /* write p(X) = e(X^2) + Xo(X^2), shallow function */
929 : void
930 61295 : F2x_even_odd(GEN p, GEN *pe, GEN *po)
931 : {
932 61295 : long n = F2x_degree(p), n0, n1, i;
933 : GEN p0, p1;
934 :
935 61295 : if (n <= 0) { *pe = F2x_copy(p); *po = pol0_F2x(p[1]); return; }
936 :
937 56983 : n0 = (n>>1)+1; n1 = n+1 - n0; /* n1 <= n0 <= n1+1 */
938 56983 : p0 = zero_zv(nbits2lg(n0+1)-1); p0[1] = p[1];
939 56983 : p1 = zero_zv(nbits2lg(n1+1)-1); p1[1] = p[1];
940 2115918 : for (i=0; i<n1; i++)
941 : {
942 2058931 : if (F2x_coeff(p,i<<1)) F2x_set(p0,i);
943 2058950 : if (F2x_coeff(p,1+(i<<1))) F2x_set(p1,i);
944 : }
945 56987 : if (n1 != n0 && F2x_coeff(p,i<<1)) F2x_set(p0,i);
946 56987 : *pe = F2x_renormalize(p0,lg(p0));
947 56984 : *po = F2x_renormalize(p1,lg(p1));
948 : }
949 :
950 : GEN
951 1286611 : F2x_deriv(GEN z)
952 : {
953 1286611 : const ulong mask = ULONG_MAX/3UL;
954 1286611 : long i,l = lg(z);
955 1286611 : GEN x = cgetg(l, t_VECSMALL); x[1] = z[1];
956 2579843 : for (i=2; i<l; i++) x[i] = (((ulong)z[i])>>1)&mask;
957 1286562 : return F2x_renormalize(x,l);
958 : }
959 :
960 : GEN
961 3860796 : F2x_gcd(GEN a, GEN b)
962 : {
963 3860796 : pari_sp av = avma;
964 3860796 : if (lg(b) > lg(a)) swap(a, b);
965 24492749 : while (lgpol(b))
966 : {
967 20384989 : GEN c = F2x_rem(a,b);
968 20631953 : a = b; b = c;
969 20631953 : if (gc_needed(av,2))
970 : {
971 0 : if (DEBUGMEM>1) pari_warn(warnmem,"F2x_gcd (d = %ld)",F2x_degree(c));
972 0 : (void)gc_all(av,2, &a,&b);
973 : }
974 : }
975 3850643 : if (gc_needed(av,2)) a = gc_leaf(av, a);
976 3850643 : return a;
977 : }
978 :
979 : GEN
980 2042416 : F2x_extgcd(GEN a, GEN b, GEN *ptu, GEN *ptv)
981 : {
982 2042416 : pari_sp av=avma;
983 : GEN u,v,d,d1,v1;
984 2042416 : long vx = a[1];
985 2042416 : d = a; d1 = b;
986 2042416 : v = pol0_F2x(vx); v1 = pol1_F2x(vx);
987 12164531 : while (lgpol(d1))
988 : {
989 10122114 : GEN r, q = F2x_divrem(d,d1, &r);
990 10122114 : v = F2x_add(v,F2x_mul(q,v1));
991 10122115 : u=v; v=v1; v1=u;
992 10122115 : u=r; d=d1; d1=u;
993 10122115 : if (gc_needed(av,2))
994 : {
995 0 : if (DEBUGMEM>1) pari_warn(warnmem,"F2x_extgcd (d = %ld)",F2x_degree(d));
996 0 : (void)gc_all(av,5, &d,&d1,&u,&v,&v1);
997 : }
998 : }
999 2042415 : if (ptu) *ptu = F2x_div(F2x_add(d, F2x_mul(b,v)), a);
1000 2042415 : *ptv = v;
1001 2042415 : if (gc_needed(av,2)) (void)gc_all(av,ptu?3:2,&d,ptv,ptu);
1002 2042415 : return d;
1003 : }
1004 :
1005 : static GEN
1006 960 : F2x_halfgcd_i(GEN a, GEN b)
1007 : {
1008 960 : pari_sp av=avma;
1009 : GEN u,u1,v,v1;
1010 960 : long vx = a[1];
1011 960 : long n = (F2x_degree(a)+1)>>1;
1012 960 : u1 = v = pol0_F2x(vx);
1013 960 : u = v1 = pol1_F2x(vx);
1014 15275 : while (F2x_degree(b)>=n)
1015 : {
1016 14315 : GEN r, q = F2x_divrem(a,b, &r);
1017 14315 : a = b; b = r; swap(u,u1); swap(v,v1);
1018 14315 : u1 = F2x_add(u1, F2x_mul(u, q));
1019 14315 : v1 = F2x_add(v1, F2x_mul(v, q));
1020 14315 : if (gc_needed(av,2))
1021 : {
1022 0 : if (DEBUGMEM>1) pari_warn(warnmem,"F2x_halfgcd (d = %ld)",F2x_degree(b));
1023 0 : (void)gc_all(av,6, &a,&b,&u1,&v1,&u,&v);
1024 : }
1025 : }
1026 960 : return gc_GEN(av, mkmat22(u,v,u1,v1));
1027 : }
1028 :
1029 : GEN
1030 960 : F2x_halfgcd(GEN x, GEN y)
1031 : {
1032 : pari_sp av;
1033 : GEN M,q,r;
1034 960 : if (F2x_degree(y)<F2x_degree(x)) return F2x_halfgcd_i(x,y);
1035 960 : av = avma;
1036 960 : q = F2x_divrem(y,x,&r);
1037 960 : M = F2x_halfgcd_i(x,r);
1038 960 : gcoeff(M,1,1) = F2x_add(gcoeff(M,1,1), F2x_mul(q, gcoeff(M,1,2)));
1039 960 : gcoeff(M,2,1) = F2x_add(gcoeff(M,2,1), F2x_mul(q, gcoeff(M,2,2)));
1040 960 : return gc_GEN(av, M);
1041 : }
1042 :
1043 : GEN
1044 10047293 : F2xq_mul(GEN x,GEN y,GEN pol)
1045 : {
1046 10047293 : GEN z = F2x_mul(x,y);
1047 10047571 : return F2x_rem(z,pol);
1048 : }
1049 :
1050 : GEN
1051 8754266 : F2xq_sqr(GEN x,GEN pol)
1052 : {
1053 8754266 : GEN z = F2x_sqr(x);
1054 8781146 : return F2x_rem(z,pol);
1055 : }
1056 :
1057 : GEN
1058 2042416 : F2xq_invsafe(GEN x, GEN T)
1059 : {
1060 2042416 : GEN V, z = F2x_extgcd(get_F2x_mod(T), x, NULL, &V);
1061 2042415 : if (F2x_degree(z)) return NULL;
1062 2042381 : return V;
1063 : }
1064 :
1065 : GEN
1066 2042409 : F2xq_inv(GEN x,GEN T)
1067 : {
1068 2042409 : pari_sp av=avma;
1069 2042409 : GEN U = F2xq_invsafe(x, T);
1070 2042409 : if (!U) pari_err_INV("F2xq_inv", F2x_to_ZX(x));
1071 2042374 : return gc_leaf(av, U);
1072 : }
1073 :
1074 : GEN
1075 558155 : F2xq_div(GEN x,GEN y,GEN T)
1076 : {
1077 558155 : pari_sp av = avma;
1078 558155 : return gc_leaf(av, F2xq_mul(x,F2xq_inv(y,T),T));
1079 : }
1080 :
1081 : static GEN
1082 581987 : _F2xq_red(void *E, GEN x) { return F2x_rem(x, (GEN)E); }
1083 : static GEN
1084 1692196 : _F2xq_add(void *E, GEN x, GEN y) { (void)E; return F2x_add(x,y); }
1085 :
1086 : static GEN
1087 2079729 : _F2xq_cmul(void *E, GEN P, long a, GEN x)
1088 : {
1089 2079729 : GEN pol = (GEN) E;
1090 2079729 : return F2x_coeff(P,a) ? x: pol0_F2x(pol[1]);
1091 : }
1092 : static GEN
1093 1211167 : _F2xq_sqr(void *E, GEN x) { return F2xq_sqr(x, (GEN) E); }
1094 : static GEN
1095 2183038 : _F2xq_mul(void *E, GEN x, GEN y) { return F2xq_mul(x,y, (GEN) E); }
1096 :
1097 : static GEN
1098 925059 : _F2xq_one(void *E)
1099 : {
1100 925059 : GEN pol = (GEN) E;
1101 925059 : return pol1_F2x(pol[1]);
1102 : }
1103 : static GEN
1104 259292 : _F2xq_zero(void *E)
1105 : {
1106 259292 : GEN pol = (GEN) E;
1107 259292 : return pol0_F2x(pol[1]);
1108 : }
1109 :
1110 : GEN
1111 2441818 : F2xq_pow(GEN x, GEN n, GEN pol)
1112 : {
1113 2441818 : pari_sp av=avma;
1114 : GEN y;
1115 :
1116 2441818 : if (!signe(n)) return pol1_F2x(x[1]);
1117 2435280 : if (is_pm1(n)) /* +/- 1 */
1118 1842788 : return (signe(n) < 0)? F2xq_inv(x,pol): F2x_copy(x);
1119 :
1120 592492 : if (signe(n) < 0) x = F2xq_inv(x,pol);
1121 592492 : y = gen_pow_i(x, n, (void*)pol, &_F2xq_sqr, &_F2xq_mul);
1122 592492 : return gc_GEN(av, y);
1123 : }
1124 :
1125 : GEN
1126 49 : F2xq_powu(GEN x, ulong n, GEN pol)
1127 : {
1128 49 : pari_sp av=avma;
1129 : GEN y;
1130 49 : switch(n)
1131 : {
1132 0 : case 0: return pol1_F2x(x[1]);
1133 7 : case 1: return F2x_copy(x);
1134 14 : case 2: return F2xq_sqr(x,pol);
1135 : }
1136 28 : y = gen_powu_i(x, n, (void*)pol, &_F2xq_sqr, &_F2xq_mul);
1137 28 : return gc_GEN(av, y);
1138 : }
1139 :
1140 : GEN
1141 14 : F2xq_pow_init(GEN x, GEN n, long k, GEN T)
1142 : {
1143 14 : return gen_pow_init(x, n, k, (void*)T, &_F2xq_sqr, &_F2xq_mul);
1144 : }
1145 :
1146 : GEN
1147 5244 : F2xq_pow_table(GEN R, GEN n, GEN T)
1148 : {
1149 5244 : return gen_pow_table(R, n, (void*)T, &_F2xq_one, &_F2xq_mul);
1150 : }
1151 :
1152 : /* generates the list of powers of x of degree 0,1,2,...,l*/
1153 : GEN
1154 364154 : F2xq_powers(GEN x, long l, GEN T)
1155 : {
1156 364154 : int use_sqr = 2*F2x_degree(x) >= get_F2x_degree(T);
1157 364152 : return gen_powers(x, l, use_sqr, (void*)T, &_F2xq_sqr, &_F2xq_mul, &_F2xq_one);
1158 : }
1159 :
1160 : GEN
1161 234920 : F2xq_matrix_pow(GEN y, long n, long m, GEN P)
1162 : {
1163 234920 : return F2xV_to_F2m(F2xq_powers(y,m-1,P),n);
1164 : }
1165 :
1166 : GEN
1167 660137 : F2x_Frobenius(GEN T)
1168 : {
1169 660137 : return F2xq_sqr(polx_F2x(get_F2x_var(T)), T);
1170 : }
1171 :
1172 : GEN
1173 234920 : F2x_matFrobenius(GEN T)
1174 : {
1175 234920 : long n = get_F2x_degree(T);
1176 234920 : return F2xq_matrix_pow(F2x_Frobenius(T), n, n, T);
1177 : }
1178 :
1179 : static struct bb_algebra F2xq_algebra = { _F2xq_red, _F2xq_add, _F2xq_add,
1180 : _F2xq_mul, _F2xq_sqr, _F2xq_one, _F2xq_zero};
1181 :
1182 : GEN
1183 610484 : F2x_F2xqV_eval(GEN Q, GEN x, GEN T)
1184 : {
1185 610484 : long d = F2x_degree(Q);
1186 610484 : return gen_bkeval_powers(Q,d,x,(void*)T,&F2xq_algebra,_F2xq_cmul);
1187 : }
1188 :
1189 : GEN
1190 44738 : F2x_F2xq_eval(GEN Q, GEN x, GEN T)
1191 : {
1192 44738 : long d = F2x_degree(Q);
1193 44738 : int use_sqr = 2*F2x_degree(x) >= get_F2x_degree(T);
1194 44738 : return gen_bkeval(Q, d, x, use_sqr, (void*)T, &F2xq_algebra, _F2xq_cmul);
1195 : }
1196 :
1197 : static GEN
1198 29320 : F2xq_autpow_sqr(void * T, GEN x) { return F2x_F2xq_eval(x, x, (GEN) T); }
1199 :
1200 : static GEN
1201 14690 : F2xq_autpow_mul(void * T, GEN x, GEN y) { return F2x_F2xq_eval(x, y, (GEN) T); }
1202 :
1203 : GEN
1204 19253 : F2xq_autpow(GEN x, long n, GEN T)
1205 : {
1206 19253 : if (n==0) return F2x_rem(polx_F2x(x[1]), T);
1207 19253 : if (n==1) return F2x_rem(x, T);
1208 19253 : return gen_powu(x,n,(void*)T,F2xq_autpow_sqr,F2xq_autpow_mul);
1209 : }
1210 :
1211 : ulong
1212 456809 : F2xq_trace(GEN x, GEN T)
1213 : {
1214 456809 : pari_sp av = avma;
1215 456809 : long n = get_F2x_degree(T)-1;
1216 456809 : GEN z = F2xq_mul(x, F2x_deriv(get_F2x_mod(T)), T);
1217 456809 : return gc_ulong(av, F2x_degree(z) < n ? 0 : 1);
1218 : }
1219 :
1220 : GEN
1221 7 : F2xq_conjvec(GEN x, GEN T)
1222 : {
1223 7 : long i, l = 1+get_F2x_degree(T);
1224 7 : GEN z = cgetg(l,t_COL);
1225 7 : gel(z,1) = F2x_copy(x);
1226 140 : for (i=2; i<l; i++) gel(z,i) = F2xq_sqr(gel(z,i-1), T);
1227 7 : return z;
1228 : }
1229 :
1230 : static GEN
1231 2398561 : _F2xq_pow(void *data, GEN x, GEN n)
1232 : {
1233 2398561 : GEN pol = (GEN) data;
1234 2398561 : return F2xq_pow(x,n, pol);
1235 : }
1236 :
1237 : static GEN
1238 9639 : _F2xq_rand(void *data)
1239 : {
1240 9639 : pari_sp av=avma;
1241 9639 : GEN pol = (GEN) data;
1242 9639 : long d = F2x_degree(pol);
1243 : GEN z;
1244 : do
1245 : {
1246 9862 : set_avma(av);
1247 9862 : z = random_F2x(d,pol[1]);
1248 9862 : } while (lgpol(z)==0);
1249 9639 : return z;
1250 : }
1251 :
1252 : static GEN F2xq_easylog(void* E, GEN a, GEN g, GEN ord);
1253 :
1254 : static const struct bb_group F2xq_star={_F2xq_mul,_F2xq_pow,_F2xq_rand,hash_GEN,F2x_equal,F2x_equal1,F2xq_easylog};
1255 :
1256 : GEN
1257 399 : F2xq_order(GEN a, GEN ord, GEN T)
1258 : {
1259 399 : return gen_order(a,ord,(void*)T,&F2xq_star);
1260 : }
1261 :
1262 : static long
1263 271996 : F2x_is_smooth_squarefree(GEN f, long r)
1264 : {
1265 271996 : pari_sp av = avma;
1266 271996 : long i, df = F2x_degree(f);
1267 : GEN sx, a;
1268 272057 : if (!df) return 1;
1269 267144 : a = sx = polx_F2x(f[1]);
1270 267123 : for(i = 1;; i++)
1271 2248495 : {
1272 : long dg;
1273 : GEN g;
1274 2515618 : a = F2xq_sqr(a, f);
1275 2490984 : if (F2x_equal(a, sx)) return gc_long(av,1);
1276 2437477 : if (i==r) return gc_long(av,0);
1277 2258303 : g = F2x_gcd(f, F2x_add(a,sx));
1278 2272341 : dg = F2x_degree(g);
1279 2271432 : if (dg == df) return gc_long(av,1);
1280 2249876 : if (dg) { f = F2x_div(f, g); df -= dg; a = F2x_rem(a, f); }
1281 : }
1282 : }
1283 :
1284 : static long
1285 236724 : F2x_is_smooth(GEN g, long r)
1286 : {
1287 236724 : if (lgpol(g)==0) return 0;
1288 : while (1)
1289 35574 : {
1290 272277 : GEN f = F2x_gcd(g, F2x_deriv(g));
1291 272032 : if (!F2x_is_smooth_squarefree(F2x_div(g, f), r)) return 0;
1292 92967 : if (F2x_degree(f)==0) return 1;
1293 35502 : g = F2x_issquare(f) ? F2x_sqrt(f): f;
1294 : }
1295 : }
1296 :
1297 : static GEN
1298 14995 : F2x_factorel(GEN h)
1299 : {
1300 14995 : GEN F = F2x_factor(h);
1301 15000 : GEN F1 = gel(F, 1), F2 = gel(F, 2);
1302 15000 : long i, l1 = lg(F1)-1;
1303 15000 : GEN p2 = cgetg(l1+1, t_VECSMALL);
1304 15000 : GEN e2 = cgetg(l1+1, t_VECSMALL);
1305 70165 : for (i = 1; i <= l1; ++i)
1306 : {
1307 55165 : p2[i] = mael(F1, i, 2);
1308 55165 : e2[i] = F2[i];
1309 : }
1310 15000 : return mkmat2(p2, e2);
1311 : }
1312 :
1313 : static GEN
1314 27006 : mkF2(ulong x, long v) { return mkvecsmall2(v, x); }
1315 :
1316 : static GEN F2xq_log_Coppersmith_d(GEN W, GEN g, long r, long n, GEN T, GEN mo);
1317 :
1318 : static GEN
1319 71 : F2xq_log_from_rel(GEN W, GEN rel, long r, long n, GEN T, GEN m)
1320 : {
1321 71 : pari_sp av = avma;
1322 71 : long vT = get_F2x_var(T);
1323 71 : GEN F = gel(rel,1), E = gel(rel,2), o = gen_0;
1324 71 : long i, l = lg(F);
1325 595 : for(i=1; i<l; i++)
1326 : {
1327 524 : GEN R = gel(W, F[i]);
1328 524 : if (signe(R)==0) /* Already failed */
1329 0 : return NULL;
1330 524 : else if (signe(R)<0) /* Not yet tested */
1331 : {
1332 6 : setsigne(gel(W,F[i]),0);
1333 6 : R = F2xq_log_Coppersmith_d(W, mkF2(F[i],vT), r, n, T, m);
1334 6 : if (!R) return NULL;
1335 : }
1336 524 : o = Fp_add(o, mulis(R, E[i]), m);
1337 : }
1338 71 : return gc_INT(av, o);
1339 : }
1340 :
1341 : static GEN
1342 95 : F2xq_log_Coppersmith_d(GEN W, GEN g, long r, long n, GEN T, GEN mo)
1343 : {
1344 95 : pari_sp av = avma, av2;
1345 95 : long dT = get_F2x_degree(T), vT = get_F2x_var(T);
1346 95 : long dg = F2x_degree(g), k = r-1, m = maxss((dg-k)/2,0);
1347 95 : long i, j, l = dg-m, N;
1348 95 : GEN v = cgetg(k+m+1,t_MAT);
1349 95 : long h = dT>>n, d = dT-(h<<n);
1350 95 : GEN p1 = pol1_F2x(vT);
1351 95 : GEN R = F2x_add(F2x_shift(p1, dT), T);
1352 95 : GEN z = F2x_rem(F2x_shift(p1, h), g);
1353 1187 : for(i=1; i<=k+m; i++)
1354 : {
1355 1092 : gel(v,i) = F2x_to_F2v(F2x_shift(z,-l),m);
1356 1092 : z = F2x_rem(F2x_shift(z,1),g);
1357 : }
1358 95 : v = F2m_ker(v);
1359 1045 : for(i=1; i<=k; i++)
1360 950 : gel(v,i) = F2v_to_F2x(gel(v,i),vT);
1361 95 : N = 1<<k;
1362 95 : av2 = avma;
1363 38329 : for (i=1; i<N; i++)
1364 : {
1365 : GEN p,q,qh,a,b;
1366 38305 : set_avma(av2);
1367 38305 : q = pol0_F2x(vT);
1368 421355 : for(j=0; j<k; j++)
1369 383050 : if (i&(1UL<<j))
1370 180909 : q = F2x_add(q, gel(v,j+1));
1371 38305 : qh= F2x_shift(q,h);
1372 38305 : p = F2x_rem(qh,g);
1373 38305 : b = F2x_add(F2x_mul(R, F2x_pow2n(q, n)), F2x_shift(F2x_pow2n(p, n), d));
1374 38305 : if (lgpol(b)==0 || !F2x_is_smooth(b, r)) continue;
1375 71 : a = F2x_div(F2x_add(qh,p),g);
1376 71 : if (F2x_degree(F2x_gcd(a,q)) && F2x_degree(F2x_gcd(a,p))) continue;
1377 71 : if (!(lgpol(a)==0 || !F2x_is_smooth(a, r)))
1378 : {
1379 71 : GEN F = F2x_factorel(b);
1380 71 : GEN G = F2x_factorel(a);
1381 71 : GEN FG = vecsmall_concat(vecsmall_append(gel(F, 1), 2), gel(G, 1));
1382 71 : GEN E = vecsmall_concat(vecsmall_append(gel(F, 2), -d),
1383 71 : zv_z_mul(gel(G, 2),-(1L<<n)));
1384 71 : GEN R = famatsmall_reduce(mkmat2(FG, E));
1385 71 : GEN l = F2xq_log_from_rel(W, R, r, n, T, mo);
1386 71 : if (!l) continue;
1387 71 : l = Fp_div(l,int2n(n),mo);
1388 71 : if (dg <= r)
1389 : {
1390 7 : affii(l,gel(W,g[2]));
1391 7 : if (DEBUGLEVEL>1) err_printf("Found %lu\n", g[2]);
1392 : }
1393 71 : return gc_INT(av, l);
1394 : }
1395 : }
1396 24 : return gc_NULL(av);
1397 : }
1398 :
1399 : static GEN
1400 65 : F2xq_log_find_rel(GEN b, long r, GEN T, GEN *g, ulong *e)
1401 : {
1402 65 : pari_sp av = avma;
1403 : while (1)
1404 895 : {
1405 : GEN M;
1406 960 : *g = F2xq_mul(*g, b, T); (*e)++;
1407 960 : M = F2x_halfgcd(*g,T);
1408 960 : if (F2x_is_smooth(gcoeff(M,1,1), r))
1409 : {
1410 393 : GEN z = F2x_add(F2x_mul(gcoeff(M,1,1),*g), F2x_mul(gcoeff(M,1,2),T));
1411 393 : if (F2x_is_smooth(z, r))
1412 : {
1413 65 : GEN F = F2x_factorel(z);
1414 65 : GEN G = F2x_factorel(gcoeff(M,1,1));
1415 65 : GEN rel = mkmat2(vecsmall_concat(gel(F, 1),gel(G, 1)),
1416 65 : vecsmall_concat(gel(F, 2),zv_neg(gel(G, 2))));
1417 65 : return gc_all(av, 2, &rel, g);
1418 : }
1419 : }
1420 895 : if (gc_needed(av,2))
1421 : {
1422 0 : if (DEBUGMEM>1) pari_warn(warnmem,"F2xq_log_find_rel");
1423 0 : *g = gc_leaf(av, *g);
1424 : }
1425 : }
1426 : }
1427 :
1428 : static GEN
1429 28 : F2xq_log_Coppersmith_rec(GEN W, long r2, GEN a, long r, long n, GEN T, GEN m)
1430 : {
1431 28 : long vT = get_F2x_var(T);
1432 28 : GEN b = polx_F2x(vT);
1433 28 : ulong AV = 0;
1434 28 : GEN g = a, bad = pol0_F2x(vT);
1435 : pari_timer ti;
1436 : while(1)
1437 37 : {
1438 : long i, l;
1439 : GEN V, F, E, Ao;
1440 65 : timer_start(&ti);
1441 65 : V = F2xq_log_find_rel(b, r2, T, &g, &AV);
1442 65 : if (DEBUGLEVEL>1) timer_printf(&ti,"%ld-smooth element",r2);
1443 65 : F = gel(V,1); E = gel(V,2);
1444 65 : l = lg(F);
1445 65 : Ao = gen_0;
1446 480 : for(i=1; i<l; i++)
1447 : {
1448 452 : GEN Fi = mkF2(F[i], vT);
1449 : GEN R;
1450 452 : if (F2x_degree(Fi) <= r)
1451 : {
1452 351 : if (signe(gel(W,F[i]))==0)
1453 0 : break;
1454 351 : else if (signe(gel(W,F[i]))<0)
1455 : {
1456 1 : setsigne(gel(W,F[i]),0);
1457 1 : R = F2xq_log_Coppersmith_d(W,Fi,r,n,T,m);
1458 : } else
1459 350 : R = gel(W,F[i]);
1460 : }
1461 : else
1462 : {
1463 101 : if (F2x_equal(Fi,bad)) break;
1464 88 : R = F2xq_log_Coppersmith_d(W,Fi,r,n,T,m);
1465 88 : if (!R) bad = Fi;
1466 : }
1467 439 : if (!R) break;
1468 415 : Ao = Fp_add(Ao, mulis(R, E[i]), m);
1469 : }
1470 65 : if (i==l) return subiu(Ao,AV);
1471 : }
1472 : }
1473 :
1474 : /* Coppersmith:
1475 : T*X^e = X^(h*2^n)-R
1476 : (u*x^h + v)^(2^n) = u^(2^n)*X^(h*2^n)+v^(2^n)
1477 : (u*x^h + v)^(2^n) = u^(2^n)*R+v^(2^n)
1478 : */
1479 :
1480 : static GEN
1481 147539 : rel_Coppersmith(GEN u, GEN v, long h, GEN R, long r, long n, long d)
1482 : {
1483 : GEN b, F, G, M;
1484 147539 : GEN a = F2x_add(F2x_shift(u, h), v);
1485 147579 : if (!F2x_is_smooth(a, r)) return NULL;
1486 49486 : b = F2x_add(F2x_mul(R, F2x_pow2n(u, n)), F2x_shift(F2x_pow2n(v, n),d));
1487 49507 : if (!F2x_is_smooth(b, r)) return NULL;
1488 7361 : F = F2x_factorel(a);
1489 7364 : G = F2x_factorel(b);
1490 14728 : M = mkmat2(vecsmall_concat(gel(F, 1), vecsmall_append(gel(G, 1), 2)),
1491 14728 : vecsmall_concat(zv_z_mul(gel(F, 2),1UL<<n), vecsmall_append(zv_neg(gel(G, 2)),d)));
1492 7364 : return famatsmall_reduce(M);
1493 : }
1494 :
1495 : GEN
1496 2044 : F2xq_log_Coppersmith_worker(GEN u, long i, GEN V, GEN R)
1497 : {
1498 2044 : long r = V[1], h = V[2], n = V[3], d = V[4];
1499 2044 : pari_sp ltop = avma;
1500 2044 : GEN v = mkF2(0,u[1]);
1501 2042 : GEN L = cgetg(2*i+1, t_VEC);
1502 2041 : pari_sp av = avma;
1503 : long j;
1504 2041 : long nbtest=0, rel = 1;
1505 148132 : for(j=1; j<=i; j++)
1506 : {
1507 146086 : v[2] = j;
1508 146086 : set_avma(av);
1509 146090 : if (F2x_degree(F2x_gcd(u,v))==0)
1510 : {
1511 73818 : GEN z = rel_Coppersmith(u, v, h, R, r, n, d);
1512 73827 : nbtest++;
1513 73827 : if (z) { gel(L, rel++) = z; av = avma; }
1514 73827 : if (i==j) continue;
1515 73813 : z = rel_Coppersmith(v, u, h, R, r, n, d);
1516 73812 : nbtest++;
1517 73812 : if (z) { gel(L, rel++) = z; av = avma; }
1518 : }
1519 : }
1520 2046 : setlg(L,rel);
1521 2046 : return gc_GEN(ltop, mkvec2(stoi(nbtest), L));
1522 : }
1523 :
1524 : static GEN
1525 14 : F2xq_log_Coppersmith(long nbrel, long r, long n, GEN T)
1526 : {
1527 14 : long dT = get_F2x_degree(T), vT = get_F2x_var(T);
1528 14 : long h = dT>>n, d = dT-(h<<n);
1529 14 : GEN R = F2x_add(F2x_shift(pol1_F2x(vT), dT), T);
1530 14 : GEN u = mkF2(0,vT);
1531 14 : long rel = 1, nbtest = 0;
1532 14 : GEN M = cgetg(nbrel+1, t_VEC);
1533 14 : long i = 0;
1534 14 : GEN worker = snm_closure(is_entry("_F2xq_log_Coppersmith_worker"),
1535 : mkvec2(mkvecsmall4(r, h, n, d), R));
1536 : struct pari_mt pt;
1537 14 : long running, pending = 0, stop=0;
1538 14 : mt_queue_start(&pt, worker);
1539 14 : if (DEBUGLEVEL) err_printf("Coppersmith (R = %ld): ",F2x_degree(R));
1540 2090 : while ((running = !stop) || pending)
1541 : {
1542 : GEN L, done;
1543 : long j, l;
1544 2076 : u[2] = i;
1545 2076 : mt_queue_submit(&pt, 0, running ? mkvec2(u, stoi(i)): NULL);
1546 2076 : done = mt_queue_get(&pt, NULL, &pending);
1547 2076 : if (!done) continue;
1548 2046 : L = gel(done, 2); nbtest += itos(gel(done,1));
1549 2046 : l = lg(L);
1550 2046 : if (l > 1)
1551 : {
1552 9116 : for (j=1; j<l; j++)
1553 : {
1554 7243 : if (rel>nbrel) break;
1555 7210 : gel(M,rel++) = gel(L,j);
1556 7210 : if (DEBUGLEVEL && (rel&511UL)==0)
1557 0 : err_printf("%ld%%[%ld] ",rel*100/nbrel,i);
1558 : }
1559 : }
1560 2046 : if (rel>nbrel) stop=1;
1561 2046 : i++;
1562 : }
1563 14 : mt_queue_end(&pt);
1564 14 : if (DEBUGLEVEL) err_printf(": %ld tests\n", nbtest);
1565 14 : return M;
1566 : }
1567 :
1568 : static GEN
1569 14 : smallirred_F2x(ulong n, long sv)
1570 : {
1571 14 : GEN a = zero_zv(nbits2lg(n+1)-1);
1572 14 : a[1] = sv; F2x_set(a,n); a[2]++;
1573 238 : while (!F2x_is_irred(a)) a[2]+=2;
1574 14 : return a;
1575 : }
1576 :
1577 : static GEN
1578 14 : check_kernel(long N, GEN M, long nbi, GEN T, GEN m)
1579 : {
1580 14 : pari_sp av = avma;
1581 14 : long dT = get_F2x_degree(T), vT = get_F2x_var(T);
1582 14 : GEN K = FpMs_leftkernel_elt(M, N, m);
1583 14 : long i, f=0, tbs;
1584 14 : long l = lg(K), lm = lgefint(m);
1585 14 : GEN idx = diviiexact(int2um1(dT), m);
1586 14 : GEN g = F2xq_pow(polx_F2x(vT), idx, T);
1587 : GEN tab;
1588 : pari_timer ti;
1589 14 : if (DEBUGLEVEL) timer_start(&ti);
1590 14 : K = FpC_Fp_mul(K, Fp_inv(gel(K,2), m), m);
1591 14 : tbs = maxss(1, expu(nbi/expi(m)));
1592 14 : tab = F2xq_pow_init(g, int2n(dT), tbs, T);
1593 57344 : for(i=1; i<l; i++)
1594 : {
1595 57330 : GEN k = gel(K,i);
1596 57330 : if (signe(k)==0 || !F2x_equal(F2xq_pow_table(tab, k, T),
1597 : F2xq_pow(mkF2(i,vT), idx, T)))
1598 52086 : gel(K,i) = cgetineg(lm);
1599 : else
1600 5244 : f++;
1601 : }
1602 14 : if (DEBUGLEVEL) timer_printf(&ti,"found %ld/%ld logs", f, nbi);
1603 14 : return gc_upto(av, K);
1604 : }
1605 :
1606 : static GEN
1607 14 : F2xq_log_index(GEN a0, GEN b0, GEN m, GEN T0)
1608 : {
1609 14 : pari_sp av = avma;
1610 14 : GEN M, S, a, b, Ao=NULL, Bo=NULL, W, e;
1611 : pari_timer ti;
1612 14 : long n = F2x_degree(T0), r = (long) (sqrt((double) 2*n))-(n>100);
1613 14 : GEN T = smallirred_F2x(n,T0[1]);
1614 14 : long d = 2, r2 = 3*r/2, d2 = 2;
1615 14 : long N = (1UL<<(r+1))-1UL;
1616 14 : long nbi = itos(ffsumnbirred(gen_2, r)), nbrel=nbi*5/4;
1617 14 : if (DEBUGLEVEL)
1618 : {
1619 0 : err_printf("F2xq_log: Parameters r=%ld r2=%ld\n", r,r2);
1620 0 : err_printf("F2xq_log: Size FB=%ld rel. needed=%ld\n", nbi, nbrel);
1621 0 : timer_start(&ti);
1622 : }
1623 14 : S = Flx_to_F2x(Flx_ffisom(F2x_to_Flx(T0),F2x_to_Flx(T),2));
1624 14 : a = F2x_F2xq_eval(a0, S, T);
1625 14 : b = F2x_F2xq_eval(b0, S, T);
1626 14 : if (DEBUGLEVEL) timer_printf(&ti,"model change");
1627 14 : M = F2xq_log_Coppersmith(nbrel,r,d,T);
1628 14 : if(DEBUGLEVEL)
1629 0 : timer_printf(&ti,"relations");
1630 14 : W = check_kernel(N, M, nbi, T, m);
1631 14 : timer_start(&ti);
1632 14 : Ao = F2xq_log_Coppersmith_rec(W, r2, a, r, d2, T, m);
1633 14 : if (DEBUGLEVEL) timer_printf(&ti,"smooth element");
1634 14 : Bo = F2xq_log_Coppersmith_rec(W, r2, b, r, d2, T, m);
1635 14 : if (DEBUGLEVEL) timer_printf(&ti,"smooth generator");
1636 14 : e = Fp_div(Ao, Bo, m);
1637 14 : if (!F2x_equal(F2xq_pow(b0,e,T0),a0)) pari_err_BUG("F2xq_log");
1638 14 : return gc_upto(av, e);
1639 : }
1640 :
1641 : static GEN
1642 559693 : F2xq_easylog(void* E, GEN a, GEN g, GEN ord)
1643 : {
1644 559693 : if (F2x_equal1(a)) return gen_0;
1645 525110 : if (F2x_equal(a,g)) return gen_1;
1646 524305 : if (typ(ord)!=t_INT) return NULL;
1647 262555 : if (expi(ord)<28) return NULL;
1648 14 : return F2xq_log_index(a,g,ord,(GEN)E);
1649 : }
1650 :
1651 : GEN
1652 543780 : F2xq_log(GEN a, GEN g, GEN ord, GEN T)
1653 : {
1654 543780 : GEN z, v = get_arith_ZZM(ord);
1655 543780 : ord = mkvec2(gel(v,1),ZM_famat_limit(gel(v,2),int2n(28)));
1656 543780 : z = gen_PH_log(a,g,ord,(void*)T,&F2xq_star);
1657 543780 : return z? z: cgetg(1,t_VEC);
1658 : }
1659 :
1660 : GEN
1661 211610 : F2xq_Artin_Schreier(GEN a, GEN T)
1662 : {
1663 211610 : pari_sp ltop=avma;
1664 211610 : long j,N = get_F2x_degree(T), vT = get_F2x_var(T);
1665 211610 : GEN Q = F2x_matFrobenius(T);
1666 1470889 : for (j=1; j<=N; j++)
1667 1259279 : F2m_flip(Q,j,j);
1668 211610 : F2v_add_inplace(gel(Q,1),a);
1669 211610 : Q = F2m_ker_sp(Q,0);
1670 211610 : if (lg(Q)!=2) return NULL;
1671 211610 : Q = gel(Q,1);
1672 211610 : Q[1] = vT;
1673 211610 : return gc_leaf(ltop, F2x_renormalize(Q, lg(Q)));
1674 : }
1675 :
1676 : GEN
1677 61295 : F2xq_sqrt_fast(GEN c, GEN sqx, GEN T)
1678 : {
1679 : GEN c0, c1;
1680 61295 : F2x_even_odd(c, &c0, &c1);
1681 61295 : return F2x_add(c0, F2xq_mul(c1, sqx, T));
1682 : }
1683 :
1684 : static int
1685 19246 : F2x_is_x(GEN a) { return lg(a)==3 && a[2]==2; }
1686 :
1687 : GEN
1688 38706 : F2xq_sqrt(GEN a, GEN T)
1689 : {
1690 38706 : pari_sp av = avma;
1691 38706 : long n = get_F2x_degree(T), vT = get_F2x_var(T);
1692 : GEN sqx;
1693 38706 : if (n==1) return F2x_copy(a);
1694 38615 : if (n==2) return F2xq_sqr(a,T);
1695 19246 : sqx = F2xq_autpow(mkF2(4, vT), n-1, T);
1696 19246 : return gc_leaf(av, F2x_is_x(a)? sqx: F2xq_sqrt_fast(a,sqx,T));
1697 : }
1698 :
1699 : GEN
1700 8348 : F2xq_sqrtn(GEN a, GEN n, GEN T, GEN *zeta)
1701 : {
1702 8348 : long dT = get_F2x_degree(T), vT = get_F2x_var(T);
1703 8348 : if (!lgpol(a))
1704 : {
1705 7 : if (signe(n) < 0) pari_err_INV("F2xq_sqrtn",a);
1706 0 : if (zeta)
1707 0 : *zeta=pol1_F2x(vT);
1708 0 : return pol0_F2x(vT);
1709 : }
1710 8341 : return gen_Shanks_sqrtn(a, n, int2um1(dT), zeta, (void*)T, &F2xq_star);
1711 : }
1712 :
1713 : GEN
1714 161 : gener_F2xq(GEN T, GEN *po)
1715 : {
1716 161 : long i, j, vT = get_F2x_var(T), f = get_F2x_degree(T);
1717 161 : pari_sp av0 = avma, av;
1718 : GEN g, L2, o, q;
1719 :
1720 161 : if (f == 1) {
1721 21 : if (po) *po = mkvec2(gen_1, trivial_fact());
1722 21 : return pol1_F2x(vT);
1723 : }
1724 140 : q = int2um1(f);
1725 140 : o = factor_pn_1(gen_2,f);
1726 140 : L2 = leafcopy( gel(o, 1) );
1727 399 : for (i = j = 1; i < lg(L2); i++)
1728 : {
1729 259 : if (absequaliu(gel(L2,i),2)) continue;
1730 259 : gel(L2,j++) = diviiexact(q, gel(L2,i));
1731 : }
1732 140 : setlg(L2, j);
1733 238 : for (av = avma;; set_avma(av))
1734 : {
1735 238 : g = random_F2x(f, vT);
1736 238 : if (F2x_degree(g) < 1) continue;
1737 469 : for (i = 1; i < j; i++)
1738 : {
1739 329 : GEN a = F2xq_pow(g, gel(L2,i), T);
1740 329 : if (F2x_equal1(a)) break;
1741 : }
1742 196 : if (i == j) break;
1743 : }
1744 140 : if (!po) g = gc_GEN(av0, g);
1745 : else {
1746 0 : *po = mkvec2(int2um1(f), o);
1747 0 : (void)gc_all(av0, 2, &g, po);
1748 : }
1749 140 : return g;
1750 : }
1751 :
1752 : static GEN
1753 756 : _F2xq_neg(void *E, GEN x) { (void) E; return F2x_copy(x); }
1754 : static GEN
1755 15799 : _F2xq_rmul(void *E, GEN x, GEN y) { (void) E; return F2x_mul(x,y); }
1756 : static GEN
1757 364 : _F2xq_inv(void *E, GEN x) { return F2xq_inv(x, (GEN) E); }
1758 : static int
1759 861 : _F2xq_equal0(GEN x) { return lgpol(x)==0; }
1760 : static GEN
1761 623 : _F2xq_s(void *E, long x)
1762 623 : { GEN T = (GEN) E;
1763 623 : long v = get_F2x_var(T);
1764 623 : return odd(x)? pol1_F2x(v): pol0_F2x(v);
1765 : }
1766 :
1767 : static const struct bb_field F2xq_field={_F2xq_red,_F2xq_add,_F2xq_rmul,_F2xq_neg,
1768 : _F2xq_inv,_F2xq_equal0,_F2xq_s};
1769 :
1770 1666 : const struct bb_field *get_F2xq_field(void **E, GEN T)
1771 : {
1772 1666 : *E = (void *) T;
1773 1666 : return &F2xq_field;
1774 : }
1775 :
1776 : /***********************************************************************/
1777 : /** **/
1778 : /** F2xV **/
1779 : /** **/
1780 : /***********************************************************************/
1781 : /* F2xV are t_VEC with F2x coefficients. */
1782 :
1783 : GEN
1784 38913 : FlxC_to_F2xC(GEN x) { pari_APPLY_type(t_COL, Flx_to_F2x(gel(x,i))) }
1785 : GEN
1786 0 : F2xC_to_FlxC(GEN x) { pari_APPLY_type(t_COL, F2x_to_Flx(gel(x,i))) }
1787 : GEN
1788 11137 : F2xC_to_ZXC(GEN x) { pari_APPLY_type(t_COL, F2x_to_ZX(gel(x,i))) }
1789 : GEN
1790 1788852 : F2xV_to_F2m(GEN x, long n) { pari_APPLY_type(t_MAT, F2x_to_F2v(gel(x,i), n)) }
1791 :
1792 : void
1793 33649 : F2xV_to_FlxV_inplace(GEN v)
1794 : {
1795 33649 : long i, l = lg(v);
1796 79497 : for(i = 1; i < l;i++) gel(v,i) = F2x_to_Flx(gel(v,i));
1797 33649 : }
1798 : void
1799 1451957 : F2xV_to_ZXV_inplace(GEN v)
1800 : {
1801 1451957 : long i, l = lg(v);
1802 2772070 : for(i = 1; i < l; i++) gel(v,i)= F2x_to_ZX(gel(v,i));
1803 1451952 : }
1804 :
1805 : /***********************************************************************/
1806 : /** **/
1807 : /** F2xX **/
1808 : /** **/
1809 : /***********************************************************************/
1810 :
1811 : GEN
1812 2711198 : F2xX_renormalize(GEN /*in place*/ x, long lx)
1813 2711198 : { return FlxX_renormalize(x, lx); }
1814 :
1815 : GEN
1816 446187 : pol1_F2xX(long v, long sv) { return pol1_FlxX(v, sv); }
1817 :
1818 : GEN
1819 441 : polx_F2xX(long v, long sv) { return polx_FlxX(v, sv); }
1820 :
1821 : long
1822 206465 : F2xY_degreex(GEN b)
1823 : {
1824 206465 : long deg = 0, i;
1825 206465 : if (!signe(b)) return -1;
1826 1340640 : for (i = 2; i < lg(b); ++i)
1827 1134175 : deg = maxss(deg, F2x_degree(gel(b, i)));
1828 206465 : return deg;
1829 : }
1830 :
1831 : GEN
1832 945 : FlxX_to_F2xX(GEN B)
1833 : {
1834 945 : long lb=lg(B);
1835 : long i;
1836 945 : GEN b=cgetg(lb,t_POL);
1837 945 : b[1]=evalsigne(1)|(((ulong)B[1])&VARNBITS);
1838 4718 : for (i=2; i<lb; i++)
1839 3773 : gel(b,i) = Flx_to_F2x(gel(B,i));
1840 945 : return F2xX_renormalize(b, lb);
1841 : }
1842 :
1843 : GEN
1844 4991 : ZXX_to_F2xX(GEN B, long v)
1845 : {
1846 4991 : long lb=lg(B);
1847 : long i;
1848 4991 : GEN b=cgetg(lb,t_POL);
1849 4991 : b[1]=evalsigne(1)|(((ulong)B[1])&VARNBITS);
1850 23492 : for (i=2; i<lb; i++)
1851 18501 : switch (typ(gel(B,i)))
1852 : {
1853 8721 : case t_INT:
1854 8721 : gel(b,i) = Z_to_F2x(gel(B,i), evalvarn(v));
1855 8721 : break;
1856 9780 : case t_POL:
1857 9780 : gel(b,i) = ZX_to_F2x(gel(B,i));
1858 9780 : break;
1859 : }
1860 4991 : return F2xX_renormalize(b, lb);
1861 : }
1862 :
1863 : GEN
1864 56 : F2xX_to_FlxX(GEN B)
1865 : {
1866 56 : long i, lb = lg(B);
1867 56 : GEN b = cgetg(lb,t_POL);
1868 266 : for (i=2; i<lb; i++)
1869 210 : gel(b,i) = F2x_to_Flx(gel(B,i));
1870 56 : b[1] = B[1]; return b;
1871 : }
1872 :
1873 : GEN
1874 1470 : F2xX_to_ZXX(GEN B)
1875 : {
1876 1470 : long i, lb = lg(B);
1877 1470 : GEN b = cgetg(lb,t_POL);
1878 4991 : for (i=2; i<lb; i++)
1879 : {
1880 3521 : GEN c = gel(B,i);
1881 3521 : gel(b,i) = lgpol(c) ? F2x_equal1(c) ? gen_1 : F2x_to_ZX(c) : gen_0;
1882 : }
1883 1470 : b[1] = B[1]; return b;
1884 : }
1885 :
1886 : GEN
1887 80465 : F2xX_deriv(GEN z)
1888 : {
1889 80465 : long i,l = lg(z)-1;
1890 : GEN x;
1891 80465 : if (l < 2) l = 2;
1892 80465 : x = cgetg(l, t_POL); x[1] = z[1];
1893 527436 : for (i=2; i<l; i++) gel(x,i) = odd(i) ? pol0_F2x(mael(z,i+1,1)): gel(z,i+1);
1894 80465 : return F2xX_renormalize(x,l);
1895 : }
1896 :
1897 : static GEN
1898 1186 : F2xX_addspec(GEN x, GEN y, long lx, long ly)
1899 : {
1900 : long i,lz;
1901 : GEN z;
1902 1186 : if (ly>lx) swapspec(x,y, lx,ly);
1903 1186 : lz = lx+2; z = cgetg(lz, t_POL);
1904 139499 : for (i=0; i<ly; i++) gel(z,i+2) = F2x_add(gel(x,i), gel(y,i));
1905 1186 : for ( ; i<lx; i++) gel(z,i+2) = F2x_copy(gel(x,i));
1906 1186 : z[1] = 0; return F2xX_renormalize(z, lz);
1907 : }
1908 :
1909 : GEN
1910 423367 : F2xX_add(GEN x, GEN y)
1911 : {
1912 : long i,lz;
1913 : GEN z;
1914 423367 : long lx=lg(x);
1915 423367 : long ly=lg(y);
1916 423367 : if (ly>lx) swapspec(x,y, lx,ly);
1917 423367 : lz = lx; z = cgetg(lz, t_POL); z[1]=x[1];
1918 1501362 : for (i=2; i<ly; i++) gel(z,i) = F2x_add(gel(x,i), gel(y,i));
1919 1680677 : for ( ; i<lx; i++) gel(z,i) = F2x_copy(gel(x,i));
1920 423367 : return F2xX_renormalize(z, lz);
1921 : }
1922 :
1923 : GEN
1924 0 : F2xX_F2x_add(GEN x, GEN y)
1925 : {
1926 0 : long i, lz = lg(y);
1927 : GEN z;
1928 0 : if (signe(y) == 0) return scalarpol(x, varn(y));
1929 0 : z = cgetg(lz,t_POL); z[1] = y[1];
1930 0 : gel(z,2) = F2x_add(gel(y,2), x);
1931 0 : if (lz == 3) z = F2xX_renormalize(z,lz);
1932 : else
1933 0 : for(i=3;i<lz;i++) gel(z,i) = F2x_copy(gel(y,i));
1934 0 : return z;
1935 : }
1936 :
1937 : GEN
1938 481488 : F2xX_F2x_mul(GEN P, GEN U)
1939 : {
1940 481488 : long i, lP = lg(P);
1941 481488 : GEN res = cgetg(lP,t_POL);
1942 481488 : res[1] = P[1];
1943 2352287 : for(i=2; i<lP; i++)
1944 1870799 : gel(res,i) = F2x_mul(U,gel(P,i));
1945 481488 : return F2xX_renormalize(res, lP);
1946 : }
1947 :
1948 : GEN
1949 136416 : F2xY_F2xqV_evalx(GEN P, GEN x, GEN T)
1950 : {
1951 136416 : long i, lP = lg(P);
1952 136416 : GEN res = cgetg(lP,t_POL);
1953 136416 : res[1] = P[1];
1954 617666 : for(i=2; i<lP; i++)
1955 481250 : gel(res,i) = F2x_F2xqV_eval(gel(P,i), x, T);
1956 136416 : return F2xX_renormalize(res, lP);
1957 : }
1958 :
1959 : GEN
1960 0 : F2xY_F2xq_evalx(GEN P, GEN x, GEN T)
1961 : {
1962 0 : pari_sp av = avma;
1963 0 : long n = brent_kung_optpow(get_F2x_degree(T)-1,lgpol(P),1);
1964 0 : GEN xp = F2xq_powers(x, n, T);
1965 0 : return gc_upto(av, F2xY_F2xqV_evalx(P, xp, T));
1966 : }
1967 :
1968 : static GEN
1969 6038 : F2xX_to_Kronecker_spec(GEN P, long n, long d)
1970 : {
1971 6038 : long i, k, l, N = 2*d + 1;
1972 6038 : long dP = n+1;
1973 : GEN x;
1974 6038 : if (n == 0) return pol0_Flx(P[1]&VARNBITS);
1975 6038 : l = nbits2nlong(N*dP+d+1);
1976 6038 : x = zero_zv(l+1);
1977 368117 : for (k=i=0; i<n; i++, k+=N)
1978 : {
1979 362079 : GEN c = gel(P,i);
1980 362079 : F2x_addshiftip(x, c, k);
1981 : }
1982 6038 : x[1] = P[1]&VARNBITS; return F2x_renormalize(x, l+2);
1983 : }
1984 :
1985 : GEN
1986 310456 : F2xX_to_Kronecker(GEN P, long d)
1987 : {
1988 310456 : long i, k, l, N = 2*d + 1;
1989 310456 : long dP = degpol(P);
1990 : GEN x;
1991 310456 : if (dP < 0) return pol0_Flx(P[1]&VARNBITS);
1992 309148 : l = nbits2nlong(N*dP+d+1);
1993 309148 : x = zero_zv(l+1);
1994 1717227 : for (k=i=0; i<=dP; i++, k+=N)
1995 : {
1996 1408079 : GEN c = gel(P,i+2);
1997 1408079 : F2x_addshiftip(x, c, k);
1998 : }
1999 309148 : x[1] = P[1]&VARNBITS; return F2x_renormalize(x, l+2);
2000 : }
2001 :
2002 : static GEN
2003 1609211 : F2x_slice(GEN x, long n, long d)
2004 : {
2005 1609211 : ulong ib, il=dvmduBIL(n, &ib);
2006 1609211 : ulong db, dl=dvmduBIL(d, &db);
2007 1609211 : long lN = dl+2+(db?1:0);
2008 1609211 : GEN t = cgetg(lN,t_VECSMALL);
2009 1609211 : t[1] = x[1];
2010 1609211 : if (ib)
2011 : {
2012 1443444 : ulong i, ic = BITS_IN_LONG-ib;
2013 1443444 : ulong r = uel(x,2+il)>>ib;
2014 1444012 : for(i=0; i<dl; i++)
2015 : {
2016 568 : uel(t,2+i) = (uel(x,3+il+i)<<ic)|r;
2017 568 : r = uel(x,3+il+i)>>ib;
2018 : }
2019 1443444 : if (db)
2020 1443444 : uel(t,2+i) = (uel(x,3+il+i)<<ic)|r;
2021 : }
2022 : else
2023 : {
2024 : long i;
2025 331682 : for(i=2; i<lN; i++)
2026 165915 : uel(t,i) = uel(x,il+i);
2027 : }
2028 1609211 : if (db) uel(t,lN-1) &= (1UL<<db)-1;
2029 1609211 : return F2x_renormalize(t, lN);
2030 : }
2031 :
2032 : GEN
2033 158247 : Kronecker_to_F2xqX(GEN z, GEN T)
2034 : {
2035 158247 : long lz = F2x_degree(z)+1;
2036 158247 : long i, j, N = get_F2x_degree(T)*2 + 1;
2037 158247 : long lx = lz / (N-2);
2038 158247 : GEN x = cgetg(lx+3,t_POL);
2039 158247 : x[1] = z[1];
2040 1767458 : for (i=0, j=2; i<lz; i+=N, j++)
2041 : {
2042 1609211 : GEN t = F2x_slice(z,i,minss(lz-i,N));
2043 1609211 : t[1] = T[1];
2044 1609211 : gel(x,j) = F2x_rem(t, T);
2045 : }
2046 158247 : return F2xX_renormalize(x, j);
2047 : }
2048 :
2049 : GEN
2050 0 : F2xX_to_F2xC(GEN x, long N, long sv)
2051 : {
2052 : long i, l;
2053 : GEN z;
2054 0 : l = lg(x)-1; x++;
2055 0 : if (l > N+1) l = N+1; /* truncate higher degree terms */
2056 0 : z = cgetg(N+1,t_COL);
2057 0 : for (i=1; i<l ; i++) gel(z,i) = gel(x,i);
2058 0 : for ( ; i<=N; i++) gel(z,i) = pol0_F2x(sv);
2059 0 : return z;
2060 : }
2061 :
2062 : GEN
2063 0 : F2xXV_to_F2xM(GEN v, long n, long sv)
2064 : {
2065 0 : long j, N = lg(v);
2066 0 : GEN y = cgetg(N, t_MAT);
2067 0 : for (j=1; j<N; j++) gel(y,j) = F2xX_to_F2xC(gel(v,j), n, sv);
2068 0 : return y;
2069 : }
2070 :
2071 : /***********************************************************************/
2072 : /** **/
2073 : /** F2xXV/F2xXC **/
2074 : /** **/
2075 : /***********************************************************************/
2076 :
2077 : GEN
2078 1330 : FlxXC_to_F2xXC(GEN x) { pari_APPLY_type(t_COL, FlxX_to_F2xX(gel(x,i))); }
2079 : GEN
2080 2611 : F2xXC_to_ZXXC(GEN x) { pari_APPLY_type(t_COL, F2xX_to_ZXX(gel(x,i))); }
2081 :
2082 : /***********************************************************************/
2083 : /** **/
2084 : /** F2xqX **/
2085 : /** **/
2086 : /***********************************************************************/
2087 :
2088 : static GEN
2089 783356 : get_F2xqX_red(GEN T, GEN *B)
2090 : {
2091 783356 : if (typ(T)!=t_VEC) { *B=NULL; return T; }
2092 2842 : *B = gel(T,1); return gel(T,2);
2093 : }
2094 :
2095 : GEN
2096 2842 : random_F2xqX(long d1, long v, GEN T)
2097 : {
2098 2842 : long dT = get_F2x_degree(T), vT = get_F2x_var(T);
2099 2842 : long i, d = d1+2;
2100 2842 : GEN y = cgetg(d,t_POL); y[1] = evalsigne(1) | evalvarn(v);
2101 19068 : for (i=2; i<d; i++) gel(y,i) = random_F2x(dT, vT);
2102 2842 : return FlxX_renormalize(y,d);
2103 : }
2104 :
2105 : GEN
2106 1004041 : F2xqX_red(GEN z, GEN T)
2107 : {
2108 : GEN res;
2109 1004041 : long i, l = lg(z);
2110 1004041 : res = cgetg(l,t_POL); res[1] = z[1];
2111 5667612 : for(i=2;i<l;i++) gel(res,i) = F2x_rem(gel(z,i),T);
2112 1004041 : return F2xX_renormalize(res,l);
2113 : }
2114 :
2115 : GEN
2116 6993 : F2xqX_F2xq_mul(GEN P, GEN U, GEN T)
2117 : {
2118 6993 : long i, lP = lg(P);
2119 6993 : GEN res = cgetg(lP,t_POL);
2120 6993 : res[1] = P[1];
2121 39165 : for(i=2; i<lP; i++)
2122 32172 : gel(res,i) = F2xq_mul(U,gel(P,i), T);
2123 6993 : return F2xX_renormalize(res, lP);
2124 : }
2125 :
2126 : GEN
2127 206010 : F2xqX_F2xq_mul_to_monic(GEN P, GEN U, GEN T)
2128 : {
2129 206010 : long i, lP = lg(P);
2130 206010 : GEN res = cgetg(lP,t_POL);
2131 206010 : res[1] = P[1];
2132 1129716 : for(i=2; i<lP-1; i++) gel(res,i) = F2xq_mul(U,gel(P,i), T);
2133 206010 : gel(res,lP-1) = pol1_F2x(T[1]);
2134 206010 : return F2xX_renormalize(res, lP);
2135 : }
2136 :
2137 : GEN
2138 206024 : F2xqX_normalize(GEN z, GEN T)
2139 : {
2140 206024 : GEN p1 = leading_coeff(z);
2141 206024 : if (!lgpol(z) || (!degpol(p1) && p1[1] == 1)) return z;
2142 206010 : return F2xqX_F2xq_mul_to_monic(z, F2xq_inv(p1,T), T);
2143 : }
2144 :
2145 : GEN
2146 155228 : F2xqX_mul(GEN x, GEN y, GEN T)
2147 : {
2148 155228 : pari_sp ltop=avma;
2149 : GEN z, kx, ky;
2150 155228 : long d = get_F2x_degree(T);
2151 155228 : kx= F2xX_to_Kronecker(x, d);
2152 155228 : ky= F2xX_to_Kronecker(y, d);
2153 155228 : z = F2x_mul(ky, kx);
2154 155228 : z = Kronecker_to_F2xqX(z, T);
2155 155228 : return gc_upto(ltop, z);
2156 : }
2157 :
2158 : static GEN
2159 3019 : F2xqX_mulspec(GEN x, GEN y, GEN T, long nx, long ny)
2160 : {
2161 3019 : pari_sp ltop=avma;
2162 : GEN z, kx, ky;
2163 3019 : long dT = get_F2x_degree(T);
2164 3019 : kx= F2xX_to_Kronecker_spec(x, nx, dT);
2165 3019 : ky= F2xX_to_Kronecker_spec(y, ny, dT);
2166 3019 : z = F2x_mul(ky, kx);
2167 3019 : z = Kronecker_to_F2xqX(z,T);
2168 3019 : return gc_upto(ltop,z);
2169 : }
2170 :
2171 : GEN
2172 105350 : F2xqX_sqr(GEN x, GEN T)
2173 : {
2174 105350 : long d = degpol(x), l = 2*d+3;
2175 : GEN z;
2176 105350 : if (!signe(x)) return pol_0(varn(x));
2177 105343 : z = cgetg(l,t_POL);
2178 105343 : z[1] = x[1];
2179 105343 : if (d > 0)
2180 : {
2181 105245 : GEN u = pol0_F2x(T[1]);
2182 : long i,j;
2183 268968 : for (i=2,j=2; i<d+2; i++,j+=2)
2184 : {
2185 163723 : gel(z, j) = F2xq_sqr(gel(x, i), T);
2186 163723 : gel(z, j+1) = u;
2187 : }
2188 : }
2189 105343 : gel(z, 2+2*d) = F2xq_sqr(gel(x, 2+d), T);
2190 105343 : return FlxX_renormalize(z, l);
2191 : }
2192 :
2193 : static GEN
2194 882 : _F2xqX_mul(void *data,GEN a,GEN b) { return F2xqX_mul(a,b, (GEN) data); }
2195 : static GEN
2196 0 : _F2xqX_sqr(void *data,GEN a) { return F2xqX_sqr(a, (GEN) data); }
2197 : GEN
2198 0 : F2xqX_powu(GEN x, ulong n, GEN T)
2199 0 : { return gen_powu(x, n, (void*)T, &_F2xqX_sqr, &_F2xqX_mul); }
2200 :
2201 : GEN
2202 7 : F2xqXV_prod(GEN V, GEN T)
2203 : {
2204 7 : return gen_product(V, (void*)T, &_F2xqX_mul);
2205 : }
2206 :
2207 : static GEN
2208 7 : F2xqV_roots_to_deg1(GEN x, GEN T, long v)
2209 : {
2210 7 : long sv = get_Flx_var(T);
2211 896 : pari_APPLY_same(deg1pol_shallow(pol1_F2x(sv),gel(x,i), v))
2212 : }
2213 :
2214 : GEN
2215 7 : F2xqV_roots_to_pol(GEN V, GEN T, long v)
2216 : {
2217 7 : pari_sp ltop = avma;
2218 7 : GEN W = F2xqV_roots_to_deg1(V, T, v);
2219 7 : return gc_upto(ltop, F2xqXV_prod(W, T));
2220 : }
2221 :
2222 : static GEN
2223 545227 : F2xqX_divrem_basecase(GEN x, GEN y, GEN T, GEN *pr)
2224 : {
2225 545227 : long vx = varn(x), dx = degpol(x), dy = degpol(y), dz, i, j, sx, lr;
2226 : pari_sp av0, av;
2227 : GEN z, p1, rem, lead;
2228 :
2229 545227 : if (!signe(y)) pari_err_INV("F2xqX_divrem",y);
2230 545227 : if (dx < dy)
2231 : {
2232 0 : if (pr)
2233 : {
2234 0 : av0 = avma; x = F2xqX_red(x, T);
2235 0 : if (pr == ONLY_DIVIDES) { set_avma(av0); return signe(x)? NULL: pol_0(vx); }
2236 0 : if (pr == ONLY_REM) return x;
2237 0 : *pr = x;
2238 : }
2239 0 : return pol_0(vx);
2240 : }
2241 545227 : lead = leading_coeff(y);
2242 545227 : if (!dy) /* y is constant */
2243 : {
2244 115507 : if (pr && pr != ONLY_DIVIDES)
2245 : {
2246 105483 : if (pr == ONLY_REM) return pol_0(vx);
2247 21 : *pr = pol_0(vx);
2248 : }
2249 10045 : if (F2x_equal1(lead)) return gcopy(x);
2250 6986 : av0 = avma; x = F2xqX_F2xq_mul(x,F2xq_inv(lead,T),T);
2251 6986 : return gc_upto(av0,x);
2252 : }
2253 429720 : av0 = avma; dz = dx-dy;
2254 429720 : lead = F2x_equal1(lead)? NULL: gclone(F2xq_inv(lead,T));
2255 429720 : set_avma(av0);
2256 429720 : z = cgetg(dz+3,t_POL); z[1] = x[1];
2257 429720 : x += 2; y += 2; z += 2;
2258 :
2259 429720 : p1 = gel(x,dx); av = avma;
2260 429720 : gel(z,dz) = lead? gc_upto(av, F2xq_mul(p1,lead, T)): leafcopy(p1);
2261 1279347 : for (i=dx-1; i>=dy; i--)
2262 : {
2263 849627 : av = avma; p1 = gel(x,i);
2264 2661311 : for (j=i-dy+1; j<=i && j<=dz; j++)
2265 1811684 : p1 = F2x_add(p1, F2x_mul(gel(z,j),gel(y,i-j)));
2266 849627 : if (lead) p1 = F2x_mul(p1, lead);
2267 849627 : gel(z,i-dy) = gc_leaf(av, F2x_rem(p1,T));
2268 : }
2269 429720 : if (!pr) { guncloneNULL(lead); return z-2; }
2270 :
2271 406574 : rem = (GEN)avma; av = (pari_sp)new_chunk(dx+3);
2272 629265 : for (sx=0; ; i--)
2273 : {
2274 629265 : p1 = gel(x,i);
2275 1900871 : for (j=0; j<=i && j<=dz; j++)
2276 1271606 : p1 = F2x_add(p1, F2x_mul(gel(z,j),gel(y,i-j)));
2277 629265 : p1 = F2x_rem(p1, T); if (lgpol(p1)) { sx = 1; break; }
2278 285607 : if (!i) break;
2279 222691 : set_avma(av);
2280 : }
2281 406574 : if (pr == ONLY_DIVIDES)
2282 : {
2283 0 : guncloneNULL(lead);
2284 0 : if (sx) return gc_NULL(av0);
2285 0 : return gc_const((pari_sp)rem, z-2);
2286 : }
2287 406574 : lr=i+3; rem -= lr; av = (pari_sp)rem;
2288 406574 : rem[0] = evaltyp(t_POL) | _evallg(lr);
2289 406574 : rem[1] = z[-1];
2290 406574 : rem += 2; gel(rem,i) = gc_leaf(av, p1);
2291 1380974 : for (i--; i>=0; i--)
2292 : {
2293 974400 : av = avma; p1 = gel(x,i);
2294 3408580 : for (j=0; j<=i && j<=dz; j++)
2295 2434180 : p1 = F2x_add(p1, F2x_mul(gel(z,j),gel(y,i-j)));
2296 974400 : gel(rem,i) = gc_leaf(av, F2x_rem(p1, T));
2297 : }
2298 406574 : rem -= 2;
2299 406574 : guncloneNULL(lead);
2300 406574 : if (!sx) (void)F2xX_renormalize(rem, lr);
2301 406574 : if (pr == ONLY_REM) return gc_upto(av0,rem);
2302 35 : *pr = rem; return z-2;
2303 : }
2304 :
2305 : static GEN
2306 2423 : F2xX_recipspec(GEN x, long l, long n, long vs)
2307 : {
2308 : long i;
2309 2423 : GEN z = cgetg(n+2,t_POL);
2310 2423 : z[1] = 0; z += 2;
2311 139712 : for(i=0; i<l; i++)
2312 137289 : gel(z,n-i-1) = F2x_copy(gel(x,i));
2313 2423 : for( ; i<n; i++)
2314 0 : gel(z,n-i-1) = pol0_F2x(vs);
2315 2423 : return F2xX_renormalize(z-2,n+2);
2316 : }
2317 :
2318 : static GEN
2319 0 : F2xqX_invBarrett_basecase(GEN T, GEN Q)
2320 : {
2321 0 : long i, l=lg(T)-1, lr = l-1, k;
2322 0 : long sv=Q[1];
2323 0 : GEN r=cgetg(lr,t_POL); r[1]=T[1];
2324 0 : gel(r,2) = pol1_F2x(sv);
2325 0 : for (i=3;i<lr;i++)
2326 : {
2327 0 : pari_sp ltop=avma;
2328 0 : GEN u = gel(T,l-i+2);
2329 0 : for (k=3;k<i;k++)
2330 0 : u = F2x_add(u, F2xq_mul(gel(T,l-i+k),gel(r,k),Q));
2331 0 : gel(r,i) = gc_upto(ltop, u);
2332 : }
2333 0 : r = F2xX_renormalize(r,lr);
2334 0 : return r;
2335 : }
2336 :
2337 : /* Return new lgpol */
2338 : static long
2339 3337 : F2xX_lgrenormalizespec(GEN x, long lx)
2340 : {
2341 : long i;
2342 3526 : for (i = lx-1; i>=0; i--)
2343 3526 : if (lgpol(gel(x,i))) break;
2344 3337 : return i+1;
2345 : }
2346 :
2347 : static GEN
2348 45 : F2xqX_invBarrett_Newton(GEN S, GEN T)
2349 : {
2350 45 : pari_sp av = avma;
2351 45 : long nold, lx, lz, lq, l = degpol(S), i, lQ;
2352 45 : GEN q, y, z, x = cgetg(l+2, t_POL) + 2;
2353 45 : long dT = get_F2x_degree(T);
2354 45 : ulong mask = quadratic_prec_mask(l-2); /* assume l > 2 */
2355 5337 : for (i=0;i<l;i++) gel(x,i) = pol0_F2x(T[1]);
2356 45 : q = F2xX_recipspec(S+2,l+1,l+1,dT);
2357 45 : lQ = lgpol(q); q+=2;
2358 : /* We work on _spec_ FlxX's, all the l[xzq] below are lgpol's */
2359 :
2360 : /* initialize */
2361 45 : gel(x,0) = F2xq_inv(gel(q,0),T);
2362 45 : if (lQ>1 && F2x_degree(gel(q,1)) >= dT)
2363 0 : gel(q,1) = F2x_rem(gel(q,1), T);
2364 45 : if (lQ>1 && lgpol(gel(q,1)))
2365 38 : {
2366 38 : GEN u = gel(q, 1);
2367 38 : if (!F2x_equal1(gel(x,0))) u = F2xq_mul(u, F2xq_sqr(gel(x,0), T), T);
2368 38 : else u = F2x_copy(u);
2369 38 : gel(x,1) = u; lx = 2;
2370 : }
2371 : else
2372 7 : lx = 1;
2373 45 : nold = 1;
2374 367 : for (; mask > 1; )
2375 : { /* set x -= x(x*q - 1) + O(t^(nnew + 1)), knowing x*q = 1 + O(t^(nold+1)) */
2376 322 : long i, lnew, nnew = nold << 1;
2377 :
2378 322 : if (mask & 1) nnew--;
2379 322 : mask >>= 1;
2380 :
2381 322 : lnew = nnew + 1;
2382 322 : lq = F2xX_lgrenormalizespec(q, minss(lQ,lnew));
2383 322 : z = F2xqX_mulspec(x, q, T, lx, lq); /* FIXME: high product */
2384 322 : lz = lgpol(z); if (lz > lnew) lz = lnew;
2385 322 : z += 2;
2386 : /* subtract 1 [=>first nold words are 0]: renormalize so that z(0) != 0 */
2387 644 : for (i = nold; i < lz; i++) if (lgpol(gel(z,i))) break;
2388 322 : nold = nnew;
2389 322 : if (i >= lz) continue; /* z-1 = 0(t^(nnew + 1)) */
2390 :
2391 : /* z + i represents (x*q - 1) / t^i */
2392 322 : lz = F2xX_lgrenormalizespec (z+i, lz-i);
2393 322 : z = F2xqX_mulspec(x, z+i, T, lx, lz); /* FIXME: low product */
2394 322 : lz = lgpol(z); z += 2;
2395 322 : if (lz > lnew-i) lz = F2xX_lgrenormalizespec(z, lnew-i);
2396 :
2397 322 : lx = lz+ i;
2398 322 : y = x + i; /* x -= z * t^i, in place */
2399 5479 : for (i = 0; i < lz; i++) gel(y,i) = gel(z,i);
2400 : }
2401 45 : x -= 2; setlg(x, lx + 2); x[1] = S[1];
2402 45 : return gc_GEN(av, x);
2403 : }
2404 :
2405 : GEN
2406 45 : F2xqX_invBarrett(GEN T, GEN Q)
2407 : {
2408 45 : pari_sp ltop=avma;
2409 45 : long l=lg(T), v = varn(T);
2410 : GEN r;
2411 45 : GEN c = gel(T,l-1);
2412 45 : if (l<5) return pol_0(v);
2413 45 : if (l<=F2xqX_INVBARRETT_LIMIT)
2414 : {
2415 0 : if (!F2x_equal1(c))
2416 : {
2417 0 : GEN ci = F2xq_inv(c,Q);
2418 0 : T = F2xqX_F2xq_mul(T, ci, Q);
2419 0 : r = F2xqX_invBarrett_basecase(T,Q);
2420 0 : r = F2xqX_F2xq_mul(r,ci,Q);
2421 : } else
2422 0 : r = F2xqX_invBarrett_basecase(T,Q);
2423 : } else
2424 45 : r = F2xqX_invBarrett_Newton(T,Q);
2425 45 : return gc_upto(ltop, r);
2426 : }
2427 :
2428 : GEN
2429 219975 : F2xqX_get_red(GEN S, GEN T)
2430 : {
2431 219975 : if (typ(S)==t_POL && lg(S)>F2xqX_BARRETT_LIMIT)
2432 42 : retmkvec2(F2xqX_invBarrett(S, T), S);
2433 219933 : return S;
2434 : }
2435 :
2436 : /* Compute x mod S where 2 <= degpol(S) <= l+1 <= 2*(degpol(S)-1)
2437 : * * and mg is the Barrett inverse of S. */
2438 : static GEN
2439 1189 : F2xqX_divrem_Barrettspec(GEN x, long l, GEN mg, GEN S, GEN T, GEN *pr)
2440 : {
2441 : GEN q, r;
2442 1189 : long lt = degpol(S); /*We discard the leading term*/
2443 : long ld, lm, lT, lmg;
2444 1189 : ld = l-lt;
2445 1189 : lm = minss(ld, lgpol(mg));
2446 1189 : lT = F2xX_lgrenormalizespec(S+2,lt);
2447 1189 : lmg = F2xX_lgrenormalizespec(mg+2,lm);
2448 1189 : q = F2xX_recipspec(x+lt,ld,ld,0); /* q = rec(x) lq<=ld*/
2449 1189 : q = F2xqX_mulspec(q+2,mg+2,T,lgpol(q),lmg); /* q = rec(x) * mg lq<=ld+lm*/
2450 1189 : q = F2xX_recipspec(q+2,minss(ld,lgpol(q)),ld,0);/* q = rec (rec(x) * mg) lq<=ld*/
2451 1189 : if (!pr) return q;
2452 1186 : r = F2xqX_mulspec(q+2,S+2,T,lgpol(q),lT); /* r = q*pol lr<=ld+lt*/
2453 1186 : r = F2xX_addspec(x,r+2,lt,minss(lt,lgpol(r)));/* r = x - r lr<=lt */
2454 1186 : if (pr == ONLY_REM) return r;
2455 3 : *pr = r; return q;
2456 : }
2457 :
2458 : static GEN
2459 1186 : F2xqX_divrem_Barrett(GEN x, GEN mg, GEN S, GEN T, GEN *pr)
2460 : {
2461 1186 : GEN q = NULL, r = F2xqX_red(x, T);
2462 1186 : long l = lgpol(r), lt = degpol(S), lm = 2*lt-1, v = varn(S);
2463 : long i;
2464 1186 : if (l <= lt)
2465 : {
2466 0 : if (pr == ONLY_REM) return r;
2467 0 : if (pr == ONLY_DIVIDES) return signe(r)? NULL: pol_0(v);
2468 0 : if (pr) *pr = r;
2469 0 : return pol_0(v);
2470 : }
2471 1186 : if (lt <= 1)
2472 0 : return F2xqX_divrem_basecase(x,S,T,pr);
2473 1186 : if (pr != ONLY_REM && l>lm)
2474 : {
2475 3 : long vT = get_F2x_var(T);
2476 3 : q = cgetg(l-lt+2, t_POL); q[1] = S[1];
2477 375 : for (i=0;i<l-lt;i++) gel(q+2,i) = pol0_F2x(vT);
2478 : }
2479 1189 : while (l>lm)
2480 : {
2481 3 : GEN zr, zq = F2xqX_divrem_Barrettspec(r+2+l-lm,lm,mg,S,T,&zr);
2482 3 : long lz = lgpol(zr);
2483 3 : if (pr != ONLY_REM)
2484 : {
2485 3 : long lq = lgpol(zq);
2486 231 : for(i=0; i<lq; i++) gel(q+2+l-lm,i) = gel(zq,2+i);
2487 : }
2488 234 : for(i=0; i<lz; i++) gel(r+2+l-lm,i) = gel(zr,2+i);
2489 3 : l = l-lm+lz;
2490 : }
2491 1186 : if (pr == ONLY_REM)
2492 : {
2493 1183 : if (l > lt)
2494 1183 : r = F2xqX_divrem_Barrettspec(r+2,l,mg,S,T,ONLY_REM);
2495 : else
2496 0 : r = F2xX_renormalize(r, lg(r));
2497 1183 : setvarn(r, v); return F2xX_renormalize(r, lg(r));
2498 : }
2499 3 : if (l > lt)
2500 : {
2501 3 : GEN zq = F2xqX_divrem_Barrettspec(r+2,l,mg,S,T,pr? &r: NULL);
2502 3 : if (!q) q = zq;
2503 : else
2504 : {
2505 3 : long lq = lgpol(zq);
2506 147 : for(i=0; i<lq; i++) gel(q+2,i) = gel(zq,2+i);
2507 : }
2508 : }
2509 0 : else if (pr)
2510 0 : r = F2xX_renormalize(r, l+2);
2511 3 : setvarn(q, v); q = F2xX_renormalize(q, lg(q));
2512 3 : if (pr == ONLY_DIVIDES) return signe(r)? NULL: q;
2513 3 : if (pr) { setvarn(r, v); *pr = r; }
2514 3 : return q;
2515 : }
2516 :
2517 : GEN
2518 33229 : F2xqX_divrem(GEN x, GEN S, GEN T, GEN *pr)
2519 : {
2520 : GEN B, y;
2521 : long dy, dx, d;
2522 33229 : if (pr==ONLY_REM) return F2xqX_rem(x, S, T);
2523 33229 : y = get_F2xqX_red(S, &B);
2524 33229 : dy = degpol(y); dx = degpol(x); d = dx-dy;
2525 33229 : if (!B && d+3 < F2xqX_DIVREM_BARRETT_LIMIT)
2526 33226 : return F2xqX_divrem_basecase(x,y,T,pr);
2527 : else
2528 : {
2529 3 : pari_sp av=avma;
2530 3 : GEN mg = B? B: F2xqX_invBarrett(y, T);
2531 3 : GEN q = F2xqX_divrem_Barrett(x,mg,y,T,pr);
2532 3 : if (!q) return gc_NULL(av);
2533 3 : if (!pr || pr==ONLY_DIVIDES) return gc_GEN(av, q);
2534 0 : return gc_all(av,2,&q,pr);
2535 : }
2536 : }
2537 :
2538 : GEN
2539 750127 : F2xqX_rem(GEN x, GEN S, GEN T)
2540 : {
2541 750127 : GEN B, y = get_F2xqX_red(S, &B);
2542 750127 : long dy = degpol(y), dx = degpol(x), d = dx-dy;
2543 750127 : if (d < 0) return F2xqX_red(x, T);
2544 513184 : if (!B && d+3 < F2xqX_REM_BARRETT_LIMIT)
2545 512001 : return F2xqX_divrem_basecase(x,y, T, ONLY_REM);
2546 : else
2547 : {
2548 1183 : pari_sp av=avma;
2549 1183 : GEN mg = B? B: F2xqX_invBarrett(y, T);
2550 1183 : GEN r = F2xqX_divrem_Barrett(x, mg, y, T, ONLY_REM);
2551 1183 : return gc_upto(av, r);
2552 : }
2553 : }
2554 :
2555 : static GEN
2556 0 : F2xqX_addmulmul(GEN u, GEN v, GEN x, GEN y, GEN T)
2557 : {
2558 0 : return F2xX_add(F2xqX_mul(u, x, T),F2xqX_mul(v, y, T));
2559 : }
2560 :
2561 : INLINE GEN
2562 0 : F2xXn_red(GEN a, long n) { return FlxXn_red(a, n); }
2563 :
2564 : static GEN
2565 0 : F2xqXM_F2xqX_mul2(GEN M, GEN x, GEN y, GEN T)
2566 : {
2567 0 : GEN res = cgetg(3, t_COL);
2568 0 : gel(res, 1) = F2xqX_addmulmul(gcoeff(M,1,1), gcoeff(M,1,2), x, y, T);
2569 0 : gel(res, 2) = F2xqX_addmulmul(gcoeff(M,2,1), gcoeff(M,2,2), x, y, T);
2570 0 : return res;
2571 : }
2572 :
2573 : static GEN
2574 0 : F2xqXM_mul2(GEN A, GEN B, GEN T)
2575 : {
2576 0 : GEN A11=gcoeff(A,1,1),A12=gcoeff(A,1,2), B11=gcoeff(B,1,1),B12=gcoeff(B,1,2);
2577 0 : GEN A21=gcoeff(A,2,1),A22=gcoeff(A,2,2), B21=gcoeff(B,2,1),B22=gcoeff(B,2,2);
2578 0 : GEN M1 = F2xqX_mul(F2xX_add(A11,A22), F2xX_add(B11,B22), T);
2579 0 : GEN M2 = F2xqX_mul(F2xX_add(A21,A22), B11, T);
2580 0 : GEN M3 = F2xqX_mul(A11, F2xX_add(B12,B22), T);
2581 0 : GEN M4 = F2xqX_mul(A22, F2xX_add(B21,B11), T);
2582 0 : GEN M5 = F2xqX_mul(F2xX_add(A11,A12), B22, T);
2583 0 : GEN M6 = F2xqX_mul(F2xX_add(A21,A11), F2xX_add(B11,B12), T);
2584 0 : GEN M7 = F2xqX_mul(F2xX_add(A12,A22), F2xX_add(B21,B22), T);
2585 0 : GEN T1 = F2xX_add(M1,M4), T2 = F2xX_add(M7,M5);
2586 0 : GEN T3 = F2xX_add(M1,M2), T4 = F2xX_add(M3,M6);
2587 0 : retmkmat22(F2xX_add(T1,T2), F2xX_add(M3,M5),
2588 : F2xX_add(M2,M4), F2xX_add(T3,T4));
2589 : }
2590 :
2591 : /* Return [0,1;1,-q]*M */
2592 : static GEN
2593 0 : F2xqX_F2xqXM_qmul(GEN q, GEN M, GEN T)
2594 : {
2595 0 : GEN u = F2xqX_mul(gcoeff(M,2,1), q, T);
2596 0 : GEN v = F2xqX_mul(gcoeff(M,2,2), q, T);
2597 0 : retmkmat22(gcoeff(M,2,1), gcoeff(M,2,2),
2598 : F2xX_add(gcoeff(M,1,1), u), F2xX_add(gcoeff(M,1,2), v));
2599 : }
2600 :
2601 : static GEN
2602 0 : matid2_F2xXM(long v, long sv)
2603 0 : { retmkmat22(pol1_F2xX(v, sv),pol_0(v),pol_0(v),pol1_F2xX(v, sv)); }
2604 :
2605 : static GEN
2606 0 : matJ2_F2xXM(long v, long sv)
2607 0 : { retmkmat22(pol_0(v),pol1_F2xX(v, sv),pol1_F2xX(v, sv),pol_0(v)); }
2608 :
2609 : struct F2xqX_res
2610 : {
2611 : GEN res, lc;
2612 : long deg0, deg1;
2613 : };
2614 :
2615 : INLINE void
2616 0 : F2xqX_halfres_update(long da, long db, long dr, GEN T, struct F2xqX_res *res)
2617 : {
2618 0 : if (dr >= 0)
2619 : {
2620 0 : if (!F2x_equal1(res->lc))
2621 : {
2622 0 : res->lc = F2xq_powu(res->lc, da - dr, T);
2623 0 : res->res = F2xq_mul(res->res, res->lc, T);
2624 : }
2625 : } else
2626 : {
2627 0 : if (db == 0)
2628 : {
2629 0 : if (!F2x_equal1(res->lc))
2630 : {
2631 0 : res->lc = F2xq_powu(res->lc, da, T);
2632 0 : res->res = F2xq_mul(res->res, res->lc, T);
2633 : }
2634 : } else
2635 0 : res->res = pol0_F2x(get_F2x_var(T));
2636 : }
2637 0 : }
2638 :
2639 : static GEN
2640 7 : F2xqX_halfres_basecase(GEN a, GEN b, GEN T, GEN *pa, GEN *pb, struct F2xqX_res *res)
2641 : {
2642 7 : pari_sp av=avma;
2643 : GEN u,u1,v,v1, M;
2644 7 : long vx = varn(a), vT = get_F2x_var(T), n = lgpol(a)>>1;
2645 7 : u1 = v = pol_0(vx);
2646 7 : u = v1 = pol1_F2xX(vx, vT);
2647 7 : while (lgpol(b)>n)
2648 : {
2649 : GEN r, q;
2650 0 : q = F2xqX_divrem(a,b, T, &r);
2651 0 : if (res)
2652 : {
2653 0 : long da = degpol(a), db = degpol(b), dr = degpol(r);
2654 0 : res->lc = gel(b,db+2);
2655 0 : if (dr >= n)
2656 0 : F2xqX_halfres_update(da, db, dr, T, res);
2657 : else
2658 : {
2659 0 : res->deg0 = da;
2660 0 : res->deg1 = db;
2661 : }
2662 : }
2663 0 : a = b; b = r; swap(u,u1); swap(v,v1);
2664 0 : u1 = F2xX_add(u1, F2xqX_mul(u, q, T));
2665 0 : v1 = F2xX_add(v1, F2xqX_mul(v, q, T));
2666 0 : if (gc_needed(av,2))
2667 : {
2668 0 : if (DEBUGMEM>1) pari_warn(warnmem,"F2xqX_halfgcd (d = %ld)",degpol(b));
2669 0 : if (res)
2670 0 : (void)gc_all(av, 8, &a,&b,&u1,&v1,&u,&v,&res->res,&res->lc);
2671 : else
2672 0 : (void)gc_all(av, 6, &a,&b,&u1,&v1,&u,&v);
2673 : }
2674 : }
2675 7 : M = mkmat22(u,v,u1,v1); *pa = a; *pb = b;
2676 0 : return res ? gc_all(av, 5, &M, pa, pb, &res->res, &res->lc)
2677 7 : : gc_all(av, 3, &M, pa, pb);
2678 : }
2679 :
2680 : static GEN F2xqX_halfres_i(GEN x, GEN y, GEN T, GEN *a, GEN *b, struct F2xqX_res *res);
2681 :
2682 : static GEN
2683 0 : F2xqX_halfres_split(GEN x, GEN y, GEN T, GEN *a, GEN *b, struct F2xqX_res *res)
2684 : {
2685 0 : pari_sp av = avma;
2686 : GEN Q, R, S, V1, V2;
2687 : GEN x1, y1, r, q;
2688 0 : long l = lgpol(x), n = l>>1, k, vT = get_F2x_var(T);
2689 0 : if (lgpol(y) <= n)
2690 0 : { *a = RgX_copy(x); *b = RgX_copy(y); return matid2_F2xXM(varn(x),vT); }
2691 0 : if (res)
2692 : {
2693 0 : res->lc = leading_coeff(y);
2694 0 : res->deg0 -= n;
2695 0 : res->deg1 -= n;
2696 : }
2697 0 : R = F2xqX_halfres_i(F2xX_shift(x,-n, vT),F2xX_shift(y,-n, vT), T, a, b, res);
2698 0 : if (res)
2699 : {
2700 0 : res->deg0 += n;
2701 0 : res->deg1 += n;
2702 : }
2703 0 : V1 = F2xqXM_F2xqX_mul2(R, Flxn_red(x,n), Flxn_red(y,n), T);
2704 0 : x1 = F2xX_add(F2xX_shift(*a,n,vT), gel(V1,1));
2705 0 : y1 = F2xX_add(F2xX_shift(*b,n,vT), gel(V1,2));
2706 0 : if (lgpol(y1) <= n)
2707 : {
2708 0 : *a = x1; *b = y1;
2709 0 : return res ? gc_all(av, 5, &R, a, b, &res->res, &res->lc)
2710 0 : : gc_all(av, 3, &R, a, b, &res->res, &res->lc);
2711 : }
2712 0 : k = 2*n-degpol(y1);
2713 0 : q = F2xqX_divrem(x1, y1, T, &r);
2714 0 : if (res)
2715 : {
2716 0 : long dx1 = degpol(x1), dy1 = degpol(y1), dr = degpol(r);
2717 0 : if (dy1 < degpol(y))
2718 0 : F2xqX_halfres_update(res->deg0, res->deg1, dy1, T, res);
2719 0 : res->lc = leading_coeff(y1);
2720 0 : res->deg0 = dx1;
2721 0 : res->deg1 = dy1;
2722 0 : if (dr >= n)
2723 : {
2724 0 : F2xqX_halfres_update(dx1, dy1, dr, T, res);
2725 0 : res->deg0 = dy1;
2726 0 : res->deg1 = dr;
2727 : }
2728 0 : res->deg0 -= k;
2729 0 : res->deg1 -= k;
2730 : }
2731 0 : S = F2xqX_halfres_i(F2xX_shift(y1,-k, vT), F2xX_shift(r,-k, vT), T, a, b, res);
2732 0 : if (res)
2733 : {
2734 0 : res->deg0 += k;
2735 0 : res->deg1 += k;
2736 : }
2737 0 : Q = F2xqXM_mul2(S,F2xqX_F2xqXM_qmul(q, R, T), T);
2738 0 : V2 = F2xqXM_F2xqX_mul2(S, F2xXn_red(y1,k), F2xXn_red(r,k), T);
2739 0 : *a = F2xX_add(F2xX_shift(*a,k,vT), gel(V2,1));
2740 0 : *b = F2xX_add(F2xX_shift(*b,k,vT), gel(V2,2));
2741 0 : return res ? gc_all(av, 5, &Q, a, b, &res->res, &res->lc)
2742 0 : : gc_all(av, 3, &Q, a, b, &res->res, &res->lc);
2743 : }
2744 :
2745 : static GEN
2746 7 : F2xqX_halfres_i(GEN x, GEN y, GEN T, GEN *a, GEN *b, struct F2xqX_res *res)
2747 : {
2748 7 : if (lgpol(x) < F2xqX_HALFGCD_LIMIT)
2749 7 : return F2xqX_halfres_basecase(x, y, T, a, b, res);
2750 0 : return F2xqX_halfres_split(x, y, T, a, b, res);
2751 : }
2752 :
2753 : static GEN
2754 7 : F2xqX_halfgcd_all_i(GEN x, GEN y, GEN T, GEN *pa, GEN *pb)
2755 : {
2756 : GEN a, b;
2757 7 : GEN R = F2xqX_halfres_i(x, y, T, &a, &b, NULL);
2758 7 : if (pa) *pa = a;
2759 7 : if (pb) *pb = b;
2760 7 : return R;
2761 : }
2762 :
2763 : /* Return M in GL_2(F_2[X]/(T)[Y]) such that:
2764 : if [a',b']~=M*[a,b]~ then degpol(a')>= (lgpol(a)>>1) >degpol(b')
2765 : */
2766 :
2767 : GEN
2768 7 : F2xqX_halfgcd_all(GEN x, GEN y, GEN T, GEN *a, GEN *b)
2769 : {
2770 7 : pari_sp av = avma;
2771 : GEN R,q,r;
2772 7 : if (!signe(x))
2773 : {
2774 0 : if (a) *a = RgX_copy(y);
2775 0 : if (b) *b = RgX_copy(x);
2776 0 : return matJ2_F2xXM(varn(x), get_F2x_var(T));
2777 : }
2778 7 : if (degpol(y)<degpol(x)) return F2xqX_halfgcd_all_i(x, y, T, a, b);
2779 7 : q = F2xqX_divrem(y, x, T, &r);
2780 7 : R = F2xqX_halfgcd_all_i(x, r, T, a, b);
2781 7 : gcoeff(R,1,1) = F2xX_add(gcoeff(R,1,1), F2xqX_mul(q, gcoeff(R,1,2), T));
2782 7 : gcoeff(R,2,1) = F2xX_add(gcoeff(R,2,1), F2xqX_mul(q, gcoeff(R,2,2), T));
2783 7 : return !a && b ? gc_all(av, 2, &R, b): gc_all(av, 1+!!a+!!b, &R, a, b);
2784 : }
2785 :
2786 : GEN
2787 0 : F2xqX_halfgcd(GEN x, GEN y, GEN T)
2788 0 : { return F2xqX_halfgcd_all(x, y, T, NULL, NULL); }
2789 :
2790 : static GEN
2791 169365 : F2xqX_gcd_basecase(GEN a, GEN b, GEN T)
2792 : {
2793 169365 : pari_sp av = avma, av0=avma;
2794 697921 : while (signe(b))
2795 : {
2796 : GEN c;
2797 528556 : if (gc_needed(av0,2))
2798 : {
2799 0 : if (DEBUGMEM>1) pari_warn(warnmem,"F2xqX_gcd (d = %ld)",degpol(b));
2800 0 : (void)gc_all(av0,2, &a,&b);
2801 : }
2802 528556 : av = avma; c = F2xqX_rem(a, b, T); a=b; b=c;
2803 : }
2804 169365 : return gc_const(av, a);
2805 : }
2806 :
2807 : GEN
2808 169750 : F2xqX_gcd(GEN x, GEN y, GEN T)
2809 : {
2810 169750 : pari_sp av = avma;
2811 169750 : x = F2xqX_red(x, T);
2812 169750 : y = F2xqX_red(y, T);
2813 169750 : if (!signe(x)) return gc_upto(av, y);
2814 169365 : while (lgpol(y)>=F2xqX_GCD_LIMIT)
2815 : {
2816 0 : if (lgpol(y)<=(lgpol(x)>>1))
2817 : {
2818 0 : GEN r = F2xqX_rem(x, y, T);
2819 0 : x = y; y = r;
2820 : }
2821 0 : (void) F2xqX_halfgcd_all(x, y, T, &x, &y);
2822 0 : if (gc_needed(av,2))
2823 : {
2824 0 : if (DEBUGMEM>1) pari_warn(warnmem,"F2xqX_gcd (y = %ld)",degpol(y));
2825 0 : (void)gc_all(av,2,&x,&y);
2826 : }
2827 : }
2828 169365 : return gc_upto(av, F2xqX_gcd_basecase(x, y, T));
2829 : }
2830 :
2831 : static GEN
2832 14 : F2xqX_extgcd_basecase(GEN a, GEN b, GEN T, GEN *ptu, GEN *ptv)
2833 : {
2834 14 : pari_sp av=avma;
2835 : GEN u,v,d,d1,v1;
2836 14 : long vx = varn(a);
2837 14 : d = a; d1 = b;
2838 14 : v = pol_0(vx); v1 = pol1_F2xX(vx, get_F2x_var(T));
2839 63 : while (signe(d1))
2840 : {
2841 49 : GEN r, q = F2xqX_divrem(d, d1, T, &r);
2842 49 : v = F2xX_add(v,F2xqX_mul(q,v1,T));
2843 49 : u=v; v=v1; v1=u;
2844 49 : u=r; d=d1; d1=u;
2845 49 : if (gc_needed(av,2))
2846 : {
2847 0 : if (DEBUGMEM>1) pari_warn(warnmem,"F2xqX_extgcd (d = %ld)",degpol(d));
2848 0 : (void)gc_all(av,5, &d,&d1,&u,&v,&v1);
2849 : }
2850 : }
2851 14 : if (ptu) *ptu = F2xqX_div(F2xX_add(d,F2xqX_mul(b,v, T)), a, T);
2852 14 : *ptv = v; return d;
2853 : }
2854 :
2855 : static GEN
2856 0 : F2xqX_extgcd_halfgcd(GEN x, GEN y, GEN T, GEN *ptu, GEN *ptv)
2857 : {
2858 : GEN u,v;
2859 0 : GEN V = cgetg(expu(lgpol(y))+2,t_VEC);
2860 0 : long i, n = 0, vs = varn(x), vT = get_F2x_var(T);
2861 0 : while (lgpol(y)>=F2xqX_EXTGCD_LIMIT)
2862 : {
2863 0 : if (lgpol(y)<=(lgpol(x)>>1))
2864 : {
2865 0 : GEN r, q = F2xqX_divrem(x, y, T, &r);
2866 0 : x = y; y = r;
2867 0 : gel(V,++n) = mkmat22(pol_0(vs),pol1_F2xX(vs,vT),pol1_F2xX(vs,vT),RgX_copy(q));
2868 : } else
2869 0 : gel(V,++n) = F2xqX_halfgcd_all(x, y, T, &x, &y);
2870 : }
2871 0 : y = F2xqX_extgcd_basecase(x,y, T, &u,&v);
2872 0 : for (i = n; i>1; i--)
2873 : {
2874 0 : GEN R = gel(V,i);
2875 0 : GEN u1 = F2xqX_addmulmul(u, v, gcoeff(R,1,1), gcoeff(R,2,1), T);
2876 0 : GEN v1 = F2xqX_addmulmul(u, v, gcoeff(R,1,2), gcoeff(R,2,2), T);
2877 0 : u = u1; v = v1;
2878 : }
2879 : {
2880 0 : GEN R = gel(V,1);
2881 0 : if (ptu)
2882 0 : *ptu = F2xqX_addmulmul(u, v, gcoeff(R,1,1), gcoeff(R,2,1), T);
2883 0 : *ptv = F2xqX_addmulmul(u, v, gcoeff(R,1,2), gcoeff(R,2,2), T);
2884 : }
2885 0 : return y;
2886 : }
2887 :
2888 : /* x and y in Z[Y][X], return lift(gcd(x mod T,p, y mod T,p)). Set u and v st
2889 : * ux + vy = gcd (mod T,p) */
2890 : GEN
2891 14 : F2xqX_extgcd(GEN x, GEN y, GEN T, GEN *ptu, GEN *ptv)
2892 : {
2893 14 : pari_sp av = avma;
2894 : GEN d;
2895 14 : x = F2xqX_red(x, T);
2896 14 : y = F2xqX_red(y, T);
2897 14 : if (lgpol(y)>=F2xqX_EXTGCD_LIMIT)
2898 0 : d = F2xqX_extgcd_halfgcd(x, y, T, ptu, ptv);
2899 : else
2900 14 : d = F2xqX_extgcd_basecase(x, y, T, ptu, ptv);
2901 14 : return gc_all(av, ptu?3:2, &d, ptv, ptu);
2902 : }
2903 :
2904 : static GEN
2905 0 : F2xqX_halfres(GEN x, GEN y, GEN T, GEN *a, GEN *b, GEN *r)
2906 : {
2907 : struct F2xqX_res res;
2908 : GEN V;
2909 : long dB;
2910 :
2911 0 : res.res = *r;
2912 0 : res.lc = leading_coeff(y);
2913 0 : res.deg0 = degpol(x);
2914 0 : res.deg1 = degpol(y);
2915 0 : V = F2xqX_halfres_i(x, y, T, a, b, &res);
2916 0 : dB = degpol(*b);
2917 0 : if (dB < degpol(y))
2918 0 : F2xqX_halfres_update(res.deg0, res.deg1, dB, T, &res);
2919 0 : *r = res.res;
2920 0 : return V;
2921 : }
2922 :
2923 : /* Res(A,B) = Res(B,R) * lc(B)^(a-r) * (-1)^(ab), with R=A%B, a=deg(A) ...*/
2924 : static GEN
2925 21 : F2xqX_resultant_basecase(GEN a, GEN b, GEN T)
2926 : {
2927 21 : pari_sp av = avma;
2928 21 : long vT = get_F2x_var(T), da,db,dc;
2929 21 : GEN c,lb, res = pol1_F2x(vT);
2930 :
2931 21 : if (!signe(a) || !signe(b)) return pol0_F2x(vT);
2932 :
2933 21 : da = degpol(a);
2934 21 : db = degpol(b);
2935 21 : if (db > da)
2936 0 : swapspec(a,b, da,db);
2937 21 : if (!da) return pol1_F2x(vT); /* = res * a[2] ^ db, since 0 <= db <= da = 0 */
2938 49 : while (db)
2939 : {
2940 28 : lb = gel(b,db+2);
2941 28 : c = F2xqX_rem(a,b, T);
2942 28 : a = b; b = c; dc = degpol(c);
2943 28 : if (dc < 0) { set_avma(av); return pol0_F2x(vT); }
2944 :
2945 28 : if (!equali1(lb)) res = F2xq_mul(res, F2xq_powu(lb, da - dc, T), T);
2946 28 : if (gc_needed(av,2))
2947 : {
2948 0 : if (DEBUGMEM>1) pari_warn(warnmem,"F2xqX_resultant (da = %ld)",da);
2949 0 : (void)gc_all(av,3, &a,&b,&res);
2950 : }
2951 28 : da = db; /* = degpol(a) */
2952 28 : db = dc; /* = degpol(b) */
2953 : }
2954 21 : res = F2xq_mul(res, F2xq_powu(gel(b,2), da, T), T);
2955 21 : return gc_upto(av, res);
2956 : }
2957 :
2958 : /* Res(A,B) = Res(B,R) * lc(B)^(a-r) * (-1)^(ab), with R=A%B, a=deg(A) ...*/
2959 : GEN
2960 21 : F2xqX_resultant(GEN x, GEN y, GEN T)
2961 : {
2962 21 : pari_sp av = avma;
2963 21 : long dx, dy, vT = get_F2x_var(T);
2964 21 : GEN res = pol1_F2x(vT);
2965 21 : if (!signe(x) || !signe(y)) return pol0_F2x(vT);
2966 21 : dx = degpol(x); dy = degpol(y);
2967 21 : if (dx < dy)
2968 7 : swap(x,y);
2969 21 : while (lgpol(y) >= F2xqX_GCD_LIMIT)
2970 : {
2971 0 : if (lgpol(y)<=(lgpol(x)>>1))
2972 : {
2973 0 : GEN r = F2xqX_rem(x, y, T);
2974 0 : long dx = degpol(x), dy = degpol(y), dr = degpol(r);
2975 0 : GEN ly = gel(y,dy+2);
2976 0 : if (!F2x_equal1(ly))
2977 0 : res = F2xq_mul(res, F2xq_powu(ly, dx - dr, T), T);
2978 0 : x = y; y = r;
2979 : }
2980 0 : (void) F2xqX_halfres(x, y, T, &x, &y, &res);
2981 0 : if (gc_needed(av,2))
2982 : {
2983 0 : if (DEBUGMEM>1) pari_warn(warnmem,"F2xqX_resultant (y = %ld)",degpol(y));
2984 0 : (void)gc_all(av,3,&x,&y,&res);
2985 : }
2986 : }
2987 21 : res = F2xq_mul(res, F2xqX_resultant_basecase(x, y, T), T);
2988 21 : return gc_upto(av, res);
2989 : }
2990 :
2991 : /* disc P = (-1)^(n(n-1)/2) lc(P)^(n - deg P' - 2) Res(P,P'), n = deg P */
2992 : GEN
2993 14 : F2xqX_disc(GEN P, GEN T)
2994 : {
2995 14 : pari_sp av = avma;
2996 14 : GEN L, dP = F2xX_deriv(P), D = F2xqX_resultant(P, dP, T);
2997 : long dd;
2998 14 : if (!lgpol(D)) return pol_0(get_F2x_var(T));
2999 14 : dd = degpol(P) - 2 - degpol(dP); /* >= -1; > -1 iff p | deg(P) */
3000 14 : L = leading_coeff(P);
3001 14 : if (dd && !F2x_equal1(L))
3002 0 : D = (dd == -1)? F2xq_div(D,L,T): F2xq_mul(D, F2xq_powu(L, dd, T), T);
3003 14 : return gc_upto(av, D);
3004 : }
3005 :
3006 : /***********************************************************************/
3007 : /** **/
3008 : /** F2xqXQ **/
3009 : /** **/
3010 : /***********************************************************************/
3011 :
3012 : GEN
3013 114240 : F2xqXQ_mul(GEN x, GEN y, GEN S, GEN T) {
3014 114240 : return F2xqX_rem(F2xqX_mul(x,y,T),S,T);
3015 : }
3016 :
3017 : GEN
3018 104279 : F2xqXQ_sqr(GEN x, GEN S, GEN T) {
3019 104279 : return F2xqX_rem(F2xqX_sqr(x,T),S,T);
3020 : }
3021 :
3022 : GEN
3023 7 : F2xqXQ_invsafe(GEN x, GEN S, GEN T)
3024 : {
3025 7 : GEN V, z = F2xqX_extgcd(get_F2xqX_mod(S), x, T, NULL, &V);
3026 7 : if (degpol(z)) return NULL;
3027 7 : z = F2xq_invsafe(gel(z,2),T);
3028 7 : if (!z) return NULL;
3029 7 : return F2xqX_F2xq_mul(V, z, T);
3030 : }
3031 :
3032 : GEN
3033 7 : F2xqXQ_inv(GEN x, GEN S, GEN T)
3034 : {
3035 7 : pari_sp av = avma;
3036 7 : GEN U = F2xqXQ_invsafe(x, S, T);
3037 7 : if (!U) pari_err_INV("F2xqXQ_inv",x);
3038 7 : return gc_upto(av, U);
3039 : }
3040 :
3041 : struct _F2xqXQ {
3042 : GEN T, S;
3043 : };
3044 :
3045 : static GEN
3046 345030 : _F2xqXQ_add(void *data, GEN x, GEN y) {
3047 : (void) data;
3048 345030 : return F2xX_add(x,y);
3049 : }
3050 : static GEN
3051 481488 : _F2xqXQ_cmul(void *data, GEN P, long a, GEN x) {
3052 : (void) data;
3053 481488 : return F2xX_F2x_mul(x,gel(P,a+2));
3054 : }
3055 : static GEN
3056 351246 : _F2xqXQ_red(void *data, GEN x) {
3057 351246 : struct _F2xqXQ *d = (struct _F2xqXQ*) data;
3058 351246 : return F2xqX_red(x, d->T);
3059 : }
3060 : static GEN
3061 114184 : _F2xqXQ_mul(void *data, GEN x, GEN y) {
3062 114184 : struct _F2xqXQ *d = (struct _F2xqXQ*) data;
3063 114184 : return F2xqXQ_mul(x,y, d->S,d->T);
3064 : }
3065 : static GEN
3066 33250 : _F2xqXQ_sqr(void *data, GEN x) {
3067 33250 : struct _F2xqXQ *d = (struct _F2xqXQ*) data;
3068 33250 : return F2xqXQ_sqr(x, d->S,d->T);
3069 : }
3070 : static GEN
3071 7 : _F2xqXQ_zero(void *data) {
3072 7 : struct _F2xqXQ *d = (struct _F2xqXQ*) data;
3073 7 : return pol_0(get_F2xqX_var(d->S));
3074 : }
3075 : static GEN
3076 374773 : _F2xqXQ_one(void *data) {
3077 374773 : struct _F2xqXQ *d = (struct _F2xqXQ*) data;
3078 374773 : return pol1_F2xX(get_F2xqX_var(d->S),get_F2x_var(d->T));
3079 : }
3080 :
3081 : static struct bb_algebra F2xqXQ_algebra = { _F2xqXQ_red,
3082 : _F2xqXQ_add, _F2xqXQ_add, _F2xqXQ_mul,_F2xqXQ_sqr,_F2xqXQ_one,_F2xqXQ_zero };
3083 :
3084 : GEN
3085 7 : F2xqXQ_pow(GEN x, GEN n, GEN S, GEN T)
3086 : {
3087 : struct _F2xqXQ D;
3088 7 : long s = signe(n);
3089 7 : if (!s) return pol1_F2xX(get_F2xqX_var(S), get_F2x_var(T));
3090 7 : if (s < 0) x = F2xqXQ_inv(x,S,T);
3091 7 : if (is_pm1(n)) return s < 0 ? x : gcopy(x);
3092 7 : if (degpol(x) >= get_F2xqX_degree(S)) x = F2xqX_rem(x,S,T);
3093 7 : D.T = F2x_get_red(T);
3094 7 : D.S = F2xqX_get_red(S, T);
3095 7 : return gen_pow(x, n, (void*)&D, &_F2xqXQ_sqr, &_F2xqXQ_mul);
3096 : }
3097 :
3098 : GEN
3099 7714 : F2xqXQ_powers(GEN x, long l, GEN S, GEN T)
3100 : {
3101 : struct _F2xqXQ D;
3102 7714 : int use_sqr = 2*degpol(x) >= get_F2xqX_degree(S);
3103 7714 : D.T = F2x_get_red(T);
3104 7714 : D.S = F2xqX_get_red(S, T);
3105 7714 : return gen_powers(x, l, use_sqr, (void*)&D, &_F2xqXQ_sqr, &_F2xqXQ_mul,&_F2xqXQ_one);
3106 : }
3107 :
3108 : GEN
3109 14413 : F2xqX_F2xqXQV_eval(GEN P, GEN V, GEN S, GEN T)
3110 : {
3111 : struct _F2xqXQ D;
3112 14413 : D.T = F2x_get_red(T);
3113 14413 : D.S = F2xqX_get_red(S, T);
3114 14413 : return gen_bkeval_powers(P, degpol(P), V, (void*)&D, &F2xqXQ_algebra,
3115 : _F2xqXQ_cmul);
3116 : }
3117 :
3118 : GEN
3119 122052 : F2xqX_F2xqXQ_eval(GEN Q, GEN x, GEN S, GEN T)
3120 : {
3121 : struct _F2xqXQ D;
3122 122052 : int use_sqr = 2*degpol(x) >= get_F2xqX_degree(S);
3123 122052 : D.T = F2x_get_red(T);
3124 122052 : D.S = F2xqX_get_red(S, T);
3125 122052 : return gen_bkeval(Q, degpol(Q), x, use_sqr, (void*)&D, &F2xqXQ_algebra,
3126 : _F2xqXQ_cmul);
3127 : }
3128 :
3129 : static GEN
3130 88809 : F2xqXQ_autpow_sqr(void * E, GEN x)
3131 : {
3132 88809 : struct _F2xqXQ *D = (struct _F2xqXQ *)E;
3133 88809 : GEN T = D->T;
3134 88809 : GEN phi = gel(x,1), S = gel(x,2);
3135 88809 : long n = brent_kung_optpow(get_F2x_degree(T)-1,lgpol(S)+1,1);
3136 88809 : GEN V = F2xq_powers(phi, n, T);
3137 88809 : GEN phi2 = F2x_F2xqV_eval(phi, V, T);
3138 88809 : GEN Sphi = F2xY_F2xqV_evalx(S, V, T);
3139 88809 : GEN S2 = F2xqX_F2xqXQ_eval(Sphi, S, D->S, T);
3140 88809 : return mkvec2(phi2, S2);
3141 : }
3142 :
3143 : static GEN
3144 33243 : F2xqXQ_autpow_mul(void * E, GEN x, GEN y)
3145 : {
3146 33243 : struct _F2xqXQ *D = (struct _F2xqXQ *)E;
3147 33243 : GEN T = D->T;
3148 33243 : GEN phi1 = gel(x,1), S1 = gel(x,2);
3149 33243 : GEN phi2 = gel(y,1), S2 = gel(y,2);
3150 33243 : long n = brent_kung_optpow(get_F2x_degree(T)-1,lgpol(S1)+1,1);
3151 33243 : GEN V = F2xq_powers(phi2, n, T);
3152 33243 : GEN phi3 = F2x_F2xqV_eval(phi1,V,T);
3153 33243 : GEN Sphi = F2xY_F2xqV_evalx(S1,V,T);
3154 33243 : GEN S3 = F2xqX_F2xqXQ_eval(Sphi, S2, D->S, T);
3155 33243 : return mkvec2(phi3, S3);
3156 : }
3157 :
3158 : GEN
3159 70434 : F2xqXQ_autpow(GEN aut, long n, GEN S, GEN T)
3160 : {
3161 : struct _F2xqXQ D;
3162 70434 : D.T = F2x_get_red(T);
3163 70434 : D.S = F2xqX_get_red(S, T);
3164 70434 : return gen_powu(aut,n,&D,F2xqXQ_autpow_sqr,F2xqXQ_autpow_mul);
3165 : }
3166 :
3167 : static GEN
3168 7182 : F2xqXQ_auttrace_mul(void *E, GEN x, GEN y)
3169 : {
3170 7182 : struct _F2xqXQ *D = (struct _F2xqXQ *) E;
3171 7182 : GEN T = D->T;
3172 7182 : GEN phi1 = gel(x,1), S1 = gel(x,2), a1 = gel(x,3);
3173 7182 : GEN phi2 = gel(y,1), S2 = gel(y,2), a2 = gel(y,3);
3174 7182 : long n2 = brent_kung_optpow(get_F2x_degree(T)-1, lgpol(S1)+lgpol(a1)+1, 1);
3175 7182 : GEN V2 = F2xq_powers(phi2, n2, T);
3176 7182 : GEN phi3 = F2x_F2xqV_eval(phi1, V2, T);
3177 7182 : GEN Sphi = F2xY_F2xqV_evalx(S1, V2, T);
3178 7182 : GEN aphi = F2xY_F2xqV_evalx(a1, V2, T);
3179 7182 : long n = brent_kung_optpow(maxss(degpol(Sphi),degpol(aphi)),2,1);
3180 7182 : GEN V = F2xqXQ_powers(S2, n, D->S, T);
3181 7182 : GEN S3 = F2xqX_F2xqXQV_eval(Sphi, V, D->S, T);
3182 7182 : GEN aS = F2xqX_F2xqXQV_eval(aphi, V, D->S, T);
3183 7182 : GEN a3 = F2xX_add(aS, a2);
3184 7182 : return mkvec3(phi3, S3, a3);
3185 : }
3186 :
3187 : static GEN
3188 4893 : F2xqXQ_auttrace_sqr(void *E, GEN x) { return F2xqXQ_auttrace_mul(E, x, x); }
3189 : GEN
3190 2723 : F2xqXQ_auttrace(GEN aut, long n, GEN S, GEN T)
3191 : {
3192 : struct _F2xqXQ D;
3193 2723 : D.T = F2x_get_red(T);
3194 2723 : D.S = F2xqX_get_red(S, T);
3195 2723 : return gen_powu(aut,n,&D,F2xqXQ_auttrace_sqr,F2xqXQ_auttrace_mul);
3196 : }
3197 :
3198 : GEN
3199 63 : F2xqXQV_red(GEN x, GEN S, GEN T)
3200 273 : { pari_APPLY_type(t_VEC, F2xqX_rem(gel(x,i), S, T)) }
|
