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 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.10.0 lcov report (development 21059-cbe0d6a) Lines: 1444 1563 92.4 %
Date: 2017-09-22 06:24:58 Functions: 173 181 95.6 %
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   299059404 : F2x_degree_lg(GEN x, long l)
      39             : {
      40   299059404 :   return (l==2)?-1:bit_accuracy(l)-bfffo(x[l-1])-1;
      41             : }
      42             : 
      43             : long
      44    80597613 : F2x_degree(GEN x)
      45             : {
      46    80597613 :   return F2x_degree_lg(x, lg(x));
      47             : }
      48             : 
      49             : GEN
      50          35 : monomial_F2x(long d, long vs)
      51             : {
      52          35 :   long l=nbits2lg(d+1);
      53          35 :   GEN z = zero_zv(l-1);
      54          35 :   z[1] = vs;
      55          35 :   F2x_set(z,d);
      56          35 :   return z;
      57             : }
      58             : 
      59             : GEN
      60      192379 : F2x_to_ZX(GEN x)
      61             : {
      62      192379 :   long l=3+F2x_degree(x);
      63      192379 :   GEN z=cgetg(l,t_POL);
      64             :   long i,j,k;
      65      384695 :   for(i=2,k=2;i<lg(x);i++)
      66      898592 :     for(j=0; j<BITS_IN_LONG && k<l; j++,k++)
      67      706276 :       gel(z,k)=(x[i]&(1UL<<j))?gen_1:gen_0;
      68      192379 :   z[1]=evalsigne(l>=3)|x[1];
      69      192379 :   return z;
      70             : }
      71             : 
      72             : GEN
      73      112403 : F2x_to_Flx(GEN x)
      74             : {
      75      112403 :   long l=3+F2x_degree(x);
      76      112403 :   GEN z=cgetg(l,t_VECSMALL);
      77             :   long i,j,k;
      78      112406 :   z[1]=x[1];
      79      260717 :   for(i=2,k=2;i<lg(x);i++)
      80     4836332 :     for(j=0;j<BITS_IN_LONG && k<l; j++,k++)
      81     4688021 :       z[k]=(x[i]>>j)&1UL;
      82      112406 :   return z;
      83             : }
      84             : 
      85             : GEN
      86      193032 : Z_to_F2x(GEN x, long v)
      87             : {
      88      193032 :   long sv = evalvarn(v);
      89      193032 :   return mpodd(x) ? pol1_F2x(sv): pol0_F2x(sv);
      90             : }
      91             : 
      92             : GEN
      93      157640 : ZX_to_F2x(GEN x)
      94             : {
      95      157640 :   long l=nbits2lg(lgpol(x));
      96      157640 :   GEN z=cgetg(l,t_VECSMALL);
      97             :   long i,j,k;
      98      157648 :   z[1]=((ulong)x[1])&VARNBITS;
      99      724947 :   for(i=2, k=1,j=BITS_IN_LONG;i<lg(x);i++,j++)
     100             :   {
     101      567307 :     if (j==BITS_IN_LONG)
     102             :     {
     103      156435 :       j=0; k++; z[k]=0;
     104             :     }
     105      567307 :     if (mpodd(gel(x,i)))
     106      429443 :       z[k]|=1UL<<j;
     107             :   }
     108      157640 :   return F2x_renormalize(z,l);
     109             : }
     110             : 
     111             : GEN
     112      242654 : Flx_to_F2x(GEN x)
     113             : {
     114      242654 :   long l=nbits2lg(lgpol(x));
     115      242653 :   GEN z=cgetg(l,t_VECSMALL);
     116             :   long i,j,k;
     117      242655 :   z[1]=x[1];
     118     5488589 :   for(i=2, k=1,j=BITS_IN_LONG;i<lg(x);i++,j++)
     119             :   {
     120     5245934 :     if (j==BITS_IN_LONG)
     121             :     {
     122      272025 :       j=0; k++; z[k]=0;
     123             :     }
     124     5245934 :     if (x[i]&1UL)
     125     2633692 :       z[k]|=1UL<<j;
     126             :   }
     127      242655 :   return F2x_renormalize(z,l);
     128             : }
     129             : 
     130             : GEN
     131     1361799 : F2x_to_F2v(GEN x, long N)
     132             : {
     133     1361799 :   long i, l = lg(x);
     134     1361799 :   long n = nbits2lg(N);
     135     1361799 :   GEN z = cgetg(n,t_VECSMALL);
     136     1361799 :   z[1] = N;
     137     1361799 :   for (i=2; i<l ; i++) z[i]=x[i];
     138     1361799 :   for (   ; i<n; i++) z[i]=0;
     139     1361799 :   return z;
     140             : }
     141             : 
     142             : GEN
     143        1141 : RgX_to_F2x(GEN x)
     144             : {
     145        1141 :   long l=nbits2lg(lgpol(x));
     146        1141 :   GEN z=cgetg(l,t_VECSMALL);
     147             :   long i,j,k;
     148        1141 :   z[1]=((ulong)x[1])&VARNBITS;
     149        3507 :   for(i=2, k=1,j=BITS_IN_LONG;i<lg(x);i++,j++)
     150             :   {
     151        2366 :     if (j==BITS_IN_LONG)
     152             :     {
     153        1141 :       j=0; k++; z[k]=0;
     154             :     }
     155        2366 :     if (Rg_to_F2(gel(x,i)))
     156        1064 :       z[k]|=1UL<<j;
     157             :   }
     158        1141 :   return F2x_renormalize(z,l);
     159             : }
     160             : 
     161             : /* If x is a POLMOD, assume modulus is a multiple of T. */
     162             : GEN
     163     1209598 : Rg_to_F2xq(GEN x, GEN T)
     164             : {
     165     1209598 :   long ta, tx = typ(x), v = T[1];
     166             :   GEN a, b;
     167     1209598 :   if (is_const_t(tx))
     168             :   {
     169     1208507 :     if (tx == t_FFELT) return FF_to_F2xq(x);
     170      244789 :     return Rg_to_F2(x)? pol1_F2x(v): pol0_F2x(v);
     171             :   }
     172        1092 :   switch(tx)
     173             :   {
     174             :     case t_POLMOD:
     175           0 :       b = gel(x,1);
     176           0 :       a = gel(x,2); ta = typ(a);
     177           0 :       if (is_const_t(ta)) return Rg_to_F2(a)? pol1_F2x(v): pol0_F2x(v);
     178           0 :       b = RgX_to_F2x(b); if (b[1] != v) break;
     179           0 :       a = RgX_to_F2x(a); if (F2x_equal(b,T)) return a;
     180           0 :       if (lgpol(F2x_rem(b,T))==0) return F2x_rem(a, T);
     181           0 :       break;
     182             :     case t_POL:
     183        1001 :       x = RgX_to_F2x(x);
     184        1001 :       if (x[1] != v) break;
     185        1001 :       return F2x_rem(x, T);
     186             :     case t_RFRAC:
     187          91 :       a = Rg_to_F2xq(gel(x,1), T);
     188          91 :       b = Rg_to_F2xq(gel(x,2), T);
     189          91 :       return F2xq_div(a,b, T);
     190             :   }
     191           0 :   pari_err_TYPE("Rg_to_F2xq",x);
     192             :   return NULL; /* LCOV_EXCL_LINE */
     193             : }
     194             : 
     195             : ulong
     196         224 : F2x_eval(GEN P, ulong x)
     197             : {
     198         224 :   if (odd(x))
     199             :   {
     200         126 :     long i, lP = lg(P);
     201         126 :     ulong c = 0;
     202         252 :     for (i=2; i<lP; i++)
     203         126 :       c ^= P[i];
     204             : #ifdef LONG_IS_64BIT
     205         108 :     c ^= c >> 32;
     206             : #endif
     207         126 :     c ^= c >> 16;
     208         126 :     c ^= c >>  8;
     209         126 :     c ^= c >>  4;
     210         126 :     c ^= c >>  2;
     211         126 :     c ^= c >>  1;
     212         126 :     return c & 1;
     213             :   }
     214          98 :   else return F2x_coeff(P,0);
     215             : }
     216             : 
     217             : GEN
     218    30615462 : F2x_add(GEN x, GEN y)
     219             : {
     220             :   long i,lz;
     221             :   GEN z;
     222    30615462 :   long lx=lg(x);
     223    30615462 :   long ly=lg(y);
     224    30615462 :   if (ly>lx) swapspec(x,y, lx,ly);
     225    30615462 :   lz = lx; z = cgetg(lz, t_VECSMALL); z[1]=x[1];
     226    30618164 :   for (i=2; i<ly; i++) z[i] = x[i]^y[i];
     227    30618164 :   for (   ; i<lx; i++) z[i] = x[i];
     228    30618164 :   return F2x_renormalize(z, lz);
     229             : }
     230             : 
     231             : static GEN
     232       43011 : F2x_addspec(GEN x, GEN y, long lx, long ly)
     233             : {
     234             :   long i,lz;
     235             :   GEN z;
     236             : 
     237       43011 :   if (ly>lx) swapspec(x,y, lx,ly);
     238       43011 :   lz = lx+2; z = cgetg(lz, t_VECSMALL) + 2;
     239      141027 :   for (i=0; i<ly-3; i+=4)
     240             :   {
     241       98016 :     z[i] = x[i]^y[i];
     242       98016 :     z[i+1] = x[i+1]^y[i+1];
     243       98016 :     z[i+2] = x[i+2]^y[i+2];
     244       98016 :     z[i+3] = x[i+3]^y[i+3];
     245             :   }
     246       71846 :   for (; i<ly; i++)
     247       28835 :     z[i] = x[i]^y[i];
     248       43011 :   for (   ; i<lx; i++) z[i] = x[i];
     249       43011 :   z -= 2; return F2x_renormalize(z, lz);
     250             : }
     251             : 
     252             : GEN
     253      189392 : F2x_1_add(GEN y)
     254             : {
     255             :   GEN z;
     256             :   long lz, i;
     257      189392 :   if (!lgpol(y))
     258       90174 :     return pol1_F2x(y[1]);
     259       99218 :   lz=lg(y);
     260       99218 :   z=cgetg(lz,t_VECSMALL);
     261       99218 :   z[1] = y[1];
     262       99218 :   z[2] = y[2]^1UL;
     263       99218 :   for(i=3;i<lz;i++)
     264           0 :     z[i] = y[i];
     265       99218 :   if (lz==3) z = F2x_renormalize(z,lz);
     266       99218 :   return z;
     267             : }
     268             : 
     269             : INLINE void
     270   192973075 : F2x_addshiftipspec(GEN x, GEN y, long ny, ulong db)
     271             : {
     272             :   long i;
     273   192973075 :   if (db)
     274             :   {
     275   165677869 :     ulong dc=BITS_IN_LONG-db;
     276   165677869 :     ulong r=0, yi;
     277   254406642 :     for(i=0; i<ny-3; i+=4)
     278             :     {
     279    88728773 :       yi = uel(y,i);   x[i]   ^= (yi<<db)|r; r = yi>>dc;
     280    88728773 :       yi = uel(y,i+1); x[i+1] ^= (yi<<db)|r; r = yi>>dc;
     281    88728773 :       yi = uel(y,i+2); x[i+2] ^= (yi<<db)|r; r = yi>>dc;
     282    88728773 :       yi = uel(y,i+3); x[i+3] ^= (yi<<db)|r; r = yi>>dc;
     283             :     }
     284   328968158 :     for(  ; i<ny; i++)
     285             :     {
     286   163290289 :       ulong yi = uel(y,i); x[i] ^= (yi<<db)|r; r = yi>>dc;
     287             :     }
     288   165677869 :     if (r) x[i] ^= r;
     289             :   }
     290             :   else
     291             :   {
     292    31617463 :     for(i=0; i<ny-3; i+=4)
     293             :     {
     294     4322257 :       x[i]   ^= y[i];
     295     4322257 :       x[i+1] ^= y[i+1];
     296     4322257 :       x[i+2] ^= y[i+2];
     297     4322257 :       x[i+3] ^= y[i+3];
     298             :     }
     299    57975281 :     for(   ; i<ny; i++)
     300    30680075 :       x[i] ^= y[i];
     301             :   }
     302   192973075 : }
     303             : 
     304             : INLINE void
     305   159700791 : F2x_addshiftip(GEN x, GEN y, ulong d)
     306             : {
     307   159700791 :   ulong db, dl=dvmduBIL(d, &db);
     308   158877870 :   F2x_addshiftipspec(x+2+dl, y+2, lgpol(y), db);
     309   159682154 : }
     310             : 
     311             : static GEN
     312    17464318 : F2x_mul1(ulong x, ulong y)
     313             : {
     314    17464318 :   ulong x1=(x&HIGHMASK)>>BITS_IN_HALFULONG;
     315    17464318 :   ulong x2=x&LOWMASK;
     316    17464318 :   ulong y1=(y&HIGHMASK)>>BITS_IN_HALFULONG;
     317    17464318 :   ulong y2=y&LOWMASK;
     318             :   ulong r1,r2,rr;
     319             :   GEN z;
     320             :   ulong i;
     321    17464318 :   rr=r1=r2=0UL;
     322    17464318 :   if (x2)
     323   539998091 :     for(i=0;i<BITS_IN_HALFULONG;i++)
     324   522559370 :       if (x2&(1UL<<i))
     325             :       {
     326    45538358 :         r2^=y2<<i;
     327    45538358 :         rr^=y1<<i;
     328             :       }
     329    17464318 :   if (x1)
     330     2646220 :     for(i=0;i<BITS_IN_HALFULONG;i++)
     331     2560923 :       if (x1&(1UL<<i))
     332             :       {
     333      811205 :         r1^=y1<<i;
     334      811205 :         rr^=y2<<i;
     335             :       }
     336    17464318 :   r2^=(rr&LOWMASK)<<BITS_IN_HALFULONG;
     337    17464318 :   r1^=(rr&HIGHMASK)>>BITS_IN_HALFULONG;
     338    17464318 :   z=cgetg((r1?4:3),t_VECSMALL);
     339    17464287 :   z[2]=r2;
     340    17464287 :   if (r1) z[3]=r1;
     341    17464287 :   return z;
     342             : }
     343             : 
     344             : static GEN
     345     5090670 : F2x_mulspec_basecase(GEN x, GEN y, long nx, long ny)
     346             : {
     347             :   long l, i, j;
     348             :   GEN z;
     349     5090670 :   l = nx + ny;
     350     5090670 :   z = zero_Flv(l+1);
     351     5756806 :   for(i=0; i < ny-1; i++)
     352             :   {
     353      667356 :     GEN zi = z+2+i;
     354      667356 :     ulong yi = uel(y,i);
     355      667356 :     if (yi)
     356    37474008 :       for(j=0; j < BITS_IN_LONG; j++)
     357    36806878 :         if (yi&(1UL<<j)) F2x_addshiftipspec(zi,x,nx,j);
     358             :   }
     359             :   {
     360     5089450 :     GEN zi = z+2+i;
     361     5089450 :     ulong yi = uel(y,i);
     362     5089450 :     long c = BITS_IN_LONG-bfffo(yi);
     363    32902065 :     for(j=0; j < c; j++)
     364    27811382 :       if (yi&(1UL<<j)) F2x_addshiftipspec(zi,x,nx,j);
     365             :   }
     366     5090683 :   return F2x_renormalize(z, l+2);
     367             : }
     368             : 
     369             : static GEN
     370       26771 : F2x_addshift(GEN x, GEN y, long d)
     371             : {
     372       26771 :   GEN xd,yd,zd = (GEN)avma;
     373       26771 :   long a,lz,ny = lgpol(y), nx = lgpol(x);
     374       26771 :   long vs = x[1];
     375             : 
     376       26771 :   x += 2; y += 2; a = ny-d;
     377       26771 :   if (a <= 0)
     378             :   {
     379        1252 :     lz = (a>nx)? ny+2: nx+d+2;
     380        1252 :     (void)new_chunk(lz); xd = x+nx; yd = y+ny;
     381        1252 :     while (xd > x) *--zd = *--xd;
     382        1252 :     x = zd + a;
     383        1252 :     while (zd > x) *--zd = 0;
     384             :   }
     385             :   else
     386             :   {
     387       25519 :     xd = new_chunk(d); yd = y+d;
     388       25519 :     x = F2x_addspec(x,yd,nx,a);
     389       25519 :     lz = (a>nx)? ny+2: lg(x)+d;
     390       25519 :     x += 2; while (xd > x) *--zd = *--xd;
     391             :   }
     392       26771 :   while (yd > y) *--zd = *--yd;
     393       26771 :   *--zd = vs;
     394       26771 :   *--zd = evaltyp(t_VECSMALL) | evallg(lz); return zd;
     395             : }
     396             : 
     397             : /* shift polynomial + gerepile */
     398             : /* Do not set evalvarn. Cf Flx_shiftip */
     399             : static GEN
     400    22572951 : F2x_shiftip(pari_sp av, GEN x, long v)
     401             : {
     402    22572951 :   long i, lx = lg(x), ly;
     403             :   GEN y;
     404    22572951 :   if (!v || lx==2) return gerepileuptoleaf(av, x);
     405       23589 :   ly = lx + v;
     406       23589 :   (void)new_chunk(ly); /* check that result fits */
     407       23589 :   x += lx; y = (GEN)av;
     408       23589 :   for (i = 2; i<lx; i++) *--y = *--x;
     409       23589 :   for (i = 0; i< v; i++) *--y = 0;
     410       23589 :   y -= 2; y[0] = evaltyp(t_VECSMALL) | evallg(ly);
     411       23588 :   avma = (pari_sp)y; return y;
     412             : }
     413             : 
     414             : /* fast product (Karatsuba) of polynomials a,b. These are not real GENs, a+2,
     415             :  * b+2 were sent instead. na, nb = number of terms of a, b.
     416             :  * Only c, c0, c1, c2 are genuine GEN.
     417             :  */
     418             : static GEN
     419    26801865 : F2x_mulspec(GEN a, GEN b, long na, long nb)
     420             : {
     421             :   GEN a0,c,c0;
     422    26801865 :   long n0, n0a, i, v = 0;
     423             :   pari_sp av;
     424             : 
     425    26801865 :   while (na && !a[0]) { a++; na-=1; v++; }
     426    26801865 :   while (nb && !b[0]) { b++; nb-=1; v++; }
     427    26801865 :   if (na < nb) swapspec(a,b, na,nb);
     428    26801865 :   if (!nb) return pol0_F2x(0);
     429             : 
     430    22572991 :   av = avma;
     431    22572991 :   if (na == 1)
     432    17464298 :     return F2x_shiftip(av, F2x_mul1(*a,*b), v);
     433     5108693 :   if (na < F2x_MUL_KARATSUBA_LIMIT)
     434     5090668 :     return F2x_shiftip(av, F2x_mulspec_basecase(a, b, na, nb), v);
     435       18025 :   i=(na>>1); n0=na-i; na=i;
     436       18025 :   a0=a+n0; n0a=n0;
     437       18025 :   while (n0a && !a[n0a-1]) n0a--;
     438             : 
     439       18025 :   if (nb > n0)
     440             :   {
     441             :     GEN b0,c1,c2;
     442             :     long n0b;
     443             : 
     444        8746 :     nb -= n0; b0 = b+n0; n0b = n0;
     445        8746 :     while (n0b && !b[n0b-1]) n0b--;
     446        8746 :     c =  F2x_mulspec(a,b,n0a,n0b);
     447        8746 :     c0 = F2x_mulspec(a0,b0,na,nb);
     448             : 
     449        8746 :     c2 = F2x_addspec(a0,a,na,n0a);
     450        8746 :     c1 = F2x_addspec(b0,b,nb,n0b);
     451             : 
     452        8746 :     c1 = F2x_mul(c1,c2);
     453        8746 :     c2 = F2x_add(c0,c);
     454             : 
     455        8746 :     c2 = F2x_add(c1,c2);
     456        8746 :     c0 = F2x_addshift(c0,c2,n0);
     457             :   }
     458             :   else
     459             :   {
     460        9279 :     c  = F2x_mulspec(a,b,n0a,nb);
     461        9279 :     c0 = F2x_mulspec(a0,b,na,nb);
     462             :   }
     463       18025 :   c0 = F2x_addshift(c0,c,n0);
     464       18025 :   return F2x_shiftip(av,c0, v);
     465             : }
     466             : 
     467             : GEN
     468    26765775 : F2x_mul(GEN x, GEN y)
     469             : {
     470    26765775 :   GEN z = F2x_mulspec(x+2,y+2, lgpol(x),lgpol(y));
     471    26765801 :   z[1] = x[1]; return z;
     472             : }
     473             : 
     474             : GEN
     475     8968603 : F2x_sqr(GEN x)
     476             : {
     477     8968603 :   const ulong sq[]={0,1,4,5,16,17,20,21,64,65,68,69,80,81,84,85};
     478             :   long i,ii,j,jj;
     479     8968603 :   long lx=lg(x), lz=2+((lx-2)<<1);
     480             :   GEN z;
     481     8968603 :   z = cgetg(lz, t_VECSMALL); z[1]=x[1];
     482    18234187 :   for (j=2,jj=2;j<lx;j++,jj++)
     483             :   {
     484     9251783 :     ulong x1=((ulong)x[j]&HIGHMASK)>>BITS_IN_HALFULONG;
     485     9251783 :     ulong x2=(ulong)x[j]&LOWMASK;
     486     9251783 :     z[jj]=0;
     487     9251783 :     if (x2)
     488    76867975 :       for(i=0,ii=0;i<BITS_IN_HALFULONG;i+=4,ii+=8)
     489    67700112 :         z[jj]|=sq[(x2>>i)&15UL]<<ii;
     490     9251783 :     z[++jj]=0;
     491     9251783 :     if (x1)
     492    10181538 :       for(i=0,ii=0;i<BITS_IN_HALFULONG;i+=4,ii+=8)
     493     8872989 :         z[jj]|=sq[(x1>>i)&15UL]<<ii;
     494             :   }
     495     8982404 :   return F2x_renormalize(z, lz);
     496             : }
     497             : 
     498             : static GEN
     499      220922 : F2x_pow2n(GEN x, long n)
     500             : {
     501             :   long i;
     502      662815 :   for(i=1;i<=n;i++)
     503      441865 :     x = F2x_sqr(x);
     504      220950 :   return x;
     505             : }
     506             : 
     507             : int
     508       35813 : F2x_issquare(GEN x)
     509             : {
     510       35813 :   const ulong mask = (ULONG_MAX/3UL)*2;
     511       35813 :   ulong i, lx = lg(x);
     512       71612 :   for (i=2; i<lx; i++)
     513       35813 :     if ((x[i]&mask)) return 0;
     514       35799 :   return 1;
     515             : }
     516             : 
     517             : /* Assume x is a perfect square */
     518             : GEN
     519       80978 : F2x_sqrt(GEN x)
     520             : {
     521       80978 :   const ulong sq[]={0,1,4,5,2,3,6,7,8,9,12,13,10,11,14,15};
     522             :   long i,ii,j,jj;
     523       80978 :   long lx=lg(x), lz=2+((lx-1)>>1);
     524             :   GEN z;
     525       80978 :   z = cgetg(lz, t_VECSMALL); z[1]=x[1];
     526      161979 :   for (j=2,jj=2;jj<lz;j++,jj++)
     527             :   {
     528       81001 :     ulong x2=x[j++];
     529       81001 :     z[jj]=0;
     530       81001 :     if (x2)
     531      683289 :       for(i=0,ii=0;ii<BITS_IN_HALFULONG;i+=8,ii+=4)
     532             :       {
     533      602288 :         ulong rl = (x2>>i)&15UL, rh = (x2>>(i+4))&15UL;
     534      602288 :         z[jj]|=sq[rl|(rh<<1)]<<ii;
     535             :       }
     536       81001 :     if (j<lx)
     537             :     {
     538         256 :       x2 = x[j];
     539         256 :       if (x2)
     540        1757 :         for(i=0,ii=0;ii<BITS_IN_HALFULONG;i+=8,ii+=4)
     541             :         {
     542        1516 :           ulong rl = (x2>>i)&15UL, rh = (x2>>(i+4))&15UL;
     543        1516 :           z[jj]|=(sq[rl|(rh<<1)]<<ii)<<BITS_IN_HALFULONG;
     544             :         }
     545             :     }
     546             :   }
     547       80978 :   return F2x_renormalize(z, lz);
     548             : }
     549             : 
     550             : static GEN
     551        1742 : F2x_shiftneg(GEN y, ulong d)
     552             : {
     553        1742 :   long db, dl=dvmdsBIL(d, &db);
     554        1742 :   long i, ly = lg(y), lx = ly-dl;
     555        1742 :   GEN x = cgetg(lx, t_VECSMALL);
     556        1742 :   x[1] = y[1];
     557        1742 :   if (db)
     558             :   {
     559        1742 :     ulong dc=BITS_IN_LONG-db;
     560        1742 :     ulong r=0;
     561        3484 :     for(i=lx-1; i>=2; i--)
     562             :     {
     563        1742 :       x[i] = (((ulong)y[i+dl])>>db)|r;
     564        1742 :       r = ((ulong)y[i+dl])<<dc;
     565             :     }
     566             :   }
     567             :   else
     568           0 :     for(i=2; i<lx; i++)
     569           0 :       x[i] = y[i+dl];
     570        1742 :   return F2x_renormalize(x,lx);
     571             : }
     572             : 
     573             : static GEN
     574      321219 : F2x_shiftpos(GEN y, ulong d)
     575             : {
     576      321219 :   long db, dl=dvmdsBIL(d, &db);
     577      321164 :   long i, ly = lg(y), lx = ly+dl+(!!db);
     578      321164 :   GEN x = cgetg(lx, t_VECSMALL);
     579      321219 :   x[1] = y[1]; for(i=0; i<dl; i++) x[i+2] = 0;
     580      321219 :   if (db)
     581             :   {
     582      321205 :     ulong dc=BITS_IN_LONG-db;
     583      321205 :     ulong r=0;
     584      651311 :     for(i=2; i<ly; i++)
     585             :     {
     586      330106 :       x[i+dl] = (((ulong)y[i])<<db)|r;
     587      330106 :       r = ((ulong)y[i])>>dc;
     588             :     }
     589      321205 :     x[i+dl] = r;
     590             :   }
     591             :   else
     592          28 :     for(i=2; i<ly; i++)
     593          14 :       x[i+dl] = y[i];
     594      321219 :   return F2x_renormalize(x,lx);
     595             : }
     596             : 
     597             : GEN
     598      322961 : F2x_shift(GEN y, long d)
     599             : {
     600      322961 :   return d<0 ? F2x_shiftneg(y,-d): F2x_shiftpos(y,d);
     601             : }
     602             : 
     603             : GEN
     604         784 : F2x_get_red(GEN T)
     605             : {
     606         784 :   return T;
     607             : }
     608             : 
     609             : /* separate from F2x_divrem for maximal speed. */
     610             : GEN
     611    57511972 : F2x_rem(GEN x, GEN y)
     612             : {
     613             :   long dx,dy;
     614    57511972 :   long lx=lg(x);
     615    57511972 :   dy = F2x_degree(y); if (!dy) return pol0_F2x(x[1]);
     616    54965913 :   dx = F2x_degree_lg(x,lx);
     617    54785013 :   x  = F2x_copy(x);
     618   244014625 :   while (dx>=dy)
     619             :   {
     620   133962687 :     F2x_addshiftip(x,y,dx-dy);
     621   133981053 :     while (lx>2 && x[lx-1]==0) lx--;
     622   133981053 :     dx = F2x_degree_lg(x,lx);
     623             :   }
     624    54955285 :   return F2x_renormalize(x, lx);
     625             : }
     626             : 
     627             : GEN
     628    13328513 : F2x_divrem(GEN x, GEN y, GEN *pr)
     629             : {
     630    13328513 :   long dx, dy, dz, lx = lg(x), vs = x[1];
     631             :   GEN z;
     632             : 
     633    13328513 :   dy = F2x_degree(y);
     634    13325880 :   if (dy<0) pari_err_INV("F2x_divrem",y);
     635    13329424 :   if (pr == ONLY_REM) return F2x_rem(x, y);
     636    13329424 :   if (!dy)
     637             :   {
     638     3625152 :     z = F2x_copy(x);
     639     3626821 :     if (pr && pr != ONLY_DIVIDES) *pr = pol0_F2x(vs);
     640     3626821 :     return z;
     641             :   }
     642     9704272 :   dx = F2x_degree_lg(x,lx);
     643     9704248 :   dz = dx-dy;
     644     9704248 :   if (dz < 0)
     645             :   {
     646           0 :     if (pr == ONLY_DIVIDES) return dx < 0? F2x_copy(x): NULL;
     647           0 :     z = pol0_F2x(vs);
     648           0 :     if (pr) *pr = F2x_copy(x);
     649           0 :     return z;
     650             :   }
     651     9704248 :   z = zero_zv(lg(x)-lg(y)+2); z[1] = vs;
     652     9704312 :   x = F2x_copy(x);
     653    43433439 :   while (dx>=dy)
     654             :   {
     655    24024950 :     F2x_set(z,dx-dy);
     656    24030753 :     F2x_addshiftip(x,y,dx-dy);
     657    24029754 :     while (lx>2 && x[lx-1]==0) lx--;
     658    24029754 :     dx = F2x_degree_lg(x,lx);
     659             :   }
     660     9704127 :   z = F2x_renormalize(z, lg(z));
     661     9704361 :   if (!pr) { cgiv(x); return z; }
     662     9023642 :   x = F2x_renormalize(x, lx);
     663     9023643 :   if (pr == ONLY_DIVIDES) {
     664           0 :     if (lg(x) == 2) { cgiv(x); return z; }
     665           0 :     avma = (pari_sp)(z + lg(z)); return NULL;
     666             :   }
     667     9023643 :   *pr = x; return z;
     668             : }
     669             : 
     670             : long
     671       57211 : F2x_valrem(GEN x, GEN *Z)
     672             : {
     673       57211 :   long v, v2, i, l=lg(x);
     674             :   GEN y;
     675       57211 :   if (l==2) { *Z = F2x_copy(x); return LONG_MAX; }
     676       57211 :   for (i=2; i<l && x[i]==0; i++) /*empty*/;
     677       57211 :   v = i-2;
     678       57211 :   v2 = (i < l)? vals(x[i]): 0;
     679       57211 :   if (v+v2 == 0) { *Z = x; return 0; }
     680       18639 :   l -= i-2;
     681       18639 :   y = cgetg(l, t_VECSMALL); y[1] = x[1];
     682       18639 :   if (v2 == 0)
     683          89 :     for (i=2; i<l; i++) y[i] = x[i+v];
     684       18550 :   else if (l == 3)
     685       18543 :     y[2] = ((ulong)x[2+v]) >> v2;
     686             :   else
     687             :   {
     688           7 :     const ulong sh = BITS_IN_LONG - v2;
     689           7 :     ulong r = x[2+v];
     690          14 :     for (i=3; i<l; i++)
     691             :     {
     692           7 :       y[i-1] = (x[i+v] << sh) | (r >> v2);
     693           7 :       r = x[i+v];
     694             :     }
     695           7 :     y[l-1] = r >> v2;
     696           7 :     (void)F2x_renormalize(y,l);
     697             :   }
     698       18639 :   *Z = y; return (v << TWOPOTBITS_IN_LONG) + v2;
     699             : }
     700             : 
     701             : GEN
     702           0 : F2x_deflate(GEN x, long d)
     703             : {
     704             :   GEN y;
     705           0 :   long i,id, dy, dx = F2x_degree(x);
     706           0 :   if (d <= 1) return F2x_copy(x);
     707           0 :   if (dx < 0) return F2x_copy(x);
     708           0 :   dy = dx/d; /* dy+1 coefficients + 1 extra word for variable */
     709           0 :   y = zero_zv(nbits2lg(dy+1)-1); y[1] = x[1];
     710           0 :   for (i=id=0; i<=dy; i++,id+=d)
     711           0 :     if (F2x_coeff(x,id)) F2x_set(y, i);
     712           0 :   return y;
     713             : }
     714             : 
     715             : /* write p(X) = e(X^2) + Xo(X^2), shallow function */
     716             : void
     717       60196 : F2x_even_odd(GEN p, GEN *pe, GEN *po)
     718             : {
     719       60196 :   long n = F2x_degree(p), n0, n1, i;
     720             :   GEN p0, p1;
     721             : 
     722      120398 :   if (n <= 0) { *pe = F2x_copy(p); *po = pol0_F2x(p[1]); return; }
     723             : 
     724       57468 :   n0 = (n>>1)+1; n1 = n+1 - n0; /* n1 <= n0 <= n1+1 */
     725       57468 :   p0 = zero_zv(nbits2lg(n0+1)-1); p0[1] = p[1];
     726       57465 :   p1 = zero_zv(nbits2lg(n1+1)-1); p1[1] = p[1];
     727     2270155 :   for (i=0; i<n1; i++)
     728             :   {
     729     2212685 :     if (F2x_coeff(p,i<<1)) F2x_set(p0,i);
     730     2213051 :     if (F2x_coeff(p,1+(i<<1))) F2x_set(p1,i);
     731             :   }
     732       57470 :   if (n1 != n0 && F2x_coeff(p,i<<1)) F2x_set(p0,i);
     733       57471 :   *pe = F2x_renormalize(p0,lg(p0));
     734       57468 :   *po = F2x_renormalize(p1,lg(p1));
     735             : }
     736             : 
     737             : GEN
     738      876997 : F2x_deriv(GEN z)
     739             : {
     740      876997 :   const ulong mask = ULONG_MAX/3UL;
     741      876997 :   long i,l = lg(z);
     742      876997 :   GEN x = cgetg(l, t_VECSMALL); x[1] = z[1];
     743      877026 :   for (i=2; i<l; i++) x[i] = (((ulong)z[i])>>1)&mask;
     744      877026 :   return F2x_renormalize(x,l);
     745             : }
     746             : 
     747             : GEN
     748     3274454 : F2x_gcd(GEN a, GEN b)
     749             : {
     750     3274454 :   pari_sp av = avma;
     751     3274454 :   if (lg(b) > lg(a)) swap(a, b);
     752    34119549 :   while (lgpol(b))
     753             :   {
     754    27533813 :     GEN c = F2x_rem(a,b);
     755    27570641 :     a = b; b = c;
     756    27570641 :     if (gc_needed(av,2))
     757             :     {
     758           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2x_gcd (d = %ld)",F2x_degree(c));
     759           0 :       gerepileall(av,2, &a,&b);
     760             :     }
     761             :   }
     762     3273187 :   if (gc_needed(av,2)) a = gerepileuptoleaf(av, a);
     763     3273187 :   return a;
     764             : }
     765             : 
     766             : GEN
     767     1310813 : F2x_extgcd(GEN a, GEN b, GEN *ptu, GEN *ptv)
     768             : {
     769     1310813 :   pari_sp av=avma;
     770             :   GEN u,v,d,d1,v1;
     771     1310813 :   long vx = a[1];
     772     1310813 :   d = a; d1 = b;
     773     1310813 :   v = pol0_F2x(vx); v1 = pol1_F2x(vx);
     774    12942941 :   while (lgpol(d1))
     775             :   {
     776    10321316 :     GEN r, q = F2x_divrem(d,d1, &r);
     777    10321315 :     v = F2x_add(v,F2x_mul(q,v1));
     778    10321314 :     u=v; v=v1; v1=u;
     779    10321314 :     u=r; d=d1; d1=u;
     780    10321314 :     if (gc_needed(av,2))
     781             :     {
     782           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2x_extgcd (d = %ld)",F2x_degree(d));
     783           0 :       gerepileall(av,5, &d,&d1,&u,&v,&v1);
     784             :     }
     785             :   }
     786     1310813 :   if (ptu) *ptu = F2x_div(F2x_add(d, F2x_mul(b,v)), a);
     787     1310813 :   *ptv = v;
     788     1310813 :   if (gc_needed(av,2)) gerepileall(av,ptu?3:2,&d,ptv,ptu);
     789     1310813 :   return d;
     790             : }
     791             : 
     792             : static GEN
     793         775 : F2x_halfgcd_i(GEN a, GEN b)
     794             : {
     795         775 :   pari_sp av=avma;
     796             :   GEN u,u1,v,v1;
     797         775 :   long vx = a[1];
     798         775 :   long n = (F2x_degree(a)+1)>>1;
     799         775 :   u1 = v = pol0_F2x(vx);
     800         775 :   u = v1 = pol1_F2x(vx);
     801       13845 :   while (F2x_degree(b)>=n)
     802             :   {
     803       12295 :     GEN r, q = F2x_divrem(a,b, &r);
     804       12295 :     a = b; b = r; swap(u,u1); swap(v,v1);
     805       12295 :     u1 = F2x_add(u1, F2x_mul(u, q));
     806       12295 :     v1 = F2x_add(v1, F2x_mul(v, q));
     807       12295 :     if (gc_needed(av,2))
     808             :     {
     809           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2x_halfgcd (d = %ld)",F2x_degree(b));
     810           0 :       gerepileall(av,6, &a,&b,&u1,&v1,&u,&v);
     811             :     }
     812             :   }
     813         775 :   return gerepilecopy(av, mkmat2(mkcol2(u,u1), mkcol2(v,v1)));
     814             : }
     815             : 
     816             : GEN
     817         775 : F2x_halfgcd(GEN x, GEN y)
     818             : {
     819             :   pari_sp av;
     820             :   GEN M,q,r;
     821         775 :   if (F2x_degree(y)<F2x_degree(x)) return F2x_halfgcd_i(x,y);
     822         775 :   av = avma;
     823         775 :   q = F2x_divrem(y,x,&r);
     824         775 :   M = F2x_halfgcd_i(x,r);
     825         775 :   gcoeff(M,1,1) = F2x_add(gcoeff(M,1,1), F2x_mul(q, gcoeff(M,1,2)));
     826         775 :   gcoeff(M,2,1) = F2x_add(gcoeff(M,2,1), F2x_mul(q, gcoeff(M,2,2)));
     827         775 :   return gerepilecopy(av, M);
     828             : }
     829             : 
     830             : GEN
     831     8691921 : F2xq_mul(GEN x,GEN y,GEN pol)
     832             : {
     833     8691921 :   GEN z = F2x_mul(x,y);
     834     8691985 :   return F2x_rem(z,pol);
     835             : }
     836             : 
     837             : GEN
     838     8527997 : F2xq_sqr(GEN x,GEN pol)
     839             : {
     840     8527997 :   GEN z = F2x_sqr(x);
     841     8531778 :   return F2x_rem(z,pol);
     842             : }
     843             : 
     844             : GEN
     845     1310813 : F2xq_invsafe(GEN x, GEN T)
     846             : {
     847     1310813 :   GEN V, z = F2x_extgcd(T, x, NULL, &V);
     848     1310813 :   if (F2x_degree(z)) return NULL;
     849     1310743 :   return V;
     850             : }
     851             : 
     852             : GEN
     853     1310806 : F2xq_inv(GEN x,GEN T)
     854             : {
     855     1310806 :   pari_sp av=avma;
     856     1310806 :   GEN U = F2xq_invsafe(x, T);
     857     1310806 :   if (!U) pari_err_INV("F2xq_inv", F2x_to_ZX(x));
     858     1310736 :   return gerepileuptoleaf(av, U);
     859             : }
     860             : 
     861             : GEN
     862      528437 : F2xq_div(GEN x,GEN y,GEN T)
     863             : {
     864      528437 :   pari_sp av = avma;
     865      528437 :   return gerepileuptoleaf(av, F2xq_mul(x,F2xq_inv(y,T),T));
     866             : }
     867             : 
     868             : static GEN
     869      559748 : _F2xq_red(void *E, GEN x)
     870      559748 : { return F2x_rem(x, (GEN)E); }
     871             : static GEN
     872     1636852 : _F2xq_add(void *E, GEN x, GEN y)
     873     1636852 : { (void)E; return F2x_add(x,y); }
     874             : 
     875             : static GEN
     876     2026019 : _F2xq_cmul(void *E, GEN P, long a, GEN x)
     877             : {
     878     2026019 :   GEN pol = (GEN) E;
     879     2026019 :   return F2x_coeff(P,a) ? x: pol0_F2x(pol[1]);
     880             : }
     881             : static GEN
     882     1135641 : _F2xq_sqr(void *E, GEN x)
     883     1135641 : { return F2xq_sqr(x, (GEN) E); }
     884             : 
     885             : static GEN
     886     1406706 : _F2xq_mul(void *E, GEN x, GEN y)
     887     1406706 : { return F2xq_mul(x,y, (GEN) E); }
     888             : 
     889             : static GEN
     890      902309 : _F2xq_one(void *E)
     891             : {
     892      902309 :   GEN pol = (GEN) E;
     893      902309 :   return pol1_F2x(pol[1]);
     894             : }
     895             : static GEN
     896      259847 : _F2xq_zero(void *E)
     897             : {
     898      259847 :   GEN pol = (GEN) E;
     899      259847 :   return pol0_F2x(pol[1]);
     900             : }
     901             : 
     902             : GEN
     903      413766 : F2xq_pow(GEN x, GEN n, GEN pol)
     904             : {
     905      413766 :   pari_sp av=avma;
     906             :   GEN y;
     907             : 
     908      413766 :   if (!signe(n)) return pol1_F2x(x[1]);
     909      406010 :   if (is_pm1(n)) /* +/- 1 */
     910      204185 :     return (signe(n) < 0)? F2xq_inv(x,pol): F2x_copy(x);
     911             : 
     912      201825 :   if (signe(n) < 0) x = F2xq_inv(x,pol);
     913      201825 :   y = gen_pow(x, n, (void*)pol, &_F2xq_sqr, &_F2xq_mul);
     914      201825 :   return gerepileupto(av, y);
     915             : }
     916             : 
     917             : GEN
     918           0 : F2xq_powu(GEN x, ulong n, GEN pol)
     919             : {
     920           0 :   pari_sp av=avma;
     921             :   GEN y;
     922           0 :   switch(n)
     923             :   {
     924           0 :     case 0: return pol1_F2x(x[1]);
     925           0 :     case 1: return F2x_copy(x);
     926           0 :     case 2: return F2xq_sqr(x,pol);
     927             :   }
     928           0 :   y = gen_powu(x, n, (void*)pol, &_F2xq_sqr, &_F2xq_mul);
     929           0 :   return gerepileupto(av, y);
     930             : }
     931             : 
     932             : /* generates the list of powers of x of degree 0,1,2,...,l*/
     933             : GEN
     934      361706 : F2xq_powers(GEN x, long l, GEN T)
     935             : {
     936      361706 :   int use_sqr = 2*F2x_degree(x) >= F2x_degree(T);
     937      361706 :   return gen_powers(x, l, use_sqr, (void*)T, &_F2xq_sqr, &_F2xq_mul, &_F2xq_one);
     938             : }
     939             : 
     940             : GEN
     941      232052 : F2xq_matrix_pow(GEN y, long n, long m, GEN P)
     942             : {
     943      232052 :   return F2xV_to_F2m(F2xq_powers(y,m-1,P),n);
     944             : }
     945             : 
     946             : GEN
     947      329729 : F2x_Frobenius(GEN T)
     948             : {
     949      329729 :   return F2xq_sqr(polx_F2x(T[1]), T);
     950             : }
     951             : 
     952             : GEN
     953      232052 : F2x_matFrobenius(GEN T)
     954             : {
     955      232052 :   long n = F2x_degree(T);
     956      232052 :   return F2xq_matrix_pow(F2x_Frobenius(T), n, n, T);
     957             : }
     958             : 
     959             : static struct bb_algebra F2xq_algebra = { _F2xq_red, _F2xq_add, _F2xq_add,
     960             :               _F2xq_mul, _F2xq_sqr, _F2xq_one, _F2xq_zero};
     961             : 
     962             : GEN
     963      610911 : F2x_F2xqV_eval(GEN Q, GEN x, GEN T)
     964             : {
     965      610911 :   long d = F2x_degree(Q);
     966      610911 :   return gen_bkeval_powers(Q,d,x,(void*)T,&F2xq_algebra,_F2xq_cmul);
     967             : }
     968             : 
     969             : GEN
     970       39668 : F2x_F2xq_eval(GEN Q, GEN x, GEN T)
     971             : {
     972       39668 :   long d = F2x_degree(Q);
     973       39667 :   int use_sqr = 2*F2x_degree(x) >= F2x_degree(T);
     974       39668 :   return gen_bkeval(Q, d, x, use_sqr, (void*)T, &F2xq_algebra, _F2xq_cmul);
     975             : }
     976             : 
     977             : static GEN
     978       25228 : F2xq_autpow_sqr(void * T, GEN x) { return F2x_F2xq_eval(x, x, (GEN) T); }
     979             : 
     980             : static GEN
     981       14412 : F2xq_autpow_mul(void * T, GEN x, GEN y) { return F2x_F2xq_eval(x, y, (GEN) T); }
     982             : 
     983             : GEN
     984       15449 : F2xq_autpow(GEN x, long n, GEN T)
     985             : {
     986       15449 :   return gen_powu(x,n,(void*)T,F2xq_autpow_sqr,F2xq_autpow_mul);
     987             : }
     988             : 
     989             : ulong
     990      459781 : F2xq_trace(GEN x, GEN T)
     991             : {
     992      459781 :   pari_sp av = avma;
     993             :   ulong t;
     994      459781 :   long n = F2x_degree(T)-1;
     995      459781 :   GEN z = F2x_mul(x, F2x_deriv(T));
     996      459781 :   z = F2x_rem(z, T);
     997      459781 :   t = F2x_degree(z)<n ? 0 : 1;
     998      459781 :   avma = av; return t;
     999             : }
    1000             : 
    1001             : GEN
    1002           7 : F2xq_conjvec(GEN x, GEN T)
    1003             : {
    1004           7 :   long i, l = F2x_degree(T);
    1005           7 :   GEN z = cgetg(l,t_COL);
    1006           7 :   gel(z,1) = F2x_copy(x);
    1007           7 :   for (i=2; i<l; i++) gel(z,i) = F2xq_sqr(gel(z,i-1), T);
    1008           7 :   return z;
    1009             : }
    1010             : 
    1011             : static GEN
    1012      365259 : _F2xq_pow(void *data, GEN x, GEN n)
    1013             : {
    1014      365259 :   GEN pol = (GEN) data;
    1015      365259 :   return F2xq_pow(x,n, pol);
    1016             : }
    1017             : 
    1018             : static GEN
    1019        9324 : _F2xq_rand(void *data)
    1020             : {
    1021        9324 :   pari_sp av=avma;
    1022        9324 :   GEN pol = (GEN) data;
    1023        9324 :   long d = F2x_degree(pol);
    1024             :   GEN z;
    1025             :   do
    1026             :   {
    1027        9492 :     avma = av;
    1028        9492 :     z = random_F2x(d,pol[1]);
    1029        9492 :   } while (lgpol(z)==0);
    1030        9324 :   return z;
    1031             : }
    1032             : 
    1033             : static GEN F2xq_easylog(void* E, GEN a, GEN g, GEN ord);
    1034             : 
    1035             : static const struct bb_group F2xq_star={_F2xq_mul,_F2xq_pow,_F2xq_rand,hash_GEN,F2x_equal,F2x_equal1,F2xq_easylog};
    1036             : 
    1037             : GEN
    1038         378 : F2xq_order(GEN a, GEN ord, GEN T)
    1039             : {
    1040         378 :   return gen_order(a,ord,(void*)T,&F2xq_star);
    1041             : }
    1042             : 
    1043             : static long
    1044      295068 : F2x_is_smooth_squarefree(GEN f, long r)
    1045             : {
    1046      295068 :   pari_sp av = avma;
    1047             :   long i;
    1048      295068 :   GEN sx = polx_F2x(f[1]), a = sx;
    1049     2794664 :   for(i=1;  ;i++)
    1050             :   {
    1051     2794664 :     a = F2xq_sqr(F2x_rem(a,f),f);
    1052     2793363 :     if (F2x_equal(a, F2x_rem(sx,f))) {avma = av; return 1;}
    1053     2701425 :     if (i==r) {avma = av; return 0;}
    1054     2499651 :     f = F2x_div(f, F2x_gcd(F2x_add(a,sx),f));
    1055     2499585 :   }
    1056             : }
    1057             : 
    1058             : static long
    1059      259302 : F2x_is_smooth(GEN g, long r)
    1060             : {
    1061      259302 :   GEN f = gen_0;
    1062      259302 :   if (lgpol(g)==0) return 0;
    1063             :   while (1)
    1064             :   {
    1065      295075 :     f = F2x_gcd(g, F2x_deriv(g));
    1066      295074 :     if (!F2x_is_smooth_squarefree(F2x_div(g, f), r))
    1067      201781 :       return 0;
    1068       93359 :     if (F2x_degree(f)==0) return 1;
    1069       35785 :     g = F2x_issquare(f) ? F2x_sqrt(f): f;
    1070       35784 :   }
    1071             : }
    1072             : 
    1073             : static GEN
    1074       15173 : F2x_factorel(GEN h)
    1075             : {
    1076       15173 :   GEN F = F2x_factcantor(h, 0);
    1077       15174 :   GEN F1 = gel(F, 1), F2 = gel(F, 2);
    1078       15174 :   long i, l1 = lg(F1)-1;
    1079       15174 :   GEN p2 = cgetg(l1+1, t_VECSMALL);
    1080       15174 :   GEN e2 = cgetg(l1+1, t_VECSMALL);
    1081       71043 :   for (i = 1; i <= l1; ++i)
    1082             :   {
    1083       55869 :     p2[i] = mael(F1, i, 2);
    1084       55869 :     e2[i] = F2[i];
    1085             :   }
    1086       15174 :   return mkmat2(p2, e2);
    1087             : }
    1088             : 
    1089             : static GEN
    1090       23360 : mkF2(ulong x, long v) { return mkvecsmall2(v, x); }
    1091             : 
    1092             : static GEN F2xq_log_Coppersmith_d(GEN W, GEN g, long r, long n, GEN T, GEN mo);
    1093             : 
    1094             : static GEN
    1095         126 : F2xq_log_from_rel(GEN W, GEN rel, long r, long n, GEN T, GEN m)
    1096             : {
    1097         126 :   pari_sp av = avma;
    1098         126 :   GEN F = gel(rel,1), E = gel(rel,2), o = gen_0;
    1099         126 :   long i, l = lg(F);
    1100        1118 :   for(i=1; i<l; i++)
    1101             :   {
    1102         998 :     GEN R = gel(W, F[i]);
    1103         998 :     if (signe(R)==0) /* Already failed */
    1104           0 :       return NULL;
    1105         998 :     else if (signe(R)<0) /* Not yet tested */
    1106             :     {
    1107          13 :       setsigne(gel(W,F[i]),0);
    1108          13 :       R = F2xq_log_Coppersmith_d(W, mkF2(F[i],T[1]), r, n, T, m);
    1109          13 :       if (!R) return NULL;
    1110             :     }
    1111         992 :     o = Fp_add(o, mulis(R, E[i]), m);
    1112             :   }
    1113         120 :   return gerepileuptoint(av, o);
    1114             : }
    1115             : 
    1116             : static GEN
    1117         152 : F2xq_log_Coppersmith_d(GEN W, GEN g, long r, long n, GEN T, GEN mo)
    1118             : {
    1119         152 :   pari_sp av = avma, av2;
    1120         152 :   long dg = F2x_degree(g), k = r-1, m = maxss((dg-k)/2,0);
    1121         152 :   long i, j, l = dg-m, N;
    1122         152 :   GEN v = cgetg(k+m+1,t_MAT);
    1123         152 :   long dT = F2x_degree(T);
    1124         152 :   long h = dT>>n, d = dT-(h<<n);
    1125         152 :   GEN R = F2x_add(F2x_shift(pol1_F2x(T[1]), dT), T);
    1126         152 :   GEN z = F2x_rem(F2x_shift(pol1_F2x(T[1]),h), g);
    1127        1894 :   for(i=1; i<=k+m; i++)
    1128             :   {
    1129        1742 :     gel(v,i) = F2x_to_F2v(F2x_shift(z,-l),m);
    1130        1742 :     z = F2x_rem(F2x_shift(z,1),g);
    1131             :   }
    1132         152 :   v = F2m_ker(v);
    1133        1672 :   for(i=1; i<=k; i++)
    1134        1520 :     gel(v,i) = F2v_to_F2x(gel(v,i),T[1]);
    1135         152 :   N = 1<<k;
    1136         152 :   av2 = avma;
    1137       61000 :   for (i=1; i<N; i++)
    1138             :   {
    1139             :     GEN p,q,qh,a,b;
    1140       60968 :     avma = av2;
    1141       60968 :     q = pol0_F2x(T[1]);
    1142      670648 :     for(j=0; j<k; j++)
    1143      609680 :       if (i&(1UL<<j))
    1144      282497 :         q = F2x_add(q, gel(v,j+1));
    1145       60968 :     qh= F2x_shift(q,h);
    1146       60968 :     p = F2x_rem(qh,g);
    1147       60968 :     b = F2x_add(F2x_mul(R, F2x_pow2n(q, n)), F2x_shift(F2x_pow2n(p, n), d));
    1148       60968 :     if (lgpol(b)==0 || !F2x_is_smooth(b, r)) continue;
    1149         228 :     a = F2x_div(F2x_add(qh,p),g);
    1150         228 :     if (F2x_degree(F2x_gcd(a,q)) &&  F2x_degree(F2x_gcd(a,p))) continue;
    1151         144 :     if (!(lgpol(a)==0 || !F2x_is_smooth(a, r)))
    1152             :     {
    1153         126 :       GEN F = F2x_factorel(b);
    1154         126 :       GEN G = F2x_factorel(a);
    1155         126 :       GEN FG = vecsmall_concat(vecsmall_append(gel(F, 1), 2), gel(G, 1));
    1156         252 :       GEN E  = vecsmall_concat(vecsmall_append(gel(F, 2), -d),
    1157         252 :                                zv_z_mul(gel(G, 2),-(1L<<n)));
    1158         126 :       GEN R  = famatsmall_reduce(mkmat2(FG, E));
    1159         126 :       GEN l  = F2xq_log_from_rel(W, R, r, n, T, mo);
    1160         126 :       if (!l) continue;
    1161         120 :       l = Fp_div(l,int2n(n),mo);
    1162         120 :       if (dg <= r)
    1163             :       {
    1164          20 :         affii(l,gel(W,g[2]));
    1165          20 :         if (DEBUGLEVEL>1) err_printf("Found %lu\n", g[2]);
    1166             :       }
    1167         120 :       return gerepileuptoint(av, l);
    1168             :     }
    1169             :   }
    1170          32 :   avma = av;
    1171          32 :   return NULL;
    1172             : }
    1173             : 
    1174             : static GEN
    1175          90 : F2xq_log_find_rel(GEN b, long r, GEN T, GEN *g, ulong *e)
    1176             : {
    1177          90 :   pari_sp av = avma;
    1178             :   while (1)
    1179             :   {
    1180             :     GEN M;
    1181         775 :     *g = F2xq_mul(*g, b, T); (*e)++;
    1182         775 :     M = F2x_halfgcd(*g,T);
    1183         775 :     if (F2x_is_smooth(gcoeff(M,1,1), r))
    1184             :     {
    1185         255 :       GEN z = F2x_add(F2x_mul(gcoeff(M,1,1),*g), F2x_mul(gcoeff(M,1,2),T));
    1186         255 :       if (F2x_is_smooth(z, r))
    1187             :       {
    1188          90 :         GEN F = F2x_factorel(z);
    1189          90 :         GEN G = F2x_factorel(gcoeff(M,1,1));
    1190         180 :         GEN rel = mkmat2(vecsmall_concat(gel(F, 1),gel(G, 1)),
    1191         180 :                          vecsmall_concat(gel(F, 2),zv_neg(gel(G, 2))));
    1192          90 :         gerepileall(av, 2, g, &rel);
    1193         180 :         return rel;
    1194             :       }
    1195             :     }
    1196         685 :     if (gc_needed(av,2))
    1197             :     {
    1198           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2xq_log_find_rel");
    1199           0 :       *g = gerepileuptoleaf(av, *g);
    1200             :     }
    1201         685 :   }
    1202             : }
    1203             : 
    1204             : static GEN
    1205          28 : F2xq_log_Coppersmith_rec(GEN W, long r2, GEN a, long r, long n, GEN T, GEN m)
    1206             : {
    1207          28 :   GEN b = polx_F2x(T[1]);
    1208          28 :   ulong AV = 0;
    1209          28 :   GEN g = a, bad = pol0_F2x(T[1]);
    1210             :   pari_timer ti;
    1211             :   while(1)
    1212             :   {
    1213             :     long i, l;
    1214             :     GEN V, F, E, Ao;
    1215          90 :     timer_start(&ti);
    1216          90 :     V = F2xq_log_find_rel(b, r2, T, &g, &AV);
    1217          90 :     if (DEBUGLEVEL>1) timer_printf(&ti,"%ld-smooth element",r2);
    1218          90 :     F = gel(V,1); E = gel(V,2);
    1219          90 :     l = lg(F);
    1220          90 :     Ao = gen_0;
    1221         623 :     for(i=1; i<l; i++)
    1222             :     {
    1223         595 :       GEN Fi = mkF2(F[i], T[1]);
    1224             :       GEN R;
    1225         595 :       if (F2x_degree(Fi) <= r)
    1226             :       {
    1227         433 :         if (signe(gel(W,F[i]))==0)
    1228           0 :           break;
    1229         433 :         else if (signe(gel(W,F[i]))<0)
    1230             :         {
    1231          13 :           setsigne(gel(W,F[i]),0);
    1232          13 :           R = F2xq_log_Coppersmith_d(W,Fi,r,n,T,m);
    1233             :         } else
    1234         420 :           R = gel(W,F[i]);
    1235             :       }
    1236             :       else
    1237             :       {
    1238         162 :         if (F2x_equal(Fi,bad)) break;
    1239         126 :         R = F2xq_log_Coppersmith_d(W,Fi,r,n,T,m);
    1240         126 :         if (!R) bad = Fi;
    1241             :       }
    1242         559 :       if (!R) break;
    1243         533 :       Ao = Fp_add(Ao, mulis(R, E[i]), m);
    1244             :     }
    1245         118 :     if (i==l) return subiu(Ao,AV);
    1246          62 :   }
    1247             : }
    1248             : 
    1249             : /* Coppersmith:
    1250             :  T*X^e = X^(h*2^n)-R
    1251             :  (u*x^h + v)^(2^n) = u^(2^n)*X^(h*2^n)+v^(2^n)
    1252             :  (u*x^h + v)^(2^n) = u^(2^n)*R+v^(2^n)
    1253             : */
    1254             : 
    1255             : static GEN
    1256      147592 : rel_Coppersmith(GEN u, GEN v, long h, GEN R, long r, long n, long d)
    1257             : {
    1258             :   GEN b, F, G, M;
    1259      147592 :   GEN a = F2x_add(F2x_shift(u, h), v);
    1260      147688 :   if (!F2x_is_smooth(a, r)) return NULL;
    1261       49506 :   b = F2x_add(F2x_mul(R, F2x_pow2n(u, n)), F2x_shift(F2x_pow2n(v, n),d));
    1262       49509 :   if (!F2x_is_smooth(b, r)) return NULL;
    1263        7370 :   F = F2x_factorel(a);
    1264        7371 :   G = F2x_factorel(b);
    1265       22113 :   M = mkmat2(vecsmall_concat(gel(F, 1), vecsmall_append(gel(G, 1), 2)),
    1266       22113 :              vecsmall_concat(zv_z_mul(gel(F, 2),1UL<<n), vecsmall_append(zv_neg(gel(G, 2)),d)));
    1267        7370 :   return famatsmall_reduce(M);
    1268             : }
    1269             : 
    1270             : GEN
    1271        2042 : F2xq_log_Coppersmith_worker(GEN u, long i, GEN V, GEN R)
    1272             : {
    1273        2042 :   long r = V[1], h = V[2], n = V[3], d = V[4];
    1274        2042 :   pari_sp ltop = avma;
    1275        2042 :   GEN v = mkF2(0,u[1]);
    1276        2039 :   GEN L = cgetg(2*i+1, t_VEC);
    1277        2042 :   pari_sp av = avma;
    1278             :   long j;
    1279        2042 :   long nbtest=0, rel = 1;
    1280      148331 :   for(j=1; j<=i; j++)
    1281             :   {
    1282      146286 :     v[2] = j;
    1283      146286 :     avma = av;
    1284      146286 :     if (F2x_degree(F2x_gcd(u,v))==0)
    1285             :     {
    1286       73863 :       GEN z = rel_Coppersmith(u, v, h, R, r, n, d);
    1287       73867 :       nbtest++;
    1288       73867 :       if (z) { gel(L, rel++) = z; av = avma; }
    1289       73867 :       if (i==j) continue;
    1290       73853 :       z = rel_Coppersmith(v, u, h, R, r, n, d);
    1291       73856 :       nbtest++;
    1292       73856 :       if (z) { gel(L, rel++) = z; av = avma; }
    1293             :     }
    1294             :   }
    1295        2045 :   setlg(L,rel);
    1296        2046 :   return gerepilecopy(ltop, mkvec2(stoi(nbtest), L));
    1297             : }
    1298             : 
    1299             : static GEN
    1300          14 : F2xq_log_Coppersmith(long nbrel, long r, long n, GEN T)
    1301             : {
    1302          14 :   long dT = F2x_degree(T);
    1303          14 :   long h = dT>>n, d = dT-(h<<n);
    1304          14 :   GEN R = F2x_add(F2x_shift(pol1_F2x(T[1]), dT), T);
    1305          14 :   GEN u = mkF2(0,T[1]);
    1306          14 :   long rel = 1, nbtest = 0;
    1307          14 :   GEN M = cgetg(nbrel+1, t_VEC);
    1308          14 :   long i = 0;
    1309          14 :   GEN worker = snm_closure(is_entry("_F2xq_log_Coppersmith_worker"),
    1310             :                mkvec2(mkvecsmall4(r, h, n, d), R));
    1311             :   struct pari_mt pt;
    1312          14 :   long running, pending = 0, stop=0;
    1313          14 :   mt_queue_start(&pt, worker);
    1314          14 :   if (DEBUGLEVEL) err_printf("Coppersmith (R = %ld): ",F2x_degree(R));
    1315        2104 :   while ((running = !stop) || pending)
    1316             :   {
    1317             :     GEN L, done;
    1318             :     long j, l;
    1319        2076 :     u[2] = i;
    1320        2076 :     mt_queue_submit(&pt, 0, running ? mkvec2(u, stoi(i)): NULL);
    1321        2076 :     done = mt_queue_get(&pt, NULL, &pending);
    1322        2076 :     if (!done) continue;
    1323        2046 :     L = gel(done, 2); nbtest += itos(gel(done,1));
    1324        2046 :     l = lg(L);
    1325        2046 :     if (l > 1)
    1326             :     {
    1327        9117 :       for (j=1; j<l; j++)
    1328             :       {
    1329        7244 :         if (rel>nbrel) break;
    1330        7210 :         gel(M,rel++) = gel(L,j);
    1331        7210 :         if (DEBUGLEVEL && (rel&511UL)==0)
    1332           0 :           err_printf("%ld%%[%ld] ",rel*100/nbrel,i);
    1333             :       }
    1334             :     }
    1335        2046 :     if (rel>nbrel) stop=1;
    1336        2046 :     i++;
    1337             :   }
    1338          14 :   mt_queue_end(&pt);
    1339          14 :   if (DEBUGLEVEL) err_printf(": %ld tests\n", nbtest);
    1340          14 :   return M;
    1341             : }
    1342             : 
    1343             : static GEN
    1344          14 : smallirred_F2x(ulong n, long sv)
    1345             : {
    1346          14 :   GEN a = zero_zv(nbits2lg(n+1)-1);
    1347          14 :   a[1] = sv; F2x_set(a,n); a[2]++;
    1348          14 :   while (!F2x_is_irred(a)) a[2]+=2;
    1349          14 :   return a;
    1350             : }
    1351             : 
    1352             : static GEN
    1353          14 : check_kernel(long N, GEN M, long nbi, GEN T, GEN m)
    1354             : {
    1355          14 :   pari_sp av = avma;
    1356          14 :   GEN K = FpMs_leftkernel_elt(M, N, m);
    1357          14 :   long i, f=0;
    1358          14 :   long l = lg(K), lm = lgefint(m);
    1359          14 :   GEN idx = diviiexact(int2um1(F2x_degree(T)),m);
    1360          14 :   GEN g = F2xq_pow(polx_F2x(T[1]), idx, T);
    1361             :   pari_timer ti;
    1362          14 :   if (DEBUGLEVEL) timer_start(&ti);
    1363          14 :   K = FpC_Fp_mul(K, Fp_inv(gel(K,2), m), m);
    1364       57344 :   for(i=1; i<l; i++)
    1365             :   {
    1366       57330 :     GEN k = gel(K,i);
    1367       62576 :     if (signe(k)==0 || !F2x_equal(F2xq_pow(g, k, T),
    1368        5246 :                                   F2xq_pow(mkF2(i,T[1]), idx, T)))
    1369       52084 :       gel(K,i) = cgetineg(lm);
    1370             :     else
    1371        5246 :       f++;
    1372             :   }
    1373          14 :   if (DEBUGLEVEL) timer_printf(&ti,"found %ld/%ld logs", f, nbi);
    1374          14 :   return gerepileupto(av, K);
    1375             : }
    1376             : 
    1377             : static GEN
    1378          14 : F2xq_log_index(GEN a0, GEN b0, GEN m, GEN T0)
    1379             : {
    1380          14 :   pari_sp av = avma;
    1381          14 :   GEN  M, S, a, b, Ao=NULL, Bo=NULL, W, e;
    1382             :   pari_timer ti;
    1383          14 :   long n = F2x_degree(T0), r = (long) (sqrt((double) 2*n))-(n>100);
    1384          14 :   GEN T = smallirred_F2x(n,T0[1]);
    1385          14 :   long d = 2, r2 = 3*r/2, d2 = 2;
    1386          14 :   long N = (1UL<<(r+1))-1UL;
    1387          14 :   long nbi = itos(ffsumnbirred(gen_2, r)), nbrel=nbi*5/4;
    1388          14 :   if (DEBUGLEVEL)
    1389             :   {
    1390           0 :     err_printf("F2xq_log: Parameters r=%ld r2=%ld\n", r,r2);
    1391           0 :     err_printf("F2xq_log: Size FB=%ld rel. needed=%ld\n", nbi, nbrel);
    1392           0 :     timer_start(&ti);
    1393             :   }
    1394          14 :   S = Flx_to_F2x(Flx_ffisom(F2x_to_Flx(T0),F2x_to_Flx(T),2));
    1395          14 :   a = F2x_F2xq_eval(a0, S, T);
    1396          14 :   b = F2x_F2xq_eval(b0, S, T);
    1397          14 :   if (DEBUGLEVEL) timer_printf(&ti,"model change");
    1398          14 :   M = F2xq_log_Coppersmith(nbrel,r,d,T);
    1399          14 :   if(DEBUGLEVEL)
    1400           0 :     timer_printf(&ti,"relations");
    1401          14 :   W = check_kernel(N, M, nbi, T, m);
    1402          14 :   timer_start(&ti);
    1403          14 :   Ao = F2xq_log_Coppersmith_rec(W, r2, a, r, d2, T, m);
    1404          14 :   if (DEBUGLEVEL) timer_printf(&ti,"smooth element");
    1405          14 :   Bo = F2xq_log_Coppersmith_rec(W, r2, b, r, d2, T, m);
    1406          14 :   if (DEBUGLEVEL) timer_printf(&ti,"smooth generator");
    1407          14 :   e = Fp_div(Ao, Bo, m);
    1408          14 :   if (!F2x_equal(F2xq_pow(b0,e,T0),a0)) pari_err_BUG("F2xq_log");
    1409          14 :   return gerepileupto(av, e);
    1410             : }
    1411             : 
    1412             : static GEN
    1413       81388 : F2xq_easylog(void* E, GEN a, GEN g, GEN ord)
    1414             : {
    1415       81388 :   if (F2x_equal1(a)) return gen_0;
    1416       67715 :   if (F2x_equal(a,g)) return gen_1;
    1417       62353 :   if (typ(ord)!=t_INT) return NULL;
    1418       31638 :   if (expi(ord)<28) return NULL;
    1419          14 :   return F2xq_log_index(a,g,ord,(GEN)E);
    1420             : }
    1421             : 
    1422             : GEN
    1423       46648 : F2xq_log(GEN a, GEN g, GEN ord, GEN T)
    1424             : {
    1425       46648 :   GEN z, v = get_arith_ZZM(ord);
    1426       46648 :   ord = mkvec2(gel(v,1),ZM_famat_limit(gel(v,2),int2n(28)));
    1427       46648 :   z = gen_PH_log(a,g,ord,(void*)T,&F2xq_star);
    1428       46648 :   return z? z: cgetg(1,t_VEC);
    1429             : }
    1430             : 
    1431             : GEN
    1432      212611 : F2xq_Artin_Schreier(GEN a, GEN T)
    1433             : {
    1434      212611 :   pari_sp ltop=avma;
    1435      212611 :   long j,N = F2x_degree(T);
    1436      212611 :   GEN Q = F2x_matFrobenius(T);
    1437     1475642 :   for (j=1; j<=N; j++)
    1438     1263031 :     F2m_flip(Q,j,j);
    1439      212611 :   F2v_add_inplace(gel(Q,1),a);
    1440      212611 :   Q = F2m_ker_sp(Q,0);
    1441      212611 :   if (lg(Q)!=2) return NULL;
    1442      212611 :   Q = gel(Q,1);
    1443      212611 :   Q[1] = T[1];
    1444      212611 :   return gerepileuptoleaf(ltop, F2x_renormalize(Q, lg(Q)));
    1445             : }
    1446             : 
    1447             : GEN
    1448       60196 : F2xq_sqrt_fast(GEN c, GEN sqx, GEN T)
    1449             : {
    1450             :   GEN c0, c1;
    1451       60196 :   F2x_even_odd(c, &c0, &c1);
    1452       60200 :   return F2x_add(c0, F2xq_mul(c1, sqx, T));
    1453             : }
    1454             : 
    1455             : static int
    1456       15449 : F2x_is_x(GEN a) { return lg(a)==3 && a[2]==2; }
    1457             : 
    1458             : GEN
    1459       30093 : F2xq_sqrt(GEN a, GEN T)
    1460             : {
    1461       30093 :   pari_sp av = avma;
    1462       30093 :   long n = F2x_degree(T);
    1463             :   GEN sqx;
    1464       30093 :   if (n==1) return F2x_copy(a);
    1465       30051 :   if (n==2) return F2xq_sqr(a,T);
    1466       15449 :   sqx = F2xq_autpow(mkF2(4, T[1]), n-1, T);
    1467       15449 :   return gerepileuptoleaf(av, F2x_is_x(a)? sqx: F2xq_sqrt_fast(a,sqx,T));
    1468             : }
    1469             : 
    1470             : GEN
    1471        9387 : F2xq_sqrtn(GEN a, GEN n, GEN T, GEN *zeta)
    1472             : {
    1473        9387 :   if (!lgpol(a))
    1474             :   {
    1475           7 :     if (signe(n) < 0) pari_err_INV("F2xq_sqrtn",a);
    1476           0 :     if (zeta)
    1477           0 :       *zeta=pol1_F2x(T[1]);
    1478           0 :     return pol0_F2x(T[1]);
    1479             :   }
    1480        9380 :   return gen_Shanks_sqrtn(a,n,subiu(powuu(2,F2x_degree(T)),1),zeta,(void*)T,&F2xq_star);
    1481             : }
    1482             : 
    1483             : GEN
    1484         154 : gener_F2xq(GEN T, GEN *po)
    1485             : {
    1486         154 :   long i, j, vT = T[1], f = F2x_degree(T);
    1487         154 :   pari_sp av0 = avma, av;
    1488             :   GEN g, L2, o, q;
    1489             : 
    1490         154 :   if (f == 1) {
    1491          21 :     if (po) *po = mkvec2(gen_1, trivial_fact());
    1492          21 :     return pol1_F2x(vT);
    1493             :   }
    1494         133 :   q = int2um1(f);
    1495         133 :   o = factor_pn_1(gen_2,f);
    1496         133 :   L2 = leafcopy( gel(o, 1) );
    1497         385 :   for (i = j = 1; i < lg(L2); i++)
    1498             :   {
    1499         252 :     if (absequaliu(gel(L2,i),2)) continue;
    1500         252 :     gel(L2,j++) = diviiexact(q, gel(L2,i));
    1501             :   }
    1502         133 :   setlg(L2, j);
    1503         156 :   for (av = avma;; avma = av)
    1504             :   {
    1505         156 :     g = random_F2x(f, vT);
    1506         156 :     if (F2x_degree(g) < 1) continue;
    1507         394 :     for (i = 1; i < j; i++)
    1508             :     {
    1509         261 :       GEN a = F2xq_pow(g, gel(L2,i), T);
    1510         261 :       if (F2x_equal1(a)) break;
    1511             :     }
    1512         142 :     if (i == j) break;
    1513          23 :   }
    1514         133 :   if (!po) g = gerepilecopy(av0, g);
    1515             :   else {
    1516           0 :     *po = mkvec2(int2um1(f), o);
    1517           0 :     gerepileall(av0, 2, &g, po);
    1518             :   }
    1519         133 :   return g;
    1520             : }
    1521             : 
    1522             : static GEN
    1523         700 : _F2xq_neg(void *E, GEN x)
    1524         700 : { (void) E; return F2x_copy(x); }
    1525             : 
    1526             : static GEN
    1527        2436 : _F2xq_rmul(void *E, GEN x, GEN y)
    1528        2436 : { (void) E; return F2x_mul(x,y); }
    1529             : 
    1530             : static GEN
    1531         371 : _F2xq_inv(void *E, GEN x)
    1532         371 : { return F2xq_inv(x, (GEN) E); }
    1533             : 
    1534             : static int
    1535         826 : _F2xq_equal0(GEN x) { return lgpol(x)==0; }
    1536             : 
    1537             : static GEN
    1538         574 : _F2xq_s(void *E, long x)
    1539         574 : { GEN T = (GEN) E;
    1540         574 :   return odd(x)? pol1_F2x(T[1]): pol0_F2x(T[0]);
    1541             : }
    1542             : 
    1543             : static const struct bb_field F2xq_field={_F2xq_red,_F2xq_add,_F2xq_rmul,_F2xq_neg,
    1544             :                                          _F2xq_inv,_F2xq_equal0,_F2xq_s};
    1545             : 
    1546         238 : const struct bb_field *get_F2xq_field(void **E, GEN T)
    1547             : {
    1548         238 :   *E = (void *) T;
    1549         238 :   return &F2xq_field;
    1550             : }
    1551             : 
    1552             : /***********************************************************************/
    1553             : /**                                                                   **/
    1554             : /**                             F2v                                   **/
    1555             : /**                                                                   **/
    1556             : /***********************************************************************/
    1557             : /* F2v objects are defined as follows:
    1558             :    An F2v is a t_VECSMALL:
    1559             :    v[0] = codeword
    1560             :    v[1] = number of components
    1561             :    x[2] = a_0...a_31 x[3] = a_32..a_63, etc.  on 32bit
    1562             :    x[2] = a_0...a_63 x[3] = a_64..a_127, etc. on 64bit
    1563             : 
    1564             :    where the a_i are bits.
    1565             : */
    1566             : 
    1567             : GEN
    1568      555620 : F2c_to_ZC(GEN x)
    1569             : {
    1570      555620 :   long l=x[1]+1;
    1571      555620 :   GEN  z = cgetg(l, t_COL);
    1572             :   long i,j,k;
    1573     1114365 :   for (i=2,k=1; i<lg(x); i++)
    1574     7079167 :     for (j=0; j<BITS_IN_LONG && k<l; j++,k++)
    1575     6520422 :       gel(z,k) = (x[i]&(1UL<<j))? gen_1: gen_0;
    1576      555620 :   return z;
    1577             : }
    1578             : GEN
    1579        3045 : F2c_to_mod(GEN x)
    1580             : {
    1581        3045 :   long l=x[1]+1;
    1582        3045 :   GEN  z = cgetg(l, t_COL);
    1583        3045 :   GEN _0 = mkintmod(gen_0,gen_2);
    1584        3045 :   GEN _1 = mkintmod(gen_1,gen_2);
    1585             :   long i,j,k;
    1586       15690 :   for (i=2,k=1; i<lg(x); i++)
    1587      573289 :     for (j=0; j<BITS_IN_LONG && k<l; j++,k++)
    1588      560644 :       gel(z,k) = (x[i]&(1UL<<j))? _1: _0;
    1589        3045 :   return z;
    1590             : }
    1591             : 
    1592             : /* x[a..b], a <= b */
    1593             : GEN
    1594          28 : F2v_slice(GEN x, long a, long b)
    1595             : {
    1596          28 :   long i,j,k, l = b-a+1;
    1597          28 :   GEN z = cgetg(nbits2lg(l), t_VECSMALL);
    1598          28 :   z[1] = l;
    1599          98 :   for(i=a,k=1,j=BITS_IN_LONG; i<=b; i++,j++)
    1600             :   {
    1601          70 :     if (j==BITS_IN_LONG) { j=0; z[++k]=0; }
    1602          70 :     if (F2v_coeff(x,i)) z[k] |= 1UL<<j;
    1603             :   }
    1604          28 :   return z;
    1605             : }
    1606             : /* x[a..b,], a <= b */
    1607             : GEN
    1608          14 : F2m_rowslice(GEN x, long a, long b)
    1609             : {
    1610             :   long i, l;
    1611          14 :   GEN y = cgetg_copy(x, &l);
    1612          14 :   for (i = 1; i < l; i++) gel(y,i) = F2v_slice(gel(x,i),a,b);
    1613          14 :   return y;
    1614             : }
    1615             : 
    1616             : GEN
    1617      121286 : F2m_to_ZM(GEN z)
    1618             : {
    1619      121286 :   long i, l = lg(z);
    1620      121286 :   GEN x = cgetg(l,t_MAT);
    1621      121286 :   for (i=1; i<l; i++) gel(x,i) = F2c_to_ZC(gel(z,i));
    1622      121286 :   return x;
    1623             : }
    1624             : GEN
    1625         112 : F2m_to_mod(GEN z)
    1626             : {
    1627         112 :   long i, l = lg(z);
    1628         112 :   GEN x = cgetg(l,t_MAT);
    1629         112 :   for (i=1; i<l; i++) gel(x,i) = F2c_to_mod(gel(z,i));
    1630         112 :   return x;
    1631             : }
    1632             : 
    1633             : GEN
    1634           0 : F2v_to_Flv(GEN x)
    1635             : {
    1636           0 :   long l=x[1]+1;
    1637           0 :   GEN  z=cgetg(l, t_VECSMALL);
    1638             :   long i,j,k;
    1639           0 :   for (i=2,k=1; i<lg(x); i++)
    1640           0 :     for (j=0; j<BITS_IN_LONG && k<l; j++,k++)
    1641           0 :       z[k] = (x[i]>>j)&1UL;
    1642           0 :   return z;
    1643             : }
    1644             : 
    1645             : GEN
    1646           0 : F2m_to_Flm(GEN z)
    1647             : {
    1648           0 :   long i, l = lg(z);
    1649           0 :   GEN x = cgetg(l,t_MAT);
    1650           0 :   for (i=1; i<l; i++) gel(x,i) = F2v_to_Flv(gel(z,i));
    1651           0 :   return x;
    1652             : }
    1653             : 
    1654             : GEN
    1655     1560951 : ZV_to_F2v(GEN x)
    1656             : {
    1657     1560951 :   long l = lg(x)-1;
    1658     1560951 :   GEN z = cgetg(nbits2lg(l), t_VECSMALL);
    1659             :   long i,j,k;
    1660     1560951 :   z[1] = l;
    1661    20934747 :   for(i=1,k=1,j=BITS_IN_LONG; i<=l; i++,j++)
    1662             :   {
    1663    19373796 :     if (j==BITS_IN_LONG) { j=0; z[++k]=0; }
    1664    19373796 :     if (mpodd(gel(x,i))) z[k] |= 1UL<<j;
    1665             :   }
    1666     1560951 :   return z;
    1667             : }
    1668             : 
    1669             : GEN
    1670        7686 : RgV_to_F2v(GEN x)
    1671             : {
    1672        7686 :   long l = lg(x)-1;
    1673        7686 :   GEN z = cgetg(nbits2lg(l), t_VECSMALL);
    1674             :   long i,j,k;
    1675        7686 :   z[1] = l;
    1676     1409758 :   for(i=1,k=1,j=BITS_IN_LONG; i<=l; i++,j++)
    1677             :   {
    1678     1402072 :     if (j==BITS_IN_LONG) { j=0; z[++k]=0; }
    1679     1402072 :     if (Rg_to_F2(gel(x,i))) z[k] |= 1UL<<j;
    1680             :   }
    1681        7686 :   return z;
    1682             : }
    1683             : 
    1684             : GEN
    1685          14 : Flv_to_F2v(GEN x)
    1686             : {
    1687          14 :   long l = lg(x)-1;
    1688          14 :   GEN z = cgetg(nbits2lg(l), t_VECSMALL);
    1689             :   long i,j,k;
    1690          14 :   z[1] = l;
    1691          42 :   for(i=1,k=1,j=BITS_IN_LONG; i<=l; i++,j++)
    1692             :   {
    1693          28 :     if (j==BITS_IN_LONG) { j=0; z[++k]=0; }
    1694          28 :     if (x[i]&1L) z[k] |= 1UL<<j;
    1695             :   }
    1696          14 :   return z;
    1697             : }
    1698             : 
    1699             : GEN
    1700      238244 : ZM_to_F2m(GEN x)
    1701             : {
    1702      238244 :   long j, l = lg(x);
    1703      238244 :   GEN y = cgetg(l,t_MAT);
    1704      238244 :   if (l == 1) return y;
    1705      238244 :   for (j=1; j<l; j++) gel(y,j) = ZV_to_F2v(gel(x,j));
    1706      238244 :   return y;
    1707             : }
    1708             : 
    1709             : GEN
    1710         287 : RgM_to_F2m(GEN x)
    1711             : {
    1712         287 :   long j, l = lg(x);
    1713         287 :   GEN y = cgetg(l,t_MAT);
    1714         287 :   if (l == 1) return y;
    1715         287 :   for (j=1; j<l; j++) gel(y,j) = RgV_to_F2v(gel(x,j));
    1716         287 :   return y;
    1717             : }
    1718             : 
    1719             : GEN
    1720           0 : Flm_to_F2m(GEN x)
    1721             : {
    1722           0 :   long j, l = lg(x);
    1723           0 :   GEN y = cgetg(l,t_MAT);
    1724           0 :   if (l == 1) return y;
    1725           0 :   for (j=1; j<l; j++) gel(y,j) = Flv_to_F2v(gel(x,j));
    1726           0 :   return y;
    1727             : }
    1728             : 
    1729             : GEN
    1730      335799 : const_F2v(long m)
    1731             : {
    1732      335799 :   long i, l = nbits2lg(m);
    1733      335799 :   GEN c = cgetg(l, t_VECSMALL);
    1734      335799 :   for (i = 2; i <= l; i++) c[i] = -1;
    1735      335799 :   if (remsBIL(m)) c[l] = (1UL<<remsBIL(m))-1UL;
    1736      335799 :   return c;
    1737             : }
    1738             : 
    1739             : /* Allow lg(y)<lg(x) */
    1740             : void
    1741    56633590 : F2v_add_inplace(GEN x, GEN y)
    1742             : {
    1743    56633590 :   long n = lg(y);
    1744    56633590 :   long r = (n-2)&7L, q = n-r, i;
    1745   270570999 :   for (i = 2; i < q; i += 8)
    1746             :   {
    1747   213937409 :     x[  i] ^= y[  i]; x[1+i] ^= y[1+i]; x[2+i] ^= y[2+i]; x[3+i] ^= y[3+i];
    1748   213937409 :     x[4+i] ^= y[4+i]; x[5+i] ^= y[5+i]; x[6+i] ^= y[6+i]; x[7+i] ^= y[7+i];
    1749             :   }
    1750    56633590 :   switch (r)
    1751             :   {
    1752    37574862 :     case 7: x[i] ^= y[i]; i++; case 6: x[i] ^= y[i]; i++;
    1753    41310335 :     case 5: x[i] ^= y[i]; i++; case 4: x[i] ^= y[i]; i++;
    1754    44410823 :     case 3: x[i] ^= y[i]; i++; case 2: x[i] ^= y[i]; i++;
    1755    50136472 :     case 1: x[i] ^= y[i]; i++;
    1756             :   }
    1757    56633590 : }
    1758             : 
    1759             : /***********************************************************************/
    1760             : /**                                                                   **/
    1761             : /**                               F2xV                                **/
    1762             : /**                                                                   **/
    1763             : /***********************************************************************/
    1764             : /* F2xV are t_VEC with F2x coefficients. */
    1765             : 
    1766             : GEN
    1767       15043 : FlxC_to_F2xC(GEN x)
    1768             : {
    1769       15043 :   long i, l=lg(x);
    1770       15043 :   GEN z = cgetg(l,t_COL);
    1771       15043 :   for (i=1; i<l ; i++) gel(z,i) = Flx_to_F2x(gel(x,i));
    1772       15043 :   return z;
    1773             : }
    1774             : 
    1775             : GEN
    1776           0 : F2xC_to_FlxC(GEN x)
    1777             : {
    1778           0 :   long i, l=lg(x);
    1779           0 :   GEN z = cgetg(l,t_COL);
    1780           0 :   for (i=1; i<l ; i++) gel(z,i) = F2x_to_Flx(gel(x,i));
    1781           0 :   return z;
    1782             : }
    1783             : 
    1784             : GEN
    1785        2331 : F2xC_to_ZXC(GEN v)
    1786             : {
    1787        2331 :   long j, N = lg(v);
    1788        2331 :   GEN y = cgetg(N, t_COL);
    1789        2331 :   for (j=1; j<N; j++) gel(y,j) = F2x_to_ZX(gel(v,j));
    1790        2331 :   return y;
    1791             : }
    1792             : 
    1793             : GEN
    1794      232052 : F2xV_to_F2m(GEN v, long n)
    1795             : {
    1796      232052 :   long j, N = lg(v);
    1797      232052 :   GEN y = cgetg(N, t_MAT);
    1798      232052 :   for (j=1; j<N; j++) gel(y,j) = F2x_to_F2v(gel(v,j), n);
    1799      232052 :   return y;
    1800             : }
    1801             : 
    1802             : /***********************************************************************/
    1803             : /**                                                                   **/
    1804             : /**                             F2xX                                  **/
    1805             : /**                                                                   **/
    1806             : /***********************************************************************/
    1807             : 
    1808             : GEN
    1809     2363168 : F2xX_renormalize(GEN /*in place*/ x, long lx)
    1810     2363168 : { return FlxX_renormalize(x, lx); }
    1811             : 
    1812             : GEN
    1813      447349 : pol1_F2xX(long v, long sv) { return pol1_FlxX(v, sv); }
    1814             : 
    1815             : GEN
    1816         357 : polx_F2xX(long v, long sv) { return polx_FlxX(v, sv); }
    1817             : 
    1818             : long
    1819      205590 : F2xY_degreex(GEN b)
    1820             : {
    1821      205590 :   long deg = 0, i;
    1822      205590 :   if (!signe(b)) return -1;
    1823     1335957 :   for (i = 2; i < lg(b); ++i)
    1824     1130367 :     deg = maxss(deg, F2x_degree(gel(b, i)));
    1825      205590 :   return deg;
    1826             : }
    1827             : 
    1828             : GEN
    1829        1848 : FlxX_to_F2xX(GEN B)
    1830             : {
    1831        1848 :   long lb=lg(B);
    1832             :   long i;
    1833        1848 :   GEN b=cgetg(lb,t_POL);
    1834        1848 :   b[1]=evalsigne(1)|(((ulong)B[1])&VARNBITS);
    1835        5544 :   for (i=2; i<lb; i++)
    1836        3696 :     gel(b,i) = Flx_to_F2x(gel(B,i));
    1837        1848 :   return F2xX_renormalize(b, lb);
    1838             : }
    1839             : 
    1840             : GEN
    1841        3038 : ZXX_to_F2xX(GEN B, long v)
    1842             : {
    1843        3038 :   long lb=lg(B);
    1844             :   long i;
    1845        3038 :   GEN b=cgetg(lb,t_POL);
    1846        3038 :   b[1]=evalsigne(1)|(((ulong)B[1])&VARNBITS);
    1847       15512 :   for (i=2; i<lb; i++)
    1848       12474 :     switch (typ(gel(B,i)))
    1849             :     {
    1850             :     case t_INT:
    1851        4074 :       gel(b,i) = Z_to_F2x(gel(B,i), v);
    1852        4074 :       break;
    1853             :     case t_POL:
    1854        8400 :       gel(b,i) = ZX_to_F2x(gel(B,i));
    1855        8400 :       break;
    1856             :     }
    1857        3038 :   return F2xX_renormalize(b, lb);
    1858             : }
    1859             : 
    1860             : GEN
    1861        2401 : F2xX_to_ZXX(GEN B)
    1862             : {
    1863        2401 :   long i, lb = lg(B);
    1864        2401 :   GEN b = cgetg(lb,t_POL);
    1865        7252 :   for (i=2; i<lb; i++)
    1866             :   {
    1867        4851 :     GEN c = gel(B,i);
    1868        4851 :     gel(b,i) = lgpol(c) ?  F2x_equal1(c) ? gen_1 : F2x_to_ZX(c) : gen_0;
    1869             :   }
    1870        2401 :   b[1] = B[1]; return b;
    1871             : }
    1872             : 
    1873             : GEN
    1874       80570 : F2xX_deriv(GEN z)
    1875             : {
    1876       80570 :   long i,l = lg(z)-1;
    1877             :   GEN x;
    1878       80570 :   if (l < 2) l = 2;
    1879       80570 :   x = cgetg(l, t_POL); x[1] = z[1];
    1880       80570 :   for (i=2; i<l; i++) gel(x,i) = odd(i) ? pol0_F2x(mael(z,i+1,1)): gel(z,i+1);
    1881       80570 :   return F2xX_renormalize(x,l);
    1882             : }
    1883             : 
    1884             : static GEN
    1885        2624 : F2xX_addspec(GEN x, GEN y, long lx, long ly)
    1886             : {
    1887             :   long i,lz;
    1888             :   GEN z;
    1889        2624 :   if (ly>lx) swapspec(x,y, lx,ly);
    1890        2624 :   lz = lx+2; z = cgetg(lz, t_POL);
    1891        2624 :   for (i=0; i<ly; i++) gel(z,i+2) = F2x_add(gel(x,i), gel(y,i));
    1892        2624 :   for (   ; i<lx; i++) gel(z,i+2) = F2x_copy(gel(x,i));
    1893        2624 :   return F2xX_renormalize(z, lz);
    1894             : }
    1895             : 
    1896             : GEN
    1897      423136 : F2xX_add(GEN x, GEN y)
    1898             : {
    1899             :   long i,lz;
    1900             :   GEN z;
    1901      423136 :   long lx=lg(x);
    1902      423136 :   long ly=lg(y);
    1903      423136 :   if (ly>lx) swapspec(x,y, lx,ly);
    1904      423136 :   lz = lx; z = cgetg(lz, t_POL); z[1]=x[1];
    1905      423136 :   for (i=2; i<ly; i++) gel(z,i) = F2x_add(gel(x,i), gel(y,i));
    1906      423136 :   for (   ; i<lx; i++) gel(z,i) = F2x_copy(gel(x,i));
    1907      423136 :   return F2xX_renormalize(z, lz);
    1908             : }
    1909             : 
    1910             : GEN
    1911           0 : F2xX_F2x_add(GEN x, GEN y)
    1912             : {
    1913           0 :   long i, lz = lg(y);
    1914             :   GEN z;
    1915           0 :   if (signe(y) == 0) return scalarpol(x, varn(y));
    1916           0 :   z = cgetg(lz,t_POL); z[1] = y[1];
    1917           0 :   gel(z,2) = F2x_add(gel(y,2), x);
    1918           0 :   if (lz == 3) z = F2xX_renormalize(z,lz);
    1919             :   else
    1920           0 :     for(i=3;i<lz;i++) gel(z,i) = F2x_copy(gel(y,i));
    1921           0 :   return z;
    1922             : }
    1923             : 
    1924             : GEN
    1925      481481 : F2xX_F2x_mul(GEN P, GEN U)
    1926             : {
    1927      481481 :   long i, lP = lg(P);
    1928      481481 :   GEN res = cgetg(lP,t_POL);
    1929      481481 :   res[1] = P[1];
    1930     2322530 :   for(i=2; i<lP; i++)
    1931     1841049 :     gel(res,i) = F2x_mul(U,gel(P,i));
    1932      481481 :   return F2xX_renormalize(res, lP);
    1933             : }
    1934             : 
    1935             : GEN
    1936      136752 : F2xY_F2xqV_evalx(GEN P, GEN x, GEN T)
    1937             : {
    1938      136752 :   long i, lP = lg(P);
    1939      136752 :   GEN res = cgetg(lP,t_POL);
    1940      136752 :   res[1] = P[1];
    1941      618009 :   for(i=2; i<lP; i++)
    1942      481257 :     gel(res,i) = F2x_F2xqV_eval(gel(P,i), x, T);
    1943      136752 :   return F2xX_renormalize(res, lP);
    1944             : }
    1945             : 
    1946             : GEN
    1947           0 : F2xY_F2xq_evalx(GEN P, GEN x, GEN T)
    1948             : {
    1949           0 :   pari_sp av = avma;
    1950           0 :   long n = brent_kung_optpow(F2x_degree(T)-1,lgpol(P),1);
    1951           0 :   GEN xp = F2xq_powers(x, n, T);
    1952           0 :   return gerepileupto(av, F2xY_F2xqV_evalx(P, xp, T));
    1953             : }
    1954             : 
    1955             : static GEN
    1956       13040 : F2xX_to_Kronecker_spec(GEN P, long n, long d)
    1957             : {
    1958       13040 :   long i, k, l, N = 2*d + 1;
    1959       13040 :   long dP = n+1;
    1960             :   GEN x;
    1961       13040 :   if (n == 0) return pol0_Flx(P[1]&VARNBITS);
    1962       13040 :   l = nbits2nlong(N*dP+d+1);
    1963       13040 :   x = zero_zv(l+1);
    1964      505930 :   for (k=i=0; i<n; i++, k+=N)
    1965             :   {
    1966      492890 :     GEN c = gel(P,i);
    1967      492890 :     F2x_addshiftip(x, c, k);
    1968             :   }
    1969       13040 :   x[1] = P[1]&VARNBITS; return F2x_renormalize(x, l+2);
    1970             : }
    1971             : 
    1972             : GEN
    1973      301216 : F2xX_to_Kronecker(GEN P, long d)
    1974             : {
    1975      301216 :   long i, k, l, N = 2*d + 1;
    1976      301216 :   long dP = degpol(P);
    1977             :   GEN x;
    1978      301216 :   if (dP < 0) return pol0_Flx(P[1]&VARNBITS);
    1979      300174 :   l = nbits2nlong(N*dP+d+1);
    1980      300174 :   x = zero_zv(l+1);
    1981     1644483 :   for (k=i=0; i<=dP; i++, k+=N)
    1982             :   {
    1983     1344309 :     GEN c = gel(P,i+2);
    1984     1344309 :     F2x_addshiftip(x, c, k);
    1985             :   }
    1986      300174 :   x[1] = P[1]&VARNBITS; return F2x_renormalize(x, l+2);
    1987             : }
    1988             : 
    1989             : static GEN
    1990     1678288 : F2x_slice(GEN x, long n, long d)
    1991             : {
    1992     1678288 :   ulong ib, il=dvmduBIL(n, &ib);
    1993     1678288 :   ulong db, dl=dvmduBIL(d, &db);
    1994     1678288 :   long lN = dl+2+(db?1:0);
    1995     1678288 :   GEN t = cgetg(lN,t_VECSMALL);
    1996     1678288 :   t[1] = x[1];
    1997     1678288 :   if (ib)
    1998             :   {
    1999     1513042 :     ulong i, ic = BITS_IN_LONG-ib;
    2000     1513042 :     ulong r = uel(x,2+il)>>ib;
    2001     1513128 :     for(i=0; i<dl; i++)
    2002             :     {
    2003          86 :       uel(t,2+i) = (uel(x,3+il+i)<<ic)|r;
    2004          86 :       r = uel(x,3+il+i)>>ib;
    2005             :     }
    2006     1513042 :     if (db)
    2007     1513042 :       uel(t,2+i) = (uel(x,3+il+i)<<ic)|r;
    2008             :   }
    2009             :   else
    2010             :   {
    2011             :     long i;
    2012      330503 :     for(i=2; i<lN; i++)
    2013      165257 :       uel(t,i) = uel(x,il+i);
    2014             :   }
    2015     1678288 :   if (db) uel(t,lN-1) &= (1UL<<db)-1;
    2016     1678288 :   return F2x_renormalize(t, lN);
    2017             : }
    2018             : 
    2019             : GEN
    2020      157128 : Kronecker_to_F2xqX(GEN z, GEN T)
    2021             : {
    2022      157128 :   long lz = F2x_degree(z)+1;
    2023      157128 :   long i, j, N = F2x_degree(T)*2 + 1;
    2024      157128 :   long lx = lz / (N-2);
    2025      157128 :   GEN x = cgetg(lx+3,t_POL);
    2026      157128 :   x[1] = z[1];
    2027     1835416 :   for (i=0, j=2; i<lz; i+=N, j++)
    2028             :   {
    2029     1678288 :     GEN t = F2x_slice(z,i,minss(lz-i,N));
    2030     1678288 :     t[1] = T[1];
    2031     1678288 :     gel(x,j) = F2x_rem(t, T);
    2032             :   }
    2033      157128 :   return F2xX_renormalize(x, j);
    2034             : }
    2035             : 
    2036             : /***********************************************************************/
    2037             : /**                                                                   **/
    2038             : /**                             F2xXV/F2xXC                           **/
    2039             : /**                                                                   **/
    2040             : /***********************************************************************/
    2041             : 
    2042             : GEN
    2043         259 : FlxXC_to_F2xXC(GEN B)
    2044             : {
    2045         259 :   long i, l = lg(B);
    2046         259 :   GEN z = cgetg(l, t_COL);
    2047        2107 :   for (i=1; i<l; i++)
    2048        1848 :     gel(z,i) = FlxX_to_F2xX(gel(B,i));
    2049         259 :   return z;
    2050             : }
    2051             : 
    2052             : GEN
    2053         707 : F2xXC_to_ZXXC(GEN B)
    2054             : {
    2055         707 :   long i, l = lg(B);
    2056         707 :   GEN z = cgetg(l, t_COL);
    2057        3108 :   for (i=1; i<l; i++)
    2058        2401 :     gel(z,i) = F2xX_to_ZXX(gel(B,i));
    2059         707 :   return z;
    2060             : }
    2061             : 
    2062             : /***********************************************************************/
    2063             : /**                                                                   **/
    2064             : /**                             F2xqX                                 **/
    2065             : /**                                                                   **/
    2066             : /***********************************************************************/
    2067             : 
    2068             : static GEN
    2069      778876 : get_F2xqX_red(GEN T, GEN *B)
    2070             : {
    2071      778876 :   if (typ(T)!=t_VEC) { *B=NULL; return T; }
    2072        5135 :   *B = gel(T,1); return gel(T,2);
    2073             : }
    2074             : 
    2075             : GEN
    2076        2807 : random_F2xqX(long d1, long v, GEN T)
    2077             : {
    2078        2807 :   long dT = F2x_degree(T), vT = T[1];
    2079        2807 :   long i, d = d1+2;
    2080        2807 :   GEN y = cgetg(d,t_POL); y[1] = evalsigne(1) | evalvarn(v);
    2081        2807 :   for (i=2; i<d; i++) gel(y,i) = random_F2x(dT, vT);
    2082        2807 :   return FlxX_renormalize(y,d);
    2083             : }
    2084             : 
    2085             : GEN
    2086      662956 : F2xqX_red(GEN z, GEN T)
    2087             : {
    2088             :   GEN res;
    2089      662956 :   long i, l = lg(z);
    2090      662956 :   res = cgetg(l,t_POL); res[1] = z[1];
    2091      662956 :   for(i=2;i<l;i++) gel(res,i) = F2x_rem(gel(z,i),T);
    2092      662956 :   return F2xX_renormalize(res,l);
    2093             : }
    2094             : 
    2095             : GEN
    2096        6937 : F2xqX_F2xq_mul(GEN P, GEN U, GEN T)
    2097             : {
    2098        6937 :   long i, lP = lg(P);
    2099        6937 :   GEN res = cgetg(lP,t_POL);
    2100        6937 :   res[1] = P[1];
    2101       38983 :   for(i=2; i<lP; i++)
    2102       32046 :     gel(res,i) = F2xq_mul(U,gel(P,i), T);
    2103        6937 :   return F2xX_renormalize(res, lP);
    2104             : }
    2105             : 
    2106             : GEN
    2107      204379 : F2xqX_F2xq_mul_to_monic(GEN P, GEN U, GEN T)
    2108             : {
    2109      204379 :   long i, lP = lg(P);
    2110      204379 :   GEN res = cgetg(lP,t_POL);
    2111      204379 :   res[1] = P[1];
    2112      204379 :   for(i=2; i<lP-1; i++) gel(res,i) = F2xq_mul(U,gel(P,i), T);
    2113      204379 :   gel(res,lP-1) = pol1_F2x(T[1]);
    2114      204379 :   return F2xX_renormalize(res, lP);
    2115             : }
    2116             : 
    2117             : GEN
    2118      204393 : F2xqX_normalize(GEN z, GEN T)
    2119             : {
    2120      204393 :   GEN p1 = leading_coeff(z);
    2121      204393 :   if (!lgpol(z) || (!degpol(p1) && p1[1] == 1)) return z;
    2122      204379 :   return F2xqX_F2xq_mul_to_monic(z, F2xq_inv(p1,T), T);
    2123             : }
    2124             : 
    2125             : GEN
    2126      150608 : F2xqX_mul(GEN x, GEN y, GEN T)
    2127             : {
    2128      150608 :   pari_sp ltop=avma;
    2129             :   GEN z,kx,ky;
    2130      150608 :   kx= F2xX_to_Kronecker(x, F2x_degree(T));
    2131      150608 :   ky= F2xX_to_Kronecker(y, F2x_degree(T));
    2132      150608 :   z = F2x_mul(ky, kx);
    2133      150608 :   z = Kronecker_to_F2xqX(z,T);
    2134      150608 :   return gerepileupto(ltop,z);
    2135             : }
    2136             : 
    2137             : static GEN
    2138        6520 : F2xqX_mulspec(GEN x, GEN y, GEN T, long nx, long ny)
    2139             : {
    2140        6520 :   pari_sp ltop=avma;
    2141             :   GEN z,kx,ky;
    2142        6520 :   kx= F2xX_to_Kronecker_spec(x, nx, F2x_degree(T));
    2143        6520 :   ky= F2xX_to_Kronecker_spec(y, ny, F2x_degree(T));
    2144        6520 :   z = F2x_mul(ky, kx);
    2145        6520 :   z = Kronecker_to_F2xqX(z,T);
    2146        6520 :   return gerepileupto(ltop,z);
    2147             : }
    2148             : 
    2149             : GEN
    2150      105350 : F2xqX_sqr(GEN x, GEN T)
    2151             : {
    2152      105350 :   long d = degpol(x), l = 2*d+3;
    2153             :   GEN z;
    2154      105350 :   if (!signe(x)) return pol_0(varn(x));
    2155      105343 :   z = cgetg(l,t_POL);
    2156      105343 :   z[1] = x[1];
    2157      105343 :   if (d > 0)
    2158             :   {
    2159      105259 :     GEN u = pol0_F2x(T[1]);
    2160             :     long i,j;
    2161      265377 :     for (i=2,j=2; i<d+2; i++,j+=2)
    2162             :     {
    2163      160118 :       gel(z, j) = F2xq_sqr(gel(x, i), T);
    2164      160118 :       gel(z, j+1) = u;
    2165             :     }
    2166             :   }
    2167      105343 :   gel(z, 2+2*d) = F2xq_sqr(gel(x, 2+d), T);
    2168      105343 :   return FlxX_renormalize(z, l);
    2169             : }
    2170             : 
    2171             : static GEN
    2172      539499 : F2xqX_divrem_basecase(GEN x, GEN y, GEN T, GEN *pr)
    2173             : {
    2174             :   long vx, dx, dy, dz, i, j, sx, lr;
    2175             :   pari_sp av0, av, tetpil;
    2176             :   GEN z,p1,rem,lead;
    2177             : 
    2178      539499 :   if (!signe(y)) pari_err_INV("F2xqX_divrem",y);
    2179      539499 :   vx=varn(x); dy=degpol(y); dx=degpol(x);
    2180      539499 :   if (dx < dy)
    2181             :   {
    2182           0 :     if (pr)
    2183             :     {
    2184           0 :       av0 = avma; x = F2xqX_red(x, T);
    2185           0 :       if (pr == ONLY_DIVIDES) { avma=av0; return signe(x)? NULL: pol_0(vx); }
    2186           0 :       if (pr == ONLY_REM) return x;
    2187           0 :       *pr = x;
    2188             :     }
    2189           0 :     return pol_0(vx);
    2190             :   }
    2191      539499 :   lead = leading_term(y);
    2192      539499 :   if (!dy) /* y is constant */
    2193             :   {
    2194      114912 :     if (pr && pr != ONLY_DIVIDES)
    2195             :     {
    2196      104937 :       if (pr == ONLY_REM) return pol_0(vx);
    2197           7 :       *pr = pol_0(vx);
    2198             :     }
    2199        9982 :     if (F2x_equal1(lead)) return gcopy(x);
    2200        6930 :     av0 = avma; x = F2xqX_F2xq_mul(x,F2xq_inv(lead,T),T);
    2201        6930 :     return gerepileupto(av0,x);
    2202             :   }
    2203      424587 :   av0 = avma; dz = dx-dy;
    2204      424587 :   lead = F2x_equal1(lead)? NULL: gclone(F2xq_inv(lead,T));
    2205      424587 :   avma = av0;
    2206      424587 :   z = cgetg(dz+3,t_POL); z[1] = x[1];
    2207      424587 :   x += 2; y += 2; z += 2;
    2208             : 
    2209      424587 :   p1 = gel(x,dx); av = avma;
    2210      424587 :   gel(z,dz) = lead? gerepileupto(av, F2xq_mul(p1,lead, T)): leafcopy(p1);
    2211     1156533 :   for (i=dx-1; i>=dy; i--)
    2212             :   {
    2213      731946 :     av=avma; p1=gel(x,i);
    2214     2108943 :     for (j=i-dy+1; j<=i && j<=dz; j++)
    2215     1376997 :       p1 = F2x_add(p1, F2x_mul(gel(z,j),gel(y,i-j)));
    2216      731946 :     if (lead) p1 = F2x_mul(p1, lead);
    2217      731946 :     tetpil=avma; gel(z,i-dy) = gerepile(av,tetpil,F2x_rem(p1,T));
    2218             :   }
    2219      424587 :   if (!pr) { if (lead) gunclone(lead); return z-2; }
    2220             : 
    2221      403795 :   rem = (GEN)avma; av = (pari_sp)new_chunk(dx+3);
    2222      622247 :   for (sx=0; ; i--)
    2223             :   {
    2224      622247 :     p1 = gel(x,i);
    2225     1888523 :     for (j=0; j<=i && j<=dz; j++)
    2226     1266276 :       p1 = F2x_add(p1, F2x_mul(gel(z,j),gel(y,i-j)));
    2227      622247 :     tetpil=avma; p1 = F2x_rem(p1, T); if (lgpol(p1)) { sx = 1; break; }
    2228      280486 :     if (!i) break;
    2229      218452 :     avma=av;
    2230      218452 :   }
    2231      403795 :   if (pr == ONLY_DIVIDES)
    2232             :   {
    2233           0 :     if (lead) gunclone(lead);
    2234           0 :     if (sx) { avma=av0; return NULL; }
    2235           0 :     avma = (pari_sp)rem; return z-2;
    2236             :   }
    2237      403795 :   lr=i+3; rem -= lr;
    2238      403795 :   rem[0] = evaltyp(t_POL) | evallg(lr);
    2239      403795 :   rem[1] = z[-1];
    2240      403795 :   p1 = gerepile((pari_sp)rem,tetpil,p1);
    2241      403795 :   rem += 2; gel(rem,i) = p1;
    2242     1347329 :   for (i--; i>=0; i--)
    2243             :   {
    2244      943534 :     av=avma; p1 = gel(x,i);
    2245     3033826 :     for (j=0; j<=i && j<=dz; j++)
    2246     2090292 :       p1 = F2x_add(p1, F2x_mul(gel(z,j),gel(y,i-j)));
    2247      943534 :     tetpil=avma; gel(rem,i) = gerepile(av,tetpil, F2x_rem(p1, T));
    2248             :   }
    2249      403795 :   rem -= 2;
    2250      403795 :   if (lead) gunclone(lead);
    2251      403795 :   if (!sx) (void)F2xX_renormalize(rem, lr);
    2252      403795 :   if (pr == ONLY_REM) return gerepileupto(av0,rem);
    2253           7 :   *pr = rem; return z-2;
    2254             : }
    2255             : 
    2256             : static GEN
    2257        5350 : F2xX_recipspec(GEN x, long l, long n, long vs)
    2258             : {
    2259             :   long i;
    2260        5350 :   GEN z=cgetg(n+2,t_POL)+2;
    2261      197410 :   for(i=0; i<l; i++)
    2262      192060 :     gel(z,n-i-1) = F2x_copy(gel(x,i));
    2263        5350 :   for(   ; i<n; i++)
    2264           0 :     gel(z,n-i-1) = pol0_F2x(vs);
    2265        5350 :   return F2xX_renormalize(z-2,n+2);
    2266             : }
    2267             : 
    2268             : static GEN
    2269          20 : F2xqX_invBarrett_basecase(GEN T, GEN Q)
    2270             : {
    2271          20 :   long i, l=lg(T)-1, lr = l-1, k;
    2272          20 :   long sv=Q[1];
    2273          20 :   GEN r=cgetg(lr,t_POL); r[1]=T[1];
    2274          20 :   gel(r,2) = pol1_F2x(sv);
    2275         288 :   for (i=3;i<lr;i++)
    2276             :   {
    2277         268 :     pari_sp ltop=avma;
    2278         268 :     GEN u = gel(T,l-i+2);
    2279        1936 :     for (k=3;k<i;k++)
    2280        1668 :       u = F2x_add(u, F2xq_mul(gel(T,l-i+k),gel(r,k),Q));
    2281         268 :     gel(r,i) = gerepileupto(ltop, u);
    2282             :   }
    2283          20 :   r = F2xX_renormalize(r,lr);
    2284          20 :   return r;
    2285             : }
    2286             : 
    2287             : /* Return new lgpol */
    2288             : static long
    2289        7156 : F2xX_lgrenormalizespec(GEN x, long lx)
    2290             : {
    2291             :   long i;
    2292        7156 :   for (i = lx-1; i>=0; i--)
    2293        7156 :     if (lgpol(gel(x,i))) break;
    2294        7156 :   return i+1;
    2295             : }
    2296             : 
    2297             : static GEN
    2298         102 : F2xqX_invBarrett_Newton(GEN S, GEN T)
    2299             : {
    2300         102 :   pari_sp av = avma;
    2301         102 :   long nold, lx, lz, lq, l = degpol(S), i, lQ;
    2302         102 :   GEN q, y, z, x = cgetg(l+2, t_POL) + 2;
    2303         102 :   long dT = F2x_degree(T);
    2304         102 :   ulong mask = quadratic_prec_mask(l-2); /* assume l > 2 */
    2305         102 :   for (i=0;i<l;i++) gel(x,i) = pol0_F2x(T[1]);
    2306         102 :   q = F2xX_recipspec(S+2,l+1,l+1,dT);
    2307         102 :   lQ = lgpol(q); q+=2;
    2308             :   /* We work on _spec_ FlxX's, all the l[xzq] below are lgpol's */
    2309             : 
    2310             :   /* initialize */
    2311         102 :   gel(x,0) = F2xq_inv(gel(q,0),T);
    2312         102 :   if (lQ>1 && F2x_degree(gel(q,1)) >= dT)
    2313           0 :     gel(q,1) = F2x_rem(gel(q,1), T);
    2314         102 :   if (lQ>1 && lgpol(gel(q,1)))
    2315         102 :   {
    2316         102 :     GEN u = gel(q, 1);
    2317         102 :     if (!F2x_equal1(gel(x,0))) u = F2xq_mul(u, F2xq_sqr(gel(x,0), T), T);
    2318         102 :     else u = F2x_copy(u);
    2319         102 :     gel(x,1) = u; lx = 2;
    2320             :   }
    2321             :   else
    2322           0 :     lx = 1;
    2323         102 :   nold = 1;
    2324         840 :   for (; mask > 1; )
    2325             :   { /* set x -= x(x*q - 1) + O(t^(nnew + 1)), knowing x*q = 1 + O(t^(nold+1)) */
    2326         636 :     long i, lnew, nnew = nold << 1;
    2327             : 
    2328         636 :     if (mask & 1) nnew--;
    2329         636 :     mask >>= 1;
    2330             : 
    2331         636 :     lnew = nnew + 1;
    2332         636 :     lq = F2xX_lgrenormalizespec(q, minss(lQ,lnew));
    2333         636 :     z = F2xqX_mulspec(x, q, T, lx, lq); /* FIXME: high product */
    2334         636 :     lz = lgpol(z); if (lz > lnew) lz = lnew;
    2335         636 :     z += 2;
    2336             :     /* subtract 1 [=>first nold words are 0]: renormalize so that z(0) != 0 */
    2337         636 :     for (i = nold; i < lz; i++) if (lgpol(gel(z,i))) break;
    2338         636 :     nold = nnew;
    2339         636 :     if (i >= lz) continue; /* z-1 = 0(t^(nnew + 1)) */
    2340             : 
    2341             :     /* z + i represents (x*q - 1) / t^i */
    2342         636 :     lz = F2xX_lgrenormalizespec (z+i, lz-i);
    2343         636 :     z = F2xqX_mulspec(x, z+i, T, lx, lz); /* FIXME: low product */
    2344         636 :     lz = lgpol(z); z += 2;
    2345         636 :     if (lz > lnew-i) lz = F2xX_lgrenormalizespec(z, lnew-i);
    2346             : 
    2347         636 :     lx = lz+ i;
    2348         636 :     y  = x + i; /* x -= z * t^i, in place */
    2349         636 :     for (i = 0; i < lz; i++) gel(y,i) = gel(z,i);
    2350             :   }
    2351         102 :   x -= 2; setlg(x, lx + 2); x[1] = S[1];
    2352         102 :   return gerepilecopy(av, x);
    2353             : }
    2354             : 
    2355             : /* x/polrecip(P)+O(x^n) */
    2356             : GEN
    2357         122 : F2xqX_invBarrett(GEN T, GEN Q)
    2358             : {
    2359         122 :   pari_sp ltop=avma;
    2360         122 :   long l=lg(T), v = varn(T);
    2361             :   GEN r;
    2362         122 :   GEN c = gel(T,l-1);
    2363         122 :   if (l<5) return pol_0(v);
    2364         122 :   if (l<=F2xqX_INVBARRETT_LIMIT)
    2365             :   {
    2366          20 :     if (!F2x_equal1(c))
    2367             :     {
    2368           0 :       GEN ci = F2xq_inv(c,Q);
    2369           0 :       T = F2xqX_F2xq_mul(T, ci, Q);
    2370           0 :       r = F2xqX_invBarrett_basecase(T,Q);
    2371           0 :       r = F2xqX_F2xq_mul(r,ci,Q);
    2372             :     } else
    2373          20 :       r = F2xqX_invBarrett_basecase(T,Q);
    2374             :   } else
    2375         102 :     r = F2xqX_invBarrett_Newton(T,Q);
    2376         122 :   return gerepileupto(ltop, r);
    2377             : }
    2378             : 
    2379             : GEN
    2380        2548 : F2xqX_get_red(GEN S, GEN T)
    2381             : {
    2382        2548 :   if (typ(S)==t_POL && lg(S)>F2xqX_BARRETT_LIMIT)
    2383          98 :     retmkvec2(F2xqX_invBarrett(S, T), S);
    2384        2450 :   return S;
    2385             : }
    2386             : 
    2387             : /* Compute x mod S where 2 <= degpol(S) <= l+1 <= 2*(degpol(S)-1)
    2388             :  *  * and mg is the Barrett inverse of S. */
    2389             : static GEN
    2390        2624 : F2xqX_divrem_Barrettspec(GEN x, long l, GEN mg, GEN S, GEN T, GEN *pr)
    2391             : {
    2392             :   GEN q, r;
    2393        2624 :   long lt = degpol(S); /*We discard the leading term*/
    2394             :   long ld, lm, lT, lmg;
    2395        2624 :   ld = l-lt;
    2396        2624 :   lm = minss(ld, lgpol(mg));
    2397        2624 :   lT  = F2xX_lgrenormalizespec(S+2,lt);
    2398        2624 :   lmg = F2xX_lgrenormalizespec(mg+2,lm);
    2399        2624 :   q = F2xX_recipspec(x+lt,ld,ld,0);               /* q = rec(x)     lq<=ld*/
    2400        2624 :   q = F2xqX_mulspec(q+2,mg+2,T,lgpol(q),lmg);   /* q = rec(x) * mg lq<=ld+lm*/
    2401        2624 :   q = F2xX_recipspec(q+2,minss(ld,lgpol(q)),ld,0);/* q = rec (rec(x) * mg) lq<=ld*/
    2402        2624 :   if (!pr) return q;
    2403        2624 :   r = F2xqX_mulspec(q+2,S+2,T,lgpol(q),lT);     /* r = q*pol        lr<=ld+lt*/
    2404        2624 :   r = F2xX_addspec(x,r+2,lt,minss(lt,lgpol(r)));/* r = x - r   lr<=lt */
    2405        2624 :   if (pr == ONLY_REM) return r;
    2406        2624 :   *pr = r; return q;
    2407             : }
    2408             : 
    2409             : static GEN
    2410        2616 : F2xqX_divrem_Barrett_noGC(GEN x, GEN mg, GEN S, GEN T, GEN *pr)
    2411             : {
    2412        2616 :   long l = lgpol(x), lt = degpol(S), lm = 2*lt-1;
    2413        2616 :   GEN q = NULL, r;
    2414             :   long i;
    2415        2616 :   if (l <= lt)
    2416             :   {
    2417           0 :     if (pr == ONLY_REM) return RgX_copy(x);
    2418           0 :     if (pr == ONLY_DIVIDES) return signe(x)? NULL: pol_0(varn(x));
    2419           0 :     if (pr) *pr =  RgX_copy(x);
    2420           0 :     return pol_0(varn(x));
    2421             :   }
    2422        2616 :   if (lt <= 1)
    2423           0 :     return F2xqX_divrem_basecase(x,S,T,pr);
    2424        2616 :   if (pr != ONLY_REM && l>lm)
    2425             :   {
    2426           8 :     long vT = get_F2x_var(T);
    2427           8 :     q = cgetg(l-lt+2, t_POL);
    2428           8 :     for (i=0;i<l-lt;i++) gel(q+2,i) = pol0_F2x(vT);
    2429             :   }
    2430        2616 :   r = l>lm ? shallowcopy(x): x;
    2431        5240 :   while (l>lm)
    2432             :   {
    2433           8 :     GEN zr, zq = F2xqX_divrem_Barrettspec(r+2+l-lm,lm,mg,S,T,&zr);
    2434           8 :     long lz = lgpol(zr);
    2435           8 :     if (pr != ONLY_REM)
    2436             :     {
    2437           8 :       long lq = lgpol(zq);
    2438           8 :       for(i=0; i<lq; i++) gel(q+2+l-lm,i) = gel(zq,2+i);
    2439             :     }
    2440           8 :     for(i=0; i<lz; i++) gel(r+2+l-lm,i) = gel(zr,2+i);
    2441           8 :     l = l-lm+lz;
    2442             :   }
    2443        2616 :   if (pr != ONLY_REM)
    2444             :   {
    2445          12 :     if (l > lt)
    2446             :     {
    2447          12 :       GEN zq = F2xqX_divrem_Barrettspec(r+2,l,mg,S,T,&r);
    2448          12 :       if (!q) q = zq;
    2449             :       else
    2450             :       {
    2451           8 :         long lq = lgpol(zq);
    2452           8 :         for(i=0; i<lq; i++) gel(q+2,i) = gel(zq,2+i);
    2453             :       }
    2454             :     }
    2455             :     else
    2456           0 :     { setlg(r, l+2); r = RgX_copy(r); }
    2457             :   }
    2458             :   else
    2459             :   {
    2460        2604 :     if (l > lt)
    2461        2604 :       (void) F2xqX_divrem_Barrettspec(r+2,l,mg,S,T,&r);
    2462             :     else
    2463           0 :     { setlg(r, l+2); r = RgX_copy(r); }
    2464        2604 :     r[1] = x[1]; return F2xX_renormalize(r, lg(r));
    2465             :   }
    2466          12 :   if (pr) { r[1] = x[1]; r = F2xX_renormalize(r, lg(r)); }
    2467          12 :   q[1] = x[1]; q = F2xX_renormalize(q, lg(q));
    2468          12 :   if (pr == ONLY_DIVIDES) return signe(r)? NULL: q;
    2469          12 :   if (pr) *pr = r;
    2470          12 :   return q;
    2471             : }
    2472             : 
    2473             : GEN
    2474       30793 : F2xqX_divrem(GEN x, GEN S, GEN T, GEN *pr)
    2475             : {
    2476       30793 :   GEN B, y = get_F2xqX_red(S, &B);
    2477       30793 :   long dy = degpol(y), dx = degpol(x), d = dx-dy;
    2478       30793 :   if (pr==ONLY_REM) return F2xqX_rem(x, y, T);
    2479       30793 :   if (!B && d+3 < F2xqX_DIVREM_BARRETT_LIMIT)
    2480       30781 :     return F2xqX_divrem_basecase(x,y,T,pr);
    2481             :   else
    2482             :   {
    2483          12 :     pari_sp av=avma;
    2484          12 :     GEN mg = B? B: F2xqX_invBarrett(y, T);
    2485          12 :     GEN q = F2xqX_divrem_Barrett_noGC(x,mg,y,T,pr);
    2486          12 :     if (!q) {avma=av; return NULL;}
    2487          12 :     if (!pr || pr==ONLY_DIVIDES) return gerepilecopy(av, q);
    2488           0 :     gerepileall(av,2,&q,pr);
    2489           0 :     return q;
    2490             :   }
    2491             : }
    2492             : 
    2493             : GEN
    2494      748083 : F2xqX_rem(GEN x, GEN S, GEN T)
    2495             : {
    2496      748083 :   GEN B, y = get_F2xqX_red(S, &B);
    2497      748083 :   long dy = degpol(y), dx = degpol(x), d = dx-dy;
    2498      748083 :   if (d < 0) return F2xqX_red(x, T);
    2499      511322 :   if (!B && d+3 < F2xqX_REM_BARRETT_LIMIT)
    2500      508718 :     return F2xqX_divrem_basecase(x,y, T, ONLY_REM);
    2501             :   else
    2502             :   {
    2503        2604 :     pari_sp av=avma;
    2504        2604 :     GEN mg = B? B: F2xqX_invBarrett(y, T);
    2505        2604 :     GEN r = F2xqX_divrem_Barrett_noGC(x, mg, y, T, ONLY_REM);
    2506        2604 :     return gerepileupto(av, r);
    2507             :   }
    2508             : }
    2509             : 
    2510             : GEN
    2511      167881 : F2xqX_gcd(GEN a, GEN b, GEN T)
    2512             : {
    2513      167881 :   pari_sp av = avma, av0=avma;
    2514      861994 :   while (signe(b))
    2515             :   {
    2516             :     GEN c;
    2517      526232 :     if (gc_needed(av0,2))
    2518             :     {
    2519           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2xqX_gcd (d = %ld)",degpol(b));
    2520           0 :       gerepileall(av0,2, &a,&b);
    2521             :     }
    2522      526232 :     av = avma; c = F2xqX_rem(a, b, T); a=b; b=c;
    2523             :   }
    2524      167881 :   avma = av; return a;
    2525             : }
    2526             : 
    2527             : GEN
    2528           7 : F2xqX_extgcd(GEN a, GEN b, GEN T,  GEN *ptu, GEN *ptv)
    2529             : {
    2530           7 :   pari_sp av=avma;
    2531             :   GEN u,v,d,d1,v1;
    2532           7 :   long vx = varn(a);
    2533           7 :   d = a; d1 = b;
    2534           7 :   v = pol_0(vx); v1 = pol1_F2xX(vx, get_F2x_var(T));
    2535          28 :   while (signe(d1))
    2536             :   {
    2537          14 :     GEN r, q = F2xqX_divrem(d, d1, T, &r);
    2538          14 :     v = F2xX_add(v,F2xqX_mul(q,v1,T));
    2539          14 :     u=v; v=v1; v1=u;
    2540          14 :     u=r; d=d1; d1=u;
    2541          14 :     if (gc_needed(av,2))
    2542             :     {
    2543           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2xqX_extgcd (d = %ld)",degpol(d));
    2544           0 :       gerepileall(av,5, &d,&d1,&u,&v,&v1);
    2545             :     }
    2546             :   }
    2547           7 :   if (ptu) *ptu = F2xqX_div(F2xX_add(d,F2xqX_mul(b,v, T)), a, T);
    2548           7 :   *ptv = v; return d;
    2549             : }
    2550             : 
    2551             : /***********************************************************************/
    2552             : /**                                                                   **/
    2553             : /**                             F2xqXQ                                **/
    2554             : /**                                                                   **/
    2555             : /***********************************************************************/
    2556             : 
    2557             : GEN
    2558      114359 : F2xqXQ_mul(GEN x, GEN y, GEN S, GEN T) {
    2559      114359 :   return F2xqX_rem(F2xqX_mul(x,y,T),S,T);
    2560             : }
    2561             : 
    2562             : GEN
    2563      104412 : F2xqXQ_sqr(GEN x, GEN S, GEN T) {
    2564      104412 :   return F2xqX_rem(F2xqX_sqr(x,T),S,T);
    2565             : }
    2566             : 
    2567             : GEN
    2568           7 : F2xqXQ_invsafe(GEN x, GEN S, GEN T)
    2569             : {
    2570           7 :   GEN V, z = F2xqX_extgcd(get_F2xqX_mod(S), x, T, NULL, &V);
    2571           7 :   if (degpol(z)) return NULL;
    2572           7 :   z = F2xq_invsafe(gel(z,2),T);
    2573           7 :   if (!z) return NULL;
    2574           7 :   return F2xqX_F2xq_mul(V, z, T);
    2575             : }
    2576             : 
    2577             : GEN
    2578           7 : F2xqXQ_inv(GEN x, GEN S, GEN T)
    2579             : {
    2580           7 :   pari_sp av = avma;
    2581           7 :   GEN U = F2xqXQ_invsafe(x, S, T);
    2582           7 :   if (!U) pari_err_INV("F2xqXQ_inv",x);
    2583           7 :   return gerepileupto(av, U);
    2584             : }
    2585             : 
    2586             : struct _F2xqXQ {
    2587             :   GEN T, S;
    2588             : };
    2589             : 
    2590             : static GEN
    2591      344736 : _F2xqXQ_add(void *data, GEN x, GEN y) {
    2592             :   (void) data;
    2593      344736 :   return F2xX_add(x,y);
    2594             : }
    2595             : static GEN
    2596      481481 : _F2xqXQ_cmul(void *data, GEN P, long a, GEN x) {
    2597             :   (void) data;
    2598      481481 :   return F2xX_F2x_mul(x,gel(P,a+2));
    2599             : }
    2600             : static GEN
    2601      352394 : _F2xqXQ_red(void *data, GEN x) {
    2602      352394 :   struct _F2xqXQ *d = (struct _F2xqXQ*) data;
    2603      352394 :   return F2xqX_red(x, d->T);
    2604             : }
    2605             : static GEN
    2606      114359 : _F2xqXQ_mul(void *data, GEN x, GEN y) {
    2607      114359 :   struct _F2xqXQ *d = (struct _F2xqXQ*) data;
    2608      114359 :   return F2xqXQ_mul(x,y, d->S,d->T);
    2609             : }
    2610             : static GEN
    2611       33089 : _F2xqXQ_sqr(void *data, GEN x) {
    2612       33089 :   struct _F2xqXQ *d = (struct _F2xqXQ*) data;
    2613       33089 :   return F2xqXQ_sqr(x, d->S,d->T);
    2614             : }
    2615             : static GEN
    2616          56 : _F2xqXQ_zero(void *data) {
    2617          56 :   struct _F2xqXQ *d = (struct _F2xqXQ*) data;
    2618          56 :   return pol_0(get_F2xqX_var(d->S));
    2619             : }
    2620             : static GEN
    2621      375816 : _F2xqXQ_one(void *data) {
    2622      375816 :   struct _F2xqXQ *d = (struct _F2xqXQ*) data;
    2623      375816 :   return pol1_F2xX(get_F2xqX_var(d->S),get_F2x_var(d->T));
    2624             : }
    2625             : 
    2626             : static struct bb_algebra F2xqXQ_algebra = { _F2xqXQ_red,
    2627             :  _F2xqXQ_add, _F2xqXQ_add, _F2xqXQ_mul,_F2xqXQ_sqr,_F2xqXQ_one,_F2xqXQ_zero };
    2628             : 
    2629             : GEN
    2630           7 : F2xqXQ_pow(GEN x, GEN n, GEN S, GEN T)
    2631             : {
    2632             :   struct _F2xqXQ D;
    2633           7 :   long s = signe(n);
    2634           7 :   if (!s) return pol1_F2xX(get_F2xqX_var(S), get_F2x_var(T));
    2635           7 :   if (s < 0) x = F2xqXQ_inv(x,S,T);
    2636           7 :   if (is_pm1(n)) return s < 0 ? x : gcopy(x);
    2637           7 :   if (degpol(x) >= get_F2xqX_degree(S)) x = F2xqX_rem(x,S,T);
    2638           7 :   D.S = S; D.T = T;
    2639           7 :   return gen_pow(x, n, (void*)&D, &_F2xqXQ_sqr, &_F2xqXQ_mul);
    2640             : }
    2641             : 
    2642             : GEN
    2643        7539 : F2xqXQ_powers(GEN x, long l, GEN S, GEN T)
    2644             : {
    2645             :   struct _F2xqXQ D;
    2646        7539 :   int use_sqr = 2*degpol(x) >= get_F2xqX_degree(S);
    2647        7539 :   D.S = S; D.T = T;
    2648        7539 :   return gen_powers(x, l, use_sqr, (void*)&D, &_F2xqXQ_sqr, &_F2xqXQ_mul,&_F2xqXQ_one);
    2649             : }
    2650             : 
    2651             : GEN
    2652       14245 : F2xqX_F2xqXQV_eval(GEN P, GEN V, GEN S, GEN T)
    2653             : {
    2654             :   struct _F2xqXQ D;
    2655       14245 :   D.S = S; D.T = T;
    2656       14245 :   return gen_bkeval_powers(P, degpol(P), V, (void*)&D, &F2xqXQ_algebra,
    2657             :                                                    _F2xqXQ_cmul);
    2658             : }
    2659             : 
    2660             : GEN
    2661      122556 : F2xqX_F2xqXQ_eval(GEN Q, GEN x, GEN S, GEN T)
    2662             : {
    2663             :   struct _F2xqXQ D;
    2664      122556 :   int use_sqr = 2*degpol(x) >= get_F2xqX_degree(S);
    2665      122556 :   D.S = S; D.T = T;
    2666      122556 :   return gen_bkeval(Q, degpol(Q), x, use_sqr, (void*)&D, &F2xqXQ_algebra,
    2667             :                                                     _F2xqXQ_cmul);
    2668             : }
    2669             : 
    2670             : static GEN
    2671       89117 : F2xqXQ_autpow_sqr(void * E, GEN x)
    2672             : {
    2673       89117 :   struct _F2xqXQ *D = (struct _F2xqXQ *)E;
    2674       89117 :   GEN T = D->T;
    2675       89117 :   GEN phi = gel(x,1), S = gel(x,2);
    2676       89117 :   long n = brent_kung_optpow(F2x_degree(T)-1,lgpol(S)+1,1);
    2677       89117 :   GEN V = F2xq_powers(phi, n, T);
    2678       89117 :   GEN phi2 = F2x_F2xqV_eval(phi, V, T);
    2679       89117 :   GEN Sphi = F2xY_F2xqV_evalx(S, V, T);
    2680       89117 :   GEN S2 = F2xqX_F2xqXQ_eval(Sphi, S, D->S, T);
    2681       89117 :   return mkvec2(phi2, S2);
    2682             : }
    2683             : 
    2684             : static GEN
    2685       33439 : F2xqXQ_autpow_mul(void * E, GEN x, GEN y)
    2686             : {
    2687       33439 :   struct _F2xqXQ *D = (struct _F2xqXQ *)E;
    2688       33439 :   GEN T = D->T;
    2689       33439 :   GEN phi1 = gel(x,1), S1 = gel(x,2);
    2690       33439 :   GEN phi2 = gel(y,1), S2 = gel(y,2);
    2691       33439 :   long n = brent_kung_optpow(F2x_degree(T)-1,lgpol(S1)+1,1);
    2692       33439 :   GEN V = F2xq_powers(phi2, n, T);
    2693       33439 :   GEN phi3 = F2x_F2xqV_eval(phi1,V,T);
    2694       33439 :   GEN Sphi = F2xY_F2xqV_evalx(S1,V,T);
    2695       33439 :   GEN S3 = F2xqX_F2xqXQ_eval(Sphi, S2, D->S, T);
    2696       33439 :   return mkvec2(phi3, S3);
    2697             : }
    2698             : 
    2699             : GEN
    2700       70763 : F2xqXQ_autpow(GEN aut, long n, GEN S, GEN T)
    2701             : {
    2702             :   struct _F2xqXQ D;
    2703       70763 :   D.S = S; D.T = T;
    2704       70763 :   return gen_powu(aut,n,&D,F2xqXQ_autpow_sqr,F2xqXQ_autpow_mul);
    2705             : }
    2706             : 
    2707             : static GEN
    2708        7098 : F2xqXQ_auttrace_mul(void *E, GEN x, GEN y)
    2709             : {
    2710        7098 :   struct _F2xqXQ *D = (struct _F2xqXQ *) E;
    2711        7098 :   GEN T = D->T;
    2712        7098 :   GEN phi1 = gel(x,1), S1 = gel(x,2), a1 = gel(x,3);
    2713        7098 :   GEN phi2 = gel(y,1), S2 = gel(y,2), a2 = gel(y,3);
    2714        7098 :   long n2 = brent_kung_optpow(F2x_degree(T)-1, lgpol(S1)+lgpol(a1)+1, 1);
    2715        7098 :   GEN V2 = F2xq_powers(phi2, n2, T);
    2716        7098 :   GEN phi3 = F2x_F2xqV_eval(phi1, V2, T);
    2717        7098 :   GEN Sphi = F2xY_F2xqV_evalx(S1, V2, T);
    2718        7098 :   GEN aphi = F2xY_F2xqV_evalx(a1, V2, T);
    2719        7098 :   long n = brent_kung_optpow(maxss(degpol(Sphi),degpol(aphi)),2,1);
    2720        7098 :   GEN V = F2xqXQ_powers(S2, n, D->S, T);
    2721        7098 :   GEN S3 = F2xqX_F2xqXQV_eval(Sphi, V, D->S, T);
    2722        7098 :   GEN aS = F2xqX_F2xqXQV_eval(aphi, V, D->S, T);
    2723        7098 :   GEN a3 = F2xX_add(aS, a2);
    2724        7098 :   return mkvec3(phi3, S3, a3);
    2725             : }
    2726             : 
    2727             : static GEN
    2728        4844 : F2xqXQ_auttrace_sqr(void *E, GEN x)
    2729        4844 : { return F2xqXQ_auttrace_mul(E, x, x); }
    2730             : 
    2731             : GEN
    2732        2688 : F2xqXQ_auttrace(GEN aut, long n, GEN S, GEN T)
    2733             : {
    2734             :   struct _F2xqXQ D;
    2735        2688 :   D.S = S; D.T = T;
    2736        2688 :   return gen_powu(aut,n,&D,F2xqXQ_auttrace_sqr,F2xqXQ_auttrace_mul);
    2737             : }
    2738             : 
    2739             : GEN
    2740          63 : F2xqXQV_red(GEN z, GEN S, GEN T)
    2741             : {
    2742          63 :   long i,l = lg(z);
    2743          63 :   GEN x = cgetg(l, t_VEC);
    2744          63 :   for (i=1; i<l; i++) gel(x,i) = F2xqX_rem(gel(z,i), S, T);
    2745          63 :   return x;
    2746             : }

Generated by: LCOV version 1.11