Code coverage tests

This page documents the degree to which the PARI/GP source code is tested by our public test suite, distributed with the source distribution in directory src/test/. This is measured by the gcov utility; we then process gcov output using the lcov frond-end.

We test a few variants depending on Configure flags on the pari.math.u-bordeaux.fr machine (x86_64 architecture), and agregate them in the final report:

The target is to exceed 90% coverage for all mathematical modules (given that branches depending on DEBUGLEVEL or DEBUGMEM are not covered). This script is run to produce the results below.

LCOV - code coverage report
Current view: top level - basemath - F2x.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.14.0 lcov report (development 27775-aca467eab2) Lines: 1497 1735 86.3 %
Date: 2022-07-03 07:33:15 Functions: 183 204 89.7 %
Legend: Lines: hit not hit

          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   260188037 : F2x_degree_lg(GEN x, long l)
      48             : {
      49   260188037 :   return (l==2)?-1:bit_accuracy(l)-bfffo(x[l-1])-1;
      50             : }
      51             : 
      52             : long
      53    76454285 : F2x_degree(GEN x)
      54             : {
      55    76454285 :   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     1246616 : F2x_to_ZX(GEN x)
      70             : {
      71     1246616 :   long l = 3+F2x_degree(x), lx = lg(x);
      72     1246631 :   GEN z = cgetg(l,t_POL);
      73             :   long i, j ,k;
      74     2494578 :   for (i=2, k=2; i<lx; i++)
      75     4302577 :     for (j=0; j<BITS_IN_LONG && k<l; j++,k++)
      76     3054640 :       gel(z,k) = (x[i]&(1UL<<j))?gen_1:gen_0;
      77     1246641 :   z[1]=evalsigne(l>=3)|x[1];
      78     1246641 :   return z;
      79             : }
      80             : 
      81             : GEN
      82      133684 : F2x_to_Flx(GEN x)
      83             : {
      84      133684 :   long l = 3+F2x_degree(x), lx = lg(x);
      85      133683 :   GEN z = cgetg(l,t_VECSMALL);
      86             :   long i, j, k;
      87      133685 :   z[1] = x[1];
      88      303022 :   for (i=2, k=2; i<lx; i++)
      89     4918068 :     for (j=0; j<BITS_IN_LONG && k<l; j++,k++)
      90     4748731 :       z[k] = (x[i]>>j)&1UL;
      91      133685 :   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      210476 : Z_to_F2x(GEN x, long sv)
     106             : {
     107      210476 :   return mpodd(x) ? pol1_F2x(sv): pol0_F2x(sv);
     108             : }
     109             : 
     110             : GEN
     111     1857332 : ZX_to_F2x(GEN x)
     112             : {
     113     1857332 :   long lx = lg(x), l = nbits2lg(lx-2);
     114     1857334 :   GEN z = cgetg(l,t_VECSMALL);
     115             :   long i, j, k;
     116     1857342 :   z[1] = ((ulong)x[1])&VARNBITS;
     117     6839533 :   for (i=2, k=1,j=BITS_IN_LONG; i<lx; i++,j++)
     118             :   {
     119     4982186 :     if (j==BITS_IN_LONG)
     120             :     {
     121     1841699 :       j=0; z[++k]=0;
     122             :     }
     123     4982186 :     if (mpodd(gel(x,i)))
     124     3398562 :       z[k] |= 1UL<<j;
     125             :   }
     126     1857347 :   return F2x_renormalize(z,l);
     127             : }
     128             : 
     129             : GEN
     130      152616 : Flx_to_F2x(GEN x)
     131             : {
     132      152616 :   long lx = lg(x), l = nbits2lg(lx-2);
     133      152616 :   GEN z = cgetg(l,t_VECSMALL);
     134             :   long i, j, k;
     135      152615 :   z[1] = x[1];
     136     4990377 :   for (i=2, k=1, j=BITS_IN_LONG; i<lx; i++,j++)
     137             :   {
     138     4837762 :     if (j==BITS_IN_LONG)
     139             :     {
     140      181054 :       j=0; z[++k] = 0;
     141             :     }
     142     4837762 :     if (x[i]&1UL)
     143     2472146 :       z[k] |= 1UL<<j;
     144             :   }
     145      152615 :   return F2x_renormalize(z,l);
     146             : }
     147             : 
     148             : GEN
     149     1565594 : F2x_to_F2v(GEN x, long N)
     150             : {
     151     1565594 :   long i, l = lg(x);
     152     1565594 :   long n = nbits2lg(N);
     153     1565595 :   GEN z = cgetg(n,t_VECSMALL);
     154     1565587 :   z[1] = N;
     155     3362622 :   for (i=2; i<l ; i++) z[i]=x[i];
     156     1656825 :   for (   ; i<n; i++) z[i]=0;
     157     1565587 :   return z;
     158             : }
     159             : 
     160             : GEN
     161        1372 : RgX_to_F2x(GEN x)
     162             : {
     163        1372 :   long l=nbits2lg(lgpol(x));
     164        1372 :   GEN z=cgetg(l,t_VECSMALL);
     165             :   long i,j,k;
     166        1372 :   z[1]=((ulong)x[1])&VARNBITS;
     167        4193 :   for(i=2, k=1,j=BITS_IN_LONG;i<lg(x);i++,j++)
     168             :   {
     169        2821 :     if (j==BITS_IN_LONG)
     170             :     {
     171        1358 :       j=0; k++; z[k]=0;
     172             :     }
     173        2821 :     if (Rg_to_F2(gel(x,i)))
     174        1379 :       z[k]|=1UL<<j;
     175             :   }
     176        1372 :   return F2x_renormalize(z,l);
     177             : }
     178             : 
     179             : /* If x is a POLMOD, assume modulus is a multiple of T. */
     180             : GEN
     181     1166048 : Rg_to_F2xq(GEN x, GEN T)
     182             : {
     183     1166048 :   long ta, tx = typ(x), v = get_F2x_var(T);
     184             :   GEN a, b;
     185     1166048 :   if (is_const_t(tx))
     186             :   {
     187     1164879 :     if (tx == t_FFELT) return FF_to_F2xq(x);
     188      246692 :     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       12411 : F2x_eval(GEN P, ulong x)
     215             : {
     216       12411 :   if (lgpol(P)==0) return 0;
     217        9128 :   if (odd(x))
     218             :   {
     219        2639 :     long i, lP = lg(P);
     220        2639 :     ulong c = 0;
     221        5278 :     for (i=2; i<lP; i++)
     222        2639 :       c ^= P[i];
     223             : #ifdef LONG_IS_64BIT
     224        2262 :     c ^= c >> 32;
     225             : #endif
     226        2639 :     c ^= c >> 16;
     227        2639 :     c ^= c >>  8;
     228        2639 :     c ^= c >>  4;
     229        2639 :     c ^= c >>  2;
     230        2639 :     c ^= c >>  1;
     231        2639 :     return c & 1;
     232             :   }
     233        6489 :   else return F2x_coeff(P,0);
     234             : }
     235             : 
     236             : GEN
     237    31324462 : F2x_add(GEN x, GEN y)
     238             : {
     239             :   long i,lz;
     240             :   GEN z;
     241    31324462 :   long lx=lg(x);
     242    31324462 :   long ly=lg(y);
     243    31324462 :   if (ly>lx) swapspec(x,y, lx,ly);
     244    31324462 :   lz = lx; z = cgetg(lz, t_VECSMALL); z[1]=x[1];
     245    66741952 :   for (i=2; i<ly; i++) z[i] = x[i]^y[i];
     246    38020781 :   for (   ; i<lx; i++) z[i] = x[i];
     247    31350209 :   return F2x_renormalize(z, lz);
     248             : }
     249             : 
     250             : static GEN
     251       57750 : F2x_addspec(GEN x, GEN y, long lx, long ly)
     252             : {
     253             :   long i,lz;
     254             :   GEN z;
     255             : 
     256       57750 :   if (ly>lx) swapspec(x,y, lx,ly);
     257       57750 :   lz = lx+2; z = cgetg(lz, t_VECSMALL) + 2;
     258      167426 :   for (i=0; i<ly-3; i+=4)
     259             :   {
     260      109676 :     z[i] = x[i]^y[i];
     261      109676 :     z[i+1] = x[i+1]^y[i+1];
     262      109676 :     z[i+2] = x[i+2]^y[i+2];
     263      109676 :     z[i+3] = x[i+3]^y[i+3];
     264             :   }
     265       94682 :   for (; i<ly; i++)
     266       36932 :     z[i] = x[i]^y[i];
     267      525234 :   for (   ; i<lx; i++) z[i] = x[i];
     268       57750 :   z -= 2; z[1] = 0; return F2x_renormalize(z, lz);
     269             : }
     270             : 
     271             : GEN
     272      190459 : F2x_1_add(GEN y)
     273             : {
     274             :   GEN z;
     275             :   long lz, i;
     276      190459 :   if (!lgpol(y))
     277       90366 :     return pol1_F2x(y[1]);
     278      100093 :   lz=lg(y);
     279      100093 :   z=cgetg(lz,t_VECSMALL);
     280      100093 :   z[1] = y[1];
     281      100093 :   z[2] = y[2]^1UL;
     282      100093 :   for(i=3;i<lz;i++)
     283           0 :     z[i] = y[i];
     284      100093 :   if (lz==3) z = F2x_renormalize(z,lz);
     285      100093 :   return z;
     286             : }
     287             : 
     288             : INLINE void
     289   166639198 : F2x_addshiftipspec(GEN x, GEN y, long ny, ulong db)
     290             : {
     291             :   long i;
     292   166639198 :   if (db)
     293             :   {
     294   142908721 :     ulong dc=BITS_IN_LONG-db;
     295   142908721 :     ulong r=0, yi;
     296   223291314 :     for(i=0; i<ny-3; i+=4)
     297             :     {
     298    80382593 :       yi = uel(y,i);   x[i]   ^= (yi<<db)|r; r = yi>>dc;
     299    80382593 :       yi = uel(y,i+1); x[i+1] ^= (yi<<db)|r; r = yi>>dc;
     300    80382593 :       yi = uel(y,i+2); x[i+2] ^= (yi<<db)|r; r = yi>>dc;
     301    80382593 :       yi = uel(y,i+3); x[i+3] ^= (yi<<db)|r; r = yi>>dc;
     302             :     }
     303   278878678 :     for(  ; i<ny; i++)
     304             :     {
     305   135969957 :       ulong yi = uel(y,i); x[i] ^= (yi<<db)|r; r = yi>>dc;
     306             :     }
     307   142908721 :     if (r) x[i] ^= r;
     308             :   }
     309             :   else
     310             :   {
     311    27083584 :     for(i=0; i<ny-3; i+=4)
     312             :     {
     313     3353107 :       x[i]   ^= y[i];
     314     3353107 :       x[i+1] ^= y[i+1];
     315     3353107 :       x[i+2] ^= y[i+2];
     316     3353107 :       x[i+3] ^= y[i+3];
     317             :     }
     318    51223510 :     for(   ; i<ny; i++)
     319    27493033 :       x[i] ^= y[i];
     320             :   }
     321   166639198 : }
     322             : 
     323             : INLINE void
     324   135119602 : F2x_addshiftip(GEN x, GEN y, ulong d)
     325             : {
     326   135119602 :   ulong db, dl=dvmduBIL(d, &db);
     327   134613932 :   F2x_addshiftipspec(x+2+dl, y+2, lgpol(y), db);
     328   134902164 : }
     329             : 
     330             : static GEN
     331    18602801 : F2x_mul1(ulong x, ulong y)
     332             : {
     333    18602801 :   ulong x1=(x&HIGHMASK)>>BITS_IN_HALFULONG;
     334    18602801 :   ulong x2=x&LOWMASK;
     335    18602801 :   ulong y1=(y&HIGHMASK)>>BITS_IN_HALFULONG;
     336    18602801 :   ulong y2=y&LOWMASK;
     337             :   ulong r1,r2,rr;
     338             :   GEN z;
     339             :   ulong i;
     340    18602801 :   rr=r1=r2=0UL;
     341    18602801 :   if (x2)
     342   573873454 :     for(i=0;i<BITS_IN_HALFULONG;i++)
     343   555309632 :       if (x2&(1UL<<i))
     344             :       {
     345    49724620 :         r2^=y2<<i;
     346    49724620 :         rr^=y1<<i;
     347             :       }
     348    18602801 :   if (x1)
     349     3468173 :     for(i=0;i<BITS_IN_HALFULONG;i++)
     350     3347319 :       if (x1&(1UL<<i))
     351             :       {
     352      913670 :         r1^=y1<<i;
     353      913670 :         rr^=y2<<i;
     354             :       }
     355    18602801 :   r2^=(rr&LOWMASK)<<BITS_IN_HALFULONG;
     356    18602801 :   r1^=(rr&HIGHMASK)>>BITS_IN_HALFULONG;
     357    18602801 :   z=cgetg((r1?4:3),t_VECSMALL);
     358    18603013 :   z[2]=r2;
     359    18603013 :   if (r1) z[3]=r1;
     360    18603013 :   return z;
     361             : }
     362             : 
     363             : static GEN
     364     5113241 : F2x_mulspec_basecase(GEN x, GEN y, long nx, long ny)
     365             : {
     366             :   long l, i, j;
     367             :   GEN z;
     368     5113241 :   l = nx + ny;
     369     5113241 :   z = zero_Flv(l+1);
     370     5772440 :   for(i=0; i < ny-1; i++)
     371             :   {
     372      659547 :     GEN zi = z+2+i;
     373      659547 :     ulong yi = uel(y,i);
     374      659547 :     if (yi)
     375    36254308 :       for(j=0; j < BITS_IN_LONG; j++)
     376    35595689 :         if (yi&(1UL<<j)) F2x_addshiftipspec(zi,x,nx,j);
     377             :   }
     378             :   {
     379     5112893 :     GEN zi = z+2+i;
     380     5112893 :     ulong yi = uel(y,i);
     381     5112893 :     long c = BITS_IN_LONG-bfffo(yi);
     382    32937014 :     for(j=0; j < c; j++)
     383    27825092 :       if (yi&(1UL<<j)) F2x_addshiftipspec(zi,x,nx,j);
     384             :   }
     385     5111922 :   return F2x_renormalize(z, l+2);
     386             : }
     387             : 
     388             : static GEN
     389       38503 : F2x_addshift(GEN x, GEN y, long d)
     390             : {
     391       38503 :   GEN xd,yd,zd = (GEN)avma;
     392       38503 :   long a,lz,ny = lgpol(y), nx = lgpol(x);
     393       38503 :   long vs = x[1];
     394       38503 :   if (nx == 0) return y;
     395       38503 :   x += 2; y += 2; a = ny-d;
     396       38503 :   if (a <= 0)
     397             :   {
     398        3127 :     lz = (a>nx)? ny+2: nx+d+2;
     399        3127 :     (void)new_chunk(lz); xd = x+nx; yd = y+ny;
     400       36811 :     while (xd > x) *--zd = *--xd;
     401        3127 :     x = zd + a;
     402        4332 :     while (zd > x) *--zd = 0;
     403             :   }
     404             :   else
     405             :   {
     406       35376 :     xd = new_chunk(d); yd = y+d;
     407       35376 :     x = F2x_addspec(x,yd,nx,a);
     408       35376 :     lz = (a>nx)? ny+2: lg(x)+d;
     409      742269 :     x += 2; while (xd > x) *--zd = *--xd;
     410             :   }
     411      448585 :   while (yd > y) *--zd = *--yd;
     412       38503 :   *--zd = vs;
     413       38503 :   *--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    23743475 : F2x_shiftip(pari_sp av, GEN x, long v)
     420             : {
     421    23743475 :   long i, lx = lg(x), ly;
     422             :   GEN y;
     423    23743475 :   if (!v || lx==2) return gerepileuptoleaf(av, x);
     424       28589 :   ly = lx + v;
     425       28589 :   (void)new_chunk(ly); /* check that result fits */
     426       28590 :   x += lx; y = (GEN)av;
     427      123312 :   for (i = 2; i<lx; i++) *--y = *--x;
     428      159558 :   for (i = 0; i< v; i++) *--y = 0;
     429       28590 :   y -= 2; y[0] = evaltyp(t_VECSMALL) | evallg(ly);
     430       28589 :   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      865989 :     for (j=0; j<BIL; j++, m+=bs)
     444             :     {
     445      852729 :       if (m >= BIL)
     446             :       {
     447      173157 :         k++; if (k>=lz) break;
     448      172953 :         zs = int_nextW(zs);
     449      172953 :         *zs = 0;
     450      172953 :         m -= BIL;
     451             :       }
     452      852525 :       *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      865647 :     for (j=0; j<BIL; j++, m+=bs)
     470             :     {
     471      852387 :       if (m >= BIL)
     472             :       {
     473      173109 :         if (++k==lx) break;
     474      173007 :         xs = int_nextW(xs);
     475      173007 :         m -= BIL;
     476             :       }
     477      852285 :       if ((*xs>>m)&1UL)
     478      385725 :         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    28174428 : F2x_mulspec(GEN a, GEN b, long na, long nb)
     501             : {
     502             :   GEN a0,c,c0;
     503    28174428 :   long n0, n0a, i, v = 0;
     504             :   pari_sp av;
     505    28280652 :   while (na && !a[0]) { a++; na-=1; v++; }
     506    28199372 :   while (nb && !b[0]) { b++; nb-=1; v++; }
     507    28174428 :   if (na < nb) swapspec(a,b, na,nb);
     508    28174428 :   if (!nb) return pol0_F2x(0);
     509             : 
     510    23743098 :   av = avma;
     511    23743098 :   if (na == 1)
     512    18602818 :     return F2x_shiftip(av, F2x_mul1(*a,*b), v);
     513     5140280 :   if (na < F2x_MUL_KARATSUBA_LIMIT)
     514     5113224 :     return F2x_shiftip(av, F2x_mulspec_basecase(a, b, na, nb), v);
     515       27056 :   if (nb >= F2x_MUL_MULII_LIMIT)
     516         102 :     return F2x_shiftip(av, F2x_mulspec_mulii(a, b, na, nb), v);
     517       26954 :   i=(na>>1); n0=na-i; na=i;
     518       26954 :   a0=a+n0; n0a=n0;
     519       27030 :   while (n0a && !a[n0a-1]) n0a--;
     520             : 
     521       26954 :   if (nb > n0)
     522             :   {
     523             :     GEN b0,c1,c2;
     524             :     long n0b;
     525             : 
     526       11187 :     nb -= n0; b0 = b+n0; n0b = n0;
     527       11195 :     while (n0b && !b[n0b-1]) n0b--;
     528       11187 :     c =  F2x_mulspec(a,b,n0a,n0b);
     529       11187 :     c0 = F2x_mulspec(a0,b0,na,nb);
     530             : 
     531       11187 :     c2 = F2x_addspec(a0,a,na,n0a);
     532       11187 :     c1 = F2x_addspec(b0,b,nb,n0b);
     533             : 
     534       11187 :     c1 = F2x_mul(c1,c2);
     535       11187 :     c2 = F2x_add(c0,c);
     536             : 
     537       11187 :     c2 = F2x_add(c1,c2);
     538       11187 :     c0 = F2x_addshift(c0,c2,n0);
     539             :   }
     540             :   else
     541             :   {
     542       15767 :     c  = F2x_mulspec(a,b,n0a,nb);
     543       16129 :     c0 = F2x_mulspec(a0,b,na,nb);
     544             :   }
     545       27316 :   c0 = F2x_addshift(c0,c,n0);
     546       27316 :   return F2x_shiftip(av,c0, v);
     547             : }
     548             : 
     549             : GEN
     550    28119584 : F2x_mul(GEN x, GEN y)
     551             : {
     552    28119584 :   GEN z = F2x_mulspec(x+2,y+2, lgpol(x),lgpol(y));
     553    28120209 :   z[1] = x[1]; return z;
     554             : }
     555             : 
     556             : GEN
     557     8533699 : F2x_sqr(GEN x)
     558             : {
     559     8533699 :   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     8533699 :   long lx=lg(x), lz=2+((lx-2)<<1);
     562             :   GEN z;
     563     8533699 :   z = cgetg(lz, t_VECSMALL); z[1]=x[1];
     564    17244275 :   for (j=2,jj=2;j<lx;j++,jj++)
     565             :   {
     566     8680163 :     ulong x1=((ulong)x[j]&HIGHMASK)>>BITS_IN_HALFULONG;
     567     8680163 :     ulong x2=(ulong)x[j]&LOWMASK;
     568     8680163 :     z[jj]=0;
     569     8680163 :     if (x2)
     570    72533622 :       for(i=0,ii=0;i<BITS_IN_HALFULONG;i+=4,ii+=8)
     571    63912068 :         z[jj]|=sq[(x2>>i)&15UL]<<ii;
     572     8680163 :     z[++jj]=0;
     573     8680163 :     if (x1)
     574     6219305 :       for(i=0,ii=0;i<BITS_IN_HALFULONG;i+=4,ii+=8)
     575     5410121 :         z[jj]|=sq[(x1>>i)&15UL]<<ii;
     576             :   }
     577     8564112 :   return F2x_renormalize(z, lz);
     578             : }
     579             : 
     580             : static GEN
     581      153309 : F2x_pow2n(GEN x, long n)
     582             : {
     583             :   long i;
     584      459926 :   for(i=1;i<=n;i++)
     585      306553 :     x = F2x_sqr(x);
     586      153373 :   return x;
     587             : }
     588             : 
     589             : int
     590       36896 : F2x_issquare(GEN x)
     591             : {
     592       36896 :   const ulong mask = (ULONG_MAX/3UL)*2;
     593       36896 :   ulong i, lx = lg(x);
     594       73792 :   for (i=2; i<lx; i++)
     595       36896 :     if ((x[i]&mask)) return 0;
     596       36896 :   return 1;
     597             : }
     598             : 
     599             : /* Assume x is a perfect square */
     600             : GEN
     601      241424 : F2x_sqrt(GEN x)
     602             : {
     603      241424 :   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      241424 :   long lx=lg(x), lz=2+((lx-1)>>1);
     606             :   GEN z;
     607      241424 :   z = cgetg(lz, t_VECSMALL); z[1]=x[1];
     608      482900 :   for (j=2,jj=2;jj<lz;j++,jj++)
     609             :   {
     610      241467 :     ulong x2=x[j++];
     611      241467 :     z[jj]=0;
     612      241467 :     if (x2)
     613     2036487 :       for(i=0,ii=0;ii<BITS_IN_HALFULONG;i+=8,ii+=4)
     614             :       {
     615     1795032 :         ulong rl = (x2>>i)&15UL, rh = (x2>>(i+4))&15UL;
     616     1795032 :         z[jj]|=sq[rl|(rh<<1)]<<ii;
     617             :       }
     618      241467 :     if (j<lx)
     619             :     {
     620         352 :       x2 = x[j];
     621         352 :       if (x2)
     622        2237 :         for(i=0,ii=0;ii<BITS_IN_HALFULONG;i+=8,ii+=4)
     623             :         {
     624        1900 :           ulong rl = (x2>>i)&15UL, rh = (x2>>(i+4))&15UL;
     625        1900 :           z[jj]|=(sq[rl|(rh<<1)]<<ii)<<BITS_IN_HALFULONG;
     626             :         }
     627             :     }
     628             :   }
     629      241433 :   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      257460 : F2x_shiftpos(GEN y, ulong d)
     659             : {
     660      257460 :   long db, dl=dvmdsBIL(d, &db);
     661      257295 :   long i, ly = lg(y), lx = ly+dl+(!!db);
     662      257295 :   GEN x = cgetg(lx, t_VECSMALL);
     663      257409 :   x[1] = y[1]; for(i=0; i<dl; i++) x[i+2] = 0;
     664      257348 :   if (db)
     665             :   {
     666      257302 :     ulong dc=BITS_IN_LONG-db;
     667      257302 :     ulong r=0;
     668      518092 :     for(i=2; i<ly; i++)
     669             :     {
     670      260790 :       x[i+dl] = (((ulong)y[i])<<db)|r;
     671      260790 :       r = ((ulong)y[i])>>dc;
     672             :     }
     673      257302 :     x[i+dl] = r;
     674             :   }
     675             :   else
     676          60 :     for(i=2; i<ly; i++)
     677          14 :       x[i+dl] = y[i];
     678      257348 :   return F2x_renormalize(x,lx);
     679             : }
     680             : 
     681             : GEN
     682      258458 : F2x_shift(GEN y, long d)
     683             : {
     684      258458 :   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          28 : F2x_recip1(ulong u)
     692             : {
     693          28 :   u = (u<<BITS_IN_HALFULONG)|(u>>BITS_IN_HALFULONG);
     694             : #ifdef LONG_IS_64BIT
     695          24 :   F2x_recipu(16);
     696             : #endif
     697          28 :   F2x_recipu(8);
     698          28 :   F2x_recipu(4);
     699          28 :   F2x_recipu(2);
     700          28 :   F2x_recipu(1);
     701          28 :   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          28 : F2xn_inv_basecase1(ulong x)
     744             : {
     745             :   ulong u, v, w;
     746             :   long i;
     747          28 :   u = x>>1;
     748          28 :   v = (u&1UL)|2UL;
     749          28 :   w = u&v; w ^= w >> 1; v = (w&1UL)|(v<<1);
     750          28 :   w = u&v; w ^= w >> 2; w ^= w >> 1; v = (w&1UL)|(v<<1);
     751          28 :   w = u&v; w ^= w >> 2; w ^= w >> 1; v = (w&1UL)|(v<<1);
     752         140 :   for (i=1;i<=4;i++)
     753         112 :   { w = u&v; w ^= w >> 4; w ^= w >> 2; w ^= w >> 1; v = (w&1UL)|(v<<1); }
     754         252 :   for (i=1;i<=8;i++)
     755         224 :   { w = u&v; w ^= w >> 8; w ^= w >> 4; w ^= w >> 2; w ^= w >> 1;
     756         224 :     v = (w&1UL)|(v<<1); }
     757         476 :   for (i=1;i<=16;i++)
     758         448 :   { w = u&v; w ^= w >> 16; w ^= w >> 8; w ^= w >> 4; w ^= w >> 2; w ^= w >> 1;
     759         448 :     v = (w&1UL)|(v<<1); }
     760             : #ifdef LONG_IS_64BIT
     761         792 :   for (i=1; i<=32; i++)
     762         768 :   { w = u&v; w ^= w >> 32; w ^= w >> 16; w ^= w >> 8; w ^= w >> 4; w ^= w >> 2;
     763         768 :     w ^= w >> 1; v = (w&1UL)|(v<<1); }
     764             : #endif
     765          28 :   return (F2x_recip1(v)<<1) | 1UL;
     766             : }
     767             : 
     768             : static GEN
     769          28 : F2xn_inv1(GEN v, long e)
     770             : {
     771          28 :   ulong mask = e==BITS_IN_LONG ? -1UL: ((1UL<<e)-1);
     772          28 :   return mkvecsmall2(v[1],F2xn_inv_basecase1(uel(v,2))&mask);
     773             : }
     774             : 
     775             : static GEN
     776          14 : F2xn_div1(GEN g, GEN f, long e)
     777             : {
     778          14 :   GEN fi = F2xn_inv1(f, e);
     779          14 :   return g ? F2xn_mul(g, fi, e): fi;
     780             : }
     781             : 
     782             : GEN
     783          28 : F2xn_div(GEN g, GEN f, long e)
     784             : {
     785          28 :   pari_sp av = avma, av2;
     786             :   ulong mask;
     787             :   GEN W;
     788          28 :   long n=1;
     789          28 :   if (lg(f)<=2) pari_err_INV("Flxn_inv",f);
     790          28 :   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          14 : F2xn_inv(GEN f, long e)
     823          14 : { return F2xn_div(NULL, f, e); }
     824             : 
     825             : GEN
     826      218554 : F2x_get_red(GEN T)
     827             : {
     828      218554 :   return T;
     829             : }
     830             : 
     831             : /* separate from F2x_divrem for maximal speed. */
     832             : GEN
     833    46079786 : F2x_rem(GEN x, GEN y)
     834             : {
     835             :   long dx,dy;
     836    46079786 :   long lx=lg(x);
     837    46079786 :   dy = F2x_degree(y); if (!dy) return pol0_F2x(x[1]);
     838    43272930 :   dx = F2x_degree_lg(x,lx);
     839    43354735 :   x  = F2x_copy(x);
     840   154257702 :   while (dx>=dy)
     841             :   {
     842   110851883 :     F2x_addshiftip(x,y,dx-dy);
     843   112917667 :     while (lx>2 && x[lx-1]==0) lx--;
     844   110274912 :     dx = F2x_degree_lg(x,lx);
     845             :   }
     846    43405819 :   return F2x_renormalize(x, lx);
     847             : }
     848             : 
     849             : GEN
     850    11954158 : F2x_divrem(GEN x, GEN y, GEN *pr)
     851             : {
     852    11954158 :   long dx, dy, dz, lx = lg(x), vs = x[1];
     853             :   GEN z;
     854             : 
     855    11954158 :   dy = F2x_degree(y);
     856    11954339 :   if (dy<0) pari_err_INV("F2x_divrem",y);
     857    11954316 :   if (pr == ONLY_REM) return F2x_rem(x, y);
     858    11954316 :   if (!dy)
     859             :   {
     860     1712460 :     z = F2x_copy(x);
     861     1712485 :     if (pr && pr != ONLY_DIVIDES) *pr = pol0_F2x(vs);
     862     1712485 :     return z;
     863             :   }
     864    10241856 :   dx = F2x_degree_lg(x,lx);
     865    10242321 :   dz = dx-dy;
     866    10242321 :   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    10242307 :   z = zero_zv(lg(x)-lg(y)+2); z[1] = vs;
     874    10243398 :   x = F2x_copy(x);
     875    33657448 :   while (dx>=dy)
     876             :   {
     877    23416117 :     F2x_set(z,dx-dy);
     878    23388521 :     F2x_addshiftip(x,y,dx-dy);
     879    24733966 :     while (lx>2 && x[lx-1]==0) lx--;
     880    23326172 :     dx = F2x_degree_lg(x,lx);
     881             :   }
     882    10241331 :   z = F2x_renormalize(z, lg(z));
     883    10243393 :   if (!pr) { cgiv(x); return z; }
     884     9242367 :   x = F2x_renormalize(x, lx);
     885     9242335 :   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     9242335 :   *pr = x; return z;
     890             : }
     891             : 
     892             : long
     893       35306 : F2x_valrem(GEN x, GEN *Z)
     894             : {
     895       35306 :   long v, v2, i, l=lg(x);
     896             :   GEN y;
     897       35306 :   if (l==2) { *Z = F2x_copy(x); return LONG_MAX; }
     898       35309 :   for (i=2; i<l && x[i]==0; i++) /*empty*/;
     899       35306 :   v = i-2;
     900       35306 :   v2 = (i < l)? vals(x[i]): 0;
     901       35306 :   if (v+v2 == 0) { *Z = x; return 0; }
     902       11286 :   l -= i-2;
     903       11286 :   y = cgetg(l, t_VECSMALL); y[1] = x[1];
     904       11286 :   if (v2 == 0)
     905           6 :     for (i=2; i<l; i++) y[i] = x[i+v];
     906       11283 :   else if (l == 3)
     907       11257 :     y[2] = ((ulong)x[2+v]) >> v2;
     908             :   else
     909             :   {
     910          26 :     const ulong sh = BITS_IN_LONG - v2;
     911          26 :     ulong r = x[2+v];
     912          52 :     for (i=3; i<l; i++)
     913             :     {
     914          26 :       y[i-1] = (x[i+v] << sh) | (r >> v2);
     915          26 :       r = x[i+v];
     916             :     }
     917          26 :     y[l-1] = r >> v2;
     918          26 :     (void)F2x_renormalize(y,l);
     919             :   }
     920       11286 :   *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       62660 : F2x_even_odd(GEN p, GEN *pe, GEN *po)
     940             : {
     941       62660 :   long n = F2x_degree(p), n0, n1, i;
     942             :   GEN p0, p1;
     943             : 
     944       62659 :   if (n <= 0) { *pe = F2x_copy(p); *po = pol0_F2x(p[1]); return; }
     945             : 
     946       58760 :   n0 = (n>>1)+1; n1 = n+1 - n0; /* n1 <= n0 <= n1+1 */
     947       58760 :   p0 = zero_zv(nbits2lg(n0+1)-1); p0[1] = p[1];
     948       58759 :   p1 = zero_zv(nbits2lg(n1+1)-1); p1[1] = p[1];
     949     2251944 :   for (i=0; i<n1; i++)
     950             :   {
     951     2193182 :     if (F2x_coeff(p,i<<1)) F2x_set(p0,i);
     952     2192945 :     if (F2x_coeff(p,1+(i<<1))) F2x_set(p1,i);
     953             :   }
     954       58762 :   if (n1 != n0 && F2x_coeff(p,i<<1)) F2x_set(p0,i);
     955       58762 :   *pe = F2x_renormalize(p0,lg(p0));
     956       58764 :   *po = F2x_renormalize(p1,lg(p1));
     957             : }
     958             : 
     959             : GEN
     960     1218407 : F2x_deriv(GEN z)
     961             : {
     962     1218407 :   const ulong mask = ULONG_MAX/3UL;
     963     1218407 :   long i,l = lg(z);
     964     1218407 :   GEN x = cgetg(l, t_VECSMALL); x[1] = z[1];
     965     2442865 :   for (i=2; i<l; i++) x[i] = (((ulong)z[i])>>1)&mask;
     966     1218470 :   return F2x_renormalize(x,l);
     967             : }
     968             : 
     969             : GEN
     970     3599183 : F2x_gcd(GEN a, GEN b)
     971             : {
     972     3599183 :   pari_sp av = avma;
     973     3599183 :   if (lg(b) > lg(a)) swap(a, b);
     974    22696453 :   while (lgpol(b))
     975             :   {
     976    18806220 :     GEN c = F2x_rem(a,b);
     977    19097270 :     a = b; b = c;
     978    19097270 :     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     3587909 :   if (gc_needed(av,2)) a = gerepileuptoleaf(av, a);
     985     3587909 :   return a;
     986             : }
     987             : 
     988             : GEN
     989     1446562 : F2x_extgcd(GEN a, GEN b, GEN *ptu, GEN *ptv)
     990             : {
     991     1446562 :   pari_sp av=avma;
     992             :   GEN u,v,d,d1,v1;
     993     1446562 :   long vx = a[1];
     994     1446562 :   d = a; d1 = b;
     995     1446562 :   v = pol0_F2x(vx); v1 = pol1_F2x(vx);
     996    12127592 :   while (lgpol(d1))
     997             :   {
     998    10681029 :     GEN r, q = F2x_divrem(d,d1, &r);
     999    10681028 :     v = F2x_add(v,F2x_mul(q,v1));
    1000    10681030 :     u=v; v=v1; v1=u;
    1001    10681030 :     u=r; d=d1; d1=u;
    1002    10681030 :     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     1446549 :   if (ptu) *ptu = F2x_div(F2x_add(d, F2x_mul(b,v)), a);
    1009     1446549 :   *ptv = v;
    1010     1446549 :   if (gc_needed(av,2)) gerepileall(av,ptu?3:2,&d,ptv,ptu);
    1011     1446561 :   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, mkmat2(mkcol2(u,u1), mkcol2(v,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     9441511 : F2xq_mul(GEN x,GEN y,GEN pol)
    1054             : {
    1055     9441511 :   GEN z = F2x_mul(x,y);
    1056     9442095 :   return F2x_rem(z,pol);
    1057             : }
    1058             : 
    1059             : GEN
    1060     8231612 : F2xq_sqr(GEN x,GEN pol)
    1061             : {
    1062     8231612 :   GEN z = F2x_sqr(x);
    1063     8254122 :   return F2x_rem(z,pol);
    1064             : }
    1065             : 
    1066             : GEN
    1067     1446562 : F2xq_invsafe(GEN x, GEN T)
    1068             : {
    1069     1446562 :   GEN V, z = F2x_extgcd(get_F2x_mod(T), x, NULL, &V);
    1070     1446561 :   if (F2x_degree(z)) return NULL;
    1071     1446492 :   return V;
    1072             : }
    1073             : 
    1074             : GEN
    1075     1446555 : F2xq_inv(GEN x,GEN T)
    1076             : {
    1077     1446555 :   pari_sp av=avma;
    1078     1446555 :   GEN U = F2xq_invsafe(x, T);
    1079     1446555 :   if (!U) pari_err_INV("F2xq_inv", F2x_to_ZX(x));
    1080     1446485 :   return gerepileuptoleaf(av, U);
    1081             : }
    1082             : 
    1083             : GEN
    1084      576068 : F2xq_div(GEN x,GEN y,GEN T)
    1085             : {
    1086      576068 :   pari_sp av = avma;
    1087      576068 :   return gerepileuptoleaf(av, F2xq_mul(x,F2xq_inv(y,T),T));
    1088             : }
    1089             : 
    1090             : static GEN
    1091      576944 : _F2xq_red(void *E, GEN x) { return F2x_rem(x, (GEN)E); }
    1092             : static GEN
    1093     1639284 : _F2xq_add(void *E, GEN x, GEN y) { (void)E; return F2x_add(x,y); }
    1094             : 
    1095             : static GEN
    1096     2025774 : _F2xq_cmul(void *E, GEN P, long a, GEN x)
    1097             : {
    1098     2025774 :   GEN pol = (GEN) E;
    1099     2025774 :   return F2x_coeff(P,a) ? x: pol0_F2x(pol[1]);
    1100             : }
    1101             : static GEN
    1102      801477 : _F2xq_sqr(void *E, GEN x) { return F2xq_sqr(x, (GEN) E); }
    1103             : static GEN
    1104     1570521 : _F2xq_mul(void *E, GEN x, GEN y) { return F2xq_mul(x,y, (GEN) E); }
    1105             : 
    1106             : static GEN
    1107      922199 : _F2xq_one(void *E)
    1108             : {
    1109      922199 :   GEN pol = (GEN) E;
    1110      922199 :   return pol1_F2x(pol[1]);
    1111             : }
    1112             : static GEN
    1113      259707 : _F2xq_zero(void *E)
    1114             : {
    1115      259707 :   GEN pol = (GEN) E;
    1116      259707 :   return pol0_F2x(pol[1]);
    1117             : }
    1118             : 
    1119             : GEN
    1120      599334 : F2xq_pow(GEN x, GEN n, GEN pol)
    1121             : {
    1122      599334 :   pari_sp av=avma;
    1123             :   GEN y;
    1124             : 
    1125      599334 :   if (!signe(n)) return pol1_F2x(x[1]);
    1126      591655 :   if (is_pm1(n)) /* +/- 1 */
    1127      409416 :     return (signe(n) < 0)? F2xq_inv(x,pol): F2x_copy(x);
    1128             : 
    1129      182239 :   if (signe(n) < 0) x = F2xq_inv(x,pol);
    1130      182239 :   y = gen_pow_i(x, n, (void*)pol, &_F2xq_sqr, &_F2xq_mul);
    1131      182240 :   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        5247 : F2xq_pow_table(GEN R, GEN n, GEN T)
    1157             : {
    1158        5247 :   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      365798 : F2xq_powers(GEN x, long l, GEN T)
    1164             : {
    1165      365798 :   int use_sqr = 2*F2x_degree(x) >= get_F2x_degree(T);
    1166      365799 :   return gen_powers(x, l, use_sqr, (void*)T, &_F2xq_sqr, &_F2xq_mul, &_F2xq_one);
    1167             : }
    1168             : 
    1169             : GEN
    1170      236332 : F2xq_matrix_pow(GEN y, long n, long m, GEN P)
    1171             : {
    1172      236332 :   return F2xV_to_F2m(F2xq_powers(y,m-1,P),n);
    1173             : }
    1174             : 
    1175             : GEN
    1176      599040 : F2x_Frobenius(GEN T)
    1177             : {
    1178      599040 :   return F2xq_sqr(polx_F2x(get_F2x_var(T)), T);
    1179             : }
    1180             : 
    1181             : GEN
    1182      236334 : F2x_matFrobenius(GEN T)
    1183             : {
    1184      236334 :   long n = get_F2x_degree(T);
    1185      236333 :   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      609917 : F2x_F2xqV_eval(GEN Q, GEN x, GEN T)
    1193             : {
    1194      609917 :   long d = F2x_degree(Q);
    1195      609917 :   return gen_bkeval_powers(Q,d,x,(void*)T,&F2xq_algebra,_F2xq_cmul);
    1196             : }
    1197             : 
    1198             : GEN
    1199       43386 : F2x_F2xq_eval(GEN Q, GEN x, GEN T)
    1200             : {
    1201       43386 :   long d = F2x_degree(Q);
    1202       43386 :   int use_sqr = 2*F2x_degree(x) >= get_F2x_degree(T);
    1203       43385 :   return gen_bkeval(Q, d, x, use_sqr, (void*)T, &F2xq_algebra, _F2xq_cmul);
    1204             : }
    1205             : 
    1206             : static GEN
    1207       28200 : F2xq_autpow_sqr(void * T, GEN x) { return F2x_F2xq_eval(x, x, (GEN) T); }
    1208             : 
    1209             : static GEN
    1210       14458 : F2xq_autpow_mul(void * T, GEN x, GEN y) { return F2x_F2xq_eval(x, y, (GEN) T); }
    1211             : 
    1212             : GEN
    1213       18406 : F2xq_autpow(GEN x, long n, GEN T)
    1214             : {
    1215       18406 :   if (n==0) return F2x_rem(polx_F2x(x[1]), T);
    1216       18406 :   if (n==1) return F2x_rem(x, T);
    1217       18406 :   return gen_powu(x,n,(void*)T,F2xq_autpow_sqr,F2xq_autpow_mul);
    1218             : }
    1219             : 
    1220             : ulong
    1221      458055 : F2xq_trace(GEN x, GEN T)
    1222             : {
    1223      458055 :   pari_sp av = avma;
    1224      458055 :   long n = get_F2x_degree(T)-1;
    1225      458055 :   GEN z = F2xq_mul(x, F2x_deriv(get_F2x_mod(T)), T);
    1226      458055 :   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      556081 : _F2xq_pow(void *data, GEN x, GEN n)
    1241             : {
    1242      556081 :   GEN pol = (GEN) data;
    1243      556081 :   return F2xq_pow(x,n, pol);
    1244             : }
    1245             : 
    1246             : static GEN
    1247        9037 : _F2xq_rand(void *data)
    1248             : {
    1249        9037 :   pari_sp av=avma;
    1250        9037 :   GEN pol = (GEN) data;
    1251        9037 :   long d = F2x_degree(pol);
    1252             :   GEN z;
    1253             :   do
    1254             :   {
    1255        9191 :     set_avma(av);
    1256        9191 :     z = random_F2x(d,pol[1]);
    1257        9191 :   } while (lgpol(z)==0);
    1258        9037 :   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      268281 : F2x_is_smooth_squarefree(GEN f, long r)
    1273             : {
    1274      268281 :   pari_sp av = avma;
    1275      268281 :   long i, df = F2x_degree(f);
    1276             :   GEN sx, a;
    1277      268284 :   if (!df) return 1;
    1278      263251 :   a = sx = polx_F2x(f[1]);
    1279      263374 :   for(i = 1;; i++)
    1280     2185230 :   {
    1281             :     long dg;
    1282             :     GEN g;
    1283     2448604 :     a = F2xq_sqr(a, f);
    1284     2437817 :     if (F2x_equal(a, sx)) return gc_long(av,1);
    1285     2377167 :     if (i==r) return gc_long(av,0);
    1286     2204981 :     g = F2x_gcd(f, F2x_add(a,sx));
    1287     2211583 :     dg = F2x_degree(g);
    1288     2207842 :     if (dg == df) return gc_long(av,1);
    1289     2185473 :     if (dg) { f = F2x_div(f, g); df -= dg; a = F2x_rem(a, f); }
    1290             :   }
    1291             : }
    1292             : 
    1293             : static long
    1294      231698 : F2x_is_smooth(GEN g, long r)
    1295             : {
    1296      231698 :   if (lgpol(g)==0) return 0;
    1297             :   while (1)
    1298       36901 :   {
    1299      268558 :     GEN f = F2x_gcd(g, F2x_deriv(g));
    1300      268323 :     if (!F2x_is_smooth_squarefree(F2x_div(g, f), r)) return 0;
    1301       96317 :     if (F2x_degree(f)==0) return 1;
    1302       36856 :     g = F2x_issquare(f) ? F2x_sqrt(f): f;
    1303             :   }
    1304             : }
    1305             : 
    1306             : static GEN
    1307       15249 : F2x_factorel(GEN h)
    1308             : {
    1309       15249 :   GEN F = F2x_factor(h);
    1310       15251 :   GEN F1 = gel(F, 1), F2 = gel(F, 2);
    1311       15251 :   long i, l1 = lg(F1)-1;
    1312       15251 :   GEN p2 = cgetg(l1+1, t_VECSMALL);
    1313       15249 :   GEN e2 = cgetg(l1+1, t_VECSMALL);
    1314       71397 :   for (i = 1; i <= l1; ++i)
    1315             :   {
    1316       56148 :     p2[i] = mael(F1, i, 2);
    1317       56148 :     e2[i] = F2[i];
    1318             :   }
    1319       15249 :   return mkmat2(p2, e2);
    1320             : }
    1321             : 
    1322             : static GEN
    1323       26235 : 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      154428 : rel_Coppersmith(GEN u, GEN v, long h, GEN R, long r, long n, long d)
    1491             : {
    1492             :   GEN b, F, G, M;
    1493      154428 :   GEN a = F2x_add(F2x_shift(u, h), v);
    1494      154399 :   if (!F2x_is_smooth(a, r)) return NULL;
    1495       51572 :   b = F2x_add(F2x_mul(R, F2x_pow2n(u, n)), F2x_shift(F2x_pow2n(v, n),d));
    1496       51576 :   if (!F2x_is_smooth(b, r)) return NULL;
    1497        7485 :   F = F2x_factorel(a);
    1498        7486 :   G = F2x_factorel(b);
    1499       14972 :   M = mkmat2(vecsmall_concat(gel(F, 1), vecsmall_append(gel(G, 1), 2)),
    1500       14972 :              vecsmall_concat(zv_z_mul(gel(F, 2),1UL<<n), vecsmall_append(zv_neg(gel(G, 2)),d)));
    1501        7486 :   return famatsmall_reduce(M);
    1502             : }
    1503             : 
    1504             : GEN
    1505        2109 : F2xq_log_Coppersmith_worker(GEN u, long i, GEN V, GEN R)
    1506             : {
    1507        2109 :   long r = V[1], h = V[2], n = V[3], d = V[4];
    1508        2109 :   pari_sp ltop = avma;
    1509        2109 :   GEN v = mkF2(0,u[1]);
    1510        2102 :   GEN L = cgetg(2*i+1, t_VEC);
    1511        2108 :   pari_sp av = avma;
    1512             :   long j;
    1513        2108 :   long nbtest=0, rel = 1;
    1514      155010 :   for(j=1; j<=i; j++)
    1515             :   {
    1516      152892 :     v[2] = j;
    1517      152892 :     set_avma(av);
    1518      152904 :     if (F2x_degree(F2x_gcd(u,v))==0)
    1519             :     {
    1520       77225 :       GEN z = rel_Coppersmith(u, v, h, R, r, n, d);
    1521       77263 :       nbtest++;
    1522       77263 :       if (z) { gel(L, rel++) = z; av = avma; }
    1523       77263 :       if (i==j) continue;
    1524       77249 :       z = rel_Coppersmith(v, u, h, R, r, n, d);
    1525       77233 :       nbtest++;
    1526       77233 :       if (z) { gel(L, rel++) = z; av = avma; }
    1527             :     }
    1528             :   }
    1529        2118 :   setlg(L,rel);
    1530        2118 :   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        2194 :   while ((running = !stop) || pending)
    1550             :   {
    1551             :     GEN L, done;
    1552             :     long j, l;
    1553        2180 :     u[2] = i;
    1554        2180 :     mt_queue_submit(&pt, 0, running ? mkvec2(u, stoi(i)): NULL);
    1555        2180 :     done = mt_queue_get(&pt, NULL, &pending);
    1556        2180 :     if (!done) continue;
    1557        2118 :     L = gel(done, 2); nbtest += itos(gel(done,1));
    1558        2118 :     l = lg(L);
    1559        2118 :     if (l > 1)
    1560             :     {
    1561        9152 :       for (j=1; j<l; j++)
    1562             :       {
    1563        7276 :         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        2118 :     if (rel>nbrel) stop=1;
    1570        2118 :     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       52083 :       gel(K,i) = cgetineg(lm);
    1608             :     else
    1609        5247 :       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      150787 : F2xq_easylog(void* E, GEN a, GEN g, GEN ord)
    1652             : {
    1653      150787 :   if (F2x_equal1(a)) return gen_0;
    1654      115678 :   if (F2x_equal(a,g)) return gen_1;
    1655      114859 :   if (typ(ord)!=t_INT) return NULL;
    1656       57776 :   if (expi(ord)<28) return NULL;
    1657          14 :   return F2xq_log_index(a,g,ord,(GEN)E);
    1658             : }
    1659             : 
    1660             : GEN
    1661      135492 : F2xq_log(GEN a, GEN g, GEN ord, GEN T)
    1662             : {
    1663      135492 :   GEN z, v = get_arith_ZZM(ord);
    1664      135492 :   ord = mkvec2(gel(v,1),ZM_famat_limit(gel(v,2),int2n(28)));
    1665      135492 :   z = gen_PH_log(a,g,ord,(void*)T,&F2xq_star);
    1666      135492 :   return z? z: cgetg(1,t_VEC);
    1667             : }
    1668             : 
    1669             : GEN
    1670      212975 : F2xq_Artin_Schreier(GEN a, GEN T)
    1671             : {
    1672      212975 :   pari_sp ltop=avma;
    1673      212975 :   long j,N = get_F2x_degree(T), vT = get_F2x_var(T);
    1674      212975 :   GEN Q = F2x_matFrobenius(T);
    1675     1478624 :   for (j=1; j<=N; j++)
    1676     1265649 :     F2m_flip(Q,j,j);
    1677      212975 :   F2v_add_inplace(gel(Q,1),a);
    1678      212975 :   Q = F2m_ker_sp(Q,0);
    1679      212975 :   if (lg(Q)!=2) return NULL;
    1680      212975 :   Q = gel(Q,1);
    1681      212975 :   Q[1] = vT;
    1682      212975 :   return gerepileuptoleaf(ltop, F2x_renormalize(Q, lg(Q)));
    1683             : }
    1684             : 
    1685             : GEN
    1686       62660 : F2xq_sqrt_fast(GEN c, GEN sqx, GEN T)
    1687             : {
    1688             :   GEN c0, c1;
    1689       62660 :   F2x_even_odd(c, &c0, &c1);
    1690       62661 :   return F2x_add(c0, F2xq_mul(c1, sqx, T));
    1691             : }
    1692             : 
    1693             : static int
    1694       18399 : F2x_is_x(GEN a) { return lg(a)==3 && a[2]==2; }
    1695             : 
    1696             : GEN
    1697       33407 : F2xq_sqrt(GEN a, GEN T)
    1698             : {
    1699       33407 :   pari_sp av = avma;
    1700       33407 :   long n = get_F2x_degree(T), vT = get_F2x_var(T);
    1701             :   GEN sqx;
    1702       33407 :   if (n==1) return F2x_copy(a);
    1703       33330 :   if (n==2) return F2xq_sqr(a,T);
    1704       18399 :   sqx = F2xq_autpow(mkF2(4, vT), n-1, T);
    1705       18399 :   return gerepileuptoleaf(av, F2x_is_x(a)? sqx: F2xq_sqrt_fast(a,sqx,T));
    1706             : }
    1707             : 
    1708             : GEN
    1709        9317 : F2xq_sqrtn(GEN a, GEN n, GEN T, GEN *zeta)
    1710             : {
    1711        9317 :   long dT = get_F2x_degree(T), vT = get_F2x_var(T);
    1712        9317 :   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        9310 :   return gen_Shanks_sqrtn(a, n, int2um1(dT), zeta, (void*)T, &F2xq_star);
    1720             : }
    1721             : 
    1722             : GEN
    1723         154 : gener_F2xq(GEN T, GEN *po)
    1724             : {
    1725         154 :   long i, j, vT = get_F2x_var(T), f = get_F2x_degree(T);
    1726         154 :   pari_sp av0 = avma, av;
    1727             :   GEN g, L2, o, q;
    1728             : 
    1729         154 :   if (f == 1) {
    1730          21 :     if (po) *po = mkvec2(gen_1, trivial_fact());
    1731          21 :     return pol1_F2x(vT);
    1732             :   }
    1733         133 :   q = int2um1(f);
    1734         133 :   o = factor_pn_1(gen_2,f);
    1735         133 :   L2 = leafcopy( gel(o, 1) );
    1736         385 :   for (i = j = 1; i < lg(L2); i++)
    1737             :   {
    1738         252 :     if (absequaliu(gel(L2,i),2)) continue;
    1739         252 :     gel(L2,j++) = diviiexact(q, gel(L2,i));
    1740             :   }
    1741         133 :   setlg(L2, j);
    1742         175 :   for (av = avma;; set_avma(av))
    1743             :   {
    1744         175 :     g = random_F2x(f, vT);
    1745         175 :     if (F2x_degree(g) < 1) continue;
    1746         406 :     for (i = 1; i < j; i++)
    1747             :     {
    1748         273 :       GEN a = F2xq_pow(g, gel(L2,i), T);
    1749         273 :       if (F2x_equal1(a)) break;
    1750             :     }
    1751         154 :     if (i == j) break;
    1752             :   }
    1753         133 :   if (!po) g = gerepilecopy(av0, g);
    1754             :   else {
    1755           0 :     *po = mkvec2(int2um1(f), o);
    1756           0 :     gerepileall(av0, 2, &g, po);
    1757             :   }
    1758         133 :   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       38738 : 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     1800804 : F2xV_to_F2m(GEN x, long n) { pari_APPLY_type(t_MAT, F2x_to_F2v(gel(x,i), n)) }
    1800             : 
    1801             : void
    1802       30294 : F2xV_to_FlxV_inplace(GEN v)
    1803             : {
    1804       30294 :   long i, l = lg(v);
    1805       69465 :   for(i = 1; i < l;i++) gel(v,i) = F2x_to_Flx(gel(v,i));
    1806       30294 : }
    1807             : void
    1808     1377422 : F2xV_to_ZXV_inplace(GEN v)
    1809             : {
    1810     1377422 :   long i, l = lg(v);
    1811     2597433 :   for(i = 1; i < l; i++) gel(v,i)= F2x_to_ZX(gel(v,i));
    1812     1377453 : }
    1813             : 
    1814             : /***********************************************************************/
    1815             : /**                                                                   **/
    1816             : /**                             F2xX                                  **/
    1817             : /**                                                                   **/
    1818             : /***********************************************************************/
    1819             : 
    1820             : GEN
    1821     2711155 : F2xX_renormalize(GEN /*in place*/ x, long lx)
    1822     2711155 : { return FlxX_renormalize(x, lx); }
    1823             : 
    1824             : GEN
    1825      447020 : pol1_F2xX(long v, long sv) { return pol1_FlxX(v, sv); }
    1826             : 
    1827             : GEN
    1828         483 : polx_F2xX(long v, long sv) { return polx_FlxX(v, sv); }
    1829             : 
    1830             : long
    1831      206976 : F2xY_degreex(GEN b)
    1832             : {
    1833      206976 :   long deg = 0, i;
    1834      206976 :   if (!signe(b)) return -1;
    1835     1343468 :   for (i = 2; i < lg(b); ++i)
    1836     1136492 :     deg = maxss(deg, F2x_degree(gel(b, i)));
    1837      206976 :   return deg;
    1838             : }
    1839             : 
    1840             : GEN
    1841         987 : FlxX_to_F2xX(GEN B)
    1842             : {
    1843         987 :   long lb=lg(B);
    1844             :   long i;
    1845         987 :   GEN b=cgetg(lb,t_POL);
    1846         987 :   b[1]=evalsigne(1)|(((ulong)B[1])&VARNBITS);
    1847        4844 :   for (i=2; i<lb; i++)
    1848        3857 :     gel(b,i) = Flx_to_F2x(gel(B,i));
    1849         987 :   return F2xX_renormalize(b, lb);
    1850             : }
    1851             : 
    1852             : GEN
    1853        4844 : ZXX_to_F2xX(GEN B, long v)
    1854             : {
    1855        4844 :   long lb=lg(B);
    1856             :   long i;
    1857        4844 :   GEN b=cgetg(lb,t_POL);
    1858        4844 :   b[1]=evalsigne(1)|(((ulong)B[1])&VARNBITS);
    1859       23170 :   for (i=2; i<lb; i++)
    1860       18326 :     switch (typ(gel(B,i)))
    1861             :     {
    1862        8190 :     case t_INT:
    1863        8190 :       gel(b,i) = Z_to_F2x(gel(B,i), evalvarn(v));
    1864        8190 :       break;
    1865       10136 :     case t_POL:
    1866       10136 :       gel(b,i) = ZX_to_F2x(gel(B,i));
    1867       10136 :       break;
    1868             :     }
    1869       23170 :   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        1463 : F2xX_to_ZXX(GEN B)
    1884             : {
    1885        1463 :   long i, lb = lg(B);
    1886        1463 :   GEN b = cgetg(lb,t_POL);
    1887        4949 :   for (i=2; i<lb; i++)
    1888             :   {
    1889        3486 :     GEN c = gel(B,i);
    1890        3486 :     gel(b,i) = lgpol(c) ?  F2x_equal1(c) ? gen_1 : F2x_to_ZX(c) : gen_0;
    1891             :   }
    1892        1463 :   b[1] = B[1]; return b;
    1893             : }
    1894             : 
    1895             : GEN
    1896       80738 : F2xX_deriv(GEN z)
    1897             : {
    1898       80738 :   long i,l = lg(z)-1;
    1899             :   GEN x;
    1900       80738 :   if (l < 2) l = 2;
    1901       80738 :   x = cgetg(l, t_POL); x[1] = z[1];
    1902      528724 :   for (i=2; i<l; i++) gel(x,i) = odd(i) ? pol0_F2x(mael(z,i+1,1)): gel(z,i+1);
    1903       80738 :   return F2xX_renormalize(x,l);
    1904             : }
    1905             : 
    1906             : static GEN
    1907        1359 : F2xX_addspec(GEN x, GEN y, long lx, long ly)
    1908             : {
    1909             :   long i,lz;
    1910             :   GEN z;
    1911        1359 :   if (ly>lx) swapspec(x,y, lx,ly);
    1912        1359 :   lz = lx+2; z = cgetg(lz, t_POL);
    1913      144699 :   for (i=0; i<ly; i++) gel(z,i+2) = F2x_add(gel(x,i), gel(y,i));
    1914        1359 :   for (   ; i<lx; i++) gel(z,i+2) = F2x_copy(gel(x,i));
    1915        1359 :   z[1] = 0; return F2xX_renormalize(z, lz);
    1916             : }
    1917             : 
    1918             : GEN
    1919      422380 : F2xX_add(GEN x, GEN y)
    1920             : {
    1921             :   long i,lz;
    1922             :   GEN z;
    1923      422380 :   long lx=lg(x);
    1924      422380 :   long ly=lg(y);
    1925      422380 :   if (ly>lx) swapspec(x,y, lx,ly);
    1926      422380 :   lz = lx; z = cgetg(lz, t_POL); z[1]=x[1];
    1927     1484847 :   for (i=2; i<ly; i++) gel(z,i) = F2x_add(gel(x,i), gel(y,i));
    1928     1677305 :   for (   ; i<lx; i++) gel(z,i) = F2x_copy(gel(x,i));
    1929      422380 :   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      480690 : F2xX_F2x_mul(GEN P, GEN U)
    1948             : {
    1949      480690 :   long i, lP = lg(P);
    1950      480690 :   GEN res = cgetg(lP,t_POL);
    1951      480690 :   res[1] = P[1];
    1952     2326422 :   for(i=2; i<lP; i++)
    1953     1845732 :     gel(res,i) = F2x_mul(U,gel(P,i));
    1954      480690 :   return F2xX_renormalize(res, lP);
    1955             : }
    1956             : 
    1957             : GEN
    1958      136381 : F2xY_F2xqV_evalx(GEN P, GEN x, GEN T)
    1959             : {
    1960      136381 :   long i, lP = lg(P);
    1961      136381 :   GEN res = cgetg(lP,t_POL);
    1962      136381 :   res[1] = P[1];
    1963      616833 :   for(i=2; i<lP; i++)
    1964      480452 :     gel(res,i) = F2x_F2xqV_eval(gel(P,i), x, T);
    1965      136381 :   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        6678 : F2xX_to_Kronecker_spec(GEN P, long n, long d)
    1979             : {
    1980        6678 :   long i, k, l, N = 2*d + 1;
    1981        6678 :   long dP = n+1;
    1982             :   GEN x;
    1983        6678 :   if (n == 0) return pol0_Flx(P[1]&VARNBITS);
    1984        6678 :   l = nbits2nlong(N*dP+d+1);
    1985        6678 :   x = zero_zv(l+1);
    1986      382369 :   for (k=i=0; i<n; i++, k+=N)
    1987             :   {
    1988      375691 :     GEN c = gel(P,i);
    1989      375691 :     F2x_addshiftip(x, c, k);
    1990             :   }
    1991        6678 :   x[1] = P[1]&VARNBITS; return F2x_renormalize(x, l+2);
    1992             : }
    1993             : 
    1994             : GEN
    1995      308188 : F2xX_to_Kronecker(GEN P, long d)
    1996             : {
    1997      308188 :   long i, k, l, N = 2*d + 1;
    1998      308188 :   long dP = degpol(P);
    1999             :   GEN x;
    2000      308188 :   if (dP < 0) return pol0_Flx(P[1]&VARNBITS);
    2001      306880 :   l = nbits2nlong(N*dP+d+1);
    2002      306880 :   x = zero_zv(l+1);
    2003     1689073 :   for (k=i=0; i<=dP; i++, k+=N)
    2004             :   {
    2005     1382193 :     GEN c = gel(P,i+2);
    2006     1382193 :     F2x_addshiftip(x, c, k);
    2007             :   }
    2008      306880 :   x[1] = P[1]&VARNBITS; return F2x_renormalize(x, l+2);
    2009             : }
    2010             : 
    2011             : static GEN
    2012     1597814 : F2x_slice(GEN x, long n, long d)
    2013             : {
    2014     1597814 :   ulong ib, il=dvmduBIL(n, &ib);
    2015     1597814 :   ulong db, dl=dvmduBIL(d, &db);
    2016     1597814 :   long lN = dl+2+(db?1:0);
    2017     1597814 :   GEN t = cgetg(lN,t_VECSMALL);
    2018     1597814 :   t[1] = x[1];
    2019     1597814 :   if (ib)
    2020             :   {
    2021     1433025 :     ulong i, ic = BITS_IN_LONG-ib;
    2022     1433025 :     ulong r = uel(x,2+il)>>ib;
    2023     1433233 :     for(i=0; i<dl; i++)
    2024             :     {
    2025         208 :       uel(t,2+i) = (uel(x,3+il+i)<<ic)|r;
    2026         208 :       r = uel(x,3+il+i)>>ib;
    2027             :     }
    2028     1433025 :     if (db)
    2029     1433025 :       uel(t,2+i) = (uel(x,3+il+i)<<ic)|r;
    2030             :   }
    2031             :   else
    2032             :   {
    2033             :     long i;
    2034      329606 :     for(i=2; i<lN; i++)
    2035      164817 :       uel(t,i) = uel(x,il+i);
    2036             :   }
    2037     1597814 :   if (db) uel(t,lN-1) &= (1UL<<db)-1;
    2038     1597814 :   return F2x_renormalize(t, lN);
    2039             : }
    2040             : 
    2041             : GEN
    2042      157433 : Kronecker_to_F2xqX(GEN z, GEN T)
    2043             : {
    2044      157433 :   long lz = F2x_degree(z)+1;
    2045      157433 :   long i, j, N = get_F2x_degree(T)*2 + 1;
    2046      157433 :   long lx = lz / (N-2);
    2047      157433 :   GEN x = cgetg(lx+3,t_POL);
    2048      157433 :   x[1] = z[1];
    2049     1755247 :   for (i=0, j=2; i<lz; i+=N, j++)
    2050             :   {
    2051     1597814 :     GEN t = F2x_slice(z,i,minss(lz-i,N));
    2052     1597814 :     t[1] = T[1];
    2053     1597814 :     gel(x,j) = F2x_rem(t, T);
    2054             :   }
    2055      157433 :   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        1414 : FlxXC_to_F2xXC(GEN x) { pari_APPLY_type(t_COL, FlxX_to_F2xX(gel(x,i))); }
    2088             : GEN
    2089        2590 : 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      784329 : get_F2xqX_red(GEN T, GEN *B)
    2099             : {
    2100      784329 :   if (typ(T)!=t_VEC) { *B=NULL; return T; }
    2101        3037 :   *B = gel(T,1); return gel(T,2);
    2102             : }
    2103             : 
    2104             : GEN
    2105        2737 : random_F2xqX(long d1, long v, GEN T)
    2106             : {
    2107        2737 :   long dT = get_F2x_degree(T), vT = get_F2x_var(T);
    2108        2737 :   long i, d = d1+2;
    2109        2737 :   GEN y = cgetg(d,t_POL); y[1] = evalsigne(1) | evalvarn(v);
    2110       18620 :   for (i=2; i<d; i++) gel(y,i) = random_F2x(dT, vT);
    2111        2737 :   return FlxX_renormalize(y,d);
    2112             : }
    2113             : 
    2114             : GEN
    2115     1006261 : F2xqX_red(GEN z, GEN T)
    2116             : {
    2117             :   GEN res;
    2118     1006261 :   long i, l = lg(z);
    2119     1006261 :   res = cgetg(l,t_POL); res[1] = z[1];
    2120     5679773 :   for(i=2;i<l;i++) gel(res,i) = F2x_rem(gel(z,i),T);
    2121     1006261 :   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      206493 : F2xqX_F2xq_mul_to_monic(GEN P, GEN U, GEN T)
    2137             : {
    2138      206493 :   long i, lP = lg(P);
    2139      206493 :   GEN res = cgetg(lP,t_POL);
    2140      206493 :   res[1] = P[1];
    2141     1131914 :   for(i=2; i<lP-1; i++) gel(res,i) = F2xq_mul(U,gel(P,i), T);
    2142      206493 :   gel(res,lP-1) = pol1_F2x(T[1]);
    2143      206493 :   return F2xX_renormalize(res, lP);
    2144             : }
    2145             : 
    2146             : GEN
    2147      206507 : F2xqX_normalize(GEN z, GEN T)
    2148             : {
    2149      206507 :   GEN p1 = leading_coeff(z);
    2150      206507 :   if (!lgpol(z) || (!degpol(p1) && p1[1] == 1)) return z;
    2151      206493 :   return F2xqX_F2xq_mul_to_monic(z, F2xq_inv(p1,T), T);
    2152             : }
    2153             : 
    2154             : GEN
    2155      154094 : F2xqX_mul(GEN x, GEN y, GEN T)
    2156             : {
    2157      154094 :   pari_sp ltop=avma;
    2158             :   GEN z, kx, ky;
    2159      154094 :   long d = get_F2x_degree(T);
    2160      154094 :   kx= F2xX_to_Kronecker(x, d);
    2161      154094 :   ky= F2xX_to_Kronecker(y, d);
    2162      154094 :   z = F2x_mul(ky, kx);
    2163      154094 :   z = Kronecker_to_F2xqX(z, T);
    2164      154094 :   return gerepileupto(ltop, z);
    2165             : }
    2166             : 
    2167             : static GEN
    2168        3339 : F2xqX_mulspec(GEN x, GEN y, GEN T, long nx, long ny)
    2169             : {
    2170        3339 :   pari_sp ltop=avma;
    2171             :   GEN z, kx, ky;
    2172        3339 :   long dT = get_F2x_degree(T);
    2173        3339 :   kx= F2xX_to_Kronecker_spec(x, nx, dT);
    2174        3339 :   ky= F2xX_to_Kronecker_spec(y, ny, dT);
    2175        3339 :   z = F2x_mul(ky, kx);
    2176        3339 :   z = Kronecker_to_F2xqX(z,T);
    2177        3339 :   return gerepileupto(ltop,z);
    2178             : }
    2179             : 
    2180             : GEN
    2181      105091 : F2xqX_sqr(GEN x, GEN T)
    2182             : {
    2183      105091 :   long d = degpol(x), l = 2*d+3;
    2184             :   GEN z;
    2185      105091 :   if (!signe(x)) return pol_0(varn(x));
    2186      105084 :   z = cgetg(l,t_POL);
    2187      105084 :   z[1] = x[1];
    2188      105084 :   if (d > 0)
    2189             :   {
    2190      105007 :     GEN u = pol0_F2x(T[1]);
    2191             :     long i,j;
    2192      269500 :     for (i=2,j=2; i<d+2; i++,j+=2)
    2193             :     {
    2194      164493 :       gel(z, j) = F2xq_sqr(gel(x, i), T);
    2195      164493 :       gel(z, j+1) = u;
    2196             :     }
    2197             :   }
    2198      105084 :   gel(z, 2+2*d) = F2xq_sqr(gel(x, 2+d), T);
    2199      105084 :   return FlxX_renormalize(z, l);
    2200             : }
    2201             : 
    2202             : static GEN
    2203      545765 : F2xqX_divrem_basecase(GEN x, GEN y, GEN T, GEN *pr)
    2204             : {
    2205             :   long vx, dx, dy, dz, i, j, sx, lr;
    2206             :   pari_sp av0, av, tetpil;
    2207             :   GEN z,p1,rem,lead;
    2208             : 
    2209      545765 :   if (!signe(y)) pari_err_INV("F2xqX_divrem",y);
    2210      545765 :   vx=varn(x); dy=degpol(y); dx=degpol(x);
    2211      545765 :   if (dx < dy)
    2212             :   {
    2213           0 :     if (pr)
    2214             :     {
    2215           0 :       av0 = avma; x = F2xqX_red(x, T);
    2216           0 :       if (pr == ONLY_DIVIDES) { set_avma(av0); return signe(x)? NULL: pol_0(vx); }
    2217           0 :       if (pr == ONLY_REM) return x;
    2218           0 :       *pr = x;
    2219             :     }
    2220           0 :     return pol_0(vx);
    2221             :   }
    2222      545765 :   lead = leading_coeff(y);
    2223      545765 :   if (!dy) /* y is constant */
    2224             :   {
    2225      115682 :     if (pr && pr != ONLY_DIVIDES)
    2226             :     {
    2227      105602 :       if (pr == ONLY_REM) return pol_0(vx);
    2228          14 :       *pr = pol_0(vx);
    2229             :     }
    2230       10094 :     if (F2x_equal1(lead)) return gcopy(x);
    2231        7014 :     av0 = avma; x = F2xqX_F2xq_mul(x,F2xq_inv(lead,T),T);
    2232        7014 :     return gerepileupto(av0,x);
    2233             :   }
    2234      430083 :   av0 = avma; dz = dx-dy;
    2235      430083 :   lead = F2x_equal1(lead)? NULL: gclone(F2xq_inv(lead,T));
    2236      430083 :   set_avma(av0);
    2237      430083 :   z = cgetg(dz+3,t_POL); z[1] = x[1];
    2238      430083 :   x += 2; y += 2; z += 2;
    2239             : 
    2240      430083 :   p1 = gel(x,dx); av = avma;
    2241      430083 :   gel(z,dz) = lead? gerepileupto(av, F2xq_mul(p1,lead, T)): leafcopy(p1);
    2242     1276962 :   for (i=dx-1; i>=dy; i--)
    2243             :   {
    2244      846879 :     av=avma; p1=gel(x,i);
    2245     2599077 :     for (j=i-dy+1; j<=i && j<=dz; j++)
    2246     1752198 :       p1 = F2x_add(p1, F2x_mul(gel(z,j),gel(y,i-j)));
    2247      846879 :     if (lead) p1 = F2x_mul(p1, lead);
    2248      846879 :     tetpil=avma; gel(z,i-dy) = gerepile(av,tetpil,F2x_rem(p1,T));
    2249             :   }
    2250      430083 :   if (!pr) { guncloneNULL(lead); return z-2; }
    2251             : 
    2252      406790 :   rem = (GEN)avma; av = (pari_sp)new_chunk(dx+3);
    2253      406790 :   for (sx=0; ; i--)
    2254             :   {
    2255      222812 :     p1 = gel(x,i);
    2256     1873994 :     for (j=0; j<=i && j<=dz; j++)
    2257     1244392 :       p1 = F2x_add(p1, F2x_mul(gel(z,j),gel(y,i-j)));
    2258      629602 :     tetpil=avma; p1 = F2x_rem(p1, T); if (lgpol(p1)) { sx = 1; break; }
    2259      286015 :     if (!i) break;
    2260      222812 :     set_avma(av);
    2261             :   }
    2262      406790 :   if (pr == ONLY_DIVIDES)
    2263             :   {
    2264           0 :     guncloneNULL(lead);
    2265           0 :     if (sx) return gc_NULL(av0);
    2266           0 :     return gc_const((pari_sp)rem, z-2);
    2267             :   }
    2268      406790 :   lr=i+3; rem -= lr;
    2269      406790 :   rem[0] = evaltyp(t_POL) | evallg(lr);
    2270      406790 :   rem[1] = z[-1];
    2271      406790 :   p1 = gerepile((pari_sp)rem,tetpil,p1);
    2272      406790 :   rem += 2; gel(rem,i) = p1;
    2273     1384618 :   for (i--; i>=0; i--)
    2274             :   {
    2275      977828 :     av=avma; p1 = gel(x,i);
    2276     3368075 :     for (j=0; j<=i && j<=dz; j++)
    2277     2390247 :       p1 = F2x_add(p1, F2x_mul(gel(z,j),gel(y,i-j)));
    2278      977828 :     tetpil=avma; gel(rem,i) = gerepile(av,tetpil, F2x_rem(p1, T));
    2279             :   }
    2280      406790 :   rem -= 2;
    2281      406790 :   guncloneNULL(lead);
    2282      406790 :   if (!sx) (void)F2xX_renormalize(rem, lr);
    2283      406790 :   if (pr == ONLY_REM) return gerepileupto(av0,rem);
    2284          35 :   *pr = rem; return z-2;
    2285             : }
    2286             : 
    2287             : static GEN
    2288        2768 : F2xX_recipspec(GEN x, long l, long n, long vs)
    2289             : {
    2290             :   long i;
    2291        2768 :   GEN z = cgetg(n+2,t_POL);
    2292        2768 :   z[1] = 0; z += 2;
    2293      146043 :   for(i=0; i<l; i++)
    2294      143275 :     gel(z,n-i-1) = F2x_copy(gel(x,i));
    2295        2768 :   for(   ; i<n; i++)
    2296           0 :     gel(z,n-i-1) = pol0_F2x(vs);
    2297        2768 :   return F2xX_renormalize(z-2,n+2);
    2298             : }
    2299             : 
    2300             : static GEN
    2301           6 : F2xqX_invBarrett_basecase(GEN T, GEN Q)
    2302             : {
    2303           6 :   long i, l=lg(T)-1, lr = l-1, k;
    2304           6 :   long sv=Q[1];
    2305           6 :   GEN r=cgetg(lr,t_POL); r[1]=T[1];
    2306           6 :   gel(r,2) = pol1_F2x(sv);
    2307         273 :   for (i=3;i<lr;i++)
    2308             :   {
    2309         267 :     pari_sp ltop=avma;
    2310         267 :     GEN u = gel(T,l-i+2);
    2311        6075 :     for (k=3;k<i;k++)
    2312        5808 :       u = F2x_add(u, F2xq_mul(gel(T,l-i+k),gel(r,k),Q));
    2313         267 :     gel(r,i) = gerepileupto(ltop, u);
    2314             :   }
    2315           6 :   r = F2xX_renormalize(r,lr);
    2316           6 :   return r;
    2317             : }
    2318             : 
    2319             : /* Return new lgpol */
    2320             : static long
    2321        3651 : F2xX_lgrenormalizespec(GEN x, long lx)
    2322             : {
    2323             :   long i;
    2324        3651 :   for (i = lx-1; i>=0; i--)
    2325        3651 :     if (lgpol(gel(x,i))) break;
    2326        3651 :   return i+1;
    2327             : }
    2328             : 
    2329             : static GEN
    2330          44 : F2xqX_invBarrett_Newton(GEN S, GEN T)
    2331             : {
    2332          44 :   pari_sp av = avma;
    2333          44 :   long nold, lx, lz, lq, l = degpol(S), i, lQ;
    2334          44 :   GEN q, y, z, x = cgetg(l+2, t_POL) + 2;
    2335          44 :   long dT = get_F2x_degree(T);
    2336          44 :   ulong mask = quadratic_prec_mask(l-2); /* assume l > 2 */
    2337        5251 :   for (i=0;i<l;i++) gel(x,i) = pol0_F2x(T[1]);
    2338          44 :   q = F2xX_recipspec(S+2,l+1,l+1,dT);
    2339          44 :   lQ = lgpol(q); q+=2;
    2340             :   /* We work on _spec_ FlxX's, all the l[xzq] below are lgpol's */
    2341             : 
    2342             :   /* initialize */
    2343          44 :   gel(x,0) = F2xq_inv(gel(q,0),T);
    2344          44 :   if (lQ>1 && F2x_degree(gel(q,1)) >= dT)
    2345           0 :     gel(q,1) = F2x_rem(gel(q,1), T);
    2346          44 :   if (lQ>1 && lgpol(gel(q,1)))
    2347          44 :   {
    2348          44 :     GEN u = gel(q, 1);
    2349          44 :     if (!F2x_equal1(gel(x,0))) u = F2xq_mul(u, F2xq_sqr(gel(x,0), T), T);
    2350          44 :     else u = F2x_copy(u);
    2351          44 :     gel(x,1) = u; lx = 2;
    2352             :   }
    2353             :   else
    2354           0 :     lx = 1;
    2355          44 :   nold = 1;
    2356         353 :   for (; mask > 1; )
    2357             :   { /* set x -= x(x*q - 1) + O(t^(nnew + 1)), knowing x*q = 1 + O(t^(nold+1)) */
    2358         309 :     long i, lnew, nnew = nold << 1;
    2359             : 
    2360         309 :     if (mask & 1) nnew--;
    2361         309 :     mask >>= 1;
    2362             : 
    2363         309 :     lnew = nnew + 1;
    2364         309 :     lq = F2xX_lgrenormalizespec(q, minss(lQ,lnew));
    2365         309 :     z = F2xqX_mulspec(x, q, T, lx, lq); /* FIXME: high product */
    2366         309 :     lz = lgpol(z); if (lz > lnew) lz = lnew;
    2367         309 :     z += 2;
    2368             :     /* subtract 1 [=>first nold words are 0]: renormalize so that z(0) != 0 */
    2369         618 :     for (i = nold; i < lz; i++) if (lgpol(gel(z,i))) break;
    2370         309 :     nold = nnew;
    2371         309 :     if (i >= lz) continue; /* z-1 = 0(t^(nnew + 1)) */
    2372             : 
    2373             :     /* z + i represents (x*q - 1) / t^i */
    2374         309 :     lz = F2xX_lgrenormalizespec (z+i, lz-i);
    2375         309 :     z = F2xqX_mulspec(x, z+i, T, lx, lz); /* FIXME: low product */
    2376         309 :     lz = lgpol(z); z += 2;
    2377         309 :     if (lz > lnew-i) lz = F2xX_lgrenormalizespec(z, lnew-i);
    2378             : 
    2379         309 :     lx = lz+ i;
    2380         309 :     y  = x + i; /* x -= z * t^i, in place */
    2381        5384 :     for (i = 0; i < lz; i++) gel(y,i) = gel(z,i);
    2382             :   }
    2383          44 :   x -= 2; setlg(x, lx + 2); x[1] = S[1];
    2384          44 :   return gerepilecopy(av, x);
    2385             : }
    2386             : 
    2387             : GEN
    2388          50 : F2xqX_invBarrett(GEN T, GEN Q)
    2389             : {
    2390          50 :   pari_sp ltop=avma;
    2391          50 :   long l=lg(T), v = varn(T);
    2392             :   GEN r;
    2393          50 :   GEN c = gel(T,l-1);
    2394          50 :   if (l<5) return pol_0(v);
    2395          50 :   if (l<=F2xqX_INVBARRETT_LIMIT)
    2396             :   {
    2397           6 :     if (!F2x_equal1(c))
    2398             :     {
    2399           0 :       GEN ci = F2xq_inv(c,Q);
    2400           0 :       T = F2xqX_F2xq_mul(T, ci, Q);
    2401           0 :       r = F2xqX_invBarrett_basecase(T,Q);
    2402           0 :       r = F2xqX_F2xq_mul(r,ci,Q);
    2403             :     } else
    2404           6 :       r = F2xqX_invBarrett_basecase(T,Q);
    2405             :   } else
    2406          44 :     r = F2xqX_invBarrett_Newton(T,Q);
    2407          50 :   return gerepileupto(ltop, r);
    2408             : }
    2409             : 
    2410             : GEN
    2411      219912 : F2xqX_get_red(GEN S, GEN T)
    2412             : {
    2413      219912 :   if (typ(S)==t_POL && lg(S)>F2xqX_BARRETT_LIMIT)
    2414          47 :     retmkvec2(F2xqX_invBarrett(S, T), S);
    2415      219865 :   return S;
    2416             : }
    2417             : 
    2418             : /* Compute x mod S where 2 <= degpol(S) <= l+1 <= 2*(degpol(S)-1)
    2419             :  *  * and mg is the Barrett inverse of S. */
    2420             : static GEN
    2421        1362 : F2xqX_divrem_Barrettspec(GEN x, long l, GEN mg, GEN S, GEN T, GEN *pr)
    2422             : {
    2423             :   GEN q, r;
    2424        1362 :   long lt = degpol(S); /*We discard the leading term*/
    2425             :   long ld, lm, lT, lmg;
    2426        1362 :   ld = l-lt;
    2427        1362 :   lm = minss(ld, lgpol(mg));
    2428        1362 :   lT  = F2xX_lgrenormalizespec(S+2,lt);
    2429        1362 :   lmg = F2xX_lgrenormalizespec(mg+2,lm);
    2430        1362 :   q = F2xX_recipspec(x+lt,ld,ld,0);               /* q = rec(x)     lq<=ld*/
    2431        1362 :   q = F2xqX_mulspec(q+2,mg+2,T,lgpol(q),lmg);   /* q = rec(x) * mg lq<=ld+lm*/
    2432        1362 :   q = F2xX_recipspec(q+2,minss(ld,lgpol(q)),ld,0);/* q = rec (rec(x) * mg) lq<=ld*/
    2433        1362 :   if (!pr) return q;
    2434        1359 :   r = F2xqX_mulspec(q+2,S+2,T,lgpol(q),lT);     /* r = q*pol        lr<=ld+lt*/
    2435        1359 :   r = F2xX_addspec(x,r+2,lt,minss(lt,lgpol(r)));/* r = x - r   lr<=lt */
    2436        1359 :   if (pr == ONLY_REM) return r;
    2437           0 :   *pr = r; return q;
    2438             : }
    2439             : 
    2440             : static GEN
    2441        1362 : F2xqX_divrem_Barrett(GEN x, GEN mg, GEN S, GEN T, GEN *pr)
    2442             : {
    2443        1362 :   GEN q = NULL, r = F2xqX_red(x, T);
    2444        1362 :   long l = lgpol(r), lt = degpol(S), lm = 2*lt-1, v = varn(S);
    2445             :   long i;
    2446        1362 :   if (l <= lt)
    2447             :   {
    2448           0 :     if (pr == ONLY_REM) return r;
    2449           0 :     if (pr == ONLY_DIVIDES) return signe(r)? NULL: pol_0(v);
    2450           0 :     if (pr) *pr = r;
    2451           0 :     return pol_0(v);
    2452             :   }
    2453        1362 :   if (lt <= 1)
    2454           0 :     return F2xqX_divrem_basecase(x,S,T,pr);
    2455        1362 :   if (pr != ONLY_REM && l>lm)
    2456             :   {
    2457           0 :     long vT = get_F2x_var(T);
    2458           0 :     q = cgetg(l-lt+2, t_POL); q[1] = S[1];
    2459           0 :     for (i=0;i<l-lt;i++) gel(q+2,i) = pol0_F2x(vT);
    2460             :   }
    2461        1362 :   while (l>lm)
    2462             :   {
    2463           0 :     GEN zr, zq = F2xqX_divrem_Barrettspec(r+2+l-lm,lm,mg,S,T,&zr);
    2464           0 :     long lz = lgpol(zr);
    2465           0 :     if (pr != ONLY_REM)
    2466             :     {
    2467           0 :       long lq = lgpol(zq);
    2468           0 :       for(i=0; i<lq; i++) gel(q+2+l-lm,i) = gel(zq,2+i);
    2469             :     }
    2470           0 :     for(i=0; i<lz; i++) gel(r+2+l-lm,i) = gel(zr,2+i);
    2471           0 :     l = l-lm+lz;
    2472             :   }
    2473        1362 :   if (pr == ONLY_REM)
    2474             :   {
    2475        1359 :     if (l > lt)
    2476        1359 :       r = F2xqX_divrem_Barrettspec(r+2,l,mg,S,T,ONLY_REM);
    2477             :     else
    2478           0 :       r = F2xX_renormalize(r, lg(r));
    2479        1359 :     setvarn(r, v); return F2xX_renormalize(r, lg(r));
    2480             :   }
    2481           3 :   if (l > lt)
    2482             :   {
    2483           3 :     GEN zq = F2xqX_divrem_Barrettspec(r+2,l,mg,S,T,pr? &r: NULL);
    2484           3 :     if (!q) q = zq;
    2485             :     else
    2486             :     {
    2487           0 :       long lq = lgpol(zq);
    2488           0 :       for(i=0; i<lq; i++) gel(q+2,i) = gel(zq,2+i);
    2489             :     }
    2490             :   }
    2491           0 :   else if (pr)
    2492           0 :     r = F2xX_renormalize(r, l+2);
    2493           3 :   setvarn(q, v); q = F2xX_renormalize(q, lg(q));
    2494           3 :   if (pr == ONLY_DIVIDES) return signe(r)? NULL: q;
    2495           3 :   if (pr) { setvarn(r, v); *pr = r; }
    2496           3 :   return q;
    2497             : }
    2498             : 
    2499             : GEN
    2500       33425 : F2xqX_divrem(GEN x, GEN S, GEN T, GEN *pr)
    2501             : {
    2502             :   GEN B, y;
    2503             :   long dy, dx, d;
    2504       33425 :   if (pr==ONLY_REM) return F2xqX_rem(x, S, T);
    2505       33425 :   y = get_F2xqX_red(S, &B);
    2506       33425 :   dy = degpol(y); dx = degpol(x); d = dx-dy;
    2507       33425 :   if (!B && d+3 < F2xqX_DIVREM_BARRETT_LIMIT)
    2508       33422 :     return F2xqX_divrem_basecase(x,y,T,pr);
    2509             :   else
    2510             :   {
    2511           3 :     pari_sp av=avma;
    2512           3 :     GEN mg = B? B: F2xqX_invBarrett(y, T);
    2513           3 :     GEN q = F2xqX_divrem_Barrett(x,mg,y,T,pr);
    2514           3 :     if (!q) return gc_NULL(av);
    2515           3 :     if (!pr || pr==ONLY_DIVIDES) return gerepilecopy(av, q);
    2516           0 :     return gc_all(av,2,&q,pr);
    2517             :   }
    2518             : }
    2519             : 
    2520             : GEN
    2521      750904 : F2xqX_rem(GEN x, GEN S, GEN T)
    2522             : {
    2523      750904 :   GEN B, y = get_F2xqX_red(S, &B);
    2524      750904 :   long dy = degpol(y), dx = degpol(x), d = dx-dy;
    2525      750904 :   if (d < 0) return F2xqX_red(x, T);
    2526      513702 :   if (!B && d+3 < F2xqX_REM_BARRETT_LIMIT)
    2527      512343 :     return F2xqX_divrem_basecase(x,y, T, ONLY_REM);
    2528             :   else
    2529             :   {
    2530        1359 :     pari_sp av=avma;
    2531        1359 :     GEN mg = B? B: F2xqX_invBarrett(y, T);
    2532        1359 :     GEN r = F2xqX_divrem_Barrett(x, mg, y, T, ONLY_REM);
    2533        1359 :     return gerepileupto(av, r);
    2534             :   }
    2535             : }
    2536             : 
    2537             : static GEN
    2538           0 : F2xqX_halfgcd_basecase(GEN a, GEN b, GEN T)
    2539             : {
    2540           0 :   pari_sp av=avma;
    2541             :   GEN u,u1,v,v1;
    2542           0 :   long vx = varn(a);
    2543           0 :   long n = lgpol(a)>>1;
    2544           0 :   u1 = v = pol_0(vx);
    2545           0 :   u = v1 = pol1_F2xX(vx, get_F2x_var(T));
    2546           0 :   while (lgpol(b)>n)
    2547             :   {
    2548           0 :     GEN r, q = F2xqX_divrem(a,b, T, &r);
    2549           0 :     a = b; b = r; swap(u,u1); swap(v,v1);
    2550           0 :     u1 = F2xX_add(u1, F2xqX_mul(u, q, T));
    2551           0 :     v1 = F2xX_add(v1, F2xqX_mul(v, q ,T));
    2552           0 :     if (gc_needed(av,2))
    2553             :     {
    2554           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2xqX_halfgcd (d = %ld)",degpol(b));
    2555           0 :       gerepileall(av,6, &a,&b,&u1,&v1,&u,&v);
    2556             :     }
    2557             :   }
    2558           0 :   return gerepilecopy(av, mkmat2(mkcol2(u,u1), mkcol2(v,v1)));
    2559             : }
    2560             : static GEN
    2561           0 : F2xqX_addmulmul(GEN u, GEN v, GEN x, GEN y, GEN T)
    2562             : {
    2563           0 :   return F2xX_add(F2xqX_mul(u, x, T),F2xqX_mul(v, y, T));
    2564             : }
    2565             : 
    2566             : static GEN
    2567           0 : F2xqXM_F2xqX_mul2(GEN M, GEN x, GEN y, GEN T)
    2568             : {
    2569           0 :   GEN res = cgetg(3, t_COL);
    2570           0 :   gel(res, 1) = F2xqX_addmulmul(gcoeff(M,1,1), gcoeff(M,1,2), x, y, T);
    2571           0 :   gel(res, 2) = F2xqX_addmulmul(gcoeff(M,2,1), gcoeff(M,2,2), x, y, T);
    2572           0 :   return res;
    2573             : }
    2574             : 
    2575             : static GEN
    2576           0 : F2xqXM_mul2(GEN A, GEN B, GEN T)
    2577             : {
    2578           0 :   GEN A11=gcoeff(A,1,1),A12=gcoeff(A,1,2), B11=gcoeff(B,1,1),B12=gcoeff(B,1,2);
    2579           0 :   GEN A21=gcoeff(A,2,1),A22=gcoeff(A,2,2), B21=gcoeff(B,2,1),B22=gcoeff(B,2,2);
    2580           0 :   GEN M1 = F2xqX_mul(F2xX_add(A11,A22), F2xX_add(B11,B22), T);
    2581           0 :   GEN M2 = F2xqX_mul(F2xX_add(A21,A22), B11, T);
    2582           0 :   GEN M3 = F2xqX_mul(A11, F2xX_add(B12,B22), T);
    2583           0 :   GEN M4 = F2xqX_mul(A22, F2xX_add(B21,B11), T);
    2584           0 :   GEN M5 = F2xqX_mul(F2xX_add(A11,A12), B22, T);
    2585           0 :   GEN M6 = F2xqX_mul(F2xX_add(A21,A11), F2xX_add(B11,B12), T);
    2586           0 :   GEN M7 = F2xqX_mul(F2xX_add(A12,A22), F2xX_add(B21,B22), T);
    2587           0 :   GEN T1 = F2xX_add(M1,M4), T2 = F2xX_add(M7,M5);
    2588           0 :   GEN T3 = F2xX_add(M1,M2), T4 = F2xX_add(M3,M6);
    2589           0 :   retmkmat2(mkcol2(F2xX_add(T1,T2), F2xX_add(M2,M4)),
    2590             :             mkcol2(F2xX_add(M3,M5), F2xX_add(T3,T4)));
    2591             : }
    2592             : 
    2593             : /* Return [0,1;1,-q]*M */
    2594             : static GEN
    2595           0 : F2xqX_F2xqXM_qmul(GEN q, GEN M, GEN T)
    2596             : {
    2597           0 :   GEN u, v, res = cgetg(3, t_MAT);
    2598           0 :   u = F2xX_add(gcoeff(M,1,1), F2xqX_mul(gcoeff(M,2,1), q, T));
    2599           0 :   gel(res,1) = mkcol2(gcoeff(M,2,1), u);
    2600           0 :   v = F2xX_add(gcoeff(M,1,2), F2xqX_mul(gcoeff(M,2,2), q, T));
    2601           0 :   gel(res,2) = mkcol2(gcoeff(M,2,2), v);
    2602           0 :   return res;
    2603             : }
    2604             : 
    2605             : static GEN
    2606           0 : matid2_F2xXM(long v, long sv)
    2607             : {
    2608           0 :   retmkmat2(mkcol2(pol1_F2xX(v, sv),pol_0(v)),
    2609             :             mkcol2(pol_0(v),pol1_F2xX(v, sv)));
    2610             : }
    2611             : 
    2612             : static GEN
    2613           0 : F2xqX_halfgcd_split(GEN x, GEN y, GEN T)
    2614             : {
    2615           0 :   pari_sp av=avma;
    2616             :   GEN R, S, V;
    2617             :   GEN y1, r, q;
    2618           0 :   long l = lgpol(x), n = l>>1, k;
    2619           0 :   if (lgpol(y)<=n) return matid2_F2xXM(varn(x),get_F2x_var(T));
    2620           0 :   R = F2xqX_halfgcd(RgX_shift_shallow(x,-n),RgX_shift_shallow(y,-n), T);
    2621           0 :   V = F2xqXM_F2xqX_mul2(R,x,y, T); y1 = gel(V,2);
    2622           0 :   if (lgpol(y1)<=n) return gerepilecopy(av, R);
    2623           0 :   q = F2xqX_divrem(gel(V,1), y1, T, &r);
    2624           0 :   k = 2*n-degpol(y1);
    2625           0 :   S = F2xqX_halfgcd(RgX_shift_shallow(y1,-k), RgX_shift_shallow(r,-k), T);
    2626           0 :   return gerepileupto(av, F2xqXM_mul2(S,F2xqX_F2xqXM_qmul(q,R, T), T));
    2627             : }
    2628             : 
    2629             : /* Return M in GL_2(Fp[X]) such that:
    2630             : if [a',b']~=M*[a,b]~ then degpol(a')>= (lgpol(a)>>1) >degpol(b')
    2631             : */
    2632             : 
    2633             : static GEN
    2634           0 : F2xqX_halfgcd_i(GEN x, GEN y, GEN T)
    2635             : {
    2636           0 :   if (lg(x)<=F2xqX_HALFGCD_LIMIT) return F2xqX_halfgcd_basecase(x, y, T);
    2637           0 :   return F2xqX_halfgcd_split(x, y, T);
    2638             : }
    2639             : 
    2640             : GEN
    2641           0 : F2xqX_halfgcd(GEN x, GEN y, GEN T)
    2642             : {
    2643           0 :   pari_sp av = avma;
    2644             :   GEN M,q,r;
    2645           0 :   if (!signe(x))
    2646             :   {
    2647           0 :     long v = varn(x), vT = get_F2x_var(T);
    2648           0 :     retmkmat2(mkcol2(pol_0(v),pol1_F2xX(v,vT)),
    2649             :         mkcol2(pol1_F2xX(v,vT),pol_0(v)));
    2650             :   }
    2651           0 :   if (degpol(y)<degpol(x)) return F2xqX_halfgcd_i(x, y, T);
    2652           0 :   q = F2xqX_divrem(y, x, T, &r);
    2653           0 :   M = F2xqX_halfgcd_i(x, r, T);
    2654           0 :   gcoeff(M,1,1) = F2xX_add(gcoeff(M,1,1), F2xqX_mul(q, gcoeff(M,1,2), T));
    2655           0 :   gcoeff(M,2,1) = F2xX_add(gcoeff(M,2,1), F2xqX_mul(q, gcoeff(M,2,2), T));
    2656           0 :   return gerepilecopy(av, M);
    2657             : }
    2658             : 
    2659             : static GEN
    2660      169771 : F2xqX_gcd_basecase(GEN a, GEN b, GEN T)
    2661             : {
    2662      169771 :   pari_sp av = avma, av0=avma;
    2663      698978 :   while (signe(b))
    2664             :   {
    2665             :     GEN c;
    2666      529207 :     if (gc_needed(av0,2))
    2667             :     {
    2668           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2xqX_gcd (d = %ld)",degpol(b));
    2669           0 :       gerepileall(av0,2, &a,&b);
    2670             :     }
    2671      529207 :     av = avma; c = F2xqX_rem(a, b, T); a=b; b=c;
    2672             :   }
    2673      169771 :   return gc_const(av, a);
    2674             : }
    2675             : 
    2676             : GEN
    2677      170107 : F2xqX_gcd(GEN x, GEN y, GEN T)
    2678             : {
    2679      170107 :   pari_sp av = avma;
    2680      170107 :   x = F2xqX_red(x, T);
    2681      170107 :   y = F2xqX_red(y, T);
    2682      170107 :   if (!signe(x)) return gerepileupto(av, y);
    2683      169771 :   while (lg(y)>F2xqX_GCD_LIMIT)
    2684             :   {
    2685             :     GEN c;
    2686           0 :     if (lgpol(y)<=(lgpol(x)>>1))
    2687             :     {
    2688           0 :       GEN r = F2xqX_rem(x, y, T);
    2689           0 :       x = y; y = r;
    2690             :     }
    2691           0 :     c = F2xqXM_F2xqX_mul2(F2xqX_halfgcd(x,y, T), x, y, T);
    2692           0 :     x = gel(c,1); y = gel(c,2);
    2693           0 :     gerepileall(av,2,&x,&y);
    2694             :   }
    2695      169771 :   return gerepileupto(av, F2xqX_gcd_basecase(x, y, T));
    2696             : }
    2697             : 
    2698             : static GEN
    2699          14 : F2xqX_extgcd_basecase(GEN a, GEN b, GEN T,  GEN *ptu, GEN *ptv)
    2700             : {
    2701          14 :   pari_sp av=avma;
    2702             :   GEN u,v,d,d1,v1;
    2703          14 :   long vx = varn(a);
    2704          14 :   d = a; d1 = b;
    2705          14 :   v = pol_0(vx); v1 = pol1_F2xX(vx, get_F2x_var(T));
    2706          63 :   while (signe(d1))
    2707             :   {
    2708          49 :     GEN r, q = F2xqX_divrem(d, d1, T, &r);
    2709          49 :     v = F2xX_add(v,F2xqX_mul(q,v1,T));
    2710          49 :     u=v; v=v1; v1=u;
    2711          49 :     u=r; d=d1; d1=u;
    2712          49 :     if (gc_needed(av,2))
    2713             :     {
    2714           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2xqX_extgcd (d = %ld)",degpol(d));
    2715           0 :       gerepileall(av,5, &d,&d1,&u,&v,&v1);
    2716             :     }
    2717             :   }
    2718          14 :   if (ptu) *ptu = F2xqX_div(F2xX_add(d,F2xqX_mul(b,v, T)), a, T);
    2719          14 :   *ptv = v; return d;
    2720             : }
    2721             : 
    2722             : static GEN
    2723           0 : F2xqX_extgcd_halfgcd(GEN x, GEN y, GEN T,  GEN *ptu, GEN *ptv)
    2724             : {
    2725           0 :   pari_sp av=avma;
    2726           0 :   GEN u,v,R = matid2_F2xXM(varn(x), get_F2x_var(T));
    2727           0 :   while (lg(y)>F2xqX_EXTGCD_LIMIT)
    2728             :   {
    2729             :     GEN M, c;
    2730           0 :     if (lgpol(y)<=(lgpol(x)>>1))
    2731             :     {
    2732           0 :       GEN r, q = F2xqX_divrem(x, y, T, &r);
    2733           0 :       x = y; y = r;
    2734           0 :       R = F2xqX_F2xqXM_qmul(q, R, T);
    2735             :     }
    2736           0 :     M = F2xqX_halfgcd(x,y, T);
    2737           0 :     c = F2xqXM_F2xqX_mul2(M, x,y, T);
    2738           0 :     R = F2xqXM_mul2(M, R, T);
    2739           0 :     x = gel(c,1); y = gel(c,2);
    2740           0 :     gerepileall(av,3,&x,&y,&R);
    2741             :   }
    2742           0 :   y = F2xqX_extgcd_basecase(x,y, T, &u,&v);
    2743           0 :   if (ptu) *ptu = F2xqX_addmulmul(u,v,gcoeff(R,1,1),gcoeff(R,2,1), T);
    2744           0 :   *ptv = F2xqX_addmulmul(u,v,gcoeff(R,1,2),gcoeff(R,2,2), T);
    2745           0 :   return y;
    2746             : }
    2747             : 
    2748             : /* x and y in Z[Y][X], return lift(gcd(x mod T,p, y mod T,p)). Set u and v st
    2749             :  * ux + vy = gcd (mod T,p) */
    2750             : GEN
    2751          14 : F2xqX_extgcd(GEN x, GEN y, GEN T,  GEN *ptu, GEN *ptv)
    2752             : {
    2753          14 :   pari_sp av = avma;
    2754             :   GEN d;
    2755          14 :   x = F2xqX_red(x, T);
    2756          14 :   y = F2xqX_red(y, T);
    2757          14 :   if (lg(y)>F2xqX_EXTGCD_LIMIT)
    2758           0 :     d = F2xqX_extgcd_halfgcd(x, y, T, ptu, ptv);
    2759             :   else
    2760          14 :     d = F2xqX_extgcd_basecase(x, y, T, ptu, ptv);
    2761          14 :   return gc_all(av, ptu?3:2, &d, ptv, ptu);
    2762             : }
    2763             : 
    2764             : static GEN
    2765           0 : _F2xqX_mul(void *data,GEN a,GEN b) { return F2xqX_mul(a,b, (GEN) data); }
    2766             : static GEN
    2767           0 : _F2xqX_sqr(void *data,GEN a) { return F2xqX_sqr(a, (GEN) data); }
    2768             : GEN
    2769           0 : F2xqX_powu(GEN x, ulong n, GEN T)
    2770           0 : { return gen_powu(x, n, (void*)T, &_F2xqX_sqr, &_F2xqX_mul); }
    2771             : 
    2772             : /* Res(A,B) = Res(B,R) * lc(B)^(a-r) * (-1)^(ab), with R=A%B, a=deg(A) ...*/
    2773             : GEN
    2774          21 : F2xqX_resultant(GEN a, GEN b, GEN T)
    2775             : {
    2776          21 :   long vT = get_F2x_var(T);
    2777             :   long da,db,dc;
    2778             :   pari_sp av;
    2779          21 :   GEN c,lb, res = pol1_F2x(vT);
    2780             : 
    2781          21 :   if (!signe(a) || !signe(b)) return pol0_F2x(vT);
    2782             : 
    2783          21 :   da = degpol(a);
    2784          21 :   db = degpol(b);
    2785          21 :   if (db > da)
    2786           7 :     swapspec(a,b, da,db);
    2787          21 :   if (!da) return pol1_F2x(vT); /* = res * a[2] ^ db, since 0 <= db <= da = 0 */
    2788          21 :   av = avma;
    2789          49 :   while (db)
    2790             :   {
    2791          28 :     lb = gel(b,db+2);
    2792          28 :     c = F2xqX_rem(a,b, T);
    2793          28 :     a = b; b = c; dc = degpol(c);
    2794          28 :     if (dc < 0) { set_avma(av); return pol0_F2x(vT); }
    2795             : 
    2796          28 :     if (!equali1(lb)) res = F2xq_mul(res, F2xq_powu(lb, da - dc, T), T);
    2797          28 :     if (gc_needed(av,2))
    2798             :     {
    2799           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2xqX_resultant (da = %ld)",da);
    2800           0 :       gerepileall(av,3, &a,&b,&res);
    2801             :     }
    2802          28 :     da = db; /* = degpol(a) */
    2803          28 :     db = dc; /* = degpol(b) */
    2804             :   }
    2805          21 :   res = F2xq_mul(res, F2xq_powu(gel(b,2), da, T), T);
    2806          21 :   return gerepileupto(av, res);
    2807             : }
    2808             : 
    2809             : /* disc P = (-1)^(n(n-1)/2) lc(P)^(n - deg P' - 2) Res(P,P'), n = deg P */
    2810             : GEN
    2811          14 : F2xqX_disc(GEN P, GEN T)
    2812             : {
    2813          14 :   pari_sp av = avma;
    2814          14 :   GEN L, dP = F2xX_deriv(P), D = F2xqX_resultant(P, dP, T);
    2815             :   long dd;
    2816          14 :   if (!lgpol(D)) return pol_0(get_F2x_var(T));
    2817          14 :   dd = degpol(P) - 2 - degpol(dP); /* >= -1; > -1 iff p | deg(P) */
    2818          14 :   L = leading_coeff(P);
    2819          14 :   if (dd && !F2x_equal1(L))
    2820           0 :     D = (dd == -1)? F2xq_div(D,L,T): F2xq_mul(D, F2xq_powu(L, dd, T), T);
    2821          14 :   return gerepileupto(av, D);
    2822             : }
    2823             : 
    2824             : /***********************************************************************/
    2825             : /**                                                                   **/
    2826             : /**                             F2xqXQ                                **/
    2827             : /**                                                                   **/
    2828             : /***********************************************************************/
    2829             : 
    2830             : GEN
    2831      114520 : F2xqXQ_mul(GEN x, GEN y, GEN S, GEN T) {
    2832      114520 :   return F2xqX_rem(F2xqX_mul(x,y,T),S,T);
    2833             : }
    2834             : 
    2835             : GEN
    2836      104125 : F2xqXQ_sqr(GEN x, GEN S, GEN T) {
    2837      104125 :   return F2xqX_rem(F2xqX_sqr(x,T),S,T);
    2838             : }
    2839             : 
    2840             : GEN
    2841           7 : F2xqXQ_invsafe(GEN x, GEN S, GEN T)
    2842             : {
    2843           7 :   GEN V, z = F2xqX_extgcd(get_F2xqX_mod(S), x, T, NULL, &V);
    2844           7 :   if (degpol(z)) return NULL;
    2845           7 :   z = F2xq_invsafe(gel(z,2),T);
    2846           7 :   if (!z) return NULL;
    2847           7 :   return F2xqX_F2xq_mul(V, z, T);
    2848             : }
    2849             : 
    2850             : GEN
    2851           7 : F2xqXQ_inv(GEN x, GEN S, GEN T)
    2852             : {
    2853           7 :   pari_sp av = avma;
    2854           7 :   GEN U = F2xqXQ_invsafe(x, S, T);
    2855           7 :   if (!U) pari_err_INV("F2xqXQ_inv",x);
    2856           7 :   return gerepileupto(av, U);
    2857             : }
    2858             : 
    2859             : struct _F2xqXQ {
    2860             :   GEN T, S;
    2861             : };
    2862             : 
    2863             : static GEN
    2864      344316 : _F2xqXQ_add(void *data, GEN x, GEN y) {
    2865             :   (void) data;
    2866      344316 :   return F2xX_add(x,y);
    2867             : }
    2868             : static GEN
    2869      480690 : _F2xqXQ_cmul(void *data, GEN P, long a, GEN x) {
    2870             :   (void) data;
    2871      480690 :   return F2xX_F2x_mul(x,gel(P,a+2));
    2872             : }
    2873             : static GEN
    2874      352261 : _F2xqXQ_red(void *data, GEN x) {
    2875      352261 :   struct _F2xqXQ *d = (struct _F2xqXQ*) data;
    2876      352261 :   return F2xqX_red(x, d->T);
    2877             : }
    2878             : static GEN
    2879      114464 : _F2xqXQ_mul(void *data, GEN x, GEN y) {
    2880      114464 :   struct _F2xqXQ *d = (struct _F2xqXQ*) data;
    2881      114464 :   return F2xqXQ_mul(x,y, d->S,d->T);
    2882             : }
    2883             : static GEN
    2884       32984 : _F2xqXQ_sqr(void *data, GEN x) {
    2885       32984 :   struct _F2xqXQ *d = (struct _F2xqXQ*) data;
    2886       32984 :   return F2xqXQ_sqr(x, d->S,d->T);
    2887             : }
    2888             : static GEN
    2889          56 : _F2xqXQ_zero(void *data) {
    2890          56 :   struct _F2xqXQ *d = (struct _F2xqXQ*) data;
    2891          56 :   return pol_0(get_F2xqX_var(d->S));
    2892             : }
    2893             : static GEN
    2894      375410 : _F2xqXQ_one(void *data) {
    2895      375410 :   struct _F2xqXQ *d = (struct _F2xqXQ*) data;
    2896      375410 :   return pol1_F2xX(get_F2xqX_var(d->S),get_F2x_var(d->T));
    2897             : }
    2898             : 
    2899             : static struct bb_algebra F2xqXQ_algebra = { _F2xqXQ_red,
    2900             :  _F2xqXQ_add, _F2xqXQ_add, _F2xqXQ_mul,_F2xqXQ_sqr,_F2xqXQ_one,_F2xqXQ_zero };
    2901             : 
    2902             : GEN
    2903           7 : F2xqXQ_pow(GEN x, GEN n, GEN S, GEN T)
    2904             : {
    2905             :   struct _F2xqXQ D;
    2906           7 :   long s = signe(n);
    2907           7 :   if (!s) return pol1_F2xX(get_F2xqX_var(S), get_F2x_var(T));
    2908           7 :   if (s < 0) x = F2xqXQ_inv(x,S,T);
    2909           7 :   if (is_pm1(n)) return s < 0 ? x : gcopy(x);
    2910           7 :   if (degpol(x) >= get_F2xqX_degree(S)) x = F2xqX_rem(x,S,T);
    2911           7 :   D.T = F2x_get_red(T);
    2912           7 :   D.S = F2xqX_get_red(S, T);
    2913           7 :   return gen_pow(x, n, (void*)&D, &_F2xqXQ_sqr, &_F2xqXQ_mul);
    2914             : }
    2915             : 
    2916             : GEN
    2917        7469 : F2xqXQ_powers(GEN x, long l, GEN S, GEN T)
    2918             : {
    2919             :   struct _F2xqXQ D;
    2920        7469 :   int use_sqr = 2*degpol(x) >= get_F2xqX_degree(S);
    2921        7469 :   D.T = F2x_get_red(T);
    2922        7469 :   D.S = F2xqX_get_red(S, T);
    2923        7469 :   return gen_powers(x, l, use_sqr, (void*)&D, &_F2xqXQ_sqr, &_F2xqXQ_mul,&_F2xqXQ_one);
    2924             : }
    2925             : 
    2926             : GEN
    2927       13881 : F2xqX_F2xqXQV_eval(GEN P, GEN V, GEN S, GEN T)
    2928             : {
    2929             :   struct _F2xqXQ D;
    2930       13881 :   D.T = F2x_get_red(T);
    2931       13881 :   D.S = F2xqX_get_red(S, T);
    2932       13881 :   return gen_bkeval_powers(P, degpol(P), V, (void*)&D, &F2xqXQ_algebra,
    2933             :                                                    _F2xqXQ_cmul);
    2934             : }
    2935             : 
    2936             : GEN
    2937      122549 : F2xqX_F2xqXQ_eval(GEN Q, GEN x, GEN S, GEN T)
    2938             : {
    2939             :   struct _F2xqXQ D;
    2940      122549 :   int use_sqr = 2*degpol(x) >= get_F2xqX_degree(S);
    2941      122549 :   D.T = F2x_get_red(T);
    2942      122549 :   D.S = F2xqX_get_red(S, T);
    2943      122549 :   return gen_bkeval(Q, degpol(Q), x, use_sqr, (void*)&D, &F2xqXQ_algebra,
    2944             :                                                     _F2xqXQ_cmul);
    2945             : }
    2946             : 
    2947             : static GEN
    2948       89068 : F2xqXQ_autpow_sqr(void * E, GEN x)
    2949             : {
    2950       89068 :   struct _F2xqXQ *D = (struct _F2xqXQ *)E;
    2951       89068 :   GEN T = D->T;
    2952       89068 :   GEN phi = gel(x,1), S = gel(x,2);
    2953       89068 :   long n = brent_kung_optpow(get_F2x_degree(T)-1,lgpol(S)+1,1);
    2954       89068 :   GEN V = F2xq_powers(phi, n, T);
    2955       89068 :   GEN phi2 = F2x_F2xqV_eval(phi, V, T);
    2956       89068 :   GEN Sphi = F2xY_F2xqV_evalx(S, V, T);
    2957       89068 :   GEN S2 = F2xqX_F2xqXQ_eval(Sphi, S, D->S, T);
    2958       89068 :   return mkvec2(phi2, S2);
    2959             : }
    2960             : 
    2961             : static GEN
    2962       33481 : F2xqXQ_autpow_mul(void * E, GEN x, GEN y)
    2963             : {
    2964       33481 :   struct _F2xqXQ *D = (struct _F2xqXQ *)E;
    2965       33481 :   GEN T = D->T;
    2966       33481 :   GEN phi1 = gel(x,1), S1 = gel(x,2);
    2967       33481 :   GEN phi2 = gel(y,1), S2 = gel(y,2);
    2968       33481 :   long n = brent_kung_optpow(get_F2x_degree(T)-1,lgpol(S1)+1,1);
    2969       33481 :   GEN V = F2xq_powers(phi2, n, T);
    2970       33481 :   GEN phi3 = F2x_F2xqV_eval(phi1,V,T);
    2971       33481 :   GEN Sphi = F2xY_F2xqV_evalx(S1,V,T);
    2972       33481 :   GEN S3 = F2xqX_F2xqXQ_eval(Sphi, S2, D->S, T);
    2973       33481 :   return mkvec2(phi3, S3);
    2974             : }
    2975             : 
    2976             : GEN
    2977       70686 : F2xqXQ_autpow(GEN aut, long n, GEN S, GEN T)
    2978             : {
    2979             :   struct _F2xqXQ D;
    2980       70686 :   D.T = F2x_get_red(T);
    2981       70686 :   D.S = F2xqX_get_red(S, T);
    2982       70686 :   return gen_powu(aut,n,&D,F2xqXQ_autpow_sqr,F2xqXQ_autpow_mul);
    2983             : }
    2984             : 
    2985             : static GEN
    2986        6916 : F2xqXQ_auttrace_mul(void *E, GEN x, GEN y)
    2987             : {
    2988        6916 :   struct _F2xqXQ *D = (struct _F2xqXQ *) E;
    2989        6916 :   GEN T = D->T;
    2990        6916 :   GEN phi1 = gel(x,1), S1 = gel(x,2), a1 = gel(x,3);
    2991        6916 :   GEN phi2 = gel(y,1), S2 = gel(y,2), a2 = gel(y,3);
    2992        6916 :   long n2 = brent_kung_optpow(get_F2x_degree(T)-1, lgpol(S1)+lgpol(a1)+1, 1);
    2993        6916 :   GEN V2 = F2xq_powers(phi2, n2, T);
    2994        6916 :   GEN phi3 = F2x_F2xqV_eval(phi1, V2, T);
    2995        6916 :   GEN Sphi = F2xY_F2xqV_evalx(S1, V2, T);
    2996        6916 :   GEN aphi = F2xY_F2xqV_evalx(a1, V2, T);
    2997        6916 :   long n = brent_kung_optpow(maxss(degpol(Sphi),degpol(aphi)),2,1);
    2998        6916 :   GEN V = F2xqXQ_powers(S2, n, D->S, T);
    2999        6916 :   GEN S3 = F2xqX_F2xqXQV_eval(Sphi, V, D->S, T);
    3000        6916 :   GEN aS = F2xqX_F2xqXQV_eval(aphi, V, D->S, T);
    3001        6916 :   GEN a3 = F2xX_add(aS, a2);
    3002        6916 :   return mkvec3(phi3, S3, a3);
    3003             : }
    3004             : 
    3005             : static GEN
    3006        4641 : F2xqXQ_auttrace_sqr(void *E, GEN x) { return F2xqXQ_auttrace_mul(E, x, x); }
    3007             : GEN
    3008        2646 : F2xqXQ_auttrace(GEN aut, long n, GEN S, GEN T)
    3009             : {
    3010             :   struct _F2xqXQ D;
    3011        2646 :   D.T = F2x_get_red(T);
    3012        2646 :   D.S = F2xqX_get_red(S, T);
    3013        2646 :   return gen_powu(aut,n,&D,F2xqXQ_auttrace_sqr,F2xqXQ_auttrace_mul);
    3014             : }
    3015             : 
    3016             : GEN
    3017          63 : F2xqXQV_red(GEN x, GEN S, GEN T)
    3018         273 : { pari_APPLY_type(t_VEC, F2xqX_rem(gel(x,i), S, T)) }

Generated by: LCOV version 1.13