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-bordeaux1.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 - F2xqE.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.8.0 lcov report (development 17932-6fdb233) Lines: 383 408 93.9 %
Date: 2015-07-31 Functions: 50 53 94.3 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 125 155 80.6 %

           Branch data     Line data    Source code
       1                 :            : /* Copyright (C) 2012  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                 :            : /* Not so fast arithmetic with points over elliptic curves over F_2^n */
      18                 :            : 
      19                 :            : /***********************************************************************/
      20                 :            : /**                                                                   **/
      21                 :            : /**                              F2xqE                                **/
      22                 :            : /**                                                                   **/
      23                 :            : /***********************************************************************/
      24                 :            : 
      25                 :            : /* Theses functions deal with point over elliptic curves over F_2^n defined
      26                 :            :  * by an equation of the form:
      27                 :            :  ** y^2+x*y=x^3+a_2*x^2+a_6 if the curve is ordinary.
      28                 :            :  ** y^2+a_3*y=x^3+a_4*x+a_6 if the curve is supersingular.
      29                 :            :  * Most of the time a6 is omitted since it can be recovered from any point
      30                 :            :  * on the curve.
      31                 :            :  * For supersingular curves, the parameter a2 is replaced by [a3,a4,a3^-1].
      32                 :            :  */
      33                 :            : 
      34                 :            : GEN
      35                 :      14609 : RgE_to_F2xqE(GEN x, GEN T)
      36                 :            : {
      37         [ +  + ]:      14609 :   if (ell_is_inf(x)) return x;
      38                 :      14609 :   retmkvec2(Rg_to_F2xq(gel(x,1),T),Rg_to_F2xq(gel(x,2),T));
      39                 :            : }
      40                 :            : 
      41                 :            : GEN
      42                 :      35525 : F2xqE_changepoint(GEN x, GEN ch, GEN T)
      43                 :            : {
      44                 :      35525 :   pari_sp av = avma;
      45                 :            :   GEN p1,z,u,r,s,t,v,v2,v3;
      46         [ +  + ]:      35525 :   if (ell_is_inf(x)) return x;
      47                 :      21350 :   u = gel(ch,1); r = gel(ch,2);
      48                 :      21350 :   s = gel(ch,3); t = gel(ch,4);
      49                 :      21350 :   v = F2xq_inv(u, T); v2 = F2xq_sqr(v, T); v3 = F2xq_mul(v,v2, T);
      50                 :      21350 :   p1 = F2x_add(gel(x,1),r);
      51                 :      21350 :   z = cgetg(3,t_VEC);
      52                 :      21350 :   gel(z,1) = F2xq_mul(v2, p1, T);
      53                 :      21350 :   gel(z,2) = F2xq_mul(v3, F2x_add(gel(x,2), F2x_add(F2xq_mul(s, p1, T),t)), T);
      54                 :      35525 :   return gerepileupto(av, z);
      55                 :            : }
      56                 :            : 
      57                 :            : GEN
      58                 :      14609 : F2xqE_changepointinv(GEN x, GEN ch, GEN T)
      59                 :            : {
      60                 :            :   GEN u, r, s, t, X, Y, u2, u3, u2X, z;
      61         [ +  + ]:      14609 :   if (ell_is_inf(x)) return x;
      62                 :      14602 :   X = gel(x,1); Y = gel(x,2);
      63                 :      14602 :   u = gel(ch,1); r = gel(ch,2);
      64                 :      14602 :   s = gel(ch,3); t = gel(ch,4);
      65                 :      14602 :   u2 = F2xq_sqr(u, T); u3 = F2xq_mul(u,u2, T);
      66                 :      14602 :   u2X = F2xq_mul(u2,X, T);
      67                 :      14602 :   z = cgetg(3, t_VEC);
      68                 :      14602 :   gel(z,1) = F2x_add(u2X,r);
      69                 :      14602 :   gel(z,2) = F2x_add(F2xq_mul(u3,Y, T), F2x_add(F2xq_mul(s,u2X, T), t));
      70                 :      14609 :   return z;
      71                 :            : }
      72                 :            : 
      73                 :            : static GEN
      74                 :       3514 : nonzerotrace_F2xq(GEN T)
      75                 :            : {
      76                 :       3514 :   pari_sp av = avma;
      77                 :       3514 :   long n = F2x_degree(T), vs = T[1];
      78                 :            :   GEN a;
      79         [ +  + ]:       3514 :   if (odd(n))
      80                 :       1162 :     return pol1_F2x(vs);
      81                 :            :   do
      82                 :            :   {
      83                 :       4515 :     avma = av;
      84                 :       4515 :     a = random_F2x(n, vs);
      85         [ +  + ]:       4515 :   } while (F2xq_trace(a, T)==0);
      86                 :       3514 :   return a;
      87                 :            : }
      88                 :            : 
      89                 :            : void
      90                 :       3514 : F2xq_elltwist(GEN a, GEN a6, GEN T, GEN *pt_a, GEN *pt_a6)
      91                 :            : {
      92                 :       3514 :   pari_sp av = avma;
      93                 :       3514 :   GEN n = nonzerotrace_F2xq(T);
      94         [ +  - ]:       3514 :   if (typ(a)==t_VECSMALL)
      95                 :            :   {
      96                 :       3514 :     *pt_a = gerepileuptoleaf(av, F2x_add(n, a));
      97                 :       3514 :     *pt_a6 = vecsmall_copy(a6);
      98                 :            :   } else
      99                 :            :   {
     100                 :          0 :     GEN a6t = F2x_add(a6, F2xq_mul(n, F2xq_sqr(gel(a,1), T), T));
     101                 :          0 :     *pt_a6 = gerepileuptoleaf(av, a6t);
     102                 :          0 :     *pt_a = vecsmall_copy(a);
     103                 :            :   }
     104                 :       3514 : }
     105                 :            : 
     106                 :            : static GEN
     107                 :     229528 : F2xqE_dbl_slope(GEN P, GEN a, GEN T, GEN *slope)
     108                 :            : {
     109                 :            :   GEN x, y, Q;
     110         [ +  + ]:     229528 :   if (ell_is_inf(P)) return ellinf();
     111                 :     216371 :   x = gel(P,1); y = gel(P,2);
     112         [ +  + ]:     216371 :   if (typ(a)==t_VECSMALL)
     113                 :            :   {
     114                 :     207911 :     GEN a2 = a;
     115         [ +  + ]:     207911 :     if (!lgpol(gel(P,1))) return ellinf();
     116                 :     191517 :     *slope = F2x_add(x, F2xq_div(y, x, T));
     117                 :     191517 :     Q = cgetg(3,t_VEC);
     118                 :     191517 :     gel(Q, 1) = F2x_add(F2xq_sqr(*slope, T), F2x_add(*slope, a2));
     119                 :     191517 :     gel(Q, 2) = F2x_add(F2xq_mul(*slope, F2x_add(x, gel(Q, 1)), T), F2x_add(y, gel(Q, 1)));
     120                 :            :   }
     121                 :            :   else
     122                 :            :   {
     123                 :       8460 :     GEN a3 = gel(a,1), a4 = gel(a,2), a3i = gel(a,3);
     124                 :       8460 :     *slope = F2xq_mul(F2x_add(a4, F2xq_sqr(x, T)), a3i, T);
     125                 :       8460 :     Q = cgetg(3,t_VEC);
     126                 :       8460 :     gel(Q, 1) = F2xq_sqr(*slope, T);
     127                 :       8460 :     gel(Q, 2) = F2x_add(F2xq_mul(*slope, F2x_add(x, gel(Q, 1)), T), F2x_add(y, a3));
     128                 :            :   }
     129                 :     229528 :   return Q;
     130                 :            : }
     131                 :            : 
     132                 :            : GEN
     133                 :     228857 : F2xqE_dbl(GEN P, GEN a, GEN T)
     134                 :            : {
     135                 :     228857 :   pari_sp av = avma;
     136                 :            :   GEN slope;
     137                 :     228857 :   return gerepileupto(av, F2xqE_dbl_slope(P, a, T,&slope));
     138                 :            : }
     139                 :            : 
     140                 :            : static GEN
     141                 :      74657 : F2xqE_add_slope(GEN P, GEN Q, GEN a, GEN T, GEN *slope)
     142                 :            : {
     143                 :            :   GEN Px, Py, Qx, Qy, R;
     144         [ +  + ]:      74657 :   if (ell_is_inf(P)) return Q;
     145         [ +  + ]:      73411 :   if (ell_is_inf(Q)) return P;
     146                 :      73404 :   Px = gel(P,1); Py = gel(P,2);
     147                 :      73404 :   Qx = gel(Q,1); Qy = gel(Q,2);
     148         [ +  + ]:      73404 :   if (F2x_equal(Px, Qx))
     149                 :            :   {
     150         [ +  + ]:       4533 :     if (F2x_equal(Py, Qy))
     151                 :        189 :       return F2xqE_dbl_slope(P, a, T, slope);
     152                 :            :     else
     153                 :       4344 :       return ellinf();
     154                 :            :   }
     155                 :      68871 :   *slope = F2xq_div(F2x_add(Py, Qy), F2x_add(Px, Qx), T);
     156                 :      68871 :   R = cgetg(3,t_VEC);
     157         [ +  + ]:      68871 :   if (typ(a)==t_VECSMALL)
     158                 :            :   {
     159                 :      66549 :     GEN a2 = a;
     160                 :      66549 :     gel(R, 1) = F2x_add(F2x_add(F2x_add(F2x_add(F2xq_sqr(*slope, T), *slope), Px), Qx), a2);
     161                 :      66549 :     gel(R, 2) = F2x_add(F2xq_mul(*slope, F2x_add(Px, gel(R, 1)), T), F2x_add(Py, gel(R, 1)));
     162                 :            :   }
     163                 :            :   else
     164                 :            :   {
     165                 :       2322 :     GEN a3 = gel(a,1);
     166                 :       2322 :     gel(R, 1) = F2x_add(F2x_add(F2xq_sqr(*slope, T), Px), Qx);
     167                 :       2322 :     gel(R, 2) = F2x_add(F2xq_mul(*slope, F2x_add(Px, gel(R, 1)), T), F2x_add(Py, a3));
     168                 :            :   }
     169                 :      74657 :   return R;
     170                 :            : }
     171                 :            : 
     172                 :            : GEN
     173                 :      74636 : F2xqE_add(GEN P, GEN Q, GEN a, GEN T)
     174                 :            : {
     175                 :      74636 :   pari_sp av = avma;
     176                 :            :   GEN slope;
     177                 :      74636 :   return gerepileupto(av, F2xqE_add_slope(P, Q, a, T, &slope));
     178                 :            : }
     179                 :            : 
     180                 :            : static GEN
     181                 :          0 : F2xqE_neg_i(GEN P, GEN a)
     182                 :            : {
     183                 :            :   GEN LHS;
     184         [ #  # ]:          0 :   if (ell_is_inf(P)) return P;
     185         [ #  # ]:          0 :   LHS = typ(a)==t_VECSMALL ? gel(P,1): gel(a,1);
     186                 :          0 :   return mkvec2(gel(P,1), F2x_add(LHS, gel(P,2)));
     187                 :            : }
     188                 :            : 
     189                 :            : GEN
     190                 :         84 : F2xqE_neg(GEN P, GEN a, GEN T)
     191                 :            : {
     192                 :            :   GEN LHS;
     193                 :            :   (void) T;
     194         [ -  + ]:         84 :   if (ell_is_inf(P)) return ellinf();
     195         [ +  + ]:         84 :   LHS = typ(a)==t_VECSMALL ? gel(P,1): gel(a,1);
     196                 :         84 :   return mkvec2(gcopy(gel(P,1)), F2x_add(LHS, gel(P,2)));
     197                 :            : }
     198                 :            : 
     199                 :            : GEN
     200                 :          0 : F2xqE_sub(GEN P, GEN Q, GEN a2, GEN T)
     201                 :            : {
     202                 :          0 :   pari_sp av = avma;
     203                 :            :   GEN slope;
     204                 :          0 :   return gerepileupto(av, F2xqE_add_slope(P, F2xqE_neg_i(Q, a2), a2, T, &slope));
     205                 :            : }
     206                 :            : 
     207                 :            : struct _F2xqE
     208                 :            : {
     209                 :            :   GEN a2, a6;
     210                 :            :   GEN T;
     211                 :            : };
     212                 :            : 
     213                 :            : static GEN
     214                 :     228857 : _F2xqE_dbl(void *E, GEN P)
     215                 :            : {
     216                 :     228857 :   struct _F2xqE *ell = (struct _F2xqE *) E;
     217                 :     228857 :   return F2xqE_dbl(P, ell->a2, ell->T);
     218                 :            : }
     219                 :            : 
     220                 :            : static GEN
     221                 :      74636 : _F2xqE_add(void *E, GEN P, GEN Q)
     222                 :            : {
     223                 :      74636 :   struct _F2xqE *ell=(struct _F2xqE *) E;
     224                 :      74636 :   return F2xqE_add(P, Q, ell->a2, ell->T);
     225                 :            : }
     226                 :            : 
     227                 :            : static GEN
     228                 :      42795 : _F2xqE_mul(void *E, GEN P, GEN n)
     229                 :            : {
     230                 :      42795 :   pari_sp av = avma;
     231                 :      42795 :   struct _F2xqE *e=(struct _F2xqE *) E;
     232                 :      42795 :   long s = signe(n);
     233 [ +  - ][ +  + ]:      42795 :   if (!s || ell_is_inf(P)) return ellinf();
     234         [ +  + ]:      42774 :   if (s<0) P = F2xqE_neg(P, e->a2, e->T);
     235 [ +  + ][ +  + ]:      42774 :   if (is_pm1(n)) return s>0? gcopy(P): P;
     236                 :      42795 :   return gerepileupto(av, gen_pow(P, n, e, &_F2xqE_dbl, &_F2xqE_add));
     237                 :            : }
     238                 :            : 
     239                 :            : GEN
     240                 :      14217 : F2xqE_mul(GEN P, GEN n, GEN a2, GEN T)
     241                 :            : {
     242                 :            :   struct _F2xqE E;
     243                 :      14217 :   E.a2 = a2; E.T = T;
     244                 :      14217 :   return _F2xqE_mul(&E, P, n);
     245                 :            : }
     246                 :            : 
     247                 :            : /* Finds a random non-singular point on E */
     248                 :            : GEN
     249                 :      31270 : random_F2xqE(GEN a, GEN a6, GEN T)
     250                 :            : {
     251                 :      31270 :   pari_sp ltop = avma;
     252                 :            :   GEN x, y, rhs, u;
     253                 :            :   do
     254                 :            :   {
     255                 :      63318 :     avma= ltop;
     256                 :      63318 :     x   = random_F2x(F2x_degree(T),T[1]);
     257         [ +  + ]:      63318 :     if (typ(a) == t_VECSMALL)
     258                 :            :     {
     259                 :      62898 :       GEN a2 = a, x2;
     260         [ +  + ]:      62898 :       if (!lgpol(x))
     261                 :        672 :         { avma=ltop; retmkvec2(pol0_Flx(T[1]), F2xq_sqrt(a6,T)); }
     262                 :      62226 :       u = x; x2  = F2xq_sqr(x, T);
     263                 :      62226 :       rhs = F2x_add(F2xq_mul(x2,F2x_add(x,a2),T),a6);
     264                 :      62226 :       rhs = F2xq_div(rhs,x2,T);
     265                 :            :     }
     266                 :            :     else
     267                 :            :     {
     268                 :        420 :       GEN a3 = gel(a,1), a4 = gel(a,2), a3i = gel(a,3), u2i;
     269                 :        420 :       u = a3; u2i = F2xq_sqr(a3i,T);
     270                 :        420 :       rhs = F2x_add(F2xq_mul(x,F2x_add(F2xq_sqr(x,T),a4),T),a6);
     271                 :        420 :       rhs = F2xq_mul(rhs,u2i,T);
     272                 :            :     }
     273         [ +  + ]:      62646 :   } while (F2xq_trace(rhs,T));
     274                 :      30598 :   y = F2xq_mul(F2xq_Artin_Schreier(rhs, T), u, T);
     275                 :      31270 :   return gerepilecopy(ltop, mkvec2(x, y));
     276                 :            : }
     277                 :            : 
     278                 :            : static GEN
     279                 :      13637 : _F2xqE_rand(void *E)
     280                 :            : {
     281                 :      13637 :   struct _F2xqE *ell=(struct _F2xqE *) E;
     282                 :      13637 :   return random_F2xqE(ell->a2, ell->a6, ell->T);
     283                 :            : }
     284                 :            : 
     285                 :            : static const struct bb_group F2xqE_group={_F2xqE_add,_F2xqE_mul,_F2xqE_rand,hash_GEN,zvV_equal,ell_is_inf, NULL};
     286                 :            : 
     287                 :            : const struct bb_group *
     288                 :          0 : get_F2xqE_group(void ** pt_E, GEN a2, GEN a6, GEN T)
     289                 :            : {
     290                 :          0 :   struct _F2xqE *e = (struct _F2xqE *) stack_malloc(sizeof(struct _F2xqE));
     291                 :          0 :   e->a2 = a2; e->a6 = a6; e->T = T;
     292                 :          0 :   *pt_E = (void *) e;
     293                 :          0 :   return &F2xqE_group;
     294                 :            : }
     295                 :            : 
     296                 :            : GEN
     297                 :        280 : F2xqE_order(GEN z, GEN o, GEN a2, GEN T)
     298                 :            : {
     299                 :        280 :   pari_sp av = avma;
     300                 :            :   struct _F2xqE e;
     301                 :        280 :   e.a2=a2; e.T=T;
     302                 :        280 :   return gerepileuptoint(av, gen_order(z, o, (void*)&e, &F2xqE_group));
     303                 :            : }
     304                 :            : 
     305                 :            : GEN
     306                 :         42 : F2xqE_log(GEN a, GEN b, GEN o, GEN a2, GEN T)
     307                 :            : {
     308                 :         42 :   pari_sp av = avma;
     309                 :            :   struct _F2xqE e;
     310                 :         42 :   e.a2=a2; e.T=T;
     311                 :         42 :   return gerepileuptoint(av, gen_PH_log(a, b, o, (void*)&e, &F2xqE_group));
     312                 :            : }
     313                 :            : 
     314                 :            : /***********************************************************************/
     315                 :            : /**                                                                   **/
     316                 :            : /**                            Pairings                               **/
     317                 :            : /**                                                                   **/
     318                 :            : /***********************************************************************/
     319                 :            : 
     320                 :            : /* Derived from APIP from and by Jerome Milan, 2012 */
     321                 :            : 
     322                 :            : static GEN
     323                 :       1425 : F2xqE_vert(GEN P, GEN Q, GEN T)
     324                 :            : {
     325         [ +  + ]:       1425 :   if (ell_is_inf(P))
     326                 :        461 :     return pol1_F2x(T[1]);
     327                 :       1425 :   return F2x_add(gel(Q, 1), gel(P, 1));
     328                 :            : }
     329                 :            : 
     330                 :            : /* Computes the equation of the line tangent to R and returns its
     331                 :            :    evaluation at the point Q. Also doubles the point R.
     332                 :            :  */
     333                 :            : 
     334                 :            : static GEN
     335                 :        482 : F2xqE_tangent_update(GEN R, GEN Q, GEN a2, GEN T, GEN *pt_R)
     336                 :            : {
     337         [ -  + ]:        482 :   if (ell_is_inf(R))
     338                 :            :   {
     339                 :          0 :     *pt_R = ellinf();
     340                 :          0 :     return pol1_F2x(T[1]);
     341                 :            :   }
     342         [ -  + ]:        482 :   else if (!lgpol(gel(R,1)))
     343                 :            :   {
     344                 :          0 :     *pt_R = ellinf();
     345                 :          0 :     return F2xqE_vert(R, Q, T);
     346                 :            :   } else {
     347                 :        482 :     GEN slope = NULL, tmp1, tmp2;
     348                 :        482 :     *pt_R = F2xqE_dbl_slope(R, a2, T, &slope);
     349                 :        482 :     tmp1 = F2x_add(gel(Q, 1), gel(R, 1));
     350                 :        482 :     tmp2 = F2x_add(F2xq_mul(tmp1, slope, T), gel(R,2));
     351                 :        482 :     return F2x_add(gel(Q, 2), tmp2);
     352                 :            :   }
     353                 :            : }
     354                 :            : 
     355                 :            : /* Computes the equation of the line through R and P, and returns its
     356                 :            :    evaluation at the point Q. Also adds P to the point R.
     357                 :            :  */
     358                 :            : 
     359                 :            : static GEN
     360                 :        482 : F2xqE_chord_update(GEN R, GEN P, GEN Q, GEN a2, GEN T, GEN *pt_R)
     361                 :            : {
     362         [ -  + ]:        482 :   if (ell_is_inf(R))
     363                 :            :   {
     364                 :          0 :     *pt_R = gcopy(P);
     365                 :          0 :     return F2xqE_vert(P, Q, T);
     366                 :            :   }
     367         [ -  + ]:        482 :   else if (ell_is_inf(P))
     368                 :            :   {
     369                 :          0 :     *pt_R = gcopy(R);
     370                 :          0 :     return F2xqE_vert(R, Q, T);
     371                 :            :   }
     372         [ +  + ]:        482 :   else if (F2x_equal(gel(P, 1), gel(R, 1)))
     373                 :            :   {
     374         [ -  + ]:        461 :     if (F2x_equal(gel(P, 2), gel(R, 2)))
     375                 :          0 :       return F2xqE_tangent_update(R, Q, a2, T, pt_R);
     376                 :            :     else
     377                 :            :     {
     378                 :        461 :       *pt_R = ellinf();
     379                 :        461 :       return F2xqE_vert(R, Q, T);
     380                 :            :     }
     381                 :            :   } else {
     382                 :         21 :     GEN slope = NULL, tmp1, tmp2;
     383                 :         21 :     *pt_R = F2xqE_add_slope(P, R, a2, T, &slope);
     384                 :         21 :     tmp1  = F2xq_mul(F2x_add(gel(Q, 1), gel(R, 1)), slope, T);
     385                 :         21 :     tmp2  = F2x_add(tmp1, gel(R, 2));
     386                 :        482 :     return F2x_add(gel(Q, 2), tmp2);
     387                 :            :   }
     388                 :            : }
     389                 :            : 
     390                 :            : /* Returns the Miller function f_{m, Q} evaluated at the point P using
     391                 :            :    the standard Miller algorithm.
     392                 :            :  */
     393                 :            : 
     394                 :            : struct _F2xqE_miller
     395                 :            : {
     396                 :            :   GEN T, a2, P;
     397                 :            : };
     398                 :            : 
     399                 :            : static GEN
     400                 :        482 : F2xqE_Miller_dbl(void* E, GEN d)
     401                 :            : {
     402                 :        482 :   struct _F2xqE_miller *m = (struct _F2xqE_miller *)E;
     403                 :        482 :   GEN T = m->T, a2 = m->a2, P = m->P;
     404                 :            :   GEN v, line;
     405                 :        482 :   GEN num = F2xq_sqr(gel(d,1), T);
     406                 :        482 :   GEN denom = F2xq_sqr(gel(d,2), T);
     407                 :        482 :   GEN point = gel(d,3);
     408                 :        482 :   line = F2xqE_tangent_update(point, P, a2, T, &point);
     409                 :        482 :   num  = F2xq_mul(num, line, T);
     410                 :        482 :   v = F2xqE_vert(point, P, T);
     411                 :        482 :   denom = F2xq_mul(denom, v, T);
     412                 :        482 :   return mkvec3(num, denom, point);
     413                 :            : }
     414                 :            : 
     415                 :            : static GEN
     416                 :        482 : F2xqE_Miller_add(void* E, GEN va, GEN vb)
     417                 :            : {
     418                 :        482 :   struct _F2xqE_miller *m = (struct _F2xqE_miller *)E;
     419                 :        482 :   GEN T = m->T, a2 = m->a2, P = m->P;
     420                 :            :   GEN v, line, point;
     421                 :        482 :   GEN na = gel(va,1), da = gel(va,2), pa = gel(va,3);
     422                 :        482 :   GEN nb = gel(vb,1), db = gel(vb,2), pb = gel(vb,3);
     423                 :        482 :   GEN num   = F2xq_mul(na, nb, T);
     424                 :        482 :   GEN denom = F2xq_mul(da, db, T);
     425                 :        482 :   line = F2xqE_chord_update(pa, pb, P, a2, T, &point);
     426                 :        482 :   num  = F2xq_mul(num, line, T);
     427                 :        482 :   v = F2xqE_vert(point, P, T);
     428                 :        482 :   denom = F2xq_mul(denom, v, T);
     429                 :        482 :   return mkvec3(num, denom, point);
     430                 :            : }
     431                 :            : 
     432                 :            : static GEN
     433                 :        482 : F2xqE_Miller(GEN Q, GEN P, GEN m, GEN a2, GEN T)
     434                 :            : {
     435                 :        482 :   pari_sp ltop = avma;
     436                 :            :   struct _F2xqE_miller d;
     437                 :            :   GEN v, num, denom, g1;
     438                 :            : 
     439                 :        482 :   d.a2 = a2; d.T = T; d.P = P;
     440                 :        482 :   g1 = pol1_F2x(T[1]);
     441                 :        482 :   v = gen_pow(mkvec3(g1,g1,Q), m, (void*)&d, F2xqE_Miller_dbl, F2xqE_Miller_add);
     442                 :        482 :   num = gel(v,1); denom = gel(v,2);
     443 [ +  + ][ -  + ]:        482 :   if (!lgpol(num) || !lgpol(denom)) { avma = ltop; return NULL; }
     444                 :        482 :   return gerepileupto(ltop, F2xq_div(num, denom, T));
     445                 :            : }
     446                 :            : 
     447                 :            : GEN
     448                 :        347 : F2xqE_weilpairing(GEN P, GEN Q, GEN m, GEN a2, GEN T)
     449                 :            : {
     450                 :        347 :   pari_sp ltop = avma;
     451                 :            :   GEN num, denom, result;
     452 [ +  + ][ +  + ]:        347 :   if (ell_is_inf(P) || ell_is_inf(Q) || F2x_equal(P,Q))
                 [ -  + ]
     453                 :         75 :     return pol1_F2x(T[1]);
     454                 :        272 :   num    = F2xqE_Miller(P, Q, m, a2, T);
     455         [ +  + ]:        272 :   if (!num) return pol1_F2x(T[1]);
     456                 :        203 :   denom  = F2xqE_Miller(Q, P, m, a2, T);
     457         [ -  + ]:        203 :   if (!denom) { avma=ltop; return pol1_F2x(T[1]); }
     458                 :        203 :   result = F2xq_div(num, denom, T);
     459                 :        347 :   return gerepileupto(ltop, result);
     460                 :            : }
     461                 :            : 
     462                 :            : GEN
     463                 :          7 : F2xqE_tatepairing(GEN P, GEN Q, GEN m, GEN a2, GEN T)
     464                 :            : {
     465                 :            :   GEN num;
     466 [ +  - ][ -  + ]:          7 :   if (ell_is_inf(P) || ell_is_inf(Q))
     467                 :          0 :     return pol1_F2x(T[1]);
     468                 :          7 :   num = F2xqE_Miller(P, Q, m, a2, T);
     469         [ -  + ]:          7 :   return num? num: pol1_F2x(T[1]);
     470                 :            : }
     471                 :            : 
     472                 :            : /***********************************************************************/
     473                 :            : /**                                                                   **/
     474                 :            : /**                          Point counting                           **/
     475                 :            : /**                                                                   **/
     476                 :            : /***********************************************************************/
     477                 :            : 
     478                 :            : static GEN
     479                 :      38272 : Z2x_rshift(GEN y, long x)
     480                 :            : {
     481                 :            :   GEN z;
     482                 :            :   long i, l;
     483         [ -  + ]:      38272 :   if (!x) return pol0_Flx(y[1]);
     484                 :      38272 :   z = cgetg_copy(y, &l); z[1] = y[1];
     485         [ +  + ]:    3776334 :   for(i=2; i<l; i++) z[i] = y[i]>>x;
     486                 :      38299 :   return Flx_renormalize(z, l);
     487                 :            : }
     488                 :            : 
     489                 :            : /* Solve the linear equation approximation in the Newton algorithm */
     490                 :            : 
     491                 :            : static GEN
     492                 :     106415 : gen_Z2x_Dixon(GEN F, GEN V, long N, void *E, GEN lin(void *E, GEN F, GEN d, long N), GEN invl(void *E, GEN d))
     493                 :            : {
     494                 :     106415 :   pari_sp av = avma;
     495                 :            :   long N2, M;
     496                 :            :   GEN VN2, V2, VM, bil;
     497                 :     106415 :   ulong q = 1UL<<N;
     498         [ +  + ]:     106415 :   if (N == 1) return invl(E, V);
     499                 :      38291 :   V = Flx_red(V, q);
     500                 :      38288 :   N2 = (N + 1)>>1; M = N - N2;
     501                 :      38288 :   F = FlxT_red(F, q);
     502                 :      38288 :   VN2 = gen_Z2x_Dixon(F, V, N2, E, lin, invl);
     503                 :      38294 :   bil = lin(E, F, VN2, N);
     504                 :      38270 :   V2 = Z2x_rshift(Flx_sub(V, bil, q), N2);
     505                 :      38276 :   VM = gen_Z2x_Dixon(F, V2, M, E, lin, invl);
     506                 :     106420 :   return gerepileupto(av, Flx_add(VN2, Flx_Fl_mul(VM, 1UL<<N2, q), q));
     507                 :            : }
     508                 :            : 
     509                 :            : /* Solve F(X) = V mod 2^N
     510                 :            :    F(Xn) = V [mod 2^n]
     511                 :            :    Vm = (V-F(Xn))/(2^n)
     512                 :            :    F(Xm) = Vm
     513                 :            :    X = Xn + 2^n*Xm
     514                 :            : */
     515                 :            : 
     516                 :            : static GEN
     517                 :      29859 : gen_Z2X_Dixon(GEN F, GEN V, long N, void *E,
     518                 :            :                      GEN lin(void *E, GEN F, GEN d, long N),
     519                 :            :                      GEN lins(void *E, GEN F, GEN d, long N),
     520                 :            :                      GEN invls(void *E, GEN d))
     521                 :            : {
     522                 :      29859 :   pari_sp av = avma;
     523                 :            :   long n, m;
     524                 :            :   GEN Xn, Xm, FXn, Vm;
     525         [ +  + ]:      29859 :   if (N<BITS_IN_LONG)
     526                 :            :   {
     527                 :      29839 :     ulong q = 1UL<<N;
     528                 :      29839 :     return Flx_to_ZX(gen_Z2x_Dixon(ZXT_to_FlxT(F,q), ZX_to_Flx(V,q),N,E,lins,invls));
     529                 :            :   }
     530                 :         20 :   V = ZX_remi2n(V, N);
     531                 :         20 :   n = (N + 1)>>1; m = N - n;
     532                 :         20 :   F = ZXT_remi2n(F, N);
     533                 :         20 :   Xn = gen_Z2X_Dixon(F, V, n, E, lin, lins, invls);
     534                 :         20 :   FXn = lin(E, F, Xn, N);
     535                 :         20 :   Vm = ZX_shifti(ZX_sub(V, FXn), -n);
     536                 :         20 :   Xm = gen_Z2X_Dixon(F, Vm, m, E, lin, lins, invls);
     537                 :      29859 :   return gerepileupto(av, ZX_remi2n(ZX_add(Xn, ZX_shifti(Xm, n)), N));
     538                 :            : }
     539                 :            : 
     540                 :            : /* H -> H mod 2*/
     541                 :            : 
     542                 :      33766 : static GEN _can_invls(void *E, GEN V) {(void) E; return V; }
     543                 :            : 
     544                 :            : /* H -> H-(f0*H0-f1*H1) */
     545                 :            : 
     546                 :         10 : static GEN _can_lin(void *E, GEN F, GEN V, long N)
     547                 :            : {
     548                 :         10 :   pari_sp av=avma;
     549                 :            :   GEN d0, d1, z;
     550                 :            :   (void) E;
     551                 :         10 :   RgX_even_odd(V, &d0, &d1);
     552                 :         10 :   z =  ZX_sub(V, ZX_sub(ZX_mul(gel(F,1), d0), ZX_mul(gel(F,2), d1)));
     553                 :         10 :   return gerepileupto(av, ZX_remi2n(z, N));
     554                 :            : }
     555                 :            : 
     556                 :      18987 : static GEN _can_lins(void *E, GEN F, GEN V, long N)
     557                 :            : {
     558                 :      18987 :   GEN D=Flx_splitting(V, 2), z;
     559                 :      18993 :   ulong q = 1UL<<N;
     560                 :            :   (void) E;
     561                 :      18993 :   z = Flx_sub(Flx_mul(gel(F,1), gel(D,1), q), Flx_mul(gel(F,2), gel(D,2), q), q);
     562                 :      18986 :   return Flx_sub(V, z, q);
     563                 :            : }
     564                 :            : 
     565                 :            : /* P -> P-(P0^2-X*P1^2) */
     566                 :            : 
     567                 :            : static GEN
     568                 :      14773 : _can_iter(void *E, GEN f2, GEN q)
     569                 :            : {
     570                 :            :   GEN f0, f1, z;
     571                 :            :   (void) E;
     572                 :      14773 :   RgX_even_odd(f2, &f0, &f1);
     573                 :      14773 :   z = ZX_add(ZX_sub(f2, FpX_sqr(f0, q)), RgX_shift_shallow(FpX_sqr(f1, q), 1));
     574                 :      14773 :   return mkvec3(z,f0,f1);
     575                 :            : }
     576                 :            : 
     577                 :            : /* H -> H-(2*P0*H0-2*X*P1*H1) */
     578                 :            : 
     579                 :            : static GEN
     580                 :      14773 : _can_invd(void *E, GEN V, GEN v, GEN q, long M)
     581                 :            : {
     582                 :            :   GEN F;
     583                 :            :   (void)E; (void)q;
     584                 :      14773 :   F = mkvec2(ZX_shifti(gel(v,2),1), ZX_shifti(RgX_shift_shallow(gel(v,3),1),1));
     585                 :      14773 :   return gen_Z2X_Dixon(F, V, M, NULL, _can_lin, _can_lins, _can_invls);
     586                 :            : }
     587                 :            : 
     588                 :            : /* Lift P to Q such that Q(x^2)=Q(x)*Q(-x) mod 2^n
     589                 :            :    if Q = Q0(X^2)+X*Q1(X^2), solve Q(x^2) = Q0^2-X*Q1^2
     590                 :            : */
     591                 :            : static GEN
     592                 :       6913 : F2x_canonlift(GEN P, long n)
     593                 :       6913 : { return gen_ZpX_Newton(F2x_to_ZX(P),gen_2, n, NULL, _can_iter, _can_invd); }
     594                 :            : 
     595                 :            : static GEN
     596                 :      15054 : Z2XQ_frob(GEN x, GEN T, GEN q)
     597                 :            : {
     598                 :      15054 :   return FpX_rem(RgX_inflate(x, 2), T, q);
     599                 :            : }
     600                 :            : 
     601                 :            : static GEN
     602                 :      19296 : Z2xq_frob(GEN x, GEN T, ulong q)
     603                 :            : {
     604                 :      19296 :   return Flx_rem(Flx_inflate(x, 2), T, q);
     605                 :            : }
     606                 :            : 
     607                 :            : struct _frob_lift
     608                 :            : {
     609                 :            :   GEN T, sqx;
     610                 :            : };
     611                 :            : 
     612                 :            : /* H -> S^-1(H) mod 2 */
     613                 :            : 
     614                 :      34350 : static GEN _frob_invls(void *E, GEN V)
     615                 :            : {
     616                 :      34350 :   struct _frob_lift *F = (struct _frob_lift*) E;
     617                 :      34350 :   GEN sqx = F->sqx;
     618                 :      34350 :   return F2x_to_Flx(F2xq_sqrt_fast(Flx_to_F2x(V), gel(sqx,1), gel(sqx,2)));
     619                 :            : }
     620                 :            : 
     621                 :            : /* H -> f1*S(H) + f2*H */
     622                 :            : 
     623                 :         10 : static GEN _frob_lin(void *E, GEN F, GEN x2, long N)
     624                 :            : {
     625                 :         10 :   GEN T = gel(F,3);
     626                 :         10 :   GEN q = int2n(N);
     627                 :         10 :   GEN y2  = Z2XQ_frob(x2, T, q);
     628                 :         10 :   GEN lin = ZX_add(ZX_mul(gel(F,1), y2), ZX_mul(gel(F,2), x2));
     629                 :            :   (void) E;
     630                 :         10 :   return FpX_rem(ZX_remi2n(lin, N), T, q);
     631                 :            : }
     632                 :            : 
     633                 :      19297 : static GEN _frob_lins(void *E, GEN F, GEN x2, long N)
     634                 :            : {
     635                 :      19297 :   GEN T = gel(F,3);
     636                 :      19297 :   ulong q = 1UL<<N;
     637                 :      19297 :   GEN y2  = Z2xq_frob(x2, T, q);
     638                 :      19289 :   GEN lin = Flx_add(Flx_mul(gel(F,1), y2,q), Flx_mul(gel(F,2), x2,q),q);
     639                 :            :   (void) E;
     640                 :      19299 :   return Flx_rem(lin, T, q);
     641                 :            : }
     642                 :            : 
     643                 :            : /* X -> P(X,S(X)) */
     644                 :            : 
     645                 :            : static GEN
     646                 :      15046 : _lift_iter(void *E, GEN x2, GEN q)
     647                 :            : {
     648                 :      15046 :   struct _frob_lift *F = (struct _frob_lift*) E;
     649                 :      15046 :   long N = expi(q);
     650                 :      15046 :   GEN TN = ZXT_remi2n(F->T, N);
     651                 :      15044 :   GEN y2 = Z2XQ_frob(x2, TN, q);
     652                 :      15044 :   GEN x2y2 = FpX_rem(ZX_remi2n(ZX_mul(x2, y2), N), TN, q);
     653                 :      15046 :   GEN s = ZX_add(ZX_add(x2, ZX_shifti(y2, 1)), ZX_shifti(x2y2, 3));
     654                 :      15046 :   GEN V = ZX_add(ZX_add(ZX_sqr(s), y2), ZX_shifti(x2y2, 2));
     655                 :      15046 :   return mkvec4(FpX_rem(ZX_remi2n(V, N), TN, q),x2,y2,s);
     656                 :            : }
     657                 :            : 
     658                 :            : /* H -> Dx*H+Dy*S(H) */
     659                 :            : 
     660                 :            : static GEN
     661                 :      15046 : _lift_invd(void *E, GEN V, GEN v, GEN qM, long M)
     662                 :            : {
     663                 :      15046 :   struct _frob_lift *F = (struct _frob_lift*) E;
     664                 :      15046 :   GEN TM = ZXT_remi2n(F->T, M);
     665                 :      15045 :   GEN x2 = gel(v,2), y2 = gel(v,3), s = gel(v,4), r;
     666                 :      15045 :   GEN Dx = ZX_add(ZX_mul(ZX_Z_add(ZX_shifti(y2, 4), gen_2), s),
     667                 :            :                          ZX_shifti(y2, 2));
     668                 :      15045 :   GEN Dy = ZX_add(ZX_Z_add(ZX_mul(ZX_Z_add(ZX_shifti(x2, 4), utoi(4)), s),
     669                 :            :                            gen_1), ZX_shifti(x2, 2));
     670                 :      15046 :   Dx = FpX_rem(ZX_remi2n(Dx, M), TM, qM);
     671                 :      15046 :   Dy = FpX_rem(ZX_remi2n(Dy, M), TM, qM);
     672                 :      15046 :   r = mkvec3(Dy, Dx, TM);
     673                 :      15045 :   return gen_Z2X_Dixon(r, V, M, E, _frob_lin, _frob_lins, _frob_invls);
     674                 :            : }
     675                 :            : 
     676                 :            : /*
     677                 :            :   Let P(X,Y)=(X+2*Y+8*X*Y)^2+Y+4*X*Y
     678                 :            :   Solve   P(x,S(x))=0 [mod 2^n,T]
     679                 :            :   assuming  x = x0    [mod 2,T]
     680                 :            : 
     681                 :            :   we set s = X+2*Y+8*X*Y, P = s^2+Y+4*X*Y
     682                 :            :   Dx = dP/dx = (16*s+4)*x+(4*s+1)
     683                 :            :   Dy = dP/dy = (16*y+2)*s+4*y
     684                 :            : */
     685                 :            : 
     686                 :            : static GEN
     687                 :       7151 : solve_AGM_eqn(GEN x0, long n, GEN T, GEN sqx)
     688                 :            : {
     689                 :            :   struct _frob_lift F;
     690                 :       7151 :   F.T=T; F.sqx=sqx;
     691                 :       7151 :   return gen_ZpX_Newton(x0, gen_2, n, &F, _lift_iter, _lift_invd);
     692                 :            : }
     693                 :            : 
     694                 :            : static GEN
     695                 :        238 : Z2XQ_invnorm_pcyc(GEN a, GEN T, long e)
     696                 :            : {
     697                 :        238 :   GEN q = int2n(e);
     698                 :        238 :   GEN z = ZpXQ_norm_pcyc(a, T, q, gen_2);
     699                 :        238 :   return Fp_inv(z, q);
     700                 :            : }
     701                 :            : 
     702                 :            : /* Assume a = 1 [4] */
     703                 :            : static GEN
     704                 :       6913 : Z2XQ_invnorm(GEN a, GEN T, long e)
     705                 :            : {
     706                 :            :   pari_timer ti;
     707                 :       6913 :   GEN pe = int2n(e), s;
     708         [ +  + ]:       6913 :   if (degpol(a)==0)
     709                 :         56 :     return Fp_inv(Fp_powu(gel(a,2), get_FpX_degree(T), pe), pe);
     710         [ -  + ]:       6857 :   if (DEBUGLEVEL>=3) timer_start(&ti);
     711                 :       6857 :   s = ZpXQ_log(a, T, gen_2, e);
     712         [ -  + ]:       6857 :   if (DEBUGLEVEL>=3) timer_printf(&ti,"Z2XQ_log");
     713                 :       6857 :   s = Fp_neg(FpXQ_trace(s, T, pe), pe);
     714         [ -  + ]:       6857 :   if (DEBUGLEVEL>=3) timer_printf(&ti,"FpXQ_trace");
     715                 :       6857 :   s = modii(gel(Qp_exp(cvtop(s, gen_2, e-2)),4),pe);
     716         [ -  + ]:       6857 :   if (DEBUGLEVEL>=3) timer_printf(&ti,"Qp_exp");
     717                 :       6913 :   return s;
     718                 :            : }
     719                 :            : 
     720                 :            : /* Assume a2==0, so 4|E(F_p): if t^4 = a6 then (t,t^2) is of order 4
     721                 :            :    8|E(F_p) <=> trace(a6)==0
     722                 :            :  */
     723                 :            : 
     724                 :            : static GEN
     725                 :       7332 : F2xq_elltrace_Harley(GEN a6, GEN T2)
     726                 :            : {
     727                 :       7332 :   pari_sp ltop = avma;
     728                 :            :   pari_timer ti;
     729                 :            :   GEN T, sqx;
     730                 :            :   GEN x, x2, t;
     731                 :       7332 :   long n = F2x_degree(T2), N = ((n + 1)>>1) + 2;
     732                 :            :   long ispcyc;
     733         [ +  + ]:       7332 :   if (n==1) return gen_m1;
     734 [ +  + ][ +  + ]:       7304 :   if (n==2) return F2x_degree(a6) ? gen_1 : stoi(-3);
     735 [ +  + ][ +  + ]:       7465 :   if (n==3) return F2x_degree(a6) ? (F2xq_trace(a6,T2) ?  stoi(-3): gen_1)
     736         [ +  + ]:        203 :                                   : stoi(5);
     737                 :       7150 :   timer_start(&ti);
     738                 :       7150 :   sqx = mkvec2(F2xq_sqrt(polx_F2x(T2[1]),T2), T2);
     739         [ -  + ]:       7151 :   if (DEBUGLEVEL>1) timer_printf(&ti,"Sqrtx");
     740                 :       7151 :   ispcyc = zx_is_pcyc(F2x_to_Flx(T2));
     741         [ +  + ]:       7151 :   T = ispcyc? F2x_to_ZX(T2): F2x_canonlift(T2, N-2);
     742         [ -  + ]:       7151 :   if (DEBUGLEVEL>1) timer_printf(&ti,"Teich");
     743                 :       7151 :   T = FpX_get_red(T, int2n(N));
     744         [ -  + ]:       7151 :   if (DEBUGLEVEL>1) timer_printf(&ti,"Barrett");
     745                 :       7151 :   x = solve_AGM_eqn(F2x_to_ZX(a6), N-2, T, sqx);
     746         [ -  + ]:       7151 :   if (DEBUGLEVEL>1) timer_printf(&ti,"Lift");
     747                 :       7151 :   x2 = ZX_Z_add_shallow(ZX_shifti(x,2), gen_1);
     748         [ +  + ]:       7151 :   t = (ispcyc? Z2XQ_invnorm_pcyc: Z2XQ_invnorm)(x2, T, N);
     749         [ -  + ]:       7151 :   if (DEBUGLEVEL>1) timer_printf(&ti,"Norm");
     750         [ +  + ]:       7151 :   if (cmpii(sqri(t), int2n(n + 2)) > 0)
     751                 :       3356 :     t = subii(t, int2n(N));
     752                 :       7333 :   return gerepileuptoint(ltop, t);
     753                 :            : }
     754                 :            : 
     755                 :            : GEN
     756                 :       7389 : F2xq_ellcard(GEN a, GEN a6, GEN T)
     757                 :            : {
     758                 :       7389 :   pari_sp av = avma;
     759                 :       7389 :   long n = F2x_degree(T);
     760                 :       7388 :   GEN q = int2u(n), c;
     761         [ +  + ]:       7388 :   if (typ(a)==t_VECSMALL)
     762                 :            :   {
     763                 :       7332 :     GEN t = F2xq_elltrace_Harley(a6, T);
     764         [ +  + ]:       7333 :     c = addii(q, F2xq_trace(a,T) ? addui(1,t): subui(1,t));
     765         [ +  + ]:         56 :   } else if (n==1)
     766                 :            :   {
     767                 :         21 :     long a4i = lgpol(gel(a,2)), a6i = lgpol(a6);
     768 [ +  - ][ +  + ]:         21 :     return utoi(a4i? (a6i? 1: 5): 3);
     769                 :            :   }
     770         [ +  + ]:         35 :   else if (n==2)
     771                 :            :   {
     772                 :          7 :     GEN a3 = gel(a,1), a4 = gel(a,2), x = polx_F2x(T[1]), x1 = pol1_F2x(T[1]);
     773                 :          7 :     GEN a613 = F2xq_mul(F2x_add(x1, a6),a3,T), a43= F2xq_mul(a4,a3,T);
     774                 :          7 :     long f0= F2xq_trace(F2xq_mul(a6,a3,T),T);
     775                 :          7 :     long f1= F2xq_trace(F2x_add(a43,a613),T);
     776                 :          7 :     long f2= F2xq_trace(F2x_add(F2xq_mul(a43,x,T),a613),T);
     777                 :          7 :     long f3= F2xq_trace(F2x_add(F2xq_mul(a43,F2x_add(x,x1),T),a613),T);
     778                 :          7 :     c = utoi(9-2*(f0+f1+f2+f3));
     779                 :            :   }
     780                 :            :   else
     781                 :            :   {
     782                 :            :     struct _F2xqE e;
     783                 :         28 :     long m = (n+1)>>1;
     784                 :         28 :     GEN q1 = addis(q, 1);
     785                 :         28 :     GEN v = n==4 ? mkvec4s(13,17,21,25)
     786 [ +  + ][ +  + ]:         35 :                  : odd(n) ? mkvec3(subii(q1,int2u(m)),q1,addii(q1,int2u(m))):
     787                 :          7 :                             mkvec5(subii(q1,int2u(m+1)),subii(q1,int2u(m)),q1,
     788                 :          7 :                                    addii(q1,int2u(m)),addii(q1,int2u(m+1)));
     789                 :         28 :     e.a2=a; e.a6=a6; e.T=T;
     790                 :         28 :     c = gen_select_order(v,(void*)&e, &F2xqE_group);
     791 [ +  + ][ +  - ]:         28 :     if (n==4 && equaliu(c, 21)) /* Ambiguous case */
     792                 :            :     {
     793                 :          7 :       GEN d = F2xq_powu(polx_F2x(T[1]),3,T), a3 = gel(a,1);
     794                 :          7 :       e.a6 = F2x_add(a6,F2xq_mul(d,F2xq_sqr(a3,T),T)); /* twist */
     795                 :         28 :       c = subui(34, gen_select_order(mkvec2s(13,25),(void*)&e, &F2xqE_group));
     796                 :            :     }
     797                 :            :   }
     798                 :       7389 :   return gerepileuptoint(av, c);
     799                 :            : }
     800                 :            : 
     801                 :            : /***********************************************************************/
     802                 :            : /**                                                                   **/
     803                 :            : /**                          Group structure                          **/
     804                 :            : /**                                                                   **/
     805                 :            : /***********************************************************************/
     806                 :            : 
     807                 :            : static GEN
     808                 :        340 : _F2xqE_pairorder(void *E, GEN P, GEN Q, GEN m, GEN F)
     809                 :            : {
     810                 :        340 :   struct _F2xqE *e = (struct _F2xqE *) E;
     811                 :        340 :   return  F2xq_order(F2xqE_weilpairing(P,Q,m,e->a2,e->T), F, e->T);
     812                 :            : }
     813                 :            : 
     814                 :            : GEN
     815                 :       3654 : F2xq_ellgroup(GEN a2, GEN a6, GEN N, GEN T, GEN *pt_m)
     816                 :            : {
     817                 :            :   struct _F2xqE e;
     818                 :       3654 :   GEN q = int2u(F2x_degree(T));
     819                 :       3654 :   e.a2=a2; e.a6=a6; e.T=T;
     820                 :       3654 :   return gen_ellgroup(N, subis(q,1), pt_m, (void*)&e, &F2xqE_group,
     821                 :            :                                                       _F2xqE_pairorder);
     822                 :            : }
     823                 :            : 
     824                 :            : GEN
     825                 :       3584 : F2xq_ellgens(GEN a2, GEN a6, GEN ch, GEN D, GEN m, GEN T)
     826                 :            : {
     827                 :            :   GEN P;
     828                 :       3584 :   pari_sp av = avma;
     829                 :            :   struct _F2xqE e;
     830                 :       3584 :   e.a2=a2; e.a6=a6; e.T=T;
     831      [ +  +  + ]:       3584 :   switch(lg(D)-1)
     832                 :            :   {
     833                 :            :   case 0:
     834                 :          7 :     return cgetg(1,t_VEC);
     835                 :            :   case 1:
     836                 :       3479 :     P = gen_gener(gel(D,1), (void*)&e, &F2xqE_group);
     837                 :       3479 :     P = mkvec(F2xqE_changepoint(P, ch, T));
     838                 :       3479 :     break;
     839                 :            :   default:
     840                 :         98 :     P = gen_ellgens(gel(D,1), gel(D,2), m, (void*)&e, &F2xqE_group,
     841                 :            :                                                       _F2xqE_pairorder);
     842                 :         98 :     gel(P,1) = F2xqE_changepoint(gel(P,1), ch, T);
     843                 :         98 :     gel(P,2) = F2xqE_changepoint(gel(P,2), ch, T);
     844                 :         98 :     break;
     845                 :            :   }
     846                 :       3584 :   return gerepilecopy(av, P);
     847                 :            : }

Generated by: LCOV version 1.9