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.12.0 lcov report (development 23339-b1c33c51a) Lines: 1463 1575 92.9 %
Date: 2018-12-11 05:41:34 Functions: 179 189 94.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. It is distributed in the hope that it will be useful, but WITHOUT
       8             : ANY WARRANTY WHATSOEVER.
       9             : 
      10             : Check the License for details. You should have received a copy of it, along
      11             : with the package; see the file 'COPYING'. If not, write to the Free Software
      12             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      13             : 
      14             : #include "pari.h"
      15             : #include "paripriv.h"
      16             : 
      17             : /* Not so fast arithmetic with polynomials over F_2 */
      18             : 
      19             : /***********************************************************************/
      20             : /**                                                                   **/
      21             : /**                             F2x                                   **/
      22             : /**                                                                   **/
      23             : /***********************************************************************/
      24             : /* F2x objects are defined as follows:
      25             :    An F2x is a t_VECSMALL:
      26             :    x[0] = codeword
      27             :    x[1] = evalvarn(variable number)  (signe is not stored).
      28             :    x[2] = a_0...a_31 x[3] = a_32..a_63, etc.  on 32bit
      29             :    x[2] = a_0...a_63 x[3] = a_64..a_127, etc. on 64bit
      30             : 
      31             :    where the a_i are bits.
      32             : 
      33             :    signe(x) is not valid. Use lgpol(x)!=0 instead.
      34             :    Note: pol0_F2x=pol0_Flx and pol1_F2x=pol1_Flx
      35             : */
      36             : 
      37             : INLINE long
      38   249282350 : F2x_degree_lg(GEN x, long l)
      39             : {
      40   249282350 :   return (l==2)?-1:bit_accuracy(l)-bfffo(x[l-1])-1;
      41             : }
      42             : 
      43             : long
      44    70640738 : F2x_degree(GEN x)
      45             : {
      46    70640738 :   return F2x_degree_lg(x, lg(x));
      47             : }
      48             : 
      49             : GEN
      50          63 : monomial_F2x(long d, long vs)
      51             : {
      52          63 :   long l=nbits2lg(d+1);
      53          63 :   GEN z = zero_zv(l-1);
      54          63 :   z[1] = vs;
      55          63 :   F2x_set(z,d);
      56          63 :   return z;
      57             : }
      58             : 
      59             : GEN
      60      215954 : F2x_to_ZX(GEN x)
      61             : {
      62      215954 :   long l=3+F2x_degree(x);
      63      215954 :   GEN z=cgetg(l,t_POL);
      64             :   long i,j,k;
      65      432839 :   for(i=2,k=2;i<lg(x);i++)
      66      971729 :     for(j=0; j<BITS_IN_LONG && k<l; j++,k++)
      67      754844 :       gel(z,k)=(x[i]&(1UL<<j))?gen_1:gen_0;
      68      215954 :   z[1]=evalsigne(l>=3)|x[1];
      69      215954 :   return z;
      70             : }
      71             : 
      72             : GEN
      73      103822 : F2x_to_Flx(GEN x)
      74             : {
      75      103822 :   long l=3+F2x_degree(x);
      76      103823 :   GEN z=cgetg(l,t_VECSMALL);
      77             :   long i,j,k;
      78      103843 :   z[1]=x[1];
      79      230801 :   for(i=2,k=2;i<lg(x);i++)
      80     3197482 :     for(j=0;j<BITS_IN_LONG && k<l; j++,k++)
      81     3070524 :       z[k]=(x[i]>>j)&1UL;
      82      103843 :   return z;
      83             : }
      84             : 
      85             : GEN
      86         322 : F2x_to_F2xX(GEN z, long sv)
      87             : {
      88         322 :   long i, d = F2x_degree(z);
      89         322 :   GEN x = cgetg(d+3,t_POL);
      90        6293 :   for (i=0; i<=d; i++)
      91        5971 :     gel(x,i+2) = F2x_coeff(z,i) ? pol1_F2x(sv): pol0_F2x(sv);
      92         322 :   x[1] = evalsigne(d+1!=0)| z[1]; return x;
      93             : }
      94             : 
      95             : GEN
      96      209132 : Z_to_F2x(GEN x, long v)
      97             : {
      98      209132 :   long sv = evalvarn(v);
      99      209132 :   return mpodd(x) ? pol1_F2x(sv): pol0_F2x(sv);
     100             : }
     101             : 
     102             : GEN
     103      373158 : ZX_to_F2x(GEN x)
     104             : {
     105      373158 :   long l=nbits2lg(lgpol(x));
     106      373158 :   GEN z=cgetg(l,t_VECSMALL);
     107             :   long i,j,k;
     108      373158 :   z[1]=((ulong)x[1])&VARNBITS;
     109     1654779 :   for(i=2, k=1,j=BITS_IN_LONG;i<lg(x);i++,j++)
     110             :   {
     111     1281621 :     if (j==BITS_IN_LONG)
     112             :     {
     113      357145 :       j=0; k++; z[k]=0;
     114             :     }
     115     1281621 :     if (mpodd(gel(x,i)))
     116      832267 :       z[k]|=1UL<<j;
     117             :   }
     118      373158 :   return F2x_renormalize(z,l);
     119             : }
     120             : 
     121             : GEN
     122       96494 : Flx_to_F2x(GEN x)
     123             : {
     124       96494 :   long l=nbits2lg(lgpol(x));
     125       96491 :   GEN z=cgetg(l,t_VECSMALL);
     126             :   long i,j,k;
     127       96516 :   z[1]=x[1];
     128     3136107 :   for(i=2, k=1,j=BITS_IN_LONG;i<lg(x);i++,j++)
     129             :   {
     130     3039591 :     if (j==BITS_IN_LONG)
     131             :     {
     132      112808 :       j=0; k++; z[k]=0;
     133             :     }
     134     3039591 :     if (x[i]&1UL)
     135     1555409 :       z[k]|=1UL<<j;
     136             :   }
     137       96516 :   return F2x_renormalize(z,l);
     138             : }
     139             : 
     140             : GEN
     141     1502647 : F2x_to_F2v(GEN x, long N)
     142             : {
     143     1502647 :   long i, l = lg(x);
     144     1502647 :   long n = nbits2lg(N);
     145     1502588 :   GEN z = cgetg(n,t_VECSMALL);
     146     1502643 :   z[1] = N;
     147     1502643 :   for (i=2; i<l ; i++) z[i]=x[i];
     148     1502643 :   for (   ; i<n; i++) z[i]=0;
     149     1502643 :   return z;
     150             : }
     151             : 
     152             : GEN
     153        1190 : RgX_to_F2x(GEN x)
     154             : {
     155        1190 :   long l=nbits2lg(lgpol(x));
     156        1190 :   GEN z=cgetg(l,t_VECSMALL);
     157             :   long i,j,k;
     158        1190 :   z[1]=((ulong)x[1])&VARNBITS;
     159        3724 :   for(i=2, k=1,j=BITS_IN_LONG;i<lg(x);i++,j++)
     160             :   {
     161        2534 :     if (j==BITS_IN_LONG)
     162             :     {
     163        1176 :       j=0; k++; z[k]=0;
     164             :     }
     165        2534 :     if (Rg_to_F2(gel(x,i)))
     166        1253 :       z[k]|=1UL<<j;
     167             :   }
     168        1190 :   return F2x_renormalize(z,l);
     169             : }
     170             : 
     171             : /* If x is a POLMOD, assume modulus is a multiple of T. */
     172             : GEN
     173     1164465 : Rg_to_F2xq(GEN x, GEN T)
     174             : {
     175     1164465 :   long ta, tx = typ(x), v = T[1];
     176             :   GEN a, b;
     177     1164465 :   if (is_const_t(tx))
     178             :   {
     179     1163436 :     if (tx == t_FFELT) return FF_to_F2xq(x);
     180      244761 :     return Rg_to_F2(x)? pol1_F2x(v): pol0_F2x(v);
     181             :   }
     182        1029 :   switch(tx)
     183             :   {
     184             :     case t_POLMOD:
     185           0 :       b = gel(x,1);
     186           0 :       a = gel(x,2); ta = typ(a);
     187           0 :       if (is_const_t(ta)) return Rg_to_F2(a)? pol1_F2x(v): pol0_F2x(v);
     188           0 :       b = RgX_to_F2x(b); if (b[1] != v) break;
     189           0 :       a = RgX_to_F2x(a); if (F2x_equal(b,T)) return a;
     190           0 :       if (lgpol(F2x_rem(b,T))==0) return F2x_rem(a, T);
     191           0 :       break;
     192             :     case t_POL:
     193        1029 :       x = RgX_to_F2x(x);
     194        1029 :       if (x[1] != v) break;
     195        1029 :       return F2x_rem(x, T);
     196             :     case t_RFRAC:
     197           0 :       a = Rg_to_F2xq(gel(x,1), T);
     198           0 :       b = Rg_to_F2xq(gel(x,2), T);
     199           0 :       return F2xq_div(a,b, T);
     200             :   }
     201           0 :   pari_err_TYPE("Rg_to_F2xq",x);
     202             :   return NULL; /* LCOV_EXCL_LINE */
     203             : }
     204             : 
     205             : ulong
     206         245 : F2x_eval(GEN P, ulong x)
     207             : {
     208         245 :   if (odd(x))
     209             :   {
     210         133 :     long i, lP = lg(P);
     211         133 :     ulong c = 0;
     212         266 :     for (i=2; i<lP; i++)
     213         133 :       c ^= P[i];
     214             : #ifdef LONG_IS_64BIT
     215         114 :     c ^= c >> 32;
     216             : #endif
     217         133 :     c ^= c >> 16;
     218         133 :     c ^= c >>  8;
     219         133 :     c ^= c >>  4;
     220         133 :     c ^= c >>  2;
     221         133 :     c ^= c >>  1;
     222         133 :     return c & 1;
     223             :   }
     224         112 :   else return F2x_coeff(P,0);
     225             : }
     226             : 
     227             : GEN
     228    30134209 : F2x_add(GEN x, GEN y)
     229             : {
     230             :   long i,lz;
     231             :   GEN z;
     232    30134209 :   long lx=lg(x);
     233    30134209 :   long ly=lg(y);
     234    30134209 :   if (ly>lx) swapspec(x,y, lx,ly);
     235    30134209 :   lz = lx; z = cgetg(lz, t_VECSMALL); z[1]=x[1];
     236    30165278 :   for (i=2; i<ly; i++) z[i] = x[i]^y[i];
     237    30165278 :   for (   ; i<lx; i++) z[i] = x[i];
     238    30165278 :   return F2x_renormalize(z, lz);
     239             : }
     240             : 
     241             : static GEN
     242       46004 : F2x_addspec(GEN x, GEN y, long lx, long ly)
     243             : {
     244             :   long i,lz;
     245             :   GEN z;
     246             : 
     247       46004 :   if (ly>lx) swapspec(x,y, lx,ly);
     248       46004 :   lz = lx+2; z = cgetg(lz, t_VECSMALL) + 2;
     249      144446 :   for (i=0; i<ly-3; i+=4)
     250             :   {
     251       98442 :     z[i] = x[i]^y[i];
     252       98442 :     z[i+1] = x[i+1]^y[i+1];
     253       98442 :     z[i+2] = x[i+2]^y[i+2];
     254       98442 :     z[i+3] = x[i+3]^y[i+3];
     255             :   }
     256       73911 :   for (; i<ly; i++)
     257       27907 :     z[i] = x[i]^y[i];
     258       46004 :   for (   ; i<lx; i++) z[i] = x[i];
     259       46004 :   z -= 2; return F2x_renormalize(z, lz);
     260             : }
     261             : 
     262             : GEN
     263      189733 : F2x_1_add(GEN y)
     264             : {
     265             :   GEN z;
     266             :   long lz, i;
     267      189733 :   if (!lgpol(y))
     268       90158 :     return pol1_F2x(y[1]);
     269       99575 :   lz=lg(y);
     270       99575 :   z=cgetg(lz,t_VECSMALL);
     271       99575 :   z[1] = y[1];
     272       99575 :   z[2] = y[2]^1UL;
     273       99575 :   for(i=3;i<lz;i++)
     274           0 :     z[i] = y[i];
     275       99575 :   if (lz==3) z = F2x_renormalize(z,lz);
     276       99575 :   return z;
     277             : }
     278             : 
     279             : INLINE void
     280   161119106 : F2x_addshiftipspec(GEN x, GEN y, long ny, ulong db)
     281             : {
     282             :   long i;
     283   161119106 :   if (db)
     284             :   {
     285   137781694 :     ulong dc=BITS_IN_LONG-db;
     286   137781694 :     ulong r=0, yi;
     287   220313380 :     for(i=0; i<ny-3; i+=4)
     288             :     {
     289    82531686 :       yi = uel(y,i);   x[i]   ^= (yi<<db)|r; r = yi>>dc;
     290    82531686 :       yi = uel(y,i+1); x[i+1] ^= (yi<<db)|r; r = yi>>dc;
     291    82531686 :       yi = uel(y,i+2); x[i+2] ^= (yi<<db)|r; r = yi>>dc;
     292    82531686 :       yi = uel(y,i+3); x[i+3] ^= (yi<<db)|r; r = yi>>dc;
     293             :     }
     294   264926568 :     for(  ; i<ny; i++)
     295             :     {
     296   127144874 :       ulong yi = uel(y,i); x[i] ^= (yi<<db)|r; r = yi>>dc;
     297             :     }
     298   137781694 :     if (r) x[i] ^= r;
     299             :   }
     300             :   else
     301             :   {
     302    26745486 :     for(i=0; i<ny-3; i+=4)
     303             :     {
     304     3408074 :       x[i]   ^= y[i];
     305     3408074 :       x[i+1] ^= y[i+1];
     306     3408074 :       x[i+2] ^= y[i+2];
     307     3408074 :       x[i+3] ^= y[i+3];
     308             :     }
     309    49504099 :     for(   ; i<ny; i++)
     310    26166687 :       x[i] ^= y[i];
     311             :   }
     312   161119106 : }
     313             : 
     314             : INLINE void
     315   128923120 : F2x_addshiftip(GEN x, GEN y, ulong d)
     316             : {
     317   128923120 :   ulong db, dl=dvmduBIL(d, &db);
     318   128533038 :   F2x_addshiftipspec(x+2+dl, y+2, lgpol(y), db);
     319   128616949 : }
     320             : 
     321             : static GEN
     322    17890397 : F2x_mul1(ulong x, ulong y)
     323             : {
     324    17890397 :   ulong x1=(x&HIGHMASK)>>BITS_IN_HALFULONG;
     325    17890397 :   ulong x2=x&LOWMASK;
     326    17890397 :   ulong y1=(y&HIGHMASK)>>BITS_IN_HALFULONG;
     327    17890397 :   ulong y2=y&LOWMASK;
     328             :   ulong r1,r2,rr;
     329             :   GEN z;
     330             :   ulong i;
     331    17890397 :   rr=r1=r2=0UL;
     332    17890397 :   if (x2)
     333   552673358 :     for(i=0;i<BITS_IN_HALFULONG;i++)
     334   534819820 :       if (x2&(1UL<<i))
     335             :       {
     336    46874046 :         r2^=y2<<i;
     337    46874046 :         rr^=y1<<i;
     338             :       }
     339    17890397 :   if (x1)
     340     3184554 :     for(i=0;i<BITS_IN_HALFULONG;i++)
     341     3073713 :       if (x1&(1UL<<i))
     342             :       {
     343      873817 :         r1^=y1<<i;
     344      873817 :         rr^=y2<<i;
     345             :       }
     346    17890397 :   r2^=(rr&LOWMASK)<<BITS_IN_HALFULONG;
     347    17890397 :   r1^=(rr&HIGHMASK)>>BITS_IN_HALFULONG;
     348    17890397 :   z=cgetg((r1?4:3),t_VECSMALL);
     349    17890198 :   z[2]=r2;
     350    17890198 :   if (r1) z[3]=r1;
     351    17890198 :   return z;
     352             : }
     353             : 
     354             : static GEN
     355     5074888 : F2x_mulspec_basecase(GEN x, GEN y, long nx, long ny)
     356             : {
     357             :   long l, i, j;
     358             :   GEN z;
     359     5074888 :   l = nx + ny;
     360     5074888 :   z = zero_Flv(l+1);
     361     5748359 :   for(i=0; i < ny-1; i++)
     362             :   {
     363      672740 :     GEN zi = z+2+i;
     364      672740 :     ulong yi = uel(y,i);
     365      672740 :     if (yi)
     366    37572604 :       for(j=0; j < BITS_IN_LONG; j++)
     367    36900069 :         if (yi&(1UL<<j)) F2x_addshiftipspec(zi,x,nx,j);
     368             :   }
     369             :   {
     370     5075619 :     GEN zi = z+2+i;
     371     5075619 :     ulong yi = uel(y,i);
     372     5075619 :     long c = BITS_IN_LONG-bfffo(yi);
     373    31434242 :     for(j=0; j < c; j++)
     374    26359252 :       if (yi&(1UL<<j)) F2x_addshiftipspec(zi,x,nx,j);
     375             :   }
     376     5074990 :   return F2x_renormalize(z, l+2);
     377             : }
     378             : 
     379             : static GEN
     380       30470 : F2x_addshift(GEN x, GEN y, long d)
     381             : {
     382       30470 :   GEN xd,yd,zd = (GEN)avma;
     383       30470 :   long a,lz,ny = lgpol(y), nx = lgpol(x);
     384       30470 :   long vs = x[1];
     385             : 
     386       30470 :   x += 2; y += 2; a = ny-d;
     387       30470 :   if (a <= 0)
     388             :   {
     389        2112 :     lz = (a>nx)? ny+2: nx+d+2;
     390        2112 :     (void)new_chunk(lz); xd = x+nx; yd = y+ny;
     391        2112 :     while (xd > x) *--zd = *--xd;
     392        2112 :     x = zd + a;
     393        2112 :     while (zd > x) *--zd = 0;
     394             :   }
     395             :   else
     396             :   {
     397       28358 :     xd = new_chunk(d); yd = y+d;
     398       28358 :     x = F2x_addspec(x,yd,nx,a);
     399       28358 :     lz = (a>nx)? ny+2: lg(x)+d;
     400       28358 :     x += 2; while (xd > x) *--zd = *--xd;
     401             :   }
     402       30470 :   while (yd > y) *--zd = *--yd;
     403       30470 :   *--zd = vs;
     404       30470 :   *--zd = evaltyp(t_VECSMALL) | evallg(lz); return zd;
     405             : }
     406             : 
     407             : /* shift polynomial + gerepile */
     408             : /* Do not set evalvarn. Cf Flx_shiftip */
     409             : static GEN
     410    22986621 : F2x_shiftip(pari_sp av, GEN x, long v)
     411             : {
     412    22986621 :   long i, lx = lg(x), ly;
     413             :   GEN y;
     414    22986621 :   if (!v || lx==2) return gerepileuptoleaf(av, x);
     415       27670 :   ly = lx + v;
     416       27670 :   (void)new_chunk(ly); /* check that result fits */
     417       27670 :   x += lx; y = (GEN)av;
     418       27670 :   for (i = 2; i<lx; i++) *--y = *--x;
     419       27670 :   for (i = 0; i< v; i++) *--y = 0;
     420       27670 :   y -= 2; y[0] = evaltyp(t_VECSMALL) | evallg(ly);
     421       27670 :   set_avma((pari_sp)y); return y;
     422             : }
     423             : 
     424             : /* fast product (Karatsuba) of polynomials a,b. These are not real GENs, a+2,
     425             :  * b+2 were sent instead. na, nb = number of terms of a, b.
     426             :  * Only c, c0, c1, c2 are genuine GEN.
     427             :  */
     428             : static GEN
     429    27395634 : F2x_mulspec(GEN a, GEN b, long na, long nb)
     430             : {
     431             :   GEN a0,c,c0;
     432    27395634 :   long n0, n0a, i, v = 0;
     433             :   pari_sp av;
     434             : 
     435    27395634 :   while (na && !a[0]) { a++; na-=1; v++; }
     436    27395634 :   while (nb && !b[0]) { b++; nb-=1; v++; }
     437    27395634 :   if (na < nb) swapspec(a,b, na,nb);
     438    27395634 :   if (!nb) return pol0_F2x(0);
     439             : 
     440    22986650 :   av = avma;
     441    22986650 :   if (na == 1)
     442    17890123 :     return F2x_shiftip(av, F2x_mul1(*a,*b), v);
     443     5096527 :   if (na < F2x_MUL_KARATSUBA_LIMIT)
     444     5074880 :     return F2x_shiftip(av, F2x_mulspec_basecase(a, b, na, nb), v);
     445       21647 :   i=(na>>1); n0=na-i; na=i;
     446       21647 :   a0=a+n0; n0a=n0;
     447       21647 :   while (n0a && !a[n0a-1]) n0a--;
     448             : 
     449       21647 :   if (nb > n0)
     450             :   {
     451             :     GEN b0,c1,c2;
     452             :     long n0b;
     453             : 
     454        8823 :     nb -= n0; b0 = b+n0; n0b = n0;
     455        8823 :     while (n0b && !b[n0b-1]) n0b--;
     456        8823 :     c =  F2x_mulspec(a,b,n0a,n0b);
     457        8823 :     c0 = F2x_mulspec(a0,b0,na,nb);
     458             : 
     459        8823 :     c2 = F2x_addspec(a0,a,na,n0a);
     460        8823 :     c1 = F2x_addspec(b0,b,nb,n0b);
     461             : 
     462        8823 :     c1 = F2x_mul(c1,c2);
     463        8823 :     c2 = F2x_add(c0,c);
     464             : 
     465        8823 :     c2 = F2x_add(c1,c2);
     466        8823 :     c0 = F2x_addshift(c0,c2,n0);
     467             :   }
     468             :   else
     469             :   {
     470       12824 :     c  = F2x_mulspec(a,b,n0a,nb);
     471       12824 :     c0 = F2x_mulspec(a0,b,na,nb);
     472             :   }
     473       21647 :   c0 = F2x_addshift(c0,c,n0);
     474       21647 :   return F2x_shiftip(av,c0, v);
     475             : }
     476             : 
     477             : GEN
     478    27351966 : F2x_mul(GEN x, GEN y)
     479             : {
     480    27351966 :   GEN z = F2x_mulspec(x+2,y+2, lgpol(x),lgpol(y));
     481    27352394 :   z[1] = x[1]; return z;
     482             : }
     483             : 
     484             : GEN
     485     8117639 : F2x_sqr(GEN x)
     486             : {
     487     8117639 :   const ulong sq[]={0,1,4,5,16,17,20,21,64,65,68,69,80,81,84,85};
     488             :   long i,ii,j,jj;
     489     8117639 :   long lx=lg(x), lz=2+((lx-2)<<1);
     490             :   GEN z;
     491     8117639 :   z = cgetg(lz, t_VECSMALL); z[1]=x[1];
     492    16401063 :   for (j=2,jj=2;j<lx;j++,jj++)
     493             :   {
     494     8230318 :     ulong x1=((ulong)x[j]&HIGHMASK)>>BITS_IN_HALFULONG;
     495     8230318 :     ulong x2=(ulong)x[j]&LOWMASK;
     496     8230318 :     z[jj]=0;
     497     8230318 :     if (x2)
     498    68950917 :       for(i=0,ii=0;i<BITS_IN_HALFULONG;i+=4,ii+=8)
     499    60756677 :         z[jj]|=sq[(x2>>i)&15UL]<<ii;
     500     8230318 :     z[++jj]=0;
     501     8230318 :     if (x1)
     502     5772347 :       for(i=0,ii=0;i<BITS_IN_HALFULONG;i+=4,ii+=8)
     503     5016860 :         z[jj]|=sq[(x1>>i)&15UL]<<ii;
     504             :   }
     505     8170745 :   return F2x_renormalize(z, lz);
     506             : }
     507             : 
     508             : static GEN
     509      136709 : F2x_pow2n(GEN x, long n)
     510             : {
     511             :   long i;
     512      410109 :   for(i=1;i<=n;i++)
     513      273355 :     x = F2x_sqr(x);
     514      136754 :   return x;
     515             : }
     516             : 
     517             : int
     518       37122 : F2x_issquare(GEN x)
     519             : {
     520       37122 :   const ulong mask = (ULONG_MAX/3UL)*2;
     521       37122 :   ulong i, lx = lg(x);
     522       74216 :   for (i=2; i<lx; i++)
     523       37122 :     if ((x[i]&mask)) return 0;
     524       37094 :   return 1;
     525             : }
     526             : 
     527             : /* Assume x is a perfect square */
     528             : GEN
     529       96855 : F2x_sqrt(GEN x)
     530             : {
     531       96855 :   const ulong sq[]={0,1,4,5,2,3,6,7,8,9,12,13,10,11,14,15};
     532             :   long i,ii,j,jj;
     533       96855 :   long lx=lg(x), lz=2+((lx-1)>>1);
     534             :   GEN z;
     535       96855 :   z = cgetg(lz, t_VECSMALL); z[1]=x[1];
     536      193759 :   for (j=2,jj=2;jj<lz;j++,jj++)
     537             :   {
     538       96889 :     ulong x2=x[j++];
     539       96889 :     z[jj]=0;
     540       96889 :     if (x2)
     541      817722 :       for(i=0,ii=0;ii<BITS_IN_HALFULONG;i+=8,ii+=4)
     542             :       {
     543      720832 :         ulong rl = (x2>>i)&15UL, rh = (x2>>(i+4))&15UL;
     544      720832 :         z[jj]|=sq[rl|(rh<<1)]<<ii;
     545             :       }
     546       96889 :     if (j<lx)
     547             :     {
     548         260 :       x2 = x[j];
     549         260 :       if (x2)
     550        1777 :         for(i=0,ii=0;ii<BITS_IN_HALFULONG;i+=8,ii+=4)
     551             :         {
     552        1532 :           ulong rl = (x2>>i)&15UL, rh = (x2>>(i+4))&15UL;
     553        1532 :           z[jj]|=(sq[rl|(rh<<1)]<<ii)<<BITS_IN_HALFULONG;
     554             :         }
     555             :     }
     556             :   }
     557       96870 :   return F2x_renormalize(z, lz);
     558             : }
     559             : 
     560             : static GEN
     561         660 : F2x_shiftneg(GEN y, ulong d)
     562             : {
     563         660 :   long db, dl=dvmdsBIL(d, &db);
     564         660 :   long i, ly = lg(y), lx = ly-dl;
     565         660 :   GEN x = cgetg(lx, t_VECSMALL);
     566         660 :   x[1] = y[1];
     567         660 :   if (db)
     568             :   {
     569         660 :     ulong dc=BITS_IN_LONG-db;
     570         660 :     ulong r=0;
     571        1320 :     for(i=lx-1; i>=2; i--)
     572             :     {
     573         660 :       x[i] = (((ulong)y[i+dl])>>db)|r;
     574         660 :       r = ((ulong)y[i+dl])<<dc;
     575             :     }
     576             :   }
     577             :   else
     578           0 :     for(i=2; i<lx; i++)
     579           0 :       x[i] = y[i+dl];
     580         660 :   return F2x_renormalize(x,lx);
     581             : }
     582             : 
     583             : static GEN
     584      240783 : F2x_shiftpos(GEN y, ulong d)
     585             : {
     586      240783 :   long db, dl=dvmdsBIL(d, &db);
     587      240608 :   long i, ly = lg(y), lx = ly+dl+(!!db);
     588      240608 :   GEN x = cgetg(lx, t_VECSMALL);
     589      240807 :   x[1] = y[1]; for(i=0; i<dl; i++) x[i+2] = 0;
     590      240807 :   if (db)
     591             :   {
     592      240779 :     ulong dc=BITS_IN_LONG-db;
     593      240779 :     ulong r=0;
     594      483916 :     for(i=2; i<ly; i++)
     595             :     {
     596      243137 :       x[i+dl] = (((ulong)y[i])<<db)|r;
     597      243137 :       r = ((ulong)y[i])>>dc;
     598             :     }
     599      240779 :     x[i+dl] = r;
     600             :   }
     601             :   else
     602          42 :     for(i=2; i<ly; i++)
     603          14 :       x[i+dl] = y[i];
     604      240807 :   return F2x_renormalize(x,lx);
     605             : }
     606             : 
     607             : GEN
     608      241402 : F2x_shift(GEN y, long d)
     609             : {
     610      241402 :   return d<0 ? F2x_shiftneg(y,-d): F2x_shiftpos(y,d);
     611             : }
     612             : 
     613             : GEN
     614        1001 : F2x_get_red(GEN T)
     615             : {
     616        1001 :   return T;
     617             : }
     618             : 
     619             : /* separate from F2x_divrem for maximal speed. */
     620             : GEN
     621    47702185 : F2x_rem(GEN x, GEN y)
     622             : {
     623             :   long dx,dy;
     624    47702185 :   long lx=lg(x);
     625    47702185 :   dy = F2x_degree(y); if (!dy) return pol0_F2x(x[1]);
     626    45697592 :   dx = F2x_degree_lg(x,lx);
     627    45325385 :   x  = F2x_copy(x);
     628   196535443 :   while (dx>=dy)
     629             :   {
     630   105237579 :     F2x_addshiftip(x,y,dx-dy);
     631   104717907 :     while (lx>2 && x[lx-1]==0) lx--;
     632   104717907 :     dx = F2x_degree_lg(x,lx);
     633             :   }
     634    45455352 :   return F2x_renormalize(x, lx);
     635             : }
     636             : 
     637             : GEN
     638    13136803 : F2x_divrem(GEN x, GEN y, GEN *pr)
     639             : {
     640    13136803 :   long dx, dy, dz, lx = lg(x), vs = x[1];
     641             :   GEN z;
     642             : 
     643    13136803 :   dy = F2x_degree(y);
     644    13137800 :   if (dy<0) pari_err_INV("F2x_divrem",y);
     645    13149715 :   if (pr == ONLY_REM) return F2x_rem(x, y);
     646    13149715 :   if (!dy)
     647             :   {
     648     3367389 :     z = F2x_copy(x);
     649     3370952 :     if (pr && pr != ONLY_DIVIDES) *pr = pol0_F2x(vs);
     650     3370952 :     return z;
     651             :   }
     652     9782326 :   dx = F2x_degree_lg(x,lx);
     653     9781637 :   dz = dx-dy;
     654     9781637 :   if (dz < 0)
     655             :   {
     656          14 :     if (pr == ONLY_DIVIDES) return dx < 0? F2x_copy(x): NULL;
     657          14 :     z = pol0_F2x(vs);
     658          14 :     if (pr) *pr = F2x_copy(x);
     659          14 :     return z;
     660             :   }
     661     9781623 :   z = zero_zv(lg(x)-lg(y)+2); z[1] = vs;
     662     9782844 :   x = F2x_copy(x);
     663    41985968 :   while (dx>=dy)
     664             :   {
     665    22422321 :     F2x_set(z,dx-dy);
     666    22401985 :     F2x_addshiftip(x,y,dx-dy);
     667    22359395 :     while (lx>2 && x[lx-1]==0) lx--;
     668    22359395 :     dx = F2x_degree_lg(x,lx);
     669             :   }
     670     9780940 :   z = F2x_renormalize(z, lg(z));
     671     9782052 :   if (!pr) { cgiv(x); return z; }
     672     9168068 :   x = F2x_renormalize(x, lx);
     673     9168058 :   if (pr == ONLY_DIVIDES) {
     674           0 :     if (lg(x) == 2) { cgiv(x); return z; }
     675           0 :     set_avma((pari_sp)(z + lg(z))); return NULL;
     676             :   }
     677     9168058 :   *pr = x; return z;
     678             : }
     679             : 
     680             : long
     681       11774 : F2x_valrem(GEN x, GEN *Z)
     682             : {
     683       11774 :   long v, v2, i, l=lg(x);
     684             :   GEN y;
     685       11774 :   if (l==2) { *Z = F2x_copy(x); return LONG_MAX; }
     686       11774 :   for (i=2; i<l && x[i]==0; i++) /*empty*/;
     687       11774 :   v = i-2;
     688       11774 :   v2 = (i < l)? vals(x[i]): 0;
     689       11775 :   if (v+v2 == 0) { *Z = x; return 0; }
     690        3494 :   l -= i-2;
     691        3494 :   y = cgetg(l, t_VECSMALL); y[1] = x[1];
     692        3494 :   if (v2 == 0)
     693           0 :     for (i=2; i<l; i++) y[i] = x[i+v];
     694        3494 :   else if (l == 3)
     695        3476 :     y[2] = ((ulong)x[2+v]) >> v2;
     696             :   else
     697             :   {
     698          18 :     const ulong sh = BITS_IN_LONG - v2;
     699          18 :     ulong r = x[2+v];
     700          36 :     for (i=3; i<l; i++)
     701             :     {
     702          18 :       y[i-1] = (x[i+v] << sh) | (r >> v2);
     703          18 :       r = x[i+v];
     704             :     }
     705          18 :     y[l-1] = r >> v2;
     706          18 :     (void)F2x_renormalize(y,l);
     707             :   }
     708        3494 :   *Z = y; return (v << TWOPOTBITS_IN_LONG) + v2;
     709             : }
     710             : 
     711             : GEN
     712           0 : F2x_deflate(GEN x, long d)
     713             : {
     714             :   GEN y;
     715           0 :   long i,id, dy, dx = F2x_degree(x);
     716           0 :   if (d <= 1) return F2x_copy(x);
     717           0 :   if (dx < 0) return F2x_copy(x);
     718           0 :   dy = dx/d; /* dy+1 coefficients + 1 extra word for variable */
     719           0 :   y = zero_zv(nbits2lg(dy+1)-1); y[1] = x[1];
     720           0 :   for (i=id=0; i<=dy; i++,id+=d)
     721           0 :     if (F2x_coeff(x,id)) F2x_set(y, i);
     722           0 :   return y;
     723             : }
     724             : 
     725             : /* write p(X) = e(X^2) + Xo(X^2), shallow function */
     726             : void
     727       49504 : F2x_even_odd(GEN p, GEN *pe, GEN *po)
     728             : {
     729       49504 :   long n = F2x_degree(p), n0, n1, i;
     730             :   GEN p0, p1;
     731             : 
     732       49506 :   if (n <= 0) { *pe = F2x_copy(p); *po = pol0_F2x(p[1]); return; }
     733             : 
     734       45859 :   n0 = (n>>1)+1; n1 = n+1 - n0; /* n1 <= n0 <= n1+1 */
     735       45859 :   p0 = zero_zv(nbits2lg(n0+1)-1); p0[1] = p[1];
     736       45863 :   p1 = zero_zv(nbits2lg(n1+1)-1); p1[1] = p[1];
     737     1437466 :   for (i=0; i<n1; i++)
     738             :   {
     739     1391596 :     if (F2x_coeff(p,i<<1)) F2x_set(p0,i);
     740     1391120 :     if (F2x_coeff(p,1+(i<<1))) F2x_set(p1,i);
     741             :   }
     742       45870 :   if (n1 != n0 && F2x_coeff(p,i<<1)) F2x_set(p0,i);
     743       45870 :   *pe = F2x_renormalize(p0,lg(p0));
     744       45863 :   *po = F2x_renormalize(p1,lg(p1));
     745             : }
     746             : 
     747             : GEN
     748      859044 : F2x_deriv(GEN z)
     749             : {
     750      859044 :   const ulong mask = ULONG_MAX/3UL;
     751      859044 :   long i,l = lg(z);
     752      859044 :   GEN x = cgetg(l, t_VECSMALL); x[1] = z[1];
     753      859182 :   for (i=2; i<l; i++) x[i] = (((ulong)z[i])>>1)&mask;
     754      859182 :   return F2x_renormalize(x,l);
     755             : }
     756             : 
     757             : GEN
     758     2860473 : F2x_gcd(GEN a, GEN b)
     759             : {
     760     2860473 :   pari_sp av = avma;
     761     2860473 :   if (lg(b) > lg(a)) swap(a, b);
     762    24630696 :   while (lgpol(b))
     763             :   {
     764    18915945 :     GEN c = F2x_rem(a,b);
     765    18909750 :     a = b; b = c;
     766    18909750 :     if (gc_needed(av,2))
     767             :     {
     768           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2x_gcd (d = %ld)",F2x_degree(c));
     769           0 :       gerepileall(av,2, &a,&b);
     770             :     }
     771             :   }
     772     2854903 :   if (gc_needed(av,2)) a = gerepileuptoleaf(av, a);
     773     2854903 :   return a;
     774             : }
     775             : 
     776             : GEN
     777     1369547 : F2x_extgcd(GEN a, GEN b, GEN *ptu, GEN *ptv)
     778             : {
     779     1369547 :   pari_sp av=avma;
     780             :   GEN u,v,d,d1,v1;
     781     1369547 :   long vx = a[1];
     782     1369547 :   d = a; d1 = b;
     783     1369547 :   v = pol0_F2x(vx); v1 = pol1_F2x(vx);
     784    13268744 :   while (lgpol(d1))
     785             :   {
     786    10529648 :     GEN r, q = F2x_divrem(d,d1, &r);
     787    10529631 :     v = F2x_add(v,F2x_mul(q,v1));
     788    10529650 :     u=v; v=v1; v1=u;
     789    10529650 :     u=r; d=d1; d1=u;
     790    10529650 :     if (gc_needed(av,2))
     791             :     {
     792           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2x_extgcd (d = %ld)",F2x_degree(d));
     793           0 :       gerepileall(av,5, &d,&d1,&u,&v,&v1);
     794             :     }
     795             :   }
     796     1369547 :   if (ptu) *ptu = F2x_div(F2x_add(d, F2x_mul(b,v)), a);
     797     1369547 :   *ptv = v;
     798     1369547 :   if (gc_needed(av,2)) gerepileall(av,ptu?3:2,&d,ptv,ptu);
     799     1369547 :   return d;
     800             : }
     801             : 
     802             : static GEN
     803         486 : F2x_halfgcd_i(GEN a, GEN b)
     804             : {
     805         486 :   pari_sp av=avma;
     806             :   GEN u,u1,v,v1;
     807         486 :   long vx = a[1];
     808         486 :   long n = (F2x_degree(a)+1)>>1;
     809         486 :   u1 = v = pol0_F2x(vx);
     810         486 :   u = v1 = pol1_F2x(vx);
     811        8387 :   while (F2x_degree(b)>=n)
     812             :   {
     813        7415 :     GEN r, q = F2x_divrem(a,b, &r);
     814        7415 :     a = b; b = r; swap(u,u1); swap(v,v1);
     815        7415 :     u1 = F2x_add(u1, F2x_mul(u, q));
     816        7415 :     v1 = F2x_add(v1, F2x_mul(v, q));
     817        7415 :     if (gc_needed(av,2))
     818             :     {
     819           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2x_halfgcd (d = %ld)",F2x_degree(b));
     820           0 :       gerepileall(av,6, &a,&b,&u1,&v1,&u,&v);
     821             :     }
     822             :   }
     823         486 :   return gerepilecopy(av, mkmat2(mkcol2(u,u1), mkcol2(v,v1)));
     824             : }
     825             : 
     826             : GEN
     827         486 : F2x_halfgcd(GEN x, GEN y)
     828             : {
     829             :   pari_sp av;
     830             :   GEN M,q,r;
     831         486 :   if (F2x_degree(y)<F2x_degree(x)) return F2x_halfgcd_i(x,y);
     832         486 :   av = avma;
     833         486 :   q = F2x_divrem(y,x,&r);
     834         486 :   M = F2x_halfgcd_i(x,r);
     835         486 :   gcoeff(M,1,1) = F2x_add(gcoeff(M,1,1), F2x_mul(q, gcoeff(M,1,2)));
     836         486 :   gcoeff(M,2,1) = F2x_add(gcoeff(M,2,1), F2x_mul(q, gcoeff(M,2,2)));
     837         486 :   return gerepilecopy(av, M);
     838             : }
     839             : 
     840             : GEN
     841     8968998 : F2xq_mul(GEN x,GEN y,GEN pol)
     842             : {
     843     8968998 :   GEN z = F2x_mul(x,y);
     844     8969329 :   return F2x_rem(z,pol);
     845             : }
     846             : 
     847             : GEN
     848     7851724 : F2xq_sqr(GEN x,GEN pol)
     849             : {
     850     7851724 :   GEN z = F2x_sqr(x);
     851     7876250 :   return F2x_rem(z,pol);
     852             : }
     853             : 
     854             : GEN
     855     1369547 : F2xq_invsafe(GEN x, GEN T)
     856             : {
     857     1369547 :   GEN V, z = F2x_extgcd(T, x, NULL, &V);
     858     1369547 :   if (F2x_degree(z)) return NULL;
     859     1369477 :   return V;
     860             : }
     861             : 
     862             : GEN
     863     1369540 : F2xq_inv(GEN x,GEN T)
     864             : {
     865     1369540 :   pari_sp av=avma;
     866     1369540 :   GEN U = F2xq_invsafe(x, T);
     867     1369540 :   if (!U) pari_err_INV("F2xq_inv", F2x_to_ZX(x));
     868     1369470 :   return gerepileuptoleaf(av, U);
     869             : }
     870             : 
     871             : GEN
     872      576413 : F2xq_div(GEN x,GEN y,GEN T)
     873             : {
     874      576413 :   pari_sp av = avma;
     875      576413 :   return gerepileuptoleaf(av, F2xq_mul(x,F2xq_inv(y,T),T));
     876             : }
     877             : 
     878             : static GEN
     879      550597 : _F2xq_red(void *E, GEN x)
     880      550597 : { return F2x_rem(x, (GEN)E); }
     881             : static GEN
     882     1420695 : _F2xq_add(void *E, GEN x, GEN y)
     883     1420695 : { (void)E; return F2x_add(x,y); }
     884             : 
     885             : static GEN
     886     1803452 : _F2xq_cmul(void *E, GEN P, long a, GEN x)
     887             : {
     888     1803452 :   GEN pol = (GEN) E;
     889     1803452 :   return F2x_coeff(P,a) ? x: pol0_F2x(pol[1]);
     890             : }
     891             : static GEN
     892      856208 : _F2xq_sqr(void *E, GEN x)
     893      856208 : { return F2xq_sqr(x, (GEN) E); }
     894             : 
     895             : static GEN
     896     1550312 : _F2xq_mul(void *E, GEN x, GEN y)
     897     1550312 : { return F2xq_mul(x,y, (GEN) E); }
     898             : 
     899             : static GEN
     900      883225 : _F2xq_one(void *E)
     901             : {
     902      883225 :   GEN pol = (GEN) E;
     903      883225 :   return pol1_F2x(pol[1]);
     904             : }
     905             : static GEN
     906      260043 : _F2xq_zero(void *E)
     907             : {
     908      260043 :   GEN pol = (GEN) E;
     909      260043 :   return pol0_F2x(pol[1]);
     910             : }
     911             : 
     912             : GEN
     913      416655 : F2xq_pow(GEN x, GEN n, GEN pol)
     914             : {
     915      416655 :   pari_sp av=avma;
     916             :   GEN y;
     917             : 
     918      416655 :   if (!signe(n)) return pol1_F2x(x[1]);
     919      408934 :   if (is_pm1(n)) /* +/- 1 */
     920      210399 :     return (signe(n) < 0)? F2xq_inv(x,pol): F2x_copy(x);
     921             : 
     922      198535 :   if (signe(n) < 0) x = F2xq_inv(x,pol);
     923      198535 :   y = gen_pow(x, n, (void*)pol, &_F2xq_sqr, &_F2xq_mul);
     924      198535 :   return gerepileupto(av, y);
     925             : }
     926             : 
     927             : GEN
     928          49 : F2xq_powu(GEN x, ulong n, GEN pol)
     929             : {
     930          49 :   pari_sp av=avma;
     931             :   GEN y;
     932          49 :   switch(n)
     933             :   {
     934           0 :     case 0: return pol1_F2x(x[1]);
     935           7 :     case 1: return F2x_copy(x);
     936          14 :     case 2: return F2xq_sqr(x,pol);
     937             :   }
     938          28 :   y = gen_powu(x, n, (void*)pol, &_F2xq_sqr, &_F2xq_mul);
     939          28 :   return gerepileupto(av, y);
     940             : }
     941             : 
     942             : GEN
     943          14 : F2xq_pow_init(GEN x, GEN n, long k,  GEN T)
     944             : {
     945          14 :   return gen_pow_init(x, n, k, (void*)T, &_F2xq_sqr, &_F2xq_mul);
     946             : }
     947             : 
     948             : GEN
     949        5247 : F2xq_pow_table(GEN R, GEN n, GEN T)
     950             : {
     951        5247 :   return gen_pow_table(R, n, (void*)T, &_F2xq_one, &_F2xq_mul);
     952             : }
     953             : 
     954             : /* generates the list of powers of x of degree 0,1,2,...,l*/
     955             : GEN
     956      352837 : F2xq_powers(GEN x, long l, GEN T)
     957             : {
     958      352837 :   int use_sqr = 2*F2x_degree(x) >= F2x_degree(T);
     959      352837 :   return gen_powers(x, l, use_sqr, (void*)T, &_F2xq_sqr, &_F2xq_mul, &_F2xq_one);
     960             : }
     961             : 
     962             : GEN
     963      223197 : F2xq_matrix_pow(GEN y, long n, long m, GEN P)
     964             : {
     965      223197 :   return F2xV_to_F2m(F2xq_powers(y,m-1,P),n);
     966             : }
     967             : 
     968             : GEN
     969      376162 : F2x_Frobenius(GEN T)
     970             : {
     971      376162 :   return F2xq_sqr(polx_F2x(T[1]), T);
     972             : }
     973             : 
     974             : GEN
     975      223197 : F2x_matFrobenius(GEN T)
     976             : {
     977      223197 :   long n = F2x_degree(T);
     978      223197 :   return F2xq_matrix_pow(F2x_Frobenius(T), n, n, T);
     979             : }
     980             : 
     981             : static struct bb_algebra F2xq_algebra = { _F2xq_red, _F2xq_add, _F2xq_add,
     982             :               _F2xq_mul, _F2xq_sqr, _F2xq_one, _F2xq_zero};
     983             : 
     984             : GEN
     985      610400 : F2x_F2xqV_eval(GEN Q, GEN x, GEN T)
     986             : {
     987      610400 :   long d = F2x_degree(Q);
     988      610400 :   return gen_bkeval_powers(Q,d,x,(void*)T,&F2xq_algebra,_F2xq_cmul);
     989             : }
     990             : 
     991             : GEN
     992       40772 : F2x_F2xq_eval(GEN Q, GEN x, GEN T)
     993             : {
     994       40772 :   long d = F2x_degree(Q);
     995       40771 :   int use_sqr = 2*F2x_degree(x) >= F2x_degree(T);
     996       40771 :   return gen_bkeval(Q, d, x, use_sqr, (void*)T, &F2xq_algebra, _F2xq_cmul);
     997             : }
     998             : 
     999             : static GEN
    1000       26882 : F2xq_autpow_sqr(void * T, GEN x) { return F2x_F2xq_eval(x, x, (GEN) T); }
    1001             : 
    1002             : static GEN
    1003       13190 : F2xq_autpow_mul(void * T, GEN x, GEN y) { return F2x_F2xq_eval(x, y, (GEN) T); }
    1004             : 
    1005             : GEN
    1006       18156 : F2xq_autpow(GEN x, long n, GEN T)
    1007             : {
    1008       18156 :   if (n==0) return F2x_rem(polx_F2x(x[1]), T);
    1009       18156 :   if (n==1) return F2x_rem(x, T);
    1010       18156 :   return gen_powu(x,n,(void*)T,F2xq_autpow_sqr,F2xq_autpow_mul);
    1011             : }
    1012             : 
    1013             : ulong
    1014      460528 : F2xq_trace(GEN x, GEN T)
    1015             : {
    1016      460528 :   pari_sp av = avma;
    1017      460528 :   long n = F2x_degree(T)-1;
    1018      460528 :   GEN z = F2x_mul(x, F2x_deriv(T));
    1019      460528 :   z = F2x_rem(z, T);
    1020      460528 :   return gc_ulong(av, F2x_degree(z) < n ? 0 : 1);
    1021             : }
    1022             : 
    1023             : GEN
    1024           7 : F2xq_conjvec(GEN x, GEN T)
    1025             : {
    1026           7 :   long i, l = F2x_degree(T);
    1027           7 :   GEN z = cgetg(l,t_COL);
    1028           7 :   gel(z,1) = F2x_copy(x);
    1029           7 :   for (i=2; i<l; i++) gel(z,i) = F2xq_sqr(gel(z,i-1), T);
    1030           7 :   return z;
    1031             : }
    1032             : 
    1033             : static GEN
    1034      373318 : _F2xq_pow(void *data, GEN x, GEN n)
    1035             : {
    1036      373318 :   GEN pol = (GEN) data;
    1037      373318 :   return F2xq_pow(x,n, pol);
    1038             : }
    1039             : 
    1040             : static GEN
    1041        9247 : _F2xq_rand(void *data)
    1042             : {
    1043        9247 :   pari_sp av=avma;
    1044        9247 :   GEN pol = (GEN) data;
    1045        9247 :   long d = F2x_degree(pol);
    1046             :   GEN z;
    1047             :   do
    1048             :   {
    1049        9415 :     set_avma(av);
    1050        9415 :     z = random_F2x(d,pol[1]);
    1051        9415 :   } while (lgpol(z)==0);
    1052        9247 :   return z;
    1053             : }
    1054             : 
    1055             : static GEN F2xq_easylog(void* E, GEN a, GEN g, GEN ord);
    1056             : 
    1057             : static const struct bb_group F2xq_star={_F2xq_mul,_F2xq_pow,_F2xq_rand,hash_GEN,F2x_equal,F2x_equal1,F2xq_easylog};
    1058             : 
    1059             : GEN
    1060         378 : F2xq_order(GEN a, GEN ord, GEN T)
    1061             : {
    1062         378 :   return gen_order(a,ord,(void*)T,&F2xq_star);
    1063             : }
    1064             : 
    1065             : static long
    1066      260960 : F2x_is_smooth_squarefree(GEN f, long r)
    1067             : {
    1068      260960 :   pari_sp av = avma;
    1069             :   long i;
    1070      260960 :   GEN sx = polx_F2x(f[1]), a = sx;
    1071     2381388 :   for(i=1;  ;i++)
    1072             :   {
    1073     4501667 :     a = F2xq_sqr(F2x_rem(a,f),f);
    1074     2357597 :     if (F2x_equal(a, F2x_rem(sx,f))) return gc_long(av,1);
    1075     2270403 :     if (i==r) return gc_long(av,0);
    1076     2106046 :     f = F2x_div(f, F2x_gcd(F2x_add(a,sx),f));
    1077             :   }
    1078             : }
    1079             : 
    1080             : static long
    1081      224080 : F2x_is_smooth(GEN g, long r)
    1082             : {
    1083      224080 :   if (lgpol(g)==0) return 0;
    1084             :   while (1)
    1085       37080 :   {
    1086      261117 :     GEN f = F2x_gcd(g, F2x_deriv(g));
    1087      260978 :     if (!F2x_is_smooth_squarefree(F2x_div(g, f), r))
    1088      164369 :       return 0;
    1089       96724 :     if (F2x_degree(f)==0) return 1;
    1090       37073 :     g = F2x_issquare(f) ? F2x_sqrt(f): f;
    1091             :   }
    1092             : }
    1093             : 
    1094             : static GEN
    1095       15186 : F2x_factorel(GEN h)
    1096             : {
    1097       15186 :   GEN F = F2x_factor(h);
    1098       15188 :   GEN F1 = gel(F, 1), F2 = gel(F, 2);
    1099       15188 :   long i, l1 = lg(F1)-1;
    1100       15188 :   GEN p2 = cgetg(l1+1, t_VECSMALL);
    1101       15188 :   GEN e2 = cgetg(l1+1, t_VECSMALL);
    1102       71144 :   for (i = 1; i <= l1; ++i)
    1103             :   {
    1104       55957 :     p2[i] = mael(F1, i, 2);
    1105       55957 :     e2[i] = F2[i];
    1106             :   }
    1107       15187 :   return mkmat2(p2, e2);
    1108             : }
    1109             : 
    1110             : static GEN
    1111       25834 : mkF2(ulong x, long v) { return mkvecsmall2(v, x); }
    1112             : 
    1113             : static GEN F2xq_log_Coppersmith_d(GEN W, GEN g, long r, long n, GEN T, GEN mo);
    1114             : 
    1115             : static GEN
    1116          45 : F2xq_log_from_rel(GEN W, GEN rel, long r, long n, GEN T, GEN m)
    1117             : {
    1118          45 :   pari_sp av = avma;
    1119          45 :   GEN F = gel(rel,1), E = gel(rel,2), o = gen_0;
    1120          45 :   long i, l = lg(F);
    1121         412 :   for(i=1; i<l; i++)
    1122             :   {
    1123         367 :     GEN R = gel(W, F[i]);
    1124         367 :     if (signe(R)==0) /* Already failed */
    1125           0 :       return NULL;
    1126         367 :     else if (signe(R)<0) /* Not yet tested */
    1127             :     {
    1128           0 :       setsigne(gel(W,F[i]),0);
    1129           0 :       R = F2xq_log_Coppersmith_d(W, mkF2(F[i],T[1]), r, n, T, m);
    1130           0 :       if (!R) return NULL;
    1131             :     }
    1132         367 :     o = Fp_add(o, mulis(R, E[i]), m);
    1133             :   }
    1134          45 :   return gerepileuptoint(av, o);
    1135             : }
    1136             : 
    1137             : static GEN
    1138          57 : F2xq_log_Coppersmith_d(GEN W, GEN g, long r, long n, GEN T, GEN mo)
    1139             : {
    1140          57 :   pari_sp av = avma, av2;
    1141          57 :   long dg = F2x_degree(g), k = r-1, m = maxss((dg-k)/2,0);
    1142          57 :   long i, j, l = dg-m, N;
    1143          57 :   GEN v = cgetg(k+m+1,t_MAT);
    1144          57 :   long dT = F2x_degree(T);
    1145          57 :   long h = dT>>n, d = dT-(h<<n);
    1146          57 :   GEN R = F2x_add(F2x_shift(pol1_F2x(T[1]), dT), T);
    1147          57 :   GEN z = F2x_rem(F2x_shift(pol1_F2x(T[1]),h), g);
    1148         717 :   for(i=1; i<=k+m; i++)
    1149             :   {
    1150         660 :     gel(v,i) = F2x_to_F2v(F2x_shift(z,-l),m);
    1151         660 :     z = F2x_rem(F2x_shift(z,1),g);
    1152             :   }
    1153          57 :   v = F2m_ker(v);
    1154         627 :   for(i=1; i<=k; i++)
    1155         570 :     gel(v,i) = F2v_to_F2x(gel(v,i),T[1]);
    1156          57 :   N = 1<<k;
    1157          57 :   av2 = avma;
    1158       16609 :   for (i=1; i<N; i++)
    1159             :   {
    1160             :     GEN p,q,qh,a,b;
    1161       16597 :     set_avma(av2);
    1162       16597 :     q = pol0_F2x(T[1]);
    1163      182567 :     for(j=0; j<k; j++)
    1164      165970 :       if (i&(1UL<<j))
    1165       76105 :         q = F2x_add(q, gel(v,j+1));
    1166       16597 :     qh= F2x_shift(q,h);
    1167       16597 :     p = F2x_rem(qh,g);
    1168       16597 :     b = F2x_add(F2x_mul(R, F2x_pow2n(q, n)), F2x_shift(F2x_pow2n(p, n), d));
    1169       16597 :     if (lgpol(b)==0 || !F2x_is_smooth(b, r)) continue;
    1170          69 :     a = F2x_div(F2x_add(qh,p),g);
    1171          69 :     if (F2x_degree(F2x_gcd(a,q)) &&  F2x_degree(F2x_gcd(a,p))) continue;
    1172          57 :     if (!(lgpol(a)==0 || !F2x_is_smooth(a, r)))
    1173             :     {
    1174          45 :       GEN F = F2x_factorel(b);
    1175          45 :       GEN G = F2x_factorel(a);
    1176          45 :       GEN FG = vecsmall_concat(vecsmall_append(gel(F, 1), 2), gel(G, 1));
    1177          90 :       GEN E  = vecsmall_concat(vecsmall_append(gel(F, 2), -d),
    1178          90 :                                zv_z_mul(gel(G, 2),-(1L<<n)));
    1179          45 :       GEN R  = famatsmall_reduce(mkmat2(FG, E));
    1180          45 :       GEN l  = F2xq_log_from_rel(W, R, r, n, T, mo);
    1181          45 :       if (!l) continue;
    1182          45 :       l = Fp_div(l,int2n(n),mo);
    1183          45 :       if (dg <= r)
    1184             :       {
    1185           7 :         affii(l,gel(W,g[2]));
    1186           7 :         if (DEBUGLEVEL>1) err_printf("Found %lu\n", g[2]);
    1187             :       }
    1188          45 :       return gerepileuptoint(av, l);
    1189             :     }
    1190             :   }
    1191          12 :   return gc_NULL(av);
    1192             : }
    1193             : 
    1194             : static GEN
    1195          52 : F2xq_log_find_rel(GEN b, long r, GEN T, GEN *g, ulong *e)
    1196             : {
    1197          52 :   pari_sp av = avma;
    1198             :   while (1)
    1199         434 :   {
    1200             :     GEN M;
    1201         486 :     *g = F2xq_mul(*g, b, T); (*e)++;
    1202         486 :     M = F2x_halfgcd(*g,T);
    1203         486 :     if (F2x_is_smooth(gcoeff(M,1,1), r))
    1204             :     {
    1205         261 :       GEN z = F2x_add(F2x_mul(gcoeff(M,1,1),*g), F2x_mul(gcoeff(M,1,2),T));
    1206         261 :       if (F2x_is_smooth(z, r))
    1207             :       {
    1208          52 :         GEN F = F2x_factorel(z);
    1209          52 :         GEN G = F2x_factorel(gcoeff(M,1,1));
    1210         104 :         GEN rel = mkmat2(vecsmall_concat(gel(F, 1),gel(G, 1)),
    1211         104 :                          vecsmall_concat(gel(F, 2),zv_neg(gel(G, 2))));
    1212          52 :         gerepileall(av, 2, g, &rel);
    1213         104 :         return rel;
    1214             :       }
    1215             :     }
    1216         434 :     if (gc_needed(av,2))
    1217             :     {
    1218           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2xq_log_find_rel");
    1219           0 :       *g = gerepileuptoleaf(av, *g);
    1220             :     }
    1221             :   }
    1222             : }
    1223             : 
    1224             : static GEN
    1225          28 : F2xq_log_Coppersmith_rec(GEN W, long r2, GEN a, long r, long n, GEN T, GEN m)
    1226             : {
    1227          28 :   GEN b = polx_F2x(T[1]);
    1228          28 :   ulong AV = 0;
    1229          28 :   GEN g = a, bad = pol0_F2x(T[1]);
    1230             :   pari_timer ti;
    1231             :   while(1)
    1232          24 :   {
    1233             :     long i, l;
    1234             :     GEN V, F, E, Ao;
    1235          52 :     timer_start(&ti);
    1236          52 :     V = F2xq_log_find_rel(b, r2, T, &g, &AV);
    1237          52 :     if (DEBUGLEVEL>1) timer_printf(&ti,"%ld-smooth element",r2);
    1238          52 :     F = gel(V,1); E = gel(V,2);
    1239          52 :     l = lg(F);
    1240          52 :     Ao = gen_0;
    1241         333 :     for(i=1; i<l; i++)
    1242             :     {
    1243         305 :       GEN Fi = mkF2(F[i], T[1]);
    1244             :       GEN R;
    1245         305 :       if (F2x_degree(Fi) <= r)
    1246             :       {
    1247         243 :         if (signe(gel(W,F[i]))==0)
    1248           0 :           break;
    1249         243 :         else if (signe(gel(W,F[i]))<0)
    1250             :         {
    1251           7 :           setsigne(gel(W,F[i]),0);
    1252           7 :           R = F2xq_log_Coppersmith_d(W,Fi,r,n,T,m);
    1253             :         } else
    1254         236 :           R = gel(W,F[i]);
    1255             :       }
    1256             :       else
    1257             :       {
    1258          62 :         if (F2x_equal(Fi,bad)) break;
    1259          50 :         R = F2xq_log_Coppersmith_d(W,Fi,r,n,T,m);
    1260          50 :         if (!R) bad = Fi;
    1261             :       }
    1262         293 :       if (!R) break;
    1263         281 :       Ao = Fp_add(Ao, mulis(R, E[i]), m);
    1264             :     }
    1265          80 :     if (i==l) return subiu(Ao,AV);
    1266             :   }
    1267             : }
    1268             : 
    1269             : /* Coppersmith:
    1270             :  T*X^e = X^(h*2^n)-R
    1271             :  (u*x^h + v)^(2^n) = u^(2^n)*X^(h*2^n)+v^(2^n)
    1272             :  (u*x^h + v)^(2^n) = u^(2^n)*R+v^(2^n)
    1273             : */
    1274             : 
    1275             : static GEN
    1276      155003 : rel_Coppersmith(GEN u, GEN v, long h, GEN R, long r, long n, long d)
    1277             : {
    1278             :   GEN b, F, G, M;
    1279      155003 :   GEN a = F2x_add(F2x_shift(u, h), v);
    1280      154995 :   if (!F2x_is_smooth(a, r)) return NULL;
    1281       51783 :   b = F2x_add(F2x_mul(R, F2x_pow2n(u, n)), F2x_shift(F2x_pow2n(v, n),d));
    1282       51787 :   if (!F2x_is_smooth(b, r)) return NULL;
    1283        7496 :   F = F2x_factorel(a);
    1284        7497 :   G = F2x_factorel(b);
    1285       22491 :   M = mkmat2(vecsmall_concat(gel(F, 1), vecsmall_append(gel(G, 1), 2)),
    1286       22491 :              vecsmall_concat(zv_z_mul(gel(F, 2),1UL<<n), vecsmall_append(zv_neg(gel(G, 2)),d)));
    1287        7496 :   return famatsmall_reduce(M);
    1288             : }
    1289             : 
    1290             : GEN
    1291        2119 : F2xq_log_Coppersmith_worker(GEN u, long i, GEN V, GEN R)
    1292             : {
    1293        2119 :   long r = V[1], h = V[2], n = V[3], d = V[4];
    1294        2119 :   pari_sp ltop = avma;
    1295        2119 :   GEN v = mkF2(0,u[1]);
    1296        2119 :   GEN L = cgetg(2*i+1, t_VEC);
    1297        2128 :   pari_sp av = avma;
    1298             :   long j;
    1299        2128 :   long nbtest=0, rel = 1;
    1300      155670 :   for(j=1; j<=i; j++)
    1301             :   {
    1302      153548 :     v[2] = j;
    1303      153548 :     set_avma(av);
    1304      153538 :     if (F2x_degree(F2x_gcd(u,v))==0)
    1305             :     {
    1306       77538 :       GEN z = rel_Coppersmith(u, v, h, R, r, n, d);
    1307       77553 :       nbtest++;
    1308       77553 :       if (z) { gel(L, rel++) = z; av = avma; }
    1309       77553 :       if (i==j) continue;
    1310       77539 :       z = rel_Coppersmith(v, u, h, R, r, n, d);
    1311       77527 :       nbtest++;
    1312       77527 :       if (z) { gel(L, rel++) = z; av = avma; }
    1313             :     }
    1314             :   }
    1315        2122 :   setlg(L,rel);
    1316        2122 :   return gerepilecopy(ltop, mkvec2(stoi(nbtest), L));
    1317             : }
    1318             : 
    1319             : static GEN
    1320          14 : F2xq_log_Coppersmith(long nbrel, long r, long n, GEN T)
    1321             : {
    1322          14 :   long dT = F2x_degree(T);
    1323          14 :   long h = dT>>n, d = dT-(h<<n);
    1324          14 :   GEN R = F2x_add(F2x_shift(pol1_F2x(T[1]), dT), T);
    1325          14 :   GEN u = mkF2(0,T[1]);
    1326          14 :   long rel = 1, nbtest = 0;
    1327          14 :   GEN M = cgetg(nbrel+1, t_VEC);
    1328          14 :   long i = 0;
    1329          14 :   GEN worker = snm_closure(is_entry("_F2xq_log_Coppersmith_worker"),
    1330             :                mkvec2(mkvecsmall4(r, h, n, d), R));
    1331             :   struct pari_mt pt;
    1332          14 :   long running, pending = 0, stop=0;
    1333          14 :   mt_queue_start(&pt, worker);
    1334          14 :   if (DEBUGLEVEL) err_printf("Coppersmith (R = %ld): ",F2x_degree(R));
    1335        2212 :   while ((running = !stop) || pending)
    1336             :   {
    1337             :     GEN L, done;
    1338             :     long j, l;
    1339        2184 :     u[2] = i;
    1340        2184 :     mt_queue_submit(&pt, 0, running ? mkvec2(u, stoi(i)): NULL);
    1341        2184 :     done = mt_queue_get(&pt, NULL, &pending);
    1342        2184 :     if (!done) continue;
    1343        2122 :     L = gel(done, 2); nbtest += itos(gel(done,1));
    1344        2122 :     l = lg(L);
    1345        2122 :     if (l > 1)
    1346             :     {
    1347        9156 :       for (j=1; j<l; j++)
    1348             :       {
    1349        7277 :         if (rel>nbrel) break;
    1350        7210 :         gel(M,rel++) = gel(L,j);
    1351        7210 :         if (DEBUGLEVEL && (rel&511UL)==0)
    1352           0 :           err_printf("%ld%%[%ld] ",rel*100/nbrel,i);
    1353             :       }
    1354             :     }
    1355        2122 :     if (rel>nbrel) stop=1;
    1356        2122 :     i++;
    1357             :   }
    1358          14 :   mt_queue_end(&pt);
    1359          14 :   if (DEBUGLEVEL) err_printf(": %ld tests\n", nbtest);
    1360          14 :   return M;
    1361             : }
    1362             : 
    1363             : static GEN
    1364          14 : smallirred_F2x(ulong n, long sv)
    1365             : {
    1366          14 :   GEN a = zero_zv(nbits2lg(n+1)-1);
    1367          14 :   a[1] = sv; F2x_set(a,n); a[2]++;
    1368          14 :   while (!F2x_is_irred(a)) a[2]+=2;
    1369          14 :   return a;
    1370             : }
    1371             : 
    1372             : static GEN
    1373          14 : check_kernel(long N, GEN M, long nbi, GEN T, GEN m)
    1374             : {
    1375          14 :   pari_sp av = avma;
    1376          14 :   GEN K = FpMs_leftkernel_elt(M, N, m);
    1377          14 :   long i, f=0, tbs;
    1378          14 :   long l = lg(K), lm = lgefint(m);
    1379          14 :   GEN idx = diviiexact(int2um1(F2x_degree(T)),m);
    1380          14 :   GEN g = F2xq_pow(polx_F2x(T[1]), idx, T);
    1381             :   GEN tab;
    1382             :   pari_timer ti;
    1383          14 :   if (DEBUGLEVEL) timer_start(&ti);
    1384          14 :   K = FpC_Fp_mul(K, Fp_inv(gel(K,2), m), m);
    1385          14 :   tbs = maxss(1, expu(nbi/expi(m)));
    1386          14 :   tab = F2xq_pow_init(g, int2n(F2x_degree(T)), tbs, T);
    1387       57344 :   for(i=1; i<l; i++)
    1388             :   {
    1389       57330 :     GEN k = gel(K,i);
    1390       62577 :     if (signe(k)==0 || !F2x_equal(F2xq_pow_table(tab, k, T),
    1391        5247 :                                   F2xq_pow(mkF2(i,T[1]), idx, T)))
    1392       52083 :       gel(K,i) = cgetineg(lm);
    1393             :     else
    1394        5247 :       f++;
    1395             :   }
    1396          14 :   if (DEBUGLEVEL) timer_printf(&ti,"found %ld/%ld logs", f, nbi);
    1397          14 :   return gerepileupto(av, K);
    1398             : }
    1399             : 
    1400             : static GEN
    1401          14 : F2xq_log_index(GEN a0, GEN b0, GEN m, GEN T0)
    1402             : {
    1403          14 :   pari_sp av = avma;
    1404          14 :   GEN  M, S, a, b, Ao=NULL, Bo=NULL, W, e;
    1405             :   pari_timer ti;
    1406          14 :   long n = F2x_degree(T0), r = (long) (sqrt((double) 2*n))-(n>100);
    1407          14 :   GEN T = smallirred_F2x(n,T0[1]);
    1408          14 :   long d = 2, r2 = 3*r/2, d2 = 2;
    1409          14 :   long N = (1UL<<(r+1))-1UL;
    1410          14 :   long nbi = itos(ffsumnbirred(gen_2, r)), nbrel=nbi*5/4;
    1411          14 :   if (DEBUGLEVEL)
    1412             :   {
    1413           0 :     err_printf("F2xq_log: Parameters r=%ld r2=%ld\n", r,r2);
    1414           0 :     err_printf("F2xq_log: Size FB=%ld rel. needed=%ld\n", nbi, nbrel);
    1415           0 :     timer_start(&ti);
    1416             :   }
    1417          14 :   S = Flx_to_F2x(Flx_ffisom(F2x_to_Flx(T0),F2x_to_Flx(T),2));
    1418          14 :   a = F2x_F2xq_eval(a0, S, T);
    1419          14 :   b = F2x_F2xq_eval(b0, S, T);
    1420          14 :   if (DEBUGLEVEL) timer_printf(&ti,"model change");
    1421          14 :   M = F2xq_log_Coppersmith(nbrel,r,d,T);
    1422          14 :   if(DEBUGLEVEL)
    1423           0 :     timer_printf(&ti,"relations");
    1424          14 :   W = check_kernel(N, M, nbi, T, m);
    1425          14 :   timer_start(&ti);
    1426          14 :   Ao = F2xq_log_Coppersmith_rec(W, r2, a, r, d2, T, m);
    1427          14 :   if (DEBUGLEVEL) timer_printf(&ti,"smooth element");
    1428          14 :   Bo = F2xq_log_Coppersmith_rec(W, r2, b, r, d2, T, m);
    1429          14 :   if (DEBUGLEVEL) timer_printf(&ti,"smooth generator");
    1430          14 :   e = Fp_div(Ao, Bo, m);
    1431          14 :   if (!F2x_equal(F2xq_pow(b0,e,T0),a0)) pari_err_BUG("F2xq_log");
    1432          14 :   return gerepileupto(av, e);
    1433             : }
    1434             : 
    1435             : static GEN
    1436       84726 : F2xq_easylog(void* E, GEN a, GEN g, GEN ord)
    1437             : {
    1438       84726 :   if (F2x_equal1(a)) return gen_0;
    1439       69555 :   if (F2x_equal(a,g)) return gen_1;
    1440       64223 :   if (typ(ord)!=t_INT) return NULL;
    1441       32605 :   if (expi(ord)<28) return NULL;
    1442          14 :   return F2xq_log_index(a,g,ord,(GEN)E);
    1443             : }
    1444             : 
    1445             : GEN
    1446       49532 : F2xq_log(GEN a, GEN g, GEN ord, GEN T)
    1447             : {
    1448       49532 :   GEN z, v = get_arith_ZZM(ord);
    1449       49532 :   ord = mkvec2(gel(v,1),ZM_famat_limit(gel(v,2),int2n(28)));
    1450       49532 :   z = gen_PH_log(a,g,ord,(void*)T,&F2xq_star);
    1451       49532 :   return z? z: cgetg(1,t_VEC);
    1452             : }
    1453             : 
    1454             : GEN
    1455      212534 : F2xq_Artin_Schreier(GEN a, GEN T)
    1456             : {
    1457      212534 :   pari_sp ltop=avma;
    1458      212534 :   long j,N = F2x_degree(T);
    1459      212534 :   GEN Q = F2x_matFrobenius(T);
    1460     1475558 :   for (j=1; j<=N; j++)
    1461     1263024 :     F2m_flip(Q,j,j);
    1462      212534 :   F2v_add_inplace(gel(Q,1),a);
    1463      212534 :   Q = F2m_ker_sp(Q,0);
    1464      212534 :   if (lg(Q)!=2) return NULL;
    1465      212534 :   Q = gel(Q,1);
    1466      212534 :   Q[1] = T[1];
    1467      212534 :   return gerepileuptoleaf(ltop, F2x_renormalize(Q, lg(Q)));
    1468             : }
    1469             : 
    1470             : GEN
    1471       49505 : F2xq_sqrt_fast(GEN c, GEN sqx, GEN T)
    1472             : {
    1473             :   GEN c0, c1;
    1474       49505 :   F2x_even_odd(c, &c0, &c1);
    1475       49515 :   return F2x_add(c0, F2xq_mul(c1, sqx, T));
    1476             : }
    1477             : 
    1478             : static int
    1479       18149 : F2x_is_x(GEN a) { return lg(a)==3 && a[2]==2; }
    1480             : 
    1481             : GEN
    1482       33045 : F2xq_sqrt(GEN a, GEN T)
    1483             : {
    1484       33045 :   pari_sp av = avma;
    1485       33045 :   long n = F2x_degree(T);
    1486             :   GEN sqx;
    1487       33045 :   if (n==1) return F2x_copy(a);
    1488       32968 :   if (n==2) return F2xq_sqr(a,T);
    1489       18149 :   sqx = F2xq_autpow(mkF2(4, T[1]), n-1, T);
    1490       18149 :   return gerepileuptoleaf(av, F2x_is_x(a)? sqx: F2xq_sqrt_fast(a,sqx,T));
    1491             : }
    1492             : 
    1493             : GEN
    1494        9233 : F2xq_sqrtn(GEN a, GEN n, GEN T, GEN *zeta)
    1495             : {
    1496        9233 :   if (!lgpol(a))
    1497             :   {
    1498           7 :     if (signe(n) < 0) pari_err_INV("F2xq_sqrtn",a);
    1499           0 :     if (zeta)
    1500           0 :       *zeta=pol1_F2x(T[1]);
    1501           0 :     return pol0_F2x(T[1]);
    1502             :   }
    1503        9226 :   return gen_Shanks_sqrtn(a,n,subiu(powuu(2,F2x_degree(T)),1),zeta,(void*)T,&F2xq_star);
    1504             : }
    1505             : 
    1506             : GEN
    1507         154 : gener_F2xq(GEN T, GEN *po)
    1508             : {
    1509         154 :   long i, j, vT = T[1], f = F2x_degree(T);
    1510         154 :   pari_sp av0 = avma, av;
    1511             :   GEN g, L2, o, q;
    1512             : 
    1513         154 :   if (f == 1) {
    1514          21 :     if (po) *po = mkvec2(gen_1, trivial_fact());
    1515          21 :     return pol1_F2x(vT);
    1516             :   }
    1517         133 :   q = int2um1(f);
    1518         133 :   o = factor_pn_1(gen_2,f);
    1519         133 :   L2 = leafcopy( gel(o, 1) );
    1520         385 :   for (i = j = 1; i < lg(L2); i++)
    1521             :   {
    1522         252 :     if (absequaliu(gel(L2,i),2)) continue;
    1523         252 :     gel(L2,j++) = diviiexact(q, gel(L2,i));
    1524             :   }
    1525         133 :   setlg(L2, j);
    1526         175 :   for (av = avma;; set_avma(av))
    1527             :   {
    1528         217 :     g = random_F2x(f, vT);
    1529         175 :     if (F2x_degree(g) < 1) continue;
    1530         427 :     for (i = 1; i < j; i++)
    1531             :     {
    1532         294 :       GEN a = F2xq_pow(g, gel(L2,i), T);
    1533         294 :       if (F2x_equal1(a)) break;
    1534             :     }
    1535         161 :     if (i == j) break;
    1536             :   }
    1537         133 :   if (!po) g = gerepilecopy(av0, g);
    1538             :   else {
    1539           0 :     *po = mkvec2(int2um1(f), o);
    1540           0 :     gerepileall(av0, 2, &g, po);
    1541             :   }
    1542         133 :   return g;
    1543             : }
    1544             : 
    1545             : static GEN
    1546         798 : _F2xq_neg(void *E, GEN x)
    1547         798 : { (void) E; return F2x_copy(x); }
    1548             : 
    1549             : static GEN
    1550       13748 : _F2xq_rmul(void *E, GEN x, GEN y)
    1551       13748 : { (void) E; return F2x_mul(x,y); }
    1552             : 
    1553             : static GEN
    1554         413 : _F2xq_inv(void *E, GEN x)
    1555         413 : { return F2xq_inv(x, (GEN) E); }
    1556             : 
    1557             : static int
    1558         973 : _F2xq_equal0(GEN x) { return lgpol(x)==0; }
    1559             : 
    1560             : static GEN
    1561         679 : _F2xq_s(void *E, long x)
    1562         679 : { GEN T = (GEN) E;
    1563         679 :   return odd(x)? pol1_F2x(T[1]): pol0_F2x(T[0]);
    1564             : }
    1565             : 
    1566             : static const struct bb_field F2xq_field={_F2xq_red,_F2xq_add,_F2xq_rmul,_F2xq_neg,
    1567             :                                          _F2xq_inv,_F2xq_equal0,_F2xq_s};
    1568             : 
    1569        1659 : const struct bb_field *get_F2xq_field(void **E, GEN T)
    1570             : {
    1571        1659 :   *E = (void *) T;
    1572        1659 :   return &F2xq_field;
    1573             : }
    1574             : 
    1575             : /***********************************************************************/
    1576             : /**                                                                   **/
    1577             : /**                             F2v                                   **/
    1578             : /**                                                                   **/
    1579             : /***********************************************************************/
    1580             : /* F2v objects are defined as follows:
    1581             :    An F2v is a t_VECSMALL:
    1582             :    v[0] = codeword
    1583             :    v[1] = number of components
    1584             :    x[2] = a_0...a_31 x[3] = a_32..a_63, etc.  on 32bit
    1585             :    x[2] = a_0...a_63 x[3] = a_64..a_127, etc. on 64bit
    1586             : 
    1587             :    where the a_i are bits.
    1588             : */
    1589             : 
    1590             : GEN
    1591      725472 : F2c_to_ZC(GEN x)
    1592             : {
    1593      725472 :   long l=x[1]+1;
    1594      725472 :   GEN  z = cgetg(l, t_COL);
    1595             :   long i,j,k;
    1596     1453817 :   for (i=2,k=1; i<lg(x); i++)
    1597     8460019 :     for (j=0; j<BITS_IN_LONG && k<l; j++,k++)
    1598     7731674 :       gel(z,k) = (x[i]&(1UL<<j))? gen_1: gen_0;
    1599      725472 :   return z;
    1600             : }
    1601             : GEN
    1602        1610 : F2c_to_mod(GEN x)
    1603             : {
    1604        1610 :   long l=x[1]+1;
    1605        1610 :   GEN  z = cgetg(l, t_COL);
    1606        1610 :   GEN _0 = mkintmod(gen_0,gen_2);
    1607        1610 :   GEN _1 = mkintmod(gen_1,gen_2);
    1608             :   long i,j,k;
    1609        8020 :   for (i=2,k=1; i<lg(x); i++)
    1610      287047 :     for (j=0; j<BITS_IN_LONG && k<l; j++,k++)
    1611      280637 :       gel(z,k) = (x[i]&(1UL<<j))? _1: _0;
    1612        1610 :   return z;
    1613             : }
    1614             : 
    1615             : /* x[a..b], a <= b */
    1616             : GEN
    1617          28 : F2v_slice(GEN x, long a, long b)
    1618             : {
    1619          28 :   long i,j,k, l = b-a+1;
    1620          28 :   GEN z = cgetg(nbits2lg(l), t_VECSMALL);
    1621          28 :   z[1] = l;
    1622          98 :   for(i=a,k=1,j=BITS_IN_LONG; i<=b; i++,j++)
    1623             :   {
    1624          70 :     if (j==BITS_IN_LONG) { j=0; z[++k]=0; }
    1625          70 :     if (F2v_coeff(x,i)) z[k] |= 1UL<<j;
    1626             :   }
    1627          28 :   return z;
    1628             : }
    1629             : /* x[a..b,], a <= b */
    1630             : GEN
    1631          14 : F2m_rowslice(GEN x, long a, long b)
    1632             : {
    1633             :   long i, l;
    1634          14 :   GEN y = cgetg_copy(x, &l);
    1635          14 :   for (i = 1; i < l; i++) gel(y,i) = F2v_slice(gel(x,i),a,b);
    1636          14 :   return y;
    1637             : }
    1638             : 
    1639             : GEN
    1640      167405 : F2m_to_ZM(GEN z)
    1641             : {
    1642      167405 :   long i, l = lg(z);
    1643      167405 :   GEN x = cgetg(l,t_MAT);
    1644      167405 :   for (i=1; i<l; i++) gel(x,i) = F2c_to_ZC(gel(z,i));
    1645      167405 :   return x;
    1646             : }
    1647             : GEN
    1648          84 : F2m_to_mod(GEN z)
    1649             : {
    1650          84 :   long i, l = lg(z);
    1651          84 :   GEN x = cgetg(l,t_MAT);
    1652          84 :   for (i=1; i<l; i++) gel(x,i) = F2c_to_mod(gel(z,i));
    1653          84 :   return x;
    1654             : }
    1655             : 
    1656             : GEN
    1657           0 : F2v_to_Flv(GEN x)
    1658             : {
    1659           0 :   long l=x[1]+1;
    1660           0 :   GEN  z=cgetg(l, t_VECSMALL);
    1661             :   long i,j,k;
    1662           0 :   for (i=2,k=1; i<lg(x); i++)
    1663           0 :     for (j=0; j<BITS_IN_LONG && k<l; j++,k++)
    1664           0 :       z[k] = (x[i]>>j)&1UL;
    1665           0 :   return z;
    1666             : }
    1667             : 
    1668             : GEN
    1669           0 : F2m_to_Flm(GEN z)
    1670             : {
    1671           0 :   long i, l = lg(z);
    1672           0 :   GEN x = cgetg(l,t_MAT);
    1673           0 :   for (i=1; i<l; i++) gel(x,i) = F2v_to_Flv(gel(z,i));
    1674           0 :   return x;
    1675             : }
    1676             : 
    1677             : GEN
    1678     2073823 : ZV_to_F2v(GEN x)
    1679             : {
    1680     2073823 :   long l = lg(x)-1;
    1681     2073823 :   GEN z = cgetg(nbits2lg(l), t_VECSMALL);
    1682             :   long i,j,k;
    1683     2073823 :   z[1] = l;
    1684    28931266 :   for(i=1,k=1,j=BITS_IN_LONG; i<=l; i++,j++)
    1685             :   {
    1686    26857443 :     if (j==BITS_IN_LONG) { j=0; z[++k]=0; }
    1687    26857443 :     if (mpodd(gel(x,i))) z[k] |= 1UL<<j;
    1688             :   }
    1689     2073823 :   return z;
    1690             : }
    1691             : 
    1692             : GEN
    1693        4788 : RgV_to_F2v(GEN x)
    1694             : {
    1695        4788 :   long l = lg(x)-1;
    1696        4788 :   GEN z = cgetg(nbits2lg(l), t_VECSMALL);
    1697             :   long i,j,k;
    1698        4788 :   z[1] = l;
    1699      846650 :   for(i=1,k=1,j=BITS_IN_LONG; i<=l; i++,j++)
    1700             :   {
    1701      841862 :     if (j==BITS_IN_LONG) { j=0; z[++k]=0; }
    1702      841862 :     if (Rg_to_F2(gel(x,i))) z[k] |= 1UL<<j;
    1703             :   }
    1704        4788 :   return z;
    1705             : }
    1706             : 
    1707             : GEN
    1708         595 : Flv_to_F2v(GEN x)
    1709             : {
    1710         595 :   long l = lg(x)-1;
    1711         595 :   GEN z = cgetg(nbits2lg(l), t_VECSMALL);
    1712             :   long i,j,k;
    1713         595 :   z[1] = l;
    1714        5096 :   for(i=1,k=1,j=BITS_IN_LONG; i<=l; i++,j++)
    1715             :   {
    1716        4501 :     if (j==BITS_IN_LONG) { j=0; z[++k]=0; }
    1717        4501 :     if (x[i]&1L) z[k] |= 1UL<<j;
    1718             :   }
    1719         595 :   return z;
    1720             : }
    1721             : 
    1722             : GEN
    1723      327760 : ZM_to_F2m(GEN x)
    1724      327760 : { pari_APPLY_same(ZV_to_F2v(gel(x,i))) }
    1725             : 
    1726             : GEN
    1727         238 : RgM_to_F2m(GEN x)
    1728         238 : { pari_APPLY_same(RgV_to_F2v(gel(x,i))) }
    1729             : 
    1730             : GEN
    1731           0 : Flm_to_F2m(GEN x)
    1732           0 : { pari_APPLY_same(Flv_to_F2v(gel(x,i))) }
    1733             : 
    1734             : GEN
    1735      344874 : const_F2v(long m)
    1736             : {
    1737      344874 :   long i, l = nbits2lg(m);
    1738      344874 :   GEN c = cgetg(l, t_VECSMALL);
    1739      344873 :   c[1] = m;
    1740      344873 :   for (i = 2; i < l; i++) uel(c,i) = -1UL;
    1741      344873 :   if (remsBIL(m)) uel(c,l-1) = (1UL<<remsBIL(m))-1UL;
    1742      344873 :   return c;
    1743             : }
    1744             : 
    1745             : /* Allow lg(y)<lg(x) */
    1746             : void
    1747    30998388 : F2v_add_inplace(GEN x, GEN y)
    1748             : {
    1749    30998388 :   long n = lg(y);
    1750    30998388 :   long r = (n-2)&7L, q = n-r, i;
    1751   116116368 :   for (i = 2; i < q; i += 8)
    1752             :   {
    1753    85117980 :     x[  i] ^= y[  i]; x[1+i] ^= y[1+i]; x[2+i] ^= y[2+i]; x[3+i] ^= y[3+i];
    1754    85117980 :     x[4+i] ^= y[4+i]; x[5+i] ^= y[5+i]; x[6+i] ^= y[6+i]; x[7+i] ^= y[7+i];
    1755             :   }
    1756    30998388 :   switch (r)
    1757             :   {
    1758    13855694 :     case 7: x[i] ^= y[i]; i++; case 6: x[i] ^= y[i]; i++;
    1759    17149843 :     case 5: x[i] ^= y[i]; i++; case 4: x[i] ^= y[i]; i++;
    1760    18794864 :     case 3: x[i] ^= y[i]; i++; case 2: x[i] ^= y[i]; i++;
    1761    25735821 :     case 1: x[i] ^= y[i]; i++;
    1762             :   }
    1763    30998388 : }
    1764             : 
    1765             : /***********************************************************************/
    1766             : /**                                                                   **/
    1767             : /**                               F2xV                                **/
    1768             : /**                                                                   **/
    1769             : /***********************************************************************/
    1770             : /* F2xV are t_VEC with F2x coefficients. */
    1771             : 
    1772             : GEN
    1773       16625 : FlxC_to_F2xC(GEN x)
    1774       16625 : { pari_APPLY_type(t_COL, Flx_to_F2x(gel(x,i))) }
    1775             : 
    1776             : GEN
    1777           0 : F2xC_to_FlxC(GEN x)
    1778           0 : { pari_APPLY_type(t_COL, F2x_to_Flx(gel(x,i))) }
    1779             : 
    1780             : GEN
    1781        3682 : F2xC_to_ZXC(GEN x)
    1782        3682 : { pari_APPLY_type(t_COL, F2x_to_ZX(gel(x,i))) }
    1783             : 
    1784             : GEN
    1785      223196 : F2xV_to_F2m(GEN x, long n)
    1786      223196 : { pari_APPLY_type(t_MAT, F2x_to_F2v(gel(x,i), n)) }
    1787             : 
    1788             : /***********************************************************************/
    1789             : /**                                                                   **/
    1790             : /**                             F2xX                                  **/
    1791             : /**                                                                   **/
    1792             : /***********************************************************************/
    1793             : 
    1794             : GEN
    1795     2437012 : F2xX_renormalize(GEN /*in place*/ x, long lx)
    1796     2437012 : { return FlxX_renormalize(x, lx); }
    1797             : 
    1798             : GEN
    1799      447496 : pol1_F2xX(long v, long sv) { return pol1_FlxX(v, sv); }
    1800             : 
    1801             : GEN
    1802         448 : polx_F2xX(long v, long sv) { return polx_FlxX(v, sv); }
    1803             : 
    1804             : long
    1805      207151 : F2xY_degreex(GEN b)
    1806             : {
    1807      207151 :   long deg = 0, i;
    1808      207151 :   if (!signe(b)) return -1;
    1809     1344028 :   for (i = 2; i < lg(b); ++i)
    1810     1136877 :     deg = maxss(deg, F2x_degree(gel(b, i)));
    1811      207151 :   return deg;
    1812             : }
    1813             : 
    1814             : GEN
    1815         553 : FlxX_to_F2xX(GEN B)
    1816             : {
    1817         553 :   long lb=lg(B);
    1818             :   long i;
    1819         553 :   GEN b=cgetg(lb,t_POL);
    1820         553 :   b[1]=evalsigne(1)|(((ulong)B[1])&VARNBITS);
    1821        3003 :   for (i=2; i<lb; i++)
    1822        2450 :     gel(b,i) = Flx_to_F2x(gel(B,i));
    1823         553 :   return F2xX_renormalize(b, lb);
    1824             : }
    1825             : 
    1826             : GEN
    1827        4501 : ZXX_to_F2xX(GEN B, long v)
    1828             : {
    1829        4501 :   long lb=lg(B);
    1830             :   long i;
    1831        4501 :   GEN b=cgetg(lb,t_POL);
    1832        4501 :   b[1]=evalsigne(1)|(((ulong)B[1])&VARNBITS);
    1833       21168 :   for (i=2; i<lb; i++)
    1834       16667 :     switch (typ(gel(B,i)))
    1835             :     {
    1836             :     case t_INT:
    1837        6846 :       gel(b,i) = Z_to_F2x(gel(B,i), v);
    1838        6846 :       break;
    1839             :     case t_POL:
    1840        9821 :       gel(b,i) = ZX_to_F2x(gel(B,i));
    1841        9821 :       break;
    1842             :     }
    1843        4501 :   return F2xX_renormalize(b, lb);
    1844             : }
    1845             : 
    1846             : GEN
    1847         945 : F2xX_to_ZXX(GEN B)
    1848             : {
    1849         945 :   long i, lb = lg(B);
    1850         945 :   GEN b = cgetg(lb,t_POL);
    1851        2891 :   for (i=2; i<lb; i++)
    1852             :   {
    1853        1946 :     GEN c = gel(B,i);
    1854        1946 :     gel(b,i) = lgpol(c) ?  F2x_equal1(c) ? gen_1 : F2x_to_ZX(c) : gen_0;
    1855             :   }
    1856         945 :   b[1] = B[1]; return b;
    1857             : }
    1858             : 
    1859             : GEN
    1860       80829 : F2xX_deriv(GEN z)
    1861             : {
    1862       80829 :   long i,l = lg(z)-1;
    1863             :   GEN x;
    1864       80829 :   if (l < 2) l = 2;
    1865       80829 :   x = cgetg(l, t_POL); x[1] = z[1];
    1866       80829 :   for (i=2; i<l; i++) gel(x,i) = odd(i) ? pol0_F2x(mael(z,i+1,1)): gel(z,i+1);
    1867       80829 :   return F2xX_renormalize(x,l);
    1868             : }
    1869             : 
    1870             : static GEN
    1871       13255 : F2xX_addspec(GEN x, GEN y, long lx, long ly)
    1872             : {
    1873             :   long i,lz;
    1874             :   GEN z;
    1875       13255 :   if (ly>lx) swapspec(x,y, lx,ly);
    1876       13255 :   lz = lx+2; z = cgetg(lz, t_POL);
    1877       13255 :   for (i=0; i<ly; i++) gel(z,i+2) = F2x_add(gel(x,i), gel(y,i));
    1878       13255 :   for (   ; i<lx; i++) gel(z,i+2) = F2x_copy(gel(x,i));
    1879       13255 :   return F2xX_renormalize(z, lz);
    1880             : }
    1881             : 
    1882             : GEN
    1883      422674 : F2xX_add(GEN x, GEN y)
    1884             : {
    1885             :   long i,lz;
    1886             :   GEN z;
    1887      422674 :   long lx=lg(x);
    1888      422674 :   long ly=lg(y);
    1889      422674 :   if (ly>lx) swapspec(x,y, lx,ly);
    1890      422674 :   lz = lx; z = cgetg(lz, t_POL); z[1]=x[1];
    1891      422674 :   for (i=2; i<ly; i++) gel(z,i) = F2x_add(gel(x,i), gel(y,i));
    1892      422674 :   for (   ; i<lx; i++) gel(z,i) = F2x_copy(gel(x,i));
    1893      422674 :   return F2xX_renormalize(z, lz);
    1894             : }
    1895             : 
    1896             : GEN
    1897           0 : F2xX_F2x_add(GEN x, GEN y)
    1898             : {
    1899           0 :   long i, lz = lg(y);
    1900             :   GEN z;
    1901           0 :   if (signe(y) == 0) return scalarpol(x, varn(y));
    1902           0 :   z = cgetg(lz,t_POL); z[1] = y[1];
    1903           0 :   gel(z,2) = F2x_add(gel(y,2), x);
    1904           0 :   if (lz == 3) z = F2xX_renormalize(z,lz);
    1905             :   else
    1906           0 :     for(i=3;i<lz;i++) gel(z,i) = F2x_copy(gel(y,i));
    1907           0 :   return z;
    1908             : }
    1909             : 
    1910             : GEN
    1911      480984 : F2xX_F2x_mul(GEN P, GEN U)
    1912             : {
    1913      480984 :   long i, lP = lg(P);
    1914      480984 :   GEN res = cgetg(lP,t_POL);
    1915      480984 :   res[1] = P[1];
    1916     2326954 :   for(i=2; i<lP; i++)
    1917     1845970 :     gel(res,i) = F2x_mul(U,gel(P,i));
    1918      480984 :   return F2xX_renormalize(res, lP);
    1919             : }
    1920             : 
    1921             : GEN
    1922      136514 : F2xY_F2xqV_evalx(GEN P, GEN x, GEN T)
    1923             : {
    1924      136514 :   long i, lP = lg(P);
    1925      136514 :   GEN res = cgetg(lP,t_POL);
    1926      136514 :   res[1] = P[1];
    1927      617274 :   for(i=2; i<lP; i++)
    1928      480760 :     gel(res,i) = F2x_F2xqV_eval(gel(P,i), x, T);
    1929      136514 :   return F2xX_renormalize(res, lP);
    1930             : }
    1931             : 
    1932             : GEN
    1933           0 : F2xY_F2xq_evalx(GEN P, GEN x, GEN T)
    1934             : {
    1935           0 :   pari_sp av = avma;
    1936           0 :   long n = brent_kung_optpow(F2x_degree(T)-1,lgpol(P),1);
    1937           0 :   GEN xp = F2xq_powers(x, n, T);
    1938           0 :   return gerepileupto(av, F2xY_F2xqV_evalx(P, xp, T));
    1939             : }
    1940             : 
    1941             : static GEN
    1942       55836 : F2xX_to_Kronecker_spec(GEN P, long n, long d)
    1943             : {
    1944       55836 :   long i, k, l, N = 2*d + 1;
    1945       55836 :   long dP = n+1;
    1946             :   GEN x;
    1947       55836 :   if (n == 0) return pol0_Flx(P[1]&VARNBITS);
    1948       55388 :   l = nbits2nlong(N*dP+d+1);
    1949       55388 :   x = zero_zv(l+1);
    1950      650784 :   for (k=i=0; i<n; i++, k+=N)
    1951             :   {
    1952      595396 :     GEN c = gel(P,i);
    1953      595396 :     F2x_addshiftip(x, c, k);
    1954             :   }
    1955       55388 :   x[1] = P[1]&VARNBITS; return F2x_renormalize(x, l+2);
    1956             : }
    1957             : 
    1958             : GEN
    1959      308272 : F2xX_to_Kronecker(GEN P, long d)
    1960             : {
    1961      308272 :   long i, k, l, N = 2*d + 1;
    1962      308272 :   long dP = degpol(P);
    1963             :   GEN x;
    1964      308272 :   if (dP < 0) return pol0_Flx(P[1]&VARNBITS);
    1965      306964 :   l = nbits2nlong(N*dP+d+1);
    1966      306964 :   x = zero_zv(l+1);
    1967     1689395 :   for (k=i=0; i<=dP; i++, k+=N)
    1968             :   {
    1969     1382431 :     GEN c = gel(P,i+2);
    1970     1382431 :     F2x_addshiftip(x, c, k);
    1971             :   }
    1972      306964 :   x[1] = P[1]&VARNBITS; return F2x_renormalize(x, l+2);
    1973             : }
    1974             : 
    1975             : static GEN
    1976     1792464 : F2x_slice(GEN x, long n, long d)
    1977             : {
    1978     1792464 :   ulong ib, il=dvmduBIL(n, &ib);
    1979     1792464 :   ulong db, dl=dvmduBIL(d, &db);
    1980     1792464 :   long lN = dl+2+(db?1:0);
    1981     1792464 :   GEN t = cgetg(lN,t_VECSMALL);
    1982     1792464 :   t[1] = x[1];
    1983     1792464 :   if (ib)
    1984             :   {
    1985     1602939 :     ulong i, ic = BITS_IN_LONG-ib;
    1986     1602939 :     ulong r = uel(x,2+il)>>ib;
    1987     1606301 :     for(i=0; i<dl; i++)
    1988             :     {
    1989        3362 :       uel(t,2+i) = (uel(x,3+il+i)<<ic)|r;
    1990        3362 :       r = uel(x,3+il+i)>>ib;
    1991             :     }
    1992     1602939 :     if (db)
    1993     1602926 :       uel(t,2+i) = (uel(x,3+il+i)<<ic)|r;
    1994             :   }
    1995             :   else
    1996             :   {
    1997             :     long i;
    1998      380445 :     for(i=2; i<lN; i++)
    1999      190920 :       uel(t,i) = uel(x,il+i);
    2000             :   }
    2001     1792464 :   if (db) uel(t,lN-1) &= (1UL<<db)-1;
    2002     1792464 :   return F2x_renormalize(t, lN);
    2003             : }
    2004             : 
    2005             : GEN
    2006      182054 : Kronecker_to_F2xqX(GEN z, GEN T)
    2007             : {
    2008      182054 :   long lz = F2x_degree(z)+1;
    2009      182054 :   long i, j, N = F2x_degree(T)*2 + 1;
    2010      182054 :   long lx = lz / (N-2);
    2011      182054 :   GEN x = cgetg(lx+3,t_POL);
    2012      182054 :   x[1] = z[1];
    2013     1974518 :   for (i=0, j=2; i<lz; i+=N, j++)
    2014             :   {
    2015     1792464 :     GEN t = F2x_slice(z,i,minss(lz-i,N));
    2016     1792464 :     t[1] = T[1];
    2017     1792464 :     gel(x,j) = F2x_rem(t, T);
    2018             :   }
    2019      182054 :   return F2xX_renormalize(x, j);
    2020             : }
    2021             : 
    2022             : /***********************************************************************/
    2023             : /**                                                                   **/
    2024             : /**                             F2xXV/F2xXC                           **/
    2025             : /**                                                                   **/
    2026             : /***********************************************************************/
    2027             : 
    2028             : GEN
    2029         252 : FlxXC_to_F2xXC(GEN x)
    2030         252 : { pari_APPLY_type(t_COL, FlxX_to_F2xX(gel(x,i))); }
    2031             : 
    2032             : GEN
    2033         819 : F2xXC_to_ZXXC(GEN x)
    2034         819 : { pari_APPLY_type(t_COL, F2xX_to_ZXX(gel(x,i))); }
    2035             : 
    2036             : /***********************************************************************/
    2037             : /**                                                                   **/
    2038             : /**                             F2xqX                                 **/
    2039             : /**                                                                   **/
    2040             : /***********************************************************************/
    2041             : 
    2042             : static GEN
    2043      784931 : get_F2xqX_red(GEN T, GEN *B)
    2044             : {
    2045      784931 :   if (typ(T)!=t_VEC) { *B=NULL; return T; }
    2046        5374 :   *B = gel(T,1); return gel(T,2);
    2047             : }
    2048             : 
    2049             : GEN
    2050        2744 : random_F2xqX(long d1, long v, GEN T)
    2051             : {
    2052        2744 :   long dT = F2x_degree(T), vT = T[1];
    2053        2744 :   long i, d = d1+2;
    2054        2744 :   GEN y = cgetg(d,t_POL); y[1] = evalsigne(1) | evalvarn(v);
    2055        2744 :   for (i=2; i<d; i++) gel(y,i) = random_F2x(dT, vT);
    2056        2744 :   return FlxX_renormalize(y,d);
    2057             : }
    2058             : 
    2059             : GEN
    2060      669041 : F2xqX_red(GEN z, GEN T)
    2061             : {
    2062             :   GEN res;
    2063      669041 :   long i, l = lg(z);
    2064      669041 :   res = cgetg(l,t_POL); res[1] = z[1];
    2065      669041 :   for(i=2;i<l;i++) gel(res,i) = F2x_rem(gel(z,i),T);
    2066      669041 :   return F2xX_renormalize(res,l);
    2067             : }
    2068             : 
    2069             : GEN
    2070        7558 : F2xqX_F2xq_mul(GEN P, GEN U, GEN T)
    2071             : {
    2072        7558 :   long i, lP = lg(P);
    2073        7558 :   GEN res = cgetg(lP,t_POL);
    2074        7558 :   res[1] = P[1];
    2075       41404 :   for(i=2; i<lP; i++)
    2076       33846 :     gel(res,i) = F2xq_mul(U,gel(P,i), T);
    2077        7558 :   return F2xX_renormalize(res, lP);
    2078             : }
    2079             : 
    2080             : GEN
    2081      206528 : F2xqX_F2xq_mul_to_monic(GEN P, GEN U, GEN T)
    2082             : {
    2083      206528 :   long i, lP = lg(P);
    2084      206528 :   GEN res = cgetg(lP,t_POL);
    2085      206528 :   res[1] = P[1];
    2086      206528 :   for(i=2; i<lP-1; i++) gel(res,i) = F2xq_mul(U,gel(P,i), T);
    2087      206528 :   gel(res,lP-1) = pol1_F2x(T[1]);
    2088      206528 :   return F2xX_renormalize(res, lP);
    2089             : }
    2090             : 
    2091             : GEN
    2092      206542 : F2xqX_normalize(GEN z, GEN T)
    2093             : {
    2094      206542 :   GEN p1 = leading_coeff(z);
    2095      206542 :   if (!lgpol(z) || (!degpol(p1) && p1[1] == 1)) return z;
    2096      206528 :   return F2xqX_F2xq_mul_to_monic(z, F2xq_inv(p1,T), T);
    2097             : }
    2098             : 
    2099             : GEN
    2100      154136 : F2xqX_mul(GEN x, GEN y, GEN T)
    2101             : {
    2102      154136 :   pari_sp ltop=avma;
    2103             :   GEN z,kx,ky;
    2104      154136 :   kx= F2xX_to_Kronecker(x, F2x_degree(T));
    2105      154136 :   ky= F2xX_to_Kronecker(y, F2x_degree(T));
    2106      154136 :   z = F2x_mul(ky, kx);
    2107      154136 :   z = Kronecker_to_F2xqX(z,T);
    2108      154136 :   return gerepileupto(ltop,z);
    2109             : }
    2110             : 
    2111             : static GEN
    2112       27918 : F2xqX_mulspec(GEN x, GEN y, GEN T, long nx, long ny)
    2113             : {
    2114       27918 :   pari_sp ltop=avma;
    2115             :   GEN z,kx,ky;
    2116       27918 :   kx= F2xX_to_Kronecker_spec(x, nx, F2x_degree(T));
    2117       27918 :   ky= F2xX_to_Kronecker_spec(y, ny, F2x_degree(T));
    2118       27918 :   z = F2x_mul(ky, kx);
    2119       27918 :   z = Kronecker_to_F2xqX(z,T);
    2120       27918 :   return gerepileupto(ltop,z);
    2121             : }
    2122             : 
    2123             : GEN
    2124      105196 : F2xqX_sqr(GEN x, GEN T)
    2125             : {
    2126      105196 :   long d = degpol(x), l = 2*d+3;
    2127             :   GEN z;
    2128      105196 :   if (!signe(x)) return pol_0(varn(x));
    2129      105189 :   z = cgetg(l,t_POL);
    2130      105189 :   z[1] = x[1];
    2131      105189 :   if (d > 0)
    2132             :   {
    2133      105105 :     GEN u = pol0_F2x(T[1]);
    2134             :     long i,j;
    2135      269605 :     for (i=2,j=2; i<d+2; i++,j+=2)
    2136             :     {
    2137      164500 :       gel(z, j) = F2xq_sqr(gel(x, i), T);
    2138      164500 :       gel(z, j+1) = u;
    2139             :     }
    2140             :   }
    2141      105189 :   gel(z, 2+2*d) = F2xq_sqr(gel(x, 2+d), T);
    2142      105189 :   return FlxX_renormalize(z, l);
    2143             : }
    2144             : 
    2145             : static GEN
    2146      544104 : F2xqX_divrem_basecase(GEN x, GEN y, GEN T, GEN *pr)
    2147             : {
    2148             :   long vx, dx, dy, dz, i, j, sx, lr;
    2149             :   pari_sp av0, av, tetpil;
    2150             :   GEN z,p1,rem,lead;
    2151             : 
    2152      544104 :   if (!signe(y)) pari_err_INV("F2xqX_divrem",y);
    2153      544104 :   vx=varn(x); dy=degpol(y); dx=degpol(x);
    2154      544104 :   if (dx < dy)
    2155             :   {
    2156           0 :     if (pr)
    2157             :     {
    2158           0 :       av0 = avma; x = F2xqX_red(x, T);
    2159           0 :       if (pr == ONLY_DIVIDES) { set_avma(av0); return signe(x)? NULL: pol_0(vx); }
    2160           0 :       if (pr == ONLY_REM) return x;
    2161           0 :       *pr = x;
    2162             :     }
    2163           0 :     return pol_0(vx);
    2164             :   }
    2165      544104 :   lead = leading_term(y);
    2166      544104 :   if (!dy) /* y is constant */
    2167             :   {
    2168      115724 :     if (pr && pr != ONLY_DIVIDES)
    2169             :     {
    2170      105672 :       if (pr == ONLY_REM) return pol_0(vx);
    2171          14 :       *pr = pol_0(vx);
    2172             :     }
    2173       10066 :     if (F2x_equal1(lead)) return gcopy(x);
    2174        7007 :     av0 = avma; x = F2xqX_F2xq_mul(x,F2xq_inv(lead,T),T);
    2175        7007 :     return gerepileupto(av0,x);
    2176             :   }
    2177      428380 :   av0 = avma; dz = dx-dy;
    2178      428380 :   lead = F2x_equal1(lead)? NULL: gclone(F2xq_inv(lead,T));
    2179      428380 :   set_avma(av0);
    2180      428380 :   z = cgetg(dz+3,t_POL); z[1] = x[1];
    2181      428380 :   x += 2; y += 2; z += 2;
    2182             : 
    2183      428380 :   p1 = gel(x,dx); av = avma;
    2184      428380 :   gel(z,dz) = lead? gerepileupto(av, F2xq_mul(p1,lead, T)): leafcopy(p1);
    2185     1227937 :   for (i=dx-1; i>=dy; i--)
    2186             :   {
    2187      799557 :     av=avma; p1=gel(x,i);
    2188     2261702 :     for (j=i-dy+1; j<=i && j<=dz; j++)
    2189     1462145 :       p1 = F2x_add(p1, F2x_mul(gel(z,j),gel(y,i-j)));
    2190      799557 :     if (lead) p1 = F2x_mul(p1, lead);
    2191      799557 :     tetpil=avma; gel(z,i-dy) = gerepile(av,tetpil,F2x_rem(p1,T));
    2192             :   }
    2193      428380 :   if (!pr) { if (lead) gunclone(lead); return z-2; }
    2194             : 
    2195      405287 :   rem = (GEN)avma; av = (pari_sp)new_chunk(dx+3);
    2196      627596 :   for (sx=0; ; i--)
    2197             :   {
    2198      849905 :     p1 = gel(x,i);
    2199     1893601 :     for (j=0; j<=i && j<=dz; j++)
    2200     1266005 :       p1 = F2x_add(p1, F2x_mul(gel(z,j),gel(y,i-j)));
    2201      627596 :     tetpil=avma; p1 = F2x_rem(p1, T); if (lgpol(p1)) { sx = 1; break; }
    2202      285496 :     if (!i) break;
    2203      222309 :     set_avma(av);
    2204             :   }
    2205      405287 :   if (pr == ONLY_DIVIDES)
    2206             :   {
    2207           0 :     if (lead) gunclone(lead);
    2208           0 :     if (sx) return gc_NULL(av0);
    2209           0 :     set_avma((pari_sp)rem); return z-2;
    2210             :   }
    2211      405287 :   lr=i+3; rem -= lr;
    2212      405287 :   rem[0] = evaltyp(t_POL) | evallg(lr);
    2213      405287 :   rem[1] = z[-1];
    2214      405287 :   p1 = gerepile((pari_sp)rem,tetpil,p1);
    2215      405287 :   rem += 2; gel(rem,i) = p1;
    2216     1351245 :   for (i--; i>=0; i--)
    2217             :   {
    2218      945958 :     av=avma; p1 = gel(x,i);
    2219     3002714 :     for (j=0; j<=i && j<=dz; j++)
    2220     2056756 :       p1 = F2x_add(p1, F2x_mul(gel(z,j),gel(y,i-j)));
    2221      945958 :     tetpil=avma; gel(rem,i) = gerepile(av,tetpil, F2x_rem(p1, T));
    2222             :   }
    2223      405287 :   rem -= 2;
    2224      405287 :   if (lead) gunclone(lead);
    2225      405287 :   if (!sx) (void)F2xX_renormalize(rem, lr);
    2226      405287 :   if (pr == ONLY_REM) return gerepileupto(av0,rem);
    2227          35 :   *pr = rem; return z-2;
    2228             : }
    2229             : 
    2230             : static GEN
    2231       26891 : F2xX_recipspec(GEN x, long l, long n, long vs)
    2232             : {
    2233             :   long i;
    2234       26891 :   GEN z = cgetg(n+2,t_POL);
    2235       26891 :   z[1] = 0; z += 2;
    2236      266480 :   for(i=0; i<l; i++)
    2237      239589 :     gel(z,n-i-1) = F2x_copy(gel(x,i));
    2238       27339 :   for(   ; i<n; i++)
    2239         448 :     gel(z,n-i-1) = pol0_F2x(vs);
    2240       26891 :   return F2xX_renormalize(z-2,n+2);
    2241             : }
    2242             : 
    2243             : static GEN
    2244         408 : F2xqX_invBarrett_basecase(GEN T, GEN Q)
    2245             : {
    2246         408 :   long i, l=lg(T)-1, lr = l-1, k;
    2247         408 :   long sv=Q[1];
    2248         408 :   GEN r=cgetg(lr,t_POL); r[1]=T[1];
    2249         408 :   gel(r,2) = pol1_F2x(sv);
    2250        1508 :   for (i=3;i<lr;i++)
    2251             :   {
    2252        1100 :     pari_sp ltop=avma;
    2253        1100 :     GEN u = gel(T,l-i+2);
    2254        5736 :     for (k=3;k<i;k++)
    2255        4636 :       u = F2x_add(u, F2xq_mul(gel(T,l-i+k),gel(r,k),Q));
    2256        1100 :     gel(r,i) = gerepileupto(ltop, u);
    2257             :   }
    2258         408 :   r = F2xX_renormalize(r,lr);
    2259         408 :   return r;
    2260             : }
    2261             : 
    2262             : /* Return new lgpol */
    2263             : static long
    2264       28692 : F2xX_lgrenormalizespec(GEN x, long lx)
    2265             : {
    2266             :   long i;
    2267       28692 :   for (i = lx-1; i>=0; i--)
    2268       28692 :     if (lgpol(gel(x,i))) break;
    2269       28692 :   return i+1;
    2270             : }
    2271             : 
    2272             : static GEN
    2273         101 : F2xqX_invBarrett_Newton(GEN S, GEN T)
    2274             : {
    2275         101 :   pari_sp av = avma;
    2276         101 :   long nold, lx, lz, lq, l = degpol(S), i, lQ;
    2277         101 :   GEN q, y, z, x = cgetg(l+2, t_POL) + 2;
    2278         101 :   long dT = F2x_degree(T);
    2279         101 :   ulong mask = quadratic_prec_mask(l-2); /* assume l > 2 */
    2280         101 :   for (i=0;i<l;i++) gel(x,i) = pol0_F2x(T[1]);
    2281         101 :   q = F2xX_recipspec(S+2,l+1,l+1,dT);
    2282         101 :   lQ = lgpol(q); q+=2;
    2283             :   /* We work on _spec_ FlxX's, all the l[xzq] below are lgpol's */
    2284             : 
    2285             :   /* initialize */
    2286         101 :   gel(x,0) = F2xq_inv(gel(q,0),T);
    2287         101 :   if (lQ>1 && F2x_degree(gel(q,1)) >= dT)
    2288           0 :     gel(q,1) = F2x_rem(gel(q,1), T);
    2289         101 :   if (lQ>1 && lgpol(gel(q,1)))
    2290         101 :   {
    2291         101 :     GEN u = gel(q, 1);
    2292         101 :     if (!F2x_equal1(gel(x,0))) u = F2xq_mul(u, F2xq_sqr(gel(x,0), T), T);
    2293         101 :     else u = F2x_copy(u);
    2294         101 :     gel(x,1) = u; lx = 2;
    2295             :   }
    2296             :   else
    2297           0 :     lx = 1;
    2298         101 :   nold = 1;
    2299         836 :   for (; mask > 1; )
    2300             :   { /* set x -= x(x*q - 1) + O(t^(nnew + 1)), knowing x*q = 1 + O(t^(nold+1)) */
    2301         634 :     long i, lnew, nnew = nold << 1;
    2302             : 
    2303         634 :     if (mask & 1) nnew--;
    2304         634 :     mask >>= 1;
    2305             : 
    2306         634 :     lnew = nnew + 1;
    2307         634 :     lq = F2xX_lgrenormalizespec(q, minss(lQ,lnew));
    2308         634 :     z = F2xqX_mulspec(x, q, T, lx, lq); /* FIXME: high product */
    2309         634 :     lz = lgpol(z); if (lz > lnew) lz = lnew;
    2310         634 :     z += 2;
    2311             :     /* subtract 1 [=>first nold words are 0]: renormalize so that z(0) != 0 */
    2312         634 :     for (i = nold; i < lz; i++) if (lgpol(gel(z,i))) break;
    2313         634 :     nold = nnew;
    2314         634 :     if (i >= lz) continue; /* z-1 = 0(t^(nnew + 1)) */
    2315             : 
    2316             :     /* z + i represents (x*q - 1) / t^i */
    2317         634 :     lz = F2xX_lgrenormalizespec (z+i, lz-i);
    2318         634 :     z = F2xqX_mulspec(x, z+i, T, lx, lz); /* FIXME: low product */
    2319         634 :     lz = lgpol(z); z += 2;
    2320         634 :     if (lz > lnew-i) lz = F2xX_lgrenormalizespec(z, lnew-i);
    2321             : 
    2322         634 :     lx = lz+ i;
    2323         634 :     y  = x + i; /* x -= z * t^i, in place */
    2324         634 :     for (i = 0; i < lz; i++) gel(y,i) = gel(z,i);
    2325             :   }
    2326         101 :   x -= 2; setlg(x, lx + 2); x[1] = S[1];
    2327         101 :   return gerepilecopy(av, x);
    2328             : }
    2329             : 
    2330             : /* x/polrecip(P)+O(x^n) */
    2331             : GEN
    2332         813 : F2xqX_invBarrett(GEN T, GEN Q)
    2333             : {
    2334         813 :   pari_sp ltop=avma;
    2335         813 :   long l=lg(T), v = varn(T);
    2336             :   GEN r;
    2337         813 :   GEN c = gel(T,l-1);
    2338         813 :   if (l<5) return pol_0(v);
    2339         509 :   if (l<=F2xqX_INVBARRETT_LIMIT)
    2340             :   {
    2341         408 :     if (!F2x_equal1(c))
    2342             :     {
    2343         272 :       GEN ci = F2xq_inv(c,Q);
    2344         272 :       T = F2xqX_F2xq_mul(T, ci, Q);
    2345         272 :       r = F2xqX_invBarrett_basecase(T,Q);
    2346         272 :       r = F2xqX_F2xq_mul(r,ci,Q);
    2347             :     } else
    2348         136 :       r = F2xqX_invBarrett_basecase(T,Q);
    2349             :   } else
    2350         101 :     r = F2xqX_invBarrett_Newton(T,Q);
    2351         509 :   return gerepileupto(ltop, r);
    2352             : }
    2353             : 
    2354             : GEN
    2355        2639 : F2xqX_get_red(GEN S, GEN T)
    2356             : {
    2357        2639 :   if (typ(S)==t_POL && lg(S)>F2xqX_BARRETT_LIMIT)
    2358         105 :     retmkvec2(F2xqX_invBarrett(S, T), S);
    2359        2534 :   return S;
    2360             : }
    2361             : 
    2362             : /* Compute x mod S where 2 <= degpol(S) <= l+1 <= 2*(degpol(S)-1)
    2363             :  *  * and mg is the Barrett inverse of S. */
    2364             : static GEN
    2365       13395 : F2xqX_divrem_Barrettspec(GEN x, long l, GEN mg, GEN S, GEN T, GEN *pr)
    2366             : {
    2367             :   GEN q, r;
    2368       13395 :   long lt = degpol(S); /*We discard the leading term*/
    2369             :   long ld, lm, lT, lmg;
    2370       13395 :   ld = l-lt;
    2371       13395 :   lm = minss(ld, lgpol(mg));
    2372       13395 :   lT  = F2xX_lgrenormalizespec(S+2,lt);
    2373       13395 :   lmg = F2xX_lgrenormalizespec(mg+2,lm);
    2374       13395 :   q = F2xX_recipspec(x+lt,ld,ld,0);               /* q = rec(x)     lq<=ld*/
    2375       13395 :   q = F2xqX_mulspec(q+2,mg+2,T,lgpol(q),lmg);   /* q = rec(x) * mg lq<=ld+lm*/
    2376       13395 :   q = F2xX_recipspec(q+2,minss(ld,lgpol(q)),ld,0);/* q = rec (rec(x) * mg) lq<=ld*/
    2377       13395 :   if (!pr) return q;
    2378       13255 :   r = F2xqX_mulspec(q+2,S+2,T,lgpol(q),lT);     /* r = q*pol        lr<=ld+lt*/
    2379       13255 :   r = F2xX_addspec(x,r+2,lt,minss(lt,lgpol(r)));/* r = x - r   lr<=lt */
    2380       13255 :   if (pr == ONLY_REM) return r;
    2381       10316 :   *pr = r; return q;
    2382             : }
    2383             : 
    2384             : static GEN
    2385        3383 : F2xqX_divrem_Barrett(GEN x, GEN mg, GEN S, GEN T, GEN *pr)
    2386             : {
    2387        3383 :   GEN q = NULL, r = F2xqX_red(x, T);
    2388        3383 :   long l = lgpol(r), lt = degpol(S), lm = 2*lt-1, v = varn(S);
    2389             :   long i;
    2390        3383 :   if (l <= lt)
    2391             :   {
    2392           0 :     if (pr == ONLY_REM) return r;
    2393           0 :     if (pr == ONLY_DIVIDES) return signe(r)? NULL: pol_0(v);
    2394           0 :     if (pr) *pr = r;
    2395           0 :     return pol_0(v);
    2396             :   }
    2397        3383 :   if (lt <= 1)
    2398         304 :     return F2xqX_divrem_basecase(x,S,T,pr);
    2399        3079 :   if (pr != ONLY_REM && l>lm)
    2400             :   {
    2401         132 :     long vT = get_F2x_var(T);
    2402         132 :     q = cgetg(l-lt+2, t_POL);
    2403         132 :     for (i=0;i<l-lt;i++) gel(q+2,i) = pol0_F2x(vT);
    2404             :   }
    2405       16474 :   while (l>lm)
    2406             :   {
    2407       10316 :     GEN zr, zq = F2xqX_divrem_Barrettspec(r+2+l-lm,lm,mg,S,T,&zr);
    2408       10316 :     long lz = lgpol(zr);
    2409       10316 :     if (pr != ONLY_REM)
    2410             :     {
    2411        3588 :       long lq = lgpol(zq);
    2412        3588 :       for(i=0; i<lq; i++) gel(q+2+l-lm,i) = gel(zq,2+i);
    2413             :     }
    2414       10316 :     for(i=0; i<lz; i++) gel(r+2+l-lm,i) = gel(zr,2+i);
    2415       10316 :     l = l-lm+lz;
    2416             :   }
    2417        3079 :   if (pr == ONLY_REM)
    2418             :   {
    2419        2939 :     if (l > lt)
    2420        2939 :       r = F2xqX_divrem_Barrettspec(r+2,l,mg,S,T,ONLY_REM);
    2421             :     else
    2422           0 :       r = F2xX_renormalize(r, lg(r));
    2423        2939 :     setvarn(r, v); return F2xX_renormalize(r, lg(r));
    2424             :   }
    2425         140 :   if (l > lt)
    2426             :   {
    2427         140 :     GEN zq = F2xqX_divrem_Barrettspec(r+2,l,mg,S,T,pr? &r: NULL);
    2428         140 :     if (!q) q = zq;
    2429             :     else
    2430             :     {
    2431         132 :       long lq = lgpol(zq);
    2432         132 :       for(i=0; i<lq; i++) gel(q+2,i) = gel(zq,2+i);
    2433             :     }
    2434             :   }
    2435           0 :   else if (pr)
    2436           0 :     r = F2xX_renormalize(r, l+2);
    2437         140 :   setvarn(q, v); q = F2xX_renormalize(q, lg(q));
    2438         140 :   if (pr == ONLY_DIVIDES) return signe(r)? NULL: q;
    2439         140 :   if (pr) { setvarn(r, v); *pr = r; }
    2440         140 :   return q;
    2441             : }
    2442             : 
    2443             : GEN
    2444       33334 : F2xqX_divrem(GEN x, GEN S, GEN T, GEN *pr)
    2445             : {
    2446       33334 :   GEN B, y = get_F2xqX_red(S, &B);
    2447       33334 :   long dy = degpol(y), dx = degpol(x), d = dx-dy;
    2448       33334 :   if (pr==ONLY_REM) return F2xqX_rem(x, y, T);
    2449       33334 :   if (!B && d+3 < F2xqX_DIVREM_BARRETT_LIMIT)
    2450       33018 :     return F2xqX_divrem_basecase(x,y,T,pr);
    2451             :   else
    2452             :   {
    2453         316 :     pari_sp av=avma;
    2454         316 :     GEN mg = B? B: F2xqX_invBarrett(y, T);
    2455         316 :     GEN q = F2xqX_divrem_Barrett(x,mg,y,T,pr);
    2456         316 :     if (!q) return gc_NULL(av);
    2457         316 :     if (!pr || pr==ONLY_DIVIDES) return gerepilecopy(av, q);
    2458           0 :     gerepileall(av,2,&q,pr);
    2459           0 :     return q;
    2460             :   }
    2461             : }
    2462             : 
    2463             : GEN
    2464      751597 : F2xqX_rem(GEN x, GEN S, GEN T)
    2465             : {
    2466      751597 :   GEN B, y = get_F2xqX_red(S, &B);
    2467      751597 :   long dy = degpol(y), dx = degpol(x), d = dx-dy;
    2468      751597 :   if (d < 0) return F2xqX_red(x, T);
    2469      513849 :   if (!B && d+3 < F2xqX_REM_BARRETT_LIMIT)
    2470      510782 :     return F2xqX_divrem_basecase(x,y, T, ONLY_REM);
    2471             :   else
    2472             :   {
    2473        3067 :     pari_sp av=avma;
    2474        3067 :     GEN mg = B? B: F2xqX_invBarrett(y, T);
    2475        3067 :     GEN r = F2xqX_divrem_Barrett(x, mg, y, T, ONLY_REM);
    2476        3067 :     return gerepileupto(av, r);
    2477             :   }
    2478             : }
    2479             : 
    2480             : GEN
    2481      170289 : F2xqX_gcd(GEN a, GEN b, GEN T)
    2482             : {
    2483      170289 :   pari_sp av = avma, av0=avma;
    2484      870387 :   while (signe(b))
    2485             :   {
    2486             :     GEN c;
    2487      529809 :     if (gc_needed(av0,2))
    2488             :     {
    2489           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2xqX_gcd (d = %ld)",degpol(b));
    2490           0 :       gerepileall(av0,2, &a,&b);
    2491             :     }
    2492      529809 :     av = avma; c = F2xqX_rem(a, b, T); a=b; b=c;
    2493             :   }
    2494      170289 :   set_avma(av); return a;
    2495             : }
    2496             : 
    2497             : GEN
    2498          14 : F2xqX_extgcd(GEN a, GEN b, GEN T,  GEN *ptu, GEN *ptv)
    2499             : {
    2500          14 :   pari_sp av=avma;
    2501             :   GEN u,v,d,d1,v1;
    2502          14 :   long vx = varn(a);
    2503          14 :   d = a; d1 = b;
    2504          14 :   v = pol_0(vx); v1 = pol1_F2xX(vx, get_F2x_var(T));
    2505          77 :   while (signe(d1))
    2506             :   {
    2507          49 :     GEN r, q = F2xqX_divrem(d, d1, T, &r);
    2508          49 :     v = F2xX_add(v,F2xqX_mul(q,v1,T));
    2509          49 :     u=v; v=v1; v1=u;
    2510          49 :     u=r; d=d1; d1=u;
    2511          49 :     if (gc_needed(av,2))
    2512             :     {
    2513           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2xqX_extgcd (d = %ld)",degpol(d));
    2514           0 :       gerepileall(av,5, &d,&d1,&u,&v,&v1);
    2515             :     }
    2516             :   }
    2517          14 :   if (ptu) *ptu = F2xqX_div(F2xX_add(d,F2xqX_mul(b,v, T)), a, T);
    2518          14 :   *ptv = v; return d;
    2519             : }
    2520             : 
    2521             : static GEN
    2522           0 : _F2xqX_mul(void *data,GEN a,GEN b)
    2523           0 : { return F2xqX_mul(a,b, (GEN) data); }
    2524             : 
    2525             : static GEN
    2526           0 : _F2xqX_sqr(void *data,GEN a)
    2527           0 : { return F2xqX_sqr(a, (GEN) data); }
    2528             : 
    2529             : GEN
    2530           0 : F2xqX_powu(GEN x, ulong n, GEN T)
    2531             : {
    2532           0 :   return gen_powu(x, n, (void*)T, &_F2xqX_sqr, &_F2xqX_mul);
    2533             : }
    2534             : 
    2535             : /* Res(A,B) = Res(B,R) * lc(B)^(a-r) * (-1)^(ab), with R=A%B, a=deg(A) ...*/
    2536             : GEN
    2537          21 : F2xqX_resultant(GEN a, GEN b, GEN T)
    2538             : {
    2539          21 :   long vT = get_F2x_var(T);
    2540             :   long da,db,dc;
    2541             :   pari_sp av;
    2542          21 :   GEN c,lb, res = pol1_F2x(vT);
    2543             : 
    2544          21 :   if (!signe(a) || !signe(b)) return pol0_F2x(vT);
    2545             : 
    2546          21 :   da = degpol(a);
    2547          21 :   db = degpol(b);
    2548          21 :   if (db > da)
    2549           7 :     swapspec(a,b, da,db);
    2550          21 :   if (!da) return pol1_F2x(vT); /* = res * a[2] ^ db, since 0 <= db <= da = 0 */
    2551          21 :   av = avma;
    2552          70 :   while (db)
    2553             :   {
    2554          28 :     lb = gel(b,db+2);
    2555          28 :     c = F2xqX_rem(a,b, T);
    2556          28 :     a = b; b = c; dc = degpol(c);
    2557          28 :     if (dc < 0) { set_avma(av); return pol0_F2x(vT); }
    2558             : 
    2559          28 :     if (!equali1(lb)) res = F2xq_mul(res, F2xq_powu(lb, da - dc, T), T);
    2560          28 :     if (gc_needed(av,2))
    2561             :     {
    2562           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2xqX_resultant (da = %ld)",da);
    2563           0 :       gerepileall(av,3, &a,&b,&res);
    2564             :     }
    2565          28 :     da = db; /* = degpol(a) */
    2566          28 :     db = dc; /* = degpol(b) */
    2567             :   }
    2568          21 :   res = F2xq_mul(res, F2xq_powu(gel(b,2), da, T), T);
    2569          21 :   return gerepileupto(av, res);
    2570             : }
    2571             : 
    2572             : /* disc P = (-1)^(n(n-1)/2) lc(P)^(n - deg P' - 2) Res(P,P'), n = deg P */
    2573             : GEN
    2574          14 : F2xqX_disc(GEN P, GEN T)
    2575             : {
    2576          14 :   pari_sp av = avma;
    2577          14 :   GEN L, dP = F2xX_deriv(P), D = F2xqX_resultant(P, dP, T);
    2578             :   long dd;
    2579          14 :   if (!lgpol(D)) return pol_0(get_F2x_var(T));
    2580          14 :   dd = degpol(P) - 2 - degpol(dP); /* >= -1; > -1 iff p | deg(P) */
    2581          14 :   L = leading_coeff(P);
    2582          14 :   if (dd && !F2x_equal1(L))
    2583           0 :     D = (dd == -1)? F2xq_div(D,L,T): F2xq_mul(D, F2xq_powu(L, dd, T), T);
    2584          14 :   return gerepileupto(av, D);
    2585             : }
    2586             : 
    2587             : /***********************************************************************/
    2588             : /**                                                                   **/
    2589             : /**                             F2xqXQ                                **/
    2590             : /**                                                                   **/
    2591             : /***********************************************************************/
    2592             : 
    2593             : GEN
    2594      114562 : F2xqXQ_mul(GEN x, GEN y, GEN S, GEN T) {
    2595      114562 :   return F2xqX_rem(F2xqX_mul(x,y,T),S,T);
    2596             : }
    2597             : 
    2598             : GEN
    2599      104230 : F2xqXQ_sqr(GEN x, GEN S, GEN T) {
    2600      104230 :   return F2xqX_rem(F2xqX_sqr(x,T),S,T);
    2601             : }
    2602             : 
    2603             : GEN
    2604           7 : F2xqXQ_invsafe(GEN x, GEN S, GEN T)
    2605             : {
    2606           7 :   GEN V, z = F2xqX_extgcd(get_F2xqX_mod(S), x, T, NULL, &V);
    2607           7 :   if (degpol(z)) return NULL;
    2608           7 :   z = F2xq_invsafe(gel(z,2),T);
    2609           7 :   if (!z) return NULL;
    2610           7 :   return F2xqX_F2xq_mul(V, z, T);
    2611             : }
    2612             : 
    2613             : GEN
    2614           7 : F2xqXQ_inv(GEN x, GEN S, GEN T)
    2615             : {
    2616           7 :   pari_sp av = avma;
    2617           7 :   GEN U = F2xqXQ_invsafe(x, S, T);
    2618           7 :   if (!U) pari_err_INV("F2xqXQ_inv",x);
    2619           7 :   return gerepileupto(av, U);
    2620             : }
    2621             : 
    2622             : struct _F2xqXQ {
    2623             :   GEN T, S;
    2624             : };
    2625             : 
    2626             : static GEN
    2627      344477 : _F2xqXQ_add(void *data, GEN x, GEN y) {
    2628             :   (void) data;
    2629      344477 :   return F2xX_add(x,y);
    2630             : }
    2631             : static GEN
    2632      480984 : _F2xqXQ_cmul(void *data, GEN P, long a, GEN x) {
    2633             :   (void) data;
    2634      480984 :   return F2xX_F2x_mul(x,gel(P,a+2));
    2635             : }
    2636             : static GEN
    2637      352590 : _F2xqXQ_red(void *data, GEN x) {
    2638      352590 :   struct _F2xqXQ *d = (struct _F2xqXQ*) data;
    2639      352590 :   return F2xqX_red(x, d->T);
    2640             : }
    2641             : static GEN
    2642      114555 : _F2xqXQ_mul(void *data, GEN x, GEN y) {
    2643      114555 :   struct _F2xqXQ *d = (struct _F2xqXQ*) data;
    2644      114555 :   return F2xqXQ_mul(x,y, d->S,d->T);
    2645             : }
    2646             : static GEN
    2647       32928 : _F2xqXQ_sqr(void *data, GEN x) {
    2648       32928 :   struct _F2xqXQ *d = (struct _F2xqXQ*) data;
    2649       32928 :   return F2xqXQ_sqr(x, d->S,d->T);
    2650             : }
    2651             : static GEN
    2652          56 : _F2xqXQ_zero(void *data) {
    2653          56 :   struct _F2xqXQ *d = (struct _F2xqXQ*) data;
    2654          56 :   return pol_0(get_F2xqX_var(d->S));
    2655             : }
    2656             : static GEN
    2657      375774 : _F2xqXQ_one(void *data) {
    2658      375774 :   struct _F2xqXQ *d = (struct _F2xqXQ*) data;
    2659      375774 :   return pol1_F2xX(get_F2xqX_var(d->S),get_F2x_var(d->T));
    2660             : }
    2661             : 
    2662             : static struct bb_algebra F2xqXQ_algebra = { _F2xqXQ_red,
    2663             :  _F2xqXQ_add, _F2xqXQ_add, _F2xqXQ_mul,_F2xqXQ_sqr,_F2xqXQ_one,_F2xqXQ_zero };
    2664             : 
    2665             : GEN
    2666           7 : F2xqXQ_pow(GEN x, GEN n, GEN S, GEN T)
    2667             : {
    2668             :   struct _F2xqXQ D;
    2669           7 :   long s = signe(n);
    2670           7 :   if (!s) return pol1_F2xX(get_F2xqX_var(S), get_F2x_var(T));
    2671           7 :   if (s < 0) x = F2xqXQ_inv(x,S,T);
    2672           7 :   if (is_pm1(n)) return s < 0 ? x : gcopy(x);
    2673           7 :   if (degpol(x) >= get_F2xqX_degree(S)) x = F2xqX_rem(x,S,T);
    2674           7 :   D.S = S; D.T = T;
    2675           7 :   return gen_pow(x, n, (void*)&D, &_F2xqXQ_sqr, &_F2xqXQ_mul);
    2676             : }
    2677             : 
    2678             : GEN
    2679        7385 : F2xqXQ_powers(GEN x, long l, GEN S, GEN T)
    2680             : {
    2681             :   struct _F2xqXQ D;
    2682        7385 :   int use_sqr = 2*degpol(x) >= get_F2xqX_degree(S);
    2683        7385 :   D.S = S; D.T = T;
    2684        7385 :   return gen_powers(x, l, use_sqr, (void*)&D, &_F2xqXQ_sqr, &_F2xqXQ_mul,&_F2xqXQ_one);
    2685             : }
    2686             : 
    2687             : GEN
    2688       13797 : F2xqX_F2xqXQV_eval(GEN P, GEN V, GEN S, GEN T)
    2689             : {
    2690             :   struct _F2xqXQ D;
    2691       13797 :   D.S = S; D.T = T;
    2692       13797 :   return gen_bkeval_powers(P, degpol(P), V, (void*)&D, &F2xqXQ_algebra,
    2693             :                                                    _F2xqXQ_cmul);
    2694             : }
    2695             : 
    2696             : GEN
    2697      122766 : F2xqX_F2xqXQ_eval(GEN Q, GEN x, GEN S, GEN T)
    2698             : {
    2699             :   struct _F2xqXQ D;
    2700      122766 :   int use_sqr = 2*degpol(x) >= get_F2xqX_degree(S);
    2701      122766 :   D.S = S; D.T = T;
    2702      122766 :   return gen_bkeval(Q, degpol(Q), x, use_sqr, (void*)&D, &F2xqXQ_algebra,
    2703             :                                                     _F2xqXQ_cmul);
    2704             : }
    2705             : 
    2706             : static GEN
    2707       89327 : F2xqXQ_autpow_sqr(void * E, GEN x)
    2708             : {
    2709       89327 :   struct _F2xqXQ *D = (struct _F2xqXQ *)E;
    2710       89327 :   GEN T = D->T;
    2711       89327 :   GEN phi = gel(x,1), S = gel(x,2);
    2712       89327 :   long n = brent_kung_optpow(F2x_degree(T)-1,lgpol(S)+1,1);
    2713       89327 :   GEN V = F2xq_powers(phi, n, T);
    2714       89327 :   GEN phi2 = F2x_F2xqV_eval(phi, V, T);
    2715       89327 :   GEN Sphi = F2xY_F2xqV_evalx(S, V, T);
    2716       89327 :   GEN S2 = F2xqX_F2xqXQ_eval(Sphi, S, D->S, T);
    2717       89327 :   return mkvec2(phi2, S2);
    2718             : }
    2719             : 
    2720             : static GEN
    2721       33439 : F2xqXQ_autpow_mul(void * E, GEN x, GEN y)
    2722             : {
    2723       33439 :   struct _F2xqXQ *D = (struct _F2xqXQ *)E;
    2724       33439 :   GEN T = D->T;
    2725       33439 :   GEN phi1 = gel(x,1), S1 = gel(x,2);
    2726       33439 :   GEN phi2 = gel(y,1), S2 = gel(y,2);
    2727       33439 :   long n = brent_kung_optpow(F2x_degree(T)-1,lgpol(S1)+1,1);
    2728       33439 :   GEN V = F2xq_powers(phi2, n, T);
    2729       33439 :   GEN phi3 = F2x_F2xqV_eval(phi1,V,T);
    2730       33439 :   GEN Sphi = F2xY_F2xqV_evalx(S1,V,T);
    2731       33439 :   GEN S3 = F2xqX_F2xqXQ_eval(Sphi, S2, D->S, T);
    2732       33439 :   return mkvec2(phi3, S3);
    2733             : }
    2734             : 
    2735             : GEN
    2736       70812 : F2xqXQ_autpow(GEN aut, long n, GEN S, GEN T)
    2737             : {
    2738             :   struct _F2xqXQ D;
    2739       70812 :   D.S = S; D.T = T;
    2740       70812 :   return gen_powu(aut,n,&D,F2xqXQ_autpow_sqr,F2xqXQ_autpow_mul);
    2741             : }
    2742             : 
    2743             : static GEN
    2744        6874 : F2xqXQ_auttrace_mul(void *E, GEN x, GEN y)
    2745             : {
    2746        6874 :   struct _F2xqXQ *D = (struct _F2xqXQ *) E;
    2747        6874 :   GEN T = D->T;
    2748        6874 :   GEN phi1 = gel(x,1), S1 = gel(x,2), a1 = gel(x,3);
    2749        6874 :   GEN phi2 = gel(y,1), S2 = gel(y,2), a2 = gel(y,3);
    2750        6874 :   long n2 = brent_kung_optpow(F2x_degree(T)-1, lgpol(S1)+lgpol(a1)+1, 1);
    2751        6874 :   GEN V2 = F2xq_powers(phi2, n2, T);
    2752        6874 :   GEN phi3 = F2x_F2xqV_eval(phi1, V2, T);
    2753        6874 :   GEN Sphi = F2xY_F2xqV_evalx(S1, V2, T);
    2754        6874 :   GEN aphi = F2xY_F2xqV_evalx(a1, V2, T);
    2755        6874 :   long n = brent_kung_optpow(maxss(degpol(Sphi),degpol(aphi)),2,1);
    2756        6874 :   GEN V = F2xqXQ_powers(S2, n, D->S, T);
    2757        6874 :   GEN S3 = F2xqX_F2xqXQV_eval(Sphi, V, D->S, T);
    2758        6874 :   GEN aS = F2xqX_F2xqXQV_eval(aphi, V, D->S, T);
    2759        6874 :   GEN a3 = F2xX_add(aS, a2);
    2760        6874 :   return mkvec3(phi3, S3, a3);
    2761             : }
    2762             : 
    2763             : static GEN
    2764        4613 : F2xqXQ_auttrace_sqr(void *E, GEN x)
    2765        4613 : { return F2xqXQ_auttrace_mul(E, x, x); }
    2766             : 
    2767             : GEN
    2768        2639 : F2xqXQ_auttrace(GEN aut, long n, GEN S, GEN T)
    2769             : {
    2770             :   struct _F2xqXQ D;
    2771        2639 :   D.S = S; D.T = T;
    2772        2639 :   return gen_powu(aut,n,&D,F2xqXQ_auttrace_sqr,F2xqXQ_auttrace_mul);
    2773             : }
    2774             : 
    2775             : GEN
    2776          63 : F2xqXQV_red(GEN x, GEN S, GEN T)
    2777          63 : { pari_APPLY_type(t_VEC, F2xqX_rem(gel(x,i), S, T)) }

Generated by: LCOV version 1.13