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