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

Generated by: LCOV version 1.11