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 to exceed 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.12.0 lcov report (development 23690-5d6e28857) Lines: 1122 1183 94.8 %
Date: 2019-03-18 05:43:21 Functions: 137 143 95.8 %
Legend: Lines: hit not hit

          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    38391047 : _getFF(GEN x, GEN *T, GEN *p, ulong *pp)
      31             : {
      32    38391047 :   *T=gel(x,3);
      33    38391047 :   *p=gel(x,4);
      34    38391047 :   *pp=(*p)[2];
      35    38391047 : }
      36             : 
      37             : INLINE GEN
      38    36916652 : _initFF(GEN x, GEN *T, GEN *p, ulong *pp)
      39             : {
      40    36916652 :   _getFF(x,T,p,pp);
      41    36916668 :   return cgetg(5,t_FFELT);
      42             : }
      43             : 
      44             : INLINE void
      45    29220368 : _checkFF(GEN x, GEN y, const char *s)
      46    29220368 : { if (!FF_samefield(x,y)) pari_err_OP(s,x,y); }
      47             : 
      48             : INLINE GEN
      49    36699837 : _mkFF(GEN x, GEN z, GEN r)
      50             : {
      51    36699837 :   z[1]=x[1];
      52    36699837 :   gel(z,2)=r;
      53    36699837 :   gel(z,3)=gcopy(gel(x,3));
      54    36699903 :   gel(z,4)=icopy(gel(x,4));
      55    36699903 :   return z;
      56             : }
      57             : 
      58             : INLINE GEN
      59     3285738 : _mkFF_i(GEN x, GEN z, GEN r)
      60             : {
      61     3285738 :   z[1]=x[1];
      62     3285738 :   gel(z,2)=r;
      63     3285738 :   gel(z,3)=gel(x,3);
      64     3285738 :   gel(z,4)=gel(x,4);
      65     3285738 :   return z;
      66             : }
      67             : 
      68             : INLINE GEN
      69     3068950 : mkFF_i(GEN x, GEN r)
      70             : {
      71     3068950 :   GEN z = cgetg(5,t_FFELT);
      72     3068961 :   return _mkFF_i(x,z,r);
      73             : }
      74             : 
      75             : /*************************************************************************/
      76             : /**                                                                     **/
      77             : /**                   medium-level constructors                         **/
      78             : /**                                                                     **/
      79             : /*************************************************************************/
      80             : 
      81             : static GEN
      82      431361 : Z_to_raw(GEN x, GEN ff)
      83             : {
      84             :   ulong pp;
      85             :   GEN T, p;
      86      431361 :   _getFF(ff,&T,&p,&pp);
      87      431361 :   switch(ff[1])
      88             :   {
      89             :   case t_FF_FpXQ:
      90       10914 :     return scalarpol(x, varn(T));
      91             :   case t_FF_F2xq:
      92      202174 :     return Z_to_F2x(x,varn(T));
      93             :   default:
      94      218273 :     return Z_to_Flx(x,pp,T[1]);
      95             :   }
      96             : }
      97             : 
      98             : static GEN
      99     2233104 : Rg_to_raw(GEN x, GEN ff)
     100             : {
     101     2233104 :   long tx = typ(x);
     102     2233104 :   switch(tx)
     103             :   {
     104             :   case t_INT: case t_FRAC: case t_PADIC: case t_INTMOD:
     105      431361 :     return Z_to_raw(Rg_to_Fp(x, FF_p_i(ff)), ff);
     106             :   case t_FFELT:
     107     1801743 :     if (!FF_samefield(x,ff))
     108           0 :       pari_err_MODULUS("Rg_to_raw",x,ff);
     109     1801743 :     return gel(x,2);
     110             :   }
     111           0 :   pari_err_TYPE("Rg_to_raw",x);
     112             :   return NULL; /* LCOV_EXCL_LINE */
     113             : }
     114             : 
     115             : static GEN
     116      322485 : FFX_to_raw(GEN x, GEN ff)
     117             : {
     118             :   long i, lx;
     119      322485 :   GEN y = cgetg_copy(x,&lx);
     120      322485 :   y[1] = x[1];
     121     1876673 :   for(i=2; i<lx; i++)
     122     1554188 :     gel(y, i) = Rg_to_raw(gel(x, i), ff);
     123      322485 :   switch (ff[1])
     124             :   {
     125             :   case t_FF_FpXQ:
     126        5647 :     return FpXX_renormalize(y, lx);
     127             :   case t_FF_F2xq:
     128      138984 :     return F2xX_renormalize(y, lx);
     129             :   default:
     130      177854 :     return FlxX_renormalize(y, lx);
     131             :   }
     132             : }
     133             : 
     134             : static GEN
     135       44058 : FFC_to_raw(GEN x, GEN ff)
     136       44058 : { pari_APPLY_same(Rg_to_raw(gel(x, i), ff)) }
     137             : 
     138             : static GEN
     139        9555 : FFM_to_raw(GEN x, GEN ff)
     140        9555 : { pari_APPLY_same(FFC_to_raw(gel(x, i), ff)) }
     141             : 
     142             : /* in place */
     143             : static GEN
     144      654648 : rawFq_to_FF(GEN x, GEN ff)
     145             : {
     146      654648 :   return mkFF_i(ff, typ(x)==t_INT ? scalarpol(x, varn(gel(ff,3))): x);
     147             : }
     148             : 
     149             : /* in place */
     150             : static GEN
     151      109351 : raw_to_FFX(GEN x, GEN ff)
     152             : {
     153      109351 :   long i, lx = lg(x);
     154      109351 :   for (i=2; i<lx; i++) gel(x,i) = rawFq_to_FF(gel(x,i), ff);
     155      109351 :   return x;
     156             : }
     157             : 
     158             : /* in place */
     159             : static GEN
     160      124663 : raw_to_FFC(GEN x, GEN ff)
     161             : {
     162      124663 :   long i, lx = lg(x);
     163      124663 :   for (i=1; i<lx; i++) gel(x,i) = mkFF_i(ff, gel(x,i));
     164      124663 :   return x;
     165             : }
     166             : 
     167             : /* in place */
     168             : static GEN
     169        4648 : raw_to_FFM(GEN x, GEN ff)
     170             : {
     171        4648 :   long i, lx = lg(x);
     172        4648 :   for (i=1; i<lx; i++) gel(x,i) = raw_to_FFC(gel(x,i), ff);
     173        4648 :   return x;
     174             : }
     175             : 
     176             : GEN
     177      131761 : Fq_to_FF(GEN x, GEN ff)
     178             : {
     179             :   ulong pp;
     180      131761 :   GEN r, T, p, z=_initFF(ff,&T,&p,&pp);
     181      131761 :   int is_int = typ(x)==t_INT;
     182      131761 :   switch(ff[1])
     183             :   {
     184             :   case t_FF_FpXQ:
     185        6944 :     r= is_int ? scalarpol(x, varn(T)): x;
     186        6944 :     break;
     187             :   case t_FF_F2xq:
     188       45150 :     r= is_int ? Z_to_F2x(x,T[1]): ZX_to_F2x(x);
     189       45150 :     break;
     190             :   default:
     191       79667 :     r= is_int ? Z_to_Flx(x,pp,T[1]): ZX_to_Flx(x,pp);
     192             :   }
     193      131761 :   setvarn(r, varn(T)); /* paranoia */
     194      131761 :   return _mkFF_i(ff,z,r);
     195             : }
     196             : 
     197             : /*************************************************************************/
     198             : /**                                                                     **/
     199             : /**                   Public functions                                  **/
     200             : /**                                                                     **/
     201             : /*************************************************************************/
     202             : 
     203             : /* Return true if x and y are defined in the same field */
     204             : 
     205             : static int
     206    32882932 : FF_samechar(GEN x, GEN y)
     207             : {
     208    32882932 :   return x[1] == y[1] && equalii(gel(x,4),gel(y,4));
     209             : }
     210             : 
     211             : int
     212    32882932 : FF_samefield(GEN x, GEN y)
     213             : {
     214    32882932 :   return FF_samechar(x, y) && gidentical(gel(x,3),gel(y,3));
     215             : }
     216             : 
     217             : int
     218       55496 : FF_equal(GEN x, GEN y)
     219       55496 : { return FF_samefield(x,y) && gidentical(gel(x,2),gel(y,2)); }
     220             : 
     221             : int
     222     8945494 : FF_equal0(GEN x)
     223             : {
     224     8945494 :   return lgpol(gel(x,2))==0;
     225             : }
     226             : 
     227             : int
     228       23730 : FF_equal1(GEN x)
     229             : {
     230       23730 :   GEN A = gel(x,2);
     231       23730 :   switch(x[1])
     232             :   {
     233             :   case t_FF_FpXQ:
     234        5391 :     return degpol(A)==0 && gequal1(gel(A,2));
     235             :   default:
     236       18339 :     return degpol(A)==0 && A[2]==1;
     237             :   }
     238             : }
     239             : 
     240             : static int
     241           0 : Fp_cmp_1(GEN x, GEN p)
     242           0 : { pari_sp av = avma; return gc_bool(av, equalii(x, addis(p,-1))); }
     243             : 
     244             : int
     245          42 : FF_equalm1(GEN x)
     246             : {
     247             :   ulong pp;
     248          42 :   GEN T, p, y = gel(x,2);
     249          42 :   _getFF(x,&T,&p,&pp);
     250          42 :   switch(x[1])
     251             :   {
     252             :   case t_FF_FpXQ:
     253           0 :     return (degpol(y) == 0 && Fp_cmp_1(gel(y,2), p));
     254             :   default:
     255          42 :     return (degpol(y) == 0 && uel(y,2) == pp-1);
     256             :   }
     257             : }
     258             : 
     259             : GEN
     260        5744 : FF_zero(GEN x)
     261             : {
     262             :   ulong pp;
     263        5744 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     264        5744 :   switch(x[1])
     265             :   {
     266             :   case t_FF_FpXQ:
     267         497 :     r=zeropol(varn(T));
     268         497 :     break;
     269             :   case t_FF_F2xq:
     270        1341 :     r=zero_F2x(T[1]);
     271        1341 :     break;
     272             :   default:
     273        3906 :     r=zero_Flx(T[1]);
     274             :   }
     275        5744 :   return _mkFF(x,z,r);
     276             : }
     277             : 
     278             : GEN
     279       13160 : FF_1(GEN x)
     280             : {
     281             :   ulong pp;
     282       13160 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     283       13160 :   switch(x[1])
     284             :   {
     285             :   case t_FF_FpXQ:
     286         137 :     r=pol_1(varn(T));
     287         137 :     break;
     288             :   case t_FF_F2xq:
     289        8064 :     r=pol1_F2x(T[1]);
     290        8064 :     break;
     291             :   default:
     292        4959 :     r=pol1_Flx(T[1]);
     293             :   }
     294       13160 :   return _mkFF(x,z,r);
     295             : }
     296             : 
     297             : GEN
     298         476 : FF_gen(GEN x)
     299             : {
     300             :   ulong pp;
     301         476 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     302         476 :   switch(x[1])
     303             :   {
     304             :   case t_FF_FpXQ:
     305         154 :     r = pol_x(varn(T));
     306         154 :     if (degpol(T)==1) r = FpX_rem(r, T, p);
     307         154 :     break;
     308             :   case t_FF_F2xq:
     309         154 :     r = polx_F2x(T[1]);
     310         154 :     if (F2x_degree(T)==1) r = F2x_rem(r, T);
     311         154 :     break;
     312             :   default:
     313         168 :     r = polx_Flx(T[1]);
     314         168 :     if (degpol(T)==1) r = Flx_rem(r, T, pp);
     315             :   }
     316         476 :   return _mkFF(x,z,r);
     317             : }
     318             : GEN
     319       54481 : FF_q(GEN x)
     320             : {
     321             :   ulong pp;
     322             :   GEN T, p;
     323       54481 :   _getFF(x,&T,&p,&pp);
     324       54481 :   switch(x[1])
     325             :   {
     326             :   case t_FF_FpXQ:
     327        1681 :     return powiu(p, degpol(T));
     328             :     break;
     329             :   case t_FF_F2xq:
     330        7028 :     return int2n(F2x_degree(T));
     331             :     break;
     332             :   default:
     333       45772 :     return powuu(pp,degpol(T));
     334             :   }
     335             : }
     336             : 
     337             : GEN
     338          56 : FF_p(GEN x)
     339             : {
     340          56 :   return icopy(gel(x,4));
     341             : }
     342             : 
     343             : GEN
     344     2620016 : FF_p_i(GEN x)
     345             : {
     346     2620016 :   return gel(x,4);
     347             : }
     348             : 
     349             : GEN
     350      165557 : FF_mod(GEN x)
     351             : {
     352      165557 :   switch(x[1])
     353             :   {
     354             :   case t_FF_FpXQ:
     355         365 :     return ZX_copy(gel(x,3));
     356             :   case t_FF_F2xq:
     357         371 :     return F2x_to_ZX(gel(x,3));
     358             :   default:
     359      164821 :     return Flx_to_ZX(gel(x,3));
     360             :   }
     361             : }
     362             : 
     363             : long
     364          42 : FF_var(GEN x)
     365             : {
     366          42 :   switch(x[1])
     367             :   {
     368             :   case t_FF_FpXQ:
     369          14 :     return varn(gel(x,3));
     370             :   case t_FF_F2xq:
     371             :   default:
     372          28 :     return gel(x,3)[1]>>VARNSHIFT;
     373             :   }
     374             : }
     375             : 
     376             : long
     377         371 : FF_f(GEN x)
     378             : {
     379         371 :   switch(x[1])
     380             :   {
     381             :   case t_FF_F2xq:
     382         147 :     return F2x_degree(gel(x,3));
     383             :   default:
     384         224 :     return degpol(gel(x,3));
     385             :   }
     386             : }
     387             : 
     388             : GEN
     389      918731 : FF_to_F2xq(GEN x)
     390             : {
     391      918731 :   switch(x[1])
     392             :   {
     393             :   case t_FF_FpXQ:
     394           0 :     return ZX_to_F2x(gel(x,2));
     395             :   case t_FF_F2xq:
     396      918731 :     return zv_copy(gel(x,2));
     397             :   default:
     398           0 :     return Flx_to_F2x(gel(x,2));
     399             :   }
     400             : }
     401             : 
     402             : GEN
     403           0 : FF_to_F2xq_i(GEN x)
     404             : {
     405           0 :   switch(x[1])
     406             :   {
     407             :   case t_FF_FpXQ:
     408           0 :     return ZX_to_F2x(gel(x,2));
     409             :   case t_FF_F2xq:
     410           0 :     return gel(x,2);
     411             :   default:
     412           0 :     return Flx_to_F2x(gel(x,2));
     413             :   }
     414             : }
     415             : 
     416             : GEN
     417      726168 : FF_to_Flxq(GEN x)
     418             : {
     419      726168 :   switch(x[1])
     420             :   {
     421             :   case t_FF_FpXQ:
     422           0 :     return ZX_to_Flx(gel(x,2),itou(gel(x,4)));
     423             :   case t_FF_F2xq:
     424           0 :     return F2x_to_Flx(gel(x,2));
     425             :   default:
     426      726168 :     return zv_copy(gel(x,2));
     427             :   }
     428             : }
     429             : 
     430             : GEN
     431           0 : FF_to_Flxq_i(GEN x)
     432             : {
     433           0 :   switch(x[1])
     434             :   {
     435             :   case t_FF_FpXQ:
     436           0 :     return ZX_to_Flx(gel(x,2),itou(gel(x,4)));
     437             :   case t_FF_F2xq:
     438           0 :     return F2x_to_Flx(gel(x,2));
     439             :   default:
     440           0 :     return gel(x,2);
     441             :   }
     442             : }
     443             : 
     444             : GEN
     445       17946 : FF_to_FpXQ(GEN x)
     446             : {
     447       17946 :   switch(x[1])
     448             :   {
     449             :   case t_FF_FpXQ:
     450       16470 :     return ZX_copy(gel(x,2));
     451             :   case t_FF_F2xq:
     452          63 :     return F2x_to_ZX(gel(x,2));
     453             :   default:
     454        1413 :     return Flx_to_ZX(gel(x,2));
     455             :   }
     456             : }
     457             : 
     458             : GEN
     459      170828 : FF_to_FpXQ_i(GEN x)
     460             : {
     461      170828 :   switch(x[1])
     462             :   {
     463             :   case t_FF_FpXQ:
     464        1214 :     return gel(x,2);
     465             :   case t_FF_F2xq:
     466        1204 :     return F2x_to_ZX(gel(x,2));
     467             :   default:
     468      168410 :     return Flx_to_ZX(gel(x,2));
     469             :   }
     470             : }
     471             : 
     472             : GEN
     473    14133655 : FF_add(GEN x, GEN y)
     474             : {
     475             :   ulong pp;
     476    14133655 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     477    14133655 :   _checkFF(x,y,"+");
     478    14133656 :   switch(x[1])
     479             :   {
     480             :   case t_FF_FpXQ:
     481     1454007 :     r=FpX_add(gel(x,2),gel(y,2),p);
     482     1454007 :     break;
     483             :   case t_FF_F2xq:
     484     1130469 :     r=F2x_add(gel(x,2),gel(y,2));
     485     1130466 :     break;
     486             :   default:
     487    11549180 :     r=Flx_add(gel(x,2),gel(y,2),pp);
     488             :   }
     489    14133653 :   return _mkFF(x,z,r);
     490             : }
     491             : GEN
     492      283094 : FF_sub(GEN x, GEN y)
     493             : {
     494             :   ulong pp;
     495      283094 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     496      283094 :   _checkFF(x,y,"+");
     497      283094 :   switch(x[1])
     498             :   {
     499             :   case t_FF_FpXQ:
     500        2892 :     r=FpX_sub(gel(x,2),gel(y,2),p);
     501        2892 :     break;
     502             :   case t_FF_F2xq:
     503      155108 :     r=F2x_add(gel(x,2),gel(y,2));
     504      155108 :     break;
     505             :   default:
     506      125094 :     r=Flx_sub(gel(x,2),gel(y,2),pp);
     507             :   }
     508      283094 :   return _mkFF(x,z,r);
     509             : }
     510             : 
     511             : GEN
     512     1658489 : FF_Z_add(GEN x, GEN y)
     513             : {
     514             :   ulong pp;
     515     1658489 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     516     1658490 :   switch(x[1])
     517             :   {
     518             :   case t_FF_FpXQ:
     519             :     {
     520        9262 :       pari_sp av=avma;
     521        9262 :       r=gerepileupto(av,FpX_Fp_add(gel(x,2),modii(y,p),p));
     522        9262 :       break;
     523             :     }
     524             :   case t_FF_F2xq:
     525      792338 :     r=mpodd(y)?F2x_1_add(gel(x,2)):vecsmall_copy(gel(x,2));
     526      792335 :     break;
     527             :   default:
     528      856890 :     r=Flx_Fl_add(gel(x,2),umodiu(y,pp),pp);
     529             :   }
     530     1658487 :   return _mkFF(x,z,r);
     531             : }
     532             : 
     533             : GEN
     534        1337 : FF_Q_add(GEN x, GEN y)
     535             : {
     536             :   ulong pp;
     537        1337 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     538        1337 :   switch(x[1])
     539             :   {
     540             :   case t_FF_FpXQ:
     541             :     {
     542           1 :       pari_sp av=avma;
     543           1 :       r=gerepileupto(av,FpX_Fp_add(gel(x,2),Rg_to_Fp(y,p),p));
     544           1 :       break;
     545             :     }
     546             :   case t_FF_F2xq:
     547           7 :     r=Rg_to_Fl(y,pp)?F2x_1_add(gel(x,2)):vecsmall_copy(gel(x,2));
     548           7 :     break;
     549             :   default:
     550        1329 :     r=Flx_Fl_add(gel(x,2),Rg_to_Fl(y,pp),pp);
     551             :   }
     552        1337 :   return _mkFF(x,z,r);
     553             : }
     554             : 
     555             : GEN
     556       41007 : FF_neg(GEN x)
     557             : {
     558             :   ulong pp;
     559       41007 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     560       41007 :   switch(x[1])
     561             :   {
     562             :   case t_FF_FpXQ:
     563        4195 :     r=FpX_neg(gel(x,2),p);
     564        4195 :     break;
     565             :   case t_FF_F2xq:
     566       14330 :     r=vecsmall_copy(gel(x,2));
     567       14330 :     break;
     568             :   default:
     569       22482 :     r=Flx_neg(gel(x,2),pp);
     570             :   }
     571       41007 :   return _mkFF(x,z,r);
     572             : }
     573             : 
     574             : GEN
     575       85015 : FF_neg_i(GEN x)
     576             : {
     577             :   ulong pp;
     578       85015 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     579       85015 :   switch(x[1])
     580             :   {
     581             :   case t_FF_FpXQ:
     582        1748 :     r=FpX_neg(gel(x,2),p);
     583        1748 :     break;
     584             :   case t_FF_F2xq:
     585        8477 :     r=gel(x,2);
     586        8477 :     break;
     587             :   default:
     588       74790 :     r=Flx_neg(gel(x,2),pp);
     589             :   }
     590       85015 :   return _mkFF_i(x,z,r);
     591             : }
     592             : 
     593             : GEN
     594        1736 : FF_map(GEN m, GEN x)
     595             : {
     596             :   ulong pp;
     597        1736 :   GEN r, T, p, z=_initFF(m,&T,&p,&pp);
     598        1736 :   switch(m[1])
     599             :   {
     600             :   case t_FF_FpXQ:
     601         574 :     r=FpX_FpXQ_eval(gel(x,2),gel(m,2),T,p);
     602         574 :     break;
     603             :   case t_FF_F2xq:
     604         686 :     r=F2x_F2xq_eval(gel(x,2),gel(m,2),T);
     605         686 :     break;
     606             :   default:
     607         476 :     r=Flx_Flxq_eval(gel(x,2),gel(m,2),T,pp);
     608             :   }
     609        1736 :   return _mkFF(m,z,r);
     610             : }
     611             : 
     612             : GEN
     613          42 : FF_Frobenius(GEN x, long e)
     614             : {
     615             :   ulong pp;
     616          42 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     617          42 :   ulong n = umodsu(e, FF_f(x));
     618          42 :   if (n==0) return gcopy(x);
     619          42 :   switch(x[1])
     620             :   {
     621             :   case t_FF_FpXQ:
     622          14 :     r=FpXQ_pow(gel(x,2),p,T,p);
     623          14 :     if (n>1) r=FpXQ_autpow(r,n,T,p);
     624          14 :     break;
     625             :   case t_FF_F2xq:
     626          14 :     r=F2xq_sqr(gel(x,2),T);
     627          14 :     if (n>1) r=F2xq_autpow(r,n,T);
     628          14 :     break;
     629             :   default:
     630          14 :     r=Flxq_powu(gel(x,2),pp,T,pp);
     631          14 :     if (n>1) r=Flxq_autpow(r,n,T,pp);
     632             :   }
     633          42 :   return _mkFF(x,z,r);
     634             : }
     635             : 
     636             : static GEN
     637         952 : FFX_preimage_i(GEN x, GEN y, GEN F, GEN T, GEN p, long pp)
     638             : {
     639             :   GEN r;
     640         952 :   F = FFX_to_raw(F, y);
     641         952 :   switch(y[1])
     642             :   {
     643             :   case t_FF_FpXQ:
     644         350 :     r = FpXQX_rem(gel(x,2), F, T, p);
     645         350 :     break;
     646             :   case t_FF_F2xq:
     647         350 :     r = F2xqX_rem(F2x_to_F2xX(gel(x,2),T[1]), F, T);
     648         350 :     break;
     649             :   default:
     650         252 :     r = FlxqX_rem(Flx_to_FlxX(gel(x,2),T[1]), F, T, pp);
     651             :   }
     652         952 :   return r;
     653             : }
     654             : 
     655             : GEN
     656         966 : FFX_preimage(GEN x, GEN F, GEN y)
     657             : {
     658             :   GEN r, T, p, z;
     659             :   ulong pp;
     660         966 :   if (FF_equal0(x)) return FF_zero(y);
     661         875 :   z = _initFF(y,&T,&p,&pp);
     662         875 :   r = FFX_preimage_i(x, y, F, T, p, pp);
     663         875 :   if (degpol(r) > 0) return NULL;
     664         791 :   r = (y[1] == t_FF_FpXQ)? Fq_to_FpXQ(gel(r,2),T, p): gel(r,2);
     665         791 :   return _mkFF(y,z,r);
     666             : }
     667             : 
     668             : GEN
     669          84 : FFX_preimagerel(GEN x, GEN F, GEN y)
     670             : {
     671          84 :   pari_sp av = avma;
     672             :   GEN r, T, p;
     673             :   ulong pp;
     674          84 :   if (FF_equal0(x)) return FF_zero(y);
     675          77 :   _getFF(y,&T,&p,&pp);
     676          77 :   r = FFX_preimage_i(x, y, F, T, p, pp);
     677          77 :   return gerepilecopy(av, raw_to_FFX(r, y));
     678             : }
     679             : 
     680             : GEN
     681    14566643 : FF_mul(GEN x, GEN y)
     682             : {
     683             :   ulong pp;
     684    14566643 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     685    14566643 :   pari_sp av=avma;
     686    14566643 :   _checkFF(x,y,"*");
     687    14566646 :   switch(x[1])
     688             :   {
     689             :   case t_FF_FpXQ:
     690     1453051 :     r=FpXQ_mul(gel(x,2),gel(y,2),T,p);
     691     1453051 :     break;
     692             :   case t_FF_F2xq:
     693      778658 :     r=F2xq_mul(gel(x,2),gel(y,2),T);
     694      778653 :     break;
     695             :   default:
     696    12334937 :     r=Flxq_mul(gel(x,2),gel(y,2),T,pp);
     697             :   }
     698    14566641 :   return _mkFF(x,z,gerepileupto(av, r));
     699             : }
     700             : 
     701             : GEN
     702     2450783 : FF_Z_mul(GEN x, GEN y)
     703             : {
     704             :   ulong pp;
     705     2450783 :   GEN r, T, p, A = gel(x,2), z=_initFF(x,&T,&p,&pp);
     706     2450781 :   switch(x[1])
     707             :   {
     708             :   case t_FF_FpXQ: /* modii(y,p) left on stack for efficiency */
     709       92987 :     r = FpX_Fp_mul(A, modii(y,p),p);
     710       92987 :     break;
     711             :   case t_FF_F2xq:
     712     1121292 :     r = mpodd(y)? vecsmall_copy(A): zero_Flx(A[1]);
     713     1121289 :     break;
     714             :   default:
     715     1236502 :     r = Flx_Fl_mul(A, umodiu(y,pp), pp);
     716             :   }
     717     2450778 :   return _mkFF(x,z,r);
     718             : }
     719             : 
     720             : GEN
     721        4529 : FF_Z_Z_muldiv(GEN x, GEN a, GEN b)
     722             : {
     723             :   ulong pp;
     724        4529 :   GEN r, T, p, A = gel(x,2), z=_initFF(x,&T,&p,&pp);
     725        4529 :   switch(x[1])
     726             :   {
     727             :   case t_FF_FpXQ: /* Fp_div(a,b,p) left on stack for efficiency */
     728          93 :     r = FpX_Fp_mul(A, Fp_div(a,b,p), p);
     729          93 :     break;
     730             :   case t_FF_F2xq:
     731         651 :     if (!mpodd(b)) pari_err_INV("FF_Z_Z_muldiv", b);
     732         644 :     r = mpodd(a)? vecsmall_copy(A): zero_Flx(A[1]);
     733         644 :     break;
     734             :   default:
     735        3785 :     r = Flx_Fl_mul(A, Fl_div(umodiu(a,pp),umodiu(b,pp),pp),pp);
     736             :   }
     737        4515 :   return _mkFF(x,z,r);
     738             : }
     739             : 
     740             : GEN
     741     2893765 : FF_sqr(GEN x)
     742             : {
     743             :   ulong pp;
     744     2893765 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     745     2893770 :   switch(x[1])
     746             :   {
     747             :   case t_FF_FpXQ:
     748             :     {
     749       16296 :       pari_sp av=avma;
     750       16296 :       r=gerepileupto(av,FpXQ_sqr(gel(x,2),T,p));
     751       16296 :       break;
     752             :     }
     753             :   case t_FF_F2xq:
     754      468678 :     r=F2xq_sqr(gel(x,2),T);
     755      468660 :     break;
     756             :   default:
     757     2408796 :     r=Flxq_sqr(gel(x,2),T,pp);
     758             :   }
     759     2893752 :   return _mkFF(x,z,r);
     760             : }
     761             : 
     762             : GEN
     763      216867 : FF_mul2n(GEN x, long n)
     764             : {
     765             :   ulong pp;
     766      216867 :   GEN r, T, p, A = gel(x,2), z=_initFF(x,&T,&p,&pp);
     767      216867 :   switch(x[1])
     768             :   {
     769             :   case t_FF_FpXQ:
     770             :     {
     771             :       GEN p1; /* left on stack for efficiency */
     772        2965 :       if (n>0) p1=remii(int2n(n),p);
     773          43 :       else p1=Fp_inv(remii(int2n(-n),p),p);
     774        2965 :       r = FpX_Fp_mul(A, p1, p);
     775             :     }
     776        2965 :     break;
     777             :   case t_FF_F2xq:
     778       91042 :     if (n<0) pari_err_INV("FF_mul2n", gen_2);
     779       91042 :     r = n==0? vecsmall_copy(A): zero_Flx(A[1]);
     780       91043 :     break;
     781             :   default:
     782             :     {
     783             :       ulong l1;
     784      122860 :       if (n>0) l1 = umodiu(int2n(n),pp);
     785         384 :       else l1 = Fl_inv(umodiu(int2n(-n),pp),pp);
     786      122860 :       r = Flx_Fl_mul(A,l1,pp);
     787             :     }
     788             :   }
     789      216868 :   return _mkFF(x,z,r);
     790             : }
     791             : 
     792             : GEN
     793       14085 : FF_inv(GEN x)
     794             : {
     795             :   ulong pp;
     796       14085 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     797       14085 :   pari_sp av=avma;
     798       14085 :   switch(x[1])
     799             :   {
     800             :   case t_FF_FpXQ:
     801        3298 :     r=gerepileupto(av,FpXQ_inv(gel(x,2),T,p));
     802        3298 :     break;
     803             :   case t_FF_F2xq:
     804        8478 :     r=F2xq_inv(gel(x,2),T);
     805        8478 :     break;
     806             :   default:
     807        2309 :     r=Flxq_inv(gel(x,2),T,pp);
     808             :   }
     809       14085 :   return _mkFF(x,z,r);
     810             : }
     811             : 
     812             : GEN
     813      236797 : FF_div(GEN x, GEN y)
     814             : {
     815             :   ulong pp;
     816      236797 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     817      236797 :   pari_sp av=avma;
     818      236797 :   _checkFF(x,y,"/");
     819      236797 :   switch(x[1])
     820             :   {
     821             :   case t_FF_FpXQ:
     822        3387 :     r=gerepileupto(av,FpXQ_div(gel(x,2),gel(y,2),T,p));
     823        3387 :     break;
     824             :   case t_FF_F2xq:
     825      101760 :     r=gerepileupto(av,F2xq_div(gel(x,2),gel(y,2),T));
     826      101690 :     break;
     827             :   default:
     828      131650 :     r=gerepileupto(av,Flxq_div(gel(x,2),gel(y,2),T,pp));
     829             :   }
     830      236699 :   return _mkFF(x,z,r);
     831             : }
     832             : 
     833             : GEN
     834         301 : Z_FF_div(GEN n, GEN x)
     835             : {
     836             :   ulong pp;
     837         301 :   GEN r, T, p, A = gel(x,2), z=_initFF(x,&T,&p,&pp);
     838         301 :   pari_sp av=avma;
     839         301 :   switch(x[1])
     840             :   {
     841             :   case t_FF_FpXQ:
     842           8 :     r = gerepileupto(av,FpX_Fp_mul(FpXQ_inv(A,T,p),modii(n,p),p));
     843           8 :     break;
     844             :   case t_FF_F2xq:
     845          56 :     r = F2xq_inv(A,T); /*Check for division by 0*/
     846          56 :     if(!mpodd(n)) { set_avma(av); r = zero_Flx(A[1]); }
     847          56 :     break;
     848             :   default:
     849         237 :     r = gerepileupto(av, Flx_Fl_mul(Flxq_inv(A,T,pp),umodiu(n,pp),pp));
     850             :   }
     851         301 :   return _mkFF(x,z,r);
     852             : }
     853             : 
     854             : GEN
     855         217 : FF_sqrtn(GEN x, GEN n, GEN *zetan)
     856             : {
     857             :   ulong pp;
     858         217 :   GEN r, T, p, y=_initFF(x,&T,&p,&pp);
     859         217 :   switch (x[1])
     860             :   {
     861             :   case t_FF_FpXQ:
     862          66 :     r=FpXQ_sqrtn(gel(x,2),n,T,p,zetan);
     863          59 :     break;
     864             :   case t_FF_F2xq:
     865          28 :     r=F2xq_sqrtn(gel(x,2),n,T,zetan);
     866          21 :     break;
     867             :   default:
     868         123 :     r=Flxq_sqrtn(gel(x,2),n,T,pp,zetan);
     869             :   }
     870         196 :   if (!r) pari_err_SQRTN("FF_sqrtn",x);
     871         196 :   (void)_mkFF(x, y, r);
     872         196 :   if (zetan)
     873             :   {
     874         140 :     GEN z = cgetg(lg(y),t_FFELT);
     875         140 :     *zetan=_mkFF(x, z, *zetan);
     876             :   }
     877         196 :   return y;
     878             : }
     879             : 
     880             : GEN
     881          70 : FF_sqrt(GEN x)
     882             : {
     883             :   ulong pp;
     884          70 :   GEN r, T, p, y=_initFF(x,&T,&p,&pp);
     885          70 :   switch (x[1])
     886             :   {
     887             :   case t_FF_FpXQ:
     888           1 :     r = FpXQ_sqrt(gel(x,2),T,p);
     889           1 :     break;
     890             :   case t_FF_F2xq:
     891          49 :     r = F2xq_sqrt(gel(x,2),T);
     892          49 :     break;
     893             :   default:
     894          20 :     r = Flxq_sqrt(gel(x,2),T,pp);
     895             :   }
     896          70 :   if (!r) pari_err_SQRTN("FF_sqrt",x);
     897          70 :   return _mkFF(x, y, r);
     898             : }
     899             : 
     900             : long
     901           7 : FF_issquare(GEN x)
     902             : {
     903             :   GEN T, p;
     904             :   ulong pp;
     905           7 :   _getFF(x, &T, &p, &pp);
     906           7 :   switch(x[1])
     907             :   {
     908             :   case t_FF_FpXQ:
     909           0 :     return FpXQ_issquare(gel(x,2), T, p);
     910             :   case t_FF_F2xq:
     911           7 :     return 1;
     912             :   default: /* case t_FF_Flxq: */
     913           0 :     return Flxq_issquare(gel(x,2), T, pp);
     914             :   }
     915             : }
     916             : 
     917             : long
     918         182 : FF_issquareall(GEN x, GEN *pt)
     919             : {
     920         182 :   if (!pt) return FF_issquare(x);
     921         175 :   return FF_ispower(x, gen_2, pt);
     922             : }
     923             : 
     924             : long
     925         203 : FF_ispower(GEN x, GEN K, GEN *pt)
     926             : {
     927             :   ulong pp;
     928             :   GEN r, T, p;
     929         203 :   pari_sp av = avma;
     930             : 
     931         203 :   if (FF_equal0(x)) { if (pt) *pt = gcopy(x); return 1; }
     932         203 :   _getFF(x, &T, &p, &pp);
     933         203 :   if (pt) *pt = cgetg(5,t_FFELT);
     934         203 :   switch(x[1])
     935             :   {
     936             :   case t_FF_FpXQ:
     937          71 :     r = FpXQ_sqrtn(gel(x,2),K,T,p,NULL);
     938          71 :     break;
     939             :   case t_FF_F2xq:
     940          42 :     r = F2xq_sqrtn(gel(x,2),K,T,NULL);
     941          42 :     break;
     942             :   default: /* case t_FF_Flxq: */
     943          90 :     r = Flxq_sqrtn(gel(x,2),K,T,pp,NULL);
     944          90 :     break;
     945             :   }
     946         203 :   if (!r) return gc_long(av,0);
     947         133 :   if (pt) { (void)_mkFF(x,*pt,r); }
     948         133 :   return 1;
     949             : }
     950             : 
     951             : GEN
     952          80 : FF_pow(GEN x, GEN n)
     953             : {
     954             :   ulong pp;
     955          80 :   GEN r, T, p, z=_initFF(x,&T,&p,&pp);
     956          80 :   switch(x[1])
     957             :    {
     958             :    case t_FF_FpXQ:
     959          17 :      r = FpXQ_pow(gel(x,2), n, T, p);
     960          17 :      break;
     961             :    case t_FF_F2xq:
     962           3 :      r = F2xq_pow(gel(x,2), n, T);
     963           3 :      break;
     964             :    default:
     965          60 :      r = Flxq_pow(gel(x,2), n, T, pp);
     966             :    }
     967          80 :   return _mkFF(x,z,r);
     968             : }
     969             : 
     970             : GEN
     971          28 : FF_norm(GEN x)
     972             : {
     973             :   ulong pp;
     974             :   GEN T,p;
     975          28 :   _getFF(x,&T,&p,&pp);
     976          28 :   switch (x[1])
     977             :   {
     978             :   case t_FF_FpXQ:
     979           1 :     return FpXQ_norm(gel(x,2),T,p);
     980             :   case t_FF_F2xq:
     981           7 :     return lgpol(gel(x,2))?gen_1:gen_0;
     982             :   default:
     983          20 :     return utoi(Flxq_norm(gel(x,2),T,pp));
     984             :   }
     985             : }
     986             : 
     987             : GEN
     988          28 : FF_trace(GEN x)
     989             : {
     990             :   ulong pp;
     991             :   GEN T,p;
     992          28 :   _getFF(x,&T,&p,&pp);
     993          28 :   switch(x[1])
     994             :   {
     995             :   case t_FF_FpXQ:
     996           1 :     return FpXQ_trace(gel(x,2),T,p);
     997             :   case t_FF_F2xq:
     998           7 :     return F2xq_trace(gel(x,2),T)?gen_1:gen_0;
     999             :   default:
    1000          20 :     return utoi(Flxq_trace(gel(x,2),T,pp));
    1001             :   }
    1002             : }
    1003             : 
    1004             : GEN
    1005          28 : FF_conjvec(GEN x)
    1006             : {
    1007             :   ulong pp;
    1008             :   GEN r,T,p,v;
    1009             :   long i,l;
    1010             :   pari_sp av;
    1011          28 :   _getFF(x,&T,&p,&pp);
    1012          28 :   av = avma;
    1013          28 :   switch(x[1])
    1014             :   {
    1015             :   case t_FF_FpXQ:
    1016           1 :     v = FpXQ_conjvec(gel(x,2), T, p);
    1017           1 :     break;
    1018             :   case t_FF_F2xq:
    1019           7 :     v = F2xq_conjvec(gel(x,2), T);
    1020           7 :     break;
    1021             :   default:
    1022          20 :     v = Flxq_conjvec(gel(x,2), T, pp);
    1023             :   }
    1024          28 :   l = lg(v); r = cgetg(l, t_COL);
    1025         252 :   for(i=1; i<l; i++)
    1026         224 :     gel(r,i) = mkFF_i(x, gel(v,i));
    1027          28 :   return gerepilecopy(av, r);
    1028             : }
    1029             : 
    1030             : GEN
    1031          28 : FF_charpoly(GEN x)
    1032             : {
    1033             :   ulong pp;
    1034             :   GEN T,p;
    1035          28 :   pari_sp av=avma;
    1036          28 :   _getFF(x,&T,&p,&pp);
    1037          28 :   switch(x[1])
    1038             :   {
    1039             :   case t_FF_FpXQ:
    1040           1 :     return gerepileupto(av,FpXQ_charpoly(gel(x,2), T, p));
    1041             :   case t_FF_F2xq:
    1042           7 :     return gerepileupto(av,Flx_to_ZX(Flxq_charpoly(F2x_to_Flx(gel(x,2)),
    1043             :                                                    F2x_to_Flx(T), 2UL)));
    1044             :   default:
    1045          20 :     return gerepileupto(av,Flx_to_ZX(Flxq_charpoly(gel(x,2), T, pp)));
    1046             :   }
    1047             : }
    1048             : 
    1049             : GEN
    1050         154 : FF_minpoly(GEN x)
    1051             : {
    1052             :   ulong pp;
    1053             :   GEN T,p;
    1054         154 :   pari_sp av=avma;
    1055         154 :   _getFF(x,&T,&p,&pp);
    1056         154 :   switch(x[1])
    1057             :   {
    1058             :   case t_FF_FpXQ:
    1059          43 :     return gerepileupto(av,FpXQ_minpoly(gel(x,2), T, p));
    1060             :   case t_FF_F2xq:
    1061          49 :     return gerepileupto(av,Flx_to_ZX(Flxq_minpoly(F2x_to_Flx(gel(x,2)),
    1062             :                                                   F2x_to_Flx(T), 2UL)));
    1063             :   default:
    1064          62 :     return gerepileupto(av,Flx_to_ZX(Flxq_minpoly(gel(x,2), T, pp)));
    1065             :   }
    1066             : }
    1067             : 
    1068             : GEN
    1069         182 : FF_log(GEN x, GEN g, GEN ord)
    1070             : {
    1071         182 :   pari_sp av=avma;
    1072             :   ulong pp;
    1073             :   GEN r, T, p;
    1074         182 :   _getFF(x,&T,&p,&pp);
    1075         182 :   _checkFF(x,g,"log");
    1076         182 :   switch(x[1])
    1077             :   {
    1078             :   case t_FF_FpXQ:
    1079          44 :     if (!ord) ord = factor_pn_1(p,degpol(T));
    1080          44 :     r = FpXQ_log(gel(x,2), gel(g,2), ord, T, p);
    1081          16 :     break;
    1082             :   case t_FF_F2xq:
    1083          28 :     if (!ord) ord = factor_pn_1(gen_2,F2x_degree(T));
    1084          28 :     r = F2xq_log(gel(x,2), gel(g,2), ord, T);
    1085          28 :     break;
    1086             :   default:
    1087         110 :     if (!ord) ord = factor_pn_1(p,degpol(T));
    1088         110 :     r = Flxq_log(gel(x,2), gel(g,2), ord, T, pp);
    1089             :   }
    1090         154 :   return gerepileupto(av, r);
    1091             : }
    1092             : 
    1093             : GEN
    1094          28 : FF_order(GEN x, GEN o)
    1095             : {
    1096          28 :   pari_sp av=avma;
    1097             :   ulong pp;
    1098             :   GEN r, T,p;
    1099          28 :   _getFF(x,&T,&p,&pp);
    1100          28 :   switch(x[1])
    1101             :   {
    1102             :   case t_FF_FpXQ:
    1103           1 :     if (!o) o = factor_pn_1(p,degpol(T));
    1104           1 :     r = FpXQ_order(gel(x,2), o, T, p);
    1105           1 :     break;
    1106             :   case t_FF_F2xq:
    1107           7 :     if (!o) o = factor_pn_1(gen_2,F2x_degree(T));
    1108           7 :     r = F2xq_order(gel(x,2), o, T);
    1109           7 :     break;
    1110             :   default:
    1111          20 :     if (!o) o = factor_pn_1(p,degpol(T));
    1112          20 :     r = Flxq_order(gel(x,2), o, T, pp);
    1113             :   }
    1114          28 :   if (!o) r = gerepileuptoint(av,r);
    1115          28 :   return r;
    1116             : }
    1117             : 
    1118             : GEN
    1119         392 : FF_primroot(GEN x, GEN *o)
    1120             : {
    1121             :   ulong pp;
    1122         392 :   GEN r,T,p,z=_initFF(x,&T,&p,&pp);
    1123         392 :   switch(x[1])
    1124             :   {
    1125             :   case t_FF_FpXQ:
    1126          30 :     r = gener_FpXQ(T, p, o);
    1127          30 :     break;
    1128             :   case t_FF_F2xq:
    1129         154 :     r = gener_F2xq(T, o);
    1130         154 :     break;
    1131             :   default:
    1132         208 :     r = gener_Flxq(T, pp, o);
    1133             :   }
    1134         392 :   return _mkFF(x,z,r);
    1135             : }
    1136             : 
    1137             : static GEN
    1138      512575 : to_FFE(GEN P, GEN fg)
    1139             : {
    1140      512575 :   if(ell_is_inf(P))
    1141      232085 :     return ellinf();
    1142             :   else
    1143      280490 :     retmkvec2(mkFF_i(fg,gel(P,1)), mkFF_i(fg,gel(P,2)));
    1144             : }
    1145             : 
    1146             : static GEN
    1147       18109 : to_FFE_vec(GEN x, GEN ff)
    1148             : {
    1149       18109 :   long i, lx = lg(x);
    1150       18109 :   for (i=1; i<lx; i++) gel(x,i) = to_FFE(gel(x,i), ff);
    1151       18109 :   return x;
    1152             : }
    1153             : 
    1154             : static GEN
    1155        1711 : FpXQ_ell_to_a4a6(GEN E, GEN T, GEN p)
    1156             : {
    1157             :   GEN a1, a3, b2, c4, c6;
    1158        1711 :   a1 = Rg_to_FpXQ(ell_get_a1(E),T,p);
    1159        1711 :   a3 = Rg_to_FpXQ(ell_get_a3(E),T,p);
    1160        1711 :   b2 = Rg_to_FpXQ(ell_get_b2(E),T,p);
    1161        1711 :   c4 = Rg_to_FpXQ(ell_get_c4(E),T,p);
    1162        1711 :   c6 = Rg_to_FpXQ(ell_get_c6(E),T,p);
    1163        1711 :   retmkvec3(FpX_neg(FpX_mulu(c4, 27, p), p), FpX_neg(FpX_mulu(c6, 54, p), p),
    1164             :             mkvec4(Z_to_FpX(utoi(6),p,varn(T)),FpX_mulu(b2,3,p),
    1165             :                    FpX_mulu(a1,3,p),FpX_mulu(a3,108,p)));
    1166             : }
    1167             : 
    1168             : static GEN
    1169       24710 : F3xq_ell_to_a4a6(GEN E, GEN T)
    1170             : {
    1171             :   GEN a1, a3, b2, b4, b6;
    1172       24710 :   a1 = Rg_to_Flxq(ell_get_a1(E),T,3);
    1173       24710 :   a3 = Rg_to_Flxq(ell_get_a3(E),T,3);
    1174       24710 :   b2 = Rg_to_Flxq(ell_get_b2(E),T,3);
    1175       24710 :   b4 = Rg_to_Flxq(ell_get_b4(E),T,3);
    1176       24710 :   b6 = Rg_to_Flxq(ell_get_b6(E),T,3);
    1177       24710 :   if(lgpol(b2)) /* ordinary case */
    1178             :   {
    1179       17885 :     GEN b4b2 = Flxq_div(b4,b2,T,3);
    1180       17885 :     GEN a6 = Flx_sub(b6,Flxq_mul(b4b2,Flx_add(b4,Flxq_sqr(b4b2,T,3),3),T,3),3);
    1181       17885 :     retmkvec3(mkvec(b2), a6,
    1182             :        mkvec4(Fl_to_Flx(1,T[1]),b4b2,Flx_neg(a1,3),Flx_neg(a3,3)));
    1183             :   }
    1184             :   else /* super-singular case */
    1185        6825 :     retmkvec3(Flx_neg(b4, 3), b6,
    1186             :        mkvec4(Fl_to_Flx(1,T[1]),zero_Flx(T[1]), Flx_neg(a1,3), Flx_neg(a3,3)));
    1187             : }
    1188             : 
    1189             : static GEN
    1190       66812 : Flxq_ell_to_a4a6(GEN E, GEN T, ulong p)
    1191             : {
    1192             :   GEN a1, a3, b2, c4, c6;
    1193       66812 :   if(p==3) return F3xq_ell_to_a4a6(E, T);
    1194       42102 :   a1 = Rg_to_Flxq(ell_get_a1(E),T,p);
    1195       42102 :   a3 = Rg_to_Flxq(ell_get_a3(E),T,p);
    1196       42102 :   b2 = Rg_to_Flxq(ell_get_b2(E),T,p);
    1197       42102 :   c4 = Rg_to_Flxq(ell_get_c4(E),T,p);
    1198       42102 :   c6 = Rg_to_Flxq(ell_get_c6(E),T,p);
    1199       42102 :   retmkvec3(Flx_neg(Flx_mulu(c4, 27, p), p), Flx_neg(Flx_mulu(c6, 54, p), p),
    1200             :             mkvec4(Fl_to_Flx(6%p,T[1]),Flx_mulu(b2,3,p),
    1201             :                    Flx_mulu(a1,3,p),Flx_mulu(a3,108,p)));
    1202             : }
    1203             : 
    1204             : static GEN
    1205       45669 : F2xq_ell_to_a4a6(GEN E, GEN T)
    1206             : {
    1207       45669 :   long v = T[1];
    1208       45669 :   GEN a1 = Rg_to_F2xq(ell_get_a1(E),T);
    1209       45669 :   GEN a2 = Rg_to_F2xq(ell_get_a2(E),T);
    1210       45669 :   GEN a3 = Rg_to_F2xq(ell_get_a3(E),T);
    1211       45669 :   GEN a4 = Rg_to_F2xq(ell_get_a4(E),T);
    1212       45669 :   GEN a6 = Rg_to_F2xq(ell_get_a6(E),T);
    1213       45669 :   if (lgpol(a1))
    1214             :   {
    1215        7652 :     GEN a1i = F2xq_inv(a1,T);
    1216        7652 :     GEN a1i2 = F2xq_sqr(a1i,T);
    1217        7652 :     GEN a1i3 = F2xq_mul(a1i,a1i2,T);
    1218        7651 :     GEN a1i6 = F2xq_sqr(a1i3,T);
    1219        7651 :     GEN d  = F2xq_mul(a3,a1i,T);
    1220        7652 :     GEN dd = F2xq_mul(d,a1i2,T);
    1221        7651 :     GEN e  = F2xq_mul(F2x_add(a4,F2xq_sqr(d,T)),a1i,T);
    1222        7651 :     GEN ee = F2xq_mul(e,a1i3,T);
    1223        7652 :     GEN da2 = F2x_add(a2,d);
    1224        7651 :     GEN d2 = F2xq_mul(da2,a1i2,T);
    1225        7650 :     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);
    1226        7651 :     retmkvec3(d2, d6, mkvec4(a1i,dd,pol0_F2x(v),ee));
    1227             :   }
    1228             :   else
    1229             :   { /* allow a1 = a3 = 0: singular curve */
    1230       38017 :     GEN d4 = F2x_add(F2xq_sqr(a2,T),a4);
    1231       38017 :     GEN d6 = F2x_add(F2xq_mul(a2,a4,T),a6);
    1232       38017 :     GEN a3i = lgpol(a3)? F2xq_inv(a3,T): a3;
    1233       38017 :     retmkvec3(mkvec3(a3,d4,a3i), d6, mkvec4(pol1_F2x(v),a2,pol0_F2x(T[1]),pol0_F2x(T[1])));
    1234             :   }
    1235             : }
    1236             : 
    1237             : static GEN
    1238        1744 : FqV_to_FpXQV(GEN x, GEN T)
    1239             : {
    1240        1744 :   pari_sp av = avma;
    1241        1744 :   long v = varn(T), i, s=0, l = lg(x);
    1242        1744 :   GEN y = shallowcopy(x);
    1243        8720 :   for(i=1; i<l; i++)
    1244        6976 :     if (typ(gel(x,i))==t_INT)
    1245             :     {
    1246           0 :       gel(y,i) = scalarpol(gel(x,i), v);
    1247           0 :       s = 1;
    1248             :     }
    1249        1744 :   if (!s) { set_avma(av); return x; }
    1250           0 :   return y;
    1251             : }
    1252             : 
    1253             : GEN
    1254       95677 : FF_ellcard(GEN E)
    1255             : {
    1256             :   GEN T,p;
    1257             :   ulong pp;
    1258       95677 :   GEN e = ellff_get_a4a6(E);
    1259       95677 :   GEN fg = ellff_get_field(E);
    1260       95677 :   _getFF(fg,&T,&p,&pp);
    1261       95677 :   switch(fg[1])
    1262             :   {
    1263             :   case t_FF_FpXQ:
    1264        1695 :     return FpXQ_ellcard(Fq_to_FpXQ(gel(e,1),T,p), Fq_to_FpXQ(gel(e,2),T,p),T,p);
    1265             :   case t_FF_F2xq:
    1266       45417 :     return F2xq_ellcard(gel(e,1),gel(e,2),T);
    1267             :   default:
    1268       48565 :     return Flxq_ellcard(gel(e,1),gel(e,2),T,pp);
    1269             :   }
    1270             : }
    1271             : 
    1272             : GEN
    1273          14 : FF_ellcard_SEA(GEN E, long smallfact)
    1274             : {
    1275          14 :   pari_sp av = avma;
    1276             :   GEN T,p;
    1277             :   ulong pp;
    1278          14 :   GEN e = ellff_get_a4a6(E), a4, a6, card;
    1279          14 :   GEN fg = ellff_get_field(E);
    1280          14 :   _getFF(fg,&T,&p,&pp);
    1281          14 :   switch(fg[1])
    1282             :   {
    1283             :   case t_FF_FpXQ:
    1284           0 :     a4 = Fq_to_FpXQ(gel(e,1), T, p);
    1285           0 :     a6 = Fq_to_FpXQ(gel(e,2), T, p);
    1286           0 :     card = Fq_ellcard_SEA(a4, a6, powiu(p,degpol(T)), T,p, smallfact);
    1287           0 :     break;
    1288             :   case t_FF_F2xq:
    1289           0 :     pari_err_IMPL("SEA for char 2");
    1290             :   default:
    1291          14 :     a4 = Flx_to_ZX(gel(e,1));
    1292          14 :     a6 = Flx_to_ZX(gel(e,2));
    1293          14 :     card = Fq_ellcard_SEA(a4, a6, powuu(pp,degpol(T)), Flx_to_ZX(T), p, smallfact);
    1294             :   }
    1295          14 :   return gerepileuptoint(av, card);
    1296             : }
    1297             : 
    1298             : /* return G, set m */
    1299             : GEN
    1300       19432 : FF_ellgroup(GEN E, GEN *pm)
    1301             : {
    1302             :   GEN T, p, e, fg, N;
    1303             :   ulong pp;
    1304             : 
    1305       19432 :   N = ellff_get_card(E);
    1306       19432 :   e = ellff_get_a4a6(E);
    1307       19432 :   fg = ellff_get_field(E);
    1308       19432 :   _getFF(fg,&T,&p,&pp);
    1309       19432 :   switch(fg[1])
    1310             :   {
    1311             :   case t_FF_FpXQ:
    1312          30 :     return FpXQ_ellgroup(Fq_to_FpXQ(gel(e,1),T,p),
    1313          15 :                          Fq_to_FpXQ(gel(e,2),T,p),N,T,p,pm);
    1314             :   case t_FF_F2xq:
    1315        3808 :     return F2xq_ellgroup(gel(e,1),gel(e,2),N,T,pm);
    1316             :   default:
    1317       15609 :     return Flxq_ellgroup(gel(e,1),gel(e,2),N,T,pp,pm);
    1318             :   }
    1319             : }
    1320             : 
    1321             : GEN
    1322       18109 : FF_ellgens(GEN E)
    1323             : {
    1324             :   GEN D, fg, e, m, T, p, F, e3;
    1325             :   ulong pp;
    1326             : 
    1327       18109 :   fg = ellff_get_field(E);
    1328       18109 :   e = ellff_get_a4a6(E);
    1329       18109 :   m = ellff_get_m(E);
    1330       18109 :   D = ellff_get_D(E);
    1331       18109 :   _getFF(fg,&T,&p,&pp);
    1332       18109 :   switch(fg[1])
    1333             :   {
    1334             :   case t_FF_FpXQ:
    1335           8 :     e3 = FqV_to_FpXQV(gel(e,3),T);
    1336           8 :     F = FpXQ_ellgens(Fq_to_FpXQ(gel(e,1),T,p),Fq_to_FpXQ(gel(e,2),T,p),e3,D,m,T,p);
    1337           8 :     break;
    1338             :   case t_FF_F2xq:
    1339        3738 :     F = F2xq_ellgens(gel(e,1),gel(e,2),gel(e,3),D,m,T);
    1340        3738 :     break;
    1341             :   default:
    1342       14363 :     F = Flxq_ellgens(gel(e,1),gel(e,2),gel(e,3),D,m,T, pp);
    1343       14363 :     break;
    1344             :   }
    1345       18109 :   return to_FFE_vec(F,fg);
    1346             : }
    1347             : 
    1348             : GEN
    1349         119 : FF_elldata(GEN E, GEN fg)
    1350             : {
    1351             :   GEN T,p,e;
    1352             :   ulong pp;
    1353         119 :   _getFF(fg,&T,&p,&pp);
    1354         119 :   switch(fg[1])
    1355             :   {
    1356             :   case t_FF_FpXQ:
    1357           0 :     e = FpXQ_ell_to_a4a6(E,T,p); break;
    1358             :   case t_FF_F2xq:
    1359          56 :     e = F2xq_ell_to_a4a6(E,T); break;
    1360             :   default:
    1361          63 :     e = Flxq_ell_to_a4a6(E,T,pp); break;
    1362             :   }
    1363         119 :   return mkvec2(fg,e);
    1364             : }
    1365             : 
    1366             : /* allow singular E, set E.j = 0 in this case */
    1367             : GEN
    1368      114073 : FF_ellinit(GEN E, GEN fg)
    1369             : {
    1370      114073 :   GEN T,p,e, D, c4, y = E;
    1371             :   ulong pp;
    1372             :   long i;
    1373      114073 :   _getFF(fg,&T,&p,&pp);
    1374      114073 :   switch(fg[1])
    1375             :   {
    1376             :   case t_FF_FpXQ:
    1377        1711 :     e = FpXQ_ell_to_a4a6(E,T,p);
    1378        1711 :     for(i=1;i<=12;i++) gel(y,i) = mkFF_i(fg,Rg_to_FpXQ(gel(E,i),T,p));
    1379        1711 :     break;
    1380             :   case t_FF_F2xq:
    1381       45613 :     e = F2xq_ell_to_a4a6(E,T);
    1382       45612 :     for(i=1;i<=12;i++) gel(y,i) = mkFF_i(fg,Rg_to_F2xq(gel(E,i),T));
    1383       45613 :     break;
    1384             :   default:
    1385       66749 :     e = Flxq_ell_to_a4a6(E,T,pp);
    1386       66749 :     for(i=1;i<=12;i++) gel(y,i) = mkFF_i(fg,Rg_to_Flxq(gel(E,i),T,pp));
    1387       66749 :     break;
    1388             :   }
    1389      114073 :   D = ell_get_disc(y);
    1390      114073 :   c4 = ell_get_c4(y);
    1391      114073 :   gel(y,13) = FF_equal0(D)? D: gdiv(gpowgs(c4,3), D);
    1392      114073 :   gel(y,14) = mkvecsmall(t_ELL_Fq);
    1393      114073 :   gel(y,15) = mkvec2(fg,e);
    1394      114073 :   return y;
    1395             : }
    1396             : 
    1397             : GEN
    1398       27188 : FF_elltwist(GEN E)
    1399             : {
    1400       27188 :   pari_sp av = avma;
    1401       27188 :   GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E);
    1402             :   GEN T, p, a, a6, V;
    1403             :   ulong pp;
    1404       27188 :   _getFF(fg,&T,&p,&pp);
    1405       27188 :   switch (fg[1])
    1406             :   {
    1407             :   case t_FF_FpXQ:
    1408         840 :     FpXQ_elltwist(gel(e,1), gel(e,2), T, p, &a, &a6);
    1409         840 :     V = mkvec5(gen_0, gen_0, gen_0, mkFF_i(fg, a), mkFF_i(fg, a6));
    1410         840 :     break;
    1411             :   case t_FF_F2xq:
    1412        3514 :     F2xq_elltwist(gel(e,1), gel(e,2), T, &a, &a6);
    1413        7028 :     V = typ(a)==t_VECSMALL ?
    1414        3514 :           mkvec5(gen_1, mkFF_i(fg, a), gen_0, gen_0, mkFF_i(fg, a6)):
    1415           0 :           mkvec5(gen_0, gen_0, mkFF_i(fg, gel(a,1)), mkFF_i(fg, gel(a,2)), mkFF_i(fg, a6));
    1416        3514 :     break;
    1417             :   default:
    1418       22834 :     Flxq_elltwist(gel(e,1), gel(e,2), T, pp, &a, &a6);
    1419       45668 :     V = typ(a)==t_VECSMALL ?
    1420       30436 :           mkvec5(gen_0, gen_0, gen_0, mkFF_i(fg, a), mkFF_i(fg, a6)):
    1421        7602 :           mkvec5(gen_0, mkFF_i(fg, gel(a,1)), gen_0, gen_0, mkFF_i(fg, a6));
    1422             :   }
    1423       27188 :   return gerepilecopy(av, V);
    1424             : }
    1425             : 
    1426             : static long
    1427           0 : F3x_equalm1(GEN x)
    1428           0 : { return degpol(x)==0 && x[2] == 2; }
    1429             : 
    1430             : GEN
    1431      244314 : FF_ellrandom(GEN E)
    1432             : {
    1433      244314 :   pari_sp av = avma;
    1434      244314 :   GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E), Q;
    1435             :   GEN T,p;
    1436             :   ulong pp;
    1437      244314 :   _getFF(fg,&T,&p,&pp);
    1438      244314 :   switch (fg[1])
    1439             :   {
    1440             :   case t_FF_FpXQ:
    1441         854 :     Q = random_FpXQE(Fq_to_FpXQ(gel(e,1),T,p), Fq_to_FpXQ(gel(e,2),T,p), T, p);
    1442         854 :     Q = FpXQE_changepoint(Q, FqV_to_FpXQV(gel(e,3), T) , T, p);
    1443         854 :     break;
    1444             :   case t_FF_F2xq:
    1445             :     {
    1446      168336 :       long d = F2x_degree(T);
    1447             :       /* if #E(Fq) = 1 return [0] */
    1448      168336 :       if (d<=2 && typ(gel(e,1)) == t_VEC)
    1449             :       { /* over F2 or F4, supersingular */
    1450        1687 :         GEN v = gel(e,1), A6 = gel(e,2), a3 = gel(v,1), A4 = gel(v,2);
    1451        1687 :         if (F2x_equal1(a3) &&
    1452         196 :              ((d==1 && F2x_equal1(A4) && F2x_equal1(A6))
    1453         595 :            || (d==2 && !lgpol(A4)     && F2x_degree(A6)==1))) return ellinf();
    1454             :       }
    1455      168252 :       Q = random_F2xqE(gel(e,1), gel(e,2), T);
    1456      168252 :       Q = F2xqE_changepoint(Q, gel(e,3), T);
    1457      168252 :       break;
    1458             :     }
    1459             :   default:
    1460             :     /* if #E(Fq) = 1 return [0] */
    1461       75124 :     if (pp==3 && degpol(T)==1 && typ(gel(e,1))==t_VECSMALL)
    1462             :     { /* over F3, supersingular */
    1463           0 :       GEN mb4 = gel(e,1), b6 = gel(e,2);
    1464           0 :       if (F3x_equalm1(mb4) && F3x_equalm1(b6)) return ellinf();
    1465             :     }
    1466       75124 :     Q = random_FlxqE(gel(e,1), gel(e,2), T, pp);
    1467       75124 :     Q = FlxqE_changepoint(Q, gel(e,3), T, pp);
    1468             :   }
    1469      244230 :   return gerepilecopy(av, to_FFE(Q, fg));
    1470             : }
    1471             : 
    1472             : GEN
    1473      247702 : FF_ellmul(GEN E, GEN P, GEN n)
    1474             : {
    1475      247702 :   pari_sp av = avma;
    1476      247702 :   GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E), Q;
    1477             :   GEN T,p, Pp, Qp, e3;
    1478             :   ulong pp;
    1479      247702 :   _getFF(fg,&T,&p,&pp);
    1480      247702 :   switch (fg[1])
    1481             :   {
    1482             :   case t_FF_FpXQ:
    1483         854 :     e3 = FqV_to_FpXQV(gel(e,3),T);
    1484         854 :     Pp = FpXQE_changepointinv(RgE_to_FpXQE(P, T, p), e3, T, p);
    1485         854 :     Qp = FpXQE_mul(Pp, n, gel(e,1), T, p);
    1486         854 :     Q = FpXQE_changepoint(Qp, gel(e,3), T, p);
    1487         854 :     break;
    1488             :   case t_FF_F2xq:
    1489      184604 :     Pp = F2xqE_changepointinv(RgE_to_F2xqE(P, T), gel(e,3), T);
    1490      184604 :     Qp = F2xqE_mul(Pp, n, gel(e,1), T);
    1491      184604 :     Q = F2xqE_changepoint(Qp, gel(e,3), T);
    1492      184604 :     break;
    1493             :   default:
    1494       62244 :     Pp = FlxqE_changepointinv(RgE_to_FlxqE(P, T, pp), gel(e,3), T, pp);
    1495       62244 :     Qp = FlxqE_mul(Pp, n, gel(e,1), T, pp);
    1496       62244 :     Q = FlxqE_changepoint(Qp, gel(e,3), T, pp);
    1497             :   }
    1498      247702 :   return gerepilecopy(av, to_FFE(Q, fg));
    1499             : }
    1500             : 
    1501             : GEN
    1502        1750 : FF_ellorder(GEN E, GEN P, GEN o)
    1503             : {
    1504        1750 :   pari_sp av = avma;
    1505        1750 :   GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E);
    1506             :   GEN r,T,p,Pp,e3;
    1507             :   ulong pp;
    1508        1750 :   _getFF(fg,&T,&p,&pp);
    1509        1750 :   switch (fg[1])
    1510             :   {
    1511             :   case t_FF_FpXQ:
    1512          14 :     e3 = FqV_to_FpXQV(gel(e,3),T);
    1513          14 :     Pp = FpXQE_changepointinv(RgE_to_FpXQE(P,T,p), e3, T, p);
    1514          14 :     r = FpXQE_order(Pp, o, gel(e,1), T, p);
    1515          14 :     break;
    1516             :   case t_FF_F2xq:
    1517         280 :     Pp = F2xqE_changepointinv(RgE_to_F2xqE(P,T), gel(e,3), T);
    1518         280 :     r = F2xqE_order(Pp, o, gel(e,1), T);
    1519         280 :     break;
    1520             :   default:
    1521        1456 :     Pp = FlxqE_changepointinv(RgE_to_FlxqE(P,T,pp), gel(e,3), T, pp);
    1522        1456 :     r = FlxqE_order(Pp, o, gel(e,1), T, pp);
    1523             :   }
    1524        1750 :   return gerepileupto(av, r);
    1525             : }
    1526             : 
    1527             : GEN
    1528          91 : FF_elllog(GEN E, GEN P, GEN Q, GEN o)
    1529             : {
    1530          91 :   pari_sp av = avma;
    1531          91 :   GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E);
    1532             :   GEN r,T,p, Pp,Qp, e3;
    1533             :   ulong pp;
    1534          91 :   _getFF(fg,&T,&p,&pp);
    1535          91 :   switch(fg[1])
    1536             :   {
    1537             :   case t_FF_FpXQ:
    1538           0 :     e3 = FqV_to_FpXQV(gel(e,3),T);
    1539           0 :     Pp = FpXQE_changepointinv(RgE_to_FpXQE(P,T,p), e3, T, p);
    1540           0 :     Qp = FpXQE_changepointinv(RgE_to_FpXQE(Q,T,p), e3, T, p);
    1541           0 :     r = FpXQE_log(Pp, Qp, o, gel(e,1), T, p);
    1542           0 :     break;
    1543             :   case t_FF_F2xq:
    1544          42 :     Pp = F2xqE_changepointinv(RgE_to_F2xqE(P,T), gel(e,3), T);
    1545          42 :     Qp = F2xqE_changepointinv(RgE_to_F2xqE(Q,T), gel(e,3), T);
    1546          42 :     r = F2xqE_log(Pp, Qp, o, gel(e,1), T);
    1547          42 :     break;
    1548             :   default:
    1549          49 :     Pp = FlxqE_changepointinv(RgE_to_FlxqE(P,T,pp), gel(e,3), T, pp);
    1550          49 :     Qp = FlxqE_changepointinv(RgE_to_FlxqE(Q,T,pp), gel(e,3), T, pp);
    1551          49 :     r = FlxqE_log(Pp, Qp, o, gel(e,1), T, pp);
    1552             :   }
    1553          91 :   return gerepileupto(av, r);
    1554             : }
    1555             : 
    1556             : GEN
    1557        4984 : FF_ellweilpairing(GEN E, GEN P, GEN Q, GEN m)
    1558             : {
    1559        4984 :   GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E);
    1560             :   GEN r,T,p, Pp,Qp, e3;
    1561             :   ulong pp;
    1562        4984 :   GEN z=_initFF(fg,&T,&p,&pp);
    1563        4984 :   pari_sp av = avma;
    1564        4984 :   switch(fg[1])
    1565             :   {
    1566             :   case t_FF_FpXQ:
    1567           7 :     e3 = FqV_to_FpXQV(gel(e,3),T);
    1568           7 :     Pp = FpXQE_changepointinv(RgE_to_FpXQE(P,T,p), e3, T, p);
    1569           7 :     Qp = FpXQE_changepointinv(RgE_to_FpXQE(Q,T,p), e3, T, p);
    1570           7 :     r = FpXQE_weilpairing(Pp, Qp, m, gel(e,1), T, p);
    1571           7 :     break;
    1572             :   case t_FF_F2xq:
    1573        4963 :     Pp = F2xqE_changepointinv(RgE_to_F2xqE(P,T), gel(e,3), T);
    1574        4963 :     Qp = F2xqE_changepointinv(RgE_to_F2xqE(Q,T), gel(e,3), T);
    1575        4963 :     r = F2xqE_weilpairing(Pp, Qp, m, gel(e,1), T);
    1576        4963 :     break;
    1577             :   default:
    1578          14 :     Pp = FlxqE_changepointinv(RgE_to_FlxqE(P,T,pp), gel(e,3), T, pp);
    1579          14 :     Qp = FlxqE_changepointinv(RgE_to_FlxqE(Q,T,pp), gel(e,3), T, pp);
    1580          14 :     r = FlxqE_weilpairing(Pp, Qp, m, gel(e,1), T, pp);
    1581             :   }
    1582        4984 :   r = gerepileupto(av, r);
    1583        4984 :   return _mkFF(fg,z,r);
    1584             : }
    1585             : 
    1586             : GEN
    1587          91 : FF_elltatepairing(GEN E, GEN P, GEN Q, GEN m)
    1588             : {
    1589          91 :   GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E);
    1590             :   GEN r,T,p, Pp,Qp, e3;
    1591             :   ulong pp;
    1592          91 :   GEN z=_initFF(fg,&T,&p,&pp);
    1593          91 :   pari_sp av = avma;
    1594          91 :   switch(fg[1])
    1595             :   {
    1596             :   case t_FF_FpXQ:
    1597           7 :     e3 = FqV_to_FpXQV(gel(e,3),T);
    1598           7 :     Pp = FpXQE_changepointinv(RgE_to_FpXQE(P,T,p), e3, T, p);
    1599           7 :     Qp = FpXQE_changepointinv(RgE_to_FpXQE(Q,T,p), e3, T, p);
    1600           7 :     r = FpXQE_tatepairing(Pp, Qp, m, gel(e,1), T, p);
    1601           7 :     break;
    1602             :   case t_FF_F2xq:
    1603          28 :     Pp = F2xqE_changepointinv(RgE_to_F2xqE(P,T), gel(e,3), T);
    1604          28 :     Qp = F2xqE_changepointinv(RgE_to_F2xqE(Q,T), gel(e,3), T);
    1605          28 :     r = F2xqE_tatepairing(Pp, Qp, m, gel(e,1), T);
    1606          28 :     break;
    1607             :   default:
    1608          56 :     Pp = FlxqE_changepointinv(RgE_to_FlxqE(P,T,pp), gel(e,3), T, pp);
    1609          56 :     Qp = FlxqE_changepointinv(RgE_to_FlxqE(Q,T,pp), gel(e,3), T, pp);
    1610          56 :     r = FlxqE_tatepairing(Pp, Qp, m, gel(e,1), T, pp);
    1611             :   }
    1612          91 :   r = gerepileupto(av, r);
    1613          91 :   return _mkFF(fg,z,r);
    1614             : }
    1615             : 
    1616             : GEN
    1617      103663 : FFX_roots(GEN Pf, GEN ff)
    1618             : {
    1619      103663 :   pari_sp av = avma;
    1620             :   GEN r,T,p;
    1621             :   ulong pp;
    1622      103663 :   GEN P = FFX_to_raw(Pf, ff);
    1623      103663 :   _getFF(ff,&T,&p,&pp);
    1624      103663 :   switch(ff[1])
    1625             :   {
    1626             :   case t_FF_FpXQ:
    1627          85 :     r = FpXQX_roots(P, T, p);
    1628          85 :     break;
    1629             :   case t_FF_F2xq:
    1630       57512 :     r = F2xqX_roots(P, T);
    1631       57512 :     break;
    1632             :   default:
    1633       46066 :     r = FlxqX_roots(P, T, pp);
    1634             :   }
    1635      103663 :   return gerepilecopy(av, raw_to_FFC(r, ff));
    1636             : }
    1637             : 
    1638             : static GEN
    1639           7 : raw_to_FFXC(GEN x, GEN ff)
    1640           7 : { pari_APPLY_type(t_COL, raw_to_FFX(gel(x,i), ff)); }
    1641             : 
    1642             : static GEN
    1643         448 : raw_to_FFX_fact(GEN F, GEN ff)
    1644             : {
    1645             :   GEN y, u, v;
    1646         448 :   GEN P = gel(F,1), E = gel(F,2);
    1647         448 :   long j, l = lg(P);
    1648         448 :   y = cgetg(3,t_MAT);
    1649         448 :   u = cgetg(l,t_COL); gel(y,1) = u;
    1650         448 :   v = cgetg(l,t_COL); gel(y,2) = v;
    1651        2107 :   for (j=1; j<l; j++)
    1652             :   {
    1653        1659 :     gel(u,j) = raw_to_FFX(gel(P,j), ff);
    1654        1659 :     gel(v,j) = utoi(uel(E,j));
    1655             :   }
    1656         448 :   return y;
    1657             : }
    1658             : 
    1659             : static GEN
    1660        2244 : FFX_zero(GEN ff, long v)
    1661             : {
    1662        2244 :   GEN r = cgetg(3,t_POL);
    1663        2244 :   r[1] = evalvarn(v);
    1664        2244 :   gel(r,2) = FF_zero(ff);
    1665        2244 :   return r;
    1666             : }
    1667             : 
    1668             : static GEN
    1669      107332 : FFX_wrap2(GEN Pf, GEN Qf, GEN ff, GEN FpXQX(GEN, GEN, GEN, GEN),
    1670             :           GEN F2xqX(GEN, GEN, GEN), GEN FlxqX(GEN, GEN, GEN, ulong))
    1671             : {
    1672      107332 :   pari_sp av = avma;
    1673             :   GEN r,T,p;
    1674             :   ulong pp;
    1675      107332 :   GEN P = FFX_to_raw(Pf, ff);
    1676      107332 :   GEN Q = FFX_to_raw(Qf, ff);
    1677      107332 :   _getFF(ff,&T,&p,&pp);
    1678      107332 :   switch(ff[1])
    1679             :   {
    1680             :   case t_FF_FpXQ:
    1681        2374 :     r = FpXQX(P, Q, T, p);
    1682        2374 :     break;
    1683             :   case t_FF_F2xq:
    1684       39931 :     r = F2xqX(P, Q, T);
    1685       39931 :     break;
    1686             :   default:
    1687       65027 :     r = FlxqX(P, Q, T, pp);
    1688             :   }
    1689      107332 :   if (!lgpol(r)) { set_avma(av); return FFX_zero(ff, varn(Pf)); }
    1690      105088 :   return gerepilecopy(av, raw_to_FFX(r, ff));
    1691             : }
    1692             : 
    1693             : GEN
    1694      104161 : FFX_mul(GEN Pf, GEN Qf, GEN ff)
    1695      104161 : { return FFX_wrap2(Pf, Qf, ff, FpXQX_mul, F2xqX_mul, FlxqX_mul); }
    1696             : 
    1697             : GEN
    1698        2541 : FFX_gcd(GEN Pf, GEN Qf, GEN ff)
    1699        2541 : { return FFX_wrap2(Pf, Qf, ff, FpXQX_gcd, F2xqX_gcd, FlxqX_gcd); }
    1700             : 
    1701             : GEN
    1702        2296 : FFX_sqr(GEN Pf, GEN ff)
    1703             : {
    1704        2296 :   pari_sp av = avma;
    1705             :   GEN r,T,p;
    1706             :   ulong pp;
    1707        2296 :   GEN P = FFX_to_raw(Pf, ff);
    1708        2296 :   _getFF(ff,&T,&p,&pp);
    1709        2296 :   switch(ff[1])
    1710             :   {
    1711             :   case t_FF_FpXQ:
    1712         210 :     r = FpXQX_sqr(P, T, p);
    1713         210 :     break;
    1714             :   case t_FF_F2xq:
    1715         966 :     r = F2xqX_sqr(P, T);
    1716         966 :     break;
    1717             :   default:
    1718        1120 :     r = FlxqX_sqr(P, T, pp);
    1719             :   }
    1720        2296 :   if (!lgpol(r)) { set_avma(av); return FFX_zero(ff, varn(Pf)); }
    1721        2296 :   return gerepilecopy(av, raw_to_FFX(r, ff));
    1722             : }
    1723             : 
    1724             : GEN
    1725         616 : FFX_rem(GEN Pf, GEN Qf, GEN ff)
    1726         616 : { return FFX_wrap2(Pf, Qf, ff, FpXQX_rem, F2xqX_rem, FlxqX_rem); }
    1727             : 
    1728             : GEN
    1729          21 : FFX_resultant(GEN Pf, GEN Qf, GEN ff)
    1730             : {
    1731          21 :   pari_sp av = avma;
    1732             :   GEN r,T,p;
    1733             :   ulong pp;
    1734          21 :   GEN P = FFX_to_raw(Pf, ff);
    1735          21 :   GEN Q = FFX_to_raw(Qf, ff);
    1736          21 :   GEN z = _initFF(ff,&T,&p,&pp);
    1737          21 :   switch(ff[1])
    1738             :   {
    1739             :   case t_FF_FpXQ:
    1740           7 :     r = FpXQX_resultant(P, Q, T, p);
    1741           7 :     break;
    1742             :   case t_FF_F2xq:
    1743           7 :     r = F2xqX_resultant(P, Q, T);
    1744           7 :     break;
    1745             :   default:
    1746           7 :     r = FlxqX_resultant(P, Q, T, pp);
    1747             :   }
    1748          21 :   return gerepileupto(av, _mkFF(ff,z,r));
    1749             : }
    1750             : 
    1751             : GEN
    1752          35 : FFX_disc(GEN Pf, GEN ff)
    1753             : {
    1754          35 :   pari_sp av = avma;
    1755             :   GEN r,T,p;
    1756             :   ulong pp;
    1757          35 :   GEN P = FFX_to_raw(Pf, ff);
    1758          35 :   GEN z = _initFF(ff,&T,&p,&pp);
    1759          35 :   switch(ff[1])
    1760             :   {
    1761             :   case t_FF_FpXQ:
    1762           7 :     r = FpXQX_disc(P, T, p);
    1763           7 :     break;
    1764             :   case t_FF_F2xq:
    1765          14 :     r = F2xqX_disc(P, T);
    1766          14 :     break;
    1767             :   default:
    1768          14 :     r = FlxqX_disc(P, T, pp);
    1769             :   }
    1770          35 :   return gerepileupto(av, _mkFF(ff,z,r));
    1771             : }
    1772             : 
    1773             : static GEN
    1774          21 : gc_gcdext(pari_sp av, GEN r, GEN *u, GEN *v)
    1775             : {
    1776          21 :   if (!u && !v) return gerepilecopy(av, r);
    1777          21 :   if (u  &&  v) gerepileall(av, 3, &r, u, v);
    1778           0 :   else          gerepileall(av, 2, &r, u ? u: v);
    1779          21 :   return r;
    1780             : }
    1781             : 
    1782             : GEN
    1783          21 : FFX_extgcd(GEN Pf, GEN Qf, GEN ff, GEN *pt_Uf, GEN *pt_Vf)
    1784             : {
    1785          21 :   pari_sp av = avma;
    1786             :   GEN r,T,p;
    1787             :   ulong pp;
    1788          21 :   GEN P = FFX_to_raw(Pf, ff);
    1789          21 :   GEN Q = FFX_to_raw(Qf, ff);
    1790          21 :   _getFF(ff,&T,&p,&pp);
    1791          21 :   switch(ff[1])
    1792             :   {
    1793             :   case t_FF_FpXQ:
    1794           0 :     r = FpXQX_extgcd(P, Q, T, p, pt_Uf, pt_Vf);
    1795           0 :     break;
    1796             :   case t_FF_F2xq:
    1797           7 :     r = F2xqX_extgcd(P, Q, T, pt_Uf, pt_Vf);
    1798           7 :     break;
    1799             :   default:
    1800          14 :     r = FlxqX_extgcd(P, Q, T, pp, pt_Uf, pt_Vf);
    1801             :   }
    1802          21 :   if (pt_Uf) *pt_Uf = raw_to_FFX(*pt_Uf, ff);
    1803          21 :   if (pt_Vf) *pt_Vf = raw_to_FFX(*pt_Vf, ff);
    1804          21 :   return gc_gcdext(av, raw_to_FFX(r, ff), pt_Uf, pt_Vf);
    1805             : }
    1806             : 
    1807             : GEN
    1808           0 : FFXQ_sqr(GEN Pf, GEN Qf, GEN ff)
    1809           0 : { return FFX_wrap2(Pf, Qf, ff, FpXQXQ_sqr, F2xqXQ_sqr, FlxqXQ_sqr); }
    1810             : 
    1811             : GEN
    1812          14 : FFXQ_inv(GEN Pf, GEN Qf, GEN ff)
    1813          14 : { return FFX_wrap2(Pf, Qf, ff, FpXQXQ_inv, F2xqXQ_inv, FlxqXQ_inv); }
    1814             : 
    1815             : GEN
    1816          14 : FFXQ_mul(GEN Pf, GEN Qf, GEN Sf, GEN ff)
    1817             : {
    1818          14 :   pari_sp av = avma;
    1819             :   GEN r,T,p;
    1820             :   ulong pp;
    1821          14 :   GEN P = FFX_to_raw(Pf, ff);
    1822          14 :   GEN Q = FFX_to_raw(Qf, ff);
    1823          14 :   GEN S = FFX_to_raw(Sf, ff);
    1824          14 :   _getFF(ff,&T,&p,&pp);
    1825          14 :   switch(ff[1])
    1826             :   {
    1827             :   case t_FF_FpXQ:
    1828           0 :     r = FpXQXQ_mul(P, Q, S, T, p);
    1829           0 :     break;
    1830             :   case t_FF_F2xq:
    1831           7 :     r = F2xqXQ_mul(P, Q, S, T);
    1832           7 :     break;
    1833             :   default:
    1834           7 :     r = FlxqXQ_mul(P, Q, S, T, pp);
    1835             :   }
    1836          14 :   if (!lgpol(r)) { set_avma(av); return FFX_zero(ff, varn(Pf)); }
    1837          14 :   return gerepilecopy(av, raw_to_FFX(r, ff));
    1838             : }
    1839             : 
    1840             : long
    1841         168 : FFX_ispower(GEN Pf, long k, GEN ff, GEN *pt_r)
    1842             : {
    1843         168 :   pari_sp av = avma;
    1844             :   GEN P,T,p;
    1845             :   ulong pp;
    1846             :   long s;
    1847         168 :   if (degpol(Pf) % k) return 0;
    1848         168 :   P = FFX_to_raw(Pf, ff);
    1849         168 :   _getFF(ff,&T,&p,&pp);
    1850         168 :   switch(ff[1])
    1851             :   {
    1852             :   case t_FF_FpXQ:
    1853          56 :     s = FpXQX_ispower(P, k, T, p, pt_r);
    1854          56 :     break;
    1855             :   case t_FF_F2xq:
    1856          56 :     s = F2xqX_ispower(P, k, T, pt_r);
    1857          56 :     break;
    1858             :   default:
    1859          56 :     s = FlxqX_ispower(P, k, T, pp, pt_r);
    1860             :   }
    1861         168 :   if (s==0) return gc_long(av,0);
    1862         147 :   if (pt_r)
    1863         147 :     *pt_r = gerepilecopy(av, raw_to_FFX(*pt_r, ff));
    1864           0 :   else set_avma(av);
    1865         147 :   return 1;
    1866             : }
    1867             : 
    1868             : GEN
    1869         441 : FFX_factor(GEN Pf, GEN ff)
    1870             : {
    1871         441 :   pari_sp av = avma;
    1872             :   GEN r,T,p;
    1873             :   ulong pp;
    1874         441 :   GEN P = FFX_to_raw(Pf, ff);
    1875         441 :   _getFF(ff,&T,&p,&pp);
    1876         441 :   switch(ff[1])
    1877             :   {
    1878             :   case t_FF_FpXQ:
    1879         121 :     r = FpXQX_factor(P, T, p);
    1880         121 :     break;
    1881             :   case t_FF_F2xq:
    1882         133 :     r = F2xqX_factor(P, T);
    1883         133 :     break;
    1884             :   default:
    1885         187 :     r = FlxqX_factor(P, T, pp);
    1886             :   }
    1887         441 :   return gerepilecopy(av, raw_to_FFX_fact(r, ff));
    1888             : }
    1889             : 
    1890             : GEN
    1891           7 : FFX_factor_squarefree(GEN Pf, GEN ff)
    1892             : {
    1893           7 :   pari_sp av = avma;
    1894             :   GEN r,T,p;
    1895             :   ulong pp;
    1896           7 :   GEN P = FFX_to_raw(Pf, ff);
    1897           7 :   _getFF(ff,&T,&p,&pp);
    1898           7 :   switch(ff[1])
    1899             :   {
    1900             :   case t_FF_FpXQ:
    1901           7 :     r = FpXQX_factor_squarefree(P, T, p);
    1902           7 :     break;
    1903             :   case t_FF_F2xq:
    1904           0 :     r = F2xqX_factor_squarefree(P, T);
    1905           0 :     break;
    1906             :   default:
    1907           0 :     r = FlxqX_factor_squarefree(P, T, pp);
    1908             :   }
    1909           7 :   return gerepilecopy(av, raw_to_FFXC(r, ff));
    1910             : }
    1911             : 
    1912             : GEN
    1913           7 : FFX_ddf(GEN Pf, GEN ff)
    1914             : {
    1915           7 :   pari_sp av = avma;
    1916             :   GEN r,T,p;
    1917             :   ulong pp;
    1918           7 :   GEN P = FFX_to_raw(Pf, ff);
    1919           7 :   _getFF(ff,&T,&p,&pp);
    1920           7 :   switch(ff[1])
    1921             :   {
    1922             :   case t_FF_FpXQ:
    1923           7 :     r = FpXQX_ddf(P, T, p);
    1924           7 :     break;
    1925             :   case t_FF_F2xq:
    1926           0 :     r = F2xqX_ddf(P, T);
    1927           0 :     break;
    1928             :   default:
    1929           0 :     r = FlxqX_ddf(P, T, pp);
    1930             :   }
    1931           7 :   return gerepilecopy(av, raw_to_FFX_fact(r, ff));
    1932             : }
    1933             : 
    1934             : GEN
    1935         126 : FFX_degfact(GEN Pf, GEN ff)
    1936             : {
    1937         126 :   pari_sp av = avma;
    1938             :   GEN r,T,p;
    1939             :   ulong pp;
    1940         126 :   GEN P = FFX_to_raw(Pf, ff);
    1941         126 :   _getFF(ff, &T, &p, &pp);
    1942         126 :   switch(ff[1])
    1943             :   {
    1944             :   case t_FF_FpXQ:
    1945          42 :     r = FpXQX_degfact(P, T, p);
    1946          42 :     break;
    1947             :   case t_FF_F2xq:
    1948          42 :     r = F2xqX_degfact(P, T);
    1949          42 :     break;
    1950             :   default:
    1951          42 :     r = FlxqX_degfact(P, T, pp);
    1952             :   }
    1953         126 :   return gerepilecopy(av, r);
    1954             : }
    1955             : 
    1956             : GEN
    1957           0 : FqX_to_FFX(GEN x, GEN ff)
    1958             : {
    1959             :   long i, lx;
    1960           0 :   GEN y =  cgetg_copy(x,&lx);
    1961           0 :   y[1] = x[1];
    1962           0 :   for (i=2; i<lx; i++) gel(y,i) = Fq_to_FF(gel(x,i), ff);
    1963           0 :   return y;
    1964             : }
    1965             : 
    1966             : GEN
    1967        2483 : ffgen(GEN T, long v)
    1968             : {
    1969        2483 :   GEN A, p = NULL, ff = cgetg(5,t_FFELT);
    1970             :   long d;
    1971        2484 :   switch(typ(T))
    1972             :   {
    1973             :     case t_FFELT:
    1974          28 :       p = FF_p_i(T); T = FF_mod(T); d = degpol(T);
    1975          28 :       break;
    1976             :     case t_POL:
    1977         259 :       d = degpol(T); p = NULL;
    1978         259 :       if (d < 1 || !RgX_is_FpX(T, &p) || !p) pari_err_TYPE("ffgen",T);
    1979         259 :       T = RgX_to_FpX(T, p);
    1980             :       /* testing for irreducibility is too costly */
    1981         259 :       if (!FpX_is_squarefree(T,p)) pari_err_IRREDPOL("ffgen",T);
    1982         252 :       break;
    1983             :     case t_INT:
    1984        1784 :       d = ispseudoprimepower(T,&p);
    1985        1780 :       if (!d) pari_err_PRIME("ffgen",T);
    1986        1780 :       T = init_Fq(p, d, v);
    1987        1784 :       break;
    1988             :     case t_VEC: case t_COL:
    1989         413 :       if (lg(T) == 3) {
    1990         413 :         p = gel(T,1);
    1991         413 :         A = gel(T,2);
    1992         413 :         if (typ(p) == t_INT && typ(A) == t_INT)
    1993             :         {
    1994         413 :           d = itos(A);
    1995         413 :           T = init_Fq(p, d, v);
    1996         413 :           break;
    1997             :         }
    1998             :       }
    1999             :     default:
    2000           0 :       pari_err_TYPE("ffgen",T);
    2001           0 :       return NULL;
    2002             :   }
    2003        2477 :   if (v < 0) v = varn(T);
    2004        2477 :   if (lgefint(p)==3)
    2005             :   {
    2006        2174 :     ulong pp = p[2];
    2007        2174 :     long sv = evalvarn(v);
    2008        2174 :     if (pp==2)
    2009             :     {
    2010        1007 :       ff[1] = t_FF_F2xq;
    2011        1007 :       T = ZX_to_F2x(T); T[1] = sv;
    2012        1005 :       A = polx_F2x(sv); if (d == 1) A = F2x_rem(A, T);
    2013        1006 :       p = gen_2;
    2014             :     }
    2015             :     else
    2016             :     {
    2017        1167 :       ff[1] = t_FF_Flxq;
    2018        1167 :       T = ZX_to_Flx(T,pp); T[1] = sv;
    2019        1167 :       A = polx_Flx(sv); if (d == 1) A = Flx_rem(A, T, pp);
    2020        1167 :       p = icopy(p);
    2021             :     }
    2022             :   }
    2023             :   else
    2024             :   {
    2025         303 :     ff[1] = t_FF_FpXQ;
    2026         303 :     setvarn(T,v);
    2027         303 :     A = pol_x(v); if (d == 1) A = FpX_rem(A, T, p);
    2028         303 :     p = icopy(p);
    2029             :   }
    2030        2476 :   gel(ff,2) = A;
    2031        2476 :   gel(ff,3) = T;
    2032        2476 :   gel(ff,4) = p; return ff;
    2033             : }
    2034             : 
    2035             : GEN
    2036        2989 : p_to_FF(GEN p, long v)
    2037             : {
    2038             :   GEN A, T;
    2039        2989 :   GEN ff = cgetg(5,t_FFELT);
    2040        2989 :   if (lgefint(p)==3)
    2041             :   {
    2042        2984 :     ulong pp = p[2];
    2043        2984 :     long sv = evalvarn(v);
    2044        2984 :     if (pp==2)
    2045             :     {
    2046         329 :       ff[1] = t_FF_F2xq;
    2047         329 :       T = polx_F2x(sv);
    2048         329 :       A = pol1_F2x(sv);
    2049         329 :       p = gen_2;
    2050             :     }
    2051             :     else
    2052             :     {
    2053        2655 :       ff[1] = t_FF_Flxq;
    2054        2655 :       T = polx_Flx(sv);
    2055        2655 :       A = pol1_Flx(sv);
    2056        2655 :       p = icopy(p);
    2057             :     }
    2058             :   }
    2059             :   else
    2060             :   {
    2061           5 :     ff[1] = t_FF_FpXQ;
    2062           5 :     T = pol_x(v);
    2063           5 :     A = pol_1(v);
    2064           5 :     p = icopy(p);
    2065             :   }
    2066        2989 :   gel(ff,2) = A;
    2067        2989 :   gel(ff,3) = T;
    2068        2989 :   gel(ff,4) = p; return ff;
    2069             : }
    2070             : GEN
    2071        4179 : Tp_to_FF(GEN T, GEN p)
    2072             : {
    2073             :   GEN A, ff;
    2074             :   long v;
    2075        4179 :   if (!T) return p_to_FF(p,0);
    2076        3990 :   ff = cgetg(5,t_FFELT);
    2077        3990 :   v = varn(T);
    2078        3990 :   if (lgefint(p)==3)
    2079             :   {
    2080        3780 :     ulong pp = p[2];
    2081        3780 :     long sv = evalvarn(v);
    2082        3780 :     if (pp==2)
    2083             :     {
    2084        1526 :       ff[1] = t_FF_F2xq;
    2085        1526 :       T = ZX_to_F2x(T);
    2086        1526 :       A = pol1_F2x(sv);
    2087        1526 :       p = gen_2;
    2088             :     }
    2089             :     else
    2090             :     {
    2091        2254 :       ff[1] = t_FF_Flxq;
    2092        2254 :       T = ZX_to_Flx(T, pp);
    2093        2254 :       A = pol1_Flx(sv);
    2094        2254 :       p = icopy(p);
    2095             :     }
    2096             :   }
    2097             :   else
    2098             :   {
    2099         210 :     ff[1] = t_FF_FpXQ;
    2100         210 :     T = ZX_copy(T);
    2101         210 :     A = pol_1(v);
    2102         210 :     p = icopy(p);
    2103             :   }
    2104        3990 :   gel(ff,2) = A;
    2105        3990 :   gel(ff,3) = T;
    2106        3990 :   gel(ff,4) = p; return ff;
    2107             : }
    2108             : 
    2109             : GEN
    2110          28 : fforder(GEN x, GEN o)
    2111             : {
    2112          28 :   if (typ(x)!=t_FFELT) pari_err_TYPE("fforder",x);
    2113          28 :   return FF_order(x,o);
    2114             : }
    2115             : 
    2116             : GEN
    2117         392 : ffprimroot(GEN x, GEN *o)
    2118             : {
    2119         392 :   if (typ(x)!=t_FFELT) pari_err_TYPE("ffprimroot",x);
    2120         392 :   return FF_primroot(x,o);
    2121             : }
    2122             : 
    2123             : GEN
    2124         182 : fflog(GEN x, GEN g, GEN o)
    2125             : {
    2126         182 :   if (typ(x)!=t_FFELT) pari_err_TYPE("fflog",x);
    2127         182 :   if (typ(g)!=t_FFELT) pari_err_TYPE("fflog",g);
    2128         182 :   return FF_log(x,g,o);
    2129             : }
    2130             : 
    2131             : GEN
    2132      170653 : ffrandom(GEN ff)
    2133             : {
    2134             :   ulong pp;
    2135      170653 :   GEN r, T, p, z = _initFF(ff,&T,&p,&pp);
    2136      170653 :   switch(ff[1])
    2137             :   {
    2138             :   case t_FF_FpXQ:
    2139       13472 :     r = random_FpX(degpol(T), varn(T), p);
    2140       13472 :     break;
    2141             :   case t_FF_F2xq:
    2142      117271 :     r = random_F2x(F2x_degree(T), T[1]);
    2143      117271 :     break;
    2144             :   default:
    2145       39910 :     r = random_Flx(degpol(T), T[1], pp);
    2146             :   }
    2147      170653 :   return _mkFF(ff,z,r);
    2148             : }
    2149             : 
    2150             : int
    2151    11574016 : Rg_is_FF(GEN c, GEN *ff)
    2152             : {
    2153    11574016 :   switch(typ(c))
    2154             :   {
    2155             :   case t_FFELT:
    2156        8008 :     if (!*ff) *ff = c;
    2157        7840 :     else if (!FF_samefield(*ff, c)) return 0;
    2158        8008 :     break;
    2159             :   default:
    2160    11566008 :     return 0;
    2161             :   }
    2162        8008 :   return 1;
    2163             : }
    2164             : 
    2165             : int
    2166    11566596 : RgC_is_FFC(GEN x, GEN *ff)
    2167             : {
    2168    11566596 :   long i, lx = lg(x);
    2169    11574604 :   for (i=lx-1; i>0; i--)
    2170    11574016 :     if (!Rg_is_FF(gel(x,i), ff)) return 0;
    2171         588 :   return (*ff != NULL);
    2172             : }
    2173             : 
    2174             : int
    2175    11566085 : RgM_is_FFM(GEN x, GEN *ff)
    2176             : {
    2177    11566085 :   long j, lx = lg(x);
    2178    11566596 :   for (j=lx-1; j>0; j--)
    2179    11566519 :     if (!RgC_is_FFC(gel(x,j), ff)) return 0;
    2180          77 :   return (*ff != NULL);
    2181             : }
    2182             : 
    2183             : static GEN
    2184        4500 : FqC_to_FpXQC(GEN x, GEN T, GEN p)
    2185             : {
    2186             :   long i, lx;
    2187        4500 :   GEN y = cgetg_copy(x,&lx);
    2188       92348 :   for(i=1; i<lx; i++)
    2189       87848 :     gel(y, i) = Fq_to_FpXQ(gel(x, i), T, p);
    2190        4500 :   return y;
    2191             : }
    2192             : 
    2193             : static GEN
    2194         497 : FqM_to_FpXQM(GEN x, GEN T, GEN p)
    2195             : {
    2196             :   long i, lx;
    2197         497 :   GEN y = cgetg_copy(x,&lx);
    2198        4927 :   for(i=1; i<lx; i++)
    2199        4430 :     gel(y, i) = FqC_to_FpXQC(gel(x, i), T, p);
    2200         497 :   return y;
    2201             : }
    2202             : 
    2203             : /* for functions t_MAT -> t_MAT */
    2204             : static GEN
    2205         308 : FFM_wrap(GEN M, GEN ff, GEN (*Fq)(GEN,GEN,GEN),
    2206             :                        GEN (*Flxq)(GEN,GEN,ulong),
    2207             :                        GEN (*F2xq)(GEN,GEN))
    2208             : {
    2209         308 :   pari_sp av = avma;
    2210             :   ulong pp;
    2211             :   GEN T, p;
    2212         308 :   _getFF(ff,&T,&p,&pp); M = FFM_to_raw(M, ff);
    2213         308 :   switch(ff[1])
    2214             :   {
    2215         119 :   case t_FF_FpXQ: M = Fq(M,T,p); if (M) M = FqM_to_FpXQM(M,T,p);
    2216         119 :                   break;
    2217          70 :   case t_FF_F2xq: M = F2xq(M,T); break;
    2218         119 :   default: M = Flxq(M,T,pp); break;
    2219             :   }
    2220         308 :   if (!M) return gc_NULL(av);
    2221         273 :   return gerepilecopy(av, raw_to_FFM(M, ff));
    2222             : }
    2223             : 
    2224             : /* for functions (t_MAT, t_MAT) -> t_MAT */
    2225             : static GEN
    2226        4466 : FFM_FFM_wrap(GEN M, GEN N, GEN ff,
    2227             :              GEN (*Fq)(GEN, GEN, GEN, GEN),
    2228             :              GEN (*Flxq)(GEN, GEN, GEN, ulong),
    2229             :              GEN (*F2xq)(GEN, GEN, GEN))
    2230             : {
    2231        4466 :   pari_sp av = avma;
    2232             :   ulong pp;
    2233             :   GEN T, p;
    2234        4466 :   int is_sqr = M==N;
    2235        4466 :   _getFF(ff, &T, &p, &pp);
    2236        4466 :   M = FFM_to_raw(M, ff);
    2237        4466 :   N = is_sqr? M: FFM_to_raw(N, ff);
    2238        4466 :   switch(ff[1])
    2239             :   {
    2240         427 :   case t_FF_FpXQ: M = Fq(M, N, T, p); if (M) M = FqM_to_FpXQM(M, T, p);
    2241         427 :                   break;
    2242        1449 :   case t_FF_F2xq: M = F2xq(M, N, T); break;
    2243        2590 :   default: M = Flxq(M, N, T, pp); break;
    2244             :   }
    2245        4466 :   if (!M) return gc_NULL(av);
    2246        4375 :   return gerepilecopy(av, raw_to_FFM(M, ff));
    2247             : }
    2248             : 
    2249             : /* for functions (t_MAT, t_COL) -> t_COL */
    2250             : static GEN
    2251         196 : FFM_FFC_wrap(GEN M, GEN C, GEN ff,
    2252             :              GEN (*Fq)(GEN, GEN, GEN, GEN),
    2253             :              GEN (*Flxq)(GEN, GEN, GEN, ulong),
    2254             :              GEN (*F2xq)(GEN, GEN, GEN))
    2255             : {
    2256         196 :   pari_sp av = avma;
    2257             :   ulong pp;
    2258             :   GEN T, p;
    2259         196 :   _getFF(ff, &T, &p, &pp);
    2260         196 :   M = FFM_to_raw(M, ff);
    2261         196 :   C = FFC_to_raw(C, ff);
    2262         196 :   switch(ff[1])
    2263             :   {
    2264          63 :   case t_FF_FpXQ: C = Fq(M, C, T, p); if (C) C = FqC_to_FpXQC(C, T, p);
    2265          63 :                   break;
    2266          70 :   case t_FF_F2xq: C = F2xq(M, C, T); break;
    2267          63 :   default: C = Flxq(M, C, T, pp); break;
    2268             :   }
    2269         196 :   if (!C) return gc_NULL(av);
    2270         147 :   return gerepilecopy(av, raw_to_FFC(C, ff));
    2271             : }
    2272             : 
    2273             : GEN
    2274          77 : FFM_ker(GEN M, GEN ff)
    2275          77 : { return FFM_wrap(M,ff, &FqM_ker,&FlxqM_ker,&F2xqM_ker); }
    2276             : GEN
    2277          49 : FFM_image(GEN M, GEN ff)
    2278          49 : { return FFM_wrap(M,ff, &FqM_image,&FlxqM_image,&F2xqM_image); }
    2279             : GEN
    2280         147 : FFM_inv(GEN M, GEN ff)
    2281         147 : { return FFM_wrap(M,ff, &FqM_inv,&FlxqM_inv,&F2xqM_inv); }
    2282             : GEN
    2283          35 : FFM_suppl(GEN M, GEN ff)
    2284          35 : { return FFM_wrap(M,ff, &FqM_suppl,&FlxqM_suppl,&F2xqM_suppl); }
    2285             : 
    2286             : GEN
    2287          84 : FFM_deplin(GEN M, GEN ff)
    2288             : {
    2289          84 :   pari_sp av = avma;
    2290             :   ulong pp;
    2291             :   GEN C, T, p;
    2292          84 :   _getFF(ff, &T, &p, &pp); M = FFM_to_raw(M, ff);
    2293          84 :   switch(ff[1]) {
    2294          35 :   case t_FF_FpXQ: C = FqM_deplin(M, T, p);
    2295          35 :     if (C) C = FqC_to_FpXQC(C, T, p); break;
    2296          14 :   case t_FF_F2xq: C = F2xqM_deplin(M, T); break;
    2297          35 :   default: C = FlxqM_deplin(M, T, pp); break;
    2298             :   }
    2299          84 :   if (!C) return gc_NULL(av);
    2300          49 :   return gerepilecopy(av, raw_to_FFC(C, ff));
    2301             : }
    2302             : 
    2303             : GEN
    2304          21 : FFM_indexrank(GEN M, GEN ff)
    2305             : {
    2306          21 :   pari_sp av = avma;
    2307             :   ulong pp;
    2308             :   GEN R, T, p;
    2309          21 :   _getFF(ff,&T,&p,&pp); M = FFM_to_raw(M, ff);
    2310          21 :   switch(ff[1]) {
    2311           7 :   case t_FF_FpXQ: R = FqM_indexrank(M,T,p); break;
    2312           7 :   case t_FF_F2xq: R = F2xqM_indexrank(M,T); break;
    2313           7 :   default: R = FlxqM_indexrank(M,T,pp); break;
    2314             :   }
    2315          21 :   return gerepileupto(av, R);
    2316             : }
    2317             : 
    2318             : long
    2319          63 : FFM_rank(GEN M, GEN ff)
    2320             : {
    2321          63 :   pari_sp av = avma;
    2322             :   long r;
    2323             :   ulong pp;
    2324             :   GEN T, p;
    2325          63 :   _getFF(ff,&T,&p,&pp); M = FFM_to_raw(M, ff);
    2326          63 :   switch(ff[1])
    2327             :   {
    2328          28 :   case t_FF_FpXQ: r = FqM_rank(M,T,p); break;
    2329           7 :   case t_FF_F2xq: r = F2xqM_rank(M,T); break;
    2330          28 :   default: r = FlxqM_rank(M,T,pp); break;
    2331             :   }
    2332          63 :   return gc_long(av,r);
    2333             : }
    2334             : GEN
    2335          63 : FFM_det(GEN M, GEN ff)
    2336             : {
    2337          63 :   pari_sp av = avma;
    2338             :   ulong pp;
    2339             :   GEN d, T, p;
    2340          63 :   _getFF(ff,&T,&p,&pp); M = FFM_to_raw(M, ff);
    2341          63 :   switch(ff[1])
    2342             :   {
    2343          28 :   case t_FF_FpXQ: d = FqM_det(M,T,p); break;
    2344           7 :   case t_FF_F2xq: d = F2xqM_det(M,T); break;
    2345          28 :   default: d = FlxqM_det(M,T,pp); break;
    2346             :   }
    2347          63 :   return gerepilecopy(av, mkFF_i(ff, d));
    2348             : }
    2349             : 
    2350             : GEN
    2351          56 : FFM_FFC_gauss(GEN M, GEN C, GEN ff)
    2352             : {
    2353          56 :   return FFM_FFC_wrap(M, C, ff, FqM_FqC_gauss,
    2354             :                       FlxqM_FlxqC_gauss, F2xqM_F2xqC_gauss);
    2355             : }
    2356             : 
    2357             : GEN
    2358          63 : FFM_gauss(GEN M, GEN N, GEN ff)
    2359             : {
    2360          63 :   return FFM_FFM_wrap(M, N, ff, FqM_gauss,
    2361             :                       FlxqM_gauss, F2xqM_gauss);
    2362             : }
    2363             : 
    2364             : GEN
    2365          63 : FFM_FFC_invimage(GEN M, GEN C, GEN ff)
    2366             : {
    2367          63 :   return FFM_FFC_wrap(M, C, ff, FqM_FqC_invimage,
    2368             :                       FlxqM_FlxqC_invimage, F2xqM_F2xqC_invimage);
    2369             : }
    2370             : 
    2371             : GEN
    2372         105 : FFM_invimage(GEN M, GEN N, GEN ff)
    2373             : {
    2374         105 :   return FFM_FFM_wrap(M, N, ff, FqM_invimage,
    2375             :                       FlxqM_invimage, F2xqM_invimage);
    2376             : }
    2377             : 
    2378             : GEN
    2379          77 : FFM_FFC_mul(GEN M, GEN C, GEN ff)
    2380             : {
    2381          77 :   return FFM_FFC_wrap(M, C, ff, FqM_FqC_mul,
    2382             :                       FlxqM_FlxqC_mul, F2xqM_F2xqC_mul);
    2383             : }
    2384             : 
    2385             : GEN
    2386        4298 : FFM_mul(GEN M, GEN N, GEN ff)
    2387             : {
    2388        4298 :   return FFM_FFM_wrap(M, N, ff, FqM_mul, FlxqM_mul, F2xqM_mul);
    2389             : }

Generated by: LCOV version 1.13