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

Generated by: LCOV version 1.13