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.8.0 lcov report (development 18898-50fc0a2) Lines: 1146 1292 88.7 %
Date: 2016-05-04 Functions: 150 158 94.9 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 573 775 73.9 %

           Branch data     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                 :  142902129 : F2x_degree_lg(GEN x, long l)
      39                 :            : {
      40 [ +  + ][ +  + ]:  142902129 :   return (l==2)?-1:bit_accuracy(l)-bfffo(x[l-1])-1;
         [ +  + ][ +  + ]
                 [ +  + ]
      41                 :            : }
      42                 :            : 
      43                 :            : long
      44                 :   37892538 : F2x_degree(GEN x)
      45                 :            : {
      46                 :   37892538 :   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                 :     105951 : F2x_to_ZX(GEN x)
      61                 :            : {
      62                 :     105951 :   long l=3+F2x_degree(x);
      63                 :     105954 :   GEN z=cgetg(l,t_POL);
      64                 :            :   long i,j,k;
      65         [ +  + ]:     210877 :   for(i=2,k=2;i<lg(x);i++)
      66 [ +  + ][ +  + ]:     503287 :     for(j=0; j<BITS_IN_LONG && k<l; j++,k++)
      67         [ +  + ]:     398364 :       gel(z,k)=(x[i]&(1UL<<j))?gen_1:gen_0;
      68         [ +  + ]:     105954 :   z[1]=evalsigne(l>=3)|x[1];
      69                 :     105954 :   return z;
      70                 :            : }
      71                 :            : 
      72                 :            : GEN
      73                 :      86992 : F2x_to_Flx(GEN x)
      74                 :            : {
      75                 :      86992 :   long l=3+F2x_degree(x);
      76                 :      87004 :   GEN z=cgetg(l,t_VECSMALL);
      77                 :            :   long i,j,k;
      78                 :      87004 :   z[1]=x[1];
      79         [ +  + ]:     191005 :   for(i=2,k=2;i<lg(x);i++)
      80 [ +  + ][ +  + ]:    2372689 :     for(j=0;j<BITS_IN_LONG && k<l; j++,k++)
      81                 :    2268688 :       z[k]=(x[i]>>j)&1UL;
      82                 :      87004 :   return z;
      83                 :            : }
      84                 :            : 
      85                 :            : GEN
      86                 :     157304 : Z_to_F2x(GEN x, long v)
      87                 :            : {
      88                 :     157304 :   long sv = evalvarn(v);
      89         [ +  + ]:     157304 :   return mpodd(x) ? pol1_F2x(sv): pol0_F2x(sv);
      90                 :            : }
      91                 :            : 
      92                 :            : GEN
      93                 :     173638 : ZX_to_F2x(GEN x)
      94                 :            : {
      95                 :     173638 :   long l=nbits2lg(lgpol(x));
      96                 :     173638 :   GEN z=cgetg(l,t_VECSMALL);
      97                 :            :   long i,j,k;
      98                 :     173666 :   z[1]=((ulong)x[1])&VARNBITS;
      99         [ +  + ]:     752963 :   for(i=2, k=1,j=BITS_IN_LONG;i<lg(x);i++,j++)
     100                 :            :   {
     101         [ +  + ]:     579325 :     if (j==BITS_IN_LONG)
     102                 :            :     {
     103                 :     171471 :       j=0; k++; z[k]=0;
     104                 :            :     }
     105         [ +  + ]:     579325 :     if (mpodd(gel(x,i)))
     106                 :     452826 :       z[k]|=1UL<<j;
     107                 :            :   }
     108                 :     173638 :   return F2x_renormalize(z,l);
     109                 :            : }
     110                 :            : 
     111                 :            : GEN
     112                 :     146345 : Flx_to_F2x(GEN x)
     113                 :            : {
     114                 :     146345 :   long l=nbits2lg(lgpol(x));
     115                 :     146347 :   GEN z=cgetg(l,t_VECSMALL);
     116                 :            :   long i,j,k;
     117                 :     146353 :   z[1]=x[1];
     118         [ +  + ]:    2727474 :   for(i=2, k=1,j=BITS_IN_LONG;i<lg(x);i++,j++)
     119                 :            :   {
     120         [ +  + ]:    2581121 :     if (j==BITS_IN_LONG)
     121                 :            :     {
     122                 :     157542 :       j=0; k++; z[k]=0;
     123                 :            :     }
     124         [ +  + ]:    2581121 :     if (x[i]&1UL)
     125                 :    1294953 :       z[k]|=1UL<<j;
     126                 :            :   }
     127                 :     146353 :   return F2x_renormalize(z,l);
     128                 :            : }
     129                 :            : 
     130                 :            : GEN
     131                 :     359331 : F2x_to_F2v(GEN x, long N)
     132                 :            : {
     133                 :     359331 :   long i, l = lg(x);
     134                 :     359331 :   long n = nbits2lg(N);
     135                 :     359331 :   GEN z = cgetg(n,t_VECSMALL);
     136                 :     359331 :   z[1] = N;
     137         [ +  + ]:     768254 :   for (i=2; i<l ; i++) z[i]=x[i];
     138         [ +  + ]:     380759 :   for (   ; i<n; i++) z[i]=0;
     139                 :     359331 :   return z;
     140                 :            : }
     141                 :            : 
     142                 :            : GEN
     143                 :        140 : RgX_to_F2x(GEN x)
     144                 :            : {
     145                 :        140 :   long l=nbits2lg(lgpol(x));
     146                 :        140 :   GEN z=cgetg(l,t_VECSMALL);
     147                 :            :   long i,j,k;
     148                 :        140 :   z[1]=((ulong)x[1])&VARNBITS;
     149         [ +  + ]:        777 :   for(i=2, k=1,j=BITS_IN_LONG;i<lg(x);i++,j++)
     150                 :            :   {
     151         [ +  + ]:        637 :     if (j==BITS_IN_LONG)
     152                 :            :     {
     153                 :        140 :       j=0; k++; z[k]=0;
     154                 :            :     }
     155         [ +  + ]:        637 :     if (Rg_to_F2(gel(x,i)))
     156                 :        336 :       z[k]|=1UL<<j;
     157                 :            :   }
     158                 :        140 :   return F2x_renormalize(z,l);
     159                 :            : }
     160                 :            : 
     161                 :            : /* If x is a POLMOD, assume modulus is a multiple of T. */
     162                 :            : GEN
     163                 :     165785 : Rg_to_F2xq(GEN x, GEN T)
     164                 :            : {
     165                 :     165785 :   long ta, tx = typ(x), v = T[1];
     166                 :            :   GEN a, b;
     167         [ +  - ]:     165785 :   if (is_const_t(tx))
     168                 :            :   {
     169         [ +  + ]:     165785 :     if (tx == t_FFELT) return FF_to_F2xq(x);
     170         [ +  + ]:      52365 :     return Rg_to_F2(x)? pol1_F2x(v): pol0_F2x(v);
     171                 :            :   }
     172   [ #  #  #  # ]:          0 :   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                 :          0 :       x = RgX_to_F2x(x);
     184         [ #  # ]:          0 :       if (x[1] != v) break;
     185                 :          0 :       return F2x_rem(x, T);
     186                 :            :     case t_RFRAC:
     187                 :          0 :       a = Rg_to_F2xq(gel(x,1), T);
     188                 :          0 :       b = Rg_to_F2xq(gel(x,2), T);
     189                 :          0 :       return F2xq_div(a,b, T);
     190                 :            :   }
     191                 :          0 :   pari_err_TYPE("Rg_to_F2xq",x);
     192                 :     165780 :   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                 :        224 :   else return F2x_coeff(P,0);
     215                 :            : }
     216                 :            : 
     217                 :            : GEN
     218                 :   16816100 : F2x_add(GEN x, GEN y)
     219                 :            : {
     220                 :            :   long i,lz;
     221                 :            :   GEN z;
     222                 :   16816100 :   long lx=lg(x);
     223                 :   16816100 :   long ly=lg(y);
     224         [ +  + ]:   16816100 :   if (ly>lx) swapspec(x,y, lx,ly);
     225                 :   16816100 :   lz = lx; z = cgetg(lz, t_VECSMALL); z[1]=x[1];
     226         [ +  + ]:   40976498 :   for (i=2; i<ly; i++) z[i] = x[i]^y[i];
     227         [ +  + ]:   20644481 :   for (   ; i<lx; i++) z[i] = x[i];
     228                 :   16823234 :   return F2x_renormalize(z, lz);
     229                 :            : }
     230                 :            : 
     231                 :            : static GEN
     232                 :          0 : F2x_addspec(GEN x, GEN y, long lx, long ly)
     233                 :            : {
     234                 :            :   long i,lz;
     235                 :            :   GEN z;
     236                 :            : 
     237         [ #  # ]:          0 :   if (ly>lx) swapspec(x,y, lx,ly);
     238                 :          0 :   lz = lx+2; z = cgetg(lz, t_VECSMALL) + 2;
     239         [ #  # ]:          0 :   for (i=0; i<ly-3; i+=4)
     240                 :            :   {
     241                 :          0 :     z[i] = x[i]^y[i];
     242                 :          0 :     z[i+1] = x[i+1]^y[i+1];
     243                 :          0 :     z[i+2] = x[i+2]^y[i+2];
     244                 :          0 :     z[i+3] = x[i+3]^y[i+3];
     245                 :            :   }
     246         [ #  # ]:          0 :   for (; i<ly; i++)
     247                 :          0 :     z[i] = x[i]^y[i];
     248         [ #  # ]:          0 :   for (   ; i<lx; i++) z[i] = x[i];
     249                 :          0 :   z -= 2; return F2x_renormalize(z, lz);
     250                 :            : }
     251                 :            : 
     252                 :            : GEN
     253                 :     172981 : F2x_1_add(GEN y)
     254                 :            : {
     255                 :            :   GEN z;
     256                 :            :   long lz, i;
     257         [ +  + ]:     172981 :   if (!lgpol(y))
     258                 :      61245 :     return pol1_F2x(y[1]);
     259                 :     111737 :   lz=lg(y);
     260                 :     111737 :   z=cgetg(lz,t_VECSMALL);
     261                 :     111737 :   z[1] = y[1];
     262                 :     111737 :   z[2] = y[2]^1UL;
     263         [ -  + ]:     111737 :   for(i=3;i<lz;i++)
     264                 :          0 :     z[i] = y[i];
     265         [ +  - ]:     111737 :   if (lz==3) z = F2x_renormalize(z,lz);
     266                 :     172982 :   return z;
     267                 :            : }
     268                 :            : 
     269                 :            : INLINE void
     270                 :  151607425 : F2x_addshiftipspec(GEN x, GEN y, long ny, ulong db)
     271                 :            : {
     272                 :            :   long i;
     273         [ +  + ]:  151607425 :   if (db)
     274                 :            :   {
     275                 :  131706827 :     ulong dc=BITS_IN_LONG-db;
     276                 :  131706827 :     ulong r=0, yi;
     277         [ +  + ]:  168989689 :     for(i=0; i<ny-3; i+=4)
     278                 :            :     {
     279                 :   37282862 :       yi = uel(y,i);   x[i]   ^= (yi<<db)|r; r = yi>>dc;
     280                 :   37282862 :       yi = uel(y,i+1); x[i+1] ^= (yi<<db)|r; r = yi>>dc;
     281                 :   37282862 :       yi = uel(y,i+2); x[i+2] ^= (yi<<db)|r; r = yi>>dc;
     282                 :   37282862 :       yi = uel(y,i+3); x[i+3] ^= (yi<<db)|r; r = yi>>dc;
     283                 :            :     }
     284         [ +  + ]:  258065766 :     for(  ; i<ny; i++)
     285                 :            :     {
     286                 :  126358939 :       ulong yi = uel(y,i); x[i] ^= (yi<<db)|r; r = yi>>dc;
     287                 :            :     }
     288         [ +  + ]:  131706827 :     if (r) x[i] ^= r;
     289                 :            :   }
     290                 :            :   else
     291                 :            :   {
     292         [ +  + ]:   22328711 :     for(i=0; i<ny-3; i+=4)
     293                 :            :     {
     294                 :    2428113 :       x[i]   ^= y[i];
     295                 :    2428113 :       x[i+1] ^= y[i+1];
     296                 :    2428113 :       x[i+2] ^= y[i+2];
     297                 :    2428113 :       x[i+3] ^= y[i+3];
     298                 :            :     }
     299         [ +  + ]:   42780566 :     for(   ; i<ny; i++)
     300                 :   22879968 :       x[i] ^= y[i];
     301                 :            :   }
     302                 :  151607425 : }
     303                 :            : 
     304                 :            : INLINE void
     305                 :   75099794 : F2x_addshiftip(GEN x, GEN y, ulong d)
     306                 :            : {
     307                 :   75099794 :   ulong db, dl=dvmduBIL(d, &db);
     308                 :   75082898 :   return F2x_addshiftipspec(x+2+dl, y+2, lgpol(y), db);
     309                 :            : }
     310                 :            : 
     311                 :            : static GEN
     312                 :   14113564 : F2x_mulspec_basecase(GEN x, GEN y, long nx, long ny)
     313                 :            : {
     314                 :            :   long l, i, j;
     315                 :            :   GEN z;
     316                 :   14113564 :   l = nx + ny;
     317                 :   14113564 :   z = zero_Flv(l+1);
     318         [ +  + ]:   14535170 :   for(i=0; i < ny-1; i++)
     319                 :            :   {
     320                 :     421965 :     GEN zi = z+2+i;
     321                 :     421965 :     ulong yi = uel(y,i);
     322         [ +  + ]:     421965 :     if (yi)
     323         [ +  + ]:   23721266 :       for(j=0; j < BITS_IN_LONG; j++)
     324         [ +  + ]:   23299305 :         if (yi&(1UL<<j)) F2x_addshiftipspec(zi,x,nx,j);
     325                 :            :   }
     326                 :            :   {
     327                 :   14113205 :     GEN zi = z+2+i;
     328 [ +  + ][ +  + ]:   14113205 :     ulong yi = uel(y,i), c = BITS_IN_LONG-bfffo(yi);
         [ +  + ][ +  + ]
     329 [ +  + ][ +  + ]:  132011367 :     for(j=0; j < c; j++)
     330         [ +  + ]:  117897784 :       if (yi&(1UL<<j)) F2x_addshiftipspec(zi,x,nx,j);
     331                 :            :   }
     332                 :   14113583 :   return F2x_renormalize(z, l+2);
     333                 :            : }
     334                 :            : 
     335                 :            : static GEN
     336                 :          0 : F2x_addshift(GEN x, GEN y, long d)
     337                 :            : {
     338                 :          0 :   GEN xd,yd,zd = (GEN)avma;
     339                 :          0 :   long a,lz,ny = lgpol(y), nx = lgpol(x);
     340                 :          0 :   long vs = x[1];
     341                 :            : 
     342                 :          0 :   x += 2; y += 2; a = ny-d;
     343         [ #  # ]:          0 :   if (a <= 0)
     344                 :            :   {
     345         [ #  # ]:          0 :     lz = (a>nx)? ny+2: nx+d+2;
     346                 :          0 :     (void)new_chunk(lz); xd = x+nx; yd = y+ny;
     347         [ #  # ]:          0 :     while (xd > x) *--zd = *--xd;
     348                 :          0 :     x = zd + a;
     349         [ #  # ]:          0 :     while (zd > x) *--zd = 0;
     350                 :            :   }
     351                 :            :   else
     352                 :            :   {
     353                 :          0 :     xd = new_chunk(d); yd = y+d;
     354                 :          0 :     x = F2x_addspec(x,yd,nx,a);
     355         [ #  # ]:          0 :     lz = (a>nx)? ny+2: lg(x)+d;
     356         [ #  # ]:          0 :     x += 2; while (xd > x) *--zd = *--xd;
     357                 :            :   }
     358         [ #  # ]:          0 :   while (yd > y) *--zd = *--yd;
     359                 :          0 :   *--zd = vs;
     360                 :          0 :   *--zd = evaltyp(t_VECSMALL) | evallg(lz); return zd;
     361                 :            : }
     362                 :            : 
     363                 :            : /* shift polynomial + gerepile */
     364                 :            : /* Do not set evalvarn. Cf Flx_shiftip */
     365                 :            : static GEN
     366                 :   14113542 : F2x_shiftip(pari_sp av, GEN x, long v)
     367                 :            : {
     368                 :   14113542 :   long i, lx = lg(x), ly;
     369                 :            :   GEN y;
     370 [ +  + ][ -  + ]:   14113542 :   if (!v || lx==2) return gerepileuptoleaf(av, x);
     371                 :      10298 :   ly = lx + v;
     372                 :      10298 :   (void)new_chunk(ly); /* check that result fits */
     373                 :      10298 :   x += lx; y = (GEN)av;
     374         [ +  + ]:      21354 :   for (i = 2; i<lx; i++) *--y = *--x;
     375         [ +  + ]:      28443 :   for (i = 0; i< v; i++) *--y = 0;
     376                 :      10298 :   y -= 2; y[0] = evaltyp(t_VECSMALL) | evallg(ly);
     377                 :   14113606 :   avma = (pari_sp)y; return y;
     378                 :            : }
     379                 :            : 
     380                 :            : /* fast product (Karatsuba) of polynomials a,b. These are not real GENs, a+2,
     381                 :            :  * b+2 were sent instead. na, nb = number of terms of a, b.
     382                 :            :  * Only c, c0, c1, c2 are genuine GEN.
     383                 :            :  */
     384                 :            : static GEN
     385                 :   17002453 : F2x_mulspec(GEN a, GEN b, long na, long nb)
     386                 :            : {
     387                 :            :   GEN a0,c,c0;
     388                 :   17002453 :   long n0, n0a, i, v = 0;
     389                 :            :   pari_sp av;
     390                 :            : 
     391 [ +  + ][ +  + ]:   17020343 :   while (na && !a[0]) { a++; na-=1; v++; }
     392 [ +  + ][ +  + ]:   17002707 :   while (nb && !b[0]) { b++; nb-=1; v++; }
     393         [ +  + ]:   17002453 :   if (na < nb) swapspec(a,b, na,nb);
     394         [ +  + ]:   17002453 :   if (!nb) return pol0_F2x(0);
     395                 :            : 
     396                 :   14113584 :   av = avma;
     397         [ +  - ]:   14113584 :   if (na < F2x_MUL_KARATSUBA_LIMIT)
     398                 :   14113584 :     return F2x_shiftip(av, F2x_mulspec_basecase(a, b, na, nb), v);
     399                 :          0 :   i=(na>>1); n0=na-i; na=i;
     400                 :          0 :   a0=a+n0; n0a=n0;
     401 [ #  # ][ #  # ]:          0 :   while (n0a && !a[n0a-1]) n0a--;
     402                 :            : 
     403         [ #  # ]:          0 :   if (nb > n0)
     404                 :            :   {
     405                 :            :     GEN b0,c1,c2;
     406                 :            :     long n0b;
     407                 :            : 
     408                 :          0 :     nb -= n0; b0 = b+n0; n0b = n0;
     409 [ #  # ][ #  # ]:          0 :     while (n0b && !b[n0b-1]) n0b--;
     410                 :          0 :     c =  F2x_mulspec(a,b,n0a,n0b);
     411                 :          0 :     c0 = F2x_mulspec(a0,b0,na,nb);
     412                 :            : 
     413                 :          0 :     c2 = F2x_addspec(a0,a,na,n0a);
     414                 :          0 :     c1 = F2x_addspec(b0,b,nb,n0b);
     415                 :            : 
     416                 :          0 :     c1 = F2x_mul(c1,c2);
     417                 :          0 :     c2 = F2x_add(c0,c);
     418                 :            : 
     419                 :          0 :     c2 = F2x_add(c1,c2);
     420                 :          0 :     c0 = F2x_addshift(c0,c2,n0);
     421                 :            :   }
     422                 :            :   else
     423                 :            :   {
     424                 :          0 :     c  = F2x_mulspec(a,b,n0a,nb);
     425                 :          0 :     c0 = F2x_mulspec(a0,b,na,nb);
     426                 :            :   }
     427                 :          0 :   c0 = F2x_addshift(c0,c,n0);
     428                 :   17002473 :   return F2x_shiftip(av,c0, v);
     429                 :            : }
     430                 :            : 
     431                 :            : GEN
     432                 :   17002398 : F2x_mul(GEN x, GEN y)
     433                 :            : {
     434                 :   17002398 :   GEN z = F2x_mulspec(x+2,y+2, lgpol(x),lgpol(y));
     435                 :   17002462 :   z[1] = x[1]; return z;
     436                 :            : }
     437                 :            : 
     438                 :            : GEN
     439                 :    2761841 : F2x_sqr(GEN x)
     440                 :            : {
     441                 :    2761841 :   const ulong sq[]={0,1,4,5,16,17,20,21,64,65,68,69,80,81,84,85};
     442                 :            :   long i,ii,j,jj;
     443                 :    2761841 :   long lx=lg(x), lz=2+((lx-2)<<1);
     444                 :            :   GEN z;
     445                 :    2761841 :   z = cgetg(lz, t_VECSMALL); z[1]=x[1];
     446         [ +  + ]:    5611108 :   for (j=2,jj=2;j<lx;j++,jj++)
     447                 :            :   {
     448                 :    2849264 :     ulong x1=((ulong)x[j]&HIGHMASK)>>BITS_IN_HALFULONG;
     449                 :    2849264 :     ulong x2=(ulong)x[j]&LOWMASK;
     450                 :    2849264 :     z[jj]=0;
     451         [ +  + ]:    2849264 :     if (x2)
     452         [ +  + ]:   23538092 :       for(i=0,ii=0;i<BITS_IN_HALFULONG;i+=4,ii+=8)
     453                 :   20722839 :         z[jj]|=sq[(x2>>i)&15UL]<<ii;
     454                 :    2849264 :     z[++jj]=0;
     455         [ +  + ]:    2849264 :     if (x1)
     456         [ +  + ]:    4639985 :       for(i=0,ii=0;i<BITS_IN_HALFULONG;i+=4,ii+=8)
     457                 :    4050100 :         z[jj]|=sq[(x1>>i)&15UL]<<ii;
     458                 :            :   }
     459                 :    2761844 :   return F2x_renormalize(z, lz);
     460                 :            : }
     461                 :            : 
     462                 :            : static GEN
     463                 :      81760 : F2x_pow2n(GEN x, long n)
     464                 :            : {
     465                 :            :   long i;
     466         [ +  + ]:     245280 :   for(i=1;i<=n;i++)
     467                 :     163520 :     x = F2x_sqr(x);
     468                 :      81760 :   return x;
     469                 :            : }
     470                 :            : 
     471                 :            : int
     472                 :      14567 : F2x_issquare(GEN x)
     473                 :            : {
     474                 :      14567 :   const ulong mask = (ULONG_MAX/3UL)*2;
     475                 :      14567 :   ulong i, lx = lg(x);
     476         [ +  + ]:      29120 :   for (i=2; i<lx; i++)
     477         [ +  + ]:      14567 :     if ((x[i]&mask)) return 0;
     478                 :      14567 :   return 1;
     479                 :            : }
     480                 :            : 
     481                 :            : /* Assume x is a perfect square */
     482                 :            : GEN
     483                 :      18627 : F2x_sqrt(GEN x)
     484                 :            : {
     485                 :      18627 :   const ulong sq[]={0,1,4,5,2,3,6,7,8,9,12,13,10,11,14,15};
     486                 :            :   long i,ii,j,jj;
     487                 :      18627 :   long lx=lg(x), lz=2+((lx-1)>>1);
     488                 :            :   GEN z;
     489                 :      18627 :   z = cgetg(lz, t_VECSMALL); z[1]=x[1];
     490         [ +  + ]:      37254 :   for (j=2,jj=2;jj<lz;j++,jj++)
     491                 :            :   {
     492                 :      18627 :     ulong x2=x[j++];
     493                 :      18627 :     z[jj]=0;
     494         [ +  - ]:      18627 :     if (x2)
     495         [ +  + ]:     156999 :       for(i=0,ii=0;ii<BITS_IN_HALFULONG;i+=8,ii+=4)
     496                 :            :       {
     497                 :     138372 :         ulong rl = (x2>>i)&15UL, rh = (x2>>(i+4))&15UL;
     498                 :     138372 :         z[jj]|=sq[rl|(rh<<1)]<<ii;
     499                 :            :       }
     500         [ -  + ]:      18627 :     if (j<lx)
     501                 :            :     {
     502                 :          0 :       x2 = x[j];
     503         [ #  # ]:          0 :       if (x2)
     504         [ #  # ]:          0 :         for(i=0,ii=0;ii<BITS_IN_HALFULONG;i+=8,ii+=4)
     505                 :            :         {
     506                 :          0 :           ulong rl = (x2>>i)&15UL, rh = (x2>>(i+4))&15UL;
     507                 :          0 :           z[jj]|=(sq[rl|(rh<<1)]<<ii)<<BITS_IN_HALFULONG;
     508                 :            :         }
     509                 :            :     }
     510                 :            :   }
     511                 :      18627 :   return F2x_renormalize(z, lz);
     512                 :            : }
     513                 :            : 
     514                 :            : static GEN
     515                 :        490 : F2x_shiftneg(GEN y, ulong d)
     516                 :            : {
     517                 :        490 :   long db, dl=dvmdsBIL(d, &db);
     518                 :        490 :   long i, ly = lg(y), lx = ly-dl;
     519                 :        490 :   GEN x = cgetg(lx, t_VECSMALL);
     520                 :        490 :   x[1] = y[1];
     521         [ +  - ]:        490 :   if (db)
     522                 :            :   {
     523                 :        490 :     ulong dc=BITS_IN_LONG-db;
     524                 :        490 :     ulong r=0;
     525         [ +  + ]:        980 :     for(i=lx-1; i>=2; i--)
     526                 :            :     {
     527                 :        490 :       x[i] = (((ulong)y[i+dl])>>db)|r;
     528                 :        490 :       r = ((ulong)y[i+dl])<<dc;
     529                 :            :     }
     530                 :            :   }
     531                 :            :   else
     532         [ #  # ]:          0 :     for(i=2; i<lx; i++)
     533                 :          0 :       x[i] = y[i+dl];
     534                 :        490 :   return F2x_renormalize(x,lx);
     535                 :            : }
     536                 :            : 
     537                 :            : static GEN
     538                 :     116326 : F2x_shiftpos(GEN y, ulong d)
     539                 :            : {
     540                 :     116326 :   long db, dl=dvmdsBIL(d, &db);
     541                 :     116326 :   long i, ly = lg(y), lx = ly+dl+(!!db);
     542                 :     116326 :   GEN x = cgetg(lx, t_VECSMALL);
     543         [ +  + ]:     116333 :   x[1] = y[1]; for(i=0; i<dl; i++) x[i+2] = 0;
     544         [ +  + ]:     116326 :   if (db)
     545                 :            :   {
     546                 :     116312 :     ulong dc=BITS_IN_LONG-db;
     547                 :     116312 :     ulong r=0;
     548         [ +  + ]:     235489 :     for(i=2; i<ly; i++)
     549                 :            :     {
     550                 :     119177 :       x[i+dl] = (((ulong)y[i])<<db)|r;
     551                 :     119177 :       r = ((ulong)y[i])>>dc;
     552                 :            :     }
     553                 :     116312 :     x[i+dl] = r;
     554                 :            :   }
     555                 :            :   else
     556         [ +  + ]:         28 :     for(i=2; i<ly; i++)
     557                 :         14 :       x[i+dl] = y[i];
     558                 :     116326 :   return F2x_renormalize(x,lx);
     559                 :            : }
     560                 :            : 
     561                 :            : GEN
     562                 :     116816 : F2x_shift(GEN y, long d)
     563                 :            : {
     564         [ +  + ]:     116816 :   return d<0 ? F2x_shiftneg(y,-d): F2x_shiftpos(y,d);
     565                 :            : }
     566                 :            : 
     567                 :            : /* separate from F2x_divrem for maximal speed. */
     568                 :            : GEN
     569                 :   22779737 : F2x_rem(GEN x, GEN y)
     570                 :            : {
     571                 :            :   long dx,dy;
     572                 :   22779737 :   long lx=lg(x);
     573         [ +  + ]:   22779737 :   dy = F2x_degree(y); if (!dy) return pol0_F2x(x[1]);
     574                 :   21799516 :   dx = F2x_degree_lg(x,lx);
     575                 :   21799464 :   x  = F2x_copy(x);
     576         [ +  + ]:   77494330 :   while (dx>=dy)
     577                 :            :   {
     578                 :   55694812 :     F2x_addshiftip(x,y,dx-dy);
     579 [ +  + ][ +  + ]:   57300696 :     while (lx>2 && x[lx-1]==0) lx--;
     580                 :   55726005 :     dx = F2x_degree_lg(x,lx);
     581                 :            :   }
     582                 :   22779684 :   return F2x_renormalize(x, lx);
     583                 :            : }
     584                 :            : 
     585                 :            : GEN
     586                 :   10482221 : F2x_divrem(GEN x, GEN y, GEN *pr)
     587                 :            : {
     588                 :   10482221 :   long dx, dy, dz, lx = lg(x), vs = x[1];
     589                 :            :   GEN z;
     590                 :            : 
     591                 :   10482221 :   dy = F2x_degree(y);
     592         [ -  + ]:   10482222 :   if (dy<0) pari_err_INV("F2x_divrem",y);
     593         [ -  + ]:   10482222 :   if (pr == ONLY_REM) return F2x_rem(x, y);
     594         [ +  + ]:   10482222 :   if (!dy)
     595                 :            :   {
     596                 :    1765147 :     z = F2x_copy(x);
     597 [ +  + ][ +  - ]:    1765147 :     if (pr && pr != ONLY_DIVIDES) *pr = pol0_F2x(vs);
     598                 :    1765147 :     return z;
     599                 :            :   }
     600                 :    8717075 :   dx = F2x_degree_lg(x,lx);
     601                 :    8717074 :   dz = dx-dy;
     602         [ -  + ]:    8717074 :   if (dz < 0)
     603                 :            :   {
     604 [ #  # ][ #  # ]:          0 :     if (pr == ONLY_DIVIDES) return dx < 0? F2x_copy(x): NULL;
     605                 :          0 :     z = pol0_F2x(vs);
     606         [ #  # ]:          0 :     if (pr) *pr = F2x_copy(x);
     607                 :          0 :     return z;
     608                 :            :   }
     609                 :    8717074 :   z = zero_zv(lg(x)-lg(y)+2); z[1] = vs;
     610                 :    8717075 :   x = F2x_copy(x);
     611         [ +  + ]:   27493535 :   while (dx>=dy)
     612                 :            :   {
     613                 :   18776459 :     F2x_set(z,dx-dy);
     614                 :   18776436 :     F2x_addshiftip(x,y,dx-dy);
     615 [ +  + ][ +  + ]:   19465159 :     while (lx>2 && x[lx-1]==0) lx--;
     616                 :   18776464 :     dx = F2x_degree_lg(x,lx);
     617                 :            :   }
     618                 :    8717076 :   z = F2x_renormalize(z, lg(z));
     619         [ +  + ]:    8717074 :   if (!pr) { cgiv(x); return z; }
     620                 :    8432951 :   x = F2x_renormalize(x, lx);
     621         [ -  + ]:    8432952 :   if (pr == ONLY_DIVIDES) {
     622         [ #  # ]:          0 :     if (lg(x) == 2) { cgiv(x); return z; }
     623                 :          0 :     avma = (pari_sp)(z + lg(z)); return NULL;
     624                 :            :   }
     625                 :   10482222 :   *pr = x; return z;
     626                 :            : }
     627                 :            : 
     628                 :            : long
     629                 :      45337 : F2x_valrem(GEN x, GEN *Z)
     630                 :            : {
     631                 :      45337 :   long v, v2, i, l=lg(x);
     632                 :            :   GEN y;
     633         [ -  + ]:      45337 :   if (l==2) { *Z = F2x_copy(x); return LONG_MAX; }
     634 [ +  - ][ +  + ]:      45436 :   for (i=2; i<l && x[i]==0; i++) /*empty*/;
     635                 :      45337 :   v = i-2;
     636         [ +  - ]:      45337 :   v2 = (i < l)? vals(x[i]): 0;
     637         [ +  + ]:      45337 :   if (v+v2 == 0) { *Z = x; return 0; }
     638                 :       9343 :   l -= i-2;
     639                 :       9343 :   y = cgetg(l, t_VECSMALL); y[1] = x[1];
     640         [ +  + ]:       9343 :   if (v2 == 0)
     641         [ +  + ]:        179 :     for (i=2; i<l; i++) y[i] = x[i+v];
     642         [ +  + ]:       9254 :   else if (l == 3)
     643                 :       9247 :     y[2] = ((ulong)x[2+v]) >> v2;
     644                 :            :   else
     645                 :            :   {
     646                 :          7 :     const ulong sh = BITS_IN_LONG - v2;
     647                 :          7 :     ulong r = x[2+v];
     648         [ +  + ]:         14 :     for (i=3; i<l; i++)
     649                 :            :     {
     650                 :          7 :       y[i-1] = (x[i+v] << sh) | (r >> v2);
     651                 :          7 :       r = x[i+v];
     652                 :            :     }
     653                 :          7 :     y[l-1] = r >> v2;
     654                 :          7 :     (void)F2x_renormalize(y,l);
     655                 :            :   }
     656                 :      45337 :   *Z = y; return (v << TWOPOTBITS_IN_LONG) + v2;
     657                 :            : }
     658                 :            : 
     659                 :            : GEN
     660                 :      36771 : F2x_deflate(GEN x, long d)
     661                 :            : {
     662                 :            :   GEN y;
     663                 :      36771 :   long i,id, dy, dx = F2x_degree(x);
     664         [ -  + ]:      36771 :   if (d <= 1) return F2x_copy(x);
     665         [ -  + ]:      36771 :   if (dx < 0) return F2x_copy(x);
     666                 :      36771 :   dy = dx/d; /* dy+1 coefficients + 1 extra word for variable */
     667                 :      36771 :   y = zero_zv(nbits2lg(dy+1)-1); y[1] = x[1];
     668         [ +  + ]:     189518 :   for (i=id=0; i<=dy; i++,id+=d)
     669         [ +  + ]:     152747 :     if (F2x_coeff(x,id)) F2x_set(y, i);
     670                 :      36771 :   return y;
     671                 :            : }
     672                 :            : 
     673                 :            : /* write p(X) = e(X^2) + Xo(X^2), shallow function */
     674                 :            : void
     675                 :      41035 : F2x_even_odd(GEN p, GEN *pe, GEN *po)
     676                 :            : {
     677                 :      41035 :   long n = F2x_degree(p), n0, n1, i;
     678                 :            :   GEN p0, p1;
     679                 :            : 
     680         [ +  + ]:      79672 :   if (n <= 0) { *pe = F2x_copy(p); *po = pol0_F2x(p[1]); return; }
     681                 :            : 
     682                 :      38627 :   n0 = (n>>1)+1; n1 = n+1 - n0; /* n1 <= n0 <= n1+1 */
     683                 :      38627 :   p0 = zero_zv(nbits2lg(n0+1)-1); p0[1] = p[1];
     684                 :      38631 :   p1 = zero_zv(nbits2lg(n1+1)-1); p1[1] = p[1];
     685         [ +  + ]:    1067010 :   for (i=0; i<n1; i++)
     686                 :            :   {
     687         [ +  + ]:    1028378 :     if (F2x_coeff(p,i<<1)) F2x_set(p0,i);
     688         [ +  + ]:    1028440 :     if (F2x_coeff(p,1+(i<<1))) F2x_set(p1,i);
     689                 :            :   }
     690 [ +  + ][ +  - ]:      38632 :   if (n1 != n0 && F2x_coeff(p,i<<1)) F2x_set(p0,i);
     691                 :      38632 :   *pe = F2x_renormalize(p0,lg(p0));
     692                 :      38628 :   *po = F2x_renormalize(p1,lg(p1));
     693                 :            : }
     694                 :            : 
     695                 :            : GEN
     696                 :     292174 : F2x_deriv(GEN z)
     697                 :            : {
     698                 :     292174 :   const ulong mask = ULONG_MAX/3UL;
     699                 :     292174 :   long i,l = lg(z);
     700                 :     292174 :   GEN x = cgetg(l, t_VECSMALL); x[1] = z[1];
     701         [ +  + ]:     588857 :   for (i=2; i<l; i++) x[i] = (((ulong)z[i])>>1)&mask;
     702                 :     292174 :   return F2x_renormalize(x,l);
     703                 :            : }
     704                 :            : 
     705                 :            : GEN
     706                 :    1273550 : F2x_gcd(GEN a, GEN b)
     707                 :            : {
     708                 :    1273550 :   pari_sp av = avma;
     709         [ +  + ]:    1273550 :   if (lg(b) > lg(a)) swap(a, b);
     710         [ +  + ]:   11149281 :   while (lgpol(b))
     711                 :            :   {
     712                 :    9875731 :     GEN c = F2x_rem(a,b);
     713                 :    9875731 :     a = b; b = c;
     714         [ -  + ]:    9875731 :     if (gc_needed(av,2))
     715                 :            :     {
     716         [ #  # ]:          0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2x_gcd (d = %ld)",F2x_degree(c));
     717                 :          0 :       gerepileall(av,2, &a,&b);
     718                 :            :     }
     719                 :            :   }
     720         [ -  + ]:    1273550 :   if (gc_needed(av,2)) a = gerepileuptoleaf(av, a);
     721                 :    1273550 :   return a;
     722                 :            : }
     723                 :            : 
     724                 :            : GEN
     725                 :     909851 : F2x_extgcd(GEN a, GEN b, GEN *ptu, GEN *ptv)
     726                 :            : {
     727                 :     909851 :   pari_sp av=avma;
     728                 :            :   GEN u,v,d,d1,v1;
     729                 :     909851 :   long vx = a[1];
     730                 :     909851 :   d = a; d1 = b;
     731                 :     909851 :   v = pol0_F2x(vx); v1 = pol1_F2x(vx);
     732         [ +  + ]:   10247638 :   while (lgpol(d1))
     733                 :            :   {
     734                 :    9337784 :     GEN r, q = F2x_divrem(d,d1, &r);
     735                 :    9337784 :     v = F2x_add(v,F2x_mul(q,v1));
     736                 :    9337786 :     u=v; v=v1; v1=u;
     737                 :    9337786 :     u=r; d=d1; d1=u;
     738         [ -  + ]:    9337786 :     if (gc_needed(av,2))
     739                 :            :     {
     740         [ #  # ]:          0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2x_extgcd (d = %ld)",F2x_degree(d));
     741                 :    9337786 :       gerepileall(av,5, &d,&d1,&u,&v,&v1);
     742                 :            :     }
     743                 :            :   }
     744         [ -  + ]:     909852 :   if (ptu) *ptu = F2x_div(F2x_add(d, F2x_mul(b,v)), a);
     745                 :     909852 :   *ptv = v;
     746 [ -  + ][ #  # ]:     909852 :   if (gc_needed(av,2)) gerepileall(av,ptu?3:2,&d,ptv,ptu);
     747                 :     909852 :   return d;
     748                 :            : }
     749                 :            : 
     750                 :            : static GEN
     751                 :        315 : F2x_halfgcd_i(GEN a, GEN b)
     752                 :            : {
     753                 :        315 :   pari_sp av=avma;
     754                 :            :   GEN u,u1,v,v1;
     755                 :        315 :   long vx = a[1];
     756                 :        315 :   long n = (F2x_degree(a)+1)>>1;
     757                 :        315 :   u1 = v = pol0_F2x(vx);
     758                 :        315 :   u = v1 = pol1_F2x(vx);
     759         [ +  + ]:       5019 :   while (F2x_degree(b)>=n)
     760                 :            :   {
     761                 :       4704 :     GEN r, q = F2x_divrem(a,b, &r);
     762                 :       4704 :     a = b; b = r; swap(u,u1); swap(v,v1);
     763                 :       4704 :     u1 = F2x_add(u1, F2x_mul(u, q));
     764                 :       4704 :     v1 = F2x_add(v1, F2x_mul(v, q));
     765         [ -  + ]:       4704 :     if (gc_needed(av,2))
     766                 :            :     {
     767         [ #  # ]:          0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2x_halfgcd (d = %ld)",F2x_degree(b));
     768                 :       4704 :       gerepileall(av,6, &a,&b,&u1,&v1,&u,&v);
     769                 :            :     }
     770                 :            :   }
     771                 :        315 :   return gerepilecopy(av, mkmat2(mkcol2(u,u1), mkcol2(v,v1)));
     772                 :            : }
     773                 :            : 
     774                 :            : GEN
     775                 :        315 : F2x_halfgcd(GEN x, GEN y)
     776                 :            : {
     777                 :            :   pari_sp av;
     778                 :            :   GEN M,q,r;
     779         [ -  + ]:        315 :   if (F2x_degree(y)<F2x_degree(x)) return F2x_halfgcd_i(x,y);
     780                 :        315 :   av = avma;
     781                 :        315 :   q = F2x_divrem(y,x,&r);
     782                 :        315 :   M = F2x_halfgcd_i(x,r);
     783                 :        315 :   gcoeff(M,1,1) = F2x_add(gcoeff(M,1,1), F2x_mul(q, gcoeff(M,1,2)));
     784                 :        315 :   gcoeff(M,2,1) = F2x_add(gcoeff(M,2,1), F2x_mul(q, gcoeff(M,2,2)));
     785                 :        315 :   return gerepilecopy(av, M);
     786                 :            : }
     787                 :            : 
     788                 :            : GEN
     789                 :    3375322 : F2xq_mul(GEN x,GEN y,GEN pol)
     790                 :            : {
     791                 :    3375322 :   GEN z = F2x_mul(x,y);
     792                 :    3375408 :   return F2x_rem(z,pol);
     793                 :            : }
     794                 :            : 
     795                 :            : GEN
     796                 :    2598116 : F2xq_sqr(GEN x,GEN pol)
     797                 :            : {
     798                 :    2598116 :   GEN z = F2x_sqr(x);
     799                 :    2598118 :   return F2x_rem(z,pol);
     800                 :            : }
     801                 :            : 
     802                 :            : GEN
     803                 :     909850 : F2xq_invsafe(GEN x, GEN T)
     804                 :            : {
     805                 :     909850 :   GEN V, z = F2x_extgcd(T, x, NULL, &V);
     806         [ -  + ]:     909852 :   if (F2x_degree(z)) return NULL;
     807                 :     909852 :   return V;
     808                 :            : }
     809                 :            : 
     810                 :            : GEN
     811                 :     909850 : F2xq_inv(GEN x,GEN T)
     812                 :            : {
     813                 :     909850 :   pari_sp av=avma;
     814                 :     909850 :   GEN U = F2xq_invsafe(x, T);
     815         [ -  + ]:     909852 :   if (!U) pari_err_INV("F2xq_inv",x);
     816                 :     909852 :   return gerepileuptoleaf(av, U);
     817                 :            : }
     818                 :            : 
     819                 :            : GEN
     820                 :     342615 : F2xq_div(GEN x,GEN y,GEN T)
     821                 :            : {
     822                 :     342615 :   pari_sp av = avma;
     823                 :     342615 :   return gerepileuptoleaf(av, F2xq_mul(x,F2xq_inv(y,T),T));
     824                 :            : }
     825                 :            : 
     826                 :            : static GEN
     827                 :     327523 : _F2xq_red(void *E, GEN x)
     828                 :     327523 : { return F2x_rem(x, (GEN)E); }
     829                 :            : static GEN
     830                 :     534242 : _F2xq_add(void *E, GEN x, GEN y)
     831                 :     534242 : { (void)E; return F2x_add(x,y); }
     832                 :            : 
     833                 :            : static GEN
     834                 :     761148 : _F2xq_cmul(void *E, GEN P, long a, GEN x)
     835                 :            : {
     836                 :     761148 :   GEN pol = (GEN) E;
     837         [ +  + ]:     761148 :   return F2x_coeff(P,a) ? x: pol0_F2x(pol[1]);
     838                 :            : }
     839                 :            : static GEN
     840                 :     490085 : _F2xq_sqr(void *E, GEN x)
     841                 :     490085 : { return F2xq_sqr(x, (GEN) E); }
     842                 :            : 
     843                 :            : static GEN
     844                 :     515475 : _F2xq_mul(void *E, GEN x, GEN y)
     845                 :     515475 : { return F2xq_mul(x,y, (GEN) E); }
     846                 :            : 
     847                 :            : static GEN
     848                 :     474772 : _F2xq_one(void *E)
     849                 :            : {
     850                 :     474772 :   GEN pol = (GEN) E;
     851                 :     474772 :   return pol1_F2x(pol[1]);
     852                 :            : }
     853                 :            : static GEN
     854                 :     218491 : _F2xq_zero(void *E)
     855                 :            : {
     856                 :     218491 :   GEN pol = (GEN) E;
     857                 :     218491 :   return pol0_F2x(pol[1]);
     858                 :            : }
     859                 :            : 
     860                 :            : GEN
     861                 :     294870 : F2xq_pow(GEN x, GEN n, GEN pol)
     862                 :            : {
     863                 :     294870 :   pari_sp av=avma;
     864                 :            :   GEN y;
     865                 :            : 
     866         [ +  + ]:     294870 :   if (!signe(n)) return pol1_F2x(x[1]);
     867         [ +  + ]:     294723 :   if (is_pm1(n)) /* +/- 1 */
     868         [ +  + ]:     171283 :     return (signe(n) < 0)? F2xq_inv(x,pol): F2x_copy(x);
     869                 :            : 
     870         [ +  + ]:     123440 :   if (signe(n) < 0) x = F2xq_inv(x,pol);
     871                 :     123440 :   y = gen_pow(x, n, (void*)pol, &_F2xq_sqr, &_F2xq_mul);
     872                 :     294870 :   return gerepileupto(av, y);
     873                 :            : }
     874                 :            : 
     875                 :            : GEN
     876                 :       3955 : F2xq_powu(GEN x, ulong n, GEN pol)
     877                 :            : {
     878                 :       3955 :   pari_sp av=avma;
     879                 :            :   GEN y;
     880   [ -  +  -  + ]:       3955 :   switch(n)
     881                 :            :   {
     882                 :          0 :     case 0: return pol1_F2x(x[1]);
     883                 :       1981 :     case 1: return F2x_copy(x);
     884                 :          0 :     case 2: return F2xq_sqr(x,pol);
     885                 :            :   }
     886                 :       1974 :   y = gen_powu(x, n, (void*)pol, &_F2xq_sqr, &_F2xq_mul);
     887                 :       3955 :   return gerepileupto(av, y);
     888                 :            : }
     889                 :            : 
     890                 :            : /* generates the list of powers of x of degree 0,1,2,...,l*/
     891                 :            : GEN
     892                 :     147882 : F2xq_powers(GEN x, long l, GEN T)
     893                 :            : {
     894                 :     147882 :   int use_sqr = 2*F2x_degree(x) >= F2x_degree(T);
     895                 :     147882 :   return gen_powers(x, l, use_sqr, (void*)T, &_F2xq_sqr, &_F2xq_mul, &_F2xq_one);
     896                 :            : }
     897                 :            : 
     898                 :            : GEN
     899                 :      60200 : F2xq_matrix_pow(GEN y, long n, long m, GEN P)
     900                 :            : {
     901                 :      60200 :   return F2xV_to_F2m(F2xq_powers(y,m-1,P),n);
     902                 :            : }
     903                 :            : 
     904                 :            : GEN
     905                 :      77854 : F2x_Frobenius(GEN T)
     906                 :            : {
     907                 :      77854 :   return F2xq_sqr(polx_F2x(T[1]), T);
     908                 :            : }
     909                 :            : 
     910                 :            : GEN
     911                 :      20825 : F2x_matFrobenius(GEN T)
     912                 :            : {
     913                 :      20825 :   long n = F2x_degree(T);
     914                 :      20825 :   return F2xq_matrix_pow(F2x_Frobenius(T), n, n, T);
     915                 :            : }
     916                 :            : 
     917                 :            : static struct bb_algebra F2xq_algebra = { _F2xq_red,_F2xq_add,_F2xq_mul,_F2xq_sqr,_F2xq_one,_F2xq_zero};
     918                 :            : 
     919                 :            : GEN
     920                 :     409486 : F2x_F2xqV_eval(GEN Q, GEN x, GEN T)
     921                 :            : {
     922                 :     409486 :   long d = F2x_degree(Q);
     923                 :     409486 :   return gen_bkeval_powers(Q,d,x,(void*)T,&F2xq_algebra,_F2xq_cmul);
     924                 :            : }
     925                 :            : 
     926                 :            : GEN
     927                 :      36245 : F2x_F2xq_eval(GEN Q, GEN x, GEN T)
     928                 :            : {
     929                 :      36245 :   long d = F2x_degree(Q);
     930                 :      36246 :   int use_sqr = 2*F2x_degree(x) >= F2x_degree(T);
     931                 :      36247 :   return gen_bkeval(Q, d, x, use_sqr, (void*)T, &F2xq_algebra, _F2xq_cmul);
     932                 :            : }
     933                 :            : 
     934                 :            : static GEN
     935                 :      23466 : F2xq_autpow_sqr(void * T, GEN x) { return F2x_F2xq_eval(x, x, (GEN) T); }
     936                 :            : 
     937                 :            : static GEN
     938                 :      12764 : F2xq_autpow_mul(void * T, GEN x, GEN y) { return F2x_F2xq_eval(x, y, (GEN) T); }
     939                 :            : 
     940                 :            : GEN
     941                 :      15219 : F2xq_autpow(GEN x, long n, GEN T)
     942                 :            : {
     943                 :      15219 :   return gen_powu(x,n,(void*)T,F2xq_autpow_sqr,F2xq_autpow_mul);
     944                 :            : }
     945                 :            : 
     946                 :            : ulong
     947                 :      84514 : F2xq_trace(GEN x, GEN T)
     948                 :            : {
     949                 :      84514 :   pari_sp av = avma;
     950                 :            :   ulong t;
     951                 :      84514 :   long n = F2x_degree(T)-1;
     952                 :      84514 :   GEN z = F2x_mul(x, F2x_deriv(T));
     953                 :      84514 :   z = F2x_rem(z, T);
     954                 :      84514 :   t = F2x_degree(z)<n ? 0 : 1;
     955                 :      84514 :   avma = av; return t;
     956                 :            : }
     957                 :            : 
     958                 :            : GEN
     959                 :          7 : F2xq_conjvec(GEN x, GEN T)
     960                 :            : {
     961                 :          7 :   long i, l = F2x_degree(T);
     962                 :          7 :   GEN z = cgetg(l,t_COL);
     963                 :          7 :   gel(z,1) = F2x_copy(x);
     964         [ +  + ]:        133 :   for (i=2; i<l; i++) gel(z,i) = F2xq_sqr(gel(z,i-1), T);
     965                 :          7 :   return z;
     966                 :            : }
     967                 :            : 
     968                 :            : static GEN
     969                 :     289534 : _F2xq_pow(void *data, GEN x, GEN n)
     970                 :            : {
     971                 :     289534 :   GEN pol = (GEN) data;
     972                 :     289534 :   return F2xq_pow(x,n, pol);
     973                 :            : }
     974                 :            : 
     975                 :            : static GEN
     976                 :         84 : _F2xq_rand(void *data)
     977                 :            : {
     978                 :         84 :   pari_sp av=avma;
     979                 :         84 :   GEN pol = (GEN) data;
     980                 :         84 :   long d = F2x_degree(pol);
     981                 :            :   GEN z;
     982                 :            :   do
     983                 :            :   {
     984                 :         84 :     avma = av;
     985                 :         84 :     z = random_F2x(d,pol[1]);
     986         [ -  + ]:         84 :   } while (lgpol(z)==0);
     987                 :         84 :   return z;
     988                 :            : }
     989                 :            : 
     990                 :            : static GEN F2xq_easylog(void* E, GEN a, GEN g, GEN ord);
     991                 :            : 
     992                 :            : static const struct bb_group F2xq_star={_F2xq_mul,_F2xq_pow,_F2xq_rand,hash_GEN,F2x_equal,F2x_equal1,F2xq_easylog};
     993                 :            : 
     994                 :            : GEN
     995                 :        350 : F2xq_order(GEN a, GEN ord, GEN T)
     996                 :            : {
     997                 :        350 :   return gen_order(a,ord,(void*)T,&F2xq_star);
     998                 :            : }
     999                 :            : 
    1000                 :            : static long
    1001                 :     109956 : F2x_is_smooth_squarefree(GEN f, long r)
    1002                 :            : {
    1003                 :     109956 :   pari_sp av = avma;
    1004                 :            :   long i;
    1005                 :     109956 :   GEN sx = polx_F2x(f[1]), a = sx;
    1006                 :     109956 :   for(i=1;  ;i++)
    1007                 :            :   {
    1008                 :    1025157 :     a = F2xq_sqr(F2x_rem(a,f),f);
    1009         [ +  + ]:    1025157 :     if (F2x_equal(a, F2x_rem(sx,f))) {avma = av; return 1;}
    1010         [ +  + ]:     986601 :     if (i==r) {avma = av; return 0;}
    1011                 :     915201 :     f = F2x_div(f, F2x_gcd(F2x_add(a,sx),f));
    1012                 :    1025157 :   }
    1013                 :            : }
    1014                 :            : 
    1015                 :            : static long
    1016                 :      95417 : F2x_is_smooth(GEN g, long r)
    1017                 :            : {
    1018                 :      95417 :   GEN f = gen_0;
    1019         [ -  + ]:      95417 :   if (lgpol(g)==0) return 0;
    1020                 :            :   while (1)
    1021                 :            :   {
    1022                 :     109956 :     f = F2x_gcd(g, F2x_deriv(g));
    1023         [ +  + ]:     109956 :     if (!F2x_is_smooth_squarefree(F2x_div(g, f), r))
    1024                 :      71400 :       return 0;
    1025         [ +  + ]:      38556 :     if (F2x_degree(f)==0) return 1;
    1026         [ +  - ]:      14539 :     g = F2x_issquare(f) ? F2x_sqrt(f): f;
    1027                 :     109956 :   }
    1028                 :            : }
    1029                 :            : 
    1030                 :            : static GEN
    1031                 :       7504 : F2x_factorel(GEN h)
    1032                 :            : {
    1033                 :       7504 :   GEN F = F2x_factcantor(h, 0);
    1034                 :       7504 :   GEN F1 = gel(F, 1), F2 = gel(F, 2);
    1035                 :       7504 :   long i, l1 = lg(F1)-1;
    1036                 :       7504 :   GEN p2 = cgetg(l1+1, t_VECSMALL);
    1037                 :       7504 :   GEN e2 = cgetg(l1+1, t_VECSMALL);
    1038         [ +  + ]:      34279 :   for (i = 1; i <= l1; ++i)
    1039                 :            :   {
    1040                 :      26775 :     p2[i] = mael(F1, i, 2);
    1041                 :      26775 :     e2[i] = F2[i];
    1042                 :            :   }
    1043                 :       7504 :   return mkmat2(p2, e2);
    1044                 :            : }
    1045                 :            : 
    1046                 :            : static GEN
    1047                 :      18272 : mkF2(ulong x, long v) { return mkvecsmall2(v, x); }
    1048                 :            : 
    1049                 :            : static GEN F2xq_log_Coppersmith_d(GEN W, GEN g, long r, long n, GEN T, GEN mo);
    1050                 :            : 
    1051                 :            : static GEN
    1052                 :         28 : F2xq_log_from_rel(GEN W, GEN rel, long r, long n, GEN T, GEN m)
    1053                 :            : {
    1054                 :         28 :   pari_sp av = avma;
    1055                 :         28 :   GEN F = gel(rel,1), E = gel(rel,2), o = gen_0;
    1056                 :         28 :   long i, l = lg(F);
    1057         [ +  + ]:        238 :   for(i=1; i<l; i++)
    1058                 :            :   {
    1059                 :        210 :     GEN R = gel(W, F[i]);
    1060         [ -  + ]:        210 :     if (signe(R)==0) /* Already failed */
    1061                 :          0 :       return NULL;
    1062         [ +  + ]:        210 :     else if (signe(R)<0) /* Not yet tested */
    1063                 :            :     {
    1064                 :          7 :       setsigne(gel(W,F[i]),0);
    1065                 :          7 :       R = F2xq_log_Coppersmith_d(W, mkF2(F[i],T[1]), r, n, T, m);
    1066         [ -  + ]:          7 :       if (!R) return NULL;
    1067                 :            :     }
    1068                 :        210 :     o = Fp_add(o, mulis(R, E[i]), m);
    1069                 :            :   }
    1070                 :         28 :   return gerepileuptoint(av, o);
    1071                 :            : }
    1072                 :            : 
    1073                 :            : static GEN
    1074                 :         42 : F2xq_log_Coppersmith_d(GEN W, GEN g, long r, long n, GEN T, GEN mo)
    1075                 :            : {
    1076                 :         42 :   pari_sp av = avma, av2;
    1077                 :         42 :   long dg = F2x_degree(g), k = r-1, m = maxss((dg-k)/2,0);
    1078                 :         42 :   long i, j, l = dg-m, N;
    1079                 :         42 :   GEN v = cgetg(k+m+1,t_MAT);
    1080                 :         42 :   long dT = F2x_degree(T);
    1081                 :         42 :   long h = dT>>n, d = dT-(h<<n);
    1082                 :         42 :   GEN R = F2x_add(F2x_shift(pol1_F2x(T[1]), dT), T);
    1083                 :         42 :   GEN z = F2x_rem(F2x_shift(pol1_F2x(T[1]),h), g);
    1084         [ +  + ]:        532 :   for(i=1; i<=k+m; i++)
    1085                 :            :   {
    1086                 :        490 :     gel(v,i) = F2x_to_F2v(F2x_shift(z,-l),m);
    1087                 :        490 :     z = F2x_rem(F2x_shift(z,1),g);
    1088                 :            :   }
    1089                 :         42 :   v = F2m_ker(v);
    1090         [ +  + ]:        462 :   for(i=1; i<=k; i++)
    1091                 :        420 :     gel(v,i) = F2v_to_F2x(gel(v,i),T[1]);
    1092                 :         42 :   N = 1<<k;
    1093                 :         42 :   av2 = avma;
    1094         [ +  + ]:      20832 :   for (i=1; i<N; i++)
    1095                 :            :   {
    1096                 :            :     GEN p,q,qh,a,b;
    1097                 :      20818 :     avma = av2;
    1098                 :      20818 :     q = pol0_F2x(T[1]);
    1099         [ +  + ]:     228998 :     for(j=0; j<k; j++)
    1100         [ +  + ]:     208180 :       if (i&(1UL<<j))
    1101                 :      99400 :         q = F2x_add(q, gel(v,j+1));
    1102                 :      20818 :     qh= F2x_shift(q,h);
    1103                 :      20818 :     p = F2x_rem(qh,g);
    1104                 :      20818 :     b = F2x_add(F2x_mul(R, F2x_pow2n(q, n)), F2x_shift(F2x_pow2n(p, n), d));
    1105 [ +  - ][ +  + ]:      20818 :     if (lgpol(b)==0 || !F2x_is_smooth(b, r)) continue;
    1106                 :         28 :     a = F2x_div(F2x_add(qh,p),g);
    1107 [ -  + ][ #  # ]:         28 :     if (F2x_degree(F2x_gcd(a,q)) &&  F2x_degree(F2x_gcd(a,p))) continue;
    1108 [ +  - ][ +  - ]:         28 :     if (!(lgpol(a)==0 || !F2x_is_smooth(a, r)))
    1109                 :            :     {
    1110                 :         28 :       GEN F = F2x_factorel(b);
    1111                 :         28 :       GEN G = F2x_factorel(a);
    1112                 :         28 :       GEN FG = vecsmall_concat(vecsmall_append(gel(F, 1), 2), gel(G, 1));
    1113                 :         28 :       GEN E  = vecsmall_concat(vecsmall_append(gel(F, 2), -d),
    1114                 :         56 :                                zv_z_mul(gel(G, 2),-(1L<<n)));
    1115                 :         28 :       GEN R  = famatsmall_reduce(mkmat2(FG, E));
    1116                 :         28 :       GEN l  = F2xq_log_from_rel(W, R, r, n, T, mo);
    1117         [ -  + ]:         28 :       if (!l) continue;
    1118                 :         28 :       l = Fp_div(l,int2n(n),mo);
    1119         [ +  + ]:         28 :       if (dg <= r)
    1120                 :            :       {
    1121                 :          7 :         affii(l,gel(W,g[2]));
    1122         [ -  + ]:          7 :         if (DEBUGLEVEL>1) err_printf("Found %lu\n", g[2]);
    1123                 :            :       }
    1124                 :         28 :       return gerepileuptoint(av, l);
    1125                 :            :     }
    1126                 :            :   }
    1127                 :         14 :   avma = av;
    1128                 :         42 :   return NULL;
    1129                 :            : }
    1130                 :            : 
    1131                 :            : static GEN
    1132                 :        119 : F2xq_log_find_rel(GEN b, long r, GEN T, GEN *g, ulong *e)
    1133                 :            : {
    1134                 :        119 :   pari_sp av = avma;
    1135                 :            :   while (1)
    1136                 :            :   {
    1137                 :            :     GEN M;
    1138                 :        315 :     *g = F2xq_mul(*g, b, T); (*e)++;
    1139                 :        315 :     M = F2x_halfgcd(*g,T);
    1140         [ +  + ]:        315 :     if (F2x_is_smooth(gcoeff(M,1,1), r))
    1141                 :            :     {
    1142                 :        175 :       GEN z = F2x_add(F2x_mul(gcoeff(M,1,1),*g), F2x_mul(gcoeff(M,1,2),T));
    1143         [ +  + ]:        175 :       if (F2x_is_smooth(z, r))
    1144                 :            :       {
    1145                 :        119 :         GEN F = F2x_factorel(z);
    1146                 :        119 :         GEN G = F2x_factorel(gcoeff(M,1,1));
    1147                 :        119 :         GEN rel = mkmat2(vecsmall_concat(gel(F, 1),gel(G, 1)),
    1148                 :        238 :                          vecsmall_concat(gel(F, 2),zv_neg(gel(G, 2))));
    1149                 :        119 :         gerepileall(av, 2, g, &rel);
    1150                 :        119 :         return rel;
    1151                 :            :       }
    1152                 :            :     }
    1153         [ -  + ]:        196 :     if (gc_needed(av,2))
    1154                 :            :     {
    1155         [ #  # ]:          0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2xq_log_find_rel");
    1156                 :          0 :       *g = gerepileuptoleaf(av, *g);
    1157                 :            :     }
    1158                 :        196 :   }
    1159                 :            : }
    1160                 :            : 
    1161                 :            : static GEN
    1162                 :         14 : F2xq_log_Coppersmith_rec(GEN W, long r2, GEN a, long r, long n, GEN T, GEN m)
    1163                 :            : {
    1164                 :         14 :   GEN b = polx_F2x(T[1]);
    1165                 :         14 :   ulong AV = 0;
    1166                 :         14 :   GEN g = a, bad = pol0_F2x(T[1]);
    1167                 :            :   pari_timer ti;
    1168                 :            :   while(1)
    1169                 :            :   {
    1170                 :            :     long i, l;
    1171                 :            :     GEN V, F, E, Ao;
    1172                 :        119 :     timer_start(&ti);
    1173                 :        119 :     V = F2xq_log_find_rel(b, r2, T, &g, &AV);
    1174         [ -  + ]:        119 :     if (DEBUGLEVEL>1) timer_printf(&ti,"%ld-smooth element",r2);
    1175                 :        119 :     F = gel(V,1); E = gel(V,2);
    1176                 :        119 :     l = lg(F);
    1177                 :        119 :     Ao = gen_0;
    1178         [ +  + ]:        455 :     for(i=1; i<l; i++)
    1179                 :            :     {
    1180                 :        441 :       GEN Fi = mkF2(F[i], T[1]);
    1181                 :            :       GEN R;
    1182         [ +  + ]:        441 :       if (F2x_degree(Fi) <= r)
    1183                 :            :       {
    1184         [ -  + ]:        315 :         if (signe(gel(W,F[i]))==0)
    1185                 :          0 :           break;
    1186         [ -  + ]:        315 :         else if (signe(gel(W,F[i]))<0)
    1187                 :            :         {
    1188                 :          0 :           setsigne(gel(W,F[i]),0);
    1189                 :          0 :           R = F2xq_log_Coppersmith_d(W,Fi,r,n,T,m);
    1190                 :            :         } else
    1191                 :        315 :           R = gel(W,F[i]);
    1192                 :            :       }
    1193                 :            :       else
    1194                 :            :       {
    1195         [ +  + ]:        126 :         if (F2x_equal(Fi,bad)) break;
    1196                 :         35 :         R = F2xq_log_Coppersmith_d(W,Fi,r,n,T,m);
    1197         [ +  + ]:         35 :         if (!R) bad = Fi;
    1198                 :            :       }
    1199         [ +  + ]:        350 :       if (!R) break;
    1200                 :        336 :       Ao = Fp_add(Ao, mulis(R, E[i]), m);
    1201                 :            :     }
    1202         [ +  + ]:        119 :     if (i==l) return subis(Ao,AV);
    1203                 :        105 :   }
    1204                 :            : }
    1205                 :            : 
    1206                 :            : /* Coppersmith:
    1207                 :            :  T*X^e = X^(h*2^n)-R
    1208                 :            :  (u*x^h + v)^(2^n) = u^(2^n)*X^(h*2^n)+v^(2^n)
    1209                 :            :  (u*x^h + v)^(2^n) = u^(2^n)*R+v^(2^n)
    1210                 :            : */
    1211                 :            : 
    1212                 :            : static GEN
    1213                 :      54019 : rel_Coppersmith(GEN u, GEN v, long h, GEN R, long r, long n, long d)
    1214                 :            : {
    1215                 :            :   GEN b, F, G, M;
    1216                 :      54019 :   GEN a = F2x_add(F2x_shift(u, h), v);
    1217         [ +  + ]:      54019 :   if (!F2x_is_smooth(a, r)) return NULL;
    1218                 :      20062 :   b = F2x_add(F2x_mul(R, F2x_pow2n(u, n)), F2x_shift(F2x_pow2n(v, n),d));
    1219         [ +  + ]:      20062 :   if (!F2x_is_smooth(b, r)) return NULL;
    1220                 :       3605 :   F = F2x_factorel(a);
    1221                 :       3605 :   G = F2x_factorel(b);
    1222                 :       3605 :   M = mkmat2(vecsmall_concat(gel(F, 1), vecsmall_append(gel(G, 1), 2)),
    1223                 :      10815 :              vecsmall_concat(zv_z_mul(gel(F, 2),1UL<<n), vecsmall_append(zv_neg(gel(G, 2)),d)));
    1224                 :      54019 :   return famatsmall_reduce(M);
    1225                 :            : }
    1226                 :            : 
    1227                 :            : static GEN
    1228                 :          7 : F2xq_log_Coppersmith(long nbrel, long r, long n, GEN T)
    1229                 :            : {
    1230                 :          7 :   long dT = F2x_degree(T);
    1231                 :          7 :   long h = dT>>n, d = dT-(h<<n);
    1232                 :          7 :   GEN R = F2x_add(F2x_shift(pol1_F2x(T[1]), dT), T);
    1233                 :          7 :   GEN u = mkF2(0,T[1]), v = mkF2(0,T[1]);
    1234                 :          7 :   long rel = 1, nbtest = 0;
    1235                 :          7 :   GEN M = cgetg(nbrel+1, t_VEC);
    1236                 :          7 :   pari_sp av = avma;
    1237                 :            :   long i,j;
    1238         [ -  + ]:          7 :   if (DEBUGLEVEL) err_printf("Coppersmith (R = %ld): ",F2x_degree(R));
    1239                 :          7 :   for (i=1; ; i++)
    1240                 :            :   {
    1241                 :        868 :     u[2] = i;
    1242         [ +  + ]:      54250 :     for(j=1; j<=i; j++)
    1243                 :            :     {
    1244                 :      53389 :       v[2] = j;
    1245                 :      53389 :       avma = av;
    1246         [ +  + ]:      53389 :       if (F2x_degree(F2x_gcd(u,v))==0)
    1247                 :            :       {
    1248                 :      27013 :         GEN z = rel_Coppersmith(u, v, h, R, r, n, d);
    1249                 :      27013 :         nbtest++;
    1250         [ +  + ]:      27013 :         if (z)
    1251                 :            :         {
    1252                 :       1127 :           gel(M,rel++) = gerepilecopy(av, z); av = avma;
    1253 [ -  + ][ #  # ]:       1127 :           if (DEBUGLEVEL && (rel&511UL)==0)
    1254                 :          0 :             err_printf("%ld%%[%ld] ",rel*100/nbrel,i);
    1255                 :            :         }
    1256         [ -  + ]:      27013 :         if (rel>nbrel) break;
    1257         [ +  + ]:      27013 :         if (i==j) continue;
    1258                 :      27006 :         z = rel_Coppersmith(v, u, h, R, r, n, d);
    1259                 :      27006 :         nbtest++;
    1260         [ +  + ]:      27006 :         if (!z) continue;
    1261                 :       2478 :         gel(M,rel++) = gerepilecopy(av, z); av = avma;
    1262 [ -  + ][ #  # ]:       2478 :         if (DEBUGLEVEL && (rel&511UL)==0)
    1263                 :          0 :           err_printf("%ld%%[%ld] ",rel*100/nbrel,i);
    1264         [ +  + ]:       2478 :         if (rel>nbrel) break;
    1265                 :            :       }
    1266                 :            :     }
    1267         [ +  + ]:        868 :     if (rel>nbrel) break;
    1268                 :        861 :   }
    1269         [ -  + ]:          7 :   if (DEBUGLEVEL) err_printf(": %ld tests\n", nbtest);
    1270                 :          7 :   return M;
    1271                 :            : }
    1272                 :            : 
    1273                 :            : static GEN
    1274                 :          7 : smallirred_F2x(ulong n, long sv)
    1275                 :            : {
    1276                 :          7 :   GEN a = zero_zv(nbits2lg(n+1)-1);
    1277                 :          7 :   a[1] = sv; F2x_set(a,n); a[2]++;
    1278         [ +  + ]:        140 :   while (!F2x_is_irred(a)) a[2]+=2;
    1279                 :          7 :   return a;
    1280                 :            : }
    1281                 :            : 
    1282                 :            : static GEN
    1283                 :          7 : check_kernel(long N, GEN M, GEN T, GEN m)
    1284                 :            : {
    1285                 :          7 :   pari_sp av = avma;
    1286                 :          7 :   GEN K = FpMs_leftkernel_elt(M, N, m);
    1287                 :          7 :   long i, f=0;
    1288                 :          7 :   long l = lg(K), lm = lgefint(m);
    1289                 :          7 :   GEN idx = diviiexact(subis(int2n(F2x_degree(T)),1),m);
    1290                 :          7 :   GEN g = F2xq_pow(polx_F2x(T[1]), idx, T);
    1291                 :            :   pari_timer ti;
    1292         [ -  + ]:          7 :   if (DEBUGLEVEL) timer_start(&ti);
    1293                 :          7 :   K = FpC_Fp_mul(K, Fp_inv(gel(K,g[2]), m), m);
    1294         [ +  + ]:      28672 :   for(i=1; i<l; i++)
    1295                 :            :   {
    1296                 :      28665 :     GEN k = gel(K,i);
    1297 [ +  + ][ -  + ]:      28665 :     if (signe(k)==0 || !F2x_equal(F2xq_pow(g, k, T),
    1298                 :       2590 :                                   F2xq_pow(mkF2(i,T[1]), idx, T)))
    1299                 :      26075 :       gel(K,i) = cgetineg(lm);
    1300                 :            :     else
    1301                 :       2590 :       f++;
    1302                 :            :   }
    1303         [ -  + ]:          7 :   if (DEBUGLEVEL) timer_printf(&ti,"found %ld logs", f);
    1304                 :          7 :   return gerepileupto(av, K);
    1305                 :            : }
    1306                 :            : 
    1307                 :            : static GEN
    1308                 :          7 : F2xq_log_index(GEN a0, GEN b0, GEN m, GEN T0)
    1309                 :            : {
    1310                 :          7 :   pari_sp av = avma;
    1311                 :          7 :   GEN  M, S, a, b, Ao=NULL, Bo=NULL, W, e;
    1312                 :            :   pari_timer ti;
    1313                 :          7 :   long n = F2x_degree(T0), r = (long) (sqrt((double) 2*n))-(n>100);
    1314                 :          7 :   GEN T = smallirred_F2x(n,T0[1]);
    1315                 :          7 :   long d = 2, r2 = 3*r/2, d2 = 2;
    1316                 :          7 :   long N = (1UL<<(r+1))-1UL;
    1317                 :          7 :   long nbi = itos(ffsumnbirred(gen_2, r)), nbrel=nbi*5/4;
    1318         [ -  + ]:          7 :   if (DEBUGLEVEL)
    1319                 :            :   {
    1320                 :          0 :     err_printf("F2xq_log: Parameters r=%ld r2=%ld\n", r,r2);
    1321                 :          0 :     err_printf("F2xq_log: Size FB=%ld rel. needed=%ld\n", nbi, nbrel);
    1322                 :          0 :     timer_start(&ti);
    1323                 :            :   }
    1324                 :          7 :   S = Flx_to_F2x(Flx_ffisom(F2x_to_Flx(T0),F2x_to_Flx(T),2));
    1325                 :          7 :   a = F2x_F2xq_eval(a0, S, T);
    1326                 :          7 :   b = F2x_F2xq_eval(b0, S, T);
    1327         [ -  + ]:          7 :   if (DEBUGLEVEL) timer_printf(&ti,"model change");
    1328                 :          7 :   M = F2xq_log_Coppersmith(nbrel,r,d,T);
    1329         [ -  + ]:          7 :   if(DEBUGLEVEL)
    1330                 :          0 :     timer_printf(&ti,"relations");
    1331                 :          7 :   W = check_kernel(N, M, T, m);
    1332                 :          7 :   timer_start(&ti);
    1333                 :          7 :   Ao = F2xq_log_Coppersmith_rec(W, r2, a, r, d2, T, m);
    1334         [ -  + ]:          7 :   if (DEBUGLEVEL) timer_printf(&ti,"smooth element");
    1335                 :          7 :   Bo = F2xq_log_Coppersmith_rec(W, r2, b, r, d2, T, m);
    1336         [ -  + ]:          7 :   if (DEBUGLEVEL) timer_printf(&ti,"smooth generator");
    1337                 :          7 :   e = Fp_div(Ao, Bo, m);
    1338         [ -  + ]:          7 :   if (!F2x_equal(F2xq_pow(b0,e,T0),a0)) pari_err_BUG("F2xq_log");
    1339                 :          7 :   return gerepileupto(av, e);
    1340                 :            : }
    1341                 :            : 
    1342                 :            : static GEN
    1343                 :      86163 : F2xq_easylog(void* E, GEN a, GEN g, GEN ord)
    1344                 :            : {
    1345         [ +  + ]:      86163 :   if (F2x_equal1(a)) return gen_0;
    1346         [ +  + ]:      60208 :   if (F2x_equal(a,g)) return gen_1;
    1347         [ +  + ]:      55657 :   if (typ(ord)!=t_INT) return NULL;
    1348         [ +  + ]:      28042 :   if (expi(ord)<28) return NULL;
    1349                 :      86163 :   return F2xq_log_index(a,g,ord,(GEN)E);
    1350                 :            : }
    1351                 :            : 
    1352                 :            : GEN
    1353                 :      53298 : F2xq_log(GEN a, GEN g, GEN ord, GEN T)
    1354                 :            : {
    1355                 :      53298 :   GEN z, v = dlog_get_ordfa(ord);
    1356                 :      53298 :   ord = mkvec2(gel(v,1),ZM_famat_limit(gel(v,2),int2n(28)));
    1357                 :      53298 :   z = gen_PH_log(a,g,ord,(void*)T,&F2xq_star);
    1358         [ -  + ]:      53298 :   return z? z: cgetg(1,t_VEC);
    1359                 :            : }
    1360                 :            : 
    1361                 :            : GEN
    1362                 :      39375 : F2xq_Artin_Schreier(GEN a, GEN T)
    1363                 :            : {
    1364                 :      39375 :   pari_sp ltop=avma;
    1365                 :      39375 :   long j,N = F2x_degree(T);
    1366                 :            :   GEN Q, XP;
    1367                 :            :   pari_timer ti;
    1368                 :      39375 :   timer_start(&ti);
    1369                 :      39375 :   XP = F2xq_sqr(polx_F2x(T[1]),T);
    1370                 :      39375 :   Q  = F2xq_matrix_pow(XP,N,N,T);
    1371         [ +  + ]:     311115 :   for (j=1; j<=N; j++)
    1372                 :     271740 :     F2m_flip(Q,j,j);
    1373         [ -  + ]:      39375 :   if(DEBUGLEVEL>=9) timer_printf(&ti,"Berlekamp matrix");
    1374                 :      39375 :   F2v_add_inplace(gel(Q,1),a);
    1375                 :      39375 :   Q = F2m_ker_sp(Q,0);
    1376         [ -  + ]:      39375 :   if(DEBUGLEVEL>=9) timer_printf(&ti,"kernel");
    1377         [ -  + ]:      39375 :   if (lg(Q)!=2) return NULL;
    1378                 :      39375 :   Q = gel(Q,1);
    1379                 :      39375 :   Q[1] = T[1];
    1380                 :      39375 :   return gerepileuptoleaf(ltop, F2x_renormalize(Q, lg(Q)));
    1381                 :            : }
    1382                 :            : 
    1383                 :            : GEN
    1384                 :      41037 : F2xq_sqrt_fast(GEN c, GEN sqx, GEN T)
    1385                 :            : {
    1386                 :            :   GEN c0, c1;
    1387                 :      41037 :   F2x_even_odd(c, &c0, &c1);
    1388                 :      41042 :   return F2x_add(c0, F2xq_mul(c1, sqx, T));
    1389                 :            : }
    1390                 :            : 
    1391                 :            : static int
    1392 [ +  + ][ +  + ]:      15220 : F2x_is_x(GEN a) { return lg(a)==3 && a[2]==2; }
    1393                 :            : 
    1394                 :            : GEN
    1395                 :      29563 : F2xq_sqrt(GEN a, GEN T)
    1396                 :            : {
    1397                 :      29563 :   pari_sp av = avma;
    1398                 :      29563 :   long n = F2x_degree(T);
    1399                 :            :   GEN sqx;
    1400         [ +  + ]:      29562 :   if (n==1) return F2x_copy(a);
    1401         [ +  + ]:      29520 :   if (n==2) return F2xq_sqr(a,T);
    1402                 :      15219 :   sqx = F2xq_autpow(mkF2(4, T[1]), n-1, T);
    1403         [ +  + ]:      29563 :   return gerepileuptoleaf(av, F2x_is_x(a)? sqx: F2xq_sqrt_fast(a,sqx,T));
    1404                 :            : }
    1405                 :            : 
    1406                 :            : GEN
    1407                 :        868 : F2xq_sqrtn(GEN a, GEN n, GEN T, GEN *zeta)
    1408                 :            : {
    1409         [ +  + ]:        868 :   if (!lgpol(a))
    1410                 :            :   {
    1411         [ +  - ]:          7 :     if (signe(n) < 0) pari_err_INV("F2xq_sqrtn",a);
    1412         [ #  # ]:          0 :     if (zeta)
    1413                 :          0 :       *zeta=pol1_F2x(T[1]);
    1414                 :          0 :     return pol0_F2x(T[1]);
    1415                 :            :   }
    1416                 :        861 :   return gen_Shanks_sqrtn(a,n,addis(powuu(2,F2x_degree(T)),-1),zeta,(void*)T,&F2xq_star);
    1417                 :            : }
    1418                 :            : 
    1419                 :            : GEN
    1420                 :         84 : gener_F2xq(GEN T, GEN *po)
    1421                 :            : {
    1422                 :         84 :   long i, j, vT = T[1], f = F2x_degree(T);
    1423                 :         84 :   pari_sp av0 = avma, av;
    1424                 :            :   GEN g, L2, o, q;
    1425                 :            : 
    1426         [ +  + ]:         84 :   if (f == 1) {
    1427         [ +  + ]:         14 :     if (po) *po = mkvec2(gen_1, trivial_fact());
    1428                 :         14 :     return pol1_F2x(vT);
    1429                 :            :   }
    1430                 :         70 :   q = subis(powuu(2,f), 1);
    1431                 :         70 :   o = factor_pn_1(gen_2,f);
    1432                 :         70 :   L2 = leafcopy( gel(o, 1) );
    1433         [ +  + ]:        203 :   for (i = j = 1; i < lg(L2); i++)
    1434                 :            :   {
    1435         [ -  + ]:        133 :     if (equaliu(gel(L2,i),2)) continue;
    1436                 :        133 :     gel(L2,j++) = diviiexact(q, gel(L2,i));
    1437                 :            :   }
    1438                 :         70 :   setlg(L2, j);
    1439                 :         70 :   for (av = avma;; avma = av)
    1440                 :            :   {
    1441                 :        105 :     g = random_F2x(f, vT);
    1442         [ +  + ]:        105 :     if (F2x_degree(g) < 1) continue;
    1443         [ +  + ]:        210 :     for (i = 1; i < j; i++)
    1444                 :            :     {
    1445                 :        140 :       GEN a = F2xq_pow(g, gel(L2,i), T);
    1446         [ +  + ]:        140 :       if (F2x_equal1(a)) break;
    1447                 :            :     }
    1448         [ +  + ]:         77 :     if (i == j) break;
    1449                 :         35 :   }
    1450         [ +  - ]:         70 :   if (!po) g = gerepilecopy(av0, g);
    1451                 :            :   else {
    1452                 :          0 :     *po = mkvec2(subis(int2n(f), 1), o);
    1453                 :          0 :     gerepileall(av0, 2, &g, po);
    1454                 :            :   }
    1455                 :         84 :   return g;
    1456                 :            : }
    1457                 :            : 
    1458                 :            : static GEN
    1459                 :        161 : _F2xq_neg(void *E, GEN x)
    1460                 :        161 : { (void) E; return F2x_copy(x); }
    1461                 :            : 
    1462                 :            : static GEN
    1463                 :        728 : _F2xq_rmul(void *E, GEN x, GEN y)
    1464                 :        728 : { (void) E; return F2x_mul(x,y); }
    1465                 :            : 
    1466                 :            : static GEN
    1467                 :         91 : _F2xq_inv(void *E, GEN x)
    1468                 :         91 : { return F2xq_inv(x, (GEN) E); }
    1469                 :            : 
    1470                 :            : static int
    1471                 :        182 : _F2xq_equal0(GEN x) { return lgpol(x)==0; }
    1472                 :            : 
    1473                 :            : static GEN
    1474                 :        119 : _F2xq_s(void *E, long x)
    1475                 :        119 : { GEN T = (GEN) E;
    1476         [ +  + ]:        119 :   return odd(x)? pol1_F2x(T[1]): pol0_F2x(T[0]);
    1477                 :            : }
    1478                 :            : 
    1479                 :            : static const struct bb_field F2xq_field={_F2xq_red,_F2xq_add,_F2xq_rmul,_F2xq_neg,
    1480                 :            :                                          _F2xq_inv,_F2xq_equal0,_F2xq_s};
    1481                 :            : 
    1482                 :         70 : const struct bb_field *get_F2xq_field(void **E, GEN T)
    1483                 :            : {
    1484                 :         70 :   *E = (void *) T;
    1485                 :         70 :   return &F2xq_field;
    1486                 :            : }
    1487                 :            : 
    1488                 :            : /***********************************************************************/
    1489                 :            : /**                                                                   **/
    1490                 :            : /**                             F2v                                   **/
    1491                 :            : /**                                                                   **/
    1492                 :            : /***********************************************************************/
    1493                 :            : /* F2v objects are defined as follows:
    1494                 :            :    An F2v is a t_VECSMALL:
    1495                 :            :    v[0] = codeword
    1496                 :            :    v[1] = number of components
    1497                 :            :    x[2] = a_0...a_31 x[3] = a_32..a_63, etc.  on 32bit
    1498                 :            :    x[2] = a_0...a_63 x[3] = a_64..a_127, etc. on 64bit
    1499                 :            : 
    1500                 :            :    where the a_i are bits.
    1501                 :            : */
    1502                 :            : 
    1503                 :            : GEN
    1504                 :    1024701 : F2c_to_ZC(GEN x)
    1505                 :            : {
    1506                 :    1024701 :   long l=x[1]+1;
    1507                 :    1024701 :   GEN  z = cgetg(l, t_COL);
    1508                 :            :   long i,j,k;
    1509         [ +  + ]:    2052016 :   for (i=2,k=1; i<lg(x); i++)
    1510 [ +  + ][ +  + ]:    8601138 :     for (j=0; j<BITS_IN_LONG && k<l; j++,k++)
    1511         [ +  + ]:    7573823 :       gel(z,k) = (x[i]&(1UL<<j))? gen_1: gen_0;
    1512                 :    1024701 :   return z;
    1513                 :            : }
    1514                 :            : GEN
    1515                 :       3045 : F2c_to_mod(GEN x)
    1516                 :            : {
    1517                 :       3045 :   long l=x[1]+1;
    1518                 :       3045 :   GEN  z = cgetg(l, t_COL);
    1519                 :       3045 :   GEN _0 = mkintmod(gen_0,gen_2);
    1520                 :       3045 :   GEN _1 = mkintmod(gen_1,gen_2);
    1521                 :            :   long i,j,k;
    1522         [ +  + ]:      15690 :   for (i=2,k=1; i<lg(x); i++)
    1523 [ +  + ][ +  + ]:     573289 :     for (j=0; j<BITS_IN_LONG && k<l; j++,k++)
    1524         [ +  + ]:     560644 :       gel(z,k) = (x[i]&(1UL<<j))? _1: _0;
    1525                 :       3045 :   return z;
    1526                 :            : }
    1527                 :            : 
    1528                 :            : /* x[a..b], a <= b */
    1529                 :            : GEN
    1530                 :         28 : F2v_slice(GEN x, long a, long b)
    1531                 :            : {
    1532                 :         28 :   long i,j,k, l = b-a+1;
    1533                 :         28 :   GEN z = cgetg(nbits2lg(l), t_VECSMALL);
    1534                 :         28 :   z[1] = l;
    1535         [ +  + ]:         98 :   for(i=a,k=1,j=BITS_IN_LONG; i<=b; i++,j++)
    1536                 :            :   {
    1537         [ +  + ]:         70 :     if (j==BITS_IN_LONG) { j=0; z[++k]=0; }
    1538         [ +  + ]:         70 :     if (F2v_coeff(x,i)) z[k] |= 1UL<<j;
    1539                 :            :   }
    1540                 :         28 :   return z;
    1541                 :            : }
    1542                 :            : /* x[a..b,], a <= b */
    1543                 :            : GEN
    1544                 :         14 : F2m_rowslice(GEN x, long a, long b)
    1545                 :            : {
    1546                 :            :   long i, l;
    1547                 :         14 :   GEN y = cgetg_copy(x, &l);
    1548         [ +  + ]:         42 :   for (i = 1; i < l; i++) gel(y,i) = F2v_slice(gel(x,i),a,b);
    1549                 :         14 :   return y;
    1550                 :            : }
    1551                 :            : 
    1552                 :            : GEN
    1553                 :     201266 : F2m_to_ZM(GEN z)
    1554                 :            : {
    1555                 :     201266 :   long i, l = lg(z);
    1556                 :     201266 :   GEN x = cgetg(l,t_MAT);
    1557         [ +  + ]:    1204290 :   for (i=1; i<l; i++) gel(x,i) = F2c_to_ZC(gel(z,i));
    1558                 :     201266 :   return x;
    1559                 :            : }
    1560                 :            : GEN
    1561                 :        112 : F2m_to_mod(GEN z)
    1562                 :            : {
    1563                 :        112 :   long i, l = lg(z);
    1564                 :        112 :   GEN x = cgetg(l,t_MAT);
    1565         [ +  + ]:       3143 :   for (i=1; i<l; i++) gel(x,i) = F2c_to_mod(gel(z,i));
    1566                 :        112 :   return x;
    1567                 :            : }
    1568                 :            : 
    1569                 :            : GEN
    1570                 :       3682 : F2v_to_Flv(GEN x)
    1571                 :            : {
    1572                 :       3682 :   long l=x[1]+1;
    1573                 :       3682 :   GEN  z=cgetg(l, t_VECSMALL);
    1574                 :            :   long i,j,k;
    1575         [ +  + ]:       7496 :   for (i=2,k=1; i<lg(x); i++)
    1576 [ +  + ][ +  + ]:      68228 :     for (j=0; j<BITS_IN_LONG && k<l; j++,k++)
    1577                 :      64414 :       z[k] = (x[i]>>j)&1UL;
    1578                 :       3682 :   return z;
    1579                 :            : }
    1580                 :            : 
    1581                 :            : GEN
    1582                 :       1386 : F2m_to_Flm(GEN z)
    1583                 :            : {
    1584                 :       1386 :   long i, l = lg(z);
    1585                 :       1386 :   GEN x = cgetg(l,t_MAT);
    1586         [ +  + ]:       5068 :   for (i=1; i<l; i++) gel(x,i) = F2v_to_Flv(gel(z,i));
    1587                 :       1386 :   return x;
    1588                 :            : }
    1589                 :            : 
    1590                 :            : GEN
    1591                 :    2169217 : ZV_to_F2v(GEN x)
    1592                 :            : {
    1593                 :    2169217 :   long l = lg(x)-1;
    1594                 :    2169217 :   GEN z = cgetg(nbits2lg(l), t_VECSMALL);
    1595                 :            :   long i,j,k;
    1596                 :    2169217 :   z[1] = l;
    1597         [ +  + ]:   22031960 :   for(i=1,k=1,j=BITS_IN_LONG; i<=l; i++,j++)
    1598                 :            :   {
    1599         [ +  + ]:   19862743 :     if (j==BITS_IN_LONG) { j=0; z[++k]=0; }
    1600         [ +  + ]:   19862743 :     if (mpodd(gel(x,i))) z[k] |= 1UL<<j;
    1601                 :            :   }
    1602                 :    2169217 :   return z;
    1603                 :            : }
    1604                 :            : 
    1605                 :            : GEN
    1606                 :       7686 : RgV_to_F2v(GEN x)
    1607                 :            : {
    1608                 :       7686 :   long l = lg(x)-1;
    1609                 :       7686 :   GEN z = cgetg(nbits2lg(l), t_VECSMALL);
    1610                 :            :   long i,j,k;
    1611                 :       7686 :   z[1] = l;
    1612         [ +  + ]:    1409758 :   for(i=1,k=1,j=BITS_IN_LONG; i<=l; i++,j++)
    1613                 :            :   {
    1614         [ +  + ]:    1402072 :     if (j==BITS_IN_LONG) { j=0; z[++k]=0; }
    1615         [ +  + ]:    1402072 :     if (Rg_to_F2(gel(x,i))) z[k] |= 1UL<<j;
    1616                 :            :   }
    1617                 :       7686 :   return z;
    1618                 :            : }
    1619                 :            : 
    1620                 :            : GEN
    1621                 :       6496 : Flv_to_F2v(GEN x)
    1622                 :            : {
    1623                 :       6496 :   long l = lg(x)-1;
    1624                 :       6496 :   GEN z = cgetg(nbits2lg(l), t_VECSMALL);
    1625                 :            :   long i,j,k;
    1626                 :       6496 :   z[1] = l;
    1627         [ +  + ]:     132006 :   for(i=1,k=1,j=BITS_IN_LONG; i<=l; i++,j++)
    1628                 :            :   {
    1629         [ +  + ]:     125510 :     if (j==BITS_IN_LONG) { j=0; z[++k]=0; }
    1630         [ +  + ]:     125510 :     if (x[i]&1L) z[k] |= 1UL<<j;
    1631                 :            :   }
    1632                 :       6496 :   return z;
    1633                 :            : }
    1634                 :            : 
    1635                 :            : GEN
    1636                 :     392508 : ZM_to_F2m(GEN x)
    1637                 :            : {
    1638                 :     392508 :   long j, l = lg(x);
    1639                 :     392508 :   GEN y = cgetg(l,t_MAT);
    1640         [ -  + ]:     392508 :   if (l == 1) return y;
    1641         [ +  + ]:    2561725 :   for (j=1; j<l; j++) gel(y,j) = ZV_to_F2v(gel(x,j));
    1642                 :     392508 :   return y;
    1643                 :            : }
    1644                 :            : 
    1645                 :            : GEN
    1646                 :        287 : RgM_to_F2m(GEN x)
    1647                 :            : {
    1648                 :        287 :   long j, l = lg(x);
    1649                 :        287 :   GEN y = cgetg(l,t_MAT);
    1650         [ -  + ]:        287 :   if (l == 1) return y;
    1651         [ +  + ]:       7952 :   for (j=1; j<l; j++) gel(y,j) = RgV_to_F2v(gel(x,j));
    1652                 :        287 :   return y;
    1653                 :            : }
    1654                 :            : 
    1655                 :            : GEN
    1656                 :       1386 : Flm_to_F2m(GEN x)
    1657                 :            : {
    1658                 :       1386 :   long j, l = lg(x);
    1659                 :       1386 :   GEN y = cgetg(l,t_MAT);
    1660         [ -  + ]:       1386 :   if (l == 1) return y;
    1661         [ +  + ]:       7868 :   for (j=1; j<l; j++) gel(y,j) = Flv_to_F2v(gel(x,j));
    1662                 :       1386 :   return y;
    1663                 :            : }
    1664                 :            : 
    1665                 :            : GEN
    1666                 :     152729 : const_F2v(long m)
    1667                 :            : {
    1668                 :     152729 :   long i, l = nbits2lg(m);
    1669                 :     152729 :   GEN c = cgetg(l, t_VECSMALL);
    1670         [ +  + ]:     460950 :   for (i = 2; i <= l; i++) c[i] = -1;
    1671         [ +  + ]:     152729 :   if (remsBIL(m)) c[l] = (1UL<<remsBIL(m))-1UL;
    1672                 :     152729 :   return c;
    1673                 :            : }
    1674                 :            : 
    1675                 :            : /* Allow lg(y)<lg(x) */
    1676                 :            : void
    1677                 :   28421428 : F2v_add_inplace(GEN x, GEN y)
    1678                 :            : {
    1679                 :   28421428 :   long n = lg(y);
    1680                 :   28421428 :   long r = (n-2)&7L, q = n-r, i;
    1681         [ +  + ]:  117140240 :   for (i = 2; i < q; i += 8)
    1682                 :            :   {
    1683                 :   88718812 :     x[  i] ^= y[  i]; x[1+i] ^= y[1+i]; x[2+i] ^= y[2+i]; x[3+i] ^= y[3+i];
    1684                 :   88718812 :     x[4+i] ^= y[4+i]; x[5+i] ^= y[5+i]; x[6+i] ^= y[6+i]; x[7+i] ^= y[7+i];
    1685                 :            :   }
    1686   [ +  +  +  +  :   28421428 :   switch (r)
             +  +  +  + ]
    1687                 :            :   {
    1688                 :   13842877 :     case 7: x[i] ^= y[i]; i++; case 6: x[i] ^= y[i]; i++;
    1689                 :   17381111 :     case 5: x[i] ^= y[i]; i++; case 4: x[i] ^= y[i]; i++;
    1690                 :   19872570 :     case 3: x[i] ^= y[i]; i++; case 2: x[i] ^= y[i]; i++;
    1691                 :   23236570 :     case 1: x[i] ^= y[i]; i++;
    1692                 :            :   }
    1693                 :   28421428 : }
    1694                 :            : 
    1695                 :            : /***********************************************************************/
    1696                 :            : /**                                                                   **/
    1697                 :            : /**                               F2xV                                **/
    1698                 :            : /**                                                                   **/
    1699                 :            : /***********************************************************************/
    1700                 :            : /* F2xV are t_VEC with F2x coefficients. */
    1701                 :            : 
    1702                 :            : GEN
    1703                 :      14091 : FlxC_to_F2xC(GEN x)
    1704                 :            : {
    1705                 :      14091 :   long i, l=lg(x);
    1706                 :      14091 :   GEN z = cgetg(l,t_COL);
    1707         [ +  + ]:      30597 :   for (i=1; i<l ; i++) gel(z,i) = Flx_to_F2x(gel(x,i));
    1708                 :      14091 :   return z;
    1709                 :            : }
    1710                 :            : 
    1711                 :            : GEN
    1712                 :          0 : F2xC_to_FlxC(GEN x)
    1713                 :            : {
    1714                 :          0 :   long i, l=lg(x);
    1715                 :          0 :   GEN z = cgetg(l,t_COL);
    1716         [ #  # ]:          0 :   for (i=1; i<l ; i++) gel(z,i) = F2x_to_Flx(gel(x,i));
    1717                 :          0 :   return z;
    1718                 :            : }
    1719                 :            : 
    1720                 :            : GEN
    1721                 :       2597 : F2xC_to_ZXC(GEN v)
    1722                 :            : {
    1723                 :       2597 :   long j, N = lg(v);
    1724                 :       2597 :   GEN y = cgetg(N, t_COL);
    1725         [ +  + ]:       5495 :   for (j=1; j<N; j++) gel(y,j) = F2x_to_ZX(gel(v,j));
    1726                 :       2597 :   return y;
    1727                 :            : }
    1728                 :            : 
    1729                 :            : GEN
    1730                 :      60200 : F2xV_to_F2m(GEN v, long n)
    1731                 :            : {
    1732                 :      60200 :   long j, N = lg(v);
    1733                 :      60200 :   GEN y = cgetg(N, t_MAT);
    1734         [ +  + ]:     418999 :   for (j=1; j<N; j++) gel(y,j) = F2x_to_F2v(gel(v,j), n);
    1735                 :      60200 :   return y;
    1736                 :            : }
    1737                 :            : 
    1738                 :            : /***********************************************************************/
    1739                 :            : /**                                                                   **/
    1740                 :            : /**                             F2xX                                  **/
    1741                 :            : /**                                                                   **/
    1742                 :            : /***********************************************************************/
    1743                 :            : 
    1744                 :            : GEN
    1745                 :    1725213 : F2xX_renormalize(GEN /*in place*/ x, long lx)
    1746                 :    1725213 : { return FlxX_renormalize(x, lx); }
    1747                 :            : 
    1748                 :            : GEN
    1749                 :     319662 : pol1_F2xX(long v, long sv) { return pol1_FlxX(v, sv); }
    1750                 :            : 
    1751                 :            : GEN
    1752                 :          0 : polx_F2xX(long v, long sv) { return polx_FlxX(v, sv); }
    1753                 :            : 
    1754                 :            : long
    1755                 :     161147 : F2xY_degreex(GEN b)
    1756                 :            : {
    1757                 :     161147 :   long deg = 0, i;
    1758         [ -  + ]:     161147 :   if (!signe(b)) return -1;
    1759         [ +  + ]:    1102591 :   for (i = 2; i < lg(b); ++i)
    1760                 :     941444 :     deg = maxss(deg, F2x_degree(gel(b, i)));
    1761                 :     161147 :   return deg;
    1762                 :            : }
    1763                 :            : 
    1764                 :            : GEN
    1765                 :          0 : FlxX_to_F2xX(GEN B)
    1766                 :            : {
    1767                 :          0 :   long lb=lg(B);
    1768                 :            :   long i;
    1769                 :          0 :   GEN b=cgetg(lb,t_POL);
    1770                 :          0 :   b[1]=evalsigne(1)|(((ulong)B[1])&VARNBITS);
    1771         [ #  # ]:          0 :   for (i=2; i<lb; i++)
    1772                 :          0 :     gel(b,i) = Flx_to_F2x(gel(B,i));
    1773                 :          0 :   return F2xX_renormalize(b, lb);
    1774                 :            : }
    1775                 :            : 
    1776                 :            : GEN
    1777                 :       2597 : ZXX_to_F2xX(GEN B, long v)
    1778                 :            : {
    1779                 :       2597 :   long lb=lg(B);
    1780                 :            :   long i;
    1781                 :       2597 :   GEN b=cgetg(lb,t_POL);
    1782                 :       2597 :   b[1]=evalsigne(1)|(((ulong)B[1])&VARNBITS);
    1783         [ +  + ]:      11326 :   for (i=2; i<lb; i++)
    1784      [ +  +  - ]:       8729 :     switch (typ(gel(B,i)))
    1785                 :            :     {
    1786                 :            :     case t_INT:
    1787                 :        133 :       gel(b,i) = Z_to_F2x(gel(B,i), v);
    1788                 :        133 :       break;
    1789                 :            :     case t_POL:
    1790                 :       8596 :       gel(b,i) = ZX_to_F2x(gel(B,i));
    1791                 :       8596 :       break;
    1792                 :            :     }
    1793                 :       2597 :   return F2xX_renormalize(b, lb);
    1794                 :            : }
    1795                 :            : 
    1796                 :            : GEN
    1797                 :          0 : F2xX_to_ZXX(GEN B)
    1798                 :            : {
    1799                 :          0 :   long i, lb = lg(B);
    1800                 :          0 :   GEN b = cgetg(lb,t_POL);
    1801         [ #  # ]:          0 :   for (i=2; i<lb; i++)
    1802                 :            :   {
    1803                 :          0 :     GEN c = gel(B,i);
    1804 [ #  # ][ #  # ]:          0 :     gel(b,i) = lgpol(c) ?  F2x_equal1(c) ? gen_1 : F2x_to_ZX(c) : gen_0;
    1805                 :            :   }
    1806                 :          0 :   b[1] = B[1]; return b;
    1807                 :            : }
    1808                 :            : 
    1809                 :            : GEN
    1810                 :      66080 : F2xX_deriv(GEN z)
    1811                 :            : {
    1812                 :      66080 :   long i,l = lg(z)-1;
    1813                 :            :   GEN x;
    1814         [ -  + ]:      66080 :   if (l < 2) l = 2;
    1815                 :      66080 :   x = cgetg(l, t_POL); x[1] = z[1];
    1816 [ +  + ][ +  + ]:     447657 :   for (i=2; i<l; i++) gel(x,i) = odd(i) ? pol0_F2x(mael(z,i+1,1)): gel(z,i+1);
    1817                 :      66080 :   return F2xX_renormalize(x,l);
    1818                 :            : }
    1819                 :            : 
    1820                 :            : GEN
    1821                 :     290479 : F2xX_add(GEN x, GEN y)
    1822                 :            : {
    1823                 :            :   long i,lz;
    1824                 :            :   GEN z;
    1825                 :     290479 :   long lx=lg(x);
    1826                 :     290479 :   long ly=lg(y);
    1827         [ +  + ]:     290479 :   if (ly>lx) swapspec(x,y, lx,ly);
    1828                 :     290479 :   lz = lx; z = cgetg(lz, t_POL); z[1]=x[1];
    1829         [ +  + ]:     431333 :   for (i=2; i<ly; i++) gel(z,i) = F2x_add(gel(x,i), gel(y,i));
    1830         [ +  + ]:    1212148 :   for (   ; i<lx; i++) gel(z,i) = F2x_copy(gel(x,i));
    1831                 :     290479 :   return F2xX_renormalize(z, lz);
    1832                 :            : }
    1833                 :            : 
    1834                 :            : GEN
    1835                 :     321804 : F2xX_F2x_mul(GEN P, GEN U)
    1836                 :            : {
    1837                 :     321804 :   long i, lP = lg(P);
    1838                 :     321804 :   GEN res = cgetg(lP,t_POL);
    1839                 :     321804 :   res[1] = P[1];
    1840         [ +  + ]:     988302 :   for(i=2; i<lP; i++)
    1841                 :     666498 :     gel(res,i) = F2x_mul(U,gel(P,i));
    1842                 :     321804 :   return F2xX_renormalize(res, lP);
    1843                 :            : }
    1844                 :            : 
    1845                 :            : GEN
    1846                 :      90524 : F2xY_F2xqV_evalx(GEN P, GEN x, GEN T)
    1847                 :            : {
    1848                 :      90524 :   long i, lP = lg(P);
    1849                 :      90524 :   GEN res = cgetg(lP,t_POL);
    1850                 :      90524 :   res[1] = P[1];
    1851         [ +  + ]:     412328 :   for(i=2; i<lP; i++)
    1852                 :     321804 :     gel(res,i) = F2x_F2xqV_eval(gel(P,i), x, T);
    1853                 :      90524 :   return F2xX_renormalize(res, lP);
    1854                 :            : }
    1855                 :            : 
    1856                 :            : GEN
    1857                 :          0 : F2xY_F2xq_evalx(GEN P, GEN x, GEN T)
    1858                 :            : {
    1859                 :          0 :   pari_sp av = avma;
    1860                 :          0 :   long n = brent_kung_optpow(F2x_degree(T)-1,lgpol(P),1);
    1861                 :          0 :   GEN xp = F2xq_powers(x, n, T);
    1862                 :          0 :   return gerepileupto(av, F2xY_F2xqV_evalx(P, xp, T));
    1863                 :            : }
    1864                 :            : 
    1865                 :            : GEN
    1866                 :     169470 : F2xX_to_Kronecker(GEN P, long d)
    1867                 :            : {
    1868                 :     169470 :   long i, k, N = 2*d + 1;
    1869                 :     169470 :   long dP = degpol(P);
    1870                 :     169470 :   long l = nbits2nlong(N*dP+d+1);
    1871                 :     169470 :   GEN x = zero_zv(l+1);
    1872         [ +  + ]:     779758 :   for (k=i=0; i<=dP; i++, k+=N)
    1873                 :            :   {
    1874                 :     610288 :     GEN c = gel(P,i+2);
    1875                 :     610288 :     F2x_addshiftip(x, c, k);
    1876                 :            :   }
    1877                 :     169470 :   x[1] = P[1]&VARNBITS; return F2x_renormalize(x, l+2);
    1878                 :            : }
    1879                 :            : 
    1880                 :            : static GEN
    1881                 :     525553 : F2x_slice(GEN x, long n, long d)
    1882                 :            : {
    1883                 :     525553 :   ulong ib, il=dvmduBIL(n, &ib);
    1884                 :     525553 :   ulong db, dl=dvmduBIL(d, &db);
    1885         [ +  - ]:     525553 :   long lN = dl+2+(db?1:0);
    1886                 :     525553 :   GEN t = cgetg(lN,t_VECSMALL);
    1887                 :     525553 :   t[1] = x[1];
    1888         [ +  + ]:     525553 :   if (ib)
    1889                 :            :   {
    1890                 :     440818 :     ulong i, ic = BITS_IN_LONG-ib;
    1891                 :     440818 :     ulong r = uel(x,2+il)>>ib;
    1892         [ -  + ]:     440818 :     for(i=0; i<dl; i++)
    1893                 :            :     {
    1894                 :          0 :       uel(t,2+i) = (uel(x,3+il+i)<<ic)|r;
    1895                 :          0 :       r = uel(x,3+il+i)>>ib;
    1896                 :            :     }
    1897         [ +  - ]:     440818 :     if (db)
    1898                 :     440818 :       uel(t,2+i) = (uel(x,3+il+i)<<ic)|r;
    1899                 :            :   }
    1900                 :            :   else
    1901                 :            :   {
    1902                 :            :     long i;
    1903         [ +  + ]:     169470 :     for(i=2; i<lN; i++)
    1904                 :      84735 :       uel(t,i) = uel(x,il+i);
    1905                 :            :   }
    1906         [ +  - ]:     525553 :   if (db) uel(t,lN-1) &= (1UL<<db)-1;
    1907                 :     525553 :   return F2x_renormalize(t, lN);
    1908                 :            : }
    1909                 :            : 
    1910                 :            : GEN
    1911                 :      84735 : Kronecker_to_F2xqX(GEN z, GEN T)
    1912                 :            : {
    1913                 :      84735 :   long lz = F2x_degree(z)+1;
    1914                 :      84735 :   long i, j, N = F2x_degree(T)*2 + 1;
    1915                 :      84735 :   long lx = lz / (N-2);
    1916                 :      84735 :   GEN x = cgetg(lx+3,t_POL);
    1917                 :      84735 :   x[1] = z[1];
    1918         [ +  + ]:     610288 :   for (i=0, j=2; i<lz; i+=N, j++)
    1919                 :            :   {
    1920                 :     525553 :     GEN t = F2x_slice(z,i,minss(lz-i,N));
    1921                 :     525553 :     t[1] = T[1];
    1922                 :     525553 :     gel(x,j) = F2x_rem(t, T);
    1923                 :            :   }
    1924                 :      84735 :   return F2xX_renormalize(x, j);
    1925                 :            : }
    1926                 :            : 
    1927                 :            : /***********************************************************************/
    1928                 :            : /**                                                                   **/
    1929                 :            : /**                             F2xqX                                 **/
    1930                 :            : /**                                                                   **/
    1931                 :            : /***********************************************************************/
    1932                 :            : 
    1933                 :            : GEN
    1934                 :       1624 : random_F2xqX(long d1, long v, GEN T)
    1935                 :            : {
    1936                 :       1624 :   long dT = F2x_degree(T), vT = T[1];
    1937                 :       1624 :   long i, d = d1+2;
    1938                 :       1624 :   GEN y = cgetg(d,t_POL); y[1] = evalsigne(1) | evalvarn(v);
    1939         [ +  + ]:       6643 :   for (i=2; i<d; i++) gel(y,i) = random_F2x(dT, vT);
    1940                 :       1624 :   return FlxX_renormalize(y,d);
    1941                 :            : }
    1942                 :            : 
    1943                 :            : GEN
    1944                 :     576142 : F2xqX_red(GEN z, GEN T)
    1945                 :            : {
    1946                 :            :   GEN res;
    1947                 :     576142 :   long i, l = lg(z);
    1948                 :     576142 :   res = cgetg(l,t_POL); res[1] = z[1];
    1949         [ +  + ]:    2698066 :   for(i=2;i<l;i++) gel(res,i) = F2x_rem(gel(z,i),T);
    1950                 :     576142 :   return F2xX_renormalize(res,l);
    1951                 :            : }
    1952                 :            : 
    1953                 :            : GEN
    1954                 :      86618 : F2xqX_F2xq_mul(GEN P, GEN U, GEN T)
    1955                 :            : {
    1956                 :      86618 :   long i, lP = lg(P);
    1957                 :      86618 :   GEN res = cgetg(lP,t_POL);
    1958                 :      86618 :   res[1] = P[1];
    1959         [ +  + ]:     645428 :   for(i=2; i<lP; i++)
    1960                 :     558810 :     gel(res,i) = F2xq_mul(U,gel(P,i), T);
    1961                 :      86618 :   return F2xX_renormalize(res, lP);
    1962                 :            : }
    1963                 :            : 
    1964                 :            : GEN
    1965                 :     159922 : F2xqX_F2xq_mul_to_monic(GEN P, GEN U, GEN T)
    1966                 :            : {
    1967                 :     159922 :   long i, lP = lg(P);
    1968                 :     159922 :   GEN res = cgetg(lP,t_POL);
    1969                 :     159922 :   res[1] = P[1];
    1970         [ +  + ]:     938350 :   for(i=2; i<lP-1; i++) gel(res,i) = F2xq_mul(U,gel(P,i), T);
    1971                 :     159922 :   gel(res,lP-1) = pol1_F2x(T[1]);
    1972                 :     159922 :   return F2xX_renormalize(res, lP);
    1973                 :            : }
    1974                 :            : 
    1975                 :            : GEN
    1976                 :     159922 : F2xqX_normalize(GEN z, GEN T)
    1977                 :            : {
    1978                 :     159922 :   GEN p1 = leading_coeff(z);
    1979 [ +  - ][ +  - ]:     159922 :   if (!lgpol(z) || (!degpol(p1) && p1[1] == 1)) return z;
                 [ -  + ]
    1980                 :     159922 :   return F2xqX_F2xq_mul_to_monic(z, F2xq_inv(p1,T), T);
    1981                 :            : }
    1982                 :            : 
    1983                 :            : GEN
    1984                 :      84735 : F2xqX_mul(GEN x, GEN y, GEN T)
    1985                 :            : {
    1986                 :      84735 :   pari_sp ltop=avma;
    1987                 :            :   GEN z,kx,ky;
    1988                 :      84735 :   kx= F2xX_to_Kronecker(x, F2x_degree(T));
    1989                 :      84735 :   ky= F2xX_to_Kronecker(y, F2x_degree(T));
    1990                 :      84735 :   z = F2x_mul(ky, kx);
    1991                 :      84735 :   z = Kronecker_to_F2xqX(z,T);
    1992                 :      84735 :   return gerepileupto(ltop,z);
    1993                 :            : }
    1994                 :            : 
    1995                 :            : GEN
    1996                 :      84574 : F2xqX_sqr(GEN x, GEN T)
    1997                 :            : {
    1998                 :      84574 :   long d = degpol(x), l = 2*d+3;
    1999                 :            :   GEN z;
    2000         [ -  + ]:      84574 :   if (!signe(x)) return pol_0(varn(x));
    2001                 :      84574 :   z = cgetg(l,t_POL);
    2002                 :      84574 :   z[1] = x[1];
    2003         [ +  - ]:      84574 :   if (d > 0)
    2004                 :            :   {
    2005                 :      84574 :     GEN u = pol0_F2x(T[1]);
    2006                 :            :     long i,j;
    2007         [ +  + ]:     197400 :     for (i=2,j=2; i<d+2; i++,j+=2)
    2008                 :            :     {
    2009                 :     112826 :       gel(z, j) = F2xq_sqr(gel(x, i), T);
    2010                 :     112826 :       gel(z, j+1) = u;
    2011                 :            :     }
    2012                 :            :   }
    2013                 :      84574 :   gel(z, 2+2*d) = F2xq_sqr(gel(x, 2+d), T);
    2014                 :      84574 :   return FlxX_renormalize(z, l);
    2015                 :            : }
    2016                 :            : 
    2017                 :            : GEN
    2018                 :     640318 : F2xqX_divrem(GEN x, GEN y, GEN T, GEN *pr)
    2019                 :            : {
    2020                 :            :   long vx, dx, dy, dz, i, j, sx, lr;
    2021                 :            :   pari_sp av0, av, tetpil;
    2022                 :            :   GEN z,p1,rem,lead;
    2023                 :            : 
    2024         [ -  + ]:     640318 :   if (!signe(y)) pari_err_INV("F2xqX_divrem",y);
    2025                 :     640318 :   vx=varn(x); dy=degpol(y); dx=degpol(x);
    2026         [ -  + ]:     640318 :   if (dx < dy)
    2027                 :            :   {
    2028         [ #  # ]:          0 :     if (pr)
    2029                 :            :     {
    2030                 :          0 :       av0 = avma; x = F2xqX_red(x, T);
    2031 [ #  # ][ #  # ]:          0 :       if (pr == ONLY_DIVIDES) { avma=av0; return signe(x)? NULL: pol_0(vx); }
    2032         [ #  # ]:          0 :       if (pr == ONLY_REM) return x;
    2033                 :          0 :       *pr = x;
    2034                 :            :     }
    2035                 :          0 :     return pol_0(vx);
    2036                 :            :   }
    2037                 :     640318 :   lead = leading_term(y);
    2038         [ +  + ]:     640318 :   if (!dy) /* y is constant */
    2039                 :            :   {
    2040 [ +  + ][ +  - ]:     266413 :     if (pr && pr != ONLY_DIVIDES)
    2041                 :            :     {
    2042         [ +  - ]:     145572 :       if (pr == ONLY_REM) return pol_0(vx);
    2043                 :          0 :       *pr = pol_0(vx);
    2044                 :            :     }
    2045         [ +  + ]:     120841 :     if (F2x_equal1(lead)) return gcopy(x);
    2046                 :      86618 :     av0 = avma; x = F2xqX_F2xq_mul(x,F2xq_inv(lead,T),T);
    2047                 :      86618 :     return gerepileupto(av0,x);
    2048                 :            :   }
    2049                 :     373905 :   av0 = avma; dz = dx-dy;
    2050         [ +  + ]:     373905 :   lead = F2x_equal1(lead)? NULL: gclone(F2xq_inv(lead,T));
    2051                 :     373905 :   avma = av0;
    2052                 :     373905 :   z = cgetg(dz+3,t_POL); z[1] = x[1];
    2053                 :     373905 :   x += 2; y += 2; z += 2;
    2054                 :            : 
    2055                 :     373905 :   p1 = gel(x,dx); av = avma;
    2056         [ +  + ]:     373905 :   gel(z,dz) = lead? gerepileupto(av, F2xq_mul(p1,lead, T)): leafcopy(p1);
    2057         [ +  + ]:    1011311 :   for (i=dx-1; i>=dy; i--)
    2058                 :            :   {
    2059                 :     637406 :     av=avma; p1=gel(x,i);
    2060 [ +  + ][ +  + ]:    1554805 :     for (j=i-dy+1; j<=i && j<=dz; j++)
    2061                 :     917399 :       p1 = F2x_add(p1, F2x_mul(gel(z,j),gel(y,i-j)));
    2062         [ +  + ]:     637406 :     if (lead) p1 = F2x_mul(p1, lead);
    2063                 :     637406 :     tetpil=avma; gel(z,i-dy) = gerepile(av,tetpil,F2x_rem(p1,T));
    2064                 :            :   }
    2065 [ +  + ][ +  + ]:     373905 :   if (!pr) { if (lead) gunclone(lead); return z-2; }
    2066                 :            : 
    2067                 :     354963 :   rem = (GEN)avma; av = (pari_sp)new_chunk(dx+3);
    2068                 :     354963 :   for (sx=0; ; i--)
    2069                 :            :   {
    2070                 :     528563 :     p1 = gel(x,i);
    2071 [ +  + ][ +  + ]:    1576071 :     for (j=0; j<=i && j<=dz; j++)
    2072                 :    1047508 :       p1 = F2x_add(p1, F2x_mul(gel(z,j),gel(y,i-j)));
    2073         [ +  + ]:     528563 :     tetpil=avma; p1 = F2x_rem(p1, T); if (lgpol(p1)) { sx = 1; break; }
    2074         [ +  + ]:     219912 :     if (!i) break;
    2075                 :     173600 :     avma=av;
    2076                 :     173600 :   }
    2077         [ -  + ]:     354963 :   if (pr == ONLY_DIVIDES)
    2078                 :            :   {
    2079         [ #  # ]:          0 :     if (lead) gunclone(lead);
    2080         [ #  # ]:          0 :     if (sx) { avma=av0; return NULL; }
    2081                 :          0 :     avma = (pari_sp)rem; return z-2;
    2082                 :            :   }
    2083                 :     354963 :   lr=i+3; rem -= lr;
    2084                 :     354963 :   rem[0] = evaltyp(t_POL) | evallg(lr);
    2085                 :     354963 :   rem[1] = z[-1];
    2086                 :     354963 :   p1 = gerepile((pari_sp)rem,tetpil,p1);
    2087                 :     354963 :   rem += 2; gel(rem,i) = p1;
    2088         [ +  + ]:     965398 :   for (i--; i>=0; i--)
    2089                 :            :   {
    2090                 :     610435 :     av=avma; p1 = gel(x,i);
    2091 [ +  + ][ +  + ]:    1684032 :     for (j=0; j<=i && j<=dz; j++)
    2092                 :    1073597 :       p1 = F2x_add(p1, F2x_mul(gel(z,j),gel(y,i-j)));
    2093                 :     610435 :     tetpil=avma; gel(rem,i) = gerepile(av,tetpil, F2x_rem(p1, T));
    2094                 :            :   }
    2095                 :     354963 :   rem -= 2;
    2096         [ +  + ]:     354963 :   if (lead) gunclone(lead);
    2097         [ +  + ]:     354963 :   if (!sx) (void)F2xX_renormalize(rem, lr);
    2098         [ +  - ]:     354963 :   if (pr == ONLY_REM) return gerepileupto(av0,rem);
    2099                 :     640318 :   *pr = rem; return z-2;
    2100                 :            : }
    2101                 :            : 
    2102                 :            : GEN
    2103                 :     757281 : F2xqX_rem(GEN x, GEN S, GEN T)
    2104                 :            : {
    2105                 :     757281 :   GEN y = S;
    2106                 :     757281 :   long dy = degpol(y), dx = degpol(x), d = dx-dy;
    2107         [ +  + ]:     757281 :   if (d < 0) return F2xqX_red(x, T);
    2108                 :     757281 :   return F2xqX_divrem(x,y, T, ONLY_REM);
    2109                 :            : }
    2110                 :            : 
    2111                 :            : GEN
    2112                 :     192920 : F2xqX_gcd(GEN a, GEN b, GEN T)
    2113                 :            : {
    2114                 :     192920 :   pari_sp av = avma, av0=avma;
    2115         [ +  + ]:     779667 :   while (signe(b))
    2116                 :            :   {
    2117                 :            :     GEN c;
    2118         [ -  + ]:     586747 :     if (gc_needed(av0,2))
    2119                 :            :     {
    2120         [ #  # ]:          0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2xqX_gcd (d = %ld)",degpol(b));
    2121                 :          0 :       gerepileall(av0,2, &a,&b);
    2122                 :            :     }
    2123                 :     586747 :     av = avma; c = F2xqX_rem(a, b, T); a=b; b=c;
    2124                 :            :   }
    2125                 :     192920 :   avma = av; return a;
    2126                 :            : }
    2127                 :            : 
    2128                 :            : /***********************************************************************/
    2129                 :            : /**                                                                   **/
    2130                 :            : /**                             F2xqXQ                                **/
    2131                 :            : /**                                                                   **/
    2132                 :            : /***********************************************************************/
    2133                 :            : 
    2134                 :            : GEN
    2135                 :      84735 : F2xqXQ_mul(GEN x, GEN y, GEN S, GEN T) {
    2136                 :      84735 :   return F2xqX_rem(F2xqX_mul(x,y,T),S,T);
    2137                 :            : }
    2138                 :            : 
    2139                 :            : GEN
    2140                 :      84574 : F2xqXQ_sqr(GEN x, GEN S, GEN T) {
    2141                 :      84574 :   return F2xqX_rem(F2xqX_sqr(x,T),S,T);
    2142                 :            : }
    2143                 :            : 
    2144                 :            : struct _F2xqXQ {
    2145                 :            :   GEN T, S;
    2146                 :            : };
    2147                 :            : 
    2148                 :            : static GEN
    2149                 :     231315 : _F2xqXQ_add(void *data, GEN x, GEN y) {
    2150                 :            :   (void) data;
    2151                 :     231315 :   return F2xX_add(x,y);
    2152                 :            : }
    2153                 :            : static GEN
    2154                 :     321804 : _F2xqXQ_cmul(void *data, GEN P, long a, GEN x) {
    2155                 :            :   (void) data;
    2156                 :     321804 :   return F2xX_F2x_mul(x,gel(P,a+2));
    2157                 :            : }
    2158                 :            : static GEN
    2159                 :     259413 : _F2xqXQ_red(void *data, GEN x) {
    2160                 :     259413 :   struct _F2xqXQ *d = (struct _F2xqXQ*) data;
    2161                 :     259413 :   return F2xqX_red(x, d->T);
    2162                 :            : }
    2163                 :            : static GEN
    2164                 :      84735 : _F2xqXQ_mul(void *data, GEN x, GEN y) {
    2165                 :      84735 :   struct _F2xqXQ *d = (struct _F2xqXQ*) data;
    2166                 :      84735 :   return F2xqXQ_mul(x,y, d->S,d->T);
    2167                 :            : }
    2168                 :            : static GEN
    2169                 :      28252 : _F2xqXQ_sqr(void *data, GEN x) {
    2170                 :      28252 :   struct _F2xqXQ *d = (struct _F2xqXQ*) data;
    2171                 :      28252 :   return F2xqXQ_sqr(x, d->S,d->T);
    2172                 :            : }
    2173                 :            : static GEN
    2174                 :         35 : _F2xqXQ_zero(void *data) {
    2175                 :         35 :   struct _F2xqXQ *d = (struct _F2xqXQ*) data;
    2176                 :         35 :   return pol_0(varn(d->S));
    2177                 :            : }
    2178                 :            : static GEN
    2179                 :     262633 : _F2xqXQ_one(void *data) {
    2180                 :     262633 :   struct _F2xqXQ *d = (struct _F2xqXQ*) data;
    2181                 :     262633 :   return pol1_F2xX(varn(d->S),d->T[1]);
    2182                 :            : }
    2183                 :            : 
    2184                 :            : static struct bb_algebra F2xqXQ_algebra = { _F2xqXQ_red,_F2xqXQ_add,
    2185                 :            :         _F2xqXQ_mul,_F2xqXQ_sqr,_F2xqXQ_one,_F2xqXQ_zero };
    2186                 :            : 
    2187                 :            : GEN
    2188                 :          0 : F2xqXQ_pow(GEN x, GEN n, GEN S, GEN T)
    2189                 :            : {
    2190                 :            :   struct _F2xqXQ D;
    2191                 :          0 :   long s = signe(n);
    2192         [ #  # ]:          0 :   if (!s) return pol1_F2xX(varn(S), T[1]);
    2193         [ #  # ]:          0 :   if (s < 0) pari_err_IMPL("F2xqXQ_inv");
    2194 [ #  # ][ #  # ]:          0 :   if (is_pm1(n)) return s < 0 ? x : gcopy(x);
    2195         [ #  # ]:          0 :   if (degpol(x)>=degpol(S)) x = F2xqX_rem(x,S,T);
    2196                 :          0 :   D.S = S; D.T = T;
    2197                 :          0 :   return gen_pow(x, n, (void*)&D, &_F2xqXQ_sqr, &_F2xqXQ_mul);
    2198                 :            : }
    2199                 :            : 
    2200                 :            : GEN
    2201                 :       2842 : F2xqXQ_powers(GEN x, long l, GEN S, GEN T)
    2202                 :            : {
    2203                 :            :   struct _F2xqXQ D;
    2204                 :       2842 :   int use_sqr = 2*degpol(x) >= degpol(S);
    2205                 :       2842 :   D.S = S; D.T = T;
    2206                 :       2842 :   return gen_powers(x, l, use_sqr, (void*)&D, &_F2xqXQ_sqr, &_F2xqXQ_mul,&_F2xqXQ_one);
    2207                 :            : }
    2208                 :            : 
    2209                 :            : GEN
    2210                 :       5684 : F2xqX_F2xqXQV_eval(GEN P, GEN V, GEN S, GEN T)
    2211                 :            : {
    2212                 :            :   struct _F2xqXQ D;
    2213                 :       5684 :   D.S = S; D.T = T;
    2214                 :       5684 :   return gen_bkeval_powers(P, degpol(P), V, (void*)&D, &F2xqXQ_algebra,
    2215                 :            :                                                    _F2xqXQ_cmul);
    2216                 :            : }
    2217                 :            : 
    2218                 :            : GEN
    2219                 :      84840 : F2xqX_F2xqXQ_eval(GEN Q, GEN x, GEN S, GEN T)
    2220                 :            : {
    2221                 :            :   struct _F2xqXQ D;
    2222                 :      84840 :   int use_sqr = 2*degpol(x) >= degpol(S);
    2223                 :      84840 :   D.S = S; D.T = T;
    2224                 :      84840 :   return gen_bkeval(Q, degpol(Q), x, use_sqr, (void*)&D, &F2xqXQ_algebra,
    2225                 :            :                                                     _F2xqXQ_cmul);
    2226                 :            : }
    2227                 :            : 
    2228                 :            : static GEN
    2229                 :      56322 : F2xqXQ_autpow_sqr(void * E, GEN x)
    2230                 :            : {
    2231                 :      56322 :   struct _F2xqXQ *D = (struct _F2xqXQ *)E;
    2232                 :      56322 :   GEN T = D->T;
    2233                 :      56322 :   GEN phi = gel(x,1), S = gel(x,2);
    2234                 :      56322 :   long n = brent_kung_optpow(F2x_degree(T)-1,lgpol(S)+1,1);
    2235                 :      56322 :   GEN V = F2xq_powers(phi, n, T);
    2236                 :      56322 :   GEN phi2 = F2x_F2xqV_eval(phi, V, T);
    2237                 :      56322 :   GEN Sphi = F2xY_F2xqV_evalx(S, V, T);
    2238                 :      56322 :   GEN S2 = F2xqX_F2xqXQ_eval(Sphi, S, D->S, T);
    2239                 :      56322 :   return mkvec2(phi2, S2);
    2240                 :            : }
    2241                 :            : 
    2242                 :            : static GEN
    2243                 :      28518 : F2xqXQ_autpow_mul(void * E, GEN x, GEN y)
    2244                 :            : {
    2245                 :      28518 :   struct _F2xqXQ *D = (struct _F2xqXQ *)E;
    2246                 :      28518 :   GEN T = D->T;
    2247                 :      28518 :   GEN phi1 = gel(x,1), S1 = gel(x,2);
    2248                 :      28518 :   GEN phi2 = gel(y,1), S2 = gel(y,2);
    2249                 :      28518 :   long n = brent_kung_optpow(F2x_degree(T)-1,lgpol(S1)+1,1);
    2250                 :      28518 :   GEN V = F2xq_powers(phi2, n, T);
    2251                 :      28518 :   GEN phi3 = F2x_F2xqV_eval(phi1,V,T);
    2252                 :      28518 :   GEN Sphi = F2xY_F2xqV_evalx(S1,V,T);
    2253                 :      28518 :   GEN S3 = F2xqX_F2xqXQ_eval(Sphi, S2, D->S, T);
    2254                 :      28518 :   return mkvec2(phi3, S3);
    2255                 :            : }
    2256                 :            : 
    2257                 :            : GEN
    2258                 :      56322 : F2xqXQV_autpow(GEN aut, long n, GEN S, GEN T)
    2259                 :            : {
    2260                 :            :   struct _F2xqXQ D;
    2261                 :      56322 :   D.S = S; D.T = T;
    2262                 :      56322 :   return gen_powu(aut,n,&D,F2xqXQ_autpow_sqr,F2xqXQ_autpow_mul);
    2263                 :            : }
    2264                 :            : 
    2265                 :            : static GEN
    2266                 :       2842 : F2xqXQ_auttrace_mul(void *E, GEN x, GEN y)
    2267                 :            : {
    2268                 :       2842 :   struct _F2xqXQ *D = (struct _F2xqXQ *) E;
    2269                 :       2842 :   GEN T = D->T;
    2270                 :       2842 :   GEN phi1 = gel(x,1), S1 = gel(x,2), a1 = gel(x,3);
    2271                 :       2842 :   GEN phi2 = gel(y,1), S2 = gel(y,2), a2 = gel(y,3);
    2272                 :       2842 :   long n2 = brent_kung_optpow(F2x_degree(T)-1, lgpol(S1)+lgpol(a1)+1, 1);
    2273                 :       2842 :   GEN V2 = F2xq_powers(phi2, n2, T);
    2274                 :       2842 :   GEN phi3 = F2x_F2xqV_eval(phi1, V2, T);
    2275                 :       2842 :   GEN Sphi = F2xY_F2xqV_evalx(S1, V2, T);
    2276                 :       2842 :   GEN aphi = F2xY_F2xqV_evalx(a1, V2, T);
    2277                 :       2842 :   long n = brent_kung_optpow(maxss(degpol(Sphi),degpol(aphi)),2,1);
    2278                 :       2842 :   GEN V = F2xqXQ_powers(S2, n, D->S, T);
    2279                 :       2842 :   GEN S3 = F2xqX_F2xqXQV_eval(Sphi, V, D->S, T);
    2280                 :       2842 :   GEN aS = F2xqX_F2xqXQV_eval(aphi, V, D->S, T);
    2281                 :       2842 :   GEN a3 = F2xX_add(aS, a2);
    2282                 :       2842 :   return mkvec3(phi3, S3, a3);
    2283                 :            : }
    2284                 :            : 
    2285                 :            : static GEN
    2286                 :       1624 : F2xqXQ_auttrace_sqr(void *E, GEN x)
    2287                 :       1624 : { return F2xqXQ_auttrace_mul(E, x, x); }
    2288                 :            : 
    2289                 :            : GEN
    2290                 :       1624 : F2xqXQV_auttrace(GEN aut, long n, GEN S, GEN T)
    2291                 :            : {
    2292                 :            :   struct _F2xqXQ D;
    2293                 :       1624 :   D.S = S; D.T = T;
    2294                 :       1624 :   return gen_powu(aut,n,&D,F2xqXQ_auttrace_sqr,F2xqXQ_auttrace_mul);
    2295                 :            : }

Generated by: LCOV version 1.9