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-bordeaux1.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 17110-9967e23) Lines: 869 938 92.6 %
Date: 2014-11-26 Functions: 104 107 97.2 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 467 603 77.4 %

           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                 :   73539819 : F2x_degree_lg(GEN x, long l)
      39                 :            : {
      40 [ +  + ][ +  + ]:   73539819 :   return (l==2)?-1:bit_accuracy(l)-bfffo(x[l-1])-1;
         [ +  + ][ +  + ]
                 [ +  + ]
      41                 :            : }
      42                 :            : 
      43                 :            : long
      44                 :   16148588 : F2x_degree(GEN x)
      45                 :            : {
      46                 :   16148588 :   return F2x_degree_lg(x, lg(x));
      47                 :            : }
      48                 :            : 
      49                 :            : GEN
      50                 :      66075 : F2x_to_ZX(GEN x)
      51                 :            : {
      52                 :      66075 :   long l=3+F2x_degree(x);
      53                 :      66075 :   GEN z=cgetg(l,t_POL);
      54                 :            :   long i,j,k;
      55         [ +  + ]:     132104 :   for(i=2,k=2;i<lg(x);i++)
      56 [ +  + ][ +  + ]:     281749 :     for(j=0; j<BITS_IN_LONG && k<l; j++,k++)
      57         [ +  + ]:     215720 :       gel(z,k)=(x[i]&(1UL<<j))?gen_1:gen_0;
      58         [ +  + ]:      66075 :   z[1]=evalsigne(l>=3)|x[1];
      59                 :      66075 :   return z;
      60                 :            : }
      61                 :            : 
      62                 :            : GEN
      63                 :       1170 : F2xC_to_ZXC(GEN v)
      64                 :            : {
      65                 :       1170 :   long j, N = lg(v);
      66                 :       1170 :   GEN y = cgetg(N, t_COL);
      67         [ +  + ]:       2450 :   for (j=1; j<N; j++) gel(y,j) = F2x_to_ZX(gel(v,j));
      68                 :       1170 :   return y;
      69                 :            : }
      70                 :            : 
      71                 :            : GEN
      72                 :      11420 : F2x_to_Flx(GEN x)
      73                 :            : {
      74                 :      11420 :   long l=3+F2x_degree(x);
      75                 :      11420 :   GEN z=cgetg(l,t_VECSMALL);
      76                 :            :   long i,j,k;
      77                 :      11420 :   z[1]=x[1];
      78         [ +  + ]:      25741 :   for(i=2,k=2;i<lg(x);i++)
      79 [ +  + ][ +  + ]:     287681 :     for(j=0;j<BITS_IN_LONG && k<l; j++,k++)
      80                 :     273360 :       z[k]=(x[i]>>j)&1UL;
      81                 :      11420 :   return z;
      82                 :            : }
      83                 :            : 
      84                 :            : GEN
      85                 :       1250 : Z_to_F2x(GEN x, long v)
      86                 :            : {
      87                 :       1250 :   long sv = evalvarn(v);
      88         [ +  + ]:       1250 :   return mpodd(x) ? pol1_F2x(sv): pol0_F2x(sv);
      89                 :            : }
      90                 :            : 
      91                 :            : GEN
      92                 :       3840 : ZX_to_F2x(GEN x)
      93                 :            : {
      94                 :       3840 :   long l=nbits2lg(lgpol(x));
      95                 :       3840 :   GEN z=cgetg(l,t_VECSMALL);
      96                 :            :   long i,j,k;
      97                 :       3840 :   z[1]=((ulong)x[1])&VARNBITS;
      98         [ +  + ]:      20520 :   for(i=2, k=1,j=BITS_IN_LONG;i<lg(x);i++,j++)
      99                 :            :   {
     100         [ +  + ]:      16680 :     if (j==BITS_IN_LONG)
     101                 :            :     {
     102                 :       3336 :       j=0; k++; z[k]=0;
     103                 :            :     }
     104         [ +  + ]:      16680 :     if (mpodd(gel(x,i)))
     105                 :      10780 :       z[k]|=1UL<<j;
     106                 :            :   }
     107                 :       3840 :   return F2x_renormalize(z,l);
     108                 :            : }
     109                 :            : 
     110                 :            : GEN
     111                 :      63170 : Flx_to_F2x(GEN x)
     112                 :            : {
     113                 :      63170 :   long l=nbits2lg(lgpol(x));
     114                 :      63170 :   GEN z=cgetg(l,t_VECSMALL);
     115                 :            :   long i,j,k;
     116                 :      63170 :   z[1]=x[1];
     117         [ +  + ]:     625315 :   for(i=2, k=1,j=BITS_IN_LONG;i<lg(x);i++,j++)
     118                 :            :   {
     119         [ +  + ]:     562145 :     if (j==BITS_IN_LONG)
     120                 :            :     {
     121                 :      66370 :       j=0; k++; z[k]=0;
     122                 :            :     }
     123         [ +  + ]:     562145 :     if (x[i]&1UL)
     124                 :     272890 :       z[k]|=1UL<<j;
     125                 :            :   }
     126                 :      63170 :   return F2x_renormalize(z,l);
     127                 :            : }
     128                 :            : 
     129                 :            : GEN
     130                 :     239643 : F2x_to_F2v(GEN x, long N)
     131                 :            : {
     132                 :     239643 :   long i, l = lg(x);
     133                 :     239643 :   long n = nbits2lg(N);
     134                 :     239643 :   GEN z = cgetg(n,t_VECSMALL);
     135                 :     239643 :   z[1] = N;
     136         [ +  + ]:     518540 :   for (i=2; i<l ; i++) z[i]=x[i];
     137         [ +  + ]:     256432 :   for (   ; i<n; i++) z[i]=0;
     138                 :     239643 :   return z;
     139                 :            : }
     140                 :            : 
     141                 :            : GEN
     142                 :          0 : RgX_to_F2x(GEN x)
     143                 :            : {
     144                 :          0 :   long l=nbits2lg(lgpol(x));
     145                 :          0 :   GEN z=cgetg(l,t_VECSMALL);
     146                 :            :   long i,j,k;
     147                 :          0 :   z[1]=((ulong)x[1])&VARNBITS;
     148         [ #  # ]:          0 :   for(i=2, k=1,j=BITS_IN_LONG;i<lg(x);i++,j++)
     149                 :            :   {
     150         [ #  # ]:          0 :     if (j==BITS_IN_LONG)
     151                 :            :     {
     152                 :          0 :       j=0; k++; z[k]=0;
     153                 :            :     }
     154         [ #  # ]:          0 :     if (Rg_to_F2(gel(x,i)))
     155                 :          0 :       z[k]|=1UL<<j;
     156                 :            :   }
     157                 :          0 :   return F2x_renormalize(z,l);
     158                 :            : }
     159                 :            : 
     160                 :            : /* If x is a POLMOD, assume modulus is a multiple of T. */
     161                 :            : GEN
     162                 :      69800 : Rg_to_F2xq(GEN x, GEN T)
     163                 :            : {
     164                 :      69800 :   long ta, tx = typ(x), v = T[1];
     165                 :            :   GEN a, b;
     166         [ +  - ]:      69800 :   if (is_const_t(tx))
     167                 :            :   {
     168         [ +  + ]:      69800 :     if (tx == t_FFELT) return FF_to_F2xq(x);
     169         [ +  + ]:      17655 :     return Rg_to_F2(x)? pol1_F2x(v): pol0_F2x(v);
     170                 :            :   }
     171   [ #  #  #  # ]:          0 :   switch(tx)
     172                 :            :   {
     173                 :            :     case t_POLMOD:
     174                 :          0 :       b = gel(x,1);
     175                 :          0 :       a = gel(x,2); ta = typ(a);
     176 [ #  # ][ #  # ]:          0 :       if (is_const_t(ta)) return Rg_to_F2(a)? pol1_F2x(v): pol0_F2x(v);
     177         [ #  # ]:          0 :       b = RgX_to_F2x(b); if (b[1] != v) break;
     178         [ #  # ]:          0 :       a = RgX_to_F2x(a); if (F2x_equal(b,T)) return a;
     179                 :          0 :       return F2x_rem(a, T);
     180                 :            :     case t_POL:
     181                 :          0 :       x = RgX_to_F2x(x);
     182         [ #  # ]:          0 :       if (x[1] != v) break;
     183                 :          0 :       return F2x_rem(x, T);
     184                 :            :     case t_RFRAC:
     185                 :          0 :       a = Rg_to_F2xq(gel(x,1), T);
     186                 :          0 :       b = Rg_to_F2xq(gel(x,2), T);
     187                 :          0 :       return F2xq_div(a,b, T);
     188                 :            :   }
     189                 :          0 :   pari_err_TYPE("Rg_to_F2xq",x);
     190                 :      69800 :   return NULL; /* not reached */
     191                 :            : }
     192                 :            : 
     193                 :            : GEN
     194                 :    9053408 : F2x_add(GEN x, GEN y)
     195                 :            : {
     196                 :            :   long i,lz;
     197                 :            :   GEN z;
     198                 :    9053408 :   long lx=lg(x);
     199                 :    9053408 :   long ly=lg(y);
     200         [ +  + ]:    9053408 :   if (ly>lx) swapspec(x,y, lx,ly);
     201                 :    9053408 :   lz = lx; z = cgetg(lz, t_VECSMALL); z[1]=x[1];
     202         [ +  + ]:   27700054 :   for (i=2; i<ly; i++) z[i] = x[i]^y[i];
     203         [ +  + ]:   10182318 :   for (   ; i<lx; i++) z[i] = x[i];
     204                 :    9053408 :   return F2x_renormalize(z, lz);
     205                 :            : }
     206                 :            : 
     207                 :            : static GEN
     208                 :    7238723 : F2x_addspec(GEN x, GEN y, long lx, long ly)
     209                 :            : {
     210                 :            :   long i,lz;
     211                 :            :   GEN z;
     212                 :            : 
     213         [ +  + ]:    7238723 :   if (ly>lx) swapspec(x,y, lx,ly);
     214                 :    7238723 :   lz = lx+2; z = cgetg(lz, t_VECSMALL) + 2;
     215         [ +  + ]:   15022185 :   for (i=0; i<ly; i++) z[i] = x[i]^y[i];
     216         [ +  + ]:   11930401 :   for (   ; i<lx; i++) z[i] = x[i];
     217                 :    7238723 :   z -= 2; return F2x_renormalize(z, lz);
     218                 :            : }
     219                 :            : 
     220                 :            : GEN
     221                 :        475 : F2x_1_add(GEN y)
     222                 :            : {
     223                 :            :   GEN z;
     224                 :            :   long lz, i;
     225         [ +  + ]:        475 :   if (!lgpol(y))
     226                 :         85 :     return pol1_F2x(y[1]);
     227                 :        390 :   lz=lg(y);
     228                 :        390 :   z=cgetg(lz,t_VECSMALL);
     229                 :        390 :   z[1] = y[1];
     230                 :        390 :   z[2] = y[2]^1UL;
     231         [ -  + ]:        390 :   for(i=3;i<lz;i++)
     232                 :          0 :     z[i] = y[i];
     233         [ +  - ]:        390 :   if (lz==3) z = F2x_renormalize(z,lz);
     234                 :        475 :   return z;
     235                 :            : }
     236                 :            : 
     237                 :            : static GEN
     238                 :    9041798 : F2x_addshift(GEN x, GEN y, long d)
     239                 :            : {
     240                 :    9041798 :   GEN xd,yd,zd = (GEN)avma;
     241                 :    9041798 :   long a,lz,ny = lgpol(y), nx = lgpol(x);
     242                 :    9041798 :   long vs = x[1];
     243                 :            : 
     244                 :    9041798 :   x += 2; y += 2; a = ny-d;
     245         [ +  + ]:    9041798 :   if (a <= 0)
     246                 :            :   {
     247         [ -  + ]:    2724419 :     lz = (a>nx)? ny+2: nx+d+2;
     248                 :    2724419 :     (void)new_chunk(lz); xd = x+nx; yd = y+ny;
     249         [ +  + ]:    6780589 :     while (xd > x) *--zd = *--xd;
     250                 :    2724419 :     x = zd + a;
     251         [ +  + ]:    2724485 :     while (zd > x) *--zd = 0;
     252                 :            :   }
     253                 :            :   else
     254                 :            :   {
     255                 :    6317379 :     xd = new_chunk(d); yd = y+d;
     256                 :    6317379 :     x = F2x_addspec(x,yd,nx,a);
     257         [ -  + ]:    6317379 :     lz = (a>nx)? ny+2: lg(x)+d;
     258         [ +  + ]:   17587830 :     x += 2; while (xd > x) *--zd = *--xd;
     259                 :            :   }
     260         [ +  + ]:   21994967 :   while (yd > y) *--zd = *--yd;
     261                 :    9041798 :   *--zd = vs;
     262                 :    9041798 :   *--zd = evaltyp(t_VECSMALL) | evallg(lz); return zd;
     263                 :            : }
     264                 :            : 
     265                 :            : /* shift polynomial + gerepile */
     266                 :            : /* Do not set evalvarn. Cf Flx_shiftip */
     267                 :            : static GEN
     268                 :   24399876 : F2x_shiftip(pari_sp av, GEN x, long v)
     269                 :            : {
     270                 :   24399876 :   long i, lx = lg(x), ly;
     271                 :            :   GEN y;
     272 [ +  + ][ -  + ]:   24399876 :   if (!v || lx==2) return gerepileuptoleaf(av, x);
     273                 :       7108 :   ly = lx + v;
     274                 :       7108 :   (void)new_chunk(ly); /* check that result fits */
     275                 :       7108 :   x += lx; y = (GEN)av;
     276         [ +  + ]:      14692 :   for (i = 2; i<lx; i++) *--y = *--x;
     277         [ +  + ]:      20855 :   for (i = 0; i< v; i++) *--y = 0;
     278                 :       7108 :   y -= 2; y[0] = evaltyp(t_VECSMALL) | evallg(ly);
     279                 :   24399876 :   avma = (pari_sp)y; return y;
     280                 :            : }
     281                 :            : 
     282                 :            : static GEN
     283                 :   15818750 : F2x_mul1(ulong x, ulong y)
     284                 :            : {
     285                 :   15818750 :   ulong x1=(x&HIGHMASK)>>BITS_IN_HALFULONG;
     286                 :   15818750 :   ulong x2=x&LOWMASK;
     287                 :   15818750 :   ulong y1=(y&HIGHMASK)>>BITS_IN_HALFULONG;
     288                 :   15818750 :   ulong y2=y&LOWMASK;
     289                 :            :   ulong r1,r2,rr;
     290                 :            :   GEN z;
     291                 :            :   ulong i;
     292                 :   15818750 :   rr=r1=r2=0UL;
     293         [ +  + ]:   15818750 :   if (x2)
     294         [ +  + ]:  442474101 :     for(i=0;i<BITS_IN_HALFULONG;i++)
     295         [ +  + ]:  426662672 :       if (x2&(1UL<<i))
     296                 :            :       {
     297                 :  162213872 :         r2^=y2<<i;
     298                 :  162213872 :         rr^=y1<<i;
     299                 :            :       }
     300         [ +  + ]:   15818750 :   if (x1)
     301         [ +  + ]:  291779568 :     for(i=0;i<BITS_IN_HALFULONG;i++)
     302         [ +  + ]:  280996928 :       if (x1&(1UL<<i))
     303                 :            :       {
     304                 :  129759441 :         r1^=y1<<i;
     305                 :  129759441 :         rr^=y2<<i;
     306                 :            :       }
     307                 :   15818750 :   r2^=(rr&LOWMASK)<<BITS_IN_HALFULONG;
     308                 :   15818750 :   r1^=(rr&HIGHMASK)>>BITS_IN_HALFULONG;
     309         [ +  + ]:   15818750 :   z=cgetg((r1?4:3),t_VECSMALL);
     310                 :   15818750 :   z[2]=r2;
     311         [ +  + ]:   15818750 :   if (r1) z[3]=r1;
     312                 :   15818750 :   return z;
     313                 :            : }
     314                 :            : 
     315                 :            : /* fast product (Karatsuba) of polynomials a,b. These are not real GENs, a+2,
     316                 :            :  * b+2 were sent instead. na, nb = number of terms of a, b.
     317                 :            :  * Only c, c0, c1, c2 are genuine GEN.
     318                 :            :  */
     319                 :            : static GEN
     320                 :   24475734 : F2x_mulspec(GEN a, GEN b, long na, long nb)
     321                 :            : {
     322                 :            :   GEN a0,c,c0;
     323                 :   24475734 :   long n0, n0a, i, v = 0;
     324                 :            :   pari_sp av;
     325                 :            : 
     326 [ +  + ][ +  + ]:   24489276 :   while (na && !a[0]) { a++; na-=1; v++; }
     327 [ +  + ][ +  + ]:   24475939 :   while (nb && !b[0]) { b++; nb-=1; v++; }
     328         [ +  + ]:   24475734 :   if (na < nb) swapspec(a,b, na,nb);
     329         [ +  + ]:   24475734 :   if (!nb) return pol0_F2x(0);
     330                 :            : 
     331                 :   24399876 :   av = avma;
     332         [ +  + ]:   24399876 :   if (na <=1) return F2x_shiftip(av,F2x_mul1(*a,*b),v);
     333                 :    8581126 :   i=(na>>1); n0=na-i; na=i;
     334                 :    8581126 :   a0=a+n0; n0a=n0;
     335 [ +  - ][ -  + ]:    8581126 :   while (n0a && !a[n0a-1]) n0a--;
     336                 :            : 
     337         [ +  + ]:    8581126 :   if (nb > n0)
     338                 :            :   {
     339                 :            :     GEN b0,c1,c2;
     340                 :            :     long n0b;
     341                 :            : 
     342                 :     460672 :     nb -= n0; b0 = b+n0; n0b = n0;
     343 [ +  - ][ +  + ]:     460677 :     while (n0b && !b[n0b-1]) n0b--;
     344                 :     460672 :     c =  F2x_mulspec(a,b,n0a,n0b);
     345                 :     460672 :     c0 = F2x_mulspec(a0,b0,na,nb);
     346                 :            : 
     347                 :     460672 :     c2 = F2x_addspec(a0,a,na,n0a);
     348                 :     460672 :     c1 = F2x_addspec(b0,b,nb,n0b);
     349                 :            : 
     350                 :     460672 :     c1 = F2x_mul(c1,c2);
     351                 :     460672 :     c2 = F2x_add(c0,c);
     352                 :            : 
     353                 :     460672 :     c2 = F2x_add(c1,c2);
     354                 :     460672 :     c0 = F2x_addshift(c0,c2,n0);
     355                 :            :   }
     356                 :            :   else
     357                 :            :   {
     358                 :    8120454 :     c  = F2x_mulspec(a,b,n0a,nb);
     359                 :    8120454 :     c0 = F2x_mulspec(a0,b,na,nb);
     360                 :            :   }
     361                 :    8581126 :   c0 = F2x_addshift(c0,c,n0);
     362                 :   24475734 :   return F2x_shiftip(av,c0, v);
     363                 :            : }
     364                 :            : 
     365                 :            : GEN
     366                 :    7313482 : F2x_mul(GEN x, GEN y)
     367                 :            : {
     368                 :    7313482 :   GEN z = F2x_mulspec(x+2,y+2, lgpol(x),lgpol(y));
     369                 :    7313482 :   z[1] = x[1]; return z;
     370                 :            : }
     371                 :            : 
     372                 :            : GEN
     373                 :    1215672 : F2x_sqr(GEN x)
     374                 :            : {
     375                 :    1215672 :   const ulong sq[]={0,1,4,5,16,17,20,21,64,65,68,69,80,81,84,85};
     376                 :            :   long i,ii,j,jj;
     377                 :    1215672 :   long lx=lg(x), lz=2+((lx-2)<<1);
     378                 :            :   GEN z;
     379                 :    1215672 :   z = cgetg(lz, t_VECSMALL); z[1]=x[1];
     380         [ +  + ]:    2601766 :   for (j=2,jj=2;j<lx;j++,jj++)
     381                 :            :   {
     382                 :    1386094 :     ulong x1=((ulong)x[j]&HIGHMASK)>>BITS_IN_HALFULONG;
     383                 :    1386094 :     ulong x2=(ulong)x[j]&LOWMASK;
     384                 :    1386094 :     z[jj]=0;
     385         [ +  + ]:    1386094 :     if (x2)
     386         [ +  + ]:   11089775 :       for(i=0,ii=0;i<BITS_IN_HALFULONG;i+=4,ii+=8)
     387                 :    9717228 :         z[jj]|=sq[(x2>>i)&15UL]<<ii;
     388                 :    1386094 :     z[++jj]=0;
     389         [ +  + ]:    1386094 :     if (x1)
     390         [ +  + ]:    2798183 :       for(i=0,ii=0;i<BITS_IN_HALFULONG;i+=4,ii+=8)
     391                 :    2421212 :         z[jj]|=sq[(x1>>i)&15UL]<<ii;
     392                 :            :   }
     393                 :    1215672 :   return F2x_renormalize(z, lz);
     394                 :            : }
     395                 :            : 
     396                 :            : static GEN
     397                 :      33060 : F2x_pow2n(GEN x, long n)
     398                 :            : {
     399                 :            :   long i;
     400         [ +  + ]:      99180 :   for(i=1;i<=n;i++)
     401                 :      66120 :     x = F2x_sqr(x);
     402                 :      33060 :   return x;
     403                 :            : }
     404                 :            : 
     405                 :            : int
     406                 :      10250 : F2x_issquare(GEN x)
     407                 :            : {
     408                 :      10250 :   const ulong mask = (ULONG_MAX/3UL)*2;
     409                 :      10250 :   ulong i, lx = lg(x);
     410         [ +  + ]:      20500 :   for (i=2; i<lx; i++)
     411         [ -  + ]:      10250 :     if ((x[i]&mask)) return 0;
     412                 :      10250 :   return 1;
     413                 :            : }
     414                 :            : 
     415                 :            : /* Assume x is a perfect square */
     416                 :            : GEN
     417                 :      12505 : F2x_sqrt(GEN x)
     418                 :            : {
     419                 :      12505 :   const ulong sq[]={0,1,4,5,2,3,6,7,8,9,12,13,10,11,14,15};
     420                 :            :   long i,ii,j,jj;
     421                 :      12505 :   long lx=lg(x), lz=2+((lx-1)>>1);
     422                 :            :   GEN z;
     423                 :      12505 :   z = cgetg(lz, t_VECSMALL); z[1]=x[1];
     424         [ +  + ]:      25010 :   for (j=2,jj=2;jj<lz;j++,jj++)
     425                 :            :   {
     426                 :      12505 :     ulong x2=x[j++];
     427                 :      12505 :     z[jj]=0;
     428         [ +  - ]:      12505 :     if (x2)
     429         [ +  + ]:     102541 :       for(i=0,ii=0;ii<BITS_IN_HALFULONG;i+=8,ii+=4)
     430                 :            :       {
     431                 :      90036 :         ulong rl = (x2>>i)&15UL, rh = (x2>>(i+4))&15UL;
     432                 :      90036 :         z[jj]|=sq[rl|(rh<<1)]<<ii;
     433                 :            :       }
     434         [ -  + ]:      12505 :     if (j<lx)
     435                 :            :     {
     436                 :          0 :       x2 = x[j];
     437         [ #  # ]:          0 :       if (x2)
     438         [ #  # ]:          0 :         for(i=0,ii=0;ii<BITS_IN_HALFULONG;i+=8,ii+=4)
     439                 :            :         {
     440                 :          0 :           ulong rl = (x2>>i)&15UL, rh = (x2>>(i+4))&15UL;
     441                 :          0 :           z[jj]|=(sq[rl|(rh<<1)]<<ii)<<BITS_IN_HALFULONG;
     442                 :            :         }
     443                 :            :     }
     444                 :            :   }
     445                 :      12505 :   return F2x_renormalize(z, lz);
     446                 :            : }
     447                 :            : 
     448                 :            : INLINE void
     449                 :   43792471 : F2x_addshiftip(GEN x, GEN y, ulong d)
     450                 :            : {
     451                 :   43792471 :   ulong db, dl=dvmduBIL(d, &db);
     452                 :   43792471 :   long i, ly = lg(y);
     453         [ +  + ]:   43792471 :   if (db)
     454                 :            :   {
     455                 :   37838230 :     ulong dc=BITS_IN_LONG-db;
     456                 :   37838230 :     ulong r=0;
     457         [ +  + ]:  138611915 :     for(i=2; i<ly; i++)
     458                 :            :     {
     459                 :  100773685 :       x[i+dl] ^= (((ulong)y[i])<<db)|r;
     460                 :  100773685 :       r = ((ulong)y[i])>>dc;
     461                 :            :     }
     462         [ +  + ]:   37838230 :     if (r) x[i+dl] ^= r;
     463                 :            :   }
     464                 :            :   else
     465         [ +  + ]:   17142685 :     for(i=2; i<ly; i++)
     466                 :   11188444 :       x[i+dl] ^= y[i];
     467                 :   43792471 : }
     468                 :            : 
     469                 :            : static GEN
     470                 :        330 : F2x_shiftneg(GEN y, ulong d)
     471                 :            : {
     472                 :        330 :   long db, dl=dvmdsBIL(d, &db);
     473                 :        330 :   long i, ly = lg(y), lx = ly-dl;
     474                 :        330 :   GEN x = cgetg(lx, t_VECSMALL);
     475                 :        330 :   x[1] = y[1];
     476         [ +  - ]:        330 :   if (db)
     477                 :            :   {
     478                 :        330 :     ulong dc=BITS_IN_LONG-db;
     479                 :        330 :     ulong r=0;
     480         [ +  + ]:        660 :     for(i=lx-1; i>=2; i--)
     481                 :            :     {
     482                 :        330 :       x[i] = (((ulong)y[i+dl])>>db)|r;
     483                 :        330 :       r = ((ulong)y[i+dl])<<dc;
     484                 :            :     }
     485                 :            :   }
     486                 :            :   else
     487         [ #  # ]:          0 :     for(i=2; i<lx; i++)
     488                 :          0 :       x[i] = y[i+dl];
     489                 :        330 :   return F2x_renormalize(x,lx);
     490                 :            : }
     491                 :            : 
     492                 :            : static GEN
     493                 :      57710 : F2x_shiftpos(GEN y, ulong d)
     494                 :            : {
     495                 :      57710 :   long db, dl=dvmdsBIL(d, &db);
     496                 :      57710 :   long i, ly = lg(y), lx = ly+dl+(!!db);
     497                 :      57710 :   GEN x = cgetg(lx, t_VECSMALL);
     498         [ +  + ]:      57717 :   x[1] = y[1]; for(i=0; i<dl; i++) x[i+2] = 0;
     499         [ +  - ]:      57710 :   if (db)
     500                 :            :   {
     501                 :      57710 :     ulong dc=BITS_IN_LONG-db;
     502                 :      57710 :     ulong r=0;
     503         [ +  + ]:     115822 :     for(i=2; i<ly; i++)
     504                 :            :     {
     505                 :      58112 :       x[i+dl] = (((ulong)y[i])<<db)|r;
     506                 :      58112 :       r = ((ulong)y[i])>>dc;
     507                 :            :     }
     508                 :      57710 :     x[i+dl] = r;
     509                 :            :   }
     510                 :            :   else
     511         [ #  # ]:          0 :     for(i=2; i<ly; i++)
     512                 :          0 :       x[i+dl] = y[i];
     513                 :      57710 :   return F2x_renormalize(x,lx);
     514                 :            : }
     515                 :            : 
     516                 :            : GEN
     517                 :      58040 : F2x_shift(GEN y, long d)
     518                 :            : {
     519         [ +  + ]:      58040 :   return d<0 ? F2x_shiftneg(y,-d): F2x_shiftpos(y,d);
     520                 :            : }
     521                 :            : 
     522                 :            : /* separate from F2x_divrem for maximal speed. */
     523                 :            : GEN
     524                 :    8356506 : F2x_rem(GEN x, GEN y)
     525                 :            : {
     526                 :            :   long dx,dy;
     527                 :    8356506 :   long lx=lg(x);
     528         [ +  + ]:    8356506 :   dy = F2x_degree(y); if (!dy) return pol0_F2x(x[1]);
     529                 :    7775441 :   dx = F2x_degree_lg(x,lx);
     530                 :    7775441 :   x  = vecsmall_copy(x);
     531         [ +  + ]:   39231712 :   while (dx>=dy)
     532                 :            :   {
     533                 :   31456271 :     F2x_addshiftip(x,y,dx-dy);
     534 [ +  + ][ +  + ]:   32411118 :     while (lx>2 && x[lx-1]==0) lx--;
     535                 :   31456271 :     dx = F2x_degree_lg(x,lx);
     536                 :            :   }
     537                 :    8356506 :   return F2x_renormalize(x, lx);
     538                 :            : }
     539                 :            : 
     540                 :            : GEN
     541                 :    6575348 : F2x_divrem(GEN x, GEN y, GEN *pr)
     542                 :            : {
     543                 :    6575348 :   long dx, dy, dz, lx = lg(x), vs = x[1];
     544                 :            :   GEN z;
     545                 :            : 
     546                 :    6575348 :   dy = F2x_degree(y);
     547         [ -  + ]:    6575348 :   if (dy<0) pari_err_INV("F2x_divrem",y);
     548         [ -  + ]:    6575348 :   if (pr == ONLY_REM) return F2x_rem(x, y);
     549         [ +  + ]:    6575348 :   if (!dy)
     550                 :            :   {
     551                 :     752029 :     z = vecsmall_copy(x);
     552 [ +  + ][ +  - ]:     752029 :     if (pr && pr != ONLY_DIVIDES) *pr = pol0_F2x(vs);
     553                 :     752029 :     return z;
     554                 :            :   }
     555                 :    5823319 :   dx = F2x_degree_lg(x,lx);
     556                 :    5823319 :   dz = dx-dy;
     557         [ -  + ]:    5823319 :   if (dz < 0)
     558                 :            :   {
     559 [ #  # ][ #  # ]:          0 :     if (pr == ONLY_DIVIDES) return dx < 0? vecsmall_copy(x): NULL;
     560                 :          0 :     z = pol0_F2x(vs);
     561         [ #  # ]:          0 :     if (pr) *pr = vecsmall_copy(x);
     562                 :          0 :     return z;
     563                 :            :   }
     564                 :    5823319 :   z = zero_zv(lg(x)-lg(y)+2); z[1] = vs;
     565                 :    5823319 :   x = vecsmall_copy(x);
     566         [ +  + ]:   18159519 :   while (dx>=dy)
     567                 :            :   {
     568                 :   12336200 :     F2x_set(z,dx-dy);
     569                 :   12336200 :     F2x_addshiftip(x,y,dx-dy);
     570 [ +  + ][ +  + ]:   12814857 :     while (lx>2 && x[lx-1]==0) lx--;
     571                 :   12336200 :     dx = F2x_degree_lg(x,lx);
     572                 :            :   }
     573                 :    5823319 :   z = F2x_renormalize(z, lg(z));
     574         [ +  + ]:    5823319 :   if (!pr) { cgiv(x); return z; }
     575                 :    5652614 :   x = F2x_renormalize(x, lx);
     576         [ -  + ]:    5652614 :   if (pr == ONLY_DIVIDES) {
     577         [ #  # ]:          0 :     if (lg(x) == 2) { cgiv(x); return z; }
     578                 :          0 :     avma = (pari_sp)(z + lg(z)); return NULL;
     579                 :            :   }
     580                 :    6575348 :   *pr = x; return z;
     581                 :            : }
     582                 :            : 
     583                 :            : long
     584                 :      31950 : F2x_valrem(GEN x, GEN *Z)
     585                 :            : {
     586                 :      31950 :   long v, v2, i, l=lg(x);
     587                 :            :   GEN y;
     588         [ -  + ]:      31950 :   if (l==2) { *Z = leafcopy(x); return LONG_MAX; }
     589 [ +  - ][ +  + ]:      32031 :   for (i=2; i<l && x[i]==0; i++) /*empty*/;
     590                 :      31950 :   v = i-2;
     591         [ +  - ]:      31950 :   v2 = (i < l)? vals(x[i]): 0;
     592         [ +  + ]:      31950 :   if (v+v2 == 0) { *Z = x; return 0; }
     593                 :       6705 :   l -= i-2;
     594                 :       6705 :   y = cgetg(l, t_VECSMALL); y[1] = x[1];
     595         [ +  + ]:       6705 :   if (v2 == 0)
     596         [ +  + ]:        143 :     for (i=2; i<l; i++) y[i] = x[i+v];
     597         [ +  + ]:       6634 :   else if (l == 3)
     598                 :       6629 :     y[2] = ((ulong)x[2+v]) >> v2;
     599                 :            :   else
     600                 :            :   {
     601                 :          5 :     const ulong sh = BITS_IN_LONG - v2;
     602                 :          5 :     ulong r = x[2+v];
     603         [ +  + ]:         10 :     for (i=3; i<l; i++)
     604                 :            :     {
     605                 :          5 :       y[i-1] = (x[i+v] << sh) | (r >> v2);
     606                 :          5 :       r = x[i+v];
     607                 :            :     }
     608                 :          5 :     y[l-1] = r >> v2;
     609                 :          5 :     (void)F2x_renormalize(y,l);
     610                 :            :   }
     611                 :      31950 :   *Z = y; return (v << TWOPOTBITS_IN_LONG) + v2;
     612                 :            : }
     613                 :            : 
     614                 :            : GEN
     615                 :      26170 : F2x_deflate(GEN x, long d)
     616                 :            : {
     617                 :            :   GEN y;
     618                 :      26170 :   long i,id, dy, dx = F2x_degree(x);
     619         [ -  + ]:      26170 :   if (d <= 1) return Flx_copy(x);
     620         [ -  + ]:      26170 :   if (dx < 0) return leafcopy(x);
     621                 :      26170 :   dy = dx/d; /* dy+1 coefficients + 1 extra word for variable */
     622                 :      26170 :   y = zero_zv(nbits2lg(dy+1)-1); y[1] = x[1];
     623         [ +  + ]:     134920 :   for (i=id=0; i<=dy; i++,id+=d)
     624         [ +  + ]:     108750 :     if (F2x_coeff(x,id)) F2x_set(y, i);
     625                 :      26170 :   return y;
     626                 :            : }
     627                 :            : 
     628                 :            : /* write p(X) = e(X^2) + Xo(X^2), shallow function */
     629                 :            : void
     630                 :       8742 : F2x_even_odd(GEN p, GEN *pe, GEN *po)
     631                 :            : {
     632                 :       8742 :   long n = F2x_degree(p), n0, n1, i;
     633                 :            :   GEN p0, p1;
     634                 :            : 
     635         [ +  + ]:      17264 :   if (n <= 0) { *pe = leafcopy(p); *po = pol0_F2x(p[1]); return; }
     636                 :            : 
     637                 :       8522 :   n0 = (n>>1)+1; n1 = n+1 - n0; /* n1 <= n0 <= n1+1 */
     638                 :       8522 :   p0 = zero_zv(nbits2lg(n0+1)-1); p0[1] = p[1];
     639                 :       8522 :   p1 = zero_zv(nbits2lg(n1+1)-1); p1[1] = p[1];
     640         [ +  + ]:     128351 :   for (i=0; i<n1; i++)
     641                 :            :   {
     642         [ +  + ]:     119829 :     if (F2x_coeff(p,i<<1)) F2x_set(p0,i);
     643         [ +  + ]:     119829 :     if (F2x_coeff(p,1+(i<<1))) F2x_set(p1,i);
     644                 :            :   }
     645 [ +  + ][ +  - ]:       8522 :   if (n1 != n0 && F2x_coeff(p,i<<1)) F2x_set(p0,i);
     646                 :       8522 :   *pe = F2x_renormalize(p0,lg(p0));
     647                 :       8522 :   *po = F2x_renormalize(p1,lg(p1));
     648                 :            : }
     649                 :            : 
     650                 :            : GEN
     651                 :     179951 : F2x_deriv(GEN z)
     652                 :            : {
     653                 :     179951 :   const ulong mask = ULONG_MAX/3UL;
     654                 :     179951 :   long i,l = lg(z);
     655                 :     179951 :   GEN x = cgetg(l, t_VECSMALL); x[1] = z[1];
     656         [ +  + ]:     361240 :   for (i=2; i<l; i++) x[i] = (((ulong)z[i])>>1)&mask;
     657                 :     179951 :   return F2x_renormalize(x,l);
     658                 :            : }
     659                 :            : 
     660                 :            : GEN
     661                 :     758815 : F2x_gcd(GEN a, GEN b)
     662                 :            : {
     663                 :     758815 :   pari_sp av = avma;
     664         [ +  + ]:     758815 :   if (lg(b) > lg(a)) swap(a, b);
     665         [ +  + ]:    5806061 :   while (lgpol(b))
     666                 :            :   {
     667                 :    5047246 :     GEN c = F2x_rem(a,b);
     668                 :    5047246 :     a = b; b = c;
     669         [ -  + ]:    5047246 :     if (gc_needed(av,2))
     670                 :            :     {
     671         [ #  # ]:          0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2x_gcd (d = %ld)",F2x_degree(c));
     672                 :          0 :       gerepileall(av,2, &a,&b);
     673                 :            :     }
     674                 :            :   }
     675         [ -  + ]:     758815 :   if (gc_needed(av,2)) a = gerepileuptoleaf(av, a);
     676                 :     758815 :   return a;
     677                 :            : }
     678                 :            : 
     679                 :            : GEN
     680                 :     255609 : F2x_extgcd(GEN a, GEN b, GEN *ptu, GEN *ptv)
     681                 :            : {
     682                 :     255609 :   pari_sp av=avma;
     683                 :            :   GEN u,v,d,d1,v1;
     684                 :     255609 :   long vx = a[1];
     685                 :     255609 :   d = a; d1 = b;
     686                 :     255609 :   v = pol0_F2x(vx); v1 = pol1_F2x(vx);
     687         [ +  + ]:    6162092 :   while (lgpol(d1))
     688                 :            :   {
     689                 :    5906483 :     GEN r, q = F2x_divrem(d,d1, &r);
     690                 :    5906483 :     v = F2x_add(v,F2x_mul(q,v1));
     691                 :    5906483 :     u=v; v=v1; v1=u;
     692                 :    5906483 :     u=r; d=d1; d1=u;
     693         [ -  + ]:    5906483 :     if (gc_needed(av,2))
     694                 :            :     {
     695         [ #  # ]:          0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2x_extgcd (d = %ld)",F2x_degree(d));
     696                 :    5906483 :       gerepileall(av,5, &d,&d1,&u,&v,&v1);
     697                 :            :     }
     698                 :            :   }
     699         [ -  + ]:     255609 :   if (ptu) *ptu = F2x_div(F2x_add(d, F2x_mul(b,v)), a);
     700                 :     255609 :   *ptv = v;
     701 [ -  + ][ #  # ]:     255609 :   if (gc_needed(av,2)) gerepileall(av,ptu?3:2,&d,ptv,ptu);
     702                 :     255609 :   return d;
     703                 :            : }
     704                 :            : 
     705                 :            : static GEN
     706                 :        105 : F2x_halfgcd_i(GEN a, GEN b)
     707                 :            : {
     708                 :        105 :   pari_sp av=avma;
     709                 :            :   GEN u,u1,v,v1;
     710                 :        105 :   long vx = a[1];
     711                 :        105 :   long n = (F2x_degree(a)+1)>>1;
     712                 :        105 :   u1 = v = pol0_F2x(vx);
     713                 :        105 :   u = v1 = pol1_F2x(vx);
     714         [ +  + ]:       1740 :   while (F2x_degree(b)>=n)
     715                 :            :   {
     716                 :       1635 :     GEN r, q = F2x_divrem(a,b, &r);
     717                 :       1635 :     a = b; b = r; swap(u,u1); swap(v,v1);
     718                 :       1635 :     u1 = F2x_add(u1, F2x_mul(u, q));
     719                 :       1635 :     v1 = F2x_add(v1, F2x_mul(v, q));
     720         [ -  + ]:       1635 :     if (gc_needed(av,2))
     721                 :            :     {
     722         [ #  # ]:          0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2x_halfgcd (d = %ld)",F2x_degree(b));
     723                 :       1635 :       gerepileall(av,6, &a,&b,&u1,&v1,&u,&v);
     724                 :            :     }
     725                 :            :   }
     726                 :        105 :   return gerepilecopy(av, mkmat2(mkcol2(u,u1), mkcol2(v,v1)));
     727                 :            : }
     728                 :            : 
     729                 :            : GEN
     730                 :        105 : F2x_halfgcd(GEN x, GEN y)
     731                 :            : {
     732                 :            :   pari_sp av;
     733                 :            :   GEN M,q,r;
     734         [ -  + ]:        105 :   if (F2x_degree(y)<F2x_degree(x)) return F2x_halfgcd_i(x,y);
     735                 :        105 :   av = avma;
     736                 :        105 :   q = F2x_divrem(y,x,&r);
     737                 :        105 :   M = F2x_halfgcd_i(x,r);
     738                 :        105 :   gcoeff(M,1,1) = F2x_add(gcoeff(M,1,1), F2x_mul(q, gcoeff(M,1,2)));
     739                 :        105 :   gcoeff(M,2,1) = F2x_add(gcoeff(M,2,1), F2x_mul(q, gcoeff(M,2,2)));
     740                 :        105 :   return gerepilecopy(av, M);
     741                 :            : }
     742                 :            : 
     743                 :            : GEN
     744                 :     878201 : F2xq_mul(GEN x,GEN y,GEN pol)
     745                 :            : {
     746                 :     878201 :   GEN z = F2x_mul(x,y);
     747                 :     878201 :   return F2x_rem(z,pol);
     748                 :            : }
     749                 :            : 
     750                 :            : GEN
     751                 :    1149552 : F2xq_sqr(GEN x,GEN pol)
     752                 :            : {
     753                 :    1149552 :   GEN z = F2x_sqr(x);
     754                 :    1149552 :   return F2x_rem(z,pol);
     755                 :            : }
     756                 :            : 
     757                 :            : GEN
     758                 :     255609 : F2xq_invsafe(GEN x, GEN T)
     759                 :            : {
     760                 :     255609 :   GEN V, z = F2x_extgcd(T, x, NULL, &V);
     761         [ -  + ]:     255609 :   if (F2x_degree(z)) return NULL;
     762                 :     255609 :   return V;
     763                 :            : }
     764                 :            : 
     765                 :            : GEN
     766                 :     255609 : F2xq_inv(GEN x,GEN T)
     767                 :            : {
     768                 :     255609 :   pari_sp av=avma;
     769                 :     255609 :   GEN U = F2xq_invsafe(x, T);
     770         [ -  + ]:     255609 :   if (!U) pari_err_INV("F2xq_inv",x);
     771                 :     255609 :   return gerepileuptoleaf(av, U);
     772                 :            : }
     773                 :            : 
     774                 :            : GEN
     775                 :     234694 : F2xq_div(GEN x,GEN y,GEN T)
     776                 :            : {
     777                 :     234694 :   pari_sp av = avma;
     778                 :     234694 :   return gerepileuptoleaf(av, F2xq_mul(x,F2xq_inv(y,T),T));
     779                 :            : }
     780                 :            : 
     781                 :            : static GEN
     782                 :      36406 : _F2xq_red(void *E, GEN x)
     783                 :      36406 : { return F2x_rem(x, (GEN)E); }
     784                 :            : static GEN
     785                 :      54081 : _F2xq_add(void *E, GEN x, GEN y)
     786                 :      54081 : { (void)E; return F2x_add(x,y); }
     787                 :            : 
     788                 :            : static GEN
     789                 :      64501 : _F2xq_cmul(void *E, GEN P, long a, GEN x)
     790                 :            : {
     791                 :      64501 :   GEN pol = (GEN) E;
     792         [ +  + ]:      64501 :   return F2x_coeff(P,a) ? x: pol0_F2x(pol[1]);
     793                 :            : }
     794                 :            : static GEN
     795                 :     159417 : _F2xq_sqr(void *E, GEN x)
     796                 :     159417 : { return F2xq_sqr(x, (GEN) E); }
     797                 :            : 
     798                 :            : static GEN
     799                 :     180720 : _F2xq_mul(void *E, GEN x, GEN y)
     800                 :     180720 : { return F2xq_mul(x,y, (GEN) E); }
     801                 :            : 
     802                 :            : static GEN
     803                 :      72795 : _F2xq_one(void *E)
     804                 :            : {
     805                 :      72795 :   GEN pol = (GEN) E;
     806                 :      72795 :   return pol1_F2x(pol[1]);
     807                 :            : }
     808                 :            : static GEN
     809                 :          0 : _F2xq_zero(void *E)
     810                 :            : {
     811                 :          0 :   GEN pol = (GEN) E;
     812                 :          0 :   return pol0_F2x(pol[1]);
     813                 :            : }
     814                 :            : 
     815                 :            : GEN
     816                 :       4628 : F2xq_pow(GEN x, GEN n, GEN pol)
     817                 :            : {
     818                 :       4628 :   pari_sp av=avma;
     819                 :            :   GEN y;
     820                 :            : 
     821         [ +  + ]:       4628 :   if (!signe(n)) return pol1_F2x(x[1]);
     822         [ +  + ]:       4598 :   if (is_pm1(n)) /* +/- 1 */
     823         [ +  + ]:       2031 :     return (signe(n) < 0)? F2xq_inv(x,pol): vecsmall_copy(x);
     824                 :            : 
     825         [ +  + ]:       2567 :   if (signe(n) < 0) x = F2xq_inv(x,pol);
     826                 :       2567 :   y = gen_pow(x, n, (void*)pol, &_F2xq_sqr, &_F2xq_mul);
     827                 :       4628 :   return gerepileupto(av, y);
     828                 :            : }
     829                 :            : 
     830                 :            : GEN
     831                 :       2715 : F2xq_powu(GEN x, ulong n, GEN pol)
     832                 :            : {
     833                 :       2715 :   pari_sp av=avma;
     834                 :            :   GEN y;
     835   [ -  +  -  + ]:       2715 :   switch(n)
     836                 :            :   {
     837                 :          0 :     case 0: return pol1_F2x(x[1]);
     838                 :       1295 :     case 1: return vecsmall_copy(x);
     839                 :          0 :     case 2: return F2xq_sqr(x,pol);
     840                 :            :   }
     841                 :       1420 :   y = gen_powu(x, n, (void*)pol, &_F2xq_sqr, &_F2xq_mul);
     842                 :       2715 :   return gerepileupto(av, y);
     843                 :            : }
     844                 :            : 
     845                 :            : /* generates the list of powers of x of degree 0,1,2,...,l*/
     846                 :            : GEN
     847                 :      36784 : F2xq_powers(GEN x, long l, GEN T)
     848                 :            : {
     849                 :      36784 :   int use_sqr = (F2x_degree(x)<<1) >= F2x_degree(T);
     850                 :      36784 :   return gen_powers(x, l, use_sqr, (void*)T, &_F2xq_sqr, &_F2xq_mul, &_F2xq_one);
     851                 :            : }
     852                 :            : 
     853                 :            : GEN
     854                 :      36784 : F2xq_matrix_pow(GEN y, long n, long m, GEN P)
     855                 :            : {
     856                 :      36784 :   return F2xV_to_F2m(F2xq_powers(y,m-1,P),n);
     857                 :            : }
     858                 :            : 
     859                 :            : static struct bb_algebra F2xq_algebra = { _F2xq_red,_F2xq_add,_F2xq_mul,_F2xq_sqr,_F2xq_one,_F2xq_zero};
     860                 :            : 
     861                 :            : GEN
     862                 :          0 : F2x_F2xqV_eval(GEN Q, GEN x, GEN T)
     863                 :            : {
     864                 :          0 :   long d = F2x_degree(Q);
     865                 :          0 :   return gen_bkeval_powers(Q,d,x,(void*)T,&F2xq_algebra,_F2xq_cmul);
     866                 :            : }
     867                 :            : 
     868                 :            : GEN
     869                 :      10705 : F2x_F2xq_eval(GEN Q, GEN x, GEN T)
     870                 :            : {
     871                 :      10705 :   long d = F2x_degree(Q);
     872                 :      10705 :   int use_sqr = (F2x_degree(x)<<1) >= F2x_degree(T);
     873                 :      10705 :   return gen_bkeval(Q, d, x, use_sqr, (void*)T, &F2xq_algebra, _F2xq_cmul);
     874                 :            : }
     875                 :            : 
     876                 :            : static GEN
     877                 :       6239 : F2xq_autpow_sqr(void * T, GEN x) { return F2x_F2xq_eval(x, x, (GEN) T); }
     878                 :            : 
     879                 :            : static GEN
     880                 :       4456 : F2xq_autpow_mul(void * T, GEN x, GEN y) { return F2x_F2xq_eval(x, y, (GEN) T); }
     881                 :            : 
     882                 :            : GEN
     883                 :       3432 : F2xq_autpow(GEN x, long n, GEN T)
     884                 :            : {
     885                 :       3432 :   return gen_powu(x,n,(void*)T,F2xq_autpow_sqr,F2xq_autpow_mul);
     886                 :            : }
     887                 :            : 
     888                 :            : ulong
     889                 :      47581 : F2xq_trace(GEN x, GEN T)
     890                 :            : {
     891                 :      47581 :   pari_sp av = avma;
     892                 :            :   ulong t;
     893                 :      47581 :   long n = F2x_degree(T)-1;
     894                 :      47581 :   GEN z = F2x_mul(x, F2x_deriv(T));
     895                 :      47581 :   z = F2x_rem(z, T);
     896                 :      47581 :   t = F2x_degree(z)<n ? 0 : 1;
     897                 :      47581 :   avma = av; return t;
     898                 :            : }
     899                 :            : 
     900                 :            : GEN
     901                 :          5 : F2xq_conjvec(GEN x, GEN T)
     902                 :            : {
     903                 :          5 :   long i, l = F2x_degree(T);
     904                 :          5 :   GEN z = cgetg(l,t_COL);
     905                 :          5 :   gel(z,1) = vecsmall_copy(x);
     906         [ +  + ]:         95 :   for (i=2; i<l; i++) gel(z,i) = F2xq_sqr(gel(z,i-1), T);
     907                 :          5 :   return z;
     908                 :            : }
     909                 :            : 
     910                 :            : static GEN
     911                 :        769 : _F2xq_pow(void *data, GEN x, GEN n)
     912                 :            : {
     913                 :        769 :   GEN pol = (GEN) data;
     914                 :        769 :   return F2xq_pow(x,n, pol);
     915                 :            : }
     916                 :            : 
     917                 :            : static GEN
     918                 :         50 : _F2xq_rand(void *data)
     919                 :            : {
     920                 :         50 :   pari_sp av=avma;
     921                 :         50 :   GEN pol = (GEN) data;
     922                 :         50 :   long d = F2x_degree(pol);
     923                 :            :   GEN z;
     924                 :            :   do
     925                 :            :   {
     926                 :         50 :     avma = av;
     927                 :         50 :     z = random_F2x(d,pol[1]);
     928         [ -  + ]:         50 :   } while (lgpol(z)==0);
     929                 :         50 :   return z;
     930                 :            : }
     931                 :            : 
     932                 :            : static GEN F2xq_easylog(void* E, GEN a, GEN g, GEN ord);
     933                 :            : 
     934                 :            : static const struct bb_group F2xq_star={_F2xq_mul,_F2xq_pow,_F2xq_rand,hash_GEN,F2x_equal,F2x_equal1,F2xq_easylog};
     935                 :            : 
     936                 :            : GEN
     937                 :        252 : F2xq_order(GEN a, GEN ord, GEN T)
     938                 :            : {
     939                 :        252 :   return gen_order(a,ord,(void*)T,&F2xq_star);
     940                 :            : }
     941                 :            : 
     942                 :            : static long
     943                 :      65530 : F2x_is_smooth_squarefree(GEN f, long r)
     944                 :            : {
     945                 :      65530 :   pari_sp av = avma;
     946                 :            :   long i;
     947                 :      65530 :   GEN sx = polx_F2x(f[1]), a = sx;
     948                 :      65530 :   for(i=1;  ;i++)
     949                 :            :   {
     950                 :     589700 :     a = F2xq_sqr(F2x_rem(a,f),f);
     951         [ +  + ]:     589700 :     if (F2x_equal(a, F2x_rem(sx,f))) {avma = av; return 1;}
     952         [ +  + ]:     562445 :     if (i==r) {avma = av; return 0;}
     953                 :     524170 :     f = F2x_div(f, F2x_gcd(F2x_add(a,sx),f));
     954                 :     589700 :   }
     955                 :            : }
     956                 :            : 
     957                 :            : static long
     958                 :      55280 : F2x_is_smooth(GEN g, long r)
     959                 :            : {
     960                 :      55280 :   GEN f = gen_0;
     961         [ -  + ]:      55280 :   if (lgpol(g)==0) return 0;
     962                 :            :   while (1)
     963                 :            :   {
     964                 :      65530 :     f = F2x_gcd(g, F2x_deriv(g));
     965         [ +  + ]:      65530 :     if (!F2x_is_smooth_squarefree(F2x_div(g, f), r))
     966                 :      38275 :       return 0;
     967         [ +  + ]:      27255 :     if (F2x_degree(f)==0) return 1;
     968         [ +  - ]:      10250 :     g = F2x_issquare(f) ? F2x_sqrt(f): f;
     969                 :      65530 :   }
     970                 :            :   return 0;
     971                 :            : }
     972                 :            : 
     973                 :            : static GEN
     974                 :       5230 : F2x_factorel(GEN h)
     975                 :            : {
     976                 :       5230 :   GEN F = F2x_factcantor(h, 0);
     977                 :       5230 :   GEN F1 = gel(F, 1), F2 = gel(F, 2);
     978                 :       5230 :   long i, l1 = lg(F1)-1;
     979                 :       5230 :   GEN p2 = cgetg(l1+1, t_VECSMALL);
     980                 :       5230 :   GEN e2 = cgetg(l1+1, t_VECSMALL);
     981         [ +  + ]:      23870 :   for (i = 1; i <= l1; ++i)
     982                 :            :   {
     983                 :      18640 :     p2[i] = mael(F1, i, 2);
     984                 :      18640 :     e2[i] = F2[i];
     985                 :            :   }
     986                 :       5230 :   return mkmat2(p2, e2);
     987                 :            : }
     988                 :            : 
     989                 :            : static GEN
     990                 :       5382 : mkF2(ulong x, long v) { return mkvecsmall2(v, x); }
     991                 :            : 
     992                 :            : static GEN F2xq_log_Coppersmith_d(GEN W, GEN g, long r, long n, GEN T, GEN mo);
     993                 :            : 
     994                 :            : static GEN
     995                 :         30 : F2xq_log_from_rel(GEN W, GEN rel, long r, long n, GEN T, GEN m)
     996                 :            : {
     997                 :         30 :   pari_sp av = avma;
     998                 :         30 :   GEN F = gel(rel,1), E = gel(rel,2), o = gen_0;
     999                 :         30 :   long i, l = lg(F);
    1000         [ +  + ]:        240 :   for(i=1; i<l; i++)
    1001                 :            :   {
    1002                 :        210 :     GEN R = gel(W, F[i]);
    1003         [ -  + ]:        210 :     if (signe(R)==0) /* Already failed */
    1004                 :          0 :       return NULL;
    1005         [ +  + ]:        210 :     else if (signe(R)<0) /* Not yet tested */
    1006                 :            :     {
    1007                 :          5 :       setsigne(gel(W,F[i]),0);
    1008                 :          5 :       R = F2xq_log_Coppersmith_d(W, mkF2(F[i],T[1]), r, n, T, m);
    1009         [ -  + ]:          5 :       if (!R) return NULL;
    1010                 :            :     }
    1011                 :        210 :     o = Fp_add(o, mulis(R, E[i]), m);
    1012                 :            :   }
    1013                 :         30 :   return gerepileuptoint(av, o);
    1014                 :            : }
    1015                 :            : 
    1016                 :            : static GEN
    1017                 :         30 : F2xq_log_Coppersmith_d(GEN W, GEN g, long r, long n, GEN T, GEN mo)
    1018                 :            : {
    1019                 :         30 :   pari_sp av = avma, av2;
    1020                 :         30 :   long dg = F2x_degree(g), k = r-1, m = maxss((dg-k)/2,0);
    1021                 :         30 :   long i, j, l = dg-m, N;
    1022                 :         30 :   GEN v = cgetg(k+m+1,t_MAT);
    1023                 :         30 :   long dT = F2x_degree(T);
    1024                 :         30 :   long h = dT>>n, d = dT-(h<<n);
    1025                 :         30 :   GEN R = F2x_add(F2x_shift(pol1_F2x(T[1]), dT), T);
    1026                 :         30 :   GEN z = F2x_rem(F2x_shift(pol1_F2x(T[1]),h), g);
    1027         [ +  + ]:        360 :   for(i=1; i<=k+m; i++)
    1028                 :            :   {
    1029                 :        330 :     gel(v,i) = F2x_to_F2v(F2x_shift(z,-l),m);
    1030                 :        330 :     z = F2x_rem(F2x_shift(z,1),g);
    1031                 :            :   }
    1032                 :         30 :   v = F2m_ker(v);
    1033         [ +  + ]:        330 :   for(i=1; i<=k; i++)
    1034                 :        300 :     gel(v,i) = F2v_to_F2x(gel(v,i),T[1]);
    1035                 :         30 :   N = 1<<k;
    1036                 :         30 :   av2 = avma;
    1037         [ +  - ]:       2200 :   for (i=1; i<N; i++)
    1038                 :            :   {
    1039                 :            :     GEN p,q,qh,a,b;
    1040                 :       2200 :     avma = av2;
    1041                 :       2200 :     q = pol0_F2x(T[1]);
    1042         [ +  + ]:      24200 :     for(j=0; j<k; j++)
    1043         [ +  + ]:      22000 :       if (i&(1UL<<j))
    1044                 :       6920 :         q = F2x_add(q, gel(v,j+1));
    1045                 :       2200 :     qh= F2x_shift(q,h);
    1046                 :       2200 :     p = F2x_rem(qh,g);
    1047                 :       2200 :     b = F2x_add(F2x_mul(R, F2x_pow2n(q, n)), F2x_shift(F2x_pow2n(p, n), d));
    1048 [ +  - ][ +  + ]:       2200 :     if (lgpol(b)==0 || !F2x_is_smooth(b, r)) continue;
    1049                 :         30 :     a = F2x_div(F2x_add(qh,p),g);
    1050 [ -  + ][ #  # ]:         30 :     if (F2x_degree(F2x_gcd(a,q)) &&  F2x_degree(F2x_gcd(a,p))) continue;
    1051 [ +  - ][ +  - ]:         30 :     if (!(lgpol(a)==0 || !F2x_is_smooth(a, r)))
    1052                 :            :     {
    1053                 :         30 :       GEN F = F2x_factorel(b);
    1054                 :         30 :       GEN G = F2x_factorel(a);
    1055                 :         30 :       GEN FG = vecsmall_concat(vecsmall_append(gel(F, 1), 2), gel(G, 1));
    1056                 :         30 :       GEN E  = vecsmall_concat(vecsmall_append(gel(F, 2), -d),
    1057                 :         60 :                                zv_z_mul(gel(G, 2),-(1L<<n)));
    1058                 :         30 :       GEN R  = famatsmall_reduce(mkmat2(FG, E));
    1059                 :         30 :       GEN l  = F2xq_log_from_rel(W, R, r, n, T, mo);
    1060         [ -  + ]:         30 :       if (!l) continue;
    1061                 :         30 :       l = Fp_div(l,int2n(n),mo);
    1062         [ +  + ]:         30 :       if (dg <= r)
    1063                 :            :       {
    1064                 :         10 :         affii(l,gel(W,g[2]));
    1065         [ -  + ]:         10 :         if (DEBUGLEVEL>1) err_printf("Found %lu\n", g[2]);
    1066                 :            :       }
    1067                 :         30 :       return gerepileuptoint(av, l);
    1068                 :            :     }
    1069                 :            :   }
    1070                 :          0 :   avma = av;
    1071                 :         30 :   return NULL;
    1072                 :            : }
    1073                 :            : 
    1074                 :            : static GEN
    1075                 :         10 : F2xq_log_find_rel(GEN b, long r, GEN T, GEN *g, ulong *e)
    1076                 :            : {
    1077                 :         10 :   pari_sp av = avma;
    1078                 :            :   while (1)
    1079                 :            :   {
    1080                 :            :     GEN M;
    1081                 :        105 :     *g = F2xq_mul(*g, b, T); (*e)++;
    1082                 :        105 :     M = F2x_halfgcd(*g,T);
    1083         [ +  + ]:        105 :     if (F2x_is_smooth(gcoeff(M,1,1), r))
    1084                 :            :     {
    1085                 :         30 :       GEN z = F2x_add(F2x_mul(gcoeff(M,1,1),*g), F2x_mul(gcoeff(M,1,2),T));
    1086         [ +  + ]:         30 :       if (F2x_is_smooth(z, r))
    1087                 :            :       {
    1088                 :         10 :         GEN F = F2x_factorel(z);
    1089                 :         10 :         GEN G = F2x_factorel(gcoeff(M,1,1));
    1090                 :         10 :         GEN rel = mkmat2(vecsmall_concat(gel(F, 1),gel(G, 1)),
    1091                 :         20 :                          vecsmall_concat(gel(F, 2),zv_neg(gel(G, 2))));
    1092                 :         10 :         gerepileall(av, 2, g, &rel);
    1093                 :         10 :         return rel;
    1094                 :            :       }
    1095                 :            :     }
    1096         [ -  + ]:         95 :     if (gc_needed(av,2))
    1097                 :            :     {
    1098         [ #  # ]:          0 :       if (DEBUGMEM>1) pari_warn(warnmem,"F2xq_log_find_rel");
    1099                 :          0 :       *g = gerepileuptoleaf(av, *g);
    1100                 :            :     }
    1101                 :         95 :   }
    1102                 :            : }
    1103                 :            : 
    1104                 :            : static GEN
    1105                 :         10 : F2xq_log_Coppersmith_rec(GEN W, long r2, GEN a, long r, long n, GEN T, GEN m)
    1106                 :            : {
    1107                 :         10 :   GEN b = polx_F2x(T[1]);
    1108                 :         10 :   ulong AV = 0;
    1109                 :         10 :   GEN g = a, bad = pol0_F2x(T[1]);
    1110                 :            :   pari_timer ti;
    1111                 :            :   while(1)
    1112                 :            :   {
    1113                 :            :     long i, l;
    1114                 :            :     GEN V, F, E, Ao;
    1115                 :         10 :     timer_start(&ti);
    1116                 :         10 :     V = F2xq_log_find_rel(b, r2, T, &g, &AV);
    1117         [ -  + ]:         10 :     if (DEBUGLEVEL>1) timer_printf(&ti,"%ld-smooth element",r2);
    1118                 :         10 :     F = gel(V,1); E = gel(V,2);
    1119                 :         10 :     l = lg(F);
    1120                 :         10 :     Ao = gen_0;
    1121         [ +  + ]:         95 :     for(i=1; i<l; i++)
    1122                 :            :     {
    1123                 :         85 :       GEN Fi = mkF2(F[i], T[1]);
    1124                 :            :       GEN R;
    1125         [ +  + ]:         85 :       if (F2x_degree(Fi) <= r)
    1126                 :            :       {
    1127         [ -  + ]:         65 :         if (signe(gel(W,F[i]))==0)
    1128                 :          0 :           break;
    1129         [ +  + ]:         65 :         else if (signe(gel(W,F[i]))<0)
    1130                 :            :         {
    1131                 :          5 :           setsigne(gel(W,F[i]),0);
    1132                 :          5 :           R = F2xq_log_Coppersmith_d(W,Fi,r,n,T,m);
    1133                 :            :         } else
    1134                 :         60 :           R = gel(W,F[i]);
    1135                 :            :       }
    1136                 :            :       else
    1137                 :            :       {
    1138         [ -  + ]:         20 :         if (F2x_equal(Fi,bad)) break;
    1139                 :         20 :         R = F2xq_log_Coppersmith_d(W,Fi,r,n,T,m);
    1140         [ -  + ]:         20 :         if (!R) bad = Fi;
    1141                 :            :       }
    1142         [ -  + ]:         85 :       if (!R) break;
    1143                 :         85 :       Ao = Fp_add(Ao, mulis(R, E[i]), m);
    1144                 :            :     }
    1145         [ +  - ]:         10 :     if (i==l) return subis(Ao,AV);
    1146                 :          0 :   }
    1147                 :            : }
    1148                 :            : 
    1149                 :            : /* Coppersmith:
    1150                 :            :  T*X^e = X^(h*2^n)-R
    1151                 :            :  (u*x^h + v)^(2^n) = u^(2^n)*X^(h*2^n)+v^(2^n)
    1152                 :            :  (u*x^h + v)^(2^n) = u^(2^n)*R+v^(2^n)
    1153                 :            : */
    1154                 :            : 
    1155                 :            : static GEN
    1156                 :      38585 : rel_Coppersmith(GEN u, GEN v, long h, GEN R, long r, long n, long d)
    1157                 :            : {
    1158                 :            :   GEN b, F, G, M;
    1159                 :      38585 :   GEN a = F2x_add(F2x_shift(u, h), v);
    1160         [ +  + ]:      38585 :   if (!F2x_is_smooth(a, r)) return NULL;
    1161                 :      14330 :   b = F2x_add(F2x_mul(R, F2x_pow2n(u, n)), F2x_shift(F2x_pow2n(v, n),d));
    1162         [ +  + ]:      14330 :   if (!F2x_is_smooth(b, r)) return NULL;
    1163                 :       2575 :   F = F2x_factorel(a);
    1164                 :       2575 :   G = F2x_factorel(b);
    1165                 :       2575 :   M = mkmat2(vecsmall_concat(gel(F, 1), vecsmall_append(gel(G, 1), 2)),
    1166                 :       7725 :              vecsmall_concat(zv_z_mul(gel(F, 2),1UL<<n), vecsmall_append(zv_neg(gel(G, 2)),d)));
    1167                 :      38585 :   return famatsmall_reduce(M);
    1168                 :            : }
    1169                 :            : 
    1170                 :            : static GEN
    1171                 :          5 : F2xq_log_Coppersmith(long nbrel, long r, long n, GEN T)
    1172                 :            : {
    1173                 :          5 :   long dT = F2x_degree(T);
    1174                 :          5 :   long h = dT>>n, d = dT-(h<<n);
    1175                 :          5 :   GEN R = F2x_add(F2x_shift(pol1_F2x(T[1]), dT), T);
    1176                 :          5 :   GEN u = mkF2(0,T[1]), v = mkF2(0,T[1]);
    1177                 :          5 :   long rel = 1, nbtest = 0;
    1178                 :          5 :   GEN M = cgetg(nbrel+1, t_VEC);
    1179                 :          5 :   pari_sp av = avma;
    1180                 :            :   long i,j;
    1181         [ -  + ]:          5 :   if (DEBUGLEVEL) err_printf("Coppersmith (R = %ld): ",F2x_degree(R));
    1182                 :          5 :   for (i=1; ; i++)
    1183                 :            :   {
    1184                 :        620 :     u[2] = i;
    1185         [ +  + ]:      38750 :     for(j=1; j<=i; j++)
    1186                 :            :     {
    1187                 :      38135 :       v[2] = j;
    1188                 :      38135 :       avma = av;
    1189         [ +  + ]:      38135 :       if (F2x_degree(F2x_gcd(u,v))==0)
    1190                 :            :       {
    1191                 :      19295 :         GEN z = rel_Coppersmith(u, v, h, R, r, n, d);
    1192                 :      19295 :         nbtest++;
    1193         [ +  + ]:      19295 :         if (z)
    1194                 :            :         {
    1195                 :        805 :           gel(M,rel++) = gerepilecopy(av, z); av = avma;
    1196 [ -  + ][ #  # ]:        805 :           if (DEBUGLEVEL && (rel&511UL)==0)
    1197                 :          0 :             err_printf("%ld%%[%ld] ",rel*100/nbrel,i);
    1198                 :            :         }
    1199         [ -  + ]:      19295 :         if (rel>nbrel) break;
    1200         [ +  + ]:      19295 :         if (i==j) continue;
    1201                 :      19290 :         z = rel_Coppersmith(v, u, h, R, r, n, d);
    1202                 :      19290 :         nbtest++;
    1203         [ +  + ]:      19290 :         if (!z) continue;
    1204                 :       1770 :         gel(M,rel++) = gerepilecopy(av, z); av = avma;
    1205 [ -  + ][ #  # ]:       1770 :         if (DEBUGLEVEL && (rel&511UL)==0)
    1206                 :          0 :           err_printf("%ld%%[%ld] ",rel*100/nbrel,i);
    1207         [ +  + ]:       1770 :         if (rel>nbrel) break;
    1208                 :            :       }
    1209                 :            :     }
    1210         [ +  + ]:        620 :     if (rel>nbrel) break;
    1211                 :        615 :   }
    1212         [ -  + ]:          5 :   if (DEBUGLEVEL) err_printf(": %ld tests\n", nbtest);
    1213                 :          5 :   return M;
    1214                 :            : }
    1215                 :            : 
    1216                 :            : static GEN
    1217                 :          5 : smallirred_F2x(ulong n, long sv)
    1218                 :            : {
    1219                 :          5 :   GEN a = zero_zv(nbits2lg(n+1)-1);
    1220                 :          5 :   a[1] = sv; F2x_set(a,n); a[2]++;
    1221         [ +  + ]:        100 :   while (!F2x_is_irred(a)) a[2]+=2;
    1222                 :          5 :   return a;
    1223                 :            : }
    1224                 :            : 
    1225                 :            : static GEN
    1226                 :          5 : check_kernel(long N, GEN M, GEN T, GEN m)
    1227                 :            : {
    1228                 :          5 :   pari_sp av = avma;
    1229                 :          5 :   GEN K = FpMs_leftkernel_elt(M, N, m);
    1230                 :          5 :   long i, f=0;
    1231                 :          5 :   long l = lg(K), lm = lgefint(m);
    1232                 :          5 :   GEN g = polx_F2x(T[1]);
    1233                 :          5 :   GEN idx = diviiexact(subis(int2n(F2x_degree(T)),1),m);
    1234                 :            :   pari_timer ti;
    1235         [ -  + ]:          5 :   if (DEBUGLEVEL) timer_start(&ti);
    1236                 :          5 :   K = FpC_Fp_mul(K, Fp_inv(gel(K,g[2]), m), m);
    1237         [ +  + ]:      20480 :   for(i=1; i<l; i++)
    1238                 :            :   {
    1239                 :      20475 :     GEN k = gel(K,i);
    1240 [ +  + ][ -  + ]:      20475 :     if (signe(k)==0 || !F2x_equal(F2xq_pow(g, mulii(k,idx), T),
    1241                 :       1850 :                                   F2xq_pow(mkF2(i,T[1]), idx, T)))
    1242                 :      18625 :       gel(K,i) = cgetineg(lm);
    1243                 :            :     else
    1244                 :       1850 :       f++;
    1245                 :            :   }
    1246         [ -  + ]:          5 :   if (DEBUGLEVEL) timer_printf(&ti,"found %ld logs", f);
    1247                 :          5 :   return gerepileupto(av, K);
    1248                 :            : }
    1249                 :            : 
    1250                 :            : static GEN
    1251                 :          5 : F2xq_log_index(GEN a0, GEN b0, GEN m, GEN T0)
    1252                 :            : {
    1253                 :          5 :   pari_sp av = avma;
    1254                 :          5 :   GEN  M, S, a, b, Ao=NULL, Bo=NULL, W, e;
    1255                 :            :   pari_timer ti;
    1256                 :          5 :   long n = F2x_degree(T0), r = (long) (sqrt((double) 2*n))-(n>100);
    1257                 :          5 :   GEN T = smallirred_F2x(n,T0[1]);
    1258                 :          5 :   long d = 2, r2 = 3*r/2, d2 = 2;
    1259                 :          5 :   long N = (1UL<<(r+1))-1UL;
    1260                 :          5 :   long nbi = itos(ffsumnbirred(gen_2, r)), nbrel=nbi*5/4;
    1261         [ -  + ]:          5 :   if (DEBUGLEVEL)
    1262                 :            :   {
    1263                 :          0 :     err_printf("F2xq_log: Parameters r=%ld r2=%ld\n", r,r2);
    1264                 :          0 :     err_printf("F2xq_log: Size FB=%ld rel. needed=%ld\n", nbi, nbrel);
    1265                 :          0 :     timer_start(&ti);
    1266                 :            :   }
    1267                 :          5 :   S = Flx_to_F2x(Flx_ffisom(F2x_to_Flx(T0),F2x_to_Flx(T),2));
    1268                 :          5 :   a = F2x_F2xq_eval(a0, S, T);
    1269                 :          5 :   b = F2x_F2xq_eval(b0, S, T);
    1270         [ -  + ]:          5 :   if (DEBUGLEVEL) timer_printf(&ti,"model change");
    1271                 :          5 :   M = F2xq_log_Coppersmith(nbrel,r,d,T);
    1272         [ -  + ]:          5 :   if(DEBUGLEVEL)
    1273                 :          0 :     timer_printf(&ti,"relations");
    1274                 :          5 :   W = check_kernel(N, M, T, m);
    1275                 :          5 :   timer_start(&ti);
    1276                 :          5 :   Ao = F2xq_log_Coppersmith_rec(W, r2, a, r, d2, T, m);
    1277         [ -  + ]:          5 :   if (DEBUGLEVEL) timer_printf(&ti,"smooth element");
    1278                 :          5 :   Bo = F2xq_log_Coppersmith_rec(W, r2, b, r, d2, T, m);
    1279         [ -  + ]:          5 :   if (DEBUGLEVEL) timer_printf(&ti,"smooth generator");
    1280                 :          5 :   e = Fp_div(Ao, Bo, m);
    1281         [ -  + ]:          5 :   if (!F2x_equal(F2xq_pow(b0,e,T0),a0)) pari_err_BUG("F2xq_log");
    1282                 :          5 :   return gerepileupto(av, e);
    1283                 :            : }
    1284                 :            : 
    1285                 :            : static GEN
    1286                 :         45 : F2xq_easylog(void* E, GEN a, GEN g, GEN ord)
    1287                 :            : {
    1288         [ -  + ]:         45 :   if (F2x_equal1(a)) return gen_0;
    1289         [ +  + ]:         45 :   if (F2x_equal(a,g)) return gen_1;
    1290         [ +  + ]:         40 :   if (typ(ord)!=t_INT) return NULL;
    1291         [ +  + ]:         30 :   if (expi(ord)<28) return NULL;
    1292                 :         45 :   return F2xq_log_index(a,g,ord,(GEN)E);
    1293                 :            : }
    1294                 :            : 
    1295                 :            : GEN
    1296                 :         15 : F2xq_log(GEN a, GEN g, GEN ord, GEN T)
    1297                 :            : {
    1298                 :         15 :   GEN z, v = dlog_get_ordfa(ord);
    1299                 :         15 :   ord = mkvec2(gel(v,1),ZM_famat_limit(gel(v,2),int2n(28)));
    1300                 :         15 :   z = gen_PH_log(a,g,ord,(void*)T,&F2xq_star);
    1301         [ -  + ]:         15 :   return z? z: cgetg(1,t_VEC);
    1302                 :            : }
    1303                 :            : 
    1304                 :            : GEN
    1305                 :      22089 : F2xq_Artin_Schreier(GEN a, GEN T)
    1306                 :            : {
    1307                 :      22089 :   pari_sp ltop=avma;
    1308                 :      22089 :   long j,N = F2x_degree(T);
    1309                 :            :   GEN Q, XP;
    1310                 :            :   pari_timer ti;
    1311                 :      22089 :   timer_start(&ti);
    1312                 :      22089 :   XP = F2xq_sqr(polx_F2x(T[1]),T);
    1313                 :      22089 :   Q  = F2xq_matrix_pow(XP,N,N,T);
    1314         [ +  + ]:     199302 :   for (j=1; j<=N; j++)
    1315                 :     177213 :     F2m_flip(Q,j,j);
    1316         [ -  + ]:      22089 :   if(DEBUGLEVEL>=9) timer_printf(&ti,"Berlekamp matrix");
    1317                 :      22089 :   F2v_add_inplace(gel(Q,1),a);
    1318                 :      22089 :   Q = F2m_ker_sp(Q,0);
    1319         [ -  + ]:      22089 :   if(DEBUGLEVEL>=9) timer_printf(&ti,"kernel");
    1320         [ -  + ]:      22089 :   if (lg(Q)!=2) return NULL;
    1321                 :      22089 :   Q = gel(Q,1);
    1322                 :      22089 :   Q[1] = T[1];
    1323                 :      22089 :   return gerepileuptoleaf(ltop, Q);
    1324                 :            : }
    1325                 :            : 
    1326                 :            : GEN
    1327                 :       8742 : F2xq_sqrt_fast(GEN c, GEN sqx, GEN T)
    1328                 :            : {
    1329                 :            :   GEN c0, c1;
    1330                 :       8742 :   F2x_even_odd(c, &c0, &c1);
    1331                 :       8742 :   return F2x_add(c0, F2xq_mul(c1, sqx, T));
    1332                 :            : }
    1333                 :            : 
    1334                 :            : static int
    1335 [ +  - ][ +  + ]:       3432 : F2x_is_x(GEN a) { return lg(a)==3 && a[2]==2; }
    1336                 :            : 
    1337                 :            : GEN
    1338                 :       3535 : F2xq_sqrt(GEN a, GEN T)
    1339                 :            : {
    1340                 :       3535 :   pari_sp av = avma;
    1341                 :       3535 :   long n = F2x_degree(T);
    1342                 :            :   GEN sqx;
    1343         [ +  + ]:       3535 :   if (n==1) return leafcopy(a);
    1344         [ +  + ]:       3516 :   if (n==2) return F2xq_sqr(a,T);
    1345                 :       3432 :   sqx = F2xq_autpow(mkF2(4, T[1]), n-1, T);
    1346         [ +  + ]:       3535 :   return gerepileuptoleaf(av, F2x_is_x(a)? sqx: F2xq_sqrt_fast(a,sqx,T));
    1347                 :            : }
    1348                 :            : 
    1349                 :            : GEN
    1350                 :         45 : F2xq_sqrtn(GEN a, GEN n, GEN T, GEN *zeta)
    1351                 :            : {
    1352         [ +  + ]:         45 :   if (!lgpol(a))
    1353                 :            :   {
    1354         [ +  - ]:          5 :     if (signe(n) < 0) pari_err_INV("F2xq_sqrtn",a);
    1355         [ #  # ]:          0 :     if (zeta)
    1356                 :          0 :       *zeta=pol1_F2x(T[1]);
    1357                 :          0 :     return pol0_F2x(T[1]);
    1358                 :            :   }
    1359                 :         40 :   return gen_Shanks_sqrtn(a,n,addis(powuu(2,F2x_degree(T)),-1),zeta,(void*)T,&F2xq_star);
    1360                 :            : }
    1361                 :            : 
    1362                 :            : GEN
    1363                 :         60 : gener_F2xq(GEN T, GEN *po)
    1364                 :            : {
    1365                 :         60 :   long i, j, vT = T[1], f = F2x_degree(T);
    1366                 :         60 :   pari_sp av0 = avma, av;
    1367                 :            :   GEN g, L2, o, q;
    1368                 :            : 
    1369         [ +  + ]:         60 :   if (f == 1) {
    1370         [ +  + ]:         10 :     if (po) *po = mkvec2(gen_1, trivial_fact());
    1371                 :         10 :     return pol1_F2x(vT);
    1372                 :            :   }
    1373                 :         50 :   q = subis(powuu(2,f), 1);
    1374                 :         50 :   o = factor_pn_1(gen_2,f);
    1375                 :         50 :   L2 = leafcopy( gel(o, 1) );
    1376         [ +  + ]:        145 :   for (i = j = 1; i < lg(L2); i++)
    1377                 :            :   {
    1378         [ -  + ]:         95 :     if (equaliu(gel(L2,i),2)) continue;
    1379                 :         95 :     gel(L2,j++) = diviiexact(q, gel(L2,i));
    1380                 :            :   }
    1381                 :         50 :   setlg(L2, j);
    1382                 :         50 :   for (av = avma;; avma = av)
    1383                 :            :   {
    1384                 :         98 :     g = random_F2x(f, vT);
    1385         [ +  + ]:         98 :     if (F2x_degree(g) < 1) continue;
    1386         [ +  + ]:        202 :     for (i = 1; i < j; i++)
    1387                 :            :     {
    1388                 :        152 :       GEN a = F2xq_pow(g, gel(L2,i), T);
    1389         [ +  + ]:        152 :       if (F2x_equal1(a)) break;
    1390                 :            :     }
    1391         [ +  + ]:         86 :     if (i == j) break;
    1392                 :         48 :   }
    1393         [ +  - ]:         50 :   if (!po) g = gerepilecopy(av0, g);
    1394                 :            :   else {
    1395                 :          0 :     *po = mkvec2(subis(int2n(f), 1), o);
    1396                 :          0 :     gerepileall(av0, 2, &g, po);
    1397                 :            :   }
    1398                 :         60 :   return g;
    1399                 :            : }
    1400                 :            : 
    1401                 :            : GEN
    1402                 :       1170 : ZXX_to_F2xX(GEN B, long v)
    1403                 :            : {
    1404                 :       1170 :   long lb=lg(B);
    1405                 :            :   long i;
    1406                 :       1170 :   GEN b=cgetg(lb,t_POL);
    1407                 :       1170 :   b[1]=evalsigne(1)|(((ulong)B[1])&VARNBITS);
    1408         [ +  + ]:       4680 :   for (i=2; i<lb; i++)
    1409      [ +  +  - ]:       3510 :     switch (typ(gel(B,i)))
    1410                 :            :     {
    1411                 :            :     case t_INT:
    1412                 :       1195 :       gel(b,i) = Z_to_F2x(gel(B,i), v);
    1413                 :       1195 :       break;
    1414                 :            :     case t_POL:
    1415                 :       2315 :       gel(b,i) = ZX_to_F2x(gel(B,i));
    1416                 :       2315 :       break;
    1417                 :            :     }
    1418                 :       1170 :   return FlxX_renormalize(b, lb);
    1419                 :            : }
    1420                 :            : 
    1421                 :            : static GEN
    1422                 :        100 : _F2xq_neg(void *E, GEN x)
    1423                 :        100 : { (void) E; return vecsmall_copy(x); }
    1424                 :            : 
    1425                 :            : static GEN
    1426                 :        475 : _F2xq_rmul(void *E, GEN x, GEN y)
    1427                 :        475 : { (void) E; return F2x_mul(x,y); }
    1428                 :            : 
    1429                 :            : static GEN
    1430                 :         55 : _F2xq_inv(void *E, GEN x)
    1431                 :         55 : { return F2xq_inv(x, (GEN) E); }
    1432                 :            : 
    1433                 :            : static int
    1434                 :        105 : _F2xq_equal0(GEN x) { return lgpol(x)==0; }
    1435                 :            : 
    1436                 :            : static GEN
    1437                 :         70 : _F2xq_s(void *E, long x)
    1438                 :         70 : { GEN T = (GEN) E;
    1439         [ +  + ]:         70 :   return odd(x)? pol1_F2x(T[1]): pol0_F2x(T[0]);
    1440                 :            : }
    1441                 :            : 
    1442                 :            : static const struct bb_field F2xq_field={_F2xq_red,_F2xq_add,_F2xq_rmul,_F2xq_neg,
    1443                 :            :                                          _F2xq_inv,_F2xq_equal0,_F2xq_s};
    1444                 :            : 
    1445                 :         40 : const struct bb_field *get_F2xq_field(void **E, GEN T)
    1446                 :            : {
    1447                 :         40 :   *E = (void *) T;
    1448                 :         40 :   return &F2xq_field;
    1449                 :            : }
    1450                 :            : 
    1451                 :            : /***********************************************************************/
    1452                 :            : /**                                                                   **/
    1453                 :            : /**                             F2v                                   **/
    1454                 :            : /**                                                                   **/
    1455                 :            : /***********************************************************************/
    1456                 :            : /* F2v objects are defined as follows:
    1457                 :            :    An F2v is a t_VECSMALL:
    1458                 :            :    v[0] = codeword
    1459                 :            :    v[1] = number of components
    1460                 :            :    x[2] = a_0...a_31 x[3] = a_32..a_63, etc.  on 32bit
    1461                 :            :    x[2] = a_0...a_63 x[3] = a_64..a_127, etc. on 64bit
    1462                 :            : 
    1463                 :            :    where the a_i are bits.
    1464                 :            : */
    1465                 :            : 
    1466                 :            : GEN
    1467                 :     628990 : F2c_to_ZC(GEN x)
    1468                 :            : {
    1469                 :     628990 :   long l=x[1]+1;
    1470                 :     628990 :   GEN  z = cgetg(l, t_COL);
    1471                 :            :   long i,j,k;
    1472         [ +  + ]:    1260342 :   for (i=2,k=1; i<lg(x); i++)
    1473 [ +  + ][ +  + ]:    5504502 :     for (j=0; j<BITS_IN_LONG && k<l; j++,k++)
    1474         [ +  + ]:    4873150 :       gel(z,k) = (x[i]&(1UL<<j))? gen_1: gen_0;
    1475                 :     628990 :   return z;
    1476                 :            : }
    1477                 :            : GEN
    1478                 :       2150 : F2c_to_mod(GEN x)
    1479                 :            : {
    1480                 :       2150 :   long l=x[1]+1;
    1481                 :       2150 :   GEN  z = cgetg(l, t_COL);
    1482                 :       2150 :   GEN _0 = mkintmod(gen_0,gen_2);
    1483                 :       2150 :   GEN _1 = mkintmod(gen_1,gen_2);
    1484                 :            :   long i,j,k;
    1485         [ +  + ]:      11500 :   for (i=2,k=1; i<lg(x); i++)
    1486 [ +  + ][ +  + ]:     409760 :     for (j=0; j<BITS_IN_LONG && k<l; j++,k++)
    1487         [ +  + ]:     400410 :       gel(z,k) = (x[i]&(1UL<<j))? _1: _0;
    1488                 :       2150 :   return z;
    1489                 :            : }
    1490                 :            : 
    1491                 :            : /* x[a..b], a <= b */
    1492                 :            : GEN
    1493                 :         20 : F2v_slice(GEN x, long a, long b)
    1494                 :            : {
    1495                 :         20 :   long i,j,k, l = b-a+1;
    1496                 :         20 :   GEN z = cgetg(nbits2lg(l), t_VECSMALL);
    1497                 :         20 :   z[1] = l;
    1498         [ +  + ]:         70 :   for(i=a,k=1,j=BITS_IN_LONG; i<=b; i++,j++)
    1499                 :            :   {
    1500         [ +  + ]:         50 :     if (j==BITS_IN_LONG) { j=0; z[++k]=0; }
    1501         [ +  + ]:         50 :     if (F2v_coeff(x,i)) z[k] |= 1UL<<j;
    1502                 :            :   }
    1503                 :         20 :   return z;
    1504                 :            : }
    1505                 :            : /* x[a..b,], a <= b */
    1506                 :            : GEN
    1507                 :         10 : F2m_rowslice(GEN x, long a, long b)
    1508                 :            : {
    1509                 :            :   long i, l;
    1510                 :         10 :   GEN y = cgetg_copy(x, &l);
    1511         [ +  + ]:         30 :   for (i = 1; i < l; i++) gel(y,i) = F2v_slice(gel(x,i),a,b);
    1512                 :         10 :   return y;
    1513                 :            : }
    1514                 :            : 
    1515                 :            : GEN
    1516                 :     110675 : F2m_to_ZM(GEN z)
    1517                 :            : {
    1518                 :     110675 :   long i, l = lg(z);
    1519                 :     110675 :   GEN x = cgetg(l,t_MAT);
    1520         [ +  + ]:     725985 :   for (i=1; i<l; i++) gel(x,i) = F2c_to_ZC(gel(z,i));
    1521                 :     110675 :   return x;
    1522                 :            : }
    1523                 :            : GEN
    1524                 :         70 : F2m_to_mod(GEN z)
    1525                 :            : {
    1526                 :         70 :   long i, l = lg(z);
    1527                 :         70 :   GEN x = cgetg(l,t_MAT);
    1528         [ +  + ]:       2210 :   for (i=1; i<l; i++) gel(x,i) = F2c_to_mod(gel(z,i));
    1529                 :         70 :   return x;
    1530                 :            : }
    1531                 :            : 
    1532                 :            : GEN
    1533                 :       2410 : F2c_to_Flc(GEN x)
    1534                 :            : {
    1535                 :       2410 :   long l=x[1]+1;
    1536                 :       2410 :   GEN  z=cgetg(l, t_VECSMALL);
    1537                 :            :   long i,j,k;
    1538         [ +  + ]:       4952 :   for (i=2,k=1; i<lg(x); i++)
    1539 [ +  + ][ +  + ]:      47892 :     for (j=0; j<BITS_IN_LONG && k<l; j++,k++)
    1540                 :      45350 :       z[k] = (x[i]>>j)&1UL;
    1541                 :       2410 :   return z;
    1542                 :            : }
    1543                 :            : 
    1544                 :            : GEN
    1545                 :        880 : F2m_to_Flm(GEN z)
    1546                 :            : {
    1547                 :        880 :   long i, l = lg(z);
    1548                 :        880 :   GEN x = cgetg(l,t_MAT);
    1549         [ +  + ]:       3290 :   for (i=1; i<l; i++) gel(x,i) = F2c_to_Flc(gel(z,i));
    1550                 :        880 :   return x;
    1551                 :            : }
    1552                 :            : 
    1553                 :            : GEN
    1554                 :    1313130 : ZV_to_F2v(GEN x)
    1555                 :            : {
    1556                 :    1313130 :   long l = lg(x)-1;
    1557                 :    1313130 :   GEN z = cgetg(nbits2lg(l), t_VECSMALL);
    1558                 :            :   long i,j,k;
    1559                 :    1313130 :   z[1] = l;
    1560         [ +  + ]:   13019255 :   for(i=1,k=1,j=BITS_IN_LONG; i<=l; i++,j++)
    1561                 :            :   {
    1562         [ +  + ]:   11706125 :     if (j==BITS_IN_LONG) { j=0; z[++k]=0; }
    1563         [ +  + ]:   11706125 :     if (mpodd(gel(x,i))) z[k] |= 1UL<<j;
    1564                 :            :   }
    1565                 :    1313130 :   return z;
    1566                 :            : }
    1567                 :            : 
    1568                 :            : GEN
    1569                 :       5445 : RgV_to_F2v(GEN x)
    1570                 :            : {
    1571                 :       5445 :   long l = lg(x)-1;
    1572                 :       5445 :   GEN z = cgetg(nbits2lg(l), t_VECSMALL);
    1573                 :            :   long i,j,k;
    1574                 :       5445 :   z[1] = l;
    1575         [ +  + ]:    1006805 :   for(i=1,k=1,j=BITS_IN_LONG; i<=l; i++,j++)
    1576                 :            :   {
    1577         [ +  + ]:    1001360 :     if (j==BITS_IN_LONG) { j=0; z[++k]=0; }
    1578         [ +  + ]:    1001360 :     if (Rg_to_F2(gel(x,i))) z[k] |= 1UL<<j;
    1579                 :            :   }
    1580                 :       5445 :   return z;
    1581                 :            : }
    1582                 :            : 
    1583                 :            : GEN
    1584                 :       4310 : Flv_to_F2v(GEN x)
    1585                 :            : {
    1586                 :       4310 :   long l = lg(x)-1;
    1587                 :       4310 :   GEN z = cgetg(nbits2lg(l), t_VECSMALL);
    1588                 :            :   long i,j,k;
    1589                 :       4310 :   z[1] = l;
    1590         [ +  + ]:      92970 :   for(i=1,k=1,j=BITS_IN_LONG; i<=l; i++,j++)
    1591                 :            :   {
    1592         [ +  + ]:      88660 :     if (j==BITS_IN_LONG) { j=0; z[++k]=0; }
    1593         [ +  + ]:      88660 :     if (x[i]&1L) z[k] |= 1UL<<j;
    1594                 :            :   }
    1595                 :       4310 :   return z;
    1596                 :            : }
    1597                 :            : 
    1598                 :            : GEN
    1599                 :     214980 : ZM_to_F2m(GEN x)
    1600                 :            : {
    1601                 :     214980 :   long j, l = lg(x);
    1602                 :     214980 :   GEN y = cgetg(l,t_MAT);
    1603         [ -  + ]:     214980 :   if (l == 1) return y;
    1604         [ +  + ]:    1528110 :   for (j=1; j<l; j++) gel(y,j) = ZV_to_F2v(gel(x,j));
    1605                 :     214980 :   return y;
    1606                 :            : }
    1607                 :            : 
    1608                 :            : GEN
    1609                 :        185 : RgM_to_F2m(GEN x)
    1610                 :            : {
    1611                 :        185 :   long j, l = lg(x);
    1612                 :        185 :   GEN y = cgetg(l,t_MAT);
    1613         [ -  + ]:        185 :   if (l == 1) return y;
    1614         [ +  + ]:       5620 :   for (j=1; j<l; j++) gel(y,j) = RgV_to_F2v(gel(x,j));
    1615                 :        185 :   return y;
    1616                 :            : }
    1617                 :            : 
    1618                 :            : GEN
    1619                 :        880 : Flm_to_F2m(GEN x)
    1620                 :            : {
    1621                 :        880 :   long j, l = lg(x);
    1622                 :        880 :   GEN y = cgetg(l,t_MAT);
    1623         [ -  + ]:        880 :   if (l == 1) return y;
    1624         [ +  + ]:       5180 :   for (j=1; j<l; j++) gel(y,j) = Flv_to_F2v(gel(x,j));
    1625                 :        880 :   return y;
    1626                 :            : }
    1627                 :            : 
    1628                 :            : /* Allow lg(y)<lg(x) */
    1629                 :            : void
    1630                 :   15350997 : F2v_add_inplace(GEN x, GEN y)
    1631                 :            : {
    1632                 :   15350997 :   long n = lg(y);
    1633                 :   15350997 :   long r = (n-2)&7L, q = n-r, i;
    1634         [ +  + ]:   36609612 :   for (i = 2; i < q; i += 8)
    1635                 :            :   {
    1636                 :   21258615 :     x[  i] ^= y[  i]; x[1+i] ^= y[1+i]; x[2+i] ^= y[2+i]; x[3+i] ^= y[3+i];
    1637                 :   21258615 :     x[4+i] ^= y[4+i]; x[5+i] ^= y[5+i]; x[6+i] ^= y[6+i]; x[7+i] ^= y[7+i];
    1638                 :            :   }
    1639   [ +  +  +  +  :   15350997 :   switch (r)
             +  +  +  + ]
    1640                 :            :   {
    1641                 :    3410010 :     case 7: x[i] ^= y[i]; i++; case 6: x[i] ^= y[i]; i++;
    1642                 :    7249674 :     case 5: x[i] ^= y[i]; i++; case 4: x[i] ^= y[i]; i++;
    1643                 :    9317953 :     case 3: x[i] ^= y[i]; i++; case 2: x[i] ^= y[i]; i++;
    1644                 :   11778798 :     case 1: x[i] ^= y[i]; i++;
    1645                 :            :   }
    1646                 :   15350997 : }
    1647                 :            : 
    1648                 :            : /***********************************************************************/
    1649                 :            : /**                                                                   **/
    1650                 :            : /**                               F2xV                                **/
    1651                 :            : /**                                                                   **/
    1652                 :            : /***********************************************************************/
    1653                 :            : /* F2xV are t_VEC with F2x coefficients. */
    1654                 :            : 
    1655                 :            : GEN
    1656                 :      36784 : F2xV_to_F2m(GEN v, long n)
    1657                 :            : {
    1658                 :      36784 :   long j, N = lg(v);
    1659                 :      36784 :   GEN y = cgetg(N, t_MAT);
    1660         [ +  + ]:     276097 :   for (j=1; j<N; j++) gel(y,j) = F2x_to_F2v(gel(v,j), n);
    1661                 :      36784 :   return y;
    1662                 :            : }

Generated by: LCOV version 1.9