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 19834-0e97742) Lines: 1261 1342 94.0 %
Date: 2016-12-09 05:49:11 Functions: 157 162 96.9 %
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   280305087 : F2x_degree_lg(GEN x, long l)
      39             : {
      40   280305087 :   return (l==2)?-1:bit_accuracy(l)-bfffo(x[l-1])-1;
      41             : }
      42             : 
      43             : long
      44    75892091 : F2x_degree(GEN x)
      45             : {
      46    75892091 :   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      147836 : F2x_to_ZX(GEN x)
      61             : {
      62      147836 :   long l=3+F2x_degree(x);
      63      147837 :   GEN z=cgetg(l,t_POL);
      64             :   long i,j,k;
      65      295092 :   for(i=2,k=2;i<lg(x);i++)
      66      692566 :     for(j=0; j<BITS_IN_LONG && k<l; j++,k++)
      67      545311 :       gel(z,k)=(x[i]&(1UL<<j))?gen_1:gen_0;
      68      147837 :   z[1]=evalsigne(l>=3)|x[1];
      69      147837 :   return z;
      70             : }
      71             : 
      72             : GEN
      73       89907 : F2x_to_Flx(GEN x)
      74             : {
      75       89907 :   long l=3+F2x_degree(x);
      76       89920 :   GEN z=cgetg(l,t_VECSMALL);
      77             :   long i,j,k;
      78       89920 :   z[1]=x[1];
      79      197150 :   for(i=2,k=2;i<lg(x);i++)
      80     2423444 :     for(j=0;j<BITS_IN_LONG && k<l; j++,k++)
      81     2316214 :       z[k]=(x[i]>>j)&1UL;
      82       89920 :   return z;
      83             : }
      84             : 
      85             : GEN
      86      159649 : Z_to_F2x(GEN x, long v)
      87             : {
      88      159649 :   long sv = evalvarn(v);
      89      159649 :   return mpodd(x) ? pol1_F2x(sv): pol0_F2x(sv);
      90             : }
      91             : 
      92             : GEN
      93      134798 : ZX_to_F2x(GEN x)
      94             : {
      95      134798 :   long l=nbits2lg(lgpol(x));
      96      134798 :   GEN z=cgetg(l,t_VECSMALL);
      97             :   long i,j,k;
      98      134814 :   z[1]=((ulong)x[1])&VARNBITS;
      99      609937 :   for(i=2, k=1,j=BITS_IN_LONG;i<lg(x);i++,j++)
     100             :   {
     101      475138 :     if (j==BITS_IN_LONG)
     102             :     {
     103      133431 :       j=0; k++; z[k]=0;
     104             :     }
     105      475138 :     if (mpodd(gel(x,i)))
     106      362397 :       z[k]|=1UL<<j;
     107             :   }
     108      134799 :   return F2x_renormalize(z,l);
     109             : }
     110             : 
     111             : GEN
     112      186270 : Flx_to_F2x(GEN x)
     113             : {
     114      186270 :   long l=nbits2lg(lgpol(x));
     115      186268 :   GEN z=cgetg(l,t_VECSMALL);
     116             :   long i,j,k;
     117      186275 :   z[1]=x[1];
     118     2938516 :   for(i=2, k=1,j=BITS_IN_LONG;i<lg(x);i++,j++)
     119             :   {
     120     2752241 :     if (j==BITS_IN_LONG)
     121             :     {
     122      197693 :       j=0; k++; z[k]=0;
     123             :     }
     124     2752241 :     if (x[i]&1UL)
     125     1385481 :       z[k]|=1UL<<j;
     126             :   }
     127      186275 :   return F2x_renormalize(z,l);
     128             : }
     129             : 
     130             : GEN
     131     1339929 : F2x_to_F2v(GEN x, long N)
     132             : {
     133     1339929 :   long i, l = lg(x);
     134     1339929 :   long n = nbits2lg(N);
     135     1339929 :   GEN z = cgetg(n,t_VECSMALL);
     136     1339929 :   z[1] = N;
     137     1339929 :   for (i=2; i<l ; i++) z[i]=x[i];
     138     1339929 :   for (   ; i<n; i++) z[i]=0;
     139     1339929 :   return z;
     140             : }
     141             : 
     142             : GEN
     143        1218 : RgX_to_F2x(GEN x)
     144             : {
     145        1218 :   long l=nbits2lg(lgpol(x));
     146        1218 :   GEN z=cgetg(l,t_VECSMALL);
     147             :   long i,j,k;
     148        1218 :   z[1]=((ulong)x[1])&VARNBITS;
     149        3717 :   for(i=2, k=1,j=BITS_IN_LONG;i<lg(x);i++,j++)
     150             :   {
     151        2499 :     if (j==BITS_IN_LONG)
     152             :     {
     153        1218 :       j=0; k++; z[k]=0;
     154             :     }
     155        2499 :     if (Rg_to_F2(gel(x,i)))
     156        1120 :       z[k]|=1UL<<j;
     157             :   }
     158        1218 :   return F2x_renormalize(z,l);
     159             : }
     160             : 
     161             : /* If x is a POLMOD, assume modulus is a multiple of T. */
     162             : GEN
     163     1145902 : Rg_to_F2xq(GEN x, GEN T)
     164             : {
     165     1145902 :   long ta, tx = typ(x), v = T[1];
     166             :   GEN a, b;
     167     1145902 :   if (is_const_t(tx))
     168             :   {
     169     1144732 :     if (tx == t_FFELT) return FF_to_F2xq(x);
     170      241712 :     return Rg_to_F2(x)? pol1_F2x(v): pol0_F2x(v);
     171             :   }
     172        1176 :   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        1078 :       x = RgX_to_F2x(x);
     184        1078 :       if (x[1] != v) break;
     185        1078 :       return F2x_rem(x, T);
     186             :     case t_RFRAC:
     187          98 :       a = Rg_to_F2xq(gel(x,1), T);
     188          98 :       b = Rg_to_F2xq(gel(x,2), T);
     189          98 :       return F2xq_div(a,b, T);
     190             :   }
     191           0 :   pari_err_TYPE("Rg_to_F2xq",x);
     192           0 :   return NULL; /* not reached */
     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    38533501 : F2x_add(GEN x, GEN y)
     219             : {
     220             :   long i,lz;
     221             :   GEN z;
     222    38533501 :   long lx=lg(x);
     223    38533501 :   long ly=lg(y);
     224    38533501 :   if (ly>lx) swapspec(x,y, lx,ly);
     225    38533501 :   lz = lx; z = cgetg(lz, t_VECSMALL); z[1]=x[1];
     226    38538035 :   for (i=2; i<ly; i++) z[i] = x[i]^y[i];
     227    38538035 :   for (   ; i<lx; i++) z[i] = x[i];
     228    38538035 :   return F2x_renormalize(z, lz);
     229             : }
     230             : 
     231             : static GEN
     232       17997 : F2x_addspec(GEN x, GEN y, long lx, long ly)
     233             : {
     234             :   long i,lz;
     235             :   GEN z;
     236             : 
     237       17997 :   if (ly>lx) swapspec(x,y, lx,ly);
     238       17997 :   lz = lx+2; z = cgetg(lz, t_VECSMALL) + 2;
     239       48806 :   for (i=0; i<ly-3; i+=4)
     240             :   {
     241       30809 :     z[i] = x[i]^y[i];
     242       30809 :     z[i+1] = x[i+1]^y[i+1];
     243       30809 :     z[i+2] = x[i+2]^y[i+2];
     244       30809 :     z[i+3] = x[i+3]^y[i+3];
     245             :   }
     246       28731 :   for (; i<ly; i++)
     247       10734 :     z[i] = x[i]^y[i];
     248       17997 :   for (   ; i<lx; i++) z[i] = x[i];
     249       17997 :   z -= 2; return F2x_renormalize(z, lz);
     250             : }
     251             : 
     252             : GEN
     253      186355 : F2x_1_add(GEN y)
     254             : {
     255             :   GEN z;
     256             :   long lz, i;
     257      186355 :   if (!lgpol(y))
     258       61249 :     return pol1_F2x(y[1]);
     259      125106 :   lz=lg(y);
     260      125106 :   z=cgetg(lz,t_VECSMALL);
     261      125106 :   z[1] = y[1];
     262      125106 :   z[2] = y[2]^1UL;
     263      125106 :   for(i=3;i<lz;i++)
     264           0 :     z[i] = y[i];
     265      125106 :   if (lz==3) z = F2x_renormalize(z,lz);
     266      125106 :   return z;
     267             : }
     268             : 
     269             : INLINE void
     270   177201905 : F2x_addshiftipspec(GEN x, GEN y, long ny, ulong db)
     271             : {
     272             :   long i;
     273   177201905 :   if (db)
     274             :   {
     275   151457143 :     ulong dc=BITS_IN_LONG-db;
     276   151457143 :     ulong r=0, yi;
     277   233810988 :     for(i=0; i<ny-3; i+=4)
     278             :     {
     279    82353845 :       yi = uel(y,i);   x[i]   ^= (yi<<db)|r; r = yi>>dc;
     280    82353845 :       yi = uel(y,i+1); x[i+1] ^= (yi<<db)|r; r = yi>>dc;
     281    82353845 :       yi = uel(y,i+2); x[i+2] ^= (yi<<db)|r; r = yi>>dc;
     282    82353845 :       yi = uel(y,i+3); x[i+3] ^= (yi<<db)|r; r = yi>>dc;
     283             :     }
     284   295710235 :     for(  ; i<ny; i++)
     285             :     {
     286   144253092 :       ulong yi = uel(y,i); x[i] ^= (yi<<db)|r; r = yi>>dc;
     287             :     }
     288   151457143 :     if (r) x[i] ^= r;
     289             :   }
     290             :   else
     291             :   {
     292    29916478 :     for(i=0; i<ny-3; i+=4)
     293             :     {
     294     4171716 :       x[i]   ^= y[i];
     295     4171716 :       x[i+1] ^= y[i+1];
     296     4171716 :       x[i+2] ^= y[i+2];
     297     4171716 :       x[i+3] ^= y[i+3];
     298             :     }
     299    54787755 :     for(   ; i<ny; i++)
     300    29042993 :       x[i] ^= y[i];
     301             :   }
     302   177201905 : }
     303             : 
     304             : INLINE void
     305   148540619 : F2x_addshiftip(GEN x, GEN y, ulong d)
     306             : {
     307   148540619 :   ulong db, dl=dvmduBIL(d, &db);
     308   148201903 :   F2x_addshiftipspec(x+2+dl, y+2, lgpol(y), db);
     309   148472340 : }
     310             : 
     311             : static GEN
     312    26198257 : F2x_mul1(ulong x, ulong y)
     313             : {
     314    26198257 :   ulong x1=(x&HIGHMASK)>>BITS_IN_HALFULONG;
     315    26198257 :   ulong x2=x&LOWMASK;
     316    26198257 :   ulong y1=(y&HIGHMASK)>>BITS_IN_HALFULONG;
     317    26198257 :   ulong y2=y&LOWMASK;
     318             :   ulong r1,r2,rr;
     319             :   GEN z;
     320             :   ulong i;
     321    26198257 :   rr=r1=r2=0UL;
     322    26198257 :   if (x2)
     323   806715999 :     for(i=0;i<BITS_IN_HALFULONG;i++)
     324   780541378 :       if (x2&(1UL<<i))
     325             :       {
     326    90492379 :         r2^=y2<<i;
     327    90492379 :         rr^=y1<<i;
     328             :       }
     329    26198257 :   if (x1)
     330     2473931 :     for(i=0;i<BITS_IN_HALFULONG;i++)
     331     2394441 :       if (x1&(1UL<<i))
     332             :       {
     333      787558 :         r1^=y1<<i;
     334      787558 :         rr^=y2<<i;
     335             :       }
     336    26198257 :   r2^=(rr&LOWMASK)<<BITS_IN_HALFULONG;
     337    26198257 :   r1^=(rr&HIGHMASK)>>BITS_IN_HALFULONG;
     338    26198257 :   z=cgetg((r1?4:3),t_VECSMALL);
     339    26198204 :   z[2]=r2;
     340    26198204 :   if (r1) z[3]=r1;
     341    26198204 :   return z;
     342             : }
     343             : 
     344             : static GEN
     345     5015266 : F2x_mulspec_basecase(GEN x, GEN y, long nx, long ny)
     346             : {
     347             :   long l, i, j;
     348             :   GEN z;
     349     5015266 :   l = nx + ny;
     350     5015266 :   z = zero_Flv(l+1);
     351     5516262 :   for(i=0; i < ny-1; i++)
     352             :   {
     353      502280 :     GEN zi = z+2+i;
     354      502280 :     ulong yi = uel(y,i);
     355      502280 :     if (yi)
     356    28144990 :       for(j=0; j < BITS_IN_LONG; j++)
     357    27642757 :         if (yi&(1UL<<j)) F2x_addshiftipspec(zi,x,nx,j);
     358             :   }
     359             :   {
     360     5013982 :     GEN zi = z+2+i;
     361     5013982 :     ulong yi = uel(y,i);
     362     5013982 :     long c = BITS_IN_LONG-bfffo(yi);
     363    29613358 :     for(j=0; j < c; j++)
     364    24598067 :       if (yi&(1UL<<j)) F2x_addshiftipspec(zi,x,nx,j);
     365             :   }
     366     5015291 :   return F2x_renormalize(z, l+2);
     367             : }
     368             : 
     369             : static GEN
     370       13386 : F2x_addshift(GEN x, GEN y, long d)
     371             : {
     372       13386 :   GEN xd,yd,zd = (GEN)avma;
     373       13386 :   long a,lz,ny = lgpol(y), nx = lgpol(x);
     374       13386 :   long vs = x[1];
     375             : 
     376       13386 :   x += 2; y += 2; a = ny-d;
     377       13386 :   if (a <= 0)
     378             :   {
     379        1199 :     lz = (a>nx)? ny+2: nx+d+2;
     380        1199 :     (void)new_chunk(lz); xd = x+nx; yd = y+ny;
     381        1199 :     while (xd > x) *--zd = *--xd;
     382        1199 :     x = zd + a;
     383        1199 :     while (zd > x) *--zd = 0;
     384             :   }
     385             :   else
     386             :   {
     387       12187 :     xd = new_chunk(d); yd = y+d;
     388       12187 :     x = F2x_addspec(x,yd,nx,a);
     389       12187 :     lz = (a>nx)? ny+2: lg(x)+d;
     390       12187 :     x += 2; while (xd > x) *--zd = *--xd;
     391             :   }
     392       13386 :   while (yd > y) *--zd = *--yd;
     393       13386 :   *--zd = vs;
     394       13386 :   *--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    31223905 : F2x_shiftip(pari_sp av, GEN x, long v)
     401             : {
     402    31223905 :   long i, lx = lg(x), ly;
     403             :   GEN y;
     404    31223905 :   if (!v || lx==2) return gerepileuptoleaf(av, x);
     405       22409 :   ly = lx + v;
     406       22409 :   (void)new_chunk(ly); /* check that result fits */
     407       22410 :   x += lx; y = (GEN)av;
     408       22410 :   for (i = 2; i<lx; i++) *--y = *--x;
     409       22410 :   for (i = 0; i< v; i++) *--y = 0;
     410       22410 :   y -= 2; y[0] = evaltyp(t_VECSMALL) | evallg(ly);
     411       22410 :   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    35395825 : F2x_mulspec(GEN a, GEN b, long na, long nb)
     420             : {
     421             :   GEN a0,c,c0;
     422    35395825 :   long n0, n0a, i, v = 0;
     423             :   pari_sp av;
     424             : 
     425    35395825 :   while (na && !a[0]) { a++; na-=1; v++; }
     426    35395825 :   while (nb && !b[0]) { b++; nb-=1; v++; }
     427    35395825 :   if (na < nb) swapspec(a,b, na,nb);
     428    35395825 :   if (!nb) return pol0_F2x(0);
     429             : 
     430    31223979 :   av = avma;
     431    31223979 :   if (na == 1)
     432    26198238 :     return F2x_shiftip(av, F2x_mul1(*a,*b), v);
     433     5025741 :   if (na < F2x_MUL_KARATSUBA_LIMIT)
     434     5015260 :     return F2x_shiftip(av, F2x_mulspec_basecase(a, b, na, nb), v);
     435       10481 :   i=(na>>1); n0=na-i; na=i;
     436       10481 :   a0=a+n0; n0a=n0;
     437       10481 :   while (n0a && !a[n0a-1]) n0a--;
     438             : 
     439       10481 :   if (nb > n0)
     440             :   {
     441             :     GEN b0,c1,c2;
     442             :     long n0b;
     443             : 
     444        2905 :     nb -= n0; b0 = b+n0; n0b = n0;
     445        2905 :     while (n0b && !b[n0b-1]) n0b--;
     446        2905 :     c =  F2x_mulspec(a,b,n0a,n0b);
     447        2905 :     c0 = F2x_mulspec(a0,b0,na,nb);
     448             : 
     449        2905 :     c2 = F2x_addspec(a0,a,na,n0a);
     450        2905 :     c1 = F2x_addspec(b0,b,nb,n0b);
     451             : 
     452        2905 :     c1 = F2x_mul(c1,c2);
     453        2905 :     c2 = F2x_add(c0,c);
     454             : 
     455        2905 :     c2 = F2x_add(c1,c2);
     456        2905 :     c0 = F2x_addshift(c0,c2,n0);
     457             :   }
     458             :   else
     459             :   {
     460        7576 :     c  = F2x_mulspec(a,b,n0a,nb);
     461        7576 :     c0 = F2x_mulspec(a0,b,na,nb);
     462             :   }
     463       10481 :   c0 = F2x_addshift(c0,c,n0);
     464       10481 :   return F2x_shiftip(av,c0, v);
     465             : }
     466             : 
     467             : GEN
     468    35374790 : F2x_mul(GEN x, GEN y)
     469             : {
     470    35374790 :   GEN z = F2x_mulspec(x+2,y+2, lgpol(x),lgpol(y));
     471    35374831 :   z[1] = x[1]; return z;
     472             : }
     473             : 
     474             : GEN
     475     8543521 : F2x_sqr(GEN x)
     476             : {
     477     8543521 :   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     8543521 :   long lx=lg(x), lz=2+((lx-2)<<1);
     480             :   GEN z;
     481     8543521 :   z = cgetg(lz, t_VECSMALL); z[1]=x[1];
     482    17388563 :   for (j=2,jj=2;j<lx;j++,jj++)
     483             :   {
     484     8828469 :     ulong x1=((ulong)x[j]&HIGHMASK)>>BITS_IN_HALFULONG;
     485     8828469 :     ulong x2=(ulong)x[j]&LOWMASK;
     486     8828469 :     z[jj]=0;
     487     8828469 :     if (x2)
     488    73413798 :       for(i=0,ii=0;i<BITS_IN_HALFULONG;i+=4,ii+=8)
     489    64655106 :         z[jj]|=sq[(x2>>i)&15UL]<<ii;
     490     8828469 :     z[++jj]=0;
     491     8828469 :     if (x1)
     492     9598344 :       for(i=0,ii=0;i<BITS_IN_HALFULONG;i+=4,ii+=8)
     493     8361341 :         z[jj]|=sq[(x1>>i)&15UL]<<ii;
     494             :   }
     495     8560094 :   return F2x_renormalize(z, lz);
     496             : }
     497             : 
     498             : static GEN
     499      189965 : F2x_pow2n(GEN x, long n)
     500             : {
     501             :   long i;
     502      569930 :   for(i=1;i<=n;i++)
     503      379936 :     x = F2x_sqr(x);
     504      189994 :   return x;
     505             : }
     506             : 
     507             : int
     508       35662 : F2x_issquare(GEN x)
     509             : {
     510       35662 :   const ulong mask = (ULONG_MAX/3UL)*2;
     511       35662 :   ulong i, lx = lg(x);
     512       71310 :   for (i=2; i<lx; i++)
     513       35662 :     if ((x[i]&mask)) return 0;
     514       35648 :   return 1;
     515             : }
     516             : 
     517             : /* Assume x is a perfect square */
     518             : GEN
     519       78763 : F2x_sqrt(GEN x)
     520             : {
     521       78763 :   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       78763 :   long lx=lg(x), lz=2+((lx-1)>>1);
     524             :   GEN z;
     525       78763 :   z = cgetg(lz, t_VECSMALL); z[1]=x[1];
     526      157555 :   for (j=2,jj=2;jj<lz;j++,jj++)
     527             :   {
     528       78786 :     ulong x2=x[j++];
     529       78786 :     z[jj]=0;
     530       78786 :     if (x2)
     531      664638 :       for(i=0,ii=0;ii<BITS_IN_HALFULONG;i+=8,ii+=4)
     532             :       {
     533      585852 :         ulong rl = (x2>>i)&15UL, rh = (x2>>(i+4))&15UL;
     534      585852 :         z[jj]|=sq[rl|(rh<<1)]<<ii;
     535             :       }
     536       78786 :     if (j<lx)
     537             :     {
     538         257 :       x2 = x[j];
     539         257 :       if (x2)
     540        1762 :         for(i=0,ii=0;ii<BITS_IN_HALFULONG;i+=8,ii+=4)
     541             :         {
     542        1520 :           ulong rl = (x2>>i)&15UL, rh = (x2>>(i+4))&15UL;
     543        1520 :           z[jj]|=(sq[rl|(rh<<1)]<<ii)<<BITS_IN_HALFULONG;
     544             :         }
     545             :     }
     546             :   }
     547       78769 :   return F2x_renormalize(z, lz);
     548             : }
     549             : 
     550             : static GEN
     551        1341 : F2x_shiftneg(GEN y, ulong d)
     552             : {
     553        1341 :   long db, dl=dvmdsBIL(d, &db);
     554        1341 :   long i, ly = lg(y), lx = ly-dl;
     555        1341 :   GEN x = cgetg(lx, t_VECSMALL);
     556        1341 :   x[1] = y[1];
     557        1341 :   if (db)
     558             :   {
     559        1341 :     ulong dc=BITS_IN_LONG-db;
     560        1341 :     ulong r=0;
     561        2682 :     for(i=lx-1; i>=2; i--)
     562             :     {
     563        1341 :       x[i] = (((ulong)y[i+dl])>>db)|r;
     564        1341 :       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        1341 :   return F2x_renormalize(x,lx);
     571             : }
     572             : 
     573             : static GEN
     574      289710 : F2x_shiftpos(GEN y, ulong d)
     575             : {
     576      289710 :   long db, dl=dvmdsBIL(d, &db);
     577      289673 :   long i, ly = lg(y), lx = ly+dl+(!!db);
     578      289673 :   GEN x = cgetg(lx, t_VECSMALL);
     579      289740 :   x[1] = y[1]; for(i=0; i<dl; i++) x[i+2] = 0;
     580      289740 :   if (db)
     581             :   {
     582      289726 :     ulong dc=BITS_IN_LONG-db;
     583      289726 :     ulong r=0;
     584      586490 :     for(i=2; i<ly; i++)
     585             :     {
     586      296764 :       x[i+dl] = (((ulong)y[i])<<db)|r;
     587      296764 :       r = ((ulong)y[i])>>dc;
     588             :     }
     589      289726 :     x[i+dl] = r;
     590             :   }
     591             :   else
     592          28 :     for(i=2; i<ly; i++)
     593          14 :       x[i+dl] = y[i];
     594      289740 :   return F2x_renormalize(x,lx);
     595             : }
     596             : 
     597             : GEN
     598      291057 : F2x_shift(GEN y, long d)
     599             : {
     600      291057 :   return d<0 ? F2x_shiftneg(y,-d): F2x_shiftpos(y,d);
     601             : }
     602             : 
     603             : /* separate from F2x_divrem for maximal speed. */
     604             : GEN
     605    53491068 : F2x_rem(GEN x, GEN y)
     606             : {
     607             :   long dx,dy;
     608    53491068 :   long lx=lg(x);
     609    53491068 :   dy = F2x_degree(y); if (!dy) return pol0_F2x(x[1]);
     610    51351560 :   dx = F2x_degree_lg(x,lx);
     611    51189198 :   x  = F2x_copy(x);
     612   226989364 :   while (dx>=dy)
     613             :   {
     614   124486897 :     F2x_addshiftip(x,y,dx-dy);
     615   124210348 :     while (lx>2 && x[lx-1]==0) lx--;
     616   124210348 :     dx = F2x_degree_lg(x,lx);
     617             :   }
     618    51134712 :   return F2x_renormalize(x, lx);
     619             : }
     620             : 
     621             : GEN
     622    13032875 : F2x_divrem(GEN x, GEN y, GEN *pr)
     623             : {
     624    13032875 :   long dx, dy, dz, lx = lg(x), vs = x[1];
     625             :   GEN z;
     626             : 
     627    13032875 :   dy = F2x_degree(y);
     628    13033399 :   if (dy<0) pari_err_INV("F2x_divrem",y);
     629    13036398 :   if (pr == ONLY_REM) return F2x_rem(x, y);
     630    13036398 :   if (!dy)
     631             :   {
     632     3433811 :     z = F2x_copy(x);
     633     3433897 :     if (pr && pr != ONLY_DIVIDES) *pr = pol0_F2x(vs);
     634     3433897 :     return z;
     635             :   }
     636     9602587 :   dx = F2x_degree_lg(x,lx);
     637     9602532 :   dz = dx-dy;
     638     9602532 :   if (dz < 0)
     639             :   {
     640           0 :     if (pr == ONLY_DIVIDES) return dx < 0? F2x_copy(x): NULL;
     641           0 :     z = pol0_F2x(vs);
     642           0 :     if (pr) *pr = F2x_copy(x);
     643           0 :     return z;
     644             :   }
     645     9602532 :   z = zero_zv(lg(x)-lg(y)+2); z[1] = vs;
     646     9602594 :   x = F2x_copy(x);
     647    42448862 :   while (dx>=dy)
     648             :   {
     649    23244011 :     F2x_set(z,dx-dy);
     650    23255522 :     F2x_addshiftip(x,y,dx-dy);
     651    23242593 :     while (lx>2 && x[lx-1]==0) lx--;
     652    23242593 :     dx = F2x_degree_lg(x,lx);
     653             :   }
     654     9602310 :   z = F2x_renormalize(z, lg(z));
     655     9602551 :   if (!pr) { cgiv(x); return z; }
     656     8962316 :   x = F2x_renormalize(x, lx);
     657     8962316 :   if (pr == ONLY_DIVIDES) {
     658           0 :     if (lg(x) == 2) { cgiv(x); return z; }
     659           0 :     avma = (pari_sp)(z + lg(z)); return NULL;
     660             :   }
     661     8962316 :   *pr = x; return z;
     662             : }
     663             : 
     664             : long
     665       53129 : F2x_valrem(GEN x, GEN *Z)
     666             : {
     667       53129 :   long v, v2, i, l=lg(x);
     668             :   GEN y;
     669       53129 :   if (l==2) { *Z = F2x_copy(x); return LONG_MAX; }
     670       53129 :   for (i=2; i<l && x[i]==0; i++) /*empty*/;
     671       53129 :   v = i-2;
     672       53129 :   v2 = (i < l)? vals(x[i]): 0;
     673       53129 :   if (v+v2 == 0) { *Z = x; return 0; }
     674       17211 :   l -= i-2;
     675       17211 :   y = cgetg(l, t_VECSMALL); y[1] = x[1];
     676       17211 :   if (v2 == 0)
     677          89 :     for (i=2; i<l; i++) y[i] = x[i+v];
     678       17122 :   else if (l == 3)
     679       17115 :     y[2] = ((ulong)x[2+v]) >> v2;
     680             :   else
     681             :   {
     682           7 :     const ulong sh = BITS_IN_LONG - v2;
     683           7 :     ulong r = x[2+v];
     684          14 :     for (i=3; i<l; i++)
     685             :     {
     686           7 :       y[i-1] = (x[i+v] << sh) | (r >> v2);
     687           7 :       r = x[i+v];
     688             :     }
     689           7 :     y[l-1] = r >> v2;
     690           7 :     (void)F2x_renormalize(y,l);
     691             :   }
     692       17211 :   *Z = y; return (v << TWOPOTBITS_IN_LONG) + v2;
     693             : }
     694             : 
     695             : GEN
     696           0 : F2x_deflate(GEN x, long d)
     697             : {
     698             :   GEN y;
     699           0 :   long i,id, dy, dx = F2x_degree(x);
     700           0 :   if (d <= 1) return F2x_copy(x);
     701           0 :   if (dx < 0) return F2x_copy(x);
     702           0 :   dy = dx/d; /* dy+1 coefficients + 1 extra word for variable */
     703           0 :   y = zero_zv(nbits2lg(dy+1)-1); y[1] = x[1];
     704           0 :   for (i=id=0; i<=dy; i++,id+=d)
     705           0 :     if (F2x_coeff(x,id)) F2x_set(y, i);
     706           0 :   return y;
     707             : }
     708             : 
     709             : /* write p(X) = e(X^2) + Xo(X^2), shallow function */
     710             : void
     711       41111 : F2x_even_odd(GEN p, GEN *pe, GEN *po)
     712             : {
     713       41111 :   long n = F2x_degree(p), n0, n1, i;
     714             :   GEN p0, p1;
     715             : 
     716       82245 :   if (n <= 0) { *pe = F2x_copy(p); *po = pol0_F2x(p[1]); return; }
     717             : 
     718       38708 :   n0 = (n>>1)+1; n1 = n+1 - n0; /* n1 <= n0 <= n1+1 */
     719       38708 :   p0 = zero_zv(nbits2lg(n0+1)-1); p0[1] = p[1];
     720       38707 :   p1 = zero_zv(nbits2lg(n1+1)-1); p1[1] = p[1];
     721     1082914 :   for (i=0; i<n1; i++)
     722             :   {
     723     1044204 :     if (F2x_coeff(p,i<<1)) F2x_set(p0,i);
     724     1044581 :     if (F2x_coeff(p,1+(i<<1))) F2x_set(p1,i);
     725             :   }
     726       38710 :   if (n1 != n0 && F2x_coeff(p,i<<1)) F2x_set(p0,i);
     727       38711 :   *pe = F2x_renormalize(p0,lg(p0));
     728       38710 :   *po = F2x_renormalize(p1,lg(p1));
     729             : }
     730             : 
     731             : GEN
     732      853910 : F2x_deriv(GEN z)
     733             : {
     734      853910 :   const ulong mask = ULONG_MAX/3UL;
     735      853910 :   long i,l = lg(z);
     736      853910 :   GEN x = cgetg(l, t_VECSMALL); x[1] = z[1];
     737      853931 :   for (i=2; i<l; i++) x[i] = (((ulong)z[i])>>1)&mask;
     738      853931 :   return F2x_renormalize(x,l);
     739             : }
     740             : 
     741             : GEN
     742     3090505 : F2x_gcd(GEN a, GEN b)
     743             : {
     744     3090505 :   pari_sp av = avma;
     745     3090505 :   if (lg(b) > lg(a)) swap(a, b);
     746    31331323 :   while (lgpol(b))
     747             :   {
     748    25137423 :     GEN c = F2x_rem(a,b);
     749    25150313 :     a = b; b = c;
     750    25150313 :     if (gc_needed(av,2))
     751             :     {
     752           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2x_gcd (d = %ld)",F2x_degree(c));
     753           0 :       gerepileall(av,2, &a,&b);
     754             :     }
     755             :   }
     756     3084739 :   if (gc_needed(av,2)) a = gerepileuptoleaf(av, a);
     757     3084739 :   return a;
     758             : }
     759             : 
     760             : GEN
     761     1259886 : F2x_extgcd(GEN a, GEN b, GEN *ptu, GEN *ptv)
     762             : {
     763     1259886 :   pari_sp av=avma;
     764             :   GEN u,v,d,d1,v1;
     765     1259886 :   long vx = a[1];
     766     1259886 :   d = a; d1 = b;
     767     1259886 :   v = pol0_F2x(vx); v1 = pol1_F2x(vx);
     768    12734081 :   while (lgpol(d1))
     769             :   {
     770    10214308 :     GEN r, q = F2x_divrem(d,d1, &r);
     771    10214309 :     v = F2x_add(v,F2x_mul(q,v1));
     772    10214309 :     u=v; v=v1; v1=u;
     773    10214309 :     u=r; d=d1; d1=u;
     774    10214309 :     if (gc_needed(av,2))
     775             :     {
     776           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2x_extgcd (d = %ld)",F2x_degree(d));
     777           0 :       gerepileall(av,5, &d,&d1,&u,&v,&v1);
     778             :     }
     779             :   }
     780     1259888 :   if (ptu) *ptu = F2x_div(F2x_add(d, F2x_mul(b,v)), a);
     781     1259888 :   *ptv = v;
     782     1259888 :   if (gc_needed(av,2)) gerepileall(av,ptu?3:2,&d,ptv,ptu);
     783     1259888 :   return d;
     784             : }
     785             : 
     786             : static GEN
     787         480 : F2x_halfgcd_i(GEN a, GEN b)
     788             : {
     789         480 :   pari_sp av=avma;
     790             :   GEN u,u1,v,v1;
     791         480 :   long vx = a[1];
     792         480 :   long n = (F2x_degree(a)+1)>>1;
     793         480 :   u1 = v = pol0_F2x(vx);
     794         480 :   u = v1 = pol1_F2x(vx);
     795        8303 :   while (F2x_degree(b)>=n)
     796             :   {
     797        7343 :     GEN r, q = F2x_divrem(a,b, &r);
     798        7343 :     a = b; b = r; swap(u,u1); swap(v,v1);
     799        7343 :     u1 = F2x_add(u1, F2x_mul(u, q));
     800        7343 :     v1 = F2x_add(v1, F2x_mul(v, q));
     801        7343 :     if (gc_needed(av,2))
     802             :     {
     803           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2x_halfgcd (d = %ld)",F2x_degree(b));
     804           0 :       gerepileall(av,6, &a,&b,&u1,&v1,&u,&v);
     805             :     }
     806             :   }
     807         480 :   return gerepilecopy(av, mkmat2(mkcol2(u,u1), mkcol2(v,v1)));
     808             : }
     809             : 
     810             : GEN
     811         480 : F2x_halfgcd(GEN x, GEN y)
     812             : {
     813             :   pari_sp av;
     814             :   GEN M,q,r;
     815         480 :   if (F2x_degree(y)<F2x_degree(x)) return F2x_halfgcd_i(x,y);
     816         480 :   av = avma;
     817         480 :   q = F2x_divrem(y,x,&r);
     818         480 :   M = F2x_halfgcd_i(x,r);
     819         480 :   gcoeff(M,1,1) = F2x_add(gcoeff(M,1,1), F2x_mul(q, gcoeff(M,1,2)));
     820         480 :   gcoeff(M,2,1) = F2x_add(gcoeff(M,2,1), F2x_mul(q, gcoeff(M,2,2)));
     821         480 :   return gerepilecopy(av, M);
     822             : }
     823             : 
     824             : GEN
     825     8329459 : F2xq_mul(GEN x,GEN y,GEN pol)
     826             : {
     827     8329459 :   GEN z = F2x_mul(x,y);
     828     8329528 :   return F2x_rem(z,pol);
     829             : }
     830             : 
     831             : GEN
     832     8165389 : F2xq_sqr(GEN x,GEN pol)
     833             : {
     834     8165389 :   GEN z = F2x_sqr(x);
     835     8172643 :   return F2x_rem(z,pol);
     836             : }
     837             : 
     838             : GEN
     839     1259886 : F2xq_invsafe(GEN x, GEN T)
     840             : {
     841     1259886 :   GEN V, z = F2x_extgcd(T, x, NULL, &V);
     842     1259886 :   if (F2x_degree(z)) return NULL;
     843     1259818 :   return V;
     844             : }
     845             : 
     846             : GEN
     847     1259886 : F2xq_inv(GEN x,GEN T)
     848             : {
     849     1259886 :   pari_sp av=avma;
     850     1259886 :   GEN U = F2xq_invsafe(x, T);
     851     1259888 :   if (!U) pari_err_INV("F2xq_inv", F2x_to_ZX(x));
     852     1259818 :   return gerepileuptoleaf(av, U);
     853             : }
     854             : 
     855             : GEN
     856      504161 : F2xq_div(GEN x,GEN y,GEN T)
     857             : {
     858      504161 :   pari_sp av = avma;
     859      504161 :   return gerepileuptoleaf(av, F2xq_mul(x,F2xq_inv(y,T),T));
     860             : }
     861             : 
     862             : static GEN
     863      516320 : _F2xq_red(void *E, GEN x)
     864      516320 : { return F2x_rem(x, (GEN)E); }
     865             : static GEN
     866     1291127 : _F2xq_add(void *E, GEN x, GEN y)
     867     1291127 : { (void)E; return F2x_add(x,y); }
     868             : 
     869             : static GEN
     870     1674142 : _F2xq_cmul(void *E, GEN P, long a, GEN x)
     871             : {
     872     1674142 :   GEN pol = (GEN) E;
     873     1674142 :   return F2x_coeff(P,a) ? x: pol0_F2x(pol[1]);
     874             : }
     875             : static GEN
     876     1116326 : _F2xq_sqr(void *E, GEN x)
     877     1116326 : { return F2xq_sqr(x, (GEN) E); }
     878             : 
     879             : static GEN
     880     1334780 : _F2xq_mul(void *E, GEN x, GEN y)
     881     1334780 : { return F2xq_mul(x,y, (GEN) E); }
     882             : 
     883             : static GEN
     884      857530 : _F2xq_one(void *E)
     885             : {
     886      857530 :   GEN pol = (GEN) E;
     887      857530 :   return pol1_F2x(pol[1]);
     888             : }
     889             : static GEN
     890      259406 : _F2xq_zero(void *E)
     891             : {
     892      259406 :   GEN pol = (GEN) E;
     893      259406 :   return pol0_F2x(pol[1]);
     894             : }
     895             : 
     896             : GEN
     897      390709 : F2xq_pow(GEN x, GEN n, GEN pol)
     898             : {
     899      390709 :   pari_sp av=avma;
     900             :   GEN y;
     901             : 
     902      390709 :   if (!signe(n)) return pol1_F2x(x[1]);
     903      384374 :   if (is_pm1(n)) /* +/- 1 */
     904      188639 :     return (signe(n) < 0)? F2xq_inv(x,pol): F2x_copy(x);
     905             : 
     906      195735 :   if (signe(n) < 0) x = F2xq_inv(x,pol);
     907      195735 :   y = gen_pow(x, n, (void*)pol, &_F2xq_sqr, &_F2xq_mul);
     908      195735 :   return gerepileupto(av, y);
     909             : }
     910             : 
     911             : GEN
     912           0 : F2xq_powu(GEN x, ulong n, GEN pol)
     913             : {
     914           0 :   pari_sp av=avma;
     915             :   GEN y;
     916           0 :   switch(n)
     917             :   {
     918           0 :     case 0: return pol1_F2x(x[1]);
     919           0 :     case 1: return F2x_copy(x);
     920           0 :     case 2: return F2xq_sqr(x,pol);
     921             :   }
     922           0 :   y = gen_powu(x, n, (void*)pol, &_F2xq_sqr, &_F2xq_mul);
     923           0 :   return gerepileupto(av, y);
     924             : }
     925             : 
     926             : /* generates the list of powers of x of degree 0,1,2,...,l*/
     927             : GEN
     928      358444 : F2xq_powers(GEN x, long l, GEN T)
     929             : {
     930      358444 :   int use_sqr = 2*F2x_degree(x) >= F2x_degree(T);
     931      358444 :   return gen_powers(x, l, use_sqr, (void*)T, &_F2xq_sqr, &_F2xq_mul, &_F2xq_one);
     932             : }
     933             : 
     934             : GEN
     935      229637 : F2xq_matrix_pow(GEN y, long n, long m, GEN P)
     936             : {
     937      229637 :   return F2xV_to_F2m(F2xq_powers(y,m-1,P),n);
     938             : }
     939             : 
     940             : GEN
     941      326658 : F2x_Frobenius(GEN T)
     942             : {
     943      326658 :   return F2xq_sqr(polx_F2x(T[1]), T);
     944             : }
     945             : 
     946             : GEN
     947      229637 : F2x_matFrobenius(GEN T)
     948             : {
     949      229637 :   long n = F2x_degree(T);
     950      229637 :   return F2xq_matrix_pow(F2x_Frobenius(T), n, n, T);
     951             : }
     952             : 
     953             : static struct bb_algebra F2xq_algebra = { _F2xq_red, _F2xq_add, _F2xq_add,
     954             :               _F2xq_mul, _F2xq_sqr, _F2xq_one, _F2xq_zero};
     955             : 
     956             : GEN
     957      606774 : F2x_F2xqV_eval(GEN Q, GEN x, GEN T)
     958             : {
     959      606774 :   long d = F2x_degree(Q);
     960      606774 :   return gen_bkeval_powers(Q,d,x,(void*)T,&F2xq_algebra,_F2xq_cmul);
     961             : }
     962             : 
     963             : GEN
     964       35929 : F2x_F2xq_eval(GEN Q, GEN x, GEN T)
     965             : {
     966       35929 :   long d = F2x_degree(Q);
     967       35927 :   int use_sqr = 2*F2x_degree(x) >= F2x_degree(T);
     968       35928 :   return gen_bkeval(Q, d, x, use_sqr, (void*)T, &F2xq_algebra, _F2xq_cmul);
     969             : }
     970             : 
     971             : static GEN
     972       23301 : F2xq_autpow_sqr(void * T, GEN x) { return F2x_F2xq_eval(x, x, (GEN) T); }
     973             : 
     974             : static GEN
     975       12600 : F2xq_autpow_mul(void * T, GEN x, GEN y) { return F2x_F2xq_eval(x, y, (GEN) T); }
     976             : 
     977             : GEN
     978       15035 : F2xq_autpow(GEN x, long n, GEN T)
     979             : {
     980       15035 :   return gen_powu(x,n,(void*)T,F2xq_autpow_sqr,F2xq_autpow_mul);
     981             : }
     982             : 
     983             : ulong
     984      459361 : F2xq_trace(GEN x, GEN T)
     985             : {
     986      459361 :   pari_sp av = avma;
     987             :   ulong t;
     988      459361 :   long n = F2x_degree(T)-1;
     989      459361 :   GEN z = F2x_mul(x, F2x_deriv(T));
     990      459361 :   z = F2x_rem(z, T);
     991      459361 :   t = F2x_degree(z)<n ? 0 : 1;
     992      459361 :   avma = av; return t;
     993             : }
     994             : 
     995             : GEN
     996           7 : F2xq_conjvec(GEN x, GEN T)
     997             : {
     998           7 :   long i, l = F2x_degree(T);
     999           7 :   GEN z = cgetg(l,t_COL);
    1000           7 :   gel(z,1) = F2x_copy(x);
    1001           7 :   for (i=2; i<l; i++) gel(z,i) = F2xq_sqr(gel(z,i-1), T);
    1002           7 :   return z;
    1003             : }
    1004             : 
    1005             : static GEN
    1006      342223 : _F2xq_pow(void *data, GEN x, GEN n)
    1007             : {
    1008      342223 :   GEN pol = (GEN) data;
    1009      342223 :   return F2xq_pow(x,n, pol);
    1010             : }
    1011             : 
    1012             : static GEN
    1013        9317 : _F2xq_rand(void *data)
    1014             : {
    1015        9317 :   pari_sp av=avma;
    1016        9317 :   GEN pol = (GEN) data;
    1017        9317 :   long d = F2x_degree(pol);
    1018             :   GEN z;
    1019             :   do
    1020             :   {
    1021        9485 :     avma = av;
    1022        9485 :     z = random_F2x(d,pol[1]);
    1023        9485 :   } while (lgpol(z)==0);
    1024        9317 :   return z;
    1025             : }
    1026             : 
    1027             : static GEN F2xq_easylog(void* E, GEN a, GEN g, GEN ord);
    1028             : 
    1029             : static const struct bb_group F2xq_star={_F2xq_mul,_F2xq_pow,_F2xq_rand,hash_GEN,F2x_equal,F2x_equal1,F2xq_easylog};
    1030             : 
    1031             : GEN
    1032         350 : F2xq_order(GEN a, GEN ord, GEN T)
    1033             : {
    1034         350 :   return gen_order(a,ord,(void*)T,&F2xq_star);
    1035             : }
    1036             : 
    1037             : static long
    1038      279048 : F2x_is_smooth_squarefree(GEN f, long r)
    1039             : {
    1040      279048 :   pari_sp av = avma;
    1041             :   long i;
    1042      279048 :   GEN sx = polx_F2x(f[1]), a = sx;
    1043     2617937 :   for(i=1;  ;i++)
    1044             :   {
    1045     2617937 :     a = F2xq_sqr(F2x_rem(a,f),f);
    1046     2614857 :     if (F2x_equal(a, F2x_rem(sx,f))) {avma = av; return 1;}
    1047     2522668 :     if (i==r) {avma = av; return 0;}
    1048     2336662 :     f = F2x_div(f, F2x_gcd(F2x_add(a,sx),f));
    1049     2338864 :   }
    1050             : }
    1051             : 
    1052             : static long
    1053      243462 : F2x_is_smooth(GEN g, long r)
    1054             : {
    1055      243462 :   GEN f = gen_0;
    1056      243462 :   if (lgpol(g)==0) return 0;
    1057             :   while (1)
    1058             :   {
    1059      279088 :     f = F2x_gcd(g, F2x_deriv(g));
    1060      279044 :     if (!F2x_is_smooth_squarefree(F2x_div(g, f), r))
    1061      186018 :       return 0;
    1062       93090 :     if (F2x_degree(f)==0) return 1;
    1063       35634 :     g = F2x_issquare(f) ? F2x_sqrt(f): f;
    1064       35639 :   }
    1065             : }
    1066             : 
    1067             : static GEN
    1068       15201 : F2x_factorel(GEN h)
    1069             : {
    1070       15201 :   GEN F = F2x_factcantor(h, 0);
    1071       15202 :   GEN F1 = gel(F, 1), F2 = gel(F, 2);
    1072       15202 :   long i, l1 = lg(F1)-1;
    1073       15202 :   GEN p2 = cgetg(l1+1, t_VECSMALL);
    1074       15201 :   GEN e2 = cgetg(l1+1, t_VECSMALL);
    1075       71159 :   for (i = 1; i <= l1; ++i)
    1076             :   {
    1077       55958 :     p2[i] = mael(F1, i, 2);
    1078       55958 :     e2[i] = F2[i];
    1079             :   }
    1080       15201 :   return mkmat2(p2, e2);
    1081             : }
    1082             : 
    1083             : static GEN
    1084       22992 : mkF2(ulong x, long v) { return mkvecsmall2(v, x); }
    1085             : 
    1086             : static GEN F2xq_log_Coppersmith_d(GEN W, GEN g, long r, long n, GEN T, GEN mo);
    1087             : 
    1088             : static GEN
    1089          97 : F2xq_log_from_rel(GEN W, GEN rel, long r, long n, GEN T, GEN m)
    1090             : {
    1091          97 :   pari_sp av = avma;
    1092          97 :   GEN F = gel(rel,1), E = gel(rel,2), o = gen_0;
    1093          97 :   long i, l = lg(F);
    1094         904 :   for(i=1; i<l; i++)
    1095             :   {
    1096         807 :     GEN R = gel(W, F[i]);
    1097         807 :     if (signe(R)==0) /* Already failed */
    1098           0 :       return NULL;
    1099         807 :     else if (signe(R)<0) /* Not yet tested */
    1100             :     {
    1101           7 :       setsigne(gel(W,F[i]),0);
    1102           7 :       R = F2xq_log_Coppersmith_d(W, mkF2(F[i],T[1]), r, n, T, m);
    1103           7 :       if (!R) return NULL;
    1104             :     }
    1105         807 :     o = Fp_add(o, mulis(R, E[i]), m);
    1106             :   }
    1107          97 :   return gerepileuptoint(av, o);
    1108             : }
    1109             : 
    1110             : static GEN
    1111         115 : F2xq_log_Coppersmith_d(GEN W, GEN g, long r, long n, GEN T, GEN mo)
    1112             : {
    1113         115 :   pari_sp av = avma, av2;
    1114         115 :   long dg = F2x_degree(g), k = r-1, m = maxss((dg-k)/2,0);
    1115         115 :   long i, j, l = dg-m, N;
    1116         115 :   GEN v = cgetg(k+m+1,t_MAT);
    1117         115 :   long dT = F2x_degree(T);
    1118         115 :   long h = dT>>n, d = dT-(h<<n);
    1119         115 :   GEN R = F2x_add(F2x_shift(pol1_F2x(T[1]), dT), T);
    1120         115 :   GEN z = F2x_rem(F2x_shift(pol1_F2x(T[1]),h), g);
    1121        1456 :   for(i=1; i<=k+m; i++)
    1122             :   {
    1123        1341 :     gel(v,i) = F2x_to_F2v(F2x_shift(z,-l),m);
    1124        1341 :     z = F2x_rem(F2x_shift(z,1),g);
    1125             :   }
    1126         115 :   v = F2m_ker(v);
    1127        1265 :   for(i=1; i<=k; i++)
    1128        1150 :     gel(v,i) = F2v_to_F2x(gel(v,i),T[1]);
    1129         115 :   N = 1<<k;
    1130         115 :   av2 = avma;
    1131       45517 :   for (i=1; i<N; i++)
    1132             :   {
    1133             :     GEN p,q,qh,a,b;
    1134       45499 :     avma = av2;
    1135       45499 :     q = pol0_F2x(T[1]);
    1136      500489 :     for(j=0; j<k; j++)
    1137      454990 :       if (i&(1UL<<j))
    1138      207759 :         q = F2x_add(q, gel(v,j+1));
    1139       45499 :     qh= F2x_shift(q,h);
    1140       45499 :     p = F2x_rem(qh,g);
    1141       45499 :     b = F2x_add(F2x_mul(R, F2x_pow2n(q, n)), F2x_shift(F2x_pow2n(p, n), d));
    1142       45499 :     if (lgpol(b)==0 || !F2x_is_smooth(b, r)) continue;
    1143         123 :     a = F2x_div(F2x_add(qh,p),g);
    1144         123 :     if (F2x_degree(F2x_gcd(a,q)) &&  F2x_degree(F2x_gcd(a,p))) continue;
    1145         122 :     if (!(lgpol(a)==0 || !F2x_is_smooth(a, r)))
    1146             :     {
    1147          97 :       GEN F = F2x_factorel(b);
    1148          97 :       GEN G = F2x_factorel(a);
    1149          97 :       GEN FG = vecsmall_concat(vecsmall_append(gel(F, 1), 2), gel(G, 1));
    1150         194 :       GEN E  = vecsmall_concat(vecsmall_append(gel(F, 2), -d),
    1151         194 :                                zv_z_mul(gel(G, 2),-(1L<<n)));
    1152          97 :       GEN R  = famatsmall_reduce(mkmat2(FG, E));
    1153          97 :       GEN l  = F2xq_log_from_rel(W, R, r, n, T, mo);
    1154          97 :       if (!l) continue;
    1155          97 :       l = Fp_div(l,int2n(n),mo);
    1156          97 :       if (dg <= r)
    1157             :       {
    1158           7 :         affii(l,gel(W,g[2]));
    1159           7 :         if (DEBUGLEVEL>1) err_printf("Found %lu\n", g[2]);
    1160             :       }
    1161          97 :       return gerepileuptoint(av, l);
    1162             :     }
    1163             :   }
    1164          18 :   avma = av;
    1165          18 :   return NULL;
    1166             : }
    1167             : 
    1168             : static GEN
    1169         136 : F2xq_log_find_rel(GEN b, long r, GEN T, GEN *g, ulong *e)
    1170             : {
    1171         136 :   pari_sp av = avma;
    1172             :   while (1)
    1173             :   {
    1174             :     GEN M;
    1175         480 :     *g = F2xq_mul(*g, b, T); (*e)++;
    1176         480 :     M = F2x_halfgcd(*g,T);
    1177         480 :     if (F2x_is_smooth(gcoeff(M,1,1), r))
    1178             :     {
    1179         250 :       GEN z = F2x_add(F2x_mul(gcoeff(M,1,1),*g), F2x_mul(gcoeff(M,1,2),T));
    1180         250 :       if (F2x_is_smooth(z, r))
    1181             :       {
    1182         136 :         GEN F = F2x_factorel(z);
    1183         136 :         GEN G = F2x_factorel(gcoeff(M,1,1));
    1184         272 :         GEN rel = mkmat2(vecsmall_concat(gel(F, 1),gel(G, 1)),
    1185         272 :                          vecsmall_concat(gel(F, 2),zv_neg(gel(G, 2))));
    1186         136 :         gerepileall(av, 2, g, &rel);
    1187         272 :         return rel;
    1188             :       }
    1189             :     }
    1190         344 :     if (gc_needed(av,2))
    1191             :     {
    1192           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2xq_log_find_rel");
    1193           0 :       *g = gerepileuptoleaf(av, *g);
    1194             :     }
    1195         344 :   }
    1196             : }
    1197             : 
    1198             : static GEN
    1199          28 : F2xq_log_Coppersmith_rec(GEN W, long r2, GEN a, long r, long n, GEN T, GEN m)
    1200             : {
    1201          28 :   GEN b = polx_F2x(T[1]);
    1202          28 :   ulong AV = 0;
    1203          28 :   GEN g = a, bad = pol0_F2x(T[1]);
    1204             :   pari_timer ti;
    1205             :   while(1)
    1206             :   {
    1207             :     long i, l;
    1208             :     GEN V, F, E, Ao;
    1209         136 :     timer_start(&ti);
    1210         136 :     V = F2xq_log_find_rel(b, r2, T, &g, &AV);
    1211         136 :     if (DEBUGLEVEL>1) timer_printf(&ti,"%ld-smooth element",r2);
    1212         136 :     F = gel(V,1); E = gel(V,2);
    1213         136 :     l = lg(F);
    1214         136 :     Ao = gen_0;
    1215         688 :     for(i=1; i<l; i++)
    1216             :     {
    1217         660 :       GEN Fi = mkF2(F[i], T[1]);
    1218             :       GEN R;
    1219         660 :       if (F2x_degree(Fi) <= r)
    1220             :       {
    1221         462 :         if (signe(gel(W,F[i]))==0)
    1222           0 :           break;
    1223         462 :         else if (signe(gel(W,F[i]))<0)
    1224             :         {
    1225           0 :           setsigne(gel(W,F[i]),0);
    1226           0 :           R = F2xq_log_Coppersmith_d(W,Fi,r,n,T,m);
    1227             :         } else
    1228         462 :           R = gel(W,F[i]);
    1229             :       }
    1230             :       else
    1231             :       {
    1232         198 :         if (F2x_equal(Fi,bad)) break;
    1233         108 :         R = F2xq_log_Coppersmith_d(W,Fi,r,n,T,m);
    1234         108 :         if (!R) bad = Fi;
    1235             :       }
    1236         570 :       if (!R) break;
    1237         552 :       Ao = Fp_add(Ao, mulis(R, E[i]), m);
    1238             :     }
    1239         164 :     if (i==l) return subis(Ao,AV);
    1240         108 :   }
    1241             : }
    1242             : 
    1243             : /* Coppersmith:
    1244             :  T*X^e = X^(h*2^n)-R
    1245             :  (u*x^h + v)^(2^n) = u^(2^n)*X^(h*2^n)+v^(2^n)
    1246             :  (u*x^h + v)^(2^n) = u^(2^n)*R+v^(2^n)
    1247             : */
    1248             : 
    1249             : static GEN
    1250      147659 : rel_Coppersmith(GEN u, GEN v, long h, GEN R, long r, long n, long d)
    1251             : {
    1252             :   GEN b, F, G, M;
    1253      147659 :   GEN a = F2x_add(F2x_shift(u, h), v);
    1254      147645 :   if (!F2x_is_smooth(a, r)) return NULL;
    1255       49499 :   b = F2x_add(F2x_mul(R, F2x_pow2n(u, n)), F2x_shift(F2x_pow2n(v, n),d));
    1256       49494 :   if (!F2x_is_smooth(b, r)) return NULL;
    1257        7368 :   F = F2x_factorel(a);
    1258        7368 :   G = F2x_factorel(b);
    1259       22103 :   M = mkmat2(vecsmall_concat(gel(F, 1), vecsmall_append(gel(G, 1), 2)),
    1260       22103 :              vecsmall_concat(zv_z_mul(gel(F, 2),1UL<<n), vecsmall_append(zv_neg(gel(G, 2)),d)));
    1261        7368 :   return famatsmall_reduce(M);
    1262             : }
    1263             : 
    1264             : GEN
    1265        2035 : F2xq_log_Coppersmith_worker(GEN u, long i, GEN V, GEN R)
    1266             : {
    1267        2035 :   long r = V[1], h = V[2], n = V[3], d = V[4];
    1268        2035 :   pari_sp ltop = avma;
    1269        2035 :   GEN v = mkF2(0,u[1]);
    1270        2035 :   GEN L = cgetg(2*i+1, t_VEC);
    1271        2038 :   pari_sp av = avma;
    1272             :   long j;
    1273        2038 :   long nbtest=0, rel = 1;
    1274      148296 :   for(j=1; j<=i; j++)
    1275             :   {
    1276      146253 :     v[2] = j;
    1277      146253 :     avma = av;
    1278      146253 :     if (F2x_degree(F2x_gcd(u,v))==0)
    1279             :     {
    1280       73836 :       GEN z = rel_Coppersmith(u, v, h, R, r, n, d);
    1281       73844 :       nbtest++;
    1282       73844 :       if (z) { gel(L, rel++) = z; av = avma; }
    1283       73844 :       if (i==j) continue;
    1284       73830 :       z = rel_Coppersmith(v, u, h, R, r, n, d);
    1285       73829 :       nbtest++;
    1286       73829 :       if (z) { gel(L, rel++) = z; av = avma; }
    1287             :     }
    1288             :   }
    1289        2043 :   setlg(L,rel);
    1290        2043 :   return gerepilecopy(ltop, mkvec2(stoi(nbtest), L));
    1291             : }
    1292             : 
    1293             : static GEN
    1294          14 : F2xq_log_Coppersmith(long nbrel, long r, long n, GEN T)
    1295             : {
    1296          14 :   long dT = F2x_degree(T);
    1297          14 :   long h = dT>>n, d = dT-(h<<n);
    1298          14 :   GEN R = F2x_add(F2x_shift(pol1_F2x(T[1]), dT), T);
    1299          14 :   GEN u = mkF2(0,T[1]);
    1300          14 :   long rel = 1, nbtest = 0;
    1301          14 :   GEN M = cgetg(nbrel+1, t_VEC);
    1302          14 :   long i = 0;
    1303          14 :   GEN worker = snm_closure(is_entry("_F2xq_log_Coppersmith_worker"),
    1304             :                mkvec2(mkvecsmall4(r, h, n, d), R));
    1305             :   struct pari_mt pt;
    1306          14 :   long running, pending = 0, stop=0;
    1307          14 :   mt_queue_start(&pt, worker);
    1308          14 :   if (DEBUGLEVEL) err_printf("Coppersmith (R = %ld): ",F2x_degree(R));
    1309        2104 :   while ((running = !stop) || pending)
    1310             :   {
    1311             :     GEN L, done;
    1312             :     long j, l;
    1313        2076 :     u[2] = i;
    1314        2076 :     mt_queue_submit(&pt, 0, running ? mkvec2(u, stoi(i)): NULL);
    1315        2076 :     done = mt_queue_get(&pt, NULL, &pending);
    1316        2076 :     if (!done) continue;
    1317        2046 :     L = gel(done, 2); nbtest += itos(gel(done,1));
    1318        2046 :     l = lg(L);
    1319        2046 :     if (l > 1)
    1320             :     {
    1321        9117 :       for (j=1; j<l; j++)
    1322             :       {
    1323        7244 :         if (rel>nbrel) break;
    1324        7210 :         gel(M,rel++) = gel(L,j);
    1325        7210 :         if (DEBUGLEVEL && (rel&511UL)==0)
    1326           0 :           err_printf("%ld%%[%ld] ",rel*100/nbrel,i);
    1327             :       }
    1328             :     }
    1329        2046 :     if (rel>nbrel) stop=1;
    1330        2046 :     i++;
    1331             :   }
    1332          14 :   mt_queue_end(&pt);
    1333          14 :   if (DEBUGLEVEL) err_printf(": %ld tests\n", nbtest);
    1334          14 :   return M;
    1335             : }
    1336             : 
    1337             : static GEN
    1338          14 : smallirred_F2x(ulong n, long sv)
    1339             : {
    1340          14 :   GEN a = zero_zv(nbits2lg(n+1)-1);
    1341          14 :   a[1] = sv; F2x_set(a,n); a[2]++;
    1342          14 :   while (!F2x_is_irred(a)) a[2]+=2;
    1343          14 :   return a;
    1344             : }
    1345             : 
    1346             : static GEN
    1347          14 : check_kernel(long N, GEN M, long nbi, GEN T, GEN m)
    1348             : {
    1349          14 :   pari_sp av = avma;
    1350          14 :   GEN K = FpMs_leftkernel_elt(M, N, m);
    1351          14 :   long i, f=0;
    1352          14 :   long l = lg(K), lm = lgefint(m);
    1353          14 :   GEN idx = diviiexact(subis(int2n(F2x_degree(T)),1),m);
    1354          14 :   GEN g = F2xq_pow(polx_F2x(T[1]), idx, T);
    1355             :   pari_timer ti;
    1356          14 :   if (DEBUGLEVEL) timer_start(&ti);
    1357          14 :   K = FpC_Fp_mul(K, Fp_inv(gel(K,2), m), m);
    1358       57344 :   for(i=1; i<l; i++)
    1359             :   {
    1360       57330 :     GEN k = gel(K,i);
    1361       62570 :     if (signe(k)==0 || !F2x_equal(F2xq_pow(g, k, T),
    1362        5240 :                                   F2xq_pow(mkF2(i,T[1]), idx, T)))
    1363       52090 :       gel(K,i) = cgetineg(lm);
    1364             :     else
    1365        5240 :       f++;
    1366             :   }
    1367          14 :   if (DEBUGLEVEL) timer_printf(&ti,"found %ld/%ld logs", f, nbi);
    1368          14 :   return gerepileupto(av, K);
    1369             : }
    1370             : 
    1371             : static GEN
    1372          14 : F2xq_log_index(GEN a0, GEN b0, GEN m, GEN T0)
    1373             : {
    1374          14 :   pari_sp av = avma;
    1375          14 :   GEN  M, S, a, b, Ao=NULL, Bo=NULL, W, e;
    1376             :   pari_timer ti;
    1377          14 :   long n = F2x_degree(T0), r = (long) (sqrt((double) 2*n))-(n>100);
    1378          14 :   GEN T = smallirred_F2x(n,T0[1]);
    1379          14 :   long d = 2, r2 = 3*r/2, d2 = 2;
    1380          14 :   long N = (1UL<<(r+1))-1UL;
    1381          14 :   long nbi = itos(ffsumnbirred(gen_2, r)), nbrel=nbi*5/4;
    1382          14 :   if (DEBUGLEVEL)
    1383             :   {
    1384           0 :     err_printf("F2xq_log: Parameters r=%ld r2=%ld\n", r,r2);
    1385           0 :     err_printf("F2xq_log: Size FB=%ld rel. needed=%ld\n", nbi, nbrel);
    1386           0 :     timer_start(&ti);
    1387             :   }
    1388          14 :   S = Flx_to_F2x(Flx_ffisom(F2x_to_Flx(T0),F2x_to_Flx(T),2));
    1389          14 :   a = F2x_F2xq_eval(a0, S, T);
    1390          14 :   b = F2x_F2xq_eval(b0, S, T);
    1391          14 :   if (DEBUGLEVEL) timer_printf(&ti,"model change");
    1392          14 :   M = F2xq_log_Coppersmith(nbrel,r,d,T);
    1393          14 :   if(DEBUGLEVEL)
    1394           0 :     timer_printf(&ti,"relations");
    1395          14 :   W = check_kernel(N, M, nbi, T, m);
    1396          14 :   timer_start(&ti);
    1397          14 :   Ao = F2xq_log_Coppersmith_rec(W, r2, a, r, d2, T, m);
    1398          14 :   if (DEBUGLEVEL) timer_printf(&ti,"smooth element");
    1399          14 :   Bo = F2xq_log_Coppersmith_rec(W, r2, b, r, d2, T, m);
    1400          14 :   if (DEBUGLEVEL) timer_printf(&ti,"smooth generator");
    1401          14 :   e = Fp_div(Ao, Bo, m);
    1402          14 :   if (!F2x_equal(F2xq_pow(b0,e,T0),a0)) pari_err_BUG("F2xq_log");
    1403          14 :   return gerepileupto(av, e);
    1404             : }
    1405             : 
    1406             : static GEN
    1407       75222 : F2xq_easylog(void* E, GEN a, GEN g, GEN ord)
    1408             : {
    1409       75222 :   if (F2x_equal1(a)) return gen_0;
    1410       63238 :   if (F2x_equal(a,g)) return gen_1;
    1411       57911 :   if (typ(ord)!=t_INT) return NULL;
    1412       29421 :   if (expi(ord)<28) return NULL;
    1413          14 :   return F2xq_log_index(a,g,ord,(GEN)E);
    1414             : }
    1415             : 
    1416             : GEN
    1417       40845 : F2xq_log(GEN a, GEN g, GEN ord, GEN T)
    1418             : {
    1419       40845 :   GEN z, v = get_arith_ZZM(ord);
    1420       40845 :   ord = mkvec2(gel(v,1),ZM_famat_limit(gel(v,2),int2n(28)));
    1421       40845 :   z = gen_PH_log(a,g,ord,(void*)T,&F2xq_star);
    1422       40845 :   return z? z: cgetg(1,t_VEC);
    1423             : }
    1424             : 
    1425             : GEN
    1426      212562 : F2xq_Artin_Schreier(GEN a, GEN T)
    1427             : {
    1428      212562 :   pari_sp ltop=avma;
    1429      212562 :   long j,N = F2x_degree(T);
    1430      212562 :   GEN Q = F2x_matFrobenius(T);
    1431     1475397 :   for (j=1; j<=N; j++)
    1432     1262835 :     F2m_flip(Q,j,j);
    1433      212562 :   F2v_add_inplace(gel(Q,1),a);
    1434      212562 :   Q = F2m_ker_sp(Q,0);
    1435      212562 :   if (lg(Q)!=2) return NULL;
    1436      212562 :   Q = gel(Q,1);
    1437      212562 :   Q[1] = T[1];
    1438      212562 :   return gerepileuptoleaf(ltop, F2x_renormalize(Q, lg(Q)));
    1439             : }
    1440             : 
    1441             : GEN
    1442       41113 : F2xq_sqrt_fast(GEN c, GEN sqx, GEN T)
    1443             : {
    1444             :   GEN c0, c1;
    1445       41113 :   F2x_even_odd(c, &c0, &c1);
    1446       41121 :   return F2x_add(c0, F2xq_mul(c1, sqx, T));
    1447             : }
    1448             : 
    1449             : static int
    1450       15035 : F2x_is_x(GEN a) { return lg(a)==3 && a[2]==2; }
    1451             : 
    1452             : GEN
    1453       29504 : F2xq_sqrt(GEN a, GEN T)
    1454             : {
    1455       29504 :   pari_sp av = avma;
    1456       29504 :   long n = F2x_degree(T);
    1457             :   GEN sqx;
    1458       29505 :   if (n==1) return F2x_copy(a);
    1459       29463 :   if (n==2) return F2xq_sqr(a,T);
    1460       15036 :   sqx = F2xq_autpow(mkF2(4, T[1]), n-1, T);
    1461       15035 :   return gerepileuptoleaf(av, F2x_is_x(a)? sqx: F2xq_sqrt_fast(a,sqx,T));
    1462             : }
    1463             : 
    1464             : GEN
    1465        7777 : F2xq_sqrtn(GEN a, GEN n, GEN T, GEN *zeta)
    1466             : {
    1467        7777 :   if (!lgpol(a))
    1468             :   {
    1469           7 :     if (signe(n) < 0) pari_err_INV("F2xq_sqrtn",a);
    1470           0 :     if (zeta)
    1471           0 :       *zeta=pol1_F2x(T[1]);
    1472           0 :     return pol0_F2x(T[1]);
    1473             :   }
    1474        7770 :   return gen_Shanks_sqrtn(a,n,addis(powuu(2,F2x_degree(T)),-1),zeta,(void*)T,&F2xq_star);
    1475             : }
    1476             : 
    1477             : GEN
    1478         154 : gener_F2xq(GEN T, GEN *po)
    1479             : {
    1480         154 :   long i, j, vT = T[1], f = F2x_degree(T);
    1481         154 :   pari_sp av0 = avma, av;
    1482             :   GEN g, L2, o, q;
    1483             : 
    1484         154 :   if (f == 1) {
    1485          21 :     if (po) *po = mkvec2(gen_1, trivial_fact());
    1486          21 :     return pol1_F2x(vT);
    1487             :   }
    1488         133 :   q = subis(powuu(2,f), 1);
    1489         133 :   o = factor_pn_1(gen_2,f);
    1490         133 :   L2 = leafcopy( gel(o, 1) );
    1491         385 :   for (i = j = 1; i < lg(L2); i++)
    1492             :   {
    1493         252 :     if (absequaliu(gel(L2,i),2)) continue;
    1494         252 :     gel(L2,j++) = diviiexact(q, gel(L2,i));
    1495             :   }
    1496         133 :   setlg(L2, j);
    1497         154 :   for (av = avma;; avma = av)
    1498             :   {
    1499         154 :     g = random_F2x(f, vT);
    1500         154 :     if (F2x_degree(g) < 1) continue;
    1501         392 :     for (i = 1; i < j; i++)
    1502             :     {
    1503         259 :       GEN a = F2xq_pow(g, gel(L2,i), T);
    1504         259 :       if (F2x_equal1(a)) break;
    1505             :     }
    1506         140 :     if (i == j) break;
    1507          21 :   }
    1508         133 :   if (!po) g = gerepilecopy(av0, g);
    1509             :   else {
    1510           0 :     *po = mkvec2(subis(int2n(f), 1), o);
    1511           0 :     gerepileall(av0, 2, &g, po);
    1512             :   }
    1513         133 :   return g;
    1514             : }
    1515             : 
    1516             : static GEN
    1517         182 : _F2xq_neg(void *E, GEN x)
    1518         182 : { (void) E; return F2x_copy(x); }
    1519             : 
    1520             : static GEN
    1521         777 : _F2xq_rmul(void *E, GEN x, GEN y)
    1522         777 : { (void) E; return F2x_mul(x,y); }
    1523             : 
    1524             : static GEN
    1525         112 : _F2xq_inv(void *E, GEN x)
    1526         112 : { return F2xq_inv(x, (GEN) E); }
    1527             : 
    1528             : static int
    1529         231 : _F2xq_equal0(GEN x) { return lgpol(x)==0; }
    1530             : 
    1531             : static GEN
    1532         168 : _F2xq_s(void *E, long x)
    1533         168 : { GEN T = (GEN) E;
    1534         168 :   return odd(x)? pol1_F2x(T[1]): pol0_F2x(T[0]);
    1535             : }
    1536             : 
    1537             : static const struct bb_field F2xq_field={_F2xq_red,_F2xq_add,_F2xq_rmul,_F2xq_neg,
    1538             :                                          _F2xq_inv,_F2xq_equal0,_F2xq_s};
    1539             : 
    1540          91 : const struct bb_field *get_F2xq_field(void **E, GEN T)
    1541             : {
    1542          91 :   *E = (void *) T;
    1543          91 :   return &F2xq_field;
    1544             : }
    1545             : 
    1546             : /***********************************************************************/
    1547             : /**                                                                   **/
    1548             : /**                             F2v                                   **/
    1549             : /**                                                                   **/
    1550             : /***********************************************************************/
    1551             : /* F2v objects are defined as follows:
    1552             :    An F2v is a t_VECSMALL:
    1553             :    v[0] = codeword
    1554             :    v[1] = number of components
    1555             :    x[2] = a_0...a_31 x[3] = a_32..a_63, etc.  on 32bit
    1556             :    x[2] = a_0...a_63 x[3] = a_64..a_127, etc. on 64bit
    1557             : 
    1558             :    where the a_i are bits.
    1559             : */
    1560             : 
    1561             : GEN
    1562      405330 : F2c_to_ZC(GEN x)
    1563             : {
    1564      405330 :   long l=x[1]+1;
    1565      405330 :   GEN  z = cgetg(l, t_COL);
    1566             :   long i,j,k;
    1567      813274 :   for (i=2,k=1; i<lg(x); i++)
    1568     4991641 :     for (j=0; j<BITS_IN_LONG && k<l; j++,k++)
    1569     4583697 :       gel(z,k) = (x[i]&(1UL<<j))? gen_1: gen_0;
    1570      405330 :   return z;
    1571             : }
    1572             : GEN
    1573        3045 : F2c_to_mod(GEN x)
    1574             : {
    1575        3045 :   long l=x[1]+1;
    1576        3045 :   GEN  z = cgetg(l, t_COL);
    1577        3045 :   GEN _0 = mkintmod(gen_0,gen_2);
    1578        3045 :   GEN _1 = mkintmod(gen_1,gen_2);
    1579             :   long i,j,k;
    1580       15690 :   for (i=2,k=1; i<lg(x); i++)
    1581      573289 :     for (j=0; j<BITS_IN_LONG && k<l; j++,k++)
    1582      560644 :       gel(z,k) = (x[i]&(1UL<<j))? _1: _0;
    1583        3045 :   return z;
    1584             : }
    1585             : 
    1586             : /* x[a..b], a <= b */
    1587             : GEN
    1588          28 : F2v_slice(GEN x, long a, long b)
    1589             : {
    1590          28 :   long i,j,k, l = b-a+1;
    1591          28 :   GEN z = cgetg(nbits2lg(l), t_VECSMALL);
    1592          28 :   z[1] = l;
    1593          98 :   for(i=a,k=1,j=BITS_IN_LONG; i<=b; i++,j++)
    1594             :   {
    1595          70 :     if (j==BITS_IN_LONG) { j=0; z[++k]=0; }
    1596          70 :     if (F2v_coeff(x,i)) z[k] |= 1UL<<j;
    1597             :   }
    1598          28 :   return z;
    1599             : }
    1600             : /* x[a..b,], a <= b */
    1601             : GEN
    1602          14 : F2m_rowslice(GEN x, long a, long b)
    1603             : {
    1604             :   long i, l;
    1605          14 :   GEN y = cgetg_copy(x, &l);
    1606          14 :   for (i = 1; i < l; i++) gel(y,i) = F2v_slice(gel(x,i),a,b);
    1607          14 :   return y;
    1608             : }
    1609             : 
    1610             : GEN
    1611       95169 : F2m_to_ZM(GEN z)
    1612             : {
    1613       95169 :   long i, l = lg(z);
    1614       95169 :   GEN x = cgetg(l,t_MAT);
    1615       95169 :   for (i=1; i<l; i++) gel(x,i) = F2c_to_ZC(gel(z,i));
    1616       95169 :   return x;
    1617             : }
    1618             : GEN
    1619         112 : F2m_to_mod(GEN z)
    1620             : {
    1621         112 :   long i, l = lg(z);
    1622         112 :   GEN x = cgetg(l,t_MAT);
    1623         112 :   for (i=1; i<l; i++) gel(x,i) = F2c_to_mod(gel(z,i));
    1624         112 :   return x;
    1625             : }
    1626             : 
    1627             : GEN
    1628        3850 : F2v_to_Flv(GEN x)
    1629             : {
    1630        3850 :   long l=x[1]+1;
    1631        3850 :   GEN  z=cgetg(l, t_VECSMALL);
    1632             :   long i,j,k;
    1633        8024 :   for (i=2,k=1; i<lg(x); i++)
    1634       79508 :     for (j=0; j<BITS_IN_LONG && k<l; j++,k++)
    1635       75334 :       z[k] = (x[i]>>j)&1UL;
    1636        3850 :   return z;
    1637             : }
    1638             : 
    1639             : GEN
    1640        1400 : F2m_to_Flm(GEN z)
    1641             : {
    1642        1400 :   long i, l = lg(z);
    1643        1400 :   GEN x = cgetg(l,t_MAT);
    1644        1400 :   for (i=1; i<l; i++) gel(x,i) = F2v_to_Flv(gel(z,i));
    1645        1400 :   return x;
    1646             : }
    1647             : 
    1648             : GEN
    1649     1060885 : ZV_to_F2v(GEN x)
    1650             : {
    1651     1060885 :   long l = lg(x)-1;
    1652     1060885 :   GEN z = cgetg(nbits2lg(l), t_VECSMALL);
    1653             :   long i,j,k;
    1654     1060885 :   z[1] = l;
    1655    14789958 :   for(i=1,k=1,j=BITS_IN_LONG; i<=l; i++,j++)
    1656             :   {
    1657    13729073 :     if (j==BITS_IN_LONG) { j=0; z[++k]=0; }
    1658    13729073 :     if (mpodd(gel(x,i))) z[k] |= 1UL<<j;
    1659             :   }
    1660     1060885 :   return z;
    1661             : }
    1662             : 
    1663             : GEN
    1664        7686 : RgV_to_F2v(GEN x)
    1665             : {
    1666        7686 :   long l = lg(x)-1;
    1667        7686 :   GEN z = cgetg(nbits2lg(l), t_VECSMALL);
    1668             :   long i,j,k;
    1669        7686 :   z[1] = l;
    1670     1409758 :   for(i=1,k=1,j=BITS_IN_LONG; i<=l; i++,j++)
    1671             :   {
    1672     1402072 :     if (j==BITS_IN_LONG) { j=0; z[++k]=0; }
    1673     1402072 :     if (Rg_to_F2(gel(x,i))) z[k] |= 1UL<<j;
    1674             :   }
    1675        7686 :   return z;
    1676             : }
    1677             : 
    1678             : GEN
    1679        7406 : Flv_to_F2v(GEN x)
    1680             : {
    1681        7406 :   long l = lg(x)-1;
    1682        7406 :   GEN z = cgetg(nbits2lg(l), t_VECSMALL);
    1683             :   long i,j,k;
    1684        7406 :   z[1] = l;
    1685      192066 :   for(i=1,k=1,j=BITS_IN_LONG; i<=l; i++,j++)
    1686             :   {
    1687      184660 :     if (j==BITS_IN_LONG) { j=0; z[++k]=0; }
    1688      184660 :     if (x[i]&1L) z[k] |= 1UL<<j;
    1689             :   }
    1690        7406 :   return z;
    1691             : }
    1692             : 
    1693             : GEN
    1694      184659 : ZM_to_F2m(GEN x)
    1695             : {
    1696      184659 :   long j, l = lg(x);
    1697      184659 :   GEN y = cgetg(l,t_MAT);
    1698      184659 :   if (l == 1) return y;
    1699      184659 :   for (j=1; j<l; j++) gel(y,j) = ZV_to_F2v(gel(x,j));
    1700      184659 :   return y;
    1701             : }
    1702             : 
    1703             : GEN
    1704         287 : RgM_to_F2m(GEN x)
    1705             : {
    1706         287 :   long j, l = lg(x);
    1707         287 :   GEN y = cgetg(l,t_MAT);
    1708         287 :   if (l == 1) return y;
    1709         287 :   for (j=1; j<l; j++) gel(y,j) = RgV_to_F2v(gel(x,j));
    1710         287 :   return y;
    1711             : }
    1712             : 
    1713             : GEN
    1714        1400 : Flm_to_F2m(GEN x)
    1715             : {
    1716        1400 :   long j, l = lg(x);
    1717        1400 :   GEN y = cgetg(l,t_MAT);
    1718        1400 :   if (l == 1) return y;
    1719        1400 :   for (j=1; j<l; j++) gel(y,j) = Flv_to_F2v(gel(x,j));
    1720        1400 :   return y;
    1721             : }
    1722             : 
    1723             : GEN
    1724      310634 : const_F2v(long m)
    1725             : {
    1726      310634 :   long i, l = nbits2lg(m);
    1727      310634 :   GEN c = cgetg(l, t_VECSMALL);
    1728      310634 :   for (i = 2; i <= l; i++) c[i] = -1;
    1729      310634 :   if (remsBIL(m)) c[l] = (1UL<<remsBIL(m))-1UL;
    1730      310634 :   return c;
    1731             : }
    1732             : 
    1733             : /* Allow lg(y)<lg(x) */
    1734             : void
    1735    30701521 : F2v_add_inplace(GEN x, GEN y)
    1736             : {
    1737    30701521 :   long n = lg(y);
    1738    30701521 :   long r = (n-2)&7L, q = n-r, i;
    1739   122426783 :   for (i = 2; i < q; i += 8)
    1740             :   {
    1741    91725262 :     x[  i] ^= y[  i]; x[1+i] ^= y[1+i]; x[2+i] ^= y[2+i]; x[3+i] ^= y[3+i];
    1742    91725262 :     x[4+i] ^= y[4+i]; x[5+i] ^= y[5+i]; x[6+i] ^= y[6+i]; x[7+i] ^= y[7+i];
    1743             :   }
    1744    30701521 :   switch (r)
    1745             :   {
    1746    13151826 :     case 7: x[i] ^= y[i]; i++; case 6: x[i] ^= y[i]; i++;
    1747    16305540 :     case 5: x[i] ^= y[i]; i++; case 4: x[i] ^= y[i]; i++;
    1748    19446300 :     case 3: x[i] ^= y[i]; i++; case 2: x[i] ^= y[i]; i++;
    1749    24204396 :     case 1: x[i] ^= y[i]; i++;
    1750             :   }
    1751    30701521 : }
    1752             : 
    1753             : /***********************************************************************/
    1754             : /**                                                                   **/
    1755             : /**                               F2xV                                **/
    1756             : /**                                                                   **/
    1757             : /***********************************************************************/
    1758             : /* F2xV are t_VEC with F2x coefficients. */
    1759             : 
    1760             : GEN
    1761       14854 : FlxC_to_F2xC(GEN x)
    1762             : {
    1763       14854 :   long i, l=lg(x);
    1764       14854 :   GEN z = cgetg(l,t_COL);
    1765       14854 :   for (i=1; i<l ; i++) gel(z,i) = Flx_to_F2x(gel(x,i));
    1766       14854 :   return z;
    1767             : }
    1768             : 
    1769             : GEN
    1770           0 : F2xC_to_FlxC(GEN x)
    1771             : {
    1772           0 :   long i, l=lg(x);
    1773           0 :   GEN z = cgetg(l,t_COL);
    1774           0 :   for (i=1; i<l ; i++) gel(z,i) = F2x_to_Flx(gel(x,i));
    1775           0 :   return z;
    1776             : }
    1777             : 
    1778             : GEN
    1779        2051 : F2xC_to_ZXC(GEN v)
    1780             : {
    1781        2051 :   long j, N = lg(v);
    1782        2051 :   GEN y = cgetg(N, t_COL);
    1783        2051 :   for (j=1; j<N; j++) gel(y,j) = F2x_to_ZX(gel(v,j));
    1784        2051 :   return y;
    1785             : }
    1786             : 
    1787             : GEN
    1788      229637 : F2xV_to_F2m(GEN v, long n)
    1789             : {
    1790      229637 :   long j, N = lg(v);
    1791      229637 :   GEN y = cgetg(N, t_MAT);
    1792      229637 :   for (j=1; j<N; j++) gel(y,j) = F2x_to_F2v(gel(v,j), n);
    1793      229637 :   return y;
    1794             : }
    1795             : 
    1796             : /***********************************************************************/
    1797             : /**                                                                   **/
    1798             : /**                             F2xX                                  **/
    1799             : /**                                                                   **/
    1800             : /***********************************************************************/
    1801             : 
    1802             : GEN
    1803     2164610 : F2xX_renormalize(GEN /*in place*/ x, long lx)
    1804     2164610 : { return FlxX_renormalize(x, lx); }
    1805             : 
    1806             : GEN
    1807      444542 : pol1_F2xX(long v, long sv) { return pol1_FlxX(v, sv); }
    1808             : 
    1809             : GEN
    1810           0 : polx_F2xX(long v, long sv) { return polx_FlxX(v, sv); }
    1811             : 
    1812             : long
    1813      205086 : F2xY_degreex(GEN b)
    1814             : {
    1815      205086 :   long deg = 0, i;
    1816      205086 :   if (!signe(b)) return -1;
    1817     1333038 :   for (i = 2; i < lg(b); ++i)
    1818     1127952 :     deg = maxss(deg, F2x_degree(gel(b, i)));
    1819      205086 :   return deg;
    1820             : }
    1821             : 
    1822             : GEN
    1823        1736 : FlxX_to_F2xX(GEN B)
    1824             : {
    1825        1736 :   long lb=lg(B);
    1826             :   long i;
    1827        1736 :   GEN b=cgetg(lb,t_POL);
    1828        1736 :   b[1]=evalsigne(1)|(((ulong)B[1])&VARNBITS);
    1829        5208 :   for (i=2; i<lb; i++)
    1830        3472 :     gel(b,i) = Flx_to_F2x(gel(B,i));
    1831        1736 :   return F2xX_renormalize(b, lb);
    1832             : }
    1833             : 
    1834             : GEN
    1835        2296 : ZXX_to_F2xX(GEN B, long v)
    1836             : {
    1837        2296 :   long lb=lg(B);
    1838             :   long i;
    1839        2296 :   GEN b=cgetg(lb,t_POL);
    1840        2296 :   b[1]=evalsigne(1)|(((ulong)B[1])&VARNBITS);
    1841       11809 :   for (i=2; i<lb; i++)
    1842        9513 :     switch (typ(gel(B,i)))
    1843             :     {
    1844             :     case t_INT:
    1845        2359 :       gel(b,i) = Z_to_F2x(gel(B,i), v);
    1846        2359 :       break;
    1847             :     case t_POL:
    1848        7154 :       gel(b,i) = ZX_to_F2x(gel(B,i));
    1849        7154 :       break;
    1850             :     }
    1851        2296 :   return F2xX_renormalize(b, lb);
    1852             : }
    1853             : 
    1854             : GEN
    1855        1855 : F2xX_to_ZXX(GEN B)
    1856             : {
    1857        1855 :   long i, lb = lg(B);
    1858        1855 :   GEN b = cgetg(lb,t_POL);
    1859        5621 :   for (i=2; i<lb; i++)
    1860             :   {
    1861        3766 :     GEN c = gel(B,i);
    1862        3766 :     gel(b,i) = lgpol(c) ?  F2x_equal1(c) ? gen_1 : F2x_to_ZX(c) : gen_0;
    1863             :   }
    1864        1855 :   b[1] = B[1]; return b;
    1865             : }
    1866             : 
    1867             : GEN
    1868       80325 : F2xX_deriv(GEN z)
    1869             : {
    1870       80325 :   long i,l = lg(z)-1;
    1871             :   GEN x;
    1872       80325 :   if (l < 2) l = 2;
    1873       80325 :   x = cgetg(l, t_POL); x[1] = z[1];
    1874       80325 :   for (i=2; i<l; i++) gel(x,i) = odd(i) ? pol0_F2x(mael(z,i+1,1)): gel(z,i+1);
    1875       80325 :   return F2xX_renormalize(x,l);
    1876             : }
    1877             : 
    1878             : GEN
    1879      420133 : F2xX_add(GEN x, GEN y)
    1880             : {
    1881             :   long i,lz;
    1882             :   GEN z;
    1883      420133 :   long lx=lg(x);
    1884      420133 :   long ly=lg(y);
    1885      420133 :   if (ly>lx) swapspec(x,y, lx,ly);
    1886      420133 :   lz = lx; z = cgetg(lz, t_POL); z[1]=x[1];
    1887      420133 :   for (i=2; i<ly; i++) gel(z,i) = F2x_add(gel(x,i), gel(y,i));
    1888      420133 :   for (   ; i<lx; i++) gel(z,i) = F2x_copy(gel(x,i));
    1889      420133 :   return F2xX_renormalize(z, lz);
    1890             : }
    1891             : 
    1892             : GEN
    1893      478247 : F2xX_F2x_mul(GEN P, GEN U)
    1894             : {
    1895      478247 :   long i, lP = lg(P);
    1896      478247 :   GEN res = cgetg(lP,t_POL);
    1897      478247 :   res[1] = P[1];
    1898     2307207 :   for(i=2; i<lP; i++)
    1899     1828960 :     gel(res,i) = F2x_mul(U,gel(P,i));
    1900      478247 :   return F2xX_renormalize(res, lP);
    1901             : }
    1902             : 
    1903             : GEN
    1904      135492 : F2xY_F2xqV_evalx(GEN P, GEN x, GEN T)
    1905             : {
    1906      135492 :   long i, lP = lg(P);
    1907      135492 :   GEN res = cgetg(lP,t_POL);
    1908      135492 :   res[1] = P[1];
    1909      613459 :   for(i=2; i<lP; i++)
    1910      477967 :     gel(res,i) = F2x_F2xqV_eval(gel(P,i), x, T);
    1911      135492 :   return F2xX_renormalize(res, lP);
    1912             : }
    1913             : 
    1914             : GEN
    1915           0 : F2xY_F2xq_evalx(GEN P, GEN x, GEN T)
    1916             : {
    1917           0 :   pari_sp av = avma;
    1918           0 :   long n = brent_kung_optpow(F2x_degree(T)-1,lgpol(P),1);
    1919           0 :   GEN xp = F2xq_powers(x, n, T);
    1920           0 :   return gerepileupto(av, F2xY_F2xqV_evalx(P, xp, T));
    1921             : }
    1922             : 
    1923             : GEN
    1924      228494 : F2xX_to_Kronecker(GEN P, long d)
    1925             : {
    1926      228494 :   long i, k, N = 2*d + 1;
    1927      228494 :   long dP = degpol(P);
    1928      228494 :   long l = nbits2nlong(N*dP+d+1);
    1929      228494 :   GEN x = zero_zv(l+1);
    1930     1356201 :   for (k=i=0; i<=dP; i++, k+=N)
    1931             :   {
    1932     1127707 :     GEN c = gel(P,i+2);
    1933     1127707 :     F2x_addshiftip(x, c, k);
    1934             :   }
    1935      228494 :   x[1] = P[1]&VARNBITS; return F2x_renormalize(x, l+2);
    1936             : }
    1937             : 
    1938             : static GEN
    1939     1013460 : F2x_slice(GEN x, long n, long d)
    1940             : {
    1941     1013460 :   ulong ib, il=dvmduBIL(n, &ib);
    1942     1013460 :   ulong db, dl=dvmduBIL(d, &db);
    1943     1013460 :   long lN = dl+2+(db?1:0);
    1944     1013460 :   GEN t = cgetg(lN,t_VECSMALL);
    1945     1013460 :   t[1] = x[1];
    1946     1013460 :   if (ib)
    1947             :   {
    1948      895696 :     ulong i, ic = BITS_IN_LONG-ib;
    1949      895696 :     ulong r = uel(x,2+il)>>ib;
    1950      895759 :     for(i=0; i<dl; i++)
    1951             :     {
    1952          63 :       uel(t,2+i) = (uel(x,3+il+i)<<ic)|r;
    1953          63 :       r = uel(x,3+il+i)>>ib;
    1954             :     }
    1955      895696 :     if (db)
    1956      895696 :       uel(t,2+i) = (uel(x,3+il+i)<<ic)|r;
    1957             :   }
    1958             :   else
    1959             :   {
    1960             :     long i;
    1961      235536 :     for(i=2; i<lN; i++)
    1962      117772 :       uel(t,i) = uel(x,il+i);
    1963             :   }
    1964     1013460 :   if (db) uel(t,lN-1) &= (1UL<<db)-1;
    1965     1013460 :   return F2x_renormalize(t, lN);
    1966             : }
    1967             : 
    1968             : GEN
    1969      114247 : Kronecker_to_F2xqX(GEN z, GEN T)
    1970             : {
    1971      114247 :   long lz = F2x_degree(z)+1;
    1972      114247 :   long i, j, N = F2x_degree(T)*2 + 1;
    1973      114247 :   long lx = lz / (N-2);
    1974      114247 :   GEN x = cgetg(lx+3,t_POL);
    1975      114247 :   x[1] = z[1];
    1976     1127707 :   for (i=0, j=2; i<lz; i+=N, j++)
    1977             :   {
    1978     1013460 :     GEN t = F2x_slice(z,i,minss(lz-i,N));
    1979     1013460 :     t[1] = T[1];
    1980     1013460 :     gel(x,j) = F2x_rem(t, T);
    1981             :   }
    1982      114247 :   return F2xX_renormalize(x, j);
    1983             : }
    1984             : 
    1985             : /***********************************************************************/
    1986             : /**                                                                   **/
    1987             : /**                             F2xXV/F2xXC                           **/
    1988             : /**                                                                   **/
    1989             : /***********************************************************************/
    1990             : 
    1991             : GEN
    1992         161 : FlxXC_to_F2xXC(GEN B)
    1993             : {
    1994         161 :   long i, l = lg(B);
    1995         161 :   GEN z = cgetg(l, t_COL);
    1996        1897 :   for (i=1; i<l; i++)
    1997        1736 :     gel(z,i) = FlxX_to_F2xX(gel(B,i));
    1998         161 :   return z;
    1999             : }
    2000             : 
    2001             : GEN
    2002         245 : F2xXC_to_ZXXC(GEN B)
    2003             : {
    2004         245 :   long i, l = lg(B);
    2005         245 :   GEN z = cgetg(l, t_COL);
    2006        2100 :   for (i=1; i<l; i++)
    2007        1855 :     gel(z,i) = F2xX_to_ZXX(gel(B,i));
    2008         245 :   return z;
    2009             : }
    2010             : 
    2011             : /***********************************************************************/
    2012             : /**                                                                   **/
    2013             : /**                             F2xqX                                 **/
    2014             : /**                                                                   **/
    2015             : /***********************************************************************/
    2016             : 
    2017             : GEN
    2018        2583 : random_F2xqX(long d1, long v, GEN T)
    2019             : {
    2020        2583 :   long dT = F2x_degree(T), vT = T[1];
    2021        2583 :   long i, d = d1+2;
    2022        2583 :   GEN y = cgetg(d,t_POL); y[1] = evalsigne(1) | evalvarn(v);
    2023        2583 :   for (i=2; i<d; i++) gel(y,i) = random_F2x(dT, vT);
    2024        2583 :   return FlxX_renormalize(y,d);
    2025             : }
    2026             : 
    2027             : GEN
    2028      660702 : F2xqX_red(GEN z, GEN T)
    2029             : {
    2030             :   GEN res;
    2031      660702 :   long i, l = lg(z);
    2032      660702 :   res = cgetg(l,t_POL); res[1] = z[1];
    2033      660702 :   for(i=2;i<l;i++) gel(res,i) = F2x_rem(gel(z,i),T);
    2034      660702 :   return F2xX_renormalize(res,l);
    2035             : }
    2036             : 
    2037             : GEN
    2038        6895 : F2xqX_F2xq_mul(GEN P, GEN U, GEN T)
    2039             : {
    2040        6895 :   long i, lP = lg(P);
    2041        6895 :   GEN res = cgetg(lP,t_POL);
    2042        6895 :   res[1] = P[1];
    2043       38822 :   for(i=2; i<lP; i++)
    2044       31927 :     gel(res,i) = F2xq_mul(U,gel(P,i), T);
    2045        6895 :   return F2xX_renormalize(res, lP);
    2046             : }
    2047             : 
    2048             : GEN
    2049      203098 : F2xqX_F2xq_mul_to_monic(GEN P, GEN U, GEN T)
    2050             : {
    2051      203098 :   long i, lP = lg(P);
    2052      203098 :   GEN res = cgetg(lP,t_POL);
    2053      203098 :   res[1] = P[1];
    2054      203098 :   for(i=2; i<lP-1; i++) gel(res,i) = F2xq_mul(U,gel(P,i), T);
    2055      203098 :   gel(res,lP-1) = pol1_F2x(T[1]);
    2056      203098 :   return F2xX_renormalize(res, lP);
    2057             : }
    2058             : 
    2059             : GEN
    2060      203098 : F2xqX_normalize(GEN z, GEN T)
    2061             : {
    2062      203098 :   GEN p1 = leading_coeff(z);
    2063      203098 :   if (!lgpol(z) || (!degpol(p1) && p1[1] == 1)) return z;
    2064      203098 :   return F2xqX_F2xq_mul_to_monic(z, F2xq_inv(p1,T), T);
    2065             : }
    2066             : 
    2067             : GEN
    2068      114247 : F2xqX_mul(GEN x, GEN y, GEN T)
    2069             : {
    2070      114247 :   pari_sp ltop=avma;
    2071             :   GEN z,kx,ky;
    2072      114247 :   kx= F2xX_to_Kronecker(x, F2x_degree(T));
    2073      114247 :   ky= F2xX_to_Kronecker(y, F2x_degree(T));
    2074      114247 :   z = F2x_mul(ky, kx);
    2075      114247 :   z = Kronecker_to_F2xqX(z,T);
    2076      114247 :   return gerepileupto(ltop,z);
    2077             : }
    2078             : 
    2079             : GEN
    2080      103292 : F2xqX_sqr(GEN x, GEN T)
    2081             : {
    2082      103292 :   long d = degpol(x), l = 2*d+3;
    2083             :   GEN z;
    2084      103292 :   if (!signe(x)) return pol_0(varn(x));
    2085      103292 :   z = cgetg(l,t_POL);
    2086      103292 :   z[1] = x[1];
    2087      103292 :   if (d > 0)
    2088             :   {
    2089      103292 :     GEN u = pol0_F2x(T[1]);
    2090             :     long i,j;
    2091      257845 :     for (i=2,j=2; i<d+2; i++,j+=2)
    2092             :     {
    2093      154553 :       gel(z, j) = F2xq_sqr(gel(x, i), T);
    2094      154553 :       gel(z, j+1) = u;
    2095             :     }
    2096             :   }
    2097      103292 :   gel(z, 2+2*d) = F2xq_sqr(gel(x, 2+d), T);
    2098      103292 :   return FlxX_renormalize(z, l);
    2099             : }
    2100             : 
    2101             : GEN
    2102      538300 : F2xqX_divrem(GEN x, GEN y, GEN T, GEN *pr)
    2103             : {
    2104             :   long vx, dx, dy, dz, i, j, sx, lr;
    2105             :   pari_sp av0, av, tetpil;
    2106             :   GEN z,p1,rem,lead;
    2107             : 
    2108      538300 :   if (!signe(y)) pari_err_INV("F2xqX_divrem",y);
    2109      538300 :   vx=varn(x); dy=degpol(y); dx=degpol(x);
    2110      538300 :   if (dx < dy)
    2111             :   {
    2112           0 :     if (pr)
    2113             :     {
    2114           0 :       av0 = avma; x = F2xqX_red(x, T);
    2115           0 :       if (pr == ONLY_DIVIDES) { avma=av0; return signe(x)? NULL: pol_0(vx); }
    2116           0 :       if (pr == ONLY_REM) return x;
    2117           0 :       *pr = x;
    2118             :     }
    2119           0 :     return pol_0(vx);
    2120             :   }
    2121      538300 :   lead = leading_term(y);
    2122      538300 :   if (!dy) /* y is constant */
    2123             :   {
    2124      114086 :     if (pr && pr != ONLY_DIVIDES)
    2125             :     {
    2126      104286 :       if (pr == ONLY_REM) return pol_0(vx);
    2127           0 :       *pr = pol_0(vx);
    2128             :     }
    2129        9800 :     if (F2x_equal1(lead)) return gcopy(x);
    2130        6895 :     av0 = avma; x = F2xqX_F2xq_mul(x,F2xq_inv(lead,T),T);
    2131        6895 :     return gerepileupto(av0,x);
    2132             :   }
    2133      424214 :   av0 = avma; dz = dx-dy;
    2134      424214 :   lead = F2x_equal1(lead)? NULL: gclone(F2xq_inv(lead,T));
    2135      424214 :   avma = av0;
    2136      424214 :   z = cgetg(dz+3,t_POL); z[1] = x[1];
    2137      424214 :   x += 2; y += 2; z += 2;
    2138             : 
    2139      424214 :   p1 = gel(x,dx); av = avma;
    2140      424214 :   gel(z,dz) = lead? gerepileupto(av, F2xq_mul(p1,lead, T)): leafcopy(p1);
    2141     1241205 :   for (i=dx-1; i>=dy; i--)
    2142             :   {
    2143      816991 :     av=avma; p1=gel(x,i);
    2144     5469786 :     for (j=i-dy+1; j<=i && j<=dz; j++)
    2145     4652795 :       p1 = F2x_add(p1, F2x_mul(gel(z,j),gel(y,i-j)));
    2146      816991 :     if (lead) p1 = F2x_mul(p1, lead);
    2147      816991 :     tetpil=avma; gel(z,i-dy) = gerepile(av,tetpil,F2x_rem(p1,T));
    2148             :   }
    2149      424214 :   if (!pr) { if (lead) gunclone(lead); return z-2; }
    2150             : 
    2151      404229 :   rem = (GEN)avma; av = (pari_sp)new_chunk(dx+3);
    2152      626913 :   for (sx=0; ; i--)
    2153             :   {
    2154      626913 :     p1 = gel(x,i);
    2155     2296455 :     for (j=0; j<=i && j<=dz; j++)
    2156     1669542 :       p1 = F2x_add(p1, F2x_mul(gel(z,j),gel(y,i-j)));
    2157      626913 :     tetpil=avma; p1 = F2x_rem(p1, T); if (lgpol(p1)) { sx = 1; break; }
    2158      284123 :     if (!i) break;
    2159      222684 :     avma=av;
    2160      222684 :   }
    2161      404229 :   if (pr == ONLY_DIVIDES)
    2162             :   {
    2163           0 :     if (lead) gunclone(lead);
    2164           0 :     if (sx) { avma=av0; return NULL; }
    2165           0 :     avma = (pari_sp)rem; return z-2;
    2166             :   }
    2167      404229 :   lr=i+3; rem -= lr;
    2168      404229 :   rem[0] = evaltyp(t_POL) | evallg(lr);
    2169      404229 :   rem[1] = z[-1];
    2170      404229 :   p1 = gerepile((pari_sp)rem,tetpil,p1);
    2171      404229 :   rem += 2; gel(rem,i) = p1;
    2172     1515388 :   for (i--; i>=0; i--)
    2173             :   {
    2174     1111159 :     av=avma; p1 = gel(x,i);
    2175     8690451 :     for (j=0; j<=i && j<=dz; j++)
    2176     7579292 :       p1 = F2x_add(p1, F2x_mul(gel(z,j),gel(y,i-j)));
    2177     1111159 :     tetpil=avma; gel(rem,i) = gerepile(av,tetpil, F2x_rem(p1, T));
    2178             :   }
    2179      404229 :   rem -= 2;
    2180      404229 :   if (lead) gunclone(lead);
    2181      404229 :   if (!sx) (void)F2xX_renormalize(rem, lr);
    2182      404229 :   if (pr == ONLY_REM) return gerepileupto(av0,rem);
    2183           0 :   *pr = rem; return z-2;
    2184             : }
    2185             : 
    2186             : GEN
    2187      744548 : F2xqX_rem(GEN x, GEN S, GEN T)
    2188             : {
    2189      744548 :   GEN y = S;
    2190      744548 :   long dy = degpol(y), dx = degpol(x), d = dx-dy;
    2191      744548 :   if (d < 0) return F2xqX_red(x, T);
    2192      508515 :   return F2xqX_divrem(x,y, T, ONLY_REM);
    2193             : }
    2194             : 
    2195             : GEN
    2196      166859 : F2xqX_gcd(GEN a, GEN b, GEN T)
    2197             : {
    2198      166859 :   pari_sp av = avma, av0=avma;
    2199      858585 :   while (signe(b))
    2200             :   {
    2201             :     GEN c;
    2202      524867 :     if (gc_needed(av0,2))
    2203             :     {
    2204           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2xqX_gcd (d = %ld)",degpol(b));
    2205           0 :       gerepileall(av0,2, &a,&b);
    2206             :     }
    2207      524867 :     av = avma; c = F2xqX_rem(a, b, T); a=b; b=c;
    2208             :   }
    2209      166859 :   avma = av; return a;
    2210             : }
    2211             : 
    2212             : /***********************************************************************/
    2213             : /**                                                                   **/
    2214             : /**                             F2xqXQ                                **/
    2215             : /**                                                                   **/
    2216             : /***********************************************************************/
    2217             : 
    2218             : GEN
    2219      114247 : F2xqXQ_mul(GEN x, GEN y, GEN S, GEN T) {
    2220      114247 :   return F2xqX_rem(F2xqX_mul(x,y,T),S,T);
    2221             : }
    2222             : 
    2223             : GEN
    2224      103131 : F2xqXQ_sqr(GEN x, GEN S, GEN T) {
    2225      103131 :   return F2xqX_rem(F2xqX_sqr(x,T),S,T);
    2226             : }
    2227             : 
    2228             : struct _F2xqXQ {
    2229             :   GEN T, S;
    2230             : };
    2231             : 
    2232             : static GEN
    2233      342713 : _F2xqXQ_add(void *data, GEN x, GEN y) {
    2234             :   (void) data;
    2235      342713 :   return F2xX_add(x,y);
    2236             : }
    2237             : static GEN
    2238      478247 : _F2xqXQ_cmul(void *data, GEN P, long a, GEN x) {
    2239             :   (void) data;
    2240      478247 :   return F2xX_F2x_mul(x,gel(P,a+2));
    2241             : }
    2242             : static GEN
    2243      351148 : _F2xqXQ_red(void *data, GEN x) {
    2244      351148 :   struct _F2xqXQ *d = (struct _F2xqXQ*) data;
    2245      351148 :   return F2xqX_red(x, d->T);
    2246             : }
    2247             : static GEN
    2248      114247 : _F2xqXQ_mul(void *data, GEN x, GEN y) {
    2249      114247 :   struct _F2xqXQ *d = (struct _F2xqXQ*) data;
    2250      114247 :   return F2xqXQ_mul(x,y, d->S,d->T);
    2251             : }
    2252             : static GEN
    2253       32606 : _F2xqXQ_sqr(void *data, GEN x) {
    2254       32606 :   struct _F2xqXQ *d = (struct _F2xqXQ*) data;
    2255       32606 :   return F2xqXQ_sqr(x, d->S,d->T);
    2256             : }
    2257             : static GEN
    2258          35 : _F2xqXQ_zero(void *data) {
    2259          35 :   struct _F2xqXQ *d = (struct _F2xqXQ*) data;
    2260          35 :   return pol_0(varn(d->S));
    2261             : }
    2262             : static GEN
    2263      373303 : _F2xqXQ_one(void *data) {
    2264      373303 :   struct _F2xqXQ *d = (struct _F2xqXQ*) data;
    2265      373303 :   return pol1_F2xX(varn(d->S),d->T[1]);
    2266             : }
    2267             : 
    2268             : static struct bb_algebra F2xqXQ_algebra = { _F2xqXQ_red,
    2269             :  _F2xqXQ_add, _F2xqXQ_add, _F2xqXQ_mul,_F2xqXQ_sqr,_F2xqXQ_one,_F2xqXQ_zero };
    2270             : 
    2271             : GEN
    2272           7 : F2xqXQ_pow(GEN x, GEN n, GEN S, GEN T)
    2273             : {
    2274             :   struct _F2xqXQ D;
    2275           7 :   long s = signe(n);
    2276           7 :   if (!s) return pol1_F2xX(varn(S), T[1]);
    2277           7 :   if (s < 0) pari_err_IMPL("F2xqXQ_inv");
    2278           7 :   if (is_pm1(n)) return s < 0 ? x : gcopy(x);
    2279           7 :   if (degpol(x)>=degpol(S)) x = F2xqX_rem(x,S,T);
    2280           7 :   D.S = S; D.T = T;
    2281           7 :   return gen_pow(x, n, (void*)&D, &_F2xqXQ_sqr, &_F2xqXQ_mul);
    2282             : }
    2283             : 
    2284             : GEN
    2285        6713 : F2xqXQ_powers(GEN x, long l, GEN S, GEN T)
    2286             : {
    2287             :   struct _F2xqXQ D;
    2288        6713 :   int use_sqr = 2*degpol(x) >= degpol(S);
    2289        6713 :   D.S = S; D.T = T;
    2290        6713 :   return gen_powers(x, l, use_sqr, (void*)&D, &_F2xqXQ_sqr, &_F2xqXQ_mul,&_F2xqXQ_one);
    2291             : }
    2292             : 
    2293             : GEN
    2294       13447 : F2xqX_F2xqXQV_eval(GEN P, GEN V, GEN S, GEN T)
    2295             : {
    2296             :   struct _F2xqXQ D;
    2297       13447 :   D.S = S; D.T = T;
    2298       13447 :   return gen_bkeval_powers(P, degpol(P), V, (void*)&D, &F2xqXQ_algebra,
    2299             :                                                    _F2xqXQ_cmul);
    2300             : }
    2301             : 
    2302             : GEN
    2303      122122 : F2xqX_F2xqXQ_eval(GEN Q, GEN x, GEN S, GEN T)
    2304             : {
    2305             :   struct _F2xqXQ D;
    2306      122122 :   int use_sqr = 2*degpol(x) >= degpol(S);
    2307      122122 :   D.S = S; D.T = T;
    2308      122122 :   return gen_bkeval(Q, degpol(Q), x, use_sqr, (void*)&D, &F2xqXQ_algebra,
    2309             :                                                     _F2xqXQ_cmul);
    2310             : }
    2311             : 
    2312             : static GEN
    2313       88816 : F2xqXQ_autpow_sqr(void * E, GEN x)
    2314             : {
    2315       88816 :   struct _F2xqXQ *D = (struct _F2xqXQ *)E;
    2316       88816 :   GEN T = D->T;
    2317       88816 :   GEN phi = gel(x,1), S = gel(x,2);
    2318       88816 :   long n = brent_kung_optpow(F2x_degree(T)-1,lgpol(S)+1,1);
    2319       88816 :   GEN V = F2xq_powers(phi, n, T);
    2320       88816 :   GEN phi2 = F2x_F2xqV_eval(phi, V, T);
    2321       88816 :   GEN Sphi = F2xY_F2xqV_evalx(S, V, T);
    2322       88816 :   GEN S2 = F2xqX_F2xqXQ_eval(Sphi, S, D->S, T);
    2323       88816 :   return mkvec2(phi2, S2);
    2324             : }
    2325             : 
    2326             : static GEN
    2327       33306 : F2xqXQ_autpow_mul(void * E, GEN x, GEN y)
    2328             : {
    2329       33306 :   struct _F2xqXQ *D = (struct _F2xqXQ *)E;
    2330       33306 :   GEN T = D->T;
    2331       33306 :   GEN phi1 = gel(x,1), S1 = gel(x,2);
    2332       33306 :   GEN phi2 = gel(y,1), S2 = gel(y,2);
    2333       33306 :   long n = brent_kung_optpow(F2x_degree(T)-1,lgpol(S1)+1,1);
    2334       33306 :   GEN V = F2xq_powers(phi2, n, T);
    2335       33306 :   GEN phi3 = F2x_F2xqV_eval(phi1,V,T);
    2336       33306 :   GEN Sphi = F2xY_F2xqV_evalx(S1,V,T);
    2337       33306 :   GEN S3 = F2xqX_F2xqXQ_eval(Sphi, S2, D->S, T);
    2338       33306 :   return mkvec2(phi3, S3);
    2339             : }
    2340             : 
    2341             : GEN
    2342       70518 : F2xqXQV_autpow(GEN aut, long n, GEN S, GEN T)
    2343             : {
    2344             :   struct _F2xqXQ D;
    2345       70518 :   D.S = S; D.T = T;
    2346       70518 :   return gen_powu(aut,n,&D,F2xqXQ_autpow_sqr,F2xqXQ_autpow_mul);
    2347             : }
    2348             : 
    2349             : static GEN
    2350        6685 : F2xqXQ_auttrace_mul(void *E, GEN x, GEN y)
    2351             : {
    2352        6685 :   struct _F2xqXQ *D = (struct _F2xqXQ *) E;
    2353        6685 :   GEN T = D->T;
    2354        6685 :   GEN phi1 = gel(x,1), S1 = gel(x,2), a1 = gel(x,3);
    2355        6685 :   GEN phi2 = gel(y,1), S2 = gel(y,2), a2 = gel(y,3);
    2356        6685 :   long n2 = brent_kung_optpow(F2x_degree(T)-1, lgpol(S1)+lgpol(a1)+1, 1);
    2357        6685 :   GEN V2 = F2xq_powers(phi2, n2, T);
    2358        6685 :   GEN phi3 = F2x_F2xqV_eval(phi1, V2, T);
    2359        6685 :   GEN Sphi = F2xY_F2xqV_evalx(S1, V2, T);
    2360        6685 :   GEN aphi = F2xY_F2xqV_evalx(a1, V2, T);
    2361        6685 :   long n = brent_kung_optpow(maxss(degpol(Sphi),degpol(aphi)),2,1);
    2362        6685 :   GEN V = F2xqXQ_powers(S2, n, D->S, T);
    2363        6685 :   GEN S3 = F2xqX_F2xqXQV_eval(Sphi, V, D->S, T);
    2364        6685 :   GEN aS = F2xqX_F2xqXQV_eval(aphi, V, D->S, T);
    2365        6685 :   GEN a3 = F2xX_add(aS, a2);
    2366        6685 :   return mkvec3(phi3, S3, a3);
    2367             : }
    2368             : 
    2369             : static GEN
    2370        4529 : F2xqXQ_auttrace_sqr(void *E, GEN x)
    2371        4529 : { return F2xqXQ_auttrace_mul(E, x, x); }
    2372             : 
    2373             : GEN
    2374        2541 : F2xqXQV_auttrace(GEN aut, long n, GEN S, GEN T)
    2375             : {
    2376             :   struct _F2xqXQ D;
    2377        2541 :   D.S = S; D.T = T;
    2378        2541 :   return gen_powu(aut,n,&D,F2xqXQ_auttrace_sqr,F2xqXQ_auttrace_mul);
    2379             : }

Generated by: LCOV version 1.11