Code coverage tests

This page documents the degree to which the PARI/GP source code is tested by our public test suite, distributed with the source distribution in directory src/test/. This is measured by the gcov utility; we then process gcov output using the lcov frond-end.

We test a few variants depending on Configure flags on the pari.math.u-bordeaux.fr machine (x86_64 architecture), and agregate them in the final report:

The target is 90% coverage for all mathematical modules (given that branches depending on DEBUGLEVEL or DEBUGMEM are not covered). This script is run to produce the results below.

LCOV - code coverage report
Current view: top level - basemath - FF.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.8.0 lcov report (development 18946-c0ba5ba) Lines: 911 961 94.8 %
Date: 2016-05-25 Functions: 104 108 96.3 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 360 443 81.3 %

           Branch data     Line data    Source code
       1                 :            : /* Copyright (C) 2000-2003  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                 :            : /*************************************************************************/
      18                 :            : /**                                                                     **/
      19                 :            : /**                   Routines for handling FFELT                       **/
      20                 :            : /**                                                                     **/
      21                 :            : /*************************************************************************/
      22                 :            : 
      23                 :            : /*************************************************************************/
      24                 :            : /**                                                                     **/
      25                 :            : /**                   Low-level constructors                            **/
      26                 :            : /**                                                                     **/
      27                 :            : /*************************************************************************/
      28                 :            : 
      29                 :            : INLINE void
      30                 :   28153271 : _getFF(GEN x, GEN *T, GEN *p, ulong *pp)
      31                 :            : {
      32                 :   28153271 :   *T=gel(x,3);
      33                 :   28153271 :   *p=gel(x,4);
      34                 :   28153271 :   *pp=(*p)[2];
      35                 :   28153271 : }
      36                 :            : 
      37                 :            : INLINE GEN
      38                 :   27281867 : _initFF(GEN x, GEN *T, GEN *p, ulong *pp)
      39                 :            : {
      40                 :   27281867 :   _getFF(x,T,p,pp);
      41                 :   27281874 :   return cgetg(5,t_FFELT);
      42                 :            : }
      43                 :            : 
      44                 :            : INLINE void
      45                 :   21138150 : _checkFF(GEN x, GEN y, const char *s)
      46         [ -  + ]:   21138150 : { if (!FF_samefield(x,y)) pari_err_OP(s,x,y); }
      47                 :            : 
      48                 :            : INLINE GEN
      49                 :   27197514 : _mkFF(GEN x, GEN z, GEN r)
      50                 :            : {
      51                 :   27197514 :   z[1]=x[1];
      52                 :   27197514 :   gel(z,2)=r;
      53                 :   27197514 :   gel(z,3)=gcopy(gel(x,3));
      54                 :   27197524 :   gel(z,4)=icopy(gel(x,4));
      55                 :   27197525 :   return z;
      56                 :            : }
      57                 :            : 
      58                 :            : INLINE GEN
      59                 :    1650798 : _mkFF_i(GEN x, GEN z, GEN r)
      60                 :            : {
      61                 :    1650798 :   z[1]=x[1];
      62                 :    1650798 :   gel(z,2)=r;
      63                 :    1650798 :   gel(z,3)=gel(x,3);
      64                 :    1650798 :   gel(z,4)=gel(x,4);
      65                 :    1650798 :   return z;
      66                 :            : }
      67                 :            : 
      68                 :            : INLINE GEN
      69                 :    1566258 : mkFF_i(GEN x, GEN r)
      70                 :            : {
      71                 :    1566258 :   GEN z = cgetg(5,t_FFELT);
      72                 :    1566261 :   return _mkFF_i(x,z,r);
      73                 :            : }
      74                 :            : 
      75                 :            : /*************************************************************************/
      76                 :            : /**                                                                     **/
      77                 :            : /**                   medium-level constructors                         **/
      78                 :            : /**                                                                     **/
      79                 :            : /*************************************************************************/
      80                 :            : 
      81                 :            : static GEN
      82                 :     301455 : Z_to_raw(GEN x, GEN ff)
      83                 :            : {
      84                 :            :   ulong pp;
      85                 :            :   GEN T, p;
      86                 :     301455 :   _getFF(ff,&T,&p,&pp);
      87      [ +  +  + ]:     301455 :   switch(ff[1])
      88                 :            :   {
      89                 :            :   case t_FF_FpXQ:
      90                 :         16 :     return scalarpol(x, varn(T));
      91                 :            :   case t_FF_F2xq:
      92                 :     157101 :     return Z_to_F2x(x,varn(T));
      93                 :            :   default:
      94                 :     301455 :     return Z_to_Flx(x,pp,T[1]);
      95                 :            :   }
      96                 :            : }
      97                 :            : 
      98                 :            : static GEN
      99                 :     762923 : Rg_to_raw(GEN x, GEN ff)
     100                 :            : {
     101                 :     762923 :   long tx = typ(x);
     102      [ +  +  - ]:     762923 :   switch(tx)
     103                 :            :   {
     104                 :            :   case t_INT: case t_FRAC: case t_PADIC: case t_INTMOD:
     105                 :     301455 :     return Z_to_raw(Rg_to_Fp(x, FF_p_i(ff)), ff);
     106                 :            :   case t_FFELT:
     107         [ -  + ]:     461468 :     if (!FF_samefield(x,ff))
     108                 :          0 :       pari_err_MODULUS("Rg_to_raw",x,ff);
     109                 :     461468 :     return gel(x,2);
     110                 :            :   }
     111                 :          0 :   pari_err_TYPE("Rg_to_raw",x);
     112                 :     762923 :   return NULL; /* not reached */
     113                 :            : }
     114                 :            : 
     115                 :            : static GEN
     116                 :     103439 : FFX_to_raw(GEN x, GEN ff)
     117                 :            : {
     118                 :            :   long i, lx;
     119                 :     103439 :   GEN y = cgetg_copy(x,&lx);
     120                 :     103439 :   y[1] = x[1];
     121         [ +  + ]:     866362 :   for(i=2; i<lx; i++)
     122                 :     762923 :     gel(y, i) = Rg_to_raw(gel(x, i), ff);
     123                 :     103439 :   return y;
     124                 :            : }
     125                 :            : 
     126                 :            : static GEN
     127                 :       3087 : FFC_to_raw(GEN x)
     128                 :            : {
     129                 :            :   long i, lx;
     130                 :       3087 :   GEN y = cgetg_copy(x,&lx);
     131         [ +  + ]:      29799 :   for(i=1; i<lx; i++)
     132                 :      26712 :     gel(y, i) = gel(gel(x, i), 2);
     133                 :       3087 :   return y;
     134                 :            : }
     135                 :            : 
     136                 :            : static GEN
     137                 :        441 : FFM_to_raw(GEN x)
     138                 :            : {
     139                 :            :   long i, lx;
     140                 :        441 :   GEN y = cgetg_copy(x,&lx);
     141         [ +  + ]:       3507 :   for(i=1; i<lx; i++)
     142                 :       3066 :     gel(y, i) = FFC_to_raw(gel(x, i));
     143                 :        441 :   return y;
     144                 :            : }
     145                 :            : 
     146                 :            : /* in place */
     147                 :            : static GEN
     148                 :     105112 : raw_to_FFC(GEN x, GEN ff)
     149                 :            : {
     150                 :     105112 :   long i, lx = lg(x);
     151         [ +  + ]:     225400 :   for (i=1; i<lx; i++) gel(x,i) = mkFF_i(ff, gel(x,i));
     152                 :     105112 :   return x;
     153                 :            : }
     154                 :            : 
     155                 :            : /* in place */
     156                 :            : static GEN
     157                 :        245 : raw_to_FFM(GEN x, GEN ff)
     158                 :            : {
     159                 :        245 :   long i, lx = lg(x);
     160         [ +  + ]:       1897 :   for (i=1; i<lx; i++) gel(x,i) = raw_to_FFC(gel(x,i), ff);
     161                 :        245 :   return x;
     162                 :            : }
     163                 :            : 
     164                 :            : GEN
     165                 :       1498 : Fq_to_FF(GEN x, GEN ff)
     166                 :            : {
     167                 :            :   ulong pp;
     168                 :       1498 :   GEN r, T, p, z=_initFF(ff,&T,&p,&pp);
     169                 :       1498 :   int is_int = typ(x)==t_INT;
     170      [ +  +  + ]:       1498 :   switch(ff[1])
     171                 :            :   {
     172                 :            :   case t_FF_FpXQ:
     173         [ +  + ]:        125 :     r= is_int ? scalarpol(x, varn(T)): x;
     174                 :        125 :     break;
     175                 :            :   case t_FF_F2xq:
     176         [ +  + ]:        441 :     r= is_int ? Z_to_F2x(x,T[1]): ZX_to_F2x(x);
     177                 :        441 :     break;
     178                 :            :   default:
     179         [ +  + ]:        932 :     r= is_int ? Z_to_Flx(x,pp,T[1]): ZX_to_Flx(x,pp);
     180                 :            :   }
     181                 :       1498 :   setvarn(r, varn(T)); /* paranoia */
     182                 :       1498 :   return _mkFF_i(ff,z,r);
     183                 :            : }
     184                 :            : 
     185                 :            : /* in place */
     186                 :            : static GEN
     187                 :        364 : to_FFX(GEN x, GEN ff)
     188                 :            : {
     189                 :        364 :   long i, lx = lg(x);
     190         [ -  + ]:        364 :   if (typ(x) != t_POL) pari_err_TYPE("to_FFX",x);
     191         [ +  + ]:       1204 :   for (i=2; i<lx; i++) gel(x,i) = Fq_to_FF(gel(x,i), ff);
     192                 :        364 :   return x;
     193                 :            : }
     194                 :            : 
     195                 :            : /*************************************************************************/
     196                 :            : /**                                                                     **/
     197                 :            : /**                   Public functions                                  **/
     198                 :            : /**                                                                     **/
     199                 :            : /*************************************************************************/
     200                 :            : 
     201                 :            : /* Return true if x and y are defined in the same field */
     202                 :            : int
     203                 :   22090734 : FF_samefield(GEN x, GEN y)
     204                 :            : {
     205         [ +  - ]:   44181466 :   return x[1] == y[1] && equalii(gel(x,4),gel(y,4))
     206 [ +  + ][ +  + ]:   44181466 :                       && gidentical(gel(x,3),gel(y,3));
     207                 :            : }
     208                 :            : 
     209                 :            : int
     210                 :      16370 : FF_equal(GEN x, GEN y)
     211 [ +  + ][ +  + ]:      16370 : { return FF_samefield(x,y) && gidentical(gel(x,2),gel(y,2)); }
     212                 :            : 
     213                 :            : int
     214                 :    8843057 : FF_equal0(GEN x)
     215                 :            : {
     216                 :    8843057 :   return lgpol(gel(x,2))==0;
     217                 :            : }
     218                 :            : 
     219                 :            : int
     220                 :       8848 : FF_equal1(GEN x)
     221                 :            : {
     222                 :       8848 :   GEN A = gel(x,2);
     223         [ +  + ]:       8848 :   switch(x[1])
     224                 :            :   {
     225                 :            :   case t_FF_FpXQ:
     226 [ +  + ][ +  + ]:        558 :     return degpol(A)==0 && gequal1(gel(A,2));
     227                 :            :   default:
     228 [ +  + ][ +  + ]:       8848 :     return degpol(A)==0 && A[2]==1;
     229                 :            :   }
     230                 :            : }
     231                 :            : 
     232                 :            : static int
     233                 :          0 : Fp_cmp_1(GEN x, GEN p)
     234                 :            : {
     235                 :          0 :   pari_sp av = avma;
     236                 :          0 :   int b = equalii(x, addis(p,-1));
     237                 :          0 :   avma = av; return b;
     238                 :            : }
     239                 :            : 
     240                 :            : int
     241                 :         42 : FF_equalm1(GEN x)
     242                 :            : {
     243                 :            :   ulong pp;
     244                 :         42 :   GEN T, p, y = gel(x,2);
     245                 :         42 :   _getFF(x,&T,&p,&pp);
     246         [ -  + ]:         42 :   switch(x[1])
     247                 :            :   {
     248                 :            :   case t_FF_FpXQ:
     249 [ #  # ][ #  # ]:          0 :     return (degpol(y) == 0 && Fp_cmp_1(gel(y,2), p));
     250                 :            :   default:
     251 [ +  + ][ +  + ]:         42 :     return (degpol(y) == 0 && uel(y,2) == pp-1);
     252                 :            :   }
     253                 :            : }
     254                 :            : 
     255                 :            : GEN
     256                 :       3248 : FF_zero(GEN x)
     257                 :            : {
     258                 :            :   ulong pp;
     259                 :       3248 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     260      [ +  +  + ]:       3248 :   switch(x[1])
     261                 :            :   {
     262                 :            :   case t_FF_FpXQ:
     263                 :        289 :     r=zeropol(varn(T));
     264                 :        289 :     break;
     265                 :            :   case t_FF_F2xq:
     266                 :         77 :     r=zero_F2x(T[1]);
     267                 :         77 :     break;
     268                 :            :   default:
     269                 :       2882 :     r=zero_Flx(T[1]);
     270                 :            :   }
     271                 :       3248 :   return _mkFF(x,z,r);
     272                 :            : }
     273                 :            : 
     274                 :            : GEN
     275                 :      24143 : FF_1(GEN x)
     276                 :            : {
     277                 :            :   ulong pp;
     278                 :      24143 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     279      [ +  +  + ]:      24143 :   switch(x[1])
     280                 :            :   {
     281                 :            :   case t_FF_FpXQ:
     282                 :         41 :     r=pol_1(varn(T));
     283                 :         41 :     break;
     284                 :            :   case t_FF_F2xq:
     285                 :      11837 :     r=pol1_F2x(T[1]);
     286                 :      11837 :     break;
     287                 :            :   default:
     288                 :      12265 :     r=pol1_Flx(T[1]);
     289                 :            :   }
     290                 :      24143 :   return _mkFF(x,z,r);
     291                 :            : }
     292                 :            : 
     293                 :            : GEN
     294                 :      69622 : FF_q(GEN x)
     295                 :            : {
     296                 :            :   ulong pp;
     297                 :            :   GEN T, p;
     298                 :      69622 :   _getFF(x,&T,&p,&pp);
     299      [ +  +  + ]:      69622 :   switch(x[1])
     300                 :            :   {
     301                 :            :   case t_FF_FpXQ:
     302                 :       1681 :     return powiu(p, degpol(T));
     303                 :            :     break;
     304                 :            :   case t_FF_F2xq:
     305                 :       7056 :     return int2n(F2x_degree(T));
     306                 :            :     break;
     307                 :            :   default:
     308                 :      69622 :     return powuu(pp,degpol(T));
     309                 :            :   }
     310                 :            : }
     311                 :            : 
     312                 :            : GEN
     313                 :         56 : FF_p(GEN x)
     314                 :            : {
     315                 :         56 :   return icopy(gel(x,4));
     316                 :            : }
     317                 :            : 
     318                 :            : GEN
     319                 :    1092036 : FF_p_i(GEN x)
     320                 :            : {
     321                 :    1092036 :   return gel(x,4);
     322                 :            : }
     323                 :            : 
     324                 :            : GEN
     325                 :     164409 : FF_mod(GEN x)
     326                 :            : {
     327      [ +  +  + ]:     164409 :   switch(x[1])
     328                 :            :   {
     329                 :            :   case t_FF_FpXQ:
     330                 :          7 :     return ZX_copy(gel(x,3));
     331                 :            :   case t_FF_F2xq:
     332                 :         49 :     return F2x_to_ZX(gel(x,3));
     333                 :            :   default:
     334                 :     164409 :     return Flx_to_ZX(gel(x,3));
     335                 :            :   }
     336                 :            : }
     337                 :            : 
     338                 :            : long
     339                 :        196 : FF_f(GEN x)
     340                 :            : {
     341         [ +  + ]:        196 :   switch(x[1])
     342                 :            :   {
     343                 :            :   case t_FF_F2xq:
     344                 :         91 :     return F2x_degree(gel(x,3));
     345                 :            :   default:
     346                 :        196 :     return degpol(gel(x,3));
     347                 :            :   }
     348                 :            : }
     349                 :            : 
     350                 :            : GEN
     351                 :     113517 : FF_to_F2xq(GEN x)
     352                 :            : {
     353      [ -  +  - ]:     113517 :   switch(x[1])
     354                 :            :   {
     355                 :            :   case t_FF_FpXQ:
     356                 :          0 :     return ZX_to_F2x(gel(x,2));
     357                 :            :   case t_FF_F2xq:
     358                 :     113517 :     return zv_copy(gel(x,2));
     359                 :            :   default:
     360                 :     113518 :     return Flx_to_F2x(gel(x,2));
     361                 :            :   }
     362                 :            : }
     363                 :            : 
     364                 :            : GEN
     365                 :          0 : FF_to_F2xq_i(GEN x)
     366                 :            : {
     367      [ #  #  # ]:          0 :   switch(x[1])
     368                 :            :   {
     369                 :            :   case t_FF_FpXQ:
     370                 :          0 :     return ZX_to_F2x(gel(x,2));
     371                 :            :   case t_FF_F2xq:
     372                 :          0 :     return gel(x,2);
     373                 :            :   default:
     374                 :          0 :     return Flx_to_F2x(gel(x,2));
     375                 :            :   }
     376                 :            : }
     377                 :            : 
     378                 :            : GEN
     379                 :     785337 : FF_to_Flxq(GEN x)
     380                 :            : {
     381      [ -  -  + ]:     785337 :   switch(x[1])
     382                 :            :   {
     383                 :            :   case t_FF_FpXQ:
     384                 :          0 :     return ZX_to_Flx(gel(x,2),itou(gel(x,4)));
     385                 :            :   case t_FF_F2xq:
     386                 :          0 :     return F2x_to_Flx(gel(x,2));
     387                 :            :   default:
     388                 :     785337 :     return zv_copy(gel(x,2));
     389                 :            :   }
     390                 :            : }
     391                 :            : 
     392                 :            : GEN
     393                 :          0 : FF_to_Flxq_i(GEN x)
     394                 :            : {
     395      [ #  #  # ]:          0 :   switch(x[1])
     396                 :            :   {
     397                 :            :   case t_FF_FpXQ:
     398                 :          0 :     return ZX_to_Flx(gel(x,2),itou(gel(x,4)));
     399                 :            :   case t_FF_F2xq:
     400                 :          0 :     return F2x_to_Flx(gel(x,2));
     401                 :            :   default:
     402                 :          0 :     return gel(x,2);
     403                 :            :   }
     404                 :            : }
     405                 :            : 
     406                 :            : GEN
     407                 :      22393 : FF_to_FpXQ(GEN x)
     408                 :            : {
     409      [ +  +  + ]:      22393 :   switch(x[1])
     410                 :            :   {
     411                 :            :   case t_FF_FpXQ:
     412                 :      18213 :     return ZX_copy(gel(x,2));
     413                 :            :   case t_FF_F2xq:
     414                 :       1470 :     return F2x_to_ZX(gel(x,2));
     415                 :            :   default:
     416                 :      22393 :     return Flx_to_ZX(gel(x,2));
     417                 :            :   }
     418                 :            : }
     419                 :            : 
     420                 :            : GEN
     421                 :     167391 : FF_to_FpXQ_i(GEN x)
     422                 :            : {
     423      [ +  +  + ]:     167391 :   switch(x[1])
     424                 :            :   {
     425                 :            :   case t_FF_FpXQ:
     426                 :        350 :     return gel(x,2);
     427                 :            :   case t_FF_F2xq:
     428                 :        567 :     return F2x_to_ZX(gel(x,2));
     429                 :            :   default:
     430                 :     167391 :     return Flx_to_ZX(gel(x,2));
     431                 :            :   }
     432                 :            : }
     433                 :            : 
     434                 :            : GEN
     435                 :   10099045 : FF_add(GEN x, GEN y)
     436                 :            : {
     437                 :            :   ulong pp;
     438                 :   10099045 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     439                 :   10099046 :   _checkFF(x,y,"+");
     440      [ +  +  + ]:   10099046 :   switch(x[1])
     441                 :            :   {
     442                 :            :   case t_FF_FpXQ:
     443                 :     378890 :     r=FpX_add(gel(x,2),gel(y,2),p);
     444                 :     378890 :     break;
     445                 :            :   case t_FF_F2xq:
     446                 :     793122 :     r=F2x_add(gel(x,2),gel(y,2));
     447                 :     793122 :     break;
     448                 :            :   default:
     449                 :    8927034 :     r=Flx_add(gel(x,2),gel(y,2),pp);
     450                 :            :   }
     451                 :   10099046 :   return _mkFF(x,z,r);
     452                 :            : }
     453                 :            : GEN
     454                 :     416467 : FF_sub(GEN x, GEN y)
     455                 :            : {
     456                 :            :   ulong pp;
     457                 :     416467 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     458                 :     416467 :   _checkFF(x,y,"+");
     459      [ +  +  + ]:     416466 :   switch(x[1])
     460                 :            :   {
     461                 :            :   case t_FF_FpXQ:
     462                 :      16369 :     r=FpX_sub(gel(x,2),gel(y,2),p);
     463                 :      16369 :     break;
     464                 :            :   case t_FF_F2xq:
     465                 :      38771 :     r=F2x_add(gel(x,2),gel(y,2));
     466                 :      38772 :     break;
     467                 :            :   default:
     468                 :     361326 :     r=Flx_sub(gel(x,2),gel(y,2),pp);
     469                 :            :   }
     470                 :     416467 :   return _mkFF(x,z,r);
     471                 :            : }
     472                 :            : 
     473                 :            : GEN
     474                 :    1491060 : FF_Z_add(GEN x, GEN y)
     475                 :            : {
     476                 :            :   ulong pp;
     477                 :    1491060 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     478      [ +  +  + ]:    1491061 :   switch(x[1])
     479                 :            :   {
     480                 :            :   case t_FF_FpXQ:
     481                 :            :     {
     482                 :       8511 :       pari_sp av=avma;
     483                 :       8511 :       r=gerepileupto(av,FpX_Fp_add(gel(x,2),modii(y,p),p));
     484                 :       8511 :       break;
     485                 :            :     }
     486                 :            :   case t_FF_F2xq:
     487         [ +  + ]:     681646 :     r=mpodd(y)?F2x_1_add(gel(x,2)):vecsmall_copy(gel(x,2));
     488                 :     681645 :     break;
     489                 :            :   default:
     490                 :     800904 :     r=Flx_Fl_add(gel(x,2),umodiu(y,pp),pp);
     491                 :            :   }
     492                 :    1491060 :   return _mkFF(x,z,r);
     493                 :            : }
     494                 :            : 
     495                 :            : GEN
     496                 :       1442 : FF_Q_add(GEN x, GEN y)
     497                 :            : {
     498                 :            :   ulong pp;
     499                 :       1442 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     500      [ +  +  + ]:       1442 :   switch(x[1])
     501                 :            :   {
     502                 :            :   case t_FF_FpXQ:
     503                 :            :     {
     504                 :          1 :       pari_sp av=avma;
     505                 :          1 :       r=gerepileupto(av,FpX_Fp_add(gel(x,2),Rg_to_Fp(y,p),p));
     506                 :          1 :       break;
     507                 :            :     }
     508                 :            :   case t_FF_F2xq:
     509         [ +  - ]:          7 :     r=Rg_to_Fl(y,pp)?F2x_1_add(gel(x,2)):vecsmall_copy(gel(x,2));
     510                 :          7 :     break;
     511                 :            :   default:
     512                 :       1434 :     r=Flx_Fl_add(gel(x,2),Rg_to_Fl(y,pp),pp);
     513                 :            :   }
     514                 :       1442 :   return _mkFF(x,z,r);
     515                 :            : }
     516                 :            : 
     517                 :            : GEN
     518                 :      19331 : FF_neg(GEN x)
     519                 :            : {
     520                 :            :   ulong pp;
     521                 :      19331 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     522      [ +  +  + ]:      19331 :   switch(x[1])
     523                 :            :   {
     524                 :            :   case t_FF_FpXQ:
     525                 :        570 :     r=FpX_neg(gel(x,2),p);
     526                 :        570 :     break;
     527                 :            :   case t_FF_F2xq:
     528                 :       1586 :     r=vecsmall_copy(gel(x,2));
     529                 :       1586 :     break;
     530                 :            :   default:
     531                 :      17175 :     r=Flx_neg(gel(x,2),pp);
     532                 :            :   }
     533                 :      19331 :   return _mkFF(x,z,r);
     534                 :            : }
     535                 :            : 
     536                 :            : GEN
     537                 :      83037 : FF_neg_i(GEN x)
     538                 :            : {
     539                 :            :   ulong pp;
     540                 :      83037 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     541      [ +  +  + ]:      83037 :   switch(x[1])
     542                 :            :   {
     543                 :            :   case t_FF_FpXQ:
     544                 :       1440 :     r=FpX_neg(gel(x,2),p);
     545                 :       1440 :     break;
     546                 :            :   case t_FF_F2xq:
     547                 :       7850 :     r=gel(x,2);
     548                 :       7850 :     break;
     549                 :            :   default:
     550                 :      73747 :     r=Flx_neg(gel(x,2),pp);
     551                 :            :   }
     552                 :      83037 :   return _mkFF_i(x,z,r);
     553                 :            : }
     554                 :            : 
     555                 :            : GEN
     556                 :   10547622 : FF_mul(GEN x, GEN y)
     557                 :            : {
     558                 :            :   ulong pp;
     559                 :   10547622 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     560                 :   10547625 :   _checkFF(x,y,"*");
     561      [ +  +  + ]:   10547623 :   switch(x[1])
     562                 :            :   {
     563                 :            :   case t_FF_FpXQ:
     564                 :            :     {
     565                 :     361002 :       pari_sp av=avma;
     566                 :     361002 :       r=gerepileupto(av,FpXQ_mul(gel(x,2),gel(y,2),T,p));
     567                 :     361002 :       break;
     568                 :            :     }
     569                 :            :   case t_FF_F2xq:
     570                 :     687480 :     r=F2xq_mul(gel(x,2),gel(y,2),T);
     571                 :     687481 :     break;
     572                 :            :   default:
     573                 :    9499141 :     r=Flxq_mul(gel(x,2),gel(y,2),T,pp);
     574                 :            :   }
     575                 :   10547624 :   return _mkFF(x,z,r);
     576                 :            : }
     577                 :            : 
     578                 :            : GEN
     579                 :    1720272 : FF_Z_mul(GEN x, GEN y)
     580                 :            : {
     581                 :            :   ulong pp;
     582                 :    1720272 :   GEN r, T, p, A = gel(x,2), z=_initFF(x,&T,&p,&pp);
     583      [ +  +  + ]:    1720274 :   switch(x[1])
     584                 :            :   {
     585                 :            :   case t_FF_FpXQ: /* modii(y,p) left on stack for efficiency */
     586                 :      20598 :     r = FpX_Fp_mul(A, modii(y,p),p);
     587                 :      20598 :     break;
     588                 :            :   case t_FF_F2xq:
     589         [ +  + ]:     643461 :     r = mpodd(y)? vecsmall_copy(A): zero_Flx(A[1]);
     590                 :     643459 :     break;
     591                 :            :   default:
     592                 :    1056215 :     r = Flx_Fl_mul(A, umodiu(y,pp), pp);
     593                 :            :   }
     594                 :    1720272 :   return _mkFF(x,z,r);
     595                 :            : }
     596                 :            : 
     597                 :            : GEN
     598                 :       4704 : FF_Z_Z_muldiv(GEN x, GEN a, GEN b)
     599                 :            : {
     600                 :            :   ulong pp;
     601                 :       4704 :   GEN r, T, p, A = gel(x,2), z=_initFF(x,&T,&p,&pp);
     602      [ +  +  + ]:       4704 :   switch(x[1])
     603                 :            :   {
     604                 :            :   case t_FF_FpXQ: /* Fp_div(a,b,p) left on stack for efficiency */
     605                 :          2 :     r = FpX_Fp_mul(A, Fp_div(a,b,p), p);
     606                 :          2 :     break;
     607                 :            :   case t_FF_F2xq:
     608         [ -  + ]:        784 :     if (!mpodd(b)) pari_err_INV("FF_Z_Z_muldiv", b);
     609         [ +  + ]:        784 :     r = mpodd(a)? vecsmall_copy(A): zero_Flx(A[1]);
     610                 :        784 :     break;
     611                 :            :   default:
     612                 :       3918 :     r = Flx_Fl_mul(A, Fl_div(umodiu(a,pp),umodiu(b,pp),pp),pp);
     613                 :            :   }
     614                 :       4697 :   return _mkFF(x,z,r);
     615                 :            : }
     616                 :            : 
     617                 :            : GEN
     618                 :    2621515 : FF_sqr(GEN x)
     619                 :            : {
     620                 :            :   ulong pp;
     621                 :    2621515 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     622      [ +  +  + ]:    2621517 :   switch(x[1])
     623                 :            :   {
     624                 :            :   case t_FF_FpXQ:
     625                 :            :     {
     626                 :      13695 :       pari_sp av=avma;
     627                 :      13695 :       r=gerepileupto(av,FpXQ_sqr(gel(x,2),T,p));
     628                 :      13695 :       break;
     629                 :            :     }
     630                 :            :   case t_FF_F2xq:
     631                 :     262943 :     r=F2xq_sqr(gel(x,2),T);
     632                 :     262940 :     break;
     633                 :            :   default:
     634                 :    2344879 :     r=Flxq_sqr(gel(x,2),T,pp);
     635                 :            :   }
     636                 :    2621514 :   return _mkFF(x,z,r);
     637                 :            : }
     638                 :            : 
     639                 :            : GEN
     640                 :     153071 : FF_mul2n(GEN x, long n)
     641                 :            : {
     642                 :            :   ulong pp;
     643                 :     153071 :   GEN r, T, p, A = gel(x,2), z=_initFF(x,&T,&p,&pp);
     644      [ +  +  + ]:     153071 :   switch(x[1])
     645                 :            :   {
     646                 :            :   case t_FF_FpXQ:
     647                 :            :     {
     648                 :            :       GEN p1; /* left on stack for efficiency */
     649         [ +  + ]:       2944 :       if (n>0) p1=remii(int2n(n),p);
     650                 :         22 :       else p1=Fp_inv(remii(int2n(-n),p),p);
     651                 :       2944 :       r = FpX_Fp_mul(A, p1, p);
     652                 :            :     }
     653                 :       2944 :     break;
     654                 :            :   case t_FF_F2xq:
     655         [ -  + ]:      18321 :     if (n<0) pari_err_INV("FF_mul2n", gen_2);
     656         [ -  + ]:      18321 :     r = n==0? vecsmall_copy(A): zero_Flx(A[1]);
     657                 :      18322 :     break;
     658                 :            :   default:
     659                 :            :     {
     660                 :            :       ulong l1;
     661         [ +  + ]:     131806 :       if (n>0) l1 = umodiu(int2n(n),pp);
     662                 :        132 :       else l1 = Fl_inv(umodiu(int2n(-n),pp),pp);
     663                 :     131806 :       r = Flx_Fl_mul(A,l1,pp);
     664                 :            :     }
     665                 :            :   }
     666                 :     153072 :   return _mkFF(x,z,r);
     667                 :            : }
     668                 :            : 
     669                 :            : GEN
     670                 :       4629 : FF_inv(GEN x)
     671                 :            : {
     672                 :            :   ulong pp;
     673                 :       4629 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     674                 :       4630 :   pari_sp av=avma;
     675      [ +  +  + ]:       4630 :   switch(x[1])
     676                 :            :   {
     677                 :            :   case t_FF_FpXQ:
     678                 :          1 :     r=gerepileupto(av,FpXQ_inv(gel(x,2),T,p));
     679                 :          1 :     break;
     680                 :            :   case t_FF_F2xq:
     681                 :       4063 :     r=F2xq_inv(gel(x,2),T);
     682                 :       4063 :     break;
     683                 :            :   default:
     684                 :        566 :     r=Flxq_inv(gel(x,2),T,pp);
     685                 :            :   }
     686                 :       4630 :   return _mkFF(x,z,r);
     687                 :            : }
     688                 :            : 
     689                 :            : GEN
     690                 :      74844 : FF_div(GEN x, GEN y)
     691                 :            : {
     692                 :            :   ulong pp;
     693                 :      74844 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     694                 :      74844 :   pari_sp av=avma;
     695                 :      74844 :   _checkFF(x,y,"/");
     696      [ +  +  + ]:      74844 :   switch(x[1])
     697                 :            :   {
     698                 :            :   case t_FF_FpXQ:
     699                 :       1424 :     r=gerepileupto(av,FpXQ_div(gel(x,2),gel(y,2),T,p));
     700                 :       1424 :     break;
     701                 :            :   case t_FF_F2xq:
     702                 :       9576 :     r=gerepileupto(av,F2xq_div(gel(x,2),gel(y,2),T));
     703                 :       9576 :     break;
     704                 :            :   default:
     705                 :      63844 :     r=gerepileupto(av,Flxq_div(gel(x,2),gel(y,2),T,pp));
     706                 :            :   }
     707                 :      74844 :   return _mkFF(x,z,r);
     708                 :            : }
     709                 :            : 
     710                 :            : GEN
     711                 :        322 : Z_FF_div(GEN n, GEN x)
     712                 :            : {
     713                 :            :   ulong pp;
     714                 :        322 :   GEN r, T, p, A = gel(x,2), z=_initFF(x,&T,&p,&pp);
     715                 :        322 :   pari_sp av=avma;
     716      [ +  +  + ]:        322 :   switch(x[1])
     717                 :            :   {
     718                 :            :   case t_FF_FpXQ:
     719                 :          8 :     r = gerepileupto(av,FpX_Fp_mul(FpXQ_inv(A,T,p),modii(n,p),p));
     720                 :          8 :     break;
     721                 :            :   case t_FF_F2xq:
     722                 :         56 :     r = F2xq_inv(A,T); /*Check for division by 0*/
     723         [ +  + ]:         56 :     if(!mpodd(n)) { avma = av; r = zero_Flx(A[1]); }
     724                 :         56 :     break;
     725                 :            :   default:
     726                 :        258 :     r = gerepileupto(av, Flx_Fl_mul(Flxq_inv(A,T,pp),umodiu(n,pp),pp));
     727                 :            :   }
     728                 :        322 :   return _mkFF(x,z,r);
     729                 :            : }
     730                 :            : 
     731                 :            : GEN
     732                 :        105 : FF_sqrtn(GEN x, GEN n, GEN *zetan)
     733                 :            : {
     734                 :            :   ulong pp;
     735                 :        105 :   GEN r, T, p, y=_initFF(x,&T,&p,&pp);
     736      [ +  +  + ]:        105 :   switch (x[1])
     737                 :            :   {
     738                 :            :   case t_FF_FpXQ:
     739                 :         10 :     r=FpXQ_sqrtn(gel(x,2),n,T,p,zetan);
     740                 :          3 :     break;
     741                 :            :   case t_FF_F2xq:
     742                 :         28 :     r=F2xq_sqrtn(gel(x,2),n,T,zetan);
     743                 :         21 :     break;
     744                 :            :   default:
     745                 :         67 :     r=Flxq_sqrtn(gel(x,2),n,T,pp,zetan);
     746                 :            :   }
     747         [ -  + ]:         84 :   if (!r) pari_err_SQRTN("FF_sqrtn",x);
     748                 :         84 :   (void)_mkFF(x, y, r);
     749         [ +  + ]:         84 :   if (zetan)
     750                 :            :   {
     751                 :         28 :     GEN z = cgetg(lg(y),t_FFELT);
     752                 :         28 :     *zetan=_mkFF(x, z, *zetan);
     753                 :            :   }
     754                 :         84 :   return y;
     755                 :            : }
     756                 :            : 
     757                 :            : GEN
     758                 :         70 : FF_sqrt(GEN x)
     759                 :            : {
     760                 :            :   ulong pp;
     761                 :         70 :   GEN r, T, p, y=_initFF(x,&T,&p,&pp);
     762      [ +  +  + ]:         70 :   switch (x[1])
     763                 :            :   {
     764                 :            :   case t_FF_FpXQ:
     765                 :          1 :     r = FpXQ_sqrt(gel(x,2),T,p);
     766                 :          1 :     break;
     767                 :            :   case t_FF_F2xq:
     768                 :         49 :     r = F2xq_sqrt(gel(x,2),T);
     769                 :         49 :     break;
     770                 :            :   default:
     771                 :         20 :     r = Flxq_sqrt(gel(x,2),T,pp);
     772                 :            :   }
     773         [ -  + ]:         70 :   if (!r) pari_err_SQRTN("FF_sqrt",x);
     774                 :         70 :   return _mkFF(x, y, r);
     775                 :            : }
     776                 :            : 
     777                 :            : long
     778                 :          7 : FF_issquare(GEN x)
     779                 :            : {
     780                 :            :   GEN T, p;
     781                 :            :   ulong pp;
     782                 :          7 :   _getFF(x, &T, &p, &pp);
     783      [ -  +  - ]:          7 :   switch(x[1])
     784                 :            :   {
     785                 :            :   case t_FF_FpXQ:
     786                 :          0 :     return FpXQ_issquare(gel(x,2), T, p);
     787                 :            :   case t_FF_F2xq:
     788                 :          7 :     return 1;
     789                 :            :   default: /* case t_FF_Flxq: */
     790                 :          7 :     return Flxq_issquare(gel(x,2), T, pp);
     791                 :            :   }
     792                 :            : }
     793                 :            : 
     794                 :            : long
     795                 :        182 : FF_issquareall(GEN x, GEN *pt)
     796                 :            : {
     797         [ +  + ]:        182 :   if (!pt) return FF_issquare(x);
     798                 :        182 :   return FF_ispower(x, gen_2, pt);
     799                 :            : }
     800                 :            : 
     801                 :            : long
     802                 :        287 : FF_ispower(GEN x, GEN K, GEN *pt)
     803                 :            : {
     804                 :            :   ulong pp;
     805                 :            :   GEN r, T, p;
     806                 :        287 :   pari_sp av = avma;
     807                 :            : 
     808 [ -  + ][ #  # ]:        287 :   if (FF_equal0(x)) { if (pt) *pt = gcopy(x); return 1; }
     809                 :        287 :   _getFF(x, &T, &p, &pp);
     810         [ +  + ]:        287 :   if (pt) *pt = cgetg(5,t_FFELT);
     811      [ +  +  + ]:        287 :   switch(x[1])
     812                 :            :   {
     813                 :            :   case t_FF_FpXQ:
     814                 :         71 :     r = FpXQ_sqrtn(gel(x,2),K,T,p,NULL);
     815                 :         71 :     break;
     816                 :            :   case t_FF_F2xq:
     817                 :         84 :     r = F2xq_sqrtn(gel(x,2),K,T,NULL);
     818                 :         84 :     break;
     819                 :            :   default: /* case t_FF_Flxq: */
     820                 :        132 :     r = Flxq_sqrtn(gel(x,2),K,T,pp,NULL);
     821                 :        132 :     break;
     822                 :            :   }
     823         [ +  + ]:        287 :   if (!r) { avma = av; return 0; }
     824         [ +  + ]:        203 :   if (pt) { (void)_mkFF(x,*pt,r); }
     825                 :        287 :   return 1;
     826                 :            : }
     827                 :            : 
     828                 :            : GEN
     829                 :         78 : FF_pow(GEN x, GEN n)
     830                 :            : {
     831                 :            :   ulong pp;
     832                 :         78 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     833      [ +  +  + ]:         78 :   switch(x[1])
     834                 :            :    {
     835                 :            :    case t_FF_FpXQ:
     836                 :         17 :      r = FpXQ_pow(gel(x,2), n, T, p);
     837                 :         17 :      break;
     838                 :            :    case t_FF_F2xq:
     839                 :          2 :      r = F2xq_pow(gel(x,2), n, T);
     840                 :          2 :      break;
     841                 :            :    default:
     842                 :         59 :      r = Flxq_pow(gel(x,2), n, T, pp);
     843                 :            :    }
     844                 :         78 :   return _mkFF(x,z,r);
     845                 :            : }
     846                 :            : 
     847                 :            : GEN
     848                 :         28 : FF_norm(GEN x)
     849                 :            : {
     850                 :            :   ulong pp;
     851                 :            :   GEN T,p;
     852                 :         28 :   _getFF(x,&T,&p,&pp);
     853      [ +  +  + ]:         28 :   switch (x[1])
     854                 :            :   {
     855                 :            :   case t_FF_FpXQ:
     856                 :          1 :     return FpXQ_norm(gel(x,2),T,p);
     857                 :            :   case t_FF_F2xq:
     858         [ +  - ]:          7 :     return lgpol(gel(x,2))?gen_1:gen_0;
     859                 :            :   default:
     860                 :         28 :     return utoi(Flxq_norm(gel(x,2),T,pp));
     861                 :            :   }
     862                 :            : }
     863                 :            : 
     864                 :            : GEN
     865                 :         28 : FF_trace(GEN x)
     866                 :            : {
     867                 :            :   ulong pp;
     868                 :            :   GEN T,p;
     869                 :         28 :   _getFF(x,&T,&p,&pp);
     870      [ +  +  + ]:         28 :   switch(x[1])
     871                 :            :   {
     872                 :            :   case t_FF_FpXQ:
     873                 :          1 :     return FpXQ_trace(gel(x,2),T,p);
     874                 :            :   case t_FF_F2xq:
     875         [ -  + ]:          7 :     return F2xq_trace(gel(x,2),T)?gen_1:gen_0;
     876                 :            :   default:
     877                 :         28 :     return utoi(Flxq_trace(gel(x,2),T,pp));
     878                 :            :   }
     879                 :            : }
     880                 :            : 
     881                 :            : GEN
     882                 :         28 : FF_conjvec(GEN x)
     883                 :            : {
     884                 :            :   ulong pp;
     885                 :            :   GEN r,T,p,v;
     886                 :            :   long i,l;
     887                 :            :   pari_sp av;
     888                 :         28 :   _getFF(x,&T,&p,&pp);
     889                 :         28 :   av = avma;
     890      [ +  +  + ]:         28 :   switch(x[1])
     891                 :            :   {
     892                 :            :   case t_FF_FpXQ:
     893                 :          1 :     v = FpXQ_conjvec(gel(x,2), T, p);
     894                 :          1 :     break;
     895                 :            :   case t_FF_F2xq:
     896                 :          7 :     v = F2xq_conjvec(gel(x,2), T);
     897                 :          7 :     break;
     898                 :            :   default:
     899                 :         20 :     v = Flxq_conjvec(gel(x,2), T, pp);
     900                 :            :   }
     901                 :         28 :   l = lg(v); r = cgetg(l, t_COL);
     902         [ +  + ]:        252 :   for(i=1; i<l; i++)
     903                 :        224 :     gel(r,i) = mkFF_i(x, gel(v,i));
     904                 :         28 :   return gerepilecopy(av, r);
     905                 :            : }
     906                 :            : 
     907                 :            : GEN
     908                 :         28 : FF_charpoly(GEN x)
     909                 :            : {
     910                 :            :   ulong pp;
     911                 :            :   GEN T,p;
     912                 :         28 :   pari_sp av=avma;
     913                 :         28 :   _getFF(x,&T,&p,&pp);
     914      [ +  +  + ]:         28 :   switch(x[1])
     915                 :            :   {
     916                 :            :   case t_FF_FpXQ:
     917                 :          1 :     return gerepileupto(av,FpXQ_charpoly(gel(x,2), T, p));
     918                 :            :   case t_FF_F2xq:
     919                 :          7 :     return gerepileupto(av,Flx_to_ZX(Flxq_charpoly(F2x_to_Flx(gel(x,2)),
     920                 :            :                                                    F2x_to_Flx(T), 2UL)));
     921                 :            :   default:
     922                 :         28 :     return gerepileupto(av,Flx_to_ZX(Flxq_charpoly(gel(x,2), T, pp)));
     923                 :            :   }
     924                 :            : }
     925                 :            : 
     926                 :            : GEN
     927                 :         28 : FF_minpoly(GEN x)
     928                 :            : {
     929                 :            :   ulong pp;
     930                 :            :   GEN T,p;
     931                 :         28 :   pari_sp av=avma;
     932                 :         28 :   _getFF(x,&T,&p,&pp);
     933      [ +  +  + ]:         28 :   switch(x[1])
     934                 :            :   {
     935                 :            :   case t_FF_FpXQ:
     936                 :          1 :     return gerepileupto(av,FpXQ_minpoly(gel(x,2), T, p));
     937                 :            :   case t_FF_F2xq:
     938                 :          7 :     return gerepileupto(av,Flx_to_ZX(Flxq_minpoly(F2x_to_Flx(gel(x,2)),
     939                 :            :                                                   F2x_to_Flx(T), 2UL)));
     940                 :            :   default:
     941                 :         28 :     return gerepileupto(av,Flx_to_ZX(Flxq_minpoly(gel(x,2), T, pp)));
     942                 :            :   }
     943                 :            : }
     944                 :            : 
     945                 :            : GEN
     946                 :        168 : FF_log(GEN x, GEN g, GEN ord)
     947                 :            : {
     948                 :        168 :   pari_sp av=avma;
     949                 :            :   ulong pp;
     950                 :            :   GEN r, T, p;
     951                 :        168 :   _getFF(x,&T,&p,&pp);
     952                 :        168 :   _checkFF(x,g,"log");
     953      [ +  +  + ]:        168 :   switch(x[1])
     954                 :            :   {
     955                 :            :   case t_FF_FpXQ:
     956         [ +  + ]:         44 :     if (!ord) ord = factor_pn_1(p,degpol(T));
     957                 :         44 :     r = FpXQ_log(gel(x,2), gel(g,2), ord, T, p);
     958                 :         16 :     break;
     959                 :            :   case t_FF_F2xq:
     960         [ +  + ]:         21 :     if (!ord) ord = factor_pn_1(gen_2,F2x_degree(T));
     961                 :         21 :     r = F2xq_log(gel(x,2), gel(g,2), ord, T);
     962                 :         21 :     break;
     963                 :            :   default:
     964         [ +  + ]:        103 :     if (!ord) ord = factor_pn_1(p,degpol(T));
     965                 :        103 :     r = Flxq_log(gel(x,2), gel(g,2), ord, T, pp);
     966                 :            :   }
     967                 :        140 :   return gerepileupto(av, r);
     968                 :            : }
     969                 :            : 
     970                 :            : GEN
     971                 :         28 : FF_order(GEN x, GEN o)
     972                 :            : {
     973                 :         28 :   pari_sp av=avma;
     974                 :            :   ulong pp;
     975                 :            :   GEN r, T,p;
     976                 :         28 :   _getFF(x,&T,&p,&pp);
     977      [ +  +  + ]:         28 :   switch(x[1])
     978                 :            :   {
     979                 :            :   case t_FF_FpXQ:
     980         [ +  - ]:          1 :     if (!o) o = factor_pn_1(p,degpol(T));
     981                 :          1 :     r = FpXQ_order(gel(x,2), o, T, p);
     982                 :          1 :     break;
     983                 :            :   case t_FF_F2xq:
     984         [ +  - ]:          7 :     if (!o) o = factor_pn_1(gen_2,F2x_degree(T));
     985                 :          7 :     r = F2xq_order(gel(x,2), o, T);
     986                 :          7 :     break;
     987                 :            :   default:
     988         [ +  - ]:         20 :     if (!o) o = factor_pn_1(p,degpol(T));
     989                 :         20 :     r = Flxq_order(gel(x,2), o, T, pp);
     990                 :            :   }
     991         [ -  + ]:         28 :   if (!o) r = gerepileuptoint(av,r);
     992                 :         28 :   return r;
     993                 :            : }
     994                 :            : 
     995                 :            : GEN
     996                 :        322 : FF_primroot(GEN x, GEN *o)
     997                 :            : {
     998                 :            :   ulong pp;
     999                 :        322 :   GEN r,T,p,z=_initFF(x,&T,&p,&pp);
    1000      [ +  +  + ]:        322 :   switch(x[1])
    1001                 :            :   {
    1002                 :            :   case t_FF_FpXQ:
    1003                 :         30 :     r = gener_FpXQ(T, p, o);
    1004                 :         30 :     break;
    1005                 :            :   case t_FF_F2xq:
    1006                 :         91 :     r = gener_F2xq(T, o);
    1007                 :         91 :     break;
    1008                 :            :   default:
    1009                 :        201 :     r = gener_Flxq(T, pp, o);
    1010                 :            :   }
    1011                 :        322 :   return _mkFF(x,z,r);
    1012                 :            : }
    1013                 :            : 
    1014                 :            : static GEN
    1015                 :     190169 : to_FFE(GEN P, GEN fg)
    1016                 :            : {
    1017         [ +  + ]:     190169 :   if(ell_is_inf(P))
    1018                 :      77182 :     return ellinf();
    1019                 :            :   else
    1020                 :     190169 :     retmkvec2(mkFF_i(fg,gel(P,1)), mkFF_i(fg,gel(P,2)));
    1021                 :            : }
    1022                 :            : 
    1023                 :            : static GEN
    1024                 :      16744 : to_FFE_vec(GEN x, GEN ff)
    1025                 :            : {
    1026                 :      16744 :   long i, lx = lg(x);
    1027         [ +  + ]:      36029 :   for (i=1; i<lx; i++) gel(x,i) = to_FFE(gel(x,i), ff);
    1028                 :      16744 :   return x;
    1029                 :            : }
    1030                 :            : 
    1031                 :            : static GEN
    1032                 :       1710 : FpXQ_ell_to_a4a6(GEN E, GEN T, GEN p)
    1033                 :            : {
    1034                 :            :   GEN a1, a3, b2, c4, c6;
    1035                 :       1710 :   a1 = Rg_to_FpXQ(ell_get_a1(E),T,p);
    1036                 :       1710 :   a3 = Rg_to_FpXQ(ell_get_a3(E),T,p);
    1037                 :       1710 :   b2 = Rg_to_FpXQ(ell_get_b2(E),T,p);
    1038                 :       1710 :   c4 = Rg_to_FpXQ(ell_get_c4(E),T,p);
    1039                 :       1710 :   c6 = Rg_to_FpXQ(ell_get_c6(E),T,p);
    1040                 :       1710 :   retmkvec3(FpX_neg(FpX_mulu(c4, 27, p), p), FpX_neg(FpX_mulu(c6, 54, p), p),
    1041                 :            :             mkvec4(Z_to_FpX(utoi(6),p,varn(T)),FpX_mulu(b2,3,p),
    1042                 :            :                    FpX_mulu(a1,3,p),FpX_mulu(a3,108,p)));
    1043                 :            : }
    1044                 :            : 
    1045                 :            : static GEN
    1046                 :      23317 : F3xq_ell_to_a4a6(GEN E, GEN T)
    1047                 :            : {
    1048                 :            :   GEN a1, a3, b2, b4, b6;
    1049                 :      23317 :   a1 = Rg_to_Flxq(ell_get_a1(E),T,3);
    1050                 :      23317 :   a3 = Rg_to_Flxq(ell_get_a3(E),T,3);
    1051                 :      23317 :   b2 = Rg_to_Flxq(ell_get_b2(E),T,3);
    1052                 :      23317 :   b4 = Rg_to_Flxq(ell_get_b4(E),T,3);
    1053                 :      23317 :   b6 = Rg_to_Flxq(ell_get_b6(E),T,3);
    1054         [ +  + ]:      23317 :   if(lgpol(b2)) /* ordinary case */
    1055                 :            :   {
    1056                 :      16898 :     GEN b4b2 = Flxq_div(b4,b2,T,3);
    1057                 :      16898 :     GEN a6 = Flx_sub(b6,Flxq_mul(b4b2,Flx_add(b4,Flxq_sqr(b4b2,T,3),3),T,3),3);
    1058                 :      16898 :     retmkvec3(mkvec(b2), a6,
    1059                 :            :        mkvec4(Fl_to_Flx(1,T[1]),b4b2,Flx_neg(a1,3),Flx_neg(a3,3)));
    1060                 :            :   }
    1061                 :            :   else /* super-singular case */
    1062                 :      23317 :     retmkvec3(Flx_neg(b4, 3), b6,
    1063                 :            :        mkvec4(Fl_to_Flx(1,T[1]),zero_Flx(T[1]), Flx_neg(a1,3), Flx_neg(a3,3)));
    1064                 :            : }
    1065                 :            : 
    1066                 :            : static GEN
    1067                 :      80421 : Flxq_ell_to_a4a6(GEN E, GEN T, ulong p)
    1068                 :            : {
    1069                 :            :   GEN a1, a3, b2, c4, c6;
    1070         [ +  + ]:      80421 :   if(p==3) return F3xq_ell_to_a4a6(E, T);
    1071                 :      57104 :   a1 = Rg_to_Flxq(ell_get_a1(E),T,p);
    1072                 :      57104 :   a3 = Rg_to_Flxq(ell_get_a3(E),T,p);
    1073                 :      57104 :   b2 = Rg_to_Flxq(ell_get_b2(E),T,p);
    1074                 :      57104 :   c4 = Rg_to_Flxq(ell_get_c4(E),T,p);
    1075                 :      57104 :   c6 = Rg_to_Flxq(ell_get_c6(E),T,p);
    1076                 :      80421 :   retmkvec3(Flx_neg(Flx_mulu(c4, 27, p), p), Flx_neg(Flx_mulu(c6, 54, p), p),
    1077                 :            :             mkvec4(Fl_to_Flx(6%p,T[1]),Flx_mulu(b2,3,p),
    1078                 :            :                    Flx_mulu(a1,3,p),Flx_mulu(a3,108,p)));
    1079                 :            : }
    1080                 :            : 
    1081                 :            : static GEN
    1082                 :       7647 : F2xq_ell_to_a4a6(GEN E, GEN T)
    1083                 :            : {
    1084                 :       7647 :   long v = T[1];
    1085                 :       7647 :   GEN a1 = Rg_to_F2xq(ell_get_a1(E),T);
    1086                 :       7647 :   GEN a2 = Rg_to_F2xq(ell_get_a2(E),T);
    1087                 :       7647 :   GEN a3 = Rg_to_F2xq(ell_get_a3(E),T);
    1088                 :       7647 :   GEN a4 = Rg_to_F2xq(ell_get_a4(E),T);
    1089                 :       7647 :   GEN a6 = Rg_to_F2xq(ell_get_a6(E),T);
    1090         [ +  + ]:       7647 :   if (lgpol(a1))
    1091                 :            :   {
    1092                 :       7486 :     GEN a1i = F2xq_inv(a1,T);
    1093                 :       7486 :     GEN a1i2 = F2xq_sqr(a1i,T);
    1094                 :       7486 :     GEN a1i3 = F2xq_mul(a1i,a1i2,T);
    1095                 :       7485 :     GEN a1i6 = F2xq_sqr(a1i3,T);
    1096                 :       7486 :     GEN d  = F2xq_mul(a3,a1i,T);
    1097                 :       7486 :     GEN dd = F2xq_mul(d,a1i2,T);
    1098                 :       7486 :     GEN e  = F2xq_mul(F2x_add(a4,F2xq_sqr(d,T)),a1i,T);
    1099                 :       7486 :     GEN ee = F2xq_mul(e,a1i3,T);
    1100                 :       7485 :     GEN da2 = F2x_add(a2,d);
    1101                 :       7486 :     GEN d2 = F2xq_mul(da2,a1i2,T);
    1102                 :       7485 :     GEN d6 = F2xq_mul(F2x_add(F2x_add(F2xq_mul(F2x_add(F2xq_mul(da2,d,T),a4),d,T),a6),F2xq_sqr(e,T)),a1i6,T);
    1103                 :       7485 :     retmkvec3(d2, d6, mkvec4(a1i,dd,pol0_F2x(v),ee));
    1104                 :            :   }
    1105         [ +  + ]:        161 :   else if (lgpol(a3))
    1106                 :            :   {
    1107                 :        147 :     GEN d4 = F2x_add(F2xq_sqr(a2,T),a4);
    1108                 :        147 :     GEN d6 = F2x_add(F2xq_mul(a2,a4,T),a6);
    1109                 :        147 :     GEN a3i = F2xq_inv(a3,T);
    1110                 :        147 :     retmkvec3(mkvec3(a3,d4,a3i), d6, mkvec4(pol1_F2x(v),a2,pol0_F2x(T[1]),pol0_F2x(T[1])));
    1111                 :            :   }
    1112                 :       7647 :   return NULL;
    1113                 :            : }
    1114                 :            : 
    1115                 :            : static GEN
    1116                 :       1743 : FqV_to_FpXQV(GEN x, GEN T)
    1117                 :            : {
    1118                 :       1743 :   pari_sp av = avma;
    1119                 :       1743 :   long v = varn(T), i, s=0, l = lg(x);
    1120                 :       1743 :   GEN y = shallowcopy(x);
    1121         [ +  + ]:       8715 :   for(i=1; i<l; i++)
    1122         [ -  + ]:       6972 :     if (typ(gel(x,i))==t_INT)
    1123                 :            :     {
    1124                 :          0 :       gel(y,i) = scalarpol(gel(x,i), v);
    1125                 :          0 :       s = 1;
    1126                 :            :     }
    1127         [ +  - ]:       1743 :   if (!s) { avma = av; return x; }
    1128                 :       1743 :   return y;
    1129                 :            : }
    1130                 :            : 
    1131                 :            : GEN
    1132                 :      71360 : FF_ellcard(GEN E)
    1133                 :            : {
    1134                 :            :   GEN T,p;
    1135                 :            :   ulong pp;
    1136                 :      71360 :   GEN e = ellff_get_a4a6(E);
    1137                 :      71360 :   GEN fg = ellff_get_field(E);
    1138                 :      71361 :   _getFF(fg,&T,&p,&pp);
    1139      [ +  +  + ]:      71361 :   switch(fg[1])
    1140                 :            :   {
    1141                 :            :   case t_FF_FpXQ:
    1142                 :       1695 :     return FpXQ_ellcard(Fq_to_FpXQ(gel(e,1),T,p), Fq_to_FpXQ(gel(e,2),T,p),T,p);
    1143                 :            :   case t_FF_F2xq:
    1144                 :       7423 :     return F2xq_ellcard(gel(e,1),gel(e,2),T);
    1145                 :            :   default:
    1146                 :      71361 :     return Flxq_ellcard(gel(e,1),gel(e,2),T,pp);
    1147                 :            :   }
    1148                 :            : }
    1149                 :            : 
    1150                 :            : GEN
    1151                 :         14 : FF_ellcard_SEA(GEN E, long smallfact)
    1152                 :            : {
    1153                 :         14 :   pari_sp av = avma;
    1154                 :            :   GEN T,p;
    1155                 :            :   ulong pp;
    1156                 :         14 :   GEN e = ellff_get_a4a6(E), a4, a6, card;
    1157                 :         14 :   GEN fg = ellff_get_field(E);
    1158                 :         14 :   _getFF(fg,&T,&p,&pp);
    1159      [ -  -  + ]:         14 :   switch(fg[1])
    1160                 :            :   {
    1161                 :            :   case t_FF_FpXQ:
    1162                 :          0 :     a4 = Fq_to_FpXQ(gel(e,1), T, p);
    1163                 :          0 :     a6 = Fq_to_FpXQ(gel(e,2), T, p);
    1164                 :          0 :     card = Fq_ellcard_SEA(a4, a6, powiu(p,degpol(T)), T,p, smallfact);
    1165                 :          0 :     break;
    1166                 :            :   case t_FF_F2xq:
    1167                 :          0 :     pari_err_IMPL("SEA for char 2");
    1168                 :            :   default:
    1169                 :         14 :     a4 = Flx_to_ZX(gel(e,1));
    1170                 :         14 :     a6 = Flx_to_ZX(gel(e,2));
    1171                 :         14 :     card = Fq_ellcard_SEA(a4, a6, powuu(pp,degpol(T)), Flx_to_ZX(T), p, smallfact);
    1172                 :            :   }
    1173                 :         14 :   return gerepileuptoint(av, card);
    1174                 :            : }
    1175                 :            : 
    1176                 :            : /* return [G,m] */
    1177                 :            : GEN
    1178                 :      18053 : FF_ellgroup(GEN E)
    1179                 :            : {
    1180                 :            :   GEN T, p, e, fg, N, G, m;
    1181                 :            :   ulong pp;
    1182                 :            : 
    1183                 :      18053 :   N = ellff_get_card(E);
    1184                 :      18053 :   e = ellff_get_a4a6(E);
    1185                 :      18053 :   fg = ellff_get_field(E);
    1186                 :      18053 :   _getFF(fg,&T,&p,&pp);
    1187      [ +  +  + ]:      18053 :   switch(fg[1])
    1188                 :            :   {
    1189                 :            :   case t_FF_FpXQ:
    1190                 :         14 :     G = FpXQ_ellgroup(Fq_to_FpXQ(gel(e,1),T,p),Fq_to_FpXQ(gel(e,2),T,p),N,T,p,&m);
    1191                 :         14 :     break;
    1192                 :            :   case t_FF_F2xq:
    1193                 :       3654 :     G = F2xq_ellgroup(gel(e,1),gel(e,2),N,T,&m); break;
    1194                 :            :   default:
    1195                 :      14385 :     G = Flxq_ellgroup(gel(e,1),gel(e,2),N,T,pp,&m); break;
    1196                 :            :   }
    1197                 :      18053 :   return mkvec2(G,m);
    1198                 :            : }
    1199                 :            : 
    1200                 :            : GEN
    1201                 :      16744 : FF_ellgens(GEN E)
    1202                 :            : {
    1203                 :            :   GEN fg, e, Gm, G, m, T, p, F, e3;
    1204                 :            :   ulong pp;
    1205                 :            : 
    1206                 :      16744 :   fg = ellff_get_field(E);
    1207                 :      16744 :   e = ellff_get_a4a6(E);
    1208                 :      16744 :   Gm = ellff_get_group(E); G = gel(Gm,1); m = gel(Gm,2);
    1209                 :      16744 :   _getFF(fg,&T,&p,&pp);
    1210      [ +  +  + ]:      16744 :   switch(fg[1])
    1211                 :            :   {
    1212                 :            :   case t_FF_FpXQ:
    1213                 :          7 :     e3 = FqV_to_FpXQV(gel(e,3),T);
    1214                 :          7 :     F = FpXQ_ellgens(Fq_to_FpXQ(gel(e,1),T,p),Fq_to_FpXQ(gel(e,2),T,p),e3,G,m,T,p);
    1215                 :          7 :     break;
    1216                 :            :   case t_FF_F2xq:
    1217                 :       3584 :     F = F2xq_ellgens(gel(e,1),gel(e,2),gel(e,3),G,m,T);
    1218                 :       3584 :     break;
    1219                 :            :   default:
    1220                 :      13153 :     F = Flxq_ellgens(gel(e,1),gel(e,2),gel(e,3),G,m,T, pp);
    1221                 :      13153 :     break;
    1222                 :            :   }
    1223                 :      16744 :   return to_FFE_vec(F,fg);
    1224                 :            : }
    1225                 :            : 
    1226                 :            : GEN
    1227                 :        119 : FF_elldata(GEN E, GEN fg)
    1228                 :            : {
    1229                 :            :   GEN T,p,e;
    1230                 :            :   ulong pp;
    1231                 :        119 :   _getFF(fg,&T,&p,&pp);
    1232      [ -  +  + ]:        119 :   switch(fg[1])
    1233                 :            :   {
    1234                 :            :   case t_FF_FpXQ:
    1235                 :          0 :     e = FpXQ_ell_to_a4a6(E,T,p); break;
    1236                 :            :   case t_FF_F2xq:
    1237                 :         56 :     e = F2xq_ell_to_a4a6(E,T); break;
    1238                 :            :   default:
    1239                 :         63 :     e = Flxq_ell_to_a4a6(E,T,pp); break;
    1240                 :            :   }
    1241                 :        119 :   return mkvec2(fg,e);
    1242                 :            : }
    1243                 :            : 
    1244                 :            : GEN
    1245                 :      89659 : FF_ellinit(GEN E, GEN fg)
    1246                 :            : {
    1247                 :            :   GEN T,p,e;
    1248                 :            :   ulong pp;
    1249                 :            :   long i;
    1250                 :      89659 :   GEN y=E;
    1251                 :      89659 :   _getFF(fg,&T,&p,&pp);
    1252      [ +  +  + ]:      89659 :   switch(fg[1])
    1253                 :            :   {
    1254                 :            :   case t_FF_FpXQ:
    1255                 :       1710 :     e = FpXQ_ell_to_a4a6(E,T,p);
    1256         [ +  + ]:      22230 :     for(i=1;i<=12;i++)
    1257                 :      20520 :       gel(y,i) = mkFF_i(fg,Rg_to_FpXQ(gel(E,i),T,p));
    1258         [ -  + ]:       1710 :     if (FF_equal0(gel(y,12))) return NULL;
    1259                 :       1710 :     gel(y,i) = mkFF_i(fg,Rg_to_FpXQ(gel(E,i),T,p));
    1260                 :       1710 :     break;
    1261                 :            :   case t_FF_F2xq:
    1262                 :       7591 :     e = F2xq_ell_to_a4a6(E,T);
    1263         [ +  + ]:       7592 :     if (!e) return NULL;
    1264         [ +  + ]:      98498 :     for(i=1;i<=12;i++)
    1265                 :      90921 :       gel(y,i) = mkFF_i(fg,Rg_to_F2xq(gel(E,i),T));
    1266         [ -  + ]:       7577 :     if (FF_equal0(gel(y,12))) return NULL;
    1267                 :       7577 :     gel(y,i) = mkFF_i(fg,Rg_to_F2xq(gel(E,i),T));
    1268                 :       7577 :     break;
    1269                 :            :   default:
    1270                 :      80358 :     e = Flxq_ell_to_a4a6(E,T,pp);
    1271         [ +  + ]:    1044654 :     for(i=1;i<=12;i++)
    1272                 :     964296 :       gel(y,i) = mkFF_i(fg,Rg_to_Flxq(gel(E,i),T,pp));
    1273         [ -  + ]:      80358 :     if (FF_equal0(gel(y,12))) return NULL;
    1274                 :      80358 :     gel(y,i) = mkFF_i(fg,Rg_to_Flxq(gel(E,i),T,pp));
    1275                 :      80358 :     break;
    1276                 :            :   }
    1277                 :      89645 :   gel(y,14) = mkvecsmall(t_ELL_Fq);
    1278                 :      89645 :   gel(y,15) = mkvec2(fg,e);
    1279                 :      89659 :   return y;
    1280                 :            : }
    1281                 :            : 
    1282                 :            : GEN
    1283                 :      27188 : FF_elltwist(GEN E)
    1284                 :            : {
    1285                 :      27188 :   pari_sp av = avma;
    1286                 :      27188 :   GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E);
    1287                 :            :   GEN T, p, a, a6, V;
    1288                 :            :   ulong pp;
    1289                 :      27188 :   _getFF(fg,&T,&p,&pp);
    1290      [ +  +  + ]:      27188 :   switch (fg[1])
    1291                 :            :   {
    1292                 :            :   case t_FF_FpXQ:
    1293                 :        840 :     FpXQ_elltwist(gel(e,1), gel(e,2), T, p, &a, &a6);
    1294                 :        840 :     V = mkvec5(gen_0, gen_0, gen_0, mkFF_i(fg, a), mkFF_i(fg, a6));
    1295                 :        840 :     break;
    1296                 :            :   case t_FF_F2xq:
    1297                 :       3514 :     F2xq_elltwist(gel(e,1), gel(e,2), T, &a, &a6);
    1298                 :       7028 :     V = typ(a)==t_VECSMALL ?
    1299         [ +  - ]:       3514 :           mkvec5(gen_1, mkFF_i(fg, a), gen_0, gen_0, mkFF_i(fg, a6)):
    1300                 :          0 :           mkvec5(gen_0, gen_0, mkFF_i(fg, gel(a,1)), mkFF_i(fg, gel(a,2)), mkFF_i(fg, a6));
    1301                 :       3514 :     break;
    1302                 :            :   default:
    1303                 :      22834 :     Flxq_elltwist(gel(e,1), gel(e,2), T, pp, &a, &a6);
    1304                 :      22834 :     V = typ(a)==t_VECSMALL ?
    1305         [ +  + ]:      30436 :           mkvec5(gen_0, gen_0, gen_0, mkFF_i(fg, a), mkFF_i(fg, a6)):
    1306                 :       7602 :           mkvec5(gen_0, mkFF_i(fg, gel(a,1)), gen_0, gen_0, mkFF_i(fg, a6));
    1307                 :            :   }
    1308                 :      27188 :   return gerepilecopy(av, V);
    1309                 :            : }
    1310                 :            : 
    1311                 :            : static long
    1312                 :          0 : F3x_equalm1(GEN x)
    1313 [ #  # ][ #  # ]:          0 : { return degpol(x)==0 && x[2] == 2; }
    1314                 :            : 
    1315                 :            : GEN
    1316                 :      93604 : FF_ellrandom(GEN E)
    1317                 :            : {
    1318                 :      93604 :   pari_sp av = avma;
    1319                 :      93604 :   GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E), Q;
    1320                 :            :   GEN T,p;
    1321                 :            :   ulong pp;
    1322                 :      93604 :   _getFF(fg,&T,&p,&pp);
    1323      [ +  +  + ]:      93604 :   switch (fg[1])
    1324                 :            :   {
    1325                 :            :   case t_FF_FpXQ:
    1326                 :        854 :     Q = random_FpXQE(Fq_to_FpXQ(gel(e,1),T,p), Fq_to_FpXQ(gel(e,2),T,p), T, p);
    1327                 :        854 :     Q = FpXQE_changepoint(Q, FqV_to_FpXQV(gel(e,3), T) , T, p);
    1328                 :        854 :     break;
    1329                 :            :   case t_FF_F2xq:
    1330                 :            :     {
    1331                 :      17640 :       long d = F2x_degree(T);
    1332                 :            :       /* if #E(Fq) = 1 return [0] */
    1333 [ +  + ][ +  + ]:      17640 :       if (d<=2 && typ(gel(e,1)) == t_VEC)
    1334                 :            :       { /* over F2 or F4, supersingular */
    1335                 :          7 :         GEN v = gel(e,1), A6 = gel(e,2), a3 = gel(v,1), A4 = gel(v,2);
    1336 [ +  - ][ -  + ]:          7 :         if (F2x_equal1(a3) &&
    1337 [ #  # ][ #  # ]:          0 :              ((d==1 && F2x_equal1(A4) && F2x_equal1(A6))
    1338 [ +  - ][ -  + ]:          7 :            || (d==2 && !lgpol(A4)     && F2x_degree(A6)==1))) return ellinf();
                 [ #  # ]
    1339                 :            :       }
    1340                 :      17640 :       Q = random_F2xqE(gel(e,1), gel(e,2), T);
    1341                 :      17640 :       Q = F2xqE_changepoint(Q, gel(e,3), T);
    1342                 :      17640 :       break;
    1343                 :            :     }
    1344                 :            :   default:
    1345                 :            :     /* if #E(Fq) = 1 return [0] */
    1346 [ +  + ][ +  + ]:      75110 :     if (pp==3 && degpol(T)==1 && typ(gel(e,1))==t_VECSMALL)
                 [ -  + ]
    1347                 :            :     { /* over F3, supersingular */
    1348                 :          0 :       GEN mb4 = gel(e,1), b6 = gel(e,2);
    1349 [ #  # ][ #  # ]:          0 :       if (F3x_equalm1(mb4) && F3x_equalm1(b6)) return ellinf();
    1350                 :            :     }
    1351                 :      75110 :     Q = random_FlxqE(gel(e,1), gel(e,2), T, pp);
    1352                 :      75110 :     Q = FlxqE_changepoint(Q, gel(e,3), T, pp);
    1353                 :            :   }
    1354                 :      93604 :   return gerepilecopy(av, to_FFE(Q, fg));
    1355                 :            : }
    1356                 :            : 
    1357                 :            : GEN
    1358                 :      77280 : FF_ellmul(GEN E, GEN P, GEN n)
    1359                 :            : {
    1360                 :      77280 :   pari_sp av = avma;
    1361                 :      77280 :   GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E), Q;
    1362                 :            :   GEN T,p, Pp, Qp, e3;
    1363                 :            :   ulong pp;
    1364                 :      77280 :   _getFF(fg,&T,&p,&pp);
    1365      [ +  +  + ]:      77280 :   switch (fg[1])
    1366                 :            :   {
    1367                 :            :   case t_FF_FpXQ:
    1368                 :        854 :     e3 = FqV_to_FpXQV(gel(e,3),T);
    1369                 :        854 :     Pp = FpXQE_changepointinv(RgE_to_FpXQE(P, T, p), e3, T, p);
    1370                 :        854 :     Qp = FpXQE_mul(Pp, n, gel(e,1), T, p);
    1371                 :        854 :     Q = FpXQE_changepoint(Qp, gel(e,3), T, p);
    1372                 :        854 :     break;
    1373                 :            :   case t_FF_F2xq:
    1374                 :      14224 :     Pp = F2xqE_changepointinv(RgE_to_F2xqE(P, T), gel(e,3), T);
    1375                 :      14224 :     Qp = F2xqE_mul(Pp, n, gel(e,1), T);
    1376                 :      14224 :     Q = F2xqE_changepoint(Qp, gel(e,3), T);
    1377                 :      14224 :     break;
    1378                 :            :   default:
    1379                 :      62202 :     Pp = FlxqE_changepointinv(RgE_to_FlxqE(P, T, pp), gel(e,3), T, pp);
    1380                 :      62202 :     Qp = FlxqE_mul(Pp, n, gel(e,1), T, pp);
    1381                 :      62202 :     Q = FlxqE_changepoint(Qp, gel(e,3), T, pp);
    1382                 :            :   }
    1383                 :      77280 :   return gerepilecopy(av, to_FFE(Q, fg));
    1384                 :            : }
    1385                 :            : 
    1386                 :            : GEN
    1387                 :       1722 : FF_ellorder(GEN E, GEN P, GEN o)
    1388                 :            : {
    1389                 :       1722 :   pari_sp av = avma;
    1390                 :       1722 :   GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E);
    1391                 :            :   GEN r,T,p,Pp,e3;
    1392                 :            :   ulong pp;
    1393                 :       1722 :   _getFF(fg,&T,&p,&pp);
    1394      [ +  +  + ]:       1722 :   switch (fg[1])
    1395                 :            :   {
    1396                 :            :   case t_FF_FpXQ:
    1397                 :         14 :     e3 = FqV_to_FpXQV(gel(e,3),T);
    1398                 :         14 :     Pp = FpXQE_changepointinv(RgE_to_FpXQE(P,T,p), e3, T, p);
    1399                 :         14 :     r = FpXQE_order(Pp, o, gel(e,1), T, p);
    1400                 :         14 :     break;
    1401                 :            :   case t_FF_F2xq:
    1402                 :        280 :     Pp = F2xqE_changepointinv(RgE_to_F2xqE(P,T), gel(e,3), T);
    1403                 :        280 :     r = F2xqE_order(Pp, o, gel(e,1), T);
    1404                 :        280 :     break;
    1405                 :            :   default:
    1406                 :       1428 :     Pp = FlxqE_changepointinv(RgE_to_FlxqE(P,T,pp), gel(e,3), T, pp);
    1407                 :       1428 :     r = FlxqE_order(Pp, o, gel(e,1), T, pp);
    1408                 :            :   }
    1409                 :       1722 :   return gerepileupto(av, r);
    1410                 :            : }
    1411                 :            : 
    1412                 :            : GEN
    1413                 :         84 : FF_elllog(GEN E, GEN P, GEN Q, GEN o)
    1414                 :            : {
    1415                 :         84 :   pari_sp av = avma;
    1416                 :         84 :   GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E);
    1417                 :            :   GEN r,T,p, Pp,Qp, e3;
    1418                 :            :   ulong pp;
    1419                 :         84 :   _getFF(fg,&T,&p,&pp);
    1420      [ -  +  + ]:         84 :   switch(fg[1])
    1421                 :            :   {
    1422                 :            :   case t_FF_FpXQ:
    1423                 :          0 :     e3 = FqV_to_FpXQV(gel(e,3),T);
    1424                 :          0 :     Pp = FpXQE_changepointinv(RgE_to_FpXQE(P,T,p), e3, T, p);
    1425                 :          0 :     Qp = FpXQE_changepointinv(RgE_to_FpXQE(Q,T,p), e3, T, p);
    1426                 :          0 :     r = FpXQE_log(Pp, Qp, o, gel(e,1), T, p);
    1427                 :          0 :     break;
    1428                 :            :   case t_FF_F2xq:
    1429                 :         42 :     Pp = F2xqE_changepointinv(RgE_to_F2xqE(P,T), gel(e,3), T);
    1430                 :         42 :     Qp = F2xqE_changepointinv(RgE_to_F2xqE(Q,T), gel(e,3), T);
    1431                 :         42 :     r = F2xqE_log(Pp, Qp, o, gel(e,1), T);
    1432                 :         42 :     break;
    1433                 :            :   default:
    1434                 :         42 :     Pp = FlxqE_changepointinv(RgE_to_FlxqE(P,T,pp), gel(e,3), T, pp);
    1435                 :         42 :     Qp = FlxqE_changepointinv(RgE_to_FlxqE(Q,T,pp), gel(e,3), T, pp);
    1436                 :         42 :     r = FlxqE_log(Pp, Qp, o, gel(e,1), T, pp);
    1437                 :            :   }
    1438                 :         84 :   return gerepileupto(av, r);
    1439                 :            : }
    1440                 :            : 
    1441                 :            : GEN
    1442                 :         28 : FF_ellweilpairing(GEN E, GEN P, GEN Q, GEN m)
    1443                 :            : {
    1444                 :         28 :   GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E);
    1445                 :            :   GEN r,T,p, Pp,Qp, e3;
    1446                 :            :   ulong pp;
    1447                 :         28 :   GEN z=_initFF(fg,&T,&p,&pp);
    1448                 :         28 :   pari_sp av = avma;
    1449      [ +  +  + ]:         28 :   switch(fg[1])
    1450                 :            :   {
    1451                 :            :   case t_FF_FpXQ:
    1452                 :          7 :     e3 = FqV_to_FpXQV(gel(e,3),T);
    1453                 :          7 :     Pp = FpXQE_changepointinv(RgE_to_FpXQE(P,T,p), e3, T, p);
    1454                 :          7 :     Qp = FpXQE_changepointinv(RgE_to_FpXQE(Q,T,p), e3, T, p);
    1455                 :          7 :     r = FpXQE_weilpairing(Pp, Qp, m, gel(e,1), T, p);
    1456                 :          7 :     break;
    1457                 :            :   case t_FF_F2xq:
    1458                 :          7 :     Pp = F2xqE_changepointinv(RgE_to_F2xqE(P,T), gel(e,3), T);
    1459                 :          7 :     Qp = F2xqE_changepointinv(RgE_to_F2xqE(Q,T), gel(e,3), T);
    1460                 :          7 :     r = F2xqE_weilpairing(Pp, Qp, m, gel(e,1), T);
    1461                 :          7 :     break;
    1462                 :            :   default:
    1463                 :         14 :     Pp = FlxqE_changepointinv(RgE_to_FlxqE(P,T,pp), gel(e,3), T, pp);
    1464                 :         14 :     Qp = FlxqE_changepointinv(RgE_to_FlxqE(Q,T,pp), gel(e,3), T, pp);
    1465                 :         14 :     r = FlxqE_weilpairing(Pp, Qp, m, gel(e,1), T, pp);
    1466                 :            :   }
    1467                 :         28 :   r = gerepileupto(av, r);
    1468                 :         28 :   return _mkFF(fg,z,r);
    1469                 :            : }
    1470                 :            : 
    1471                 :            : GEN
    1472                 :         91 : FF_elltatepairing(GEN E, GEN P, GEN Q, GEN m)
    1473                 :            : {
    1474                 :         91 :   GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E);
    1475                 :            :   GEN r,T,p, Pp,Qp, e3;
    1476                 :            :   ulong pp;
    1477                 :         91 :   GEN z=_initFF(fg,&T,&p,&pp);
    1478                 :         91 :   pari_sp av = avma;
    1479      [ +  +  + ]:         91 :   switch(fg[1])
    1480                 :            :   {
    1481                 :            :   case t_FF_FpXQ:
    1482                 :          7 :     e3 = FqV_to_FpXQV(gel(e,3),T);
    1483                 :          7 :     Pp = FpXQE_changepointinv(RgE_to_FpXQE(P,T,p), e3, T, p);
    1484                 :          7 :     Qp = FpXQE_changepointinv(RgE_to_FpXQE(Q,T,p), e3, T, p);
    1485                 :          7 :     r = FpXQE_tatepairing(Pp, Qp, m, gel(e,1), T, p);
    1486                 :          7 :     break;
    1487                 :            :   case t_FF_F2xq:
    1488                 :         28 :     Pp = F2xqE_changepointinv(RgE_to_F2xqE(P,T), gel(e,3), T);
    1489                 :         28 :     Qp = F2xqE_changepointinv(RgE_to_F2xqE(Q,T), gel(e,3), T);
    1490                 :         28 :     r = F2xqE_tatepairing(Pp, Qp, m, gel(e,1), T);
    1491                 :         28 :     break;
    1492                 :            :   default:
    1493                 :         56 :     Pp = FlxqE_changepointinv(RgE_to_FlxqE(P,T,pp), gel(e,3), T, pp);
    1494                 :         56 :     Qp = FlxqE_changepointinv(RgE_to_FlxqE(Q,T,pp), gel(e,3), T, pp);
    1495                 :         56 :     r = FlxqE_tatepairing(Pp, Qp, m, gel(e,1), T, pp);
    1496                 :            :   }
    1497                 :         91 :   r = gerepileupto(av, r);
    1498                 :         91 :   return _mkFF(fg,z,r);
    1499                 :            : }
    1500                 :            : 
    1501                 :            : GEN
    1502                 :     103439 : FFX_roots(GEN Pf, GEN ff)
    1503                 :            : {
    1504                 :     103439 :   pari_sp av = avma;
    1505                 :            :   GEN r,T,p;
    1506                 :            :   ulong pp;
    1507                 :     103439 :   GEN P = FFX_to_raw(Pf, ff);
    1508                 :     103439 :   _getFF(ff,&T,&p,&pp);
    1509      [ +  +  + ]:     103439 :   switch(ff[1])
    1510                 :            :   {
    1511                 :            :   case t_FF_FpXQ:
    1512                 :         15 :     r = FpXQX_roots(P, T, p);
    1513                 :         15 :     break;
    1514                 :            :   case t_FF_F2xq:
    1515                 :      57442 :     r = F2xqX_roots(P, T);
    1516                 :      57442 :     break;
    1517                 :            :   default:
    1518                 :      45982 :     r = FlxqX_roots(P, T, pp);
    1519                 :            :   }
    1520                 :     103439 :   r = raw_to_FFC(r, ff);
    1521                 :     103439 :   return gerepilecopy(av, r);
    1522                 :            : }
    1523                 :            : 
    1524                 :            : GEN
    1525                 :         70 : FqX_to_FFX(GEN x, GEN ff)
    1526                 :            : {
    1527                 :            :   long i, lx;
    1528                 :         70 :   GEN y =  cgetg_copy(x,&lx);
    1529                 :         70 :   y[1] = x[1];
    1530         [ +  + ]:        728 :   for (i=2; i<lx; i++) gel(y,i) = Fq_to_FF(gel(x,i), ff);
    1531                 :         70 :   return y;
    1532                 :            : }
    1533                 :            : 
    1534                 :            : /* P vector of t_POL, E t_VECSMALL of exponents, ff a t_FFELT. Update elts of
    1535                 :            :  * P so that 1) variable number is vP, 2) coefficients are ff-compatible.
    1536                 :            :  * Collect garbage wrt av */
    1537                 :            : static GEN
    1538                 :         77 : to_FF_fact(long vP, GEN P, GEN E, GEN ff, pari_sp av)
    1539                 :            : {
    1540                 :         77 :   GEN y = cgetg(3,t_MAT), u, v, zf;
    1541                 :         77 :   long j, l = lg(P), nbf = lg(P);
    1542                 :            : 
    1543                 :         77 :   u = cgetg(nbf,t_COL); gel(y,1) = u;
    1544                 :         77 :   v = cgetg(nbf,t_COL); gel(y,2) = v;
    1545         [ +  + ]:        441 :   for (j=1; j<l; j++)
    1546                 :            :   {
    1547                 :        364 :     GEN Q = simplify_shallow(gel(P,j)); /* may contain pols of degree 0 */
    1548         [ +  - ]:        364 :     if (typ(Q) == t_POL) setvarn(Q, vP);
    1549                 :        364 :     gel(u,j) = Q;
    1550                 :        364 :     gel(v,j) = utoi(uel(E,j));
    1551                 :            :   }
    1552                 :         77 :   y = gerepilecopy(av, y); u = gel(y,1);
    1553                 :         77 :   zf = FF_zero(ff);
    1554         [ +  + ]:        441 :   for (j=1; j<nbf; j++) gel(u,j) = to_FFX(gel(u,j), zf);
    1555                 :         77 :   return y;
    1556                 :            : }
    1557                 :            : 
    1558                 :            : static GEN
    1559                 :         77 : FFX_init_fix_varn(GEN P, GEN x, GEN *pT, GEN *pp)
    1560                 :            : {
    1561                 :            :   ulong junk;
    1562                 :            :   GEN Q, T, p;
    1563                 :            : 
    1564                 :         77 :   _getFF(x, &T, &p, &junk);
    1565      [ +  +  + ]:         77 :   switch(x[1])
    1566                 :            :   {
    1567                 :            :   case t_FF_FpXQ:
    1568                 :          9 :     T=shallowcopy(T);
    1569                 :          9 :     break;
    1570                 :            :   case t_FF_F2xq:
    1571                 :         21 :     T=F2x_to_ZX(T);
    1572                 :         21 :     break;
    1573                 :            :   default:
    1574                 :         47 :     T=Flx_to_ZX(T);
    1575                 :            :   }
    1576                 :         77 :   setvarn(T, 1);
    1577                 :         77 :   Q = RgX_to_FqX(P, T,p);
    1578                 :         77 :   setvarn(Q, 0);
    1579                 :            : 
    1580                 :         77 :   *pT = T;
    1581                 :         77 :   *pp = p; return Q;
    1582                 :            : }
    1583                 :            : 
    1584                 :            : /* Factor P over the field of definition of x */
    1585                 :            : GEN
    1586                 :         77 : FFX_factor(GEN P, GEN x)
    1587                 :            : {
    1588                 :         77 :   long vP = varn(P);
    1589                 :            :   GEN r, T, p;
    1590                 :         77 :   pari_sp av=avma;
    1591                 :            : 
    1592                 :         77 :   P = FFX_init_fix_varn(P, x, &T, &p);
    1593                 :         77 :   r = FpXQX_factor(P, T,p);
    1594                 :         77 :   return to_FF_fact(vP, gel(r,1),gel(r,2), x,av);
    1595                 :            : }
    1596                 :            : 
    1597                 :            : GEN
    1598                 :       1836 : ffgen(GEN T, long v)
    1599                 :            : {
    1600                 :       1836 :   GEN A, p = NULL, ff = cgetg(5,t_FFELT);
    1601                 :            :   long d;
    1602   [ +  +  +  - ]:       1835 :   switch(typ(T))
    1603                 :            :   {
    1604                 :            :     case t_POL:
    1605                 :        210 :       d = degpol(T); p = NULL;
    1606 [ +  - ][ +  - ]:        210 :       if (d < 1 || !RgX_is_FpX(T, &p) || !p) pari_err_TYPE("ffgen",T);
                 [ -  + ]
    1607                 :        210 :       T = RgX_to_FpX(T, p);
    1608                 :            :       /* testing for irreducibility is too costly */
    1609         [ +  + ]:        210 :       if (!FpX_is_squarefree(T,p)) pari_err_IRREDPOL("ffgen",T);
    1610                 :        204 :       break;
    1611                 :            :     case t_INT:
    1612                 :       1521 :       d = ispseudoprimepower(T,&p);
    1613         [ -  + ]:       1520 :       if (!d) pari_err_PRIME("ffgen",T);
    1614                 :       1520 :       T = init_Fq(p, d, v);
    1615                 :       1521 :       break;
    1616                 :            :     case t_VEC: case t_COL:
    1617         [ +  - ]:        105 :       if (lg(T) == 3) {
    1618                 :        105 :         p = gel(T,1);
    1619                 :        105 :         A = gel(T,2);
    1620 [ +  - ][ +  - ]:        105 :         if (typ(p) == t_INT && typ(A) == t_INT)
    1621                 :            :         {
    1622                 :        105 :           d = itos(A);
    1623                 :        105 :           T = init_Fq(p, d, v);
    1624                 :        105 :           break;
    1625                 :            :         }
    1626                 :            :       }
    1627                 :            :     default:
    1628                 :          0 :       pari_err_TYPE("ffgen",T);
    1629                 :          0 :       return NULL;
    1630                 :            :   }
    1631         [ +  + ]:       1830 :   if (v < 0) v = varn(T);
    1632         [ +  + ]:       1830 :   if (lgefint(p)==3)
    1633                 :            :   {
    1634                 :       1648 :     ulong pp = p[2];
    1635                 :       1648 :     long sv = evalvarn(v);
    1636         [ +  + ]:       1648 :     if (pp==2)
    1637                 :            :     {
    1638                 :        710 :       ff[1] = t_FF_F2xq;
    1639                 :        710 :       T = ZX_to_F2x(T); T[1] = sv;
    1640         [ +  + ]:        709 :       A = polx_F2x(sv); if (d == 1) A = F2x_rem(A, T);
    1641                 :        709 :       p = gen_2;
    1642                 :            :     }
    1643                 :            :     else
    1644                 :            :     {
    1645                 :        938 :       ff[1] = t_FF_Flxq;
    1646                 :        938 :       T = ZX_to_Flx(T,pp); T[1] = sv;
    1647         [ +  + ]:        938 :       A = polx_Flx(sv); if (d == 1) A = Flx_rem(A, T, pp);
    1648                 :        938 :       p = icopy(p);
    1649                 :            :     }
    1650                 :            :   }
    1651                 :            :   else
    1652                 :            :   {
    1653                 :        182 :     ff[1] = t_FF_FpXQ;
    1654                 :        182 :     setvarn(T,v);
    1655         [ +  + ]:        182 :     A = pol_x(v); if (d == 1) A = FpX_rem(A, T, p);
    1656                 :        182 :     p = icopy(p);
    1657                 :            :   }
    1658                 :       1829 :   gel(ff,2) = A;
    1659                 :       1829 :   gel(ff,3) = T;
    1660                 :       1829 :   gel(ff,4) = p; return ff;
    1661                 :            : }
    1662                 :            : 
    1663                 :            : GEN
    1664                 :       2583 : p_to_FF(GEN p, long v)
    1665                 :            : {
    1666                 :            :   GEN A, T;
    1667                 :       2583 :   GEN ff = cgetg(5,t_FFELT);
    1668         [ +  + ]:       2583 :   if (lgefint(p)==3)
    1669                 :            :   {
    1670                 :       2579 :     ulong pp = p[2];
    1671                 :       2579 :     long sv = evalvarn(v);
    1672         [ +  + ]:       2579 :     if (pp==2)
    1673                 :            :     {
    1674                 :        182 :       ff[1] = t_FF_F2xq;
    1675                 :        182 :       T = polx_F2x(sv);
    1676                 :        182 :       A = pol1_F2x(sv);
    1677                 :        182 :       p = gen_2;
    1678                 :            :     }
    1679                 :            :     else
    1680                 :            :     {
    1681                 :       2397 :       ff[1] = t_FF_Flxq;
    1682                 :       2397 :       T = polx_Flx(sv);
    1683                 :       2397 :       A = pol1_Flx(sv);
    1684                 :       2397 :       p = icopy(p);
    1685                 :            :     }
    1686                 :            :   }
    1687                 :            :   else
    1688                 :            :   {
    1689                 :          4 :     ff[1] = t_FF_FpXQ;
    1690                 :          4 :     T = pol_x(v);
    1691                 :          4 :     A = pol_1(v);
    1692                 :          4 :     p = icopy(p);
    1693                 :            :   }
    1694                 :       2583 :   gel(ff,2) = A;
    1695                 :       2583 :   gel(ff,3) = T;
    1696                 :       2583 :   gel(ff,4) = p; return ff;
    1697                 :            : }
    1698                 :            : GEN
    1699                 :      15204 : Tp_to_FF(GEN T, GEN p)
    1700                 :            : {
    1701                 :            :   GEN A, ff;
    1702                 :            :   long v;
    1703         [ -  + ]:      15204 :   if (!T) return p_to_FF(p,0);
    1704                 :      15204 :   ff = cgetg(5,t_FFELT);
    1705                 :      15204 :   v = varn(T);
    1706         [ +  - ]:      15204 :   if (lgefint(p)==3)
    1707                 :            :   {
    1708                 :      15204 :     ulong pp = p[2];
    1709                 :      15204 :     long sv = evalvarn(v);
    1710         [ -  + ]:      15204 :     if (pp==2)
    1711                 :            :     {
    1712                 :          0 :       ff[1] = t_FF_F2xq;
    1713                 :          0 :       T = ZX_to_F2x(T);
    1714                 :          0 :       A = pol1_F2x(sv);
    1715                 :          0 :       p = gen_2;
    1716                 :            :     }
    1717                 :            :     else
    1718                 :            :     {
    1719                 :      15204 :       ff[1] = t_FF_Flxq;
    1720                 :      15204 :       T = ZX_to_Flx(T, pp);
    1721                 :      15204 :       A = pol1_Flx(sv);
    1722                 :      15204 :       p = icopy(p);
    1723                 :            :     }
    1724                 :            :   }
    1725                 :            :   else
    1726                 :            :   {
    1727                 :          0 :     ff[1] = t_FF_FpXQ;
    1728                 :          0 :     T = ZX_copy(T);
    1729                 :          0 :     A = pol_1(v);
    1730                 :          0 :     p = icopy(p);
    1731                 :            :   }
    1732                 :      15204 :   gel(ff,2) = A;
    1733                 :      15204 :   gel(ff,3) = T;
    1734                 :      15204 :   gel(ff,4) = p; return ff;
    1735                 :            : }
    1736                 :            : 
    1737                 :            : GEN
    1738                 :         28 : fforder(GEN x, GEN o)
    1739                 :            : {
    1740         [ -  + ]:         28 :   if (typ(x)!=t_FFELT) pari_err_TYPE("fforder",x);
    1741                 :         28 :   return FF_order(x,o);
    1742                 :            : }
    1743                 :            : 
    1744                 :            : GEN
    1745                 :        322 : ffprimroot(GEN x, GEN *o)
    1746                 :            : {
    1747         [ -  + ]:        322 :   if (typ(x)!=t_FFELT) pari_err_TYPE("ffprimroot",x);
    1748                 :        322 :   return FF_primroot(x,o);
    1749                 :            : }
    1750                 :            : 
    1751                 :            : GEN
    1752                 :        168 : fflog(GEN x, GEN g, GEN o)
    1753                 :            : {
    1754         [ -  + ]:        168 :   if (typ(x)!=t_FFELT) pari_err_TYPE("fflog",x);
    1755         [ -  + ]:        168 :   if (typ(g)!=t_FFELT) pari_err_TYPE("fflog",g);
    1756                 :        168 :   return FF_log(x,g,o);
    1757                 :            : }
    1758                 :            : 
    1759                 :            : GEN
    1760                 :      14924 : ffrandom(GEN ff)
    1761                 :            : {
    1762                 :            :   ulong pp;
    1763                 :      14924 :   GEN r, T, p, z = _initFF(ff,&T,&p,&pp);
    1764      [ +  +  + ]:      14924 :   switch(ff[1])
    1765                 :            :   {
    1766                 :            :   case t_FF_FpXQ:
    1767                 :        948 :     r = random_FpX(degpol(T), varn(T), p);
    1768                 :        948 :     break;
    1769                 :            :   case t_FF_F2xq:
    1770                 :          7 :     r = random_F2x(F2x_degree(T), T[1]);
    1771                 :          7 :     break;
    1772                 :            :   default:
    1773                 :      13969 :     r = random_Flx(degpol(T), T[1], pp);
    1774                 :            :   }
    1775                 :      14924 :   return _mkFF(ff,z,r);
    1776                 :            : }
    1777                 :            : 
    1778                 :            : int
    1779                 :    7558771 : Rg_is_FF(GEN c, GEN *ff)
    1780                 :            : {
    1781         [ +  + ]:    7558771 :   switch(typ(c))
    1782                 :            :   {
    1783                 :            :   case t_FFELT:
    1784         [ +  + ]:      26712 :     if (!*ff) *ff = c;
    1785         [ -  + ]:      26250 :     else if (!FF_samefield(*ff, c)) return 0;
    1786                 :      26712 :     break;
    1787                 :            :   default:
    1788                 :    7532059 :     return 0;
    1789                 :            :   }
    1790                 :    7558771 :   return 1;
    1791                 :            : }
    1792                 :            : 
    1793                 :            : int
    1794                 :    7535195 : RgC_is_FFC(GEN x, GEN *ff)
    1795                 :            : {
    1796                 :    7535195 :   long i, lx = lg(x);
    1797         [ +  + ]:    7561907 :   for (i=lx-1; i>0; i--)
    1798         [ +  + ]:    7558771 :     if (!Rg_is_FF(gel(x,i), ff)) return 0;
    1799                 :    7535195 :   return (*ff != NULL);
    1800                 :            : }
    1801                 :            : 
    1802                 :            : int
    1803                 :    7533410 : RgM_is_FFM(GEN x, GEN *ff)
    1804                 :            : {
    1805                 :    7533410 :   long j, lx = lg(x);
    1806         [ +  + ]:    7536476 :   for (j=lx-1; j>0; j--)
    1807         [ +  + ]:    7535174 :     if (!RgC_is_FFC(gel(x,j), ff)) return 0;
    1808                 :    7533410 :   return (*ff != NULL);
    1809                 :            : }
    1810                 :            : 
    1811                 :            : static GEN
    1812                 :         63 : FqC_to_FpXQC(GEN x, GEN T, GEN p)
    1813                 :            : {
    1814                 :            :   long i, lx;
    1815                 :         63 :   GEN y = cgetg_copy(x,&lx);
    1816         [ +  + ]:        217 :   for(i=1; i<lx; i++)
    1817                 :        154 :     gel(y, i) = Fq_to_FpXQ(gel(x, i), T, p);
    1818                 :         63 :   return y;
    1819                 :            : }
    1820                 :            : 
    1821                 :            : static GEN
    1822                 :         28 : FqM_to_FpXQM(GEN x, GEN T, GEN p)
    1823                 :            : {
    1824                 :            :   long i, lx;
    1825                 :         28 :   GEN y = cgetg_copy(x,&lx);
    1826         [ +  + ]:         91 :   for(i=1; i<lx; i++)
    1827                 :         63 :     gel(y, i) = FqC_to_FpXQC(gel(x, i), T, p);
    1828                 :         28 :   return y;
    1829                 :            : }
    1830                 :            : 
    1831                 :            : static GEN
    1832                 :         84 : FFM_wrap(GEN M, GEN ff, GEN (*Fq)(GEN,GEN,GEN),
    1833                 :            :                        GEN (*Flxq)(GEN,GEN,ulong),
    1834                 :            :                        GEN (*F2xq)(GEN,GEN))
    1835                 :            : {
    1836                 :         84 :   pari_sp av = avma;
    1837                 :            :   ulong pp;
    1838                 :            :   GEN T, p;
    1839                 :         84 :   _getFF(ff,&T,&p,&pp); M = FFM_to_raw(M);
    1840      [ +  +  + ]:         84 :   switch(ff[1])
    1841                 :            :   {
    1842                 :         28 :   case t_FF_FpXQ: M = FqM_to_FpXQM(Fq(M,T,p), T, p); break;
    1843                 :         28 :   case t_FF_F2xq: M = F2xq(M,T); break;
    1844                 :         28 :   default: M = Flxq(M,T,pp); break;
    1845                 :            :   }
    1846                 :         84 :   return gerepilecopy(av, raw_to_FFM(M, ff));
    1847                 :            : }
    1848                 :            : GEN
    1849                 :         21 : FFM_ker(GEN M, GEN ff)
    1850                 :         21 : { return FFM_wrap(M,ff, &FqM_ker,&FlxqM_ker,&F2xqM_ker); }
    1851                 :            : GEN
    1852                 :         21 : FFM_image(GEN M, GEN ff)
    1853                 :         21 : { return FFM_wrap(M,ff, &FqM_image,&FlxqM_image,&F2xqM_image); }
    1854                 :            : GEN
    1855                 :         42 : FFM_inv(GEN M, GEN ff)
    1856                 :         42 : { return FFM_wrap(M,ff, &FqM_inv,&FlxqM_inv,&F2xqM_inv); }
    1857                 :            : long
    1858                 :         21 : FFM_rank(GEN M, GEN ff)
    1859                 :            : {
    1860                 :         21 :   pari_sp av = avma;
    1861                 :            :   long r;
    1862                 :            :   ulong pp;
    1863                 :            :   GEN T, p;
    1864                 :         21 :   _getFF(ff,&T,&p,&pp); M = FFM_to_raw(M);
    1865      [ +  +  + ]:         21 :   switch(ff[1])
    1866                 :            :   {
    1867                 :          7 :   case t_FF_FpXQ: r = FqM_rank(M,T,p); break;
    1868                 :          7 :   case t_FF_F2xq: r = F2xqM_rank(M,T); break;
    1869                 :          7 :   default: r = FlxqM_rank(M,T,pp); break;
    1870                 :            :   }
    1871                 :         21 :   avma = av; return r;
    1872                 :            : }
    1873                 :            : GEN
    1874                 :         21 : FFM_det(GEN M, GEN ff)
    1875                 :            : {
    1876                 :         21 :   pari_sp av = avma;
    1877                 :            :   ulong pp;
    1878                 :            :   GEN d, T, p;
    1879                 :         21 :   _getFF(ff,&T,&p,&pp); M = FFM_to_raw(M);
    1880      [ +  +  + ]:         21 :   switch(ff[1])
    1881                 :            :   {
    1882                 :          7 :   case t_FF_FpXQ: d = FqM_det(M,T,p); break;
    1883                 :          7 :   case t_FF_F2xq: d = F2xqM_det(M,T); break;
    1884                 :          7 :   default: d = FlxqM_det(M,T,pp); break;
    1885                 :            :   }
    1886                 :         21 :   return gerepilecopy(av, mkFF_i(ff, d));
    1887                 :            : }
    1888                 :            : 
    1889                 :            : GEN
    1890                 :         21 : FFM_FFC_mul(GEN M, GEN C, GEN ff)
    1891                 :            : {
    1892                 :         21 :   pari_sp av = avma;
    1893                 :            :   ulong pp;
    1894                 :            :   GEN P, T, p;
    1895                 :         21 :   _getFF(ff, &T, &p, &pp);
    1896                 :         21 :   M = FFM_to_raw(M);
    1897                 :         21 :   C = FFC_to_raw(C);
    1898      [ +  +  + ]:         21 :   switch (ff[1])
    1899                 :            :   {
    1900                 :          7 :   case t_FF_FpXQ: P = FqM_FqC_mul(M, C, T, p); break;
    1901                 :          7 :   case t_FF_F2xq: P = F2xqM_F2xqC_mul(M, C, T); break;
    1902                 :          7 :   default: P = FlxqM_FlxqC_mul(M, C, T, pp); break;
    1903                 :            :   }
    1904                 :         21 :   return gerepilecopy(av, raw_to_FFC(P, ff));
    1905                 :            : }
    1906                 :            : 
    1907                 :            : GEN
    1908                 :        161 : FFM_mul(GEN M, GEN N, GEN ff)
    1909                 :            : {
    1910                 :        161 :   pari_sp av = avma;
    1911                 :            :   ulong pp;
    1912                 :            :   GEN P, T, p;
    1913                 :        161 :   int is_sqr = M==N;
    1914                 :        161 :   _getFF(ff, &T, &p, &pp);
    1915                 :        161 :   M = FFM_to_raw(M);
    1916         [ +  + ]:        161 :   N = is_sqr? M: FFM_to_raw(N);
    1917      [ +  +  + ]:        161 :   switch (ff[1])
    1918                 :            :   {
    1919                 :         12 :   case t_FF_FpXQ: P = FqM_mul(M, N, T, p); break;
    1920                 :          7 :   case t_FF_F2xq: P = F2xqM_mul(M, N, T); break;
    1921                 :        142 :   default: P = FlxqM_mul(M, N, T, pp); break;
    1922                 :            :   }
    1923                 :        161 :   return gerepilecopy(av, raw_to_FFM(P, ff));
    1924                 :            : }

Generated by: LCOV version 1.9