Code coverage tests

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

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

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

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

Generated by: LCOV version 1.11