CoCalc -- F2x.c

Testing latest pari + WASM + node.js... and it works?! Wow.
pari / 2021-07-01 / pari-2.14.0.alpha / src / basemath / F2x.c
²⁸⁴⁷⁸ views
License: GPL3
ubuntu2004
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
F2x_degreespec(GEN x, long l)
42
{
43
  return (l==0)?-1:l*BITS_IN_LONG-bfffo(x[l-1])-1;
44
}
45

46
INLINE long
47
F2x_degree_lg(GEN x, long l)
48
{
49
  return (l==2)?-1:bit_accuracy(l)-bfffo(x[l-1])-1;
50
}
51

52
long
53
F2x_degree(GEN x)
54
{
55
  return F2x_degree_lg(x, lg(x));
56
}
57

58
GEN
59
monomial_F2x(long d, long vs)
60
{
61
  long l=nbits2lg(d+1);
62
  GEN z = zero_zv(l-1);
63
  z[1] = vs;
64
  F2x_set(z,d);
65
  return z;
66
}
67

68
GEN
69
F2x_to_ZX(GEN x)
70
{
71
  long l = 3+F2x_degree(x), lx = lg(x);
72
  GEN z = cgetg(l,t_POL);
73
  long i, j ,k;
74
  for (i=2, k=2; i<lx; i++)
75
    for (j=0; j<BITS_IN_LONG && k<l; j++,k++)
76
      gel(z,k) = (x[i]&(1UL<<j))?gen_1:gen_0;
77
  z[1]=evalsigne(l>=3)|x[1];
78
  return z;
79
}
80

81
GEN
82
F2x_to_Flx(GEN x)
83
{
84
  long l = 3+F2x_degree(x), lx = lg(x);
85
  GEN z = cgetg(l,t_VECSMALL);
86
  long i, j, k;
87
  z[1] = x[1];
88
  for (i=2, k=2; i<lx; i++)
89
    for (j=0; j<BITS_IN_LONG && k<l; j++,k++)
90
      z[k] = (x[i]>>j)&1UL;
91
  return z;
92
}
93

94
GEN
95
F2x_to_F2xX(GEN z, long sv)
96
{
97
  long i, d = F2x_degree(z);
98
  GEN x = cgetg(d+3,t_POL);
99
  for (i=0; i<=d; i++)
100
    gel(x,i+2) = F2x_coeff(z,i) ? pol1_F2x(sv): pol0_F2x(sv);
101
  x[1] = evalsigne(d+1!=0)| z[1]; return x;
102
}
103

104
GEN
105
Z_to_F2x(GEN x, long sv)
106
{
107
  return mpodd(x) ? pol1_F2x(sv): pol0_F2x(sv);
108
}
109

110
GEN
111
ZX_to_F2x(GEN x)
112
{
113
  long lx = lg(x), l = nbits2lg(lx-2);
114
  GEN z = cgetg(l,t_VECSMALL);
115
  long i, j, k;
116
  z[1] = ((ulong)x[1])&VARNBITS;
117
  for (i=2, k=1,j=BITS_IN_LONG; i<lx; i++,j++)
118
  {
119
    if (j==BITS_IN_LONG)
120
    {
121
      j=0; z[++k]=0;
122
    }
123
    if (mpodd(gel(x,i)))
124
      z[k] |= 1UL<<j;
125
  }
126
  return F2x_renormalize(z,l);
127
}
128

129
GEN
130
Flx_to_F2x(GEN x)
131
{
132
  long lx = lg(x), l = nbits2lg(lx-2);
133
  GEN z = cgetg(l,t_VECSMALL);
134
  long i, j, k;
135
  z[1] = x[1];
136
  for (i=2, k=1, j=BITS_IN_LONG; i<lx; i++,j++)
137
  {
138
    if (j==BITS_IN_LONG)
139
    {
140
      j=0; z[++k] = 0;
141
    }
142
    if (x[i]&1UL)
143
      z[k] |= 1UL<<j;
144
  }
145
  return F2x_renormalize(z,l);
146
}
147

148
GEN
149
F2x_to_F2v(GEN x, long N)
150
{
151
  long i, l = lg(x);
152
  long n = nbits2lg(N);
153
  GEN z = cgetg(n,t_VECSMALL);
154
  z[1] = N;
155
  for (i=2; i<l ; i++) z[i]=x[i];
156
  for (   ; i<n; i++) z[i]=0;
157
  return z;
158
}
159

160
GEN
161
RgX_to_F2x(GEN x)
162
{
163
  long l=nbits2lg(lgpol(x));
164
  GEN z=cgetg(l,t_VECSMALL);
165
  long i,j,k;
166
  z[1]=((ulong)x[1])&VARNBITS;
167
  for(i=2, k=1,j=BITS_IN_LONG;i<lg(x);i++,j++)
168
  {
169
    if (j==BITS_IN_LONG)
170
    {
171
      j=0; k++; z[k]=0;
172
    }
173
    if (Rg_to_F2(gel(x,i)))
174
      z[k]|=1UL<<j;
175
  }
176
  return F2x_renormalize(z,l);
177
}
178

179
/* If x is a POLMOD, assume modulus is a multiple of T. */
180
GEN
181
Rg_to_F2xq(GEN x, GEN T)
182
{
183
  long ta, tx = typ(x), v = get_F2x_var(T);
184
  GEN a, b;
185
  if (is_const_t(tx))
186
  {
187
    if (tx == t_FFELT) return FF_to_F2xq(x);
188
    return Rg_to_F2(x)? pol1_F2x(v): pol0_F2x(v);
189
  }
190
  switch(tx)
191
  {
192
    case t_POLMOD:
193
      b = gel(x,1);
194
      a = gel(x,2); ta = typ(a);
195
      if (is_const_t(ta)) return Rg_to_F2(a)? pol1_F2x(v): pol0_F2x(v);
196
      b = RgX_to_F2x(b); if (b[1] != v) break;
197
      a = RgX_to_F2x(a); if (F2x_equal(b,T)) return a;
198
      if (lgpol(F2x_rem(b,T))==0) return F2x_rem(a, T);
199
      break;
200
    case t_POL:
201
      x = RgX_to_F2x(x);
202
      if (x[1] != v) break;
203
      return F2x_rem(x, T);
204
    case t_RFRAC:
205
      a = Rg_to_F2xq(gel(x,1), T);
206
      b = Rg_to_F2xq(gel(x,2), T);
207
      return F2xq_div(a,b, T);
208
  }
209
  pari_err_TYPE("Rg_to_F2xq",x);
210
  return NULL; /* LCOV_EXCL_LINE */
211
}
212

213
ulong
214
F2x_eval(GEN P, ulong x)
215
{
216
  if (odd(x))
217
  {
218
    long i, lP = lg(P);
219
    ulong c = 0;
220
    for (i=2; i<lP; i++)
221
      c ^= P[i];
222
#ifdef LONG_IS_64BIT
223
    c ^= c >> 32;
224
#endif
225
    c ^= c >> 16;
226
    c ^= c >>  8;
227
    c ^= c >>  4;
228
    c ^= c >>  2;
229
    c ^= c >>  1;
230
    return c & 1;
231
  }
232
  else return F2x_coeff(P,0);
233
}
234

235
GEN
236
F2x_add(GEN x, GEN y)
237
{
238
  long i,lz;
239
  GEN z;
240
  long lx=lg(x);
241
  long ly=lg(y);
242
  if (ly>lx) swapspec(x,y, lx,ly);
243
  lz = lx; z = cgetg(lz, t_VECSMALL); z[1]=x[1];
244
  for (i=2; i<ly; i++) z[i] = x[i]^y[i];
245
  for (   ; i<lx; i++) z[i] = x[i];
246
  return F2x_renormalize(z, lz);
247
}
248

249
static GEN
250
F2x_addspec(GEN x, GEN y, long lx, long ly)
251
{
252
  long i,lz;
253
  GEN z;
254

255
  if (ly>lx) swapspec(x,y, lx,ly);
256
  lz = lx+2; z = cgetg(lz, t_VECSMALL) + 2;
257
  for (i=0; i<ly-3; i+=4)
258
  {
259
    z[i] = x[i]^y[i];
260
    z[i+1] = x[i+1]^y[i+1];
261
    z[i+2] = x[i+2]^y[i+2];
262
    z[i+3] = x[i+3]^y[i+3];
263
  }
264
  for (; i<ly; i++)
265
    z[i] = x[i]^y[i];
266
  for (   ; i<lx; i++) z[i] = x[i];
267
  z -= 2; z[1] = 0; return F2x_renormalize(z, lz);
268
}
269

270
GEN
271
F2x_1_add(GEN y)
272
{
273
  GEN z;
274
  long lz, i;
275
  if (!lgpol(y))
276
    return pol1_F2x(y[1]);
277
  lz=lg(y);
278
  z=cgetg(lz,t_VECSMALL);
279
  z[1] = y[1];
280
  z[2] = y[2]^1UL;
281
  for(i=3;i<lz;i++)
282
    z[i] = y[i];
283
  if (lz==3) z = F2x_renormalize(z,lz);
284
  return z;
285
}
286

287
INLINE void
288
F2x_addshiftipspec(GEN x, GEN y, long ny, ulong db)
289
{
290
  long i;
291
  if (db)
292
  {
293
    ulong dc=BITS_IN_LONG-db;
294
    ulong r=0, yi;
295
    for(i=0; i<ny-3; i+=4)
296
    {
297
      yi = uel(y,i);   x[i]   ^= (yi<<db)|r; r = yi>>dc;
298
      yi = uel(y,i+1); x[i+1] ^= (yi<<db)|r; r = yi>>dc;
299
      yi = uel(y,i+2); x[i+2] ^= (yi<<db)|r; r = yi>>dc;
300
      yi = uel(y,i+3); x[i+3] ^= (yi<<db)|r; r = yi>>dc;
301
    }
302
    for(  ; i<ny; i++)
303
    {
304
      ulong yi = uel(y,i); x[i] ^= (yi<<db)|r; r = yi>>dc;
305
    }
306
    if (r) x[i] ^= r;
307
  }
308
  else
309
  {
310
    for(i=0; i<ny-3; i+=4)
311
    {
312
      x[i]   ^= y[i];
313
      x[i+1] ^= y[i+1];
314
      x[i+2] ^= y[i+2];
315
      x[i+3] ^= y[i+3];
316
    }
317
    for(   ; i<ny; i++)
318
      x[i] ^= y[i];
319
  }
320
}
321

322
INLINE void
323
F2x_addshiftip(GEN x, GEN y, ulong d)
324
{
325
  ulong db, dl=dvmduBIL(d, &db);
326
  F2x_addshiftipspec(x+2+dl, y+2, lgpol(y), db);
327
}
328

329
static GEN
330
F2x_mul1(ulong x, ulong y)
331
{
332
  ulong x1=(x&HIGHMASK)>>BITS_IN_HALFULONG;
333
  ulong x2=x&LOWMASK;
334
  ulong y1=(y&HIGHMASK)>>BITS_IN_HALFULONG;
335
  ulong y2=y&LOWMASK;
336
  ulong r1,r2,rr;
337
  GEN z;
338
  ulong i;
339
  rr=r1=r2=0UL;
340
  if (x2)
341
    for(i=0;i<BITS_IN_HALFULONG;i++)
342
      if (x2&(1UL<<i))
343
      {
344
        r2^=y2<<i;
345
        rr^=y1<<i;
346
      }
347
  if (x1)
348
    for(i=0;i<BITS_IN_HALFULONG;i++)
349
      if (x1&(1UL<<i))
350
      {
351
        r1^=y1<<i;
352
        rr^=y2<<i;
353
      }
354
  r2^=(rr&LOWMASK)<<BITS_IN_HALFULONG;
355
  r1^=(rr&HIGHMASK)>>BITS_IN_HALFULONG;
356
  z=cgetg((r1?4:3),t_VECSMALL);
357
  z[2]=r2;
358
  if (r1) z[3]=r1;
359
  return z;
360
}
361

362
static GEN
363
F2x_mulspec_basecase(GEN x, GEN y, long nx, long ny)
364
{
365
  long l, i, j;
366
  GEN z;
367
  l = nx + ny;
368
  z = zero_Flv(l+1);
369
  for(i=0; i < ny-1; i++)
370
  {
371
    GEN zi = z+2+i;
372
    ulong yi = uel(y,i);
373
    if (yi)
374
      for(j=0; j < BITS_IN_LONG; j++)
375
        if (yi&(1UL<<j)) F2x_addshiftipspec(zi,x,nx,j);
376
  }
377
  {
378
    GEN zi = z+2+i;
379
    ulong yi = uel(y,i);
380
    long c = BITS_IN_LONG-bfffo(yi);
381
    for(j=0; j < c; j++)
382
      if (yi&(1UL<<j)) F2x_addshiftipspec(zi,x,nx,j);
383
  }
384
  return F2x_renormalize(z, l+2);
385
}
386

387
static GEN
388
F2x_addshift(GEN x, GEN y, long d)
389
{
390
  GEN xd,yd,zd = (GEN)avma;
391
  long a,lz,ny = lgpol(y), nx = lgpol(x);
392
  long vs = x[1];
393
  if (nx == 0) return y;
394
  x += 2; y += 2; a = ny-d;
395
  if (a <= 0)
396
  {
397
    lz = (a>nx)? ny+2: nx+d+2;
398
    (void)new_chunk(lz); xd = x+nx; yd = y+ny;
399
    while (xd > x) *--zd = *--xd;
400
    x = zd + a;
401
    while (zd > x) *--zd = 0;
402
  }
403
  else
404
  {
405
    xd = new_chunk(d); yd = y+d;
406
    x = F2x_addspec(x,yd,nx,a);
407
    lz = (a>nx)? ny+2: lg(x)+d;
408
    x += 2; while (xd > x) *--zd = *--xd;
409
  }
410
  while (yd > y) *--zd = *--yd;
411
  *--zd = vs;
412
  *--zd = evaltyp(t_VECSMALL) | evallg(lz); return zd;
413
}
414

415
/* shift polynomial + gerepile */
416
/* Do not set evalvarn. Cf Flx_shiftip */
417
static GEN
418
F2x_shiftip(pari_sp av, GEN x, long v)
419
{
420
  long i, lx = lg(x), ly;
421
  GEN y;
422
  if (!v || lx==2) return gerepileuptoleaf(av, x);
423
  ly = lx + v;
424
  (void)new_chunk(ly); /* check that result fits */
425
  x += lx; y = (GEN)av;
426
  for (i = 2; i<lx; i++) *--y = *--x;
427
  for (i = 0; i< v; i++) *--y = 0;
428
  y -= 2; y[0] = evaltyp(t_VECSMALL) | evallg(ly);
429
  return gc_const((pari_sp)y, y);
430
}
431

432
static GEN
433
F2x_to_int(GEN a, long na, long da, long bs)
434
{
435
  const long BIL = BITS_IN_LONG;
436
  GEN z, zs;
437
  long i,j,k,m;
438
  long lz = nbits2lg(1+da*bs);
439
  z = cgeti(lz); z[1] = evalsigne(1)|evallgefint(lz);
440
  zs = int_LSW(z); *zs = 0;
441
  for (i=0, k=2, m=0; i<na; i++)
442
    for (j=0; j<BIL; j++, m+=bs)
443
    {
444
      if (m >= BIL)
445
      {
446
        k++; if (k>=lz) break;
447
        zs = int_nextW(zs);
448
        *zs = 0;
449
        m -= BIL;
450
      }
451
      *zs |= ((a[i]>>j)&1UL)<<m;
452
    }
453
  return int_normalize(z,0);
454
}
455

456
static GEN
457
int_to_F2x(GEN x, long d, long bs)
458
{
459
  const long BIL = BITS_IN_LONG;
460
  long lx = lgefint(x), lz = nbits2lg(d+1);
461
  long i,j,k,m;
462
  GEN xs = int_LSW(x);
463
  GEN z = cgetg(lz, t_VECSMALL);
464
  z[1] = 0;
465
  for (k=2, i=2, m=0; k < lx; i++)
466
  {
467
    z[i] = 0;
468
    for (j=0; j<BIL; j++, m+=bs)
469
    {
470
      if (m >= BIL)
471
      {
472
        if (++k==lx) break;
473
        xs = int_nextW(xs);
474
        m -= BIL;
475
      }
476
      if ((*xs>>m)&1UL)
477
        z[i]|=1UL<<j;
478
    }
479
  }
480
  return F2x_renormalize(z,lz);
481
}
482

483
static GEN
484
F2x_mulspec_mulii(GEN a, GEN b, long na, long nb)
485
{
486
  long da = F2x_degreespec(a,na), db = F2x_degreespec(b,nb);
487
  long bs = expu(1 + maxss(da, db))+1;
488
  GEN A = F2x_to_int(a,na,da,bs);
489
  GEN B = F2x_to_int(b,nb,db,bs);
490
  GEN z = mulii(A,B);
491
  return int_to_F2x(z,da+db,bs);
492
}
493

494
/* fast product (Karatsuba) of polynomials a,b. These are not real GENs, a+2,
495
 * b+2 were sent instead. na, nb = number of terms of a, b.
496
 * Only c, c0, c1, c2 are genuine GEN.
497
 */
498
static GEN
499
F2x_mulspec(GEN a, GEN b, long na, long nb)
500
{
501
  GEN a0,c,c0;
502
  long n0, n0a, i, v = 0;
503
  pari_sp av;
504
  while (na && !a[0]) { a++; na-=1; v++; }
505
  while (nb && !b[0]) { b++; nb-=1; v++; }
506
  if (na < nb) swapspec(a,b, na,nb);
507
  if (!nb) return pol0_F2x(0);
508

509
  av = avma;
510
  if (na == 1)
511
    return F2x_shiftip(av, F2x_mul1(*a,*b), v);
512
  if (na < F2x_MUL_KARATSUBA_LIMIT)
513
    return F2x_shiftip(av, F2x_mulspec_basecase(a, b, na, nb), v);
514
  if (nb >= F2x_MUL_MULII_LIMIT)
515
    return F2x_shiftip(av, F2x_mulspec_mulii(a, b, na, nb), v);
516
  i=(na>>1); n0=na-i; na=i;
517
  a0=a+n0; n0a=n0;
518
  while (n0a && !a[n0a-1]) n0a--;
519

520
  if (nb > n0)
521
  {
522
    GEN b0,c1,c2;
523
    long n0b;
524

525
    nb -= n0; b0 = b+n0; n0b = n0;
526
    while (n0b && !b[n0b-1]) n0b--;
527
    c =  F2x_mulspec(a,b,n0a,n0b);
528
    c0 = F2x_mulspec(a0,b0,na,nb);
529

530
    c2 = F2x_addspec(a0,a,na,n0a);
531
    c1 = F2x_addspec(b0,b,nb,n0b);
532

533
    c1 = F2x_mul(c1,c2);
534
    c2 = F2x_add(c0,c);
535

536
    c2 = F2x_add(c1,c2);
537
    c0 = F2x_addshift(c0,c2,n0);
538
  }
539
  else
540
  {
541
    c  = F2x_mulspec(a,b,n0a,nb);
542
    c0 = F2x_mulspec(a0,b,na,nb);
543
  }
544
  c0 = F2x_addshift(c0,c,n0);
545
  return F2x_shiftip(av,c0, v);
546
}
547

548
GEN
549
F2x_mul(GEN x, GEN y)
550
{
551
  GEN z = F2x_mulspec(x+2,y+2, lgpol(x),lgpol(y));
552
  z[1] = x[1]; return z;
553
}
554

555
GEN
556
F2x_sqr(GEN x)
557
{
558
  const ulong sq[]={0,1,4,5,16,17,20,21,64,65,68,69,80,81,84,85};
559
  long i,ii,j,jj;
560
  long lx=lg(x), lz=2+((lx-2)<<1);
561
  GEN z;
562
  z = cgetg(lz, t_VECSMALL); z[1]=x[1];
563
  for (j=2,jj=2;j<lx;j++,jj++)
564
  {
565
    ulong x1=((ulong)x[j]&HIGHMASK)>>BITS_IN_HALFULONG;
566
    ulong x2=(ulong)x[j]&LOWMASK;
567
    z[jj]=0;
568
    if (x2)
569
      for(i=0,ii=0;i<BITS_IN_HALFULONG;i+=4,ii+=8)
570
        z[jj]|=sq[(x2>>i)&15UL]<<ii;
571
    z[++jj]=0;
572
    if (x1)
573
      for(i=0,ii=0;i<BITS_IN_HALFULONG;i+=4,ii+=8)
574
        z[jj]|=sq[(x1>>i)&15UL]<<ii;
575
  }
576
  return F2x_renormalize(z, lz);
577
}
578

579
static GEN
580
F2x_pow2n(GEN x, long n)
581
{
582
  long i;
583
  for(i=1;i<=n;i++)
584
    x = F2x_sqr(x);
585
  return x;
586
}
587

588
int
589
F2x_issquare(GEN x)
590
{
591
  const ulong mask = (ULONG_MAX/3UL)*2;
592
  ulong i, lx = lg(x);
593
  for (i=2; i<lx; i++)
594
    if ((x[i]&mask)) return 0;
595
  return 1;
596
}
597

598
/* Assume x is a perfect square */
599
GEN
600
F2x_sqrt(GEN x)
601
{
602
  const ulong sq[]={0,1,4,5,2,3,6,7,8,9,12,13,10,11,14,15};
603
  long i,ii,j,jj;
604
  long lx=lg(x), lz=2+((lx-1)>>1);
605
  GEN z;
606
  z = cgetg(lz, t_VECSMALL); z[1]=x[1];
607
  for (j=2,jj=2;jj<lz;j++,jj++)
608
  {
609
    ulong x2=x[j++];
610
    z[jj]=0;
611
    if (x2)
612
      for(i=0,ii=0;ii<BITS_IN_HALFULONG;i+=8,ii+=4)
613
      {
614
        ulong rl = (x2>>i)&15UL, rh = (x2>>(i+4))&15UL;
615
        z[jj]|=sq[rl|(rh<<1)]<<ii;
616
      }
617
    if (j<lx)
618
    {
619
      x2 = x[j];
620
      if (x2)
621
        for(i=0,ii=0;ii<BITS_IN_HALFULONG;i+=8,ii+=4)
622
        {
623
          ulong rl = (x2>>i)&15UL, rh = (x2>>(i+4))&15UL;
624
          z[jj]|=(sq[rl|(rh<<1)]<<ii)<<BITS_IN_HALFULONG;
625
        }
626
    }
627
  }
628
  return F2x_renormalize(z, lz);
629
}
630

631
static GEN
632
F2x_shiftneg(GEN y, ulong d)
633
{
634
  long db, dl=dvmdsBIL(d, &db);
635
  long i, ly = lg(y), lx = ly-dl;
636
  GEN x = cgetg(lx, t_VECSMALL);
637
  x[1] = y[1];
638
  if (db)
639
  {
640
    ulong dc=BITS_IN_LONG-db;
641
    ulong r=0;
642
    for(i=lx-1; i>=2; i--)
643
    {
644
      x[i] = (((ulong)y[i+dl])>>db)|r;
645
      r = ((ulong)y[i+dl])<<dc;
646
    }
647
  }
648
  else
649
    for(i=2; i<lx; i++)
650
      x[i] = y[i+dl];
651
  return F2x_renormalize(x,lx);
652
}
653

654
static GEN
655
F2x_shiftpos(GEN y, ulong d)
656
{
657
  long db, dl=dvmdsBIL(d, &db);
658
  long i, ly = lg(y), lx = ly+dl+(!!db);
659
  GEN x = cgetg(lx, t_VECSMALL);
660
  x[1] = y[1]; for(i=0; i<dl; i++) x[i+2] = 0;
661
  if (db)
662
  {
663
    ulong dc=BITS_IN_LONG-db;
664
    ulong r=0;
665
    for(i=2; i<ly; i++)
666
    {
667
      x[i+dl] = (((ulong)y[i])<<db)|r;
668
      r = ((ulong)y[i])>>dc;
669
    }
670
    x[i+dl] = r;
671
  }
672
  else
673
    for(i=2; i<ly; i++)
674
      x[i+dl] = y[i];
675
  return F2x_renormalize(x,lx);
676
}
677

678
GEN
679
F2x_shift(GEN y, long d)
680
{
681
  return d<0 ? F2x_shiftneg(y,-d): F2x_shiftpos(y,d);
682
}
683

684
#define F2x_recip2(pk,m) u = ((u&m)<<pk)|((u&(~m))>>pk);
685
#define F2x_recipu(pk) F2x_recip2(pk,((~0UL)/((1UL<<pk)+1)))
686

687
static ulong
688
F2x_recip1(ulong u)
689
{
690
  u = (u<<BITS_IN_HALFULONG)|(u>>BITS_IN_HALFULONG);
691
#ifdef LONG_IS_64BIT
692
  F2x_recipu(16);
693
#endif
694
  F2x_recipu(8);
695
  F2x_recipu(4);
696
  F2x_recipu(2);
697
  F2x_recipu(1);
698
  return u;
699
}
700

701
static GEN
702
F2x_recip_raw(GEN x)
703
{
704
  long i, l;
705
  GEN y = cgetg_copy(x,&l);
706
  y[1] = x[1];
707
  for (i=0; i<l-2; i++)
708
    uel(y,l-1-i) = F2x_recip1(uel(x,2+i));
709
  return y;
710
}
711

712
GEN
713
F2x_recip(GEN x)
714
{
715
  long lb = remsBIL(F2x_degree(x)+1);
716
  GEN y = F2x_recip_raw(x);
717
  if (lb) y = F2x_shiftneg(y,BITS_IN_LONG-lb);
718
  return y;
719
}
720

721
GEN
722
F2xn_red(GEN f, long n)
723
{
724
  GEN g;
725
  long i, dl, db, l;
726
  if (F2x_degree(f) < n) return zv_copy(f);
727
  dl = dvmdsBIL(n, &db); l = 2 + dl + (db>0);
728
  g = cgetg(l, t_VECSMALL);
729
  g[1] = f[1];
730
  for (i=2; i<l; i++)
731
    uel(g,i) = uel(f,i);
732
  if (db) uel(g,l-1) = uel(f,l-1)&((1UL<<db)-1);
733
  return F2x_renormalize(g, l);
734
}
735

736
static GEN
737
F2xn_mul(GEN a, GEN b, long n) { return F2xn_red(F2x_mul(a, b), n); }
738

739
static ulong
740
F2xn_inv_basecase1(ulong x)
741
{
742
  ulong u, v, w;
743
  long i;
744
  u = x>>1;
745
  v = (u&1UL)|2UL;
746
  w = u&v; w ^= w >> 1; v = (w&1UL)|(v<<1);
747
  w = u&v; w ^= w >> 2; w ^= w >> 1; v = (w&1UL)|(v<<1);
748
  w = u&v; w ^= w >> 2; w ^= w >> 1; v = (w&1UL)|(v<<1);
749
  for (i=1;i<=4;i++)
750
  { w = u&v; w ^= w >> 4; w ^= w >> 2; w ^= w >> 1; v = (w&1UL)|(v<<1); }
751
  for (i=1;i<=8;i++)
752
  { w = u&v; w ^= w >> 8; w ^= w >> 4; w ^= w >> 2; w ^= w >> 1;
753
    v = (w&1UL)|(v<<1); }
754
  for (i=1;i<=16;i++)
755
  { w = u&v; w ^= w >> 16; w ^= w >> 8; w ^= w >> 4; w ^= w >> 2; w ^= w >> 1;
756
    v = (w&1UL)|(v<<1); }
757
#ifdef LONG_IS_64BIT
758
  for (i=1; i<=32; i++)
759
  { w = u&v; w ^= w >> 32; w ^= w >> 16; w ^= w >> 8; w ^= w >> 4; w ^= w >> 2;
760
    w ^= w >> 1; v = (w&1UL)|(v<<1); }
761
#endif
762
  return (F2x_recip1(v)<<1) | 1UL;
763
}
764

765
static GEN
766
F2xn_inv1(GEN v, long e)
767
{
768
  ulong mask = e==BITS_IN_LONG ? -1UL: ((1UL<<e)-1);
769
  return mkvecsmall2(v[1],F2xn_inv_basecase1(uel(v,2))&mask);
770
}
771

772
GEN
773
F2xn_inv(GEN f, long e)
774
{
775
  pari_sp av = avma, av2;
776
  ulong mask;
777
  GEN W;
778
  long n=1;
779
  if (lg(f)==2) pari_err_INV("Flxn_inv",f);
780
  if (e <= BITS_IN_LONG) return F2xn_inv1(f, e);
781
  W = F2xn_inv1(f, BITS_IN_LONG);
782
  mask = quadratic_prec_mask(divsBIL(e+BITS_IN_LONG-1));
783
  n = BITS_IN_LONG;
784
  av2 = avma;
785
  for (;mask>1;)
786
  {
787
    GEN u, fr;
788
    long n2 = n;
789
    n<<=1; if (mask & 1) n--;
790
    mask >>= 1;
791
    fr = F2xn_red(f, n);
792
    u = F2x_shift(F2xn_mul(W, fr, n), -n2);
793
    W = F2x_add(W, F2x_shift(F2xn_mul(u, W, n-n2), n2));
794
    if (gc_needed(av2,2))
795
    {
796
      if(DEBUGMEM>1) pari_warn(warnmem,"F2xn_inv, e = %ld", n);
797
      W = gerepileupto(av2, W);
798
    }
799
  }
800
  return gerepileupto(av, F2xn_red(W,e));
801
}
802

803
GEN
804
F2x_get_red(GEN T)
805
{
806
  return T;
807
}
808

809
/* separate from F2x_divrem for maximal speed. */
810
GEN
811
F2x_rem(GEN x, GEN y)
812
{
813
  long dx,dy;
814
  long lx=lg(x);
815
  dy = F2x_degree(y); if (!dy) return pol0_F2x(x[1]);
816
  dx = F2x_degree_lg(x,lx);
817
  x  = F2x_copy(x);
818
  while (dx>=dy)
819
  {
820
    F2x_addshiftip(x,y,dx-dy);
821
    while (lx>2 && x[lx-1]==0) lx--;
822
    dx = F2x_degree_lg(x,lx);
823
  }
824
  return F2x_renormalize(x, lx);
825
}
826

827
GEN
828
F2x_divrem(GEN x, GEN y, GEN *pr)
829
{
830
  long dx, dy, dz, lx = lg(x), vs = x[1];
831
  GEN z;
832

833
  dy = F2x_degree(y);
834
  if (dy<0) pari_err_INV("F2x_divrem",y);
835
  if (pr == ONLY_REM) return F2x_rem(x, y);
836
  if (!dy)
837
  {
838
    z = F2x_copy(x);
839
    if (pr && pr != ONLY_DIVIDES) *pr = pol0_F2x(vs);
840
    return z;
841
  }
842
  dx = F2x_degree_lg(x,lx);
843
  dz = dx-dy;
844
  if (dz < 0)
845
  {
846
    if (pr == ONLY_DIVIDES) return dx < 0? F2x_copy(x): NULL;
847
    z = pol0_F2x(vs);
848
    if (pr) *pr = F2x_copy(x);
849
    return z;
850
  }
851
  z = zero_zv(lg(x)-lg(y)+2); z[1] = vs;
852
  x = F2x_copy(x);
853
  while (dx>=dy)
854
  {
855
    F2x_set(z,dx-dy);
856
    F2x_addshiftip(x,y,dx-dy);
857
    while (lx>2 && x[lx-1]==0) lx--;
858
    dx = F2x_degree_lg(x,lx);
859
  }
860
  z = F2x_renormalize(z, lg(z));
861
  if (!pr) { cgiv(x); return z; }
862
  x = F2x_renormalize(x, lx);
863
  if (pr == ONLY_DIVIDES) {
864
    if (lg(x) == 2) { cgiv(x); return z; }
865
    return gc_NULL((pari_sp)(z + lg(z)));
866
  }
867
  *pr = x; return z;
868
}
869

870
long
871
F2x_valrem(GEN x, GEN *Z)
872
{
873
  long v, v2, i, l=lg(x);
874
  GEN y;
875
  if (l==2) { *Z = F2x_copy(x); return LONG_MAX; }
876
  for (i=2; i<l && x[i]==0; i++) /*empty*/;
877
  v = i-2;
878
  v2 = (i < l)? vals(x[i]): 0;
879
  if (v+v2 == 0) { *Z = x; return 0; }
880
  l -= i-2;
881
  y = cgetg(l, t_VECSMALL); y[1] = x[1];
882
  if (v2 == 0)
883
    for (i=2; i<l; i++) y[i] = x[i+v];
884
  else if (l == 3)
885
    y[2] = ((ulong)x[2+v]) >> v2;
886
  else
887
  {
888
    const ulong sh = BITS_IN_LONG - v2;
889
    ulong r = x[2+v];
890
    for (i=3; i<l; i++)
891
    {
892
      y[i-1] = (x[i+v] << sh) | (r >> v2);
893
      r = x[i+v];
894
    }
895
    y[l-1] = r >> v2;
896
    (void)F2x_renormalize(y,l);
897
  }
898
  *Z = y; return (v << TWOPOTBITS_IN_LONG) + v2;
899
}
900

901
GEN
902
F2x_deflate(GEN x, long d)
903
{
904
  GEN y;
905
  long i,id, dy, dx = F2x_degree(x);
906
  if (d <= 1) return F2x_copy(x);
907
  if (dx < 0) return F2x_copy(x);
908
  dy = dx/d; /* dy+1 coefficients + 1 extra word for variable */
909
  y = zero_zv(nbits2lg(dy+1)-1); y[1] = x[1];
910
  for (i=id=0; i<=dy; i++,id+=d)
911
    if (F2x_coeff(x,id)) F2x_set(y, i);
912
  return y;
913
}
914

915
/* write p(X) = e(X^2) + Xo(X^2), shallow function */
916
void
917
F2x_even_odd(GEN p, GEN *pe, GEN *po)
918
{
919
  long n = F2x_degree(p), n0, n1, i;
920
  GEN p0, p1;
921

922
  if (n <= 0) { *pe = F2x_copy(p); *po = pol0_F2x(p[1]); return; }
923

924
  n0 = (n>>1)+1; n1 = n+1 - n0; /* n1 <= n0 <= n1+1 */
925
  p0 = zero_zv(nbits2lg(n0+1)-1); p0[1] = p[1];
926
  p1 = zero_zv(nbits2lg(n1+1)-1); p1[1] = p[1];
927
  for (i=0; i<n1; i++)
928
  {
929
    if (F2x_coeff(p,i<<1)) F2x_set(p0,i);
930
    if (F2x_coeff(p,1+(i<<1))) F2x_set(p1,i);
931
  }
932
  if (n1 != n0 && F2x_coeff(p,i<<1)) F2x_set(p0,i);
933
  *pe = F2x_renormalize(p0,lg(p0));
934
  *po = F2x_renormalize(p1,lg(p1));
935
}
936

937
GEN
938
F2x_deriv(GEN z)
939
{
940
  const ulong mask = ULONG_MAX/3UL;
941
  long i,l = lg(z);
942
  GEN x = cgetg(l, t_VECSMALL); x[1] = z[1];
943
  for (i=2; i<l; i++) x[i] = (((ulong)z[i])>>1)&mask;
944
  return F2x_renormalize(x,l);
945
}
946

947
GEN
948
F2x_gcd(GEN a, GEN b)
949
{
950
  pari_sp av = avma;
951
  if (lg(b) > lg(a)) swap(a, b);
952
  while (lgpol(b))
953
  {
954
    GEN c = F2x_rem(a,b);
955
    a = b; b = c;
956
    if (gc_needed(av,2))
957
    {
958
      if (DEBUGMEM>1) pari_warn(warnmem,"F2x_gcd (d = %ld)",F2x_degree(c));
959
      gerepileall(av,2, &a,&b);
960
    }
961
  }
962
  if (gc_needed(av,2)) a = gerepileuptoleaf(av, a);
963
  return a;
964
}
965

966
GEN
967
F2x_extgcd(GEN a, GEN b, GEN *ptu, GEN *ptv)
968
{
969
  pari_sp av=avma;
970
  GEN u,v,d,d1,v1;
971
  long vx = a[1];
972
  d = a; d1 = b;
973
  v = pol0_F2x(vx); v1 = pol1_F2x(vx);
974
  while (lgpol(d1))
975
  {
976
    GEN r, q = F2x_divrem(d,d1, &r);
977
    v = F2x_add(v,F2x_mul(q,v1));
978
    u=v; v=v1; v1=u;
979
    u=r; d=d1; d1=u;
980
    if (gc_needed(av,2))
981
    {
982
      if (DEBUGMEM>1) pari_warn(warnmem,"F2x_extgcd (d = %ld)",F2x_degree(d));
983
      gerepileall(av,5, &d,&d1,&u,&v,&v1);
984
    }
985
  }
986
  if (ptu) *ptu = F2x_div(F2x_add(d, F2x_mul(b,v)), a);
987
  *ptv = v;
988
  if (gc_needed(av,2)) gerepileall(av,ptu?3:2,&d,ptv,ptu);
989
  return d;
990
}
991

992
static GEN
993
F2x_halfgcd_i(GEN a, GEN b)
994
{
995
  pari_sp av=avma;
996
  GEN u,u1,v,v1;
997
  long vx = a[1];
998
  long n = (F2x_degree(a)+1)>>1;
999
  u1 = v = pol0_F2x(vx);
1000
  u = v1 = pol1_F2x(vx);
1001
  while (F2x_degree(b)>=n)
1002
  {
1003
    GEN r, q = F2x_divrem(a,b, &r);
1004
    a = b; b = r; swap(u,u1); swap(v,v1);
1005
    u1 = F2x_add(u1, F2x_mul(u, q));
1006
    v1 = F2x_add(v1, F2x_mul(v, q));
1007
    if (gc_needed(av,2))
1008
    {
1009
      if (DEBUGMEM>1) pari_warn(warnmem,"F2x_halfgcd (d = %ld)",F2x_degree(b));
1010
      gerepileall(av,6, &a,&b,&u1,&v1,&u,&v);
1011
    }
1012
  }
1013
  return gerepilecopy(av, mkmat2(mkcol2(u,u1), mkcol2(v,v1)));
1014
}
1015

1016
GEN
1017
F2x_halfgcd(GEN x, GEN y)
1018
{
1019
  pari_sp av;
1020
  GEN M,q,r;
1021
  if (F2x_degree(y)<F2x_degree(x)) return F2x_halfgcd_i(x,y);
1022
  av = avma;
1023
  q = F2x_divrem(y,x,&r);
1024
  M = F2x_halfgcd_i(x,r);
1025
  gcoeff(M,1,1) = F2x_add(gcoeff(M,1,1), F2x_mul(q, gcoeff(M,1,2)));
1026
  gcoeff(M,2,1) = F2x_add(gcoeff(M,2,1), F2x_mul(q, gcoeff(M,2,2)));
1027
  return gerepilecopy(av, M);
1028
}
1029

1030
GEN
1031
F2xq_mul(GEN x,GEN y,GEN pol)
1032
{
1033
  GEN z = F2x_mul(x,y);
1034
  return F2x_rem(z,pol);
1035
}
1036

1037
GEN
1038
F2xq_sqr(GEN x,GEN pol)
1039
{
1040
  GEN z = F2x_sqr(x);
1041
  return F2x_rem(z,pol);
1042
}
1043

1044
GEN
1045
F2xq_invsafe(GEN x, GEN T)
1046
{
1047
  GEN V, z = F2x_extgcd(get_F2x_mod(T), x, NULL, &V);
1048
  if (F2x_degree(z)) return NULL;
1049
  return V;
1050
}
1051

1052
GEN
1053
F2xq_inv(GEN x,GEN T)
1054
{
1055
  pari_sp av=avma;
1056
  GEN U = F2xq_invsafe(x, T);
1057
  if (!U) pari_err_INV("F2xq_inv", F2x_to_ZX(x));
1058
  return gerepileuptoleaf(av, U);
1059
}
1060

1061
GEN
1062
F2xq_div(GEN x,GEN y,GEN T)
1063
{
1064
  pari_sp av = avma;
1065
  return gerepileuptoleaf(av, F2xq_mul(x,F2xq_inv(y,T),T));
1066
}
1067

1068
static GEN
1069
_F2xq_red(void *E, GEN x) { return F2x_rem(x, (GEN)E); }
1070
static GEN
1071
_F2xq_add(void *E, GEN x, GEN y) { (void)E; return F2x_add(x,y); }
1072

1073
static GEN
1074
_F2xq_cmul(void *E, GEN P, long a, GEN x)
1075
{
1076
  GEN pol = (GEN) E;
1077
  return F2x_coeff(P,a) ? x: pol0_F2x(pol[1]);
1078
}
1079
static GEN
1080
_F2xq_sqr(void *E, GEN x) { return F2xq_sqr(x, (GEN) E); }
1081
static GEN
1082
_F2xq_mul(void *E, GEN x, GEN y) { return F2xq_mul(x,y, (GEN) E); }
1083

1084
static GEN
1085
_F2xq_one(void *E)
1086
{
1087
  GEN pol = (GEN) E;
1088
  return pol1_F2x(pol[1]);
1089
}
1090
static GEN
1091
_F2xq_zero(void *E)
1092
{
1093
  GEN pol = (GEN) E;
1094
  return pol0_F2x(pol[1]);
1095
}
1096

1097
GEN
1098
F2xq_pow(GEN x, GEN n, GEN pol)
1099
{
1100
  pari_sp av=avma;
1101
  GEN y;
1102

1103
  if (!signe(n)) return pol1_F2x(x[1]);
1104
  if (is_pm1(n)) /* +/- 1 */
1105
    return (signe(n) < 0)? F2xq_inv(x,pol): F2x_copy(x);
1106

1107
  if (signe(n) < 0) x = F2xq_inv(x,pol);
1108
  y = gen_pow_i(x, n, (void*)pol, &_F2xq_sqr, &_F2xq_mul);
1109
  return gerepilecopy(av, y);
1110
}
1111

1112
GEN
1113
F2xq_powu(GEN x, ulong n, GEN pol)
1114
{
1115
  pari_sp av=avma;
1116
  GEN y;
1117
  switch(n)
1118
  {
1119
    case 0: return pol1_F2x(x[1]);
1120
    case 1: return F2x_copy(x);
1121
    case 2: return F2xq_sqr(x,pol);
1122
  }
1123
  y = gen_powu_i(x, n, (void*)pol, &_F2xq_sqr, &_F2xq_mul);
1124
  return gerepilecopy(av, y);
1125
}
1126

1127
GEN
1128
F2xq_pow_init(GEN x, GEN n, long k,  GEN T)
1129
{
1130
  return gen_pow_init(x, n, k, (void*)T, &_F2xq_sqr, &_F2xq_mul);
1131
}
1132

1133
GEN
1134
F2xq_pow_table(GEN R, GEN n, GEN T)
1135
{
1136
  return gen_pow_table(R, n, (void*)T, &_F2xq_one, &_F2xq_mul);
1137
}
1138

1139
/* generates the list of powers of x of degree 0,1,2,...,l*/
1140
GEN
1141
F2xq_powers(GEN x, long l, GEN T)
1142
{
1143
  int use_sqr = 2*F2x_degree(x) >= get_F2x_degree(T);
1144
  return gen_powers(x, l, use_sqr, (void*)T, &_F2xq_sqr, &_F2xq_mul, &_F2xq_one);
1145
}
1146

1147
GEN
1148
F2xq_matrix_pow(GEN y, long n, long m, GEN P)
1149
{
1150
  return F2xV_to_F2m(F2xq_powers(y,m-1,P),n);
1151
}
1152

1153
GEN
1154
F2x_Frobenius(GEN T)
1155
{
1156
  return F2xq_sqr(polx_F2x(get_F2x_var(T)), T);
1157
}
1158

1159
GEN
1160
F2x_matFrobenius(GEN T)
1161
{
1162
  long n = get_F2x_degree(T);
1163
  return F2xq_matrix_pow(F2x_Frobenius(T), n, n, T);
1164
}
1165

1166
static struct bb_algebra F2xq_algebra = { _F2xq_red, _F2xq_add, _F2xq_add,
1167
              _F2xq_mul, _F2xq_sqr, _F2xq_one, _F2xq_zero};
1168

1169
GEN
1170
F2x_F2xqV_eval(GEN Q, GEN x, GEN T)
1171
{
1172
  long d = F2x_degree(Q);
1173
  return gen_bkeval_powers(Q,d,x,(void*)T,&F2xq_algebra,_F2xq_cmul);
1174
}
1175

1176
GEN
1177
F2x_F2xq_eval(GEN Q, GEN x, GEN T)
1178
{
1179
  long d = F2x_degree(Q);
1180
  int use_sqr = 2*F2x_degree(x) >= get_F2x_degree(T);
1181
  return gen_bkeval(Q, d, x, use_sqr, (void*)T, &F2xq_algebra, _F2xq_cmul);
1182
}
1183

1184
static GEN
1185
F2xq_autpow_sqr(void * T, GEN x) { return F2x_F2xq_eval(x, x, (GEN) T); }
1186

1187
static GEN
1188
F2xq_autpow_mul(void * T, GEN x, GEN y) { return F2x_F2xq_eval(x, y, (GEN) T); }
1189

1190
GEN
1191
F2xq_autpow(GEN x, long n, GEN T)
1192
{
1193
  if (n==0) return F2x_rem(polx_F2x(x[1]), T);
1194
  if (n==1) return F2x_rem(x, T);
1195
  return gen_powu(x,n,(void*)T,F2xq_autpow_sqr,F2xq_autpow_mul);
1196
}
1197

1198
ulong
1199
F2xq_trace(GEN x, GEN T)
1200
{
1201
  pari_sp av = avma;
1202
  long n = get_F2x_degree(T)-1;
1203
  GEN z = F2xq_mul(x, F2x_deriv(get_F2x_mod(T)), T);
1204
  return gc_ulong(av, F2x_degree(z) < n ? 0 : 1);
1205
}
1206

1207
GEN
1208
F2xq_conjvec(GEN x, GEN T)
1209
{
1210
  long i, l = 1+get_F2x_degree(T);
1211
  GEN z = cgetg(l,t_COL);
1212
  gel(z,1) = F2x_copy(x);
1213
  for (i=2; i<l; i++) gel(z,i) = F2xq_sqr(gel(z,i-1), T);
1214
  return z;
1215
}
1216

1217
static GEN
1218
_F2xq_pow(void *data, GEN x, GEN n)
1219
{
1220
  GEN pol = (GEN) data;
1221
  return F2xq_pow(x,n, pol);
1222
}
1223

1224
static GEN
1225
_F2xq_rand(void *data)
1226
{
1227
  pari_sp av=avma;
1228
  GEN pol = (GEN) data;
1229
  long d = F2x_degree(pol);
1230
  GEN z;
1231
  do
1232
  {
1233
    set_avma(av);
1234
    z = random_F2x(d,pol[1]);
1235
  } while (lgpol(z)==0);
1236
  return z;
1237
}
1238

1239
static GEN F2xq_easylog(void* E, GEN a, GEN g, GEN ord);
1240

1241
static const struct bb_group F2xq_star={_F2xq_mul,_F2xq_pow,_F2xq_rand,hash_GEN,F2x_equal,F2x_equal1,F2xq_easylog};
1242

1243
GEN
1244
F2xq_order(GEN a, GEN ord, GEN T)
1245
{
1246
  return gen_order(a,ord,(void*)T,&F2xq_star);
1247
}
1248

1249
static long
1250
F2x_is_smooth_squarefree(GEN f, long r)
1251
{
1252
  pari_sp av = avma;
1253
  long i, df = F2x_degree(f);
1254
  GEN sx, a;
1255
  if (!df) return 1;
1256
  a = sx = polx_F2x(f[1]);
1257
  for(i = 1;; i++)
1258
  {
1259
    long dg;
1260
    GEN g;
1261
    a = F2xq_sqr(a, f);
1262
    if (F2x_equal(a, sx)) return gc_long(av,1);
1263
    if (i==r) return gc_long(av,0);
1264
    g = F2x_gcd(f, F2x_add(a,sx));
1265
    dg = F2x_degree(g);
1266
    if (dg == df) return gc_long(av,1);
1267
    if (dg) { f = F2x_div(f, g); df -= dg; a = F2x_rem(a, f); }
1268
  }
1269
}
1270

1271
static long
1272
F2x_is_smooth(GEN g, long r)
1273
{
1274
  if (lgpol(g)==0) return 0;
1275
  while (1)
1276
  {
1277
    GEN f = F2x_gcd(g, F2x_deriv(g));
1278
    if (!F2x_is_smooth_squarefree(F2x_div(g, f), r)) return 0;
1279
    if (F2x_degree(f)==0) return 1;
1280
    g = F2x_issquare(f) ? F2x_sqrt(f): f;
1281
  }
1282
}
1283

1284
static GEN
1285
F2x_factorel(GEN h)
1286
{
1287
  GEN F = F2x_factor(h);
1288
  GEN F1 = gel(F, 1), F2 = gel(F, 2);
1289
  long i, l1 = lg(F1)-1;
1290
  GEN p2 = cgetg(l1+1, t_VECSMALL);
1291
  GEN e2 = cgetg(l1+1, t_VECSMALL);
1292
  for (i = 1; i <= l1; ++i)
1293
  {
1294
    p2[i] = mael(F1, i, 2);
1295
    e2[i] = F2[i];
1296
  }
1297
  return mkmat2(p2, e2);
1298
}
1299

1300
static GEN
1301
mkF2(ulong x, long v) { return mkvecsmall2(v, x); }
1302

1303
static GEN F2xq_log_Coppersmith_d(GEN W, GEN g, long r, long n, GEN T, GEN mo);
1304

1305
static GEN
1306
F2xq_log_from_rel(GEN W, GEN rel, long r, long n, GEN T, GEN m)
1307
{
1308
  pari_sp av = avma;
1309
  long vT = get_F2x_var(T);
1310
  GEN F = gel(rel,1), E = gel(rel,2), o = gen_0;
1311
  long i, l = lg(F);
1312
  for(i=1; i<l; i++)
1313
  {
1314
    GEN R = gel(W, F[i]);
1315
    if (signe(R)==0) /* Already failed */
1316
      return NULL;
1317
    else if (signe(R)<0) /* Not yet tested */
1318
    {
1319
      setsigne(gel(W,F[i]),0);
1320
      R = F2xq_log_Coppersmith_d(W, mkF2(F[i],vT), r, n, T, m);
1321
      if (!R) return NULL;
1322
    }
1323
    o = Fp_add(o, mulis(R, E[i]), m);
1324
  }
1325
  return gerepileuptoint(av, o);
1326
}
1327

1328
static GEN
1329
F2xq_log_Coppersmith_d(GEN W, GEN g, long r, long n, GEN T, GEN mo)
1330
{
1331
  pari_sp av = avma, av2;
1332
  long dT = get_F2x_degree(T), vT = get_F2x_var(T);
1333
  long dg = F2x_degree(g), k = r-1, m = maxss((dg-k)/2,0);
1334
  long i, j, l = dg-m, N;
1335
  GEN v = cgetg(k+m+1,t_MAT);
1336
  long h = dT>>n, d = dT-(h<<n);
1337
  GEN p1 = pol1_F2x(vT);
1338
  GEN R = F2x_add(F2x_shift(p1, dT), T);
1339
  GEN z = F2x_rem(F2x_shift(p1, h), g);
1340
  for(i=1; i<=k+m; i++)
1341
  {
1342
    gel(v,i) = F2x_to_F2v(F2x_shift(z,-l),m);
1343
    z = F2x_rem(F2x_shift(z,1),g);
1344
  }
1345
  v = F2m_ker(v);
1346
  for(i=1; i<=k; i++)
1347
    gel(v,i) = F2v_to_F2x(gel(v,i),vT);
1348
  N = 1<<k;
1349
  av2 = avma;
1350
  for (i=1; i<N; i++)
1351
  {
1352
    GEN p,q,qh,a,b;
1353
    set_avma(av2);
1354
    q = pol0_F2x(vT);
1355
    for(j=0; j<k; j++)
1356
      if (i&(1UL<<j))
1357
        q = F2x_add(q, gel(v,j+1));
1358
    qh= F2x_shift(q,h);
1359
    p = F2x_rem(qh,g);
1360
    b = F2x_add(F2x_mul(R, F2x_pow2n(q, n)), F2x_shift(F2x_pow2n(p, n), d));
1361
    if (lgpol(b)==0 || !F2x_is_smooth(b, r)) continue;
1362
    a = F2x_div(F2x_add(qh,p),g);
1363
    if (F2x_degree(F2x_gcd(a,q)) &&  F2x_degree(F2x_gcd(a,p))) continue;
1364
    if (!(lgpol(a)==0 || !F2x_is_smooth(a, r)))
1365
    {
1366
      GEN F = F2x_factorel(b);
1367
      GEN G = F2x_factorel(a);
1368
      GEN FG = vecsmall_concat(vecsmall_append(gel(F, 1), 2), gel(G, 1));
1369
      GEN E  = vecsmall_concat(vecsmall_append(gel(F, 2), -d),
1370
                               zv_z_mul(gel(G, 2),-(1L<<n)));
1371
      GEN R  = famatsmall_reduce(mkmat2(FG, E));
1372
      GEN l  = F2xq_log_from_rel(W, R, r, n, T, mo);
1373
      if (!l) continue;
1374
      l = Fp_div(l,int2n(n),mo);
1375
      if (dg <= r)
1376
      {
1377
        affii(l,gel(W,g[2]));
1378
        if (DEBUGLEVEL>1) err_printf("Found %lu\n", g[2]);
1379
      }
1380
      return gerepileuptoint(av, l);
1381
    }
1382
  }
1383
  return gc_NULL(av);
1384
}
1385

1386
static GEN
1387
F2xq_log_find_rel(GEN b, long r, GEN T, GEN *g, ulong *e)
1388
{
1389
  pari_sp av = avma;
1390
  while (1)
1391
  {
1392
    GEN M;
1393
    *g = F2xq_mul(*g, b, T); (*e)++;
1394
    M = F2x_halfgcd(*g,T);
1395
    if (F2x_is_smooth(gcoeff(M,1,1), r))
1396
    {
1397
      GEN z = F2x_add(F2x_mul(gcoeff(M,1,1),*g), F2x_mul(gcoeff(M,1,2),T));
1398
      if (F2x_is_smooth(z, r))
1399
      {
1400
        GEN F = F2x_factorel(z);
1401
        GEN G = F2x_factorel(gcoeff(M,1,1));
1402
        GEN rel = mkmat2(vecsmall_concat(gel(F, 1),gel(G, 1)),
1403
                         vecsmall_concat(gel(F, 2),zv_neg(gel(G, 2))));
1404
        gerepileall(av, 2, g, &rel);
1405
        return rel;
1406
      }
1407
    }
1408
    if (gc_needed(av,2))
1409
    {
1410
      if (DEBUGMEM>1) pari_warn(warnmem,"F2xq_log_find_rel");
1411
      *g = gerepileuptoleaf(av, *g);
1412
    }
1413
  }
1414
}
1415

1416
static GEN
1417
F2xq_log_Coppersmith_rec(GEN W, long r2, GEN a, long r, long n, GEN T, GEN m)
1418
{
1419
  long vT = get_F2x_var(T);
1420
  GEN b = polx_F2x(vT);
1421
  ulong AV = 0;
1422
  GEN g = a, bad = pol0_F2x(vT);
1423
  pari_timer ti;
1424
  while(1)
1425
  {
1426
    long i, l;
1427
    GEN V, F, E, Ao;
1428
    timer_start(&ti);
1429
    V = F2xq_log_find_rel(b, r2, T, &g, &AV);
1430
    if (DEBUGLEVEL>1) timer_printf(&ti,"%ld-smooth element",r2);
1431
    F = gel(V,1); E = gel(V,2);
1432
    l = lg(F);
1433
    Ao = gen_0;
1434
    for(i=1; i<l; i++)
1435
    {
1436
      GEN Fi = mkF2(F[i], vT);
1437
      GEN R;
1438
      if (F2x_degree(Fi) <= r)
1439
      {
1440
        if (signe(gel(W,F[i]))==0)
1441
          break;
1442
        else if (signe(gel(W,F[i]))<0)
1443
        {
1444
          setsigne(gel(W,F[i]),0);
1445
          R = F2xq_log_Coppersmith_d(W,Fi,r,n,T,m);
1446
        } else
1447
          R = gel(W,F[i]);
1448
      }
1449
      else
1450
      {
1451
        if (F2x_equal(Fi,bad)) break;
1452
        R = F2xq_log_Coppersmith_d(W,Fi,r,n,T,m);
1453
        if (!R) bad = Fi;
1454
      }
1455
      if (!R) break;
1456
      Ao = Fp_add(Ao, mulis(R, E[i]), m);
1457
    }
1458
    if (i==l) return subiu(Ao,AV);
1459
  }
1460
}
1461

1462
/* Coppersmith:
1463
 T*X^e = X^(h*2^n)-R
1464
 (u*x^h + v)^(2^n) = u^(2^n)*X^(h*2^n)+v^(2^n)
1465
 (u*x^h + v)^(2^n) = u^(2^n)*R+v^(2^n)
1466
*/
1467

1468
static GEN
1469
rel_Coppersmith(GEN u, GEN v, long h, GEN R, long r, long n, long d)
1470
{
1471
  GEN b, F, G, M;
1472
  GEN a = F2x_add(F2x_shift(u, h), v);
1473
  if (!F2x_is_smooth(a, r)) return NULL;
1474
  b = F2x_add(F2x_mul(R, F2x_pow2n(u, n)), F2x_shift(F2x_pow2n(v, n),d));
1475
  if (!F2x_is_smooth(b, r)) return NULL;
1476
  F = F2x_factorel(a);
1477
  G = F2x_factorel(b);
1478
  M = mkmat2(vecsmall_concat(gel(F, 1), vecsmall_append(gel(G, 1), 2)),
1479
             vecsmall_concat(zv_z_mul(gel(F, 2),1UL<<n), vecsmall_append(zv_neg(gel(G, 2)),d)));
1480
  return famatsmall_reduce(M);
1481
}
1482

1483
GEN
1484
F2xq_log_Coppersmith_worker(GEN u, long i, GEN V, GEN R)
1485
{
1486
  long r = V[1], h = V[2], n = V[3], d = V[4];
1487
  pari_sp ltop = avma;
1488
  GEN v = mkF2(0,u[1]);
1489
  GEN L = cgetg(2*i+1, t_VEC);
1490
  pari_sp av = avma;
1491
  long j;
1492
  long nbtest=0, rel = 1;
1493
  for(j=1; j<=i; j++)
1494
  {
1495
    v[2] = j;
1496
    set_avma(av);
1497
    if (F2x_degree(F2x_gcd(u,v))==0)
1498
    {
1499
      GEN z = rel_Coppersmith(u, v, h, R, r, n, d);
1500
      nbtest++;
1501
      if (z) { gel(L, rel++) = z; av = avma; }
1502
      if (i==j) continue;
1503
      z = rel_Coppersmith(v, u, h, R, r, n, d);
1504
      nbtest++;
1505
      if (z) { gel(L, rel++) = z; av = avma; }
1506
    }
1507
  }
1508
  setlg(L,rel);
1509
  return gerepilecopy(ltop, mkvec2(stoi(nbtest), L));
1510
}
1511

1512
static GEN
1513
F2xq_log_Coppersmith(long nbrel, long r, long n, GEN T)
1514
{
1515
  long dT = get_F2x_degree(T), vT = get_F2x_var(T);
1516
  long h = dT>>n, d = dT-(h<<n);
1517
  GEN R = F2x_add(F2x_shift(pol1_F2x(vT), dT), T);
1518
  GEN u = mkF2(0,vT);
1519
  long rel = 1, nbtest = 0;
1520
  GEN M = cgetg(nbrel+1, t_VEC);
1521
  long i = 0;
1522
  GEN worker = snm_closure(is_entry("_F2xq_log_Coppersmith_worker"),
1523
               mkvec2(mkvecsmall4(r, h, n, d), R));
1524
  struct pari_mt pt;
1525
  long running, pending = 0, stop=0;
1526
  mt_queue_start(&pt, worker);
1527
  if (DEBUGLEVEL) err_printf("Coppersmith (R = %ld): ",F2x_degree(R));
1528
  while ((running = !stop) || pending)
1529
  {
1530
    GEN L, done;
1531
    long j, l;
1532
    u[2] = i;
1533
    mt_queue_submit(&pt, 0, running ? mkvec2(u, stoi(i)): NULL);
1534
    done = mt_queue_get(&pt, NULL, &pending);
1535
    if (!done) continue;
1536
    L = gel(done, 2); nbtest += itos(gel(done,1));
1537
    l = lg(L);
1538
    if (l > 1)
1539
    {
1540
      for (j=1; j<l; j++)
1541
      {
1542
        if (rel>nbrel) break;
1543
        gel(M,rel++) = gel(L,j);
1544
        if (DEBUGLEVEL && (rel&511UL)==0)
1545
          err_printf("%ld%%[%ld] ",rel*100/nbrel,i);
1546
      }
1547
    }
1548
    if (rel>nbrel) stop=1;
1549
    i++;
1550
  }
1551
  mt_queue_end(&pt);
1552
  if (DEBUGLEVEL) err_printf(": %ld tests\n", nbtest);
1553
  return M;
1554
}
1555

1556
static GEN
1557
smallirred_F2x(ulong n, long sv)
1558
{
1559
  GEN a = zero_zv(nbits2lg(n+1)-1);
1560
  a[1] = sv; F2x_set(a,n); a[2]++;
1561
  while (!F2x_is_irred(a)) a[2]+=2;
1562
  return a;
1563
}
1564

1565
static GEN
1566
check_kernel(long N, GEN M, long nbi, GEN T, GEN m)
1567
{
1568
  pari_sp av = avma;
1569
  long dT = get_F2x_degree(T), vT = get_F2x_var(T);
1570
  GEN K = FpMs_leftkernel_elt(M, N, m);
1571
  long i, f=0, tbs;
1572
  long l = lg(K), lm = lgefint(m);
1573
  GEN idx = diviiexact(int2um1(dT), m);
1574
  GEN g = F2xq_pow(polx_F2x(vT), idx, T);
1575
  GEN tab;
1576
  pari_timer ti;
1577
  if (DEBUGLEVEL) timer_start(&ti);
1578
  K = FpC_Fp_mul(K, Fp_inv(gel(K,2), m), m);
1579
  tbs = maxss(1, expu(nbi/expi(m)));
1580
  tab = F2xq_pow_init(g, int2n(dT), tbs, T);
1581
  for(i=1; i<l; i++)
1582
  {
1583
    GEN k = gel(K,i);
1584
    if (signe(k)==0 || !F2x_equal(F2xq_pow_table(tab, k, T),
1585
                                  F2xq_pow(mkF2(i,vT), idx, T)))
1586
      gel(K,i) = cgetineg(lm);
1587
    else
1588
      f++;
1589
  }
1590
  if (DEBUGLEVEL) timer_printf(&ti,"found %ld/%ld logs", f, nbi);
1591
  return gerepileupto(av, K);
1592
}
1593

1594
static GEN
1595
F2xq_log_index(GEN a0, GEN b0, GEN m, GEN T0)
1596
{
1597
  pari_sp av = avma;
1598
  GEN  M, S, a, b, Ao=NULL, Bo=NULL, W, e;
1599
  pari_timer ti;
1600
  long n = F2x_degree(T0), r = (long) (sqrt((double) 2*n))-(n>100);
1601
  GEN T = smallirred_F2x(n,T0[1]);
1602
  long d = 2, r2 = 3*r/2, d2 = 2;
1603
  long N = (1UL<<(r+1))-1UL;
1604
  long nbi = itos(ffsumnbirred(gen_2, r)), nbrel=nbi*5/4;
1605
  if (DEBUGLEVEL)
1606
  {
1607
    err_printf("F2xq_log: Parameters r=%ld r2=%ld\n", r,r2);
1608
    err_printf("F2xq_log: Size FB=%ld rel. needed=%ld\n", nbi, nbrel);
1609
    timer_start(&ti);
1610
  }
1611
  S = Flx_to_F2x(Flx_ffisom(F2x_to_Flx(T0),F2x_to_Flx(T),2));
1612
  a = F2x_F2xq_eval(a0, S, T);
1613
  b = F2x_F2xq_eval(b0, S, T);
1614
  if (DEBUGLEVEL) timer_printf(&ti,"model change");
1615
  M = F2xq_log_Coppersmith(nbrel,r,d,T);
1616
  if(DEBUGLEVEL)
1617
    timer_printf(&ti,"relations");
1618
  W = check_kernel(N, M, nbi, T, m);
1619
  timer_start(&ti);
1620
  Ao = F2xq_log_Coppersmith_rec(W, r2, a, r, d2, T, m);
1621
  if (DEBUGLEVEL) timer_printf(&ti,"smooth element");
1622
  Bo = F2xq_log_Coppersmith_rec(W, r2, b, r, d2, T, m);
1623
  if (DEBUGLEVEL) timer_printf(&ti,"smooth generator");
1624
  e = Fp_div(Ao, Bo, m);
1625
  if (!F2x_equal(F2xq_pow(b0,e,T0),a0)) pari_err_BUG("F2xq_log");
1626
  return gerepileupto(av, e);
1627
}
1628

1629
static GEN
1630
F2xq_easylog(void* E, GEN a, GEN g, GEN ord)
1631
{
1632
  if (F2x_equal1(a)) return gen_0;
1633
  if (F2x_equal(a,g)) return gen_1;
1634
  if (typ(ord)!=t_INT) return NULL;
1635
  if (expi(ord)<28) return NULL;
1636
  return F2xq_log_index(a,g,ord,(GEN)E);
1637
}
1638

1639
GEN
1640
F2xq_log(GEN a, GEN g, GEN ord, GEN T)
1641
{
1642
  GEN z, v = get_arith_ZZM(ord);
1643
  ord = mkvec2(gel(v,1),ZM_famat_limit(gel(v,2),int2n(28)));
1644
  z = gen_PH_log(a,g,ord,(void*)T,&F2xq_star);
1645
  return z? z: cgetg(1,t_VEC);
1646
}
1647

1648
GEN
1649
F2xq_Artin_Schreier(GEN a, GEN T)
1650
{
1651
  pari_sp ltop=avma;
1652
  long j,N = get_F2x_degree(T), vT = get_F2x_var(T);
1653
  GEN Q = F2x_matFrobenius(T);
1654
  for (j=1; j<=N; j++)
1655
    F2m_flip(Q,j,j);
1656
  F2v_add_inplace(gel(Q,1),a);
1657
  Q = F2m_ker_sp(Q,0);
1658
  if (lg(Q)!=2) return NULL;
1659
  Q = gel(Q,1);
1660
  Q[1] = vT;
1661
  return gerepileuptoleaf(ltop, F2x_renormalize(Q, lg(Q)));
1662
}
1663

1664
GEN
1665
F2xq_sqrt_fast(GEN c, GEN sqx, GEN T)
1666
{
1667
  GEN c0, c1;
1668
  F2x_even_odd(c, &c0, &c1);
1669
  return F2x_add(c0, F2xq_mul(c1, sqx, T));
1670
}
1671

1672
static int
1673
F2x_is_x(GEN a) { return lg(a)==3 && a[2]==2; }
1674

1675
GEN
1676
F2xq_sqrt(GEN a, GEN T)
1677
{
1678
  pari_sp av = avma;
1679
  long n = get_F2x_degree(T), vT = get_F2x_var(T);
1680
  GEN sqx;
1681
  if (n==1) return F2x_copy(a);
1682
  if (n==2) return F2xq_sqr(a,T);
1683
  sqx = F2xq_autpow(mkF2(4, vT), n-1, T);
1684
  return gerepileuptoleaf(av, F2x_is_x(a)? sqx: F2xq_sqrt_fast(a,sqx,T));
1685
}
1686

1687
GEN
1688
F2xq_sqrtn(GEN a, GEN n, GEN T, GEN *zeta)
1689
{
1690
  long dT = get_F2x_degree(T), vT = get_F2x_var(T);
1691
  if (!lgpol(a))
1692
  {
1693
    if (signe(n) < 0) pari_err_INV("F2xq_sqrtn",a);
1694
    if (zeta)
1695
      *zeta=pol1_F2x(vT);
1696
    return pol0_F2x(vT);
1697
  }
1698
  return gen_Shanks_sqrtn(a, n, int2um1(dT), zeta, (void*)T, &F2xq_star);
1699
}
1700

1701
GEN
1702
gener_F2xq(GEN T, GEN *po)
1703
{
1704
  long i, j, vT = get_F2x_var(T), f = get_F2x_degree(T);
1705
  pari_sp av0 = avma, av;
1706
  GEN g, L2, o, q;
1707

1708
  if (f == 1) {
1709
    if (po) *po = mkvec2(gen_1, trivial_fact());
1710
    return pol1_F2x(vT);
1711
  }
1712
  q = int2um1(f);
1713
  o = factor_pn_1(gen_2,f);
1714
  L2 = leafcopy( gel(o, 1) );
1715
  for (i = j = 1; i < lg(L2); i++)
1716
  {
1717
    if (absequaliu(gel(L2,i),2)) continue;
1718
    gel(L2,j++) = diviiexact(q, gel(L2,i));
1719
  }
1720
  setlg(L2, j);
1721
  for (av = avma;; set_avma(av))
1722
  {
1723
    g = random_F2x(f, vT);
1724
    if (F2x_degree(g) < 1) continue;
1725
    for (i = 1; i < j; i++)
1726
    {
1727
      GEN a = F2xq_pow(g, gel(L2,i), T);
1728
      if (F2x_equal1(a)) break;
1729
    }
1730
    if (i == j) break;
1731
  }
1732
  if (!po) g = gerepilecopy(av0, g);
1733
  else {
1734
    *po = mkvec2(int2um1(f), o);
1735
    gerepileall(av0, 2, &g, po);
1736
  }
1737
  return g;
1738
}
1739

1740
static GEN
1741
_F2xq_neg(void *E, GEN x) { (void) E; return F2x_copy(x); }
1742
static GEN
1743
_F2xq_rmul(void *E, GEN x, GEN y) { (void) E; return F2x_mul(x,y); }
1744
static GEN
1745
_F2xq_inv(void *E, GEN x) { return F2xq_inv(x, (GEN) E); }
1746
static int
1747
_F2xq_equal0(GEN x) { return lgpol(x)==0; }
1748
static GEN
1749
_F2xq_s(void *E, long x)
1750
{ GEN T = (GEN) E;
1751
  long v = get_F2x_var(T);
1752
  return odd(x)? pol1_F2x(v): pol0_F2x(v);
1753
}
1754

1755
static const struct bb_field F2xq_field={_F2xq_red,_F2xq_add,_F2xq_rmul,_F2xq_neg,
1756
                                         _F2xq_inv,_F2xq_equal0,_F2xq_s};
1757

1758
const struct bb_field *get_F2xq_field(void **E, GEN T)
1759
{
1760
  *E = (void *) T;
1761
  return &F2xq_field;
1762
}
1763

1764
/***********************************************************************/
1765
/**                                                                   **/
1766
/**                               F2xV                                **/
1767
/**                                                                   **/
1768
/***********************************************************************/
1769
/* F2xV are t_VEC with F2x coefficients. */
1770

1771
GEN
1772
FlxC_to_F2xC(GEN x) { pari_APPLY_type(t_COL, Flx_to_F2x(gel(x,i))) }
1773
GEN
1774
F2xC_to_FlxC(GEN x) { pari_APPLY_type(t_COL, F2x_to_Flx(gel(x,i))) }
1775
GEN
1776
F2xC_to_ZXC(GEN x) { pari_APPLY_type(t_COL, F2x_to_ZX(gel(x,i))) }
1777
GEN
1778
F2xV_to_F2m(GEN x, long n) { pari_APPLY_type(t_MAT, F2x_to_F2v(gel(x,i), n)) }
1779

1780
void
1781
F2xV_to_FlxV_inplace(GEN v)
1782
{
1783
  long i, l = lg(v);
1784
  for(i = 1; i < l;i++) gel(v,i) = F2x_to_Flx(gel(v,i));
1785
}
1786
void
1787
F2xV_to_ZXV_inplace(GEN v)
1788
{
1789
  long i, l = lg(v);
1790
  for(i = 1; i < l; i++) gel(v,i)= F2x_to_ZX(gel(v,i));
1791
}
1792

1793
/***********************************************************************/
1794
/**                                                                   **/
1795
/**                             F2xX                                  **/
1796
/**                                                                   **/
1797
/***********************************************************************/
1798

1799
GEN
1800
F2xX_renormalize(GEN /*in place*/ x, long lx)
1801
{ return FlxX_renormalize(x, lx); }
1802

1803
GEN
1804
pol1_F2xX(long v, long sv) { return pol1_FlxX(v, sv); }
1805

1806
GEN
1807
polx_F2xX(long v, long sv) { return polx_FlxX(v, sv); }
1808

1809
long
1810
F2xY_degreex(GEN b)
1811
{
1812
  long deg = 0, i;
1813
  if (!signe(b)) return -1;
1814
  for (i = 2; i < lg(b); ++i)
1815
    deg = maxss(deg, F2x_degree(gel(b, i)));
1816
  return deg;
1817
}
1818

1819
GEN
1820
FlxX_to_F2xX(GEN B)
1821
{
1822
  long lb=lg(B);
1823
  long i;
1824
  GEN b=cgetg(lb,t_POL);
1825
  b[1]=evalsigne(1)|(((ulong)B[1])&VARNBITS);
1826
  for (i=2; i<lb; i++)
1827
    gel(b,i) = Flx_to_F2x(gel(B,i));
1828
  return F2xX_renormalize(b, lb);
1829
}
1830

1831
GEN
1832
ZXX_to_F2xX(GEN B, long v)
1833
{
1834
  long lb=lg(B);
1835
  long i;
1836
  GEN b=cgetg(lb,t_POL);
1837
  b[1]=evalsigne(1)|(((ulong)B[1])&VARNBITS);
1838
  for (i=2; i<lb; i++)
1839
    switch (typ(gel(B,i)))
1840
    {
1841
    case t_INT:
1842
      gel(b,i) = Z_to_F2x(gel(B,i), evalvarn(v));
1843
      break;
1844
    case t_POL:
1845
      gel(b,i) = ZX_to_F2x(gel(B,i));
1846
      break;
1847
    }
1848
  return F2xX_renormalize(b, lb);
1849
}
1850

1851
GEN
1852
F2xX_to_FlxX(GEN B)
1853
{
1854
  long i, lb = lg(B);
1855
  GEN b = cgetg(lb,t_POL);
1856
  for (i=2; i<lb; i++)
1857
    gel(b,i) = F2x_to_Flx(gel(B,i));
1858
  b[1] = B[1]; return b;
1859
}
1860

1861
GEN
1862
F2xX_to_ZXX(GEN B)
1863
{
1864
  long i, lb = lg(B);
1865
  GEN b = cgetg(lb,t_POL);
1866
  for (i=2; i<lb; i++)
1867
  {
1868
    GEN c = gel(B,i);
1869
    gel(b,i) = lgpol(c) ?  F2x_equal1(c) ? gen_1 : F2x_to_ZX(c) : gen_0;
1870
  }
1871
  b[1] = B[1]; return b;
1872
}
1873

1874
GEN
1875
F2xX_deriv(GEN z)
1876
{
1877
  long i,l = lg(z)-1;
1878
  GEN x;
1879
  if (l < 2) l = 2;
1880
  x = cgetg(l, t_POL); x[1] = z[1];
1881
  for (i=2; i<l; i++) gel(x,i) = odd(i) ? pol0_F2x(mael(z,i+1,1)): gel(z,i+1);
1882
  return F2xX_renormalize(x,l);
1883
}
1884

1885
static GEN
1886
F2xX_addspec(GEN x, GEN y, long lx, long ly)
1887
{
1888
  long i,lz;
1889
  GEN z;
1890
  if (ly>lx) swapspec(x,y, lx,ly);
1891
  lz = lx+2; z = cgetg(lz, t_POL);
1892
  for (i=0; i<ly; i++) gel(z,i+2) = F2x_add(gel(x,i), gel(y,i));
1893
  for (   ; i<lx; i++) gel(z,i+2) = F2x_copy(gel(x,i));
1894
  z[1] = 0; return F2xX_renormalize(z, lz);
1895
}
1896

1897
GEN
1898
F2xX_add(GEN x, GEN y)
1899
{
1900
  long i,lz;
1901
  GEN z;
1902
  long lx=lg(x);
1903
  long ly=lg(y);
1904
  if (ly>lx) swapspec(x,y, lx,ly);
1905
  lz = lx; z = cgetg(lz, t_POL); z[1]=x[1];
1906
  for (i=2; i<ly; i++) gel(z,i) = F2x_add(gel(x,i), gel(y,i));
1907
  for (   ; i<lx; i++) gel(z,i) = F2x_copy(gel(x,i));
1908
  return F2xX_renormalize(z, lz);
1909
}
1910

1911
GEN
1912
F2xX_F2x_add(GEN x, GEN y)
1913
{
1914
  long i, lz = lg(y);
1915
  GEN z;
1916
  if (signe(y) == 0) return scalarpol(x, varn(y));
1917
  z = cgetg(lz,t_POL); z[1] = y[1];
1918
  gel(z,2) = F2x_add(gel(y,2), x);
1919
  if (lz == 3) z = F2xX_renormalize(z,lz);
1920
  else
1921
    for(i=3;i<lz;i++) gel(z,i) = F2x_copy(gel(y,i));
1922
  return z;
1923
}
1924

1925
GEN
1926
F2xX_F2x_mul(GEN P, GEN U)
1927
{
1928
  long i, lP = lg(P);
1929
  GEN res = cgetg(lP,t_POL);
1930
  res[1] = P[1];
1931
  for(i=2; i<lP; i++)
1932
    gel(res,i) = F2x_mul(U,gel(P,i));
1933
  return F2xX_renormalize(res, lP);
1934
}
1935

1936
GEN
1937
F2xY_F2xqV_evalx(GEN P, GEN x, GEN T)
1938
{
1939
  long i, lP = lg(P);
1940
  GEN res = cgetg(lP,t_POL);
1941
  res[1] = P[1];
1942
  for(i=2; i<lP; i++)
1943
    gel(res,i) = F2x_F2xqV_eval(gel(P,i), x, T);
1944
  return F2xX_renormalize(res, lP);
1945
}
1946

1947
GEN
1948
F2xY_F2xq_evalx(GEN P, GEN x, GEN T)
1949
{
1950
  pari_sp av = avma;
1951
  long n = brent_kung_optpow(get_F2x_degree(T)-1,lgpol(P),1);
1952
  GEN xp = F2xq_powers(x, n, T);
1953
  return gerepileupto(av, F2xY_F2xqV_evalx(P, xp, T));
1954
}
1955

1956
static GEN
1957
F2xX_to_Kronecker_spec(GEN P, long n, long d)
1958
{
1959
  long i, k, l, N = 2*d + 1;
1960
  long dP = n+1;
1961
  GEN x;
1962
  if (n == 0) return pol0_Flx(P[1]&VARNBITS);
1963
  l = nbits2nlong(N*dP+d+1);
1964
  x = zero_zv(l+1);
1965
  for (k=i=0; i<n; i++, k+=N)
1966
  {
1967
    GEN c = gel(P,i);
1968
    F2x_addshiftip(x, c, k);
1969
  }
1970
  x[1] = P[1]&VARNBITS; return F2x_renormalize(x, l+2);
1971
}
1972

1973
GEN
1974
F2xX_to_Kronecker(GEN P, long d)
1975
{
1976
  long i, k, l, N = 2*d + 1;
1977
  long dP = degpol(P);
1978
  GEN x;
1979
  if (dP < 0) return pol0_Flx(P[1]&VARNBITS);
1980
  l = nbits2nlong(N*dP+d+1);
1981
  x = zero_zv(l+1);
1982
  for (k=i=0; i<=dP; i++, k+=N)
1983
  {
1984
    GEN c = gel(P,i+2);
1985
    F2x_addshiftip(x, c, k);
1986
  }
1987
  x[1] = P[1]&VARNBITS; return F2x_renormalize(x, l+2);
1988
}
1989

1990
static GEN
1991
F2x_slice(GEN x, long n, long d)
1992
{
1993
  ulong ib, il=dvmduBIL(n, &ib);
1994
  ulong db, dl=dvmduBIL(d, &db);
1995
  long lN = dl+2+(db?1:0);
1996
  GEN t = cgetg(lN,t_VECSMALL);
1997
  t[1] = x[1];
1998
  if (ib)
1999
  {
2000
    ulong i, ic = BITS_IN_LONG-ib;
2001
    ulong r = uel(x,2+il)>>ib;
2002
    for(i=0; i<dl; i++)
2003
    {
2004
      uel(t,2+i) = (uel(x,3+il+i)<<ic)|r;
2005
      r = uel(x,3+il+i)>>ib;
2006
    }
2007
    if (db)
2008
      uel(t,2+i) = (uel(x,3+il+i)<<ic)|r;
2009
  }
2010
  else
2011
  {
2012
    long i;
2013
    for(i=2; i<lN; i++)
2014
      uel(t,i) = uel(x,il+i);
2015
  }
2016
  if (db) uel(t,lN-1) &= (1UL<<db)-1;
2017
  return F2x_renormalize(t, lN);
2018
}
2019

2020
GEN
2021
Kronecker_to_F2xqX(GEN z, GEN T)
2022
{
2023
  long lz = F2x_degree(z)+1;
2024
  long i, j, N = get_F2x_degree(T)*2 + 1;
2025
  long lx = lz / (N-2);
2026
  GEN x = cgetg(lx+3,t_POL);
2027
  x[1] = z[1];
2028
  for (i=0, j=2; i<lz; i+=N, j++)
2029
  {
2030
    GEN t = F2x_slice(z,i,minss(lz-i,N));
2031
    t[1] = T[1];
2032
    gel(x,j) = F2x_rem(t, T);
2033
  }
2034
  return F2xX_renormalize(x, j);
2035
}
2036

2037
GEN
2038
F2xX_to_F2xC(GEN x, long N, long sv)
2039
{
2040
  long i, l;
2041
  GEN z;
2042
  l = lg(x)-1; x++;
2043
  if (l > N+1) l = N+1; /* truncate higher degree terms */
2044
  z = cgetg(N+1,t_COL);
2045
  for (i=1; i<l ; i++) gel(z,i) = gel(x,i);
2046
  for (   ; i<=N; i++) gel(z,i) = pol0_F2x(sv);
2047
  return z;
2048
}
2049

2050
GEN
2051
F2xXV_to_F2xM(GEN v, long n, long sv)
2052
{
2053
  long j, N = lg(v);
2054
  GEN y = cgetg(N, t_MAT);
2055
  for (j=1; j<N; j++) gel(y,j) = F2xX_to_F2xC(gel(v,j), n, sv);
2056
  return y;
2057
}
2058

2059
/***********************************************************************/
2060
/**                                                                   **/
2061
/**                             F2xXV/F2xXC                           **/
2062
/**                                                                   **/
2063
/***********************************************************************/
2064

2065
GEN
2066
FlxXC_to_F2xXC(GEN x) { pari_APPLY_type(t_COL, FlxX_to_F2xX(gel(x,i))); }
2067
GEN
2068
F2xXC_to_ZXXC(GEN x) { pari_APPLY_type(t_COL, F2xX_to_ZXX(gel(x,i))); }
2069

2070
/***********************************************************************/
2071
/**                                                                   **/
2072
/**                             F2xqX                                 **/
2073
/**                                                                   **/
2074
/***********************************************************************/
2075

2076
static GEN
2077
get_F2xqX_red(GEN T, GEN *B)
2078
{
2079
  if (typ(T)!=t_VEC) { *B=NULL; return T; }
2080
  *B = gel(T,1); return gel(T,2);
2081
}
2082

2083
GEN
2084
random_F2xqX(long d1, long v, GEN T)
2085
{
2086
  long dT = get_F2x_degree(T), vT = get_F2x_var(T);
2087
  long i, d = d1+2;
2088
  GEN y = cgetg(d,t_POL); y[1] = evalsigne(1) | evalvarn(v);
2089
  for (i=2; i<d; i++) gel(y,i) = random_F2x(dT, vT);
2090
  return FlxX_renormalize(y,d);
2091
}
2092

2093
GEN
2094
F2xqX_red(GEN z, GEN T)
2095
{
2096
  GEN res;
2097
  long i, l = lg(z);
2098
  res = cgetg(l,t_POL); res[1] = z[1];
2099
  for(i=2;i<l;i++) gel(res,i) = F2x_rem(gel(z,i),T);
2100
  return F2xX_renormalize(res,l);
2101
}
2102

2103
GEN
2104
F2xqX_F2xq_mul(GEN P, GEN U, GEN T)
2105
{
2106
  long i, lP = lg(P);
2107
  GEN res = cgetg(lP,t_POL);
2108
  res[1] = P[1];
2109
  for(i=2; i<lP; i++)
2110
    gel(res,i) = F2xq_mul(U,gel(P,i), T);
2111
  return F2xX_renormalize(res, lP);
2112
}
2113

2114
GEN
2115
F2xqX_F2xq_mul_to_monic(GEN P, GEN U, GEN T)
2116
{
2117
  long i, lP = lg(P);
2118
  GEN res = cgetg(lP,t_POL);
2119
  res[1] = P[1];
2120
  for(i=2; i<lP-1; i++) gel(res,i) = F2xq_mul(U,gel(P,i), T);
2121
  gel(res,lP-1) = pol1_F2x(T[1]);
2122
  return F2xX_renormalize(res, lP);
2123
}
2124

2125
GEN
2126
F2xqX_normalize(GEN z, GEN T)
2127
{
2128
  GEN p1 = leading_coeff(z);
2129
  if (!lgpol(z) || (!degpol(p1) && p1[1] == 1)) return z;
2130
  return F2xqX_F2xq_mul_to_monic(z, F2xq_inv(p1,T), T);
2131
}
2132

2133
GEN
2134
F2xqX_mul(GEN x, GEN y, GEN T)
2135
{
2136
  pari_sp ltop=avma;
2137
  GEN z, kx, ky;
2138
  long d = get_F2x_degree(T);
2139
  kx= F2xX_to_Kronecker(x, d);
2140
  ky= F2xX_to_Kronecker(y, d);
2141
  z = F2x_mul(ky, kx);
2142
  z = Kronecker_to_F2xqX(z, T);
2143
  return gerepileupto(ltop, z);
2144
}
2145

2146
static GEN
2147
F2xqX_mulspec(GEN x, GEN y, GEN T, long nx, long ny)
2148
{
2149
  pari_sp ltop=avma;
2150
  GEN z, kx, ky;
2151
  long dT = get_F2x_degree(T);
2152
  kx= F2xX_to_Kronecker_spec(x, nx, dT);
2153
  ky= F2xX_to_Kronecker_spec(y, ny, dT);
2154
  z = F2x_mul(ky, kx);
2155
  z = Kronecker_to_F2xqX(z,T);
2156
  return gerepileupto(ltop,z);
2157
}
2158

2159
GEN
2160
F2xqX_sqr(GEN x, GEN T)
2161
{
2162
  long d = degpol(x), l = 2*d+3;
2163
  GEN z;
2164
  if (!signe(x)) return pol_0(varn(x));
2165
  z = cgetg(l,t_POL);
2166
  z[1] = x[1];
2167
  if (d > 0)
2168
  {
2169
    GEN u = pol0_F2x(T[1]);
2170
    long i,j;
2171
    for (i=2,j=2; i<d+2; i++,j+=2)
2172
    {
2173
      gel(z, j) = F2xq_sqr(gel(x, i), T);
2174
      gel(z, j+1) = u;
2175
    }
2176
  }
2177
  gel(z, 2+2*d) = F2xq_sqr(gel(x, 2+d), T);
2178
  return FlxX_renormalize(z, l);
2179
}
2180

2181
static GEN
2182
F2xqX_divrem_basecase(GEN x, GEN y, GEN T, GEN *pr)
2183
{
2184
  long vx, dx, dy, dz, i, j, sx, lr;
2185
  pari_sp av0, av, tetpil;
2186
  GEN z,p1,rem,lead;
2187

2188
  if (!signe(y)) pari_err_INV("F2xqX_divrem",y);
2189
  vx=varn(x); dy=degpol(y); dx=degpol(x);
2190
  if (dx < dy)
2191
  {
2192
    if (pr)
2193
    {
2194
      av0 = avma; x = F2xqX_red(x, T);
2195
      if (pr == ONLY_DIVIDES) { set_avma(av0); return signe(x)? NULL: pol_0(vx); }
2196
      if (pr == ONLY_REM) return x;
2197
      *pr = x;
2198
    }
2199
    return pol_0(vx);
2200
  }
2201
  lead = leading_coeff(y);
2202
  if (!dy) /* y is constant */
2203
  {
2204
    if (pr && pr != ONLY_DIVIDES)
2205
    {
2206
      if (pr == ONLY_REM) return pol_0(vx);
2207
      *pr = pol_0(vx);
2208
    }
2209
    if (F2x_equal1(lead)) return gcopy(x);
2210
    av0 = avma; x = F2xqX_F2xq_mul(x,F2xq_inv(lead,T),T);
2211
    return gerepileupto(av0,x);
2212
  }
2213
  av0 = avma; dz = dx-dy;
2214
  lead = F2x_equal1(lead)? NULL: gclone(F2xq_inv(lead,T));
2215
  set_avma(av0);
2216
  z = cgetg(dz+3,t_POL); z[1] = x[1];
2217
  x += 2; y += 2; z += 2;
2218

2219
  p1 = gel(x,dx); av = avma;
2220
  gel(z,dz) = lead? gerepileupto(av, F2xq_mul(p1,lead, T)): leafcopy(p1);
2221
  for (i=dx-1; i>=dy; i--)
2222
  {
2223
    av=avma; p1=gel(x,i);
2224
    for (j=i-dy+1; j<=i && j<=dz; j++)
2225
      p1 = F2x_add(p1, F2x_mul(gel(z,j),gel(y,i-j)));
2226
    if (lead) p1 = F2x_mul(p1, lead);
2227
    tetpil=avma; gel(z,i-dy) = gerepile(av,tetpil,F2x_rem(p1,T));
2228
  }
2229
  if (!pr) { guncloneNULL(lead); return z-2; }
2230

2231
  rem = (GEN)avma; av = (pari_sp)new_chunk(dx+3);
2232
  for (sx=0; ; i--)
2233
  {
2234
    p1 = gel(x,i);
2235
    for (j=0; j<=i && j<=dz; j++)
2236
      p1 = F2x_add(p1, F2x_mul(gel(z,j),gel(y,i-j)));
2237
    tetpil=avma; p1 = F2x_rem(p1, T); if (lgpol(p1)) { sx = 1; break; }
2238
    if (!i) break;
2239
    set_avma(av);
2240
  }
2241
  if (pr == ONLY_DIVIDES)
2242
  {
2243
    guncloneNULL(lead);
2244
    if (sx) return gc_NULL(av0);
2245
    return gc_const((pari_sp)rem, z-2);
2246
  }
2247
  lr=i+3; rem -= lr;
2248
  rem[0] = evaltyp(t_POL) | evallg(lr);
2249
  rem[1] = z[-1];
2250
  p1 = gerepile((pari_sp)rem,tetpil,p1);
2251
  rem += 2; gel(rem,i) = p1;
2252
  for (i--; i>=0; i--)
2253
  {
2254
    av=avma; p1 = gel(x,i);
2255
    for (j=0; j<=i && j<=dz; j++)
2256
      p1 = F2x_add(p1, F2x_mul(gel(z,j),gel(y,i-j)));
2257
    tetpil=avma; gel(rem,i) = gerepile(av,tetpil, F2x_rem(p1, T));
2258
  }
2259
  rem -= 2;
2260
  guncloneNULL(lead);
2261
  if (!sx) (void)F2xX_renormalize(rem, lr);
2262
  if (pr == ONLY_REM) return gerepileupto(av0,rem);
2263
  *pr = rem; return z-2;
2264
}
2265

2266
static GEN
2267
F2xX_recipspec(GEN x, long l, long n, long vs)
2268
{
2269
  long i;
2270
  GEN z = cgetg(n+2,t_POL);
2271
  z[1] = 0; z += 2;
2272
  for(i=0; i<l; i++)
2273
    gel(z,n-i-1) = F2x_copy(gel(x,i));
2274
  for(   ; i<n; i++)
2275
    gel(z,n-i-1) = pol0_F2x(vs);
2276
  return F2xX_renormalize(z-2,n+2);
2277
}
2278

2279
static GEN
2280
F2xqX_invBarrett_basecase(GEN T, GEN Q)
2281
{
2282
  long i, l=lg(T)-1, lr = l-1, k;
2283
  long sv=Q[1];
2284
  GEN r=cgetg(lr,t_POL); r[1]=T[1];
2285
  gel(r,2) = pol1_F2x(sv);
2286
  for (i=3;i<lr;i++)
2287
  {
2288
    pari_sp ltop=avma;
2289
    GEN u = gel(T,l-i+2);
2290
    for (k=3;k<i;k++)
2291
      u = F2x_add(u, F2xq_mul(gel(T,l-i+k),gel(r,k),Q));
2292
    gel(r,i) = gerepileupto(ltop, u);
2293
  }
2294
  r = F2xX_renormalize(r,lr);
2295
  return r;
2296
}
2297

2298
/* Return new lgpol */
2299
static long
2300
F2xX_lgrenormalizespec(GEN x, long lx)
2301
{
2302
  long i;
2303
  for (i = lx-1; i>=0; i--)
2304
    if (lgpol(gel(x,i))) break;
2305
  return i+1;
2306
}
2307

2308
static GEN
2309
F2xqX_invBarrett_Newton(GEN S, GEN T)
2310
{
2311
  pari_sp av = avma;
2312
  long nold, lx, lz, lq, l = degpol(S), i, lQ;
2313
  GEN q, y, z, x = cgetg(l+2, t_POL) + 2;
2314
  long dT = get_F2x_degree(T);
2315
  ulong mask = quadratic_prec_mask(l-2); /* assume l > 2 */
2316
  for (i=0;i<l;i++) gel(x,i) = pol0_F2x(T[1]);
2317
  q = F2xX_recipspec(S+2,l+1,l+1,dT);
2318
  lQ = lgpol(q); q+=2;
2319
  /* We work on _spec_ FlxX's, all the l[xzq] below are lgpol's */
2320

2321
  /* initialize */
2322
  gel(x,0) = F2xq_inv(gel(q,0),T);
2323
  if (lQ>1 && F2x_degree(gel(q,1)) >= dT)
2324
    gel(q,1) = F2x_rem(gel(q,1), T);
2325
  if (lQ>1 && lgpol(gel(q,1)))
2326
  {
2327
    GEN u = gel(q, 1);
2328
    if (!F2x_equal1(gel(x,0))) u = F2xq_mul(u, F2xq_sqr(gel(x,0), T), T);
2329
    else u = F2x_copy(u);
2330
    gel(x,1) = u; lx = 2;
2331
  }
2332
  else
2333
    lx = 1;
2334
  nold = 1;
2335
  for (; mask > 1; )
2336
  { /* set x -= x(x*q - 1) + O(t^(nnew + 1)), knowing x*q = 1 + O(t^(nold+1)) */
2337
    long i, lnew, nnew = nold << 1;
2338

2339
    if (mask & 1) nnew--;
2340
    mask >>= 1;
2341

2342
    lnew = nnew + 1;
2343
    lq = F2xX_lgrenormalizespec(q, minss(lQ,lnew));
2344
    z = F2xqX_mulspec(x, q, T, lx, lq); /* FIXME: high product */
2345
    lz = lgpol(z); if (lz > lnew) lz = lnew;
2346
    z += 2;
2347
    /* subtract 1 [=>first nold words are 0]: renormalize so that z(0) != 0 */
2348
    for (i = nold; i < lz; i++) if (lgpol(gel(z,i))) break;
2349
    nold = nnew;
2350
    if (i >= lz) continue; /* z-1 = 0(t^(nnew + 1)) */
2351

2352
    /* z + i represents (x*q - 1) / t^i */
2353
    lz = F2xX_lgrenormalizespec (z+i, lz-i);
2354
    z = F2xqX_mulspec(x, z+i, T, lx, lz); /* FIXME: low product */
2355
    lz = lgpol(z); z += 2;
2356
    if (lz > lnew-i) lz = F2xX_lgrenormalizespec(z, lnew-i);
2357

2358
    lx = lz+ i;
2359
    y  = x + i; /* x -= z * t^i, in place */
2360
    for (i = 0; i < lz; i++) gel(y,i) = gel(z,i);
2361
  }
2362
  x -= 2; setlg(x, lx + 2); x[1] = S[1];
2363
  return gerepilecopy(av, x);
2364
}
2365

2366
GEN
2367
F2xqX_invBarrett(GEN T, GEN Q)
2368
{
2369
  pari_sp ltop=avma;
2370
  long l=lg(T), v = varn(T);
2371
  GEN r;
2372
  GEN c = gel(T,l-1);
2373
  if (l<5) return pol_0(v);
2374
  if (l<=F2xqX_INVBARRETT_LIMIT)
2375
  {
2376
    if (!F2x_equal1(c))
2377
    {
2378
      GEN ci = F2xq_inv(c,Q);
2379
      T = F2xqX_F2xq_mul(T, ci, Q);
2380
      r = F2xqX_invBarrett_basecase(T,Q);
2381
      r = F2xqX_F2xq_mul(r,ci,Q);
2382
    } else
2383
      r = F2xqX_invBarrett_basecase(T,Q);
2384
  } else
2385
    r = F2xqX_invBarrett_Newton(T,Q);
2386
  return gerepileupto(ltop, r);
2387
}
2388

2389
GEN
2390
F2xqX_get_red(GEN S, GEN T)
2391
{
2392
  if (typ(S)==t_POL && lg(S)>F2xqX_BARRETT_LIMIT)
2393
    retmkvec2(F2xqX_invBarrett(S, T), S);
2394
  return S;
2395
}
2396

2397
/* Compute x mod S where 2 <= degpol(S) <= l+1 <= 2*(degpol(S)-1)
2398
 *  * and mg is the Barrett inverse of S. */
2399
static GEN
2400
F2xqX_divrem_Barrettspec(GEN x, long l, GEN mg, GEN S, GEN T, GEN *pr)
2401
{
2402
  GEN q, r;
2403
  long lt = degpol(S); /*We discard the leading term*/
2404
  long ld, lm, lT, lmg;
2405
  ld = l-lt;
2406
  lm = minss(ld, lgpol(mg));
2407
  lT  = F2xX_lgrenormalizespec(S+2,lt);
2408
  lmg = F2xX_lgrenormalizespec(mg+2,lm);
2409
  q = F2xX_recipspec(x+lt,ld,ld,0);               /* q = rec(x)     lq<=ld*/
2410
  q = F2xqX_mulspec(q+2,mg+2,T,lgpol(q),lmg);   /* q = rec(x) * mg lq<=ld+lm*/
2411
  q = F2xX_recipspec(q+2,minss(ld,lgpol(q)),ld,0);/* q = rec (rec(x) * mg) lq<=ld*/
2412
  if (!pr) return q;
2413
  r = F2xqX_mulspec(q+2,S+2,T,lgpol(q),lT);     /* r = q*pol        lr<=ld+lt*/
2414
  r = F2xX_addspec(x,r+2,lt,minss(lt,lgpol(r)));/* r = x - r   lr<=lt */
2415
  if (pr == ONLY_REM) return r;
2416
  *pr = r; return q;
2417
}
2418

2419
static GEN
2420
F2xqX_divrem_Barrett(GEN x, GEN mg, GEN S, GEN T, GEN *pr)
2421
{
2422
  GEN q = NULL, r = F2xqX_red(x, T);
2423
  long l = lgpol(r), lt = degpol(S), lm = 2*lt-1, v = varn(S);
2424
  long i;
2425
  if (l <= lt)
2426
  {
2427
    if (pr == ONLY_REM) return r;
2428
    if (pr == ONLY_DIVIDES) return signe(r)? NULL: pol_0(v);
2429
    if (pr) *pr = r;
2430
    return pol_0(v);
2431
  }
2432
  if (lt <= 1)
2433
    return F2xqX_divrem_basecase(x,S,T,pr);
2434
  if (pr != ONLY_REM && l>lm)
2435
  {
2436
    long vT = get_F2x_var(T);
2437
    q = cgetg(l-lt+2, t_POL); q[1] = S[1];
2438
    for (i=0;i<l-lt;i++) gel(q+2,i) = pol0_F2x(vT);
2439
  }
2440
  while (l>lm)
2441
  {
2442
    GEN zr, zq = F2xqX_divrem_Barrettspec(r+2+l-lm,lm,mg,S,T,&zr);
2443
    long lz = lgpol(zr);
2444
    if (pr != ONLY_REM)
2445
    {
2446
      long lq = lgpol(zq);
2447
      for(i=0; i<lq; i++) gel(q+2+l-lm,i) = gel(zq,2+i);
2448
    }
2449
    for(i=0; i<lz; i++) gel(r+2+l-lm,i) = gel(zr,2+i);
2450
    l = l-lm+lz;
2451
  }
2452
  if (pr == ONLY_REM)
2453
  {
2454
    if (l > lt)
2455
      r = F2xqX_divrem_Barrettspec(r+2,l,mg,S,T,ONLY_REM);
2456
    else
2457
      r = F2xX_renormalize(r, lg(r));
2458
    setvarn(r, v); return F2xX_renormalize(r, lg(r));
2459
  }
2460
  if (l > lt)
2461
  {
2462
    GEN zq = F2xqX_divrem_Barrettspec(r+2,l,mg,S,T,pr? &r: NULL);
2463
    if (!q) q = zq;
2464
    else
2465
    {
2466
      long lq = lgpol(zq);
2467
      for(i=0; i<lq; i++) gel(q+2,i) = gel(zq,2+i);
2468
    }
2469
  }
2470
  else if (pr)
2471
    r = F2xX_renormalize(r, l+2);
2472
  setvarn(q, v); q = F2xX_renormalize(q, lg(q));
2473
  if (pr == ONLY_DIVIDES) return signe(r)? NULL: q;
2474
  if (pr) { setvarn(r, v); *pr = r; }
2475
  return q;
2476
}
2477

2478
GEN
2479
F2xqX_divrem(GEN x, GEN S, GEN T, GEN *pr)
2480
{
2481
  GEN B, y;
2482
  long dy, dx, d;
2483
  if (pr==ONLY_REM) return F2xqX_rem(x, S, T);
2484
  y = get_F2xqX_red(S, &B);
2485
  dy = degpol(y); dx = degpol(x); d = dx-dy;
2486
  if (!B && d+3 < F2xqX_DIVREM_BARRETT_LIMIT)
2487
    return F2xqX_divrem_basecase(x,y,T,pr);
2488
  else
2489
  {
2490
    pari_sp av=avma;
2491
    GEN mg = B? B: F2xqX_invBarrett(y, T);
2492
    GEN q = F2xqX_divrem_Barrett(x,mg,y,T,pr);
2493
    if (!q) return gc_NULL(av);
2494
    if (!pr || pr==ONLY_DIVIDES) return gerepilecopy(av, q);
2495
    gerepileall(av,2,&q,pr);
2496
    return q;
2497
  }
2498
}
2499

2500
GEN
2501
F2xqX_rem(GEN x, GEN S, GEN T)
2502
{
2503
  GEN B, y = get_F2xqX_red(S, &B);
2504
  long dy = degpol(y), dx = degpol(x), d = dx-dy;
2505
  if (d < 0) return F2xqX_red(x, T);
2506
  if (!B && d+3 < F2xqX_REM_BARRETT_LIMIT)
2507
    return F2xqX_divrem_basecase(x,y, T, ONLY_REM);
2508
  else
2509
  {
2510
    pari_sp av=avma;
2511
    GEN mg = B? B: F2xqX_invBarrett(y, T);
2512
    GEN r = F2xqX_divrem_Barrett(x, mg, y, T, ONLY_REM);
2513
    return gerepileupto(av, r);
2514
  }
2515
}
2516

2517
static GEN
2518
F2xqX_halfgcd_basecase(GEN a, GEN b, GEN T)
2519
{
2520
  pari_sp av=avma;
2521
  GEN u,u1,v,v1;
2522
  long vx = varn(a);
2523
  long n = lgpol(a)>>1;
2524
  u1 = v = pol_0(vx);
2525
  u = v1 = pol1_F2xX(vx, get_F2x_var(T));
2526
  while (lgpol(b)>n)
2527
  {
2528
    GEN r, q = F2xqX_divrem(a,b, T, &r);
2529
    a = b; b = r; swap(u,u1); swap(v,v1);
2530
    u1 = F2xX_add(u1, F2xqX_mul(u, q, T));
2531
    v1 = F2xX_add(v1, F2xqX_mul(v, q ,T));
2532
    if (gc_needed(av,2))
2533
    {
2534
      if (DEBUGMEM>1) pari_warn(warnmem,"F2xqX_halfgcd (d = %ld)",degpol(b));
2535
      gerepileall(av,6, &a,&b,&u1,&v1,&u,&v);
2536
    }
2537
  }
2538
  return gerepilecopy(av, mkmat2(mkcol2(u,u1), mkcol2(v,v1)));
2539
}
2540
static GEN
2541
F2xqX_addmulmul(GEN u, GEN v, GEN x, GEN y, GEN T)
2542
{
2543
  return F2xX_add(F2xqX_mul(u, x, T),F2xqX_mul(v, y, T));
2544
}
2545

2546
static GEN
2547
F2xqXM_F2xqX_mul2(GEN M, GEN x, GEN y, GEN T)
2548
{
2549
  GEN res = cgetg(3, t_COL);
2550
  gel(res, 1) = F2xqX_addmulmul(gcoeff(M,1,1), gcoeff(M,1,2), x, y, T);
2551
  gel(res, 2) = F2xqX_addmulmul(gcoeff(M,2,1), gcoeff(M,2,2), x, y, T);
2552
  return res;
2553
}
2554

2555
static GEN
2556
F2xqXM_mul2(GEN A, GEN B, GEN T)
2557
{
2558
  GEN A11=gcoeff(A,1,1),A12=gcoeff(A,1,2), B11=gcoeff(B,1,1),B12=gcoeff(B,1,2);
2559
  GEN A21=gcoeff(A,2,1),A22=gcoeff(A,2,2), B21=gcoeff(B,2,1),B22=gcoeff(B,2,2);
2560
  GEN M1 = F2xqX_mul(F2xX_add(A11,A22), F2xX_add(B11,B22), T);
2561
  GEN M2 = F2xqX_mul(F2xX_add(A21,A22), B11, T);
2562
  GEN M3 = F2xqX_mul(A11, F2xX_add(B12,B22), T);
2563
  GEN M4 = F2xqX_mul(A22, F2xX_add(B21,B11), T);
2564
  GEN M5 = F2xqX_mul(F2xX_add(A11,A12), B22, T);
2565
  GEN M6 = F2xqX_mul(F2xX_add(A21,A11), F2xX_add(B11,B12), T);
2566
  GEN M7 = F2xqX_mul(F2xX_add(A12,A22), F2xX_add(B21,B22), T);
2567
  GEN T1 = F2xX_add(M1,M4), T2 = F2xX_add(M7,M5);
2568
  GEN T3 = F2xX_add(M1,M2), T4 = F2xX_add(M3,M6);
2569
  retmkmat2(mkcol2(F2xX_add(T1,T2), F2xX_add(M2,M4)),
2570
            mkcol2(F2xX_add(M3,M5), F2xX_add(T3,T4)));
2571
}
2572

2573
/* Return [0,1;1,-q]*M */
2574
static GEN
2575
F2xqX_F2xqXM_qmul(GEN q, GEN M, GEN T)
2576
{
2577
  GEN u, v, res = cgetg(3, t_MAT);
2578
  u = F2xX_add(gcoeff(M,1,1), F2xqX_mul(gcoeff(M,2,1), q, T));
2579
  gel(res,1) = mkcol2(gcoeff(M,2,1), u);
2580
  v = F2xX_add(gcoeff(M,1,2), F2xqX_mul(gcoeff(M,2,2), q, T));
2581
  gel(res,2) = mkcol2(gcoeff(M,2,2), v);
2582
  return res;
2583
}
2584

2585
static GEN
2586
matid2_F2xXM(long v, long sv)
2587
{
2588
  retmkmat2(mkcol2(pol1_F2xX(v, sv),pol_0(v)),
2589
            mkcol2(pol_0(v),pol1_F2xX(v, sv)));
2590
}
2591

2592
static GEN
2593
F2xqX_halfgcd_split(GEN x, GEN y, GEN T)
2594
{
2595
  pari_sp av=avma;
2596
  GEN R, S, V;
2597
  GEN y1, r, q;
2598
  long l = lgpol(x), n = l>>1, k;
2599
  if (lgpol(y)<=n) return matid2_F2xXM(varn(x),get_F2x_var(T));
2600
  R = F2xqX_halfgcd(RgX_shift_shallow(x,-n),RgX_shift_shallow(y,-n), T);
2601
  V = F2xqXM_F2xqX_mul2(R,x,y, T); y1 = gel(V,2);
2602
  if (lgpol(y1)<=n) return gerepilecopy(av, R);
2603
  q = F2xqX_divrem(gel(V,1), y1, T, &r);
2604
  k = 2*n-degpol(y1);
2605
  S = F2xqX_halfgcd(RgX_shift_shallow(y1,-k), RgX_shift_shallow(r,-k), T);
2606
  return gerepileupto(av, F2xqXM_mul2(S,F2xqX_F2xqXM_qmul(q,R, T), T));
2607
}
2608

2609
/* Return M in GL_2(Fp[X]) such that:
2610
if [a',b']~=M*[a,b]~ then degpol(a')>= (lgpol(a)>>1) >degpol(b')
2611
*/
2612

2613
static GEN
2614
F2xqX_halfgcd_i(GEN x, GEN y, GEN T)
2615
{
2616
  if (lg(x)<=F2xqX_HALFGCD_LIMIT) return F2xqX_halfgcd_basecase(x, y, T);
2617
  return F2xqX_halfgcd_split(x, y, T);
2618
}
2619

2620
GEN
2621
F2xqX_halfgcd(GEN x, GEN y, GEN T)
2622
{
2623
  pari_sp av = avma;
2624
  GEN M,q,r;
2625
  if (!signe(x))
2626
  {
2627
    long v = varn(x), vT = get_F2x_var(T);
2628
    retmkmat2(mkcol2(pol_0(v),pol1_F2xX(v,vT)),
2629
        mkcol2(pol1_F2xX(v,vT),pol_0(v)));
2630
  }
2631
  if (degpol(y)<degpol(x)) return F2xqX_halfgcd_i(x, y, T);
2632
  q = F2xqX_divrem(y, x, T, &r);
2633
  M = F2xqX_halfgcd_i(x, r, T);
2634
  gcoeff(M,1,1) = F2xX_add(gcoeff(M,1,1), F2xqX_mul(q, gcoeff(M,1,2), T));
2635
  gcoeff(M,2,1) = F2xX_add(gcoeff(M,2,1), F2xqX_mul(q, gcoeff(M,2,2), T));
2636
  return gerepilecopy(av, M);
2637
}
2638

2639
static GEN
2640
F2xqX_gcd_basecase(GEN a, GEN b, GEN T)
2641
{
2642
  pari_sp av = avma, av0=avma;
2643
  while (signe(b))
2644
  {
2645
    GEN c;
2646
    if (gc_needed(av0,2))
2647
    {
2648
      if (DEBUGMEM>1) pari_warn(warnmem,"F2xqX_gcd (d = %ld)",degpol(b));
2649
      gerepileall(av0,2, &a,&b);
2650
    }
2651
    av = avma; c = F2xqX_rem(a, b, T); a=b; b=c;
2652
  }
2653
  return gc_const(av, a);
2654
}
2655

2656
GEN
2657
F2xqX_gcd(GEN x, GEN y, GEN T)
2658
{
2659
  pari_sp av = avma;
2660
  x = F2xqX_red(x, T);
2661
  y = F2xqX_red(y, T);
2662
  if (!signe(x)) return gerepileupto(av, y);
2663
  while (lg(y)>F2xqX_GCD_LIMIT)
2664
  {
2665
    GEN c;
2666
    if (lgpol(y)<=(lgpol(x)>>1))
2667
    {
2668
      GEN r = F2xqX_rem(x, y, T);
2669
      x = y; y = r;
2670
    }
2671
    c = F2xqXM_F2xqX_mul2(F2xqX_halfgcd(x,y, T), x, y, T);
2672
    x = gel(c,1); y = gel(c,2);
2673
    gerepileall(av,2,&x,&y);
2674
  }
2675
  return gerepileupto(av, F2xqX_gcd_basecase(x, y, T));
2676
}
2677

2678
static GEN
2679
F2xqX_extgcd_basecase(GEN a, GEN b, GEN T,  GEN *ptu, GEN *ptv)
2680
{
2681
  pari_sp av=avma;
2682
  GEN u,v,d,d1,v1;
2683
  long vx = varn(a);
2684
  d = a; d1 = b;
2685
  v = pol_0(vx); v1 = pol1_F2xX(vx, get_F2x_var(T));
2686
  while (signe(d1))
2687
  {
2688
    GEN r, q = F2xqX_divrem(d, d1, T, &r);
2689
    v = F2xX_add(v,F2xqX_mul(q,v1,T));
2690
    u=v; v=v1; v1=u;
2691
    u=r; d=d1; d1=u;
2692
    if (gc_needed(av,2))
2693
    {
2694
      if (DEBUGMEM>1) pari_warn(warnmem,"F2xqX_extgcd (d = %ld)",degpol(d));
2695
      gerepileall(av,5, &d,&d1,&u,&v,&v1);
2696
    }
2697
  }
2698
  if (ptu) *ptu = F2xqX_div(F2xX_add(d,F2xqX_mul(b,v, T)), a, T);
2699
  *ptv = v; return d;
2700
}
2701

2702
static GEN
2703
F2xqX_extgcd_halfgcd(GEN x, GEN y, GEN T,  GEN *ptu, GEN *ptv)
2704
{
2705
  pari_sp av=avma;
2706
  GEN u,v,R = matid2_F2xXM(varn(x), get_F2x_var(T));
2707
  while (lg(y)>F2xqX_EXTGCD_LIMIT)
2708
  {
2709
    GEN M, c;
2710
    if (lgpol(y)<=(lgpol(x)>>1))
2711
    {
2712
      GEN r, q = F2xqX_divrem(x, y, T, &r);
2713
      x = y; y = r;
2714
      R = F2xqX_F2xqXM_qmul(q, R, T);
2715
    }
2716
    M = F2xqX_halfgcd(x,y, T);
2717
    c = F2xqXM_F2xqX_mul2(M, x,y, T);
2718
    R = F2xqXM_mul2(M, R, T);
2719
    x = gel(c,1); y = gel(c,2);
2720
    gerepileall(av,3,&x,&y,&R);
2721
  }
2722
  y = F2xqX_extgcd_basecase(x,y, T, &u,&v);
2723
  if (ptu) *ptu = F2xqX_addmulmul(u,v,gcoeff(R,1,1),gcoeff(R,2,1), T);
2724
  *ptv = F2xqX_addmulmul(u,v,gcoeff(R,1,2),gcoeff(R,2,2), T);
2725
  return y;
2726
}
2727

2728
/* x and y in Z[Y][X], return lift(gcd(x mod T,p, y mod T,p)). Set u and v st
2729
 * ux + vy = gcd (mod T,p) */
2730
GEN
2731
F2xqX_extgcd(GEN x, GEN y, GEN T,  GEN *ptu, GEN *ptv)
2732
{
2733
  GEN d;
2734
  pari_sp ltop=avma;
2735
  x = F2xqX_red(x, T);
2736
  y = F2xqX_red(y, T);
2737
  if (lg(y)>F2xqX_EXTGCD_LIMIT)
2738
    d = F2xqX_extgcd_halfgcd(x, y, T, ptu, ptv);
2739
  else
2740
    d = F2xqX_extgcd_basecase(x, y, T, ptu, ptv);
2741
  gerepileall(ltop,ptu?3:2,&d,ptv,ptu);
2742
  return d;
2743
}
2744

2745
static GEN
2746
_F2xqX_mul(void *data,GEN a,GEN b) { return F2xqX_mul(a,b, (GEN) data); }
2747
static GEN
2748
_F2xqX_sqr(void *data,GEN a) { return F2xqX_sqr(a, (GEN) data); }
2749
GEN
2750
F2xqX_powu(GEN x, ulong n, GEN T)
2751
{ return gen_powu(x, n, (void*)T, &_F2xqX_sqr, &_F2xqX_mul); }
2752

2753
/* Res(A,B) = Res(B,R) * lc(B)^(a-r) * (-1)^(ab), with R=A%B, a=deg(A) ...*/
2754
GEN
2755
F2xqX_resultant(GEN a, GEN b, GEN T)
2756
{
2757
  long vT = get_F2x_var(T);
2758
  long da,db,dc;
2759
  pari_sp av;
2760
  GEN c,lb, res = pol1_F2x(vT);
2761

2762
  if (!signe(a) || !signe(b)) return pol0_F2x(vT);
2763

2764
  da = degpol(a);
2765
  db = degpol(b);
2766
  if (db > da)
2767
    swapspec(a,b, da,db);
2768
  if (!da) return pol1_F2x(vT); /* = res * a[2] ^ db, since 0 <= db <= da = 0 */
2769
  av = avma;
2770
  while (db)
2771
  {
2772
    lb = gel(b,db+2);
2773
    c = F2xqX_rem(a,b, T);
2774
    a = b; b = c; dc = degpol(c);
2775
    if (dc < 0) { set_avma(av); return pol0_F2x(vT); }
2776

2777
    if (!equali1(lb)) res = F2xq_mul(res, F2xq_powu(lb, da - dc, T), T);
2778
    if (gc_needed(av,2))
2779
    {
2780
      if (DEBUGMEM>1) pari_warn(warnmem,"F2xqX_resultant (da = %ld)",da);
2781
      gerepileall(av,3, &a,&b,&res);
2782
    }
2783
    da = db; /* = degpol(a) */
2784
    db = dc; /* = degpol(b) */
2785
  }
2786
  res = F2xq_mul(res, F2xq_powu(gel(b,2), da, T), T);
2787
  return gerepileupto(av, res);
2788
}
2789

2790
/* disc P = (-1)^(n(n-1)/2) lc(P)^(n - deg P' - 2) Res(P,P'), n = deg P */
2791
GEN
2792
F2xqX_disc(GEN P, GEN T)
2793
{
2794
  pari_sp av = avma;
2795
  GEN L, dP = F2xX_deriv(P), D = F2xqX_resultant(P, dP, T);
2796
  long dd;
2797
  if (!lgpol(D)) return pol_0(get_F2x_var(T));
2798
  dd = degpol(P) - 2 - degpol(dP); /* >= -1; > -1 iff p | deg(P) */
2799
  L = leading_coeff(P);
2800
  if (dd && !F2x_equal1(L))
2801
    D = (dd == -1)? F2xq_div(D,L,T): F2xq_mul(D, F2xq_powu(L, dd, T), T);
2802
  return gerepileupto(av, D);
2803
}
2804

2805
/***********************************************************************/
2806
/**                                                                   **/
2807
/**                             F2xqXQ                                **/
2808
/**                                                                   **/
2809
/***********************************************************************/
2810

2811
GEN
2812
F2xqXQ_mul(GEN x, GEN y, GEN S, GEN T) {
2813
  return F2xqX_rem(F2xqX_mul(x,y,T),S,T);
2814
}
2815

2816
GEN
2817
F2xqXQ_sqr(GEN x, GEN S, GEN T) {
2818
  return F2xqX_rem(F2xqX_sqr(x,T),S,T);
2819
}
2820

2821
GEN
2822
F2xqXQ_invsafe(GEN x, GEN S, GEN T)
2823
{
2824
  GEN V, z = F2xqX_extgcd(get_F2xqX_mod(S), x, T, NULL, &V);
2825
  if (degpol(z)) return NULL;
2826
  z = F2xq_invsafe(gel(z,2),T);
2827
  if (!z) return NULL;
2828
  return F2xqX_F2xq_mul(V, z, T);
2829
}
2830

2831
GEN
2832
F2xqXQ_inv(GEN x, GEN S, GEN T)
2833
{
2834
  pari_sp av = avma;
2835
  GEN U = F2xqXQ_invsafe(x, S, T);
2836
  if (!U) pari_err_INV("F2xqXQ_inv",x);
2837
  return gerepileupto(av, U);
2838
}
2839

2840
struct _F2xqXQ {
2841
  GEN T, S;
2842
};
2843

2844
static GEN
2845
_F2xqXQ_add(void *data, GEN x, GEN y) {
2846
  (void) data;
2847
  return F2xX_add(x,y);
2848
}
2849
static GEN
2850
_F2xqXQ_cmul(void *data, GEN P, long a, GEN x) {
2851
  (void) data;
2852
  return F2xX_F2x_mul(x,gel(P,a+2));
2853
}
2854
static GEN
2855
_F2xqXQ_red(void *data, GEN x) {
2856
  struct _F2xqXQ *d = (struct _F2xqXQ*) data;
2857
  return F2xqX_red(x, d->T);
2858
}
2859
static GEN
2860
_F2xqXQ_mul(void *data, GEN x, GEN y) {
2861
  struct _F2xqXQ *d = (struct _F2xqXQ*) data;
2862
  return F2xqXQ_mul(x,y, d->S,d->T);
2863
}
2864
static GEN
2865
_F2xqXQ_sqr(void *data, GEN x) {
2866
  struct _F2xqXQ *d = (struct _F2xqXQ*) data;
2867
  return F2xqXQ_sqr(x, d->S,d->T);
2868
}
2869
static GEN
2870
_F2xqXQ_zero(void *data) {
2871
  struct _F2xqXQ *d = (struct _F2xqXQ*) data;
2872
  return pol_0(get_F2xqX_var(d->S));
2873
}
2874
static GEN
2875
_F2xqXQ_one(void *data) {
2876
  struct _F2xqXQ *d = (struct _F2xqXQ*) data;
2877
  return pol1_F2xX(get_F2xqX_var(d->S),get_F2x_var(d->T));
2878
}
2879

2880
static struct bb_algebra F2xqXQ_algebra = { _F2xqXQ_red,
2881
 _F2xqXQ_add, _F2xqXQ_add, _F2xqXQ_mul,_F2xqXQ_sqr,_F2xqXQ_one,_F2xqXQ_zero };
2882

2883
GEN
2884
F2xqXQ_pow(GEN x, GEN n, GEN S, GEN T)
2885
{
2886
  struct _F2xqXQ D;
2887
  long s = signe(n);
2888
  if (!s) return pol1_F2xX(get_F2xqX_var(S), get_F2x_var(T));
2889
  if (s < 0) x = F2xqXQ_inv(x,S,T);
2890
  if (is_pm1(n)) return s < 0 ? x : gcopy(x);
2891
  if (degpol(x) >= get_F2xqX_degree(S)) x = F2xqX_rem(x,S,T);
2892
  D.T = F2x_get_red(T);
2893
  D.S = F2xqX_get_red(S, T);
2894
  return gen_pow(x, n, (void*)&D, &_F2xqXQ_sqr, &_F2xqXQ_mul);
2895
}
2896

2897
GEN
2898
F2xqXQ_powers(GEN x, long l, GEN S, GEN T)
2899
{
2900
  struct _F2xqXQ D;
2901
  int use_sqr = 2*degpol(x) >= get_F2xqX_degree(S);
2902
  D.T = F2x_get_red(T);
2903
  D.S = F2xqX_get_red(S, T);
2904
  return gen_powers(x, l, use_sqr, (void*)&D, &_F2xqXQ_sqr, &_F2xqXQ_mul,&_F2xqXQ_one);
2905
}
2906

2907
GEN
2908
F2xqX_F2xqXQV_eval(GEN P, GEN V, GEN S, GEN T)
2909
{
2910
  struct _F2xqXQ D;
2911
  D.T = F2x_get_red(T);
2912
  D.S = F2xqX_get_red(S, T);
2913
  return gen_bkeval_powers(P, degpol(P), V, (void*)&D, &F2xqXQ_algebra,
2914
                                                   _F2xqXQ_cmul);
2915
}
2916

2917
GEN
2918
F2xqX_F2xqXQ_eval(GEN Q, GEN x, GEN S, GEN T)
2919
{
2920
  struct _F2xqXQ D;
2921
  int use_sqr = 2*degpol(x) >= get_F2xqX_degree(S);
2922
  D.T = F2x_get_red(T);
2923
  D.S = F2xqX_get_red(S, T);
2924
  return gen_bkeval(Q, degpol(Q), x, use_sqr, (void*)&D, &F2xqXQ_algebra,
2925
                                                    _F2xqXQ_cmul);
2926
}
2927

2928
static GEN
2929
F2xqXQ_autpow_sqr(void * E, GEN x)
2930
{
2931
  struct _F2xqXQ *D = (struct _F2xqXQ *)E;
2932
  GEN T = D->T;
2933
  GEN phi = gel(x,1), S = gel(x,2);
2934
  long n = brent_kung_optpow(get_F2x_degree(T)-1,lgpol(S)+1,1);
2935
  GEN V = F2xq_powers(phi, n, T);
2936
  GEN phi2 = F2x_F2xqV_eval(phi, V, T);
2937
  GEN Sphi = F2xY_F2xqV_evalx(S, V, T);
2938
  GEN S2 = F2xqX_F2xqXQ_eval(Sphi, S, D->S, T);
2939
  return mkvec2(phi2, S2);
2940
}
2941

2942
static GEN
2943
F2xqXQ_autpow_mul(void * E, GEN x, GEN y)
2944
{
2945
  struct _F2xqXQ *D = (struct _F2xqXQ *)E;
2946
  GEN T = D->T;
2947
  GEN phi1 = gel(x,1), S1 = gel(x,2);
2948
  GEN phi2 = gel(y,1), S2 = gel(y,2);
2949
  long n = brent_kung_optpow(get_F2x_degree(T)-1,lgpol(S1)+1,1);
2950
  GEN V = F2xq_powers(phi2, n, T);
2951
  GEN phi3 = F2x_F2xqV_eval(phi1,V,T);
2952
  GEN Sphi = F2xY_F2xqV_evalx(S1,V,T);
2953
  GEN S3 = F2xqX_F2xqXQ_eval(Sphi, S2, D->S, T);
2954
  return mkvec2(phi3, S3);
2955
}
2956

2957
GEN
2958
F2xqXQ_autpow(GEN aut, long n, GEN S, GEN T)
2959
{
2960
  struct _F2xqXQ D;
2961
  D.T = F2x_get_red(T);
2962
  D.S = F2xqX_get_red(S, T);
2963
  return gen_powu(aut,n,&D,F2xqXQ_autpow_sqr,F2xqXQ_autpow_mul);
2964
}
2965

2966
static GEN
2967
F2xqXQ_auttrace_mul(void *E, GEN x, GEN y)
2968
{
2969
  struct _F2xqXQ *D = (struct _F2xqXQ *) E;
2970
  GEN T = D->T;
2971
  GEN phi1 = gel(x,1), S1 = gel(x,2), a1 = gel(x,3);
2972
  GEN phi2 = gel(y,1), S2 = gel(y,2), a2 = gel(y,3);
2973
  long n2 = brent_kung_optpow(get_F2x_degree(T)-1, lgpol(S1)+lgpol(a1)+1, 1);
2974
  GEN V2 = F2xq_powers(phi2, n2, T);
2975
  GEN phi3 = F2x_F2xqV_eval(phi1, V2, T);
2976
  GEN Sphi = F2xY_F2xqV_evalx(S1, V2, T);
2977
  GEN aphi = F2xY_F2xqV_evalx(a1, V2, T);
2978
  long n = brent_kung_optpow(maxss(degpol(Sphi),degpol(aphi)),2,1);
2979
  GEN V = F2xqXQ_powers(S2, n, D->S, T);
2980
  GEN S3 = F2xqX_F2xqXQV_eval(Sphi, V, D->S, T);
2981
  GEN aS = F2xqX_F2xqXQV_eval(aphi, V, D->S, T);
2982
  GEN a3 = F2xX_add(aS, a2);
2983
  return mkvec3(phi3, S3, a3);
2984
}
2985

2986
static GEN
2987
F2xqXQ_auttrace_sqr(void *E, GEN x) { return F2xqXQ_auttrace_mul(E, x, x); }
2988
GEN
2989
F2xqXQ_auttrace(GEN aut, long n, GEN S, GEN T)
2990
{
2991
  struct _F2xqXQ D;
2992
  D.T = F2x_get_red(T);
2993
  D.S = F2xqX_get_red(S, T);
2994
  return gen_powu(aut,n,&D,F2xqXQ_auttrace_sqr,F2xqXQ_auttrace_mul);
2995
}
2996

2997
GEN
2998
F2xqXQV_red(GEN x, GEN S, GEN T)
2999
{ pari_APPLY_type(t_VEC, F2xqX_rem(gel(x,i), S, T)) }
3000

3001
Product

Resources

Company
