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 - F2xqE.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.10.0 lcov report (development 20924-e159ed0) Lines: 420 446 94.2 %
Date: 2017-08-21 06:23:16 Functions: 55 58 94.8 %
Legend: Lines: hit not hit

          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      194698 : RgE_to_F2xqE(GEN x, GEN T)
      36             : {
      37      194698 :   if (ell_is_inf(x)) return x;
      38      194215 :   retmkvec2(Rg_to_F2xq(gel(x,1),T),Rg_to_F2xq(gel(x,2),T));
      39             : }
      40             : 
      41             : GEN
      42      356055 : F2xqE_changepoint(GEN x, GEN ch, GEN T)
      43             : {
      44      356055 :   pari_sp av = avma;
      45             :   GEN p1,z,u,r,s,t,v,v2,v3;
      46      356055 :   if (ell_is_inf(x)) return x;
      47      187264 :   u = gel(ch,1); r = gel(ch,2);
      48      187264 :   s = gel(ch,3); t = gel(ch,4);
      49      187264 :   v = F2xq_inv(u, T); v2 = F2xq_sqr(v, T); v3 = F2xq_mul(v,v2, T);
      50      187264 :   p1 = F2x_add(gel(x,1),r);
      51      187264 :   z = cgetg(3,t_VEC);
      52      187264 :   gel(z,1) = F2xq_mul(v2, p1, T);
      53      187264 :   gel(z,2) = F2xq_mul(v3, F2x_add(gel(x,2), F2x_add(F2xq_mul(s, p1, T),t)), T);
      54      187264 :   return gerepileupto(av, z);
      55             : }
      56             : 
      57             : GEN
      58      194698 : F2xqE_changepointinv(GEN x, GEN ch, GEN T)
      59             : {
      60             :   GEN u, r, s, t, X, Y, u2, u3, u2X, z;
      61      194698 :   if (ell_is_inf(x)) return x;
      62      194215 :   X = gel(x,1); Y = gel(x,2);
      63      194215 :   u = gel(ch,1); r = gel(ch,2);
      64      194215 :   s = gel(ch,3); t = gel(ch,4);
      65      194215 :   u2 = F2xq_sqr(u, T); u3 = F2xq_mul(u,u2, T);
      66      194215 :   u2X = F2xq_mul(u2,X, T);
      67      194215 :   z = cgetg(3, t_VEC);
      68      194215 :   gel(z,1) = F2x_add(u2X,r);
      69      194215 :   gel(z,2) = F2x_add(F2xq_mul(u3,Y, T), F2x_add(F2xq_mul(s,u2X, T), t));
      70      194215 :   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        2352 :   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     1075242 : F2xqE_dbl_slope(GEN P, GEN a, GEN T, GEN *slope)
     108             : {
     109             :   GEN x, y, Q;
     110     1075242 :   if (ell_is_inf(P)) return ellinf();
     111     1061788 :   x = gel(P,1); y = gel(P,2);
     112     1061788 :   if (typ(a)==t_VECSMALL)
     113             :   {
     114      207655 :     GEN a2 = a;
     115      207655 :     if (!lgpol(gel(P,1))) return ellinf();
     116      191261 :     *slope = F2x_add(x, F2xq_div(y, x, T));
     117      191261 :     Q = cgetg(3,t_VEC);
     118      191261 :     gel(Q, 1) = F2x_add(F2xq_sqr(*slope, T), F2x_add(*slope, a2));
     119      191261 :     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      854133 :     GEN a3 = gel(a,1), a4 = gel(a,2), a3i = gel(a,3);
     124      854133 :     *slope = F2xq_mul(F2x_add(a4, F2xq_sqr(x, T)), a3i, T);
     125      854133 :     Q = cgetg(3,t_VEC);
     126      854133 :     gel(Q, 1) = F2xq_sqr(*slope, T);
     127      854133 :     gel(Q, 2) = F2x_add(F2xq_mul(*slope, F2x_add(x, gel(Q, 1)), T), F2x_add(y, a3));
     128             :   }
     129     1045394 :   return Q;
     130             : }
     131             : 
     132             : GEN
     133     1055971 : F2xqE_dbl(GEN P, GEN a, GEN T)
     134             : {
     135     1055971 :   pari_sp av = avma;
     136             :   GEN slope;
     137     1055971 :   return gerepileupto(av, F2xqE_dbl_slope(P, a, T,&slope));
     138             : }
     139             : 
     140             : static GEN
     141      354242 : F2xqE_add_slope(GEN P, GEN Q, GEN a, GEN T, GEN *slope)
     142             : {
     143             :   GEN Px, Py, Qx, Qy, R;
     144      354242 :   if (ell_is_inf(P)) return Q;
     145      352751 :   if (ell_is_inf(Q)) return P;
     146      352744 :   Px = gel(P,1); Py = gel(P,2);
     147      352744 :   Qx = gel(Q,1); Qy = gel(Q,2);
     148      352744 :   if (F2x_equal(Px, Qx))
     149             :   {
     150      156548 :     if (F2x_equal(Py, Qy))
     151        1540 :       return F2xqE_dbl_slope(P, a, T, slope);
     152             :     else
     153      155008 :       return ellinf();
     154             :   }
     155      196196 :   *slope = F2xq_div(F2x_add(Py, Qy), F2x_add(Px, Qx), T);
     156      196196 :   R = cgetg(3,t_VEC);
     157      196196 :   if (typ(a)==t_VECSMALL)
     158             :   {
     159       66437 :     GEN a2 = a;
     160       66437 :     gel(R, 1) = F2x_add(F2x_add(F2x_add(F2x_add(F2xq_sqr(*slope, T), *slope), Px), Qx), a2);
     161       66437 :     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      129759 :     GEN a3 = gel(a,1);
     166      129759 :     gel(R, 1) = F2x_add(F2x_add(F2xq_sqr(*slope, T), Px), Qx);
     167      129759 :     gel(R, 2) = F2x_add(F2xq_mul(*slope, F2x_add(Px, gel(R, 1)), T), F2x_add(Py, a3));
     168             :   }
     169      196196 :   return R;
     170             : }
     171             : 
     172             : GEN
     173      354207 : F2xqE_add(GEN P, GEN Q, GEN a, GEN T)
     174             : {
     175      354207 :   pari_sp av = avma;
     176             :   GEN slope;
     177      354207 :   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     1055971 : _F2xqE_dbl(void *E, GEN P)
     215             : {
     216     1055971 :   struct _F2xqE *ell = (struct _F2xqE *) E;
     217     1055971 :   return F2xqE_dbl(P, ell->a2, ell->T);
     218             : }
     219             : 
     220             : static GEN
     221      354207 : _F2xqE_add(void *E, GEN P, GEN Q)
     222             : {
     223      354207 :   struct _F2xqE *ell=(struct _F2xqE *) E;
     224      354207 :   return F2xqE_add(P, Q, ell->a2, ell->T);
     225             : }
     226             : 
     227             : static GEN
     228      212898 : _F2xqE_mul(void *E, GEN P, GEN n)
     229             : {
     230      212898 :   pari_sp av = avma;
     231      212898 :   struct _F2xqE *e=(struct _F2xqE *) E;
     232      212898 :   long s = signe(n);
     233      212898 :   if (!s || ell_is_inf(P)) return ellinf();
     234      208621 :   if (s<0) P = F2xqE_neg(P, e->a2, e->T);
     235      208621 :   if (is_pm1(n)) return s>0? gcopy(P): P;
     236      203231 :   return gerepileupto(av, gen_pow(P, n, e, &_F2xqE_dbl, &_F2xqE_add));
     237             : }
     238             : 
     239             : GEN
     240      184352 : F2xqE_mul(GEN P, GEN n, GEN a2, GEN T)
     241             : {
     242             :   struct _F2xqE E;
     243      184352 :   E.a2 = a2; E.T = T;
     244      184352 :   return _F2xqE_mul(&E, P, n);
     245             : }
     246             : 
     247             : /* Finds a random non-singular point on E */
     248             : GEN
     249      181650 : random_F2xqE(GEN a, GEN a6, GEN T)
     250             : {
     251      181650 :   pari_sp ltop = avma;
     252             :   GEN x, y, rhs, u;
     253             :   do
     254             :   {
     255      377776 :     avma= ltop;
     256      377776 :     x   = random_F2x(F2x_degree(T),T[1]);
     257      377776 :     if (typ(a) == t_VECSMALL)
     258             :     {
     259       62909 :       GEN a2 = a, x2;
     260       62909 :       if (!lgpol(x))
     261         672 :         { avma=ltop; retmkvec2(pol0_Flx(T[1]), F2xq_sqrt(a6,T)); }
     262       62237 :       u = x; x2  = F2xq_sqr(x, T);
     263       62237 :       rhs = F2x_add(F2xq_mul(x2,F2x_add(x,a2),T),a6);
     264       62237 :       rhs = F2xq_div(rhs,x2,T);
     265             :     }
     266             :     else
     267             :     {
     268      314867 :       GEN a3 = gel(a,1), a4 = gel(a,2), a3i = gel(a,3), u2i;
     269      314867 :       u = a3; u2i = F2xq_sqr(a3i,T);
     270      314867 :       rhs = F2x_add(F2xq_mul(x,F2x_add(F2xq_sqr(x,T),a4),T),a6);
     271      314867 :       rhs = F2xq_mul(rhs,u2i,T);
     272             :     }
     273      377104 :   } while (F2xq_trace(rhs,T));
     274      180978 :   y = F2xq_mul(F2xq_Artin_Schreier(rhs, T), u, T);
     275      180978 :   return gerepilecopy(ltop, mkvec2(x, y));
     276             : }
     277             : 
     278             : static GEN
     279       13650 : _F2xqE_rand(void *E)
     280             : {
     281       13650 :   struct _F2xqE *ell=(struct _F2xqE *) E;
     282       13650 :   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 long
     323       22099 : is_2_torsion(GEN Q, GEN a)
     324             : {
     325       22099 :   return (typ(a)==t_VEC || lgpol(gel(Q, 1))) ? 0: 1;
     326             : }
     327             : 
     328             : static GEN
     329       36932 : F2xqE_vert(GEN P, GEN Q, GEN a, GEN T)
     330             : {
     331       36932 :   long vT = T[1];
     332       36932 :   if (ell_is_inf(P))
     333        9583 :     return pol1_F2x(T[1]);
     334       27349 :   if (!F2x_equal(gel(Q, 1), gel(P, 1)))
     335       24591 :     return F2x_add(gel(Q, 1), gel(P, 1));
     336        2758 :   if (is_2_torsion(Q, a))
     337           0 :     return F2xq_inv(gel(Q,2), T);
     338        2758 :   return pol1_F2x(vT);
     339             : }
     340             : 
     341             : static GEN
     342       17766 : F2xqE_Miller_line(GEN R, GEN Q, GEN slope, GEN a, GEN T)
     343             : {
     344       17766 :   long vT = T[1];
     345       17766 :   GEN x = gel(Q, 1), y = gel(Q, 2);
     346       17766 :   GEN tmp1 = F2x_add(x, gel(R, 1));
     347       17766 :   GEN tmp2 = F2x_add(F2xq_mul(tmp1, slope, T), gel(R, 2));
     348             :   GEN s1, s2, ix;
     349       17766 :   if (!F2x_equal(y, tmp2))
     350       16156 :     return F2x_add(y, tmp2);
     351        1610 :   if (is_2_torsion(Q, a)) return pol1_F2x(vT);
     352        1610 :   if (typ(a)==t_VEC)
     353             :   {
     354        1498 :     GEN a4 = gel(a,2), a3i = gel(a,3);
     355        1498 :     s1 = F2xq_mul(F2x_add(a4, F2xq_sqr(x, T)), a3i, T);
     356        1498 :     if (!F2x_equal(s1, slope))
     357         686 :       return F2x_add(s1, slope);
     358         812 :     s2 = F2xq_mul(F2x_add(x, F2xq_sqr(s1, T)), a3i, T);
     359         812 :     if (lgpol(s2)) return s2;
     360         126 :     return zv_copy(a3i);
     361             :   } else
     362             :   {
     363         112 :     GEN a2 = a ;
     364         112 :     ix = F2xq_inv(x, T);
     365         112 :     s1 = F2x_add(x, F2xq_mul(y, ix, T));
     366         112 :     if (!F2x_equal(s1, slope))
     367           7 :       return F2x_add(s1, slope);
     368         105 :     s2 =F2x_add(a2, F2x_add(F2xq_sqr(s1,T), s1));
     369         105 :     if (!F2x_equal(s2, x))
     370           7 :       return  F2x_add(pol1_F2x(vT), F2xq_mul(s2, ix, T));
     371          98 :     return ix;
     372             :   }
     373             : }
     374             : 
     375             : /* Computes the equation of the line tangent to R and returns its
     376             :    evaluation at the point Q. Also doubles the point R.
     377             :  */
     378             : 
     379             : static GEN
     380       17731 : F2xqE_tangent_update(GEN R, GEN Q, GEN a2, GEN T, GEN *pt_R)
     381             : {
     382       17731 :   if (ell_is_inf(R))
     383             :   {
     384           0 :     *pt_R = ellinf();
     385           0 :     return pol1_F2x(T[1]);
     386             :   }
     387       17731 :   else if (is_2_torsion(R, a2))
     388             :   {
     389           0 :     *pt_R = ellinf();
     390           0 :     return F2xqE_vert(R, Q, a2, T);
     391             :   } else {
     392             :     GEN slope;
     393       17731 :     *pt_R = F2xqE_dbl_slope(R, a2, T, &slope);
     394       17731 :     return F2xqE_Miller_line(R, Q, slope, a2, T);
     395             :   }
     396             : }
     397             : 
     398             : /* Computes the equation of the line through R and P, and returns its
     399             :    evaluation at the point Q. Also adds P to the point R.
     400             :  */
     401             : 
     402             : static GEN
     403        9618 : F2xqE_chord_update(GEN R, GEN P, GEN Q, GEN a2, GEN T, GEN *pt_R)
     404             : {
     405        9618 :   if (ell_is_inf(R))
     406             :   {
     407           0 :     *pt_R = gcopy(P);
     408           0 :     return F2xqE_vert(P, Q, a2, T);
     409             :   }
     410        9618 :   else if (ell_is_inf(P))
     411             :   {
     412           0 :     *pt_R = gcopy(R);
     413           0 :     return F2xqE_vert(R, Q, a2, T);
     414             :   }
     415        9618 :   else if (F2x_equal(gel(P, 1), gel(R, 1)))
     416             :   {
     417        9583 :     if (F2x_equal(gel(P, 2), gel(R, 2)))
     418           0 :       return F2xqE_tangent_update(R, Q, a2, T, pt_R);
     419             :     else
     420             :     {
     421        9583 :       *pt_R = ellinf();
     422        9583 :       return F2xqE_vert(R, Q, a2, T);
     423             :     }
     424             :   } else {
     425             :     GEN slope;
     426          35 :     *pt_R = F2xqE_add_slope(P, R, a2, T, &slope);
     427          35 :     return F2xqE_Miller_line(R, Q, slope, a2, T);
     428             :   }
     429             : }
     430             : 
     431             : /* Returns the Miller function f_{m, Q} evaluated at the point P using
     432             :    the standard Miller algorithm.
     433             :  */
     434             : 
     435             : struct _F2xqE_miller
     436             : {
     437             :   GEN T, a2, P;
     438             : };
     439             : 
     440             : static GEN
     441       17731 : F2xqE_Miller_dbl(void* E, GEN d)
     442             : {
     443       17731 :   struct _F2xqE_miller *m = (struct _F2xqE_miller *)E;
     444       17731 :   GEN T = m->T, a2 = m->a2, P = m->P;
     445             :   GEN v, line;
     446       17731 :   GEN num = F2xq_sqr(gel(d,1), T);
     447       17731 :   GEN denom = F2xq_sqr(gel(d,2), T);
     448       17731 :   GEN point = gel(d,3);
     449       17731 :   line = F2xqE_tangent_update(point, P, a2, T, &point);
     450       17731 :   num  = F2xq_mul(num, line, T);
     451       17731 :   v = F2xqE_vert(point, P, a2, T);
     452       17731 :   denom = F2xq_mul(denom, v, T);
     453       17731 :   return mkvec3(num, denom, point);
     454             : }
     455             : 
     456             : static GEN
     457        9618 : F2xqE_Miller_add(void* E, GEN va, GEN vb)
     458             : {
     459        9618 :   struct _F2xqE_miller *m = (struct _F2xqE_miller *)E;
     460        9618 :   GEN T = m->T, a2 = m->a2, P = m->P;
     461             :   GEN v, line, point;
     462        9618 :   GEN na = gel(va,1), da = gel(va,2), pa = gel(va,3);
     463        9618 :   GEN nb = gel(vb,1), db = gel(vb,2), pb = gel(vb,3);
     464        9618 :   GEN num   = F2xq_mul(na, nb, T);
     465        9618 :   GEN denom = F2xq_mul(da, db, T);
     466        9618 :   line = F2xqE_chord_update(pa, pb, P, a2, T, &point);
     467        9618 :   num  = F2xq_mul(num, line, T);
     468        9618 :   v = F2xqE_vert(point, P, a2, T);
     469        9618 :   denom = F2xq_mul(denom, v, T);
     470        9618 :   return mkvec3(num, denom, point);
     471             : }
     472             : 
     473             : static GEN
     474        9618 : F2xqE_Miller(GEN Q, GEN P, GEN m, GEN a2, GEN T)
     475             : {
     476        9618 :   pari_sp ltop = avma;
     477             :   struct _F2xqE_miller d;
     478             :   GEN v, num, denom, g1;
     479             : 
     480        9618 :   d.a2 = a2; d.T = T; d.P = P;
     481        9618 :   g1 = pol1_F2x(T[1]);
     482        9618 :   v = gen_pow(mkvec3(g1,g1,Q), m, (void*)&d, F2xqE_Miller_dbl, F2xqE_Miller_add);
     483        9618 :   num = gel(v,1); denom = gel(v,2);
     484        9618 :   return gerepileupto(ltop, F2xq_div(num, denom, T));
     485             : }
     486             : 
     487             : GEN
     488        5334 : F2xqE_weilpairing(GEN P, GEN Q, GEN m, GEN a2, GEN T)
     489             : {
     490        5334 :   pari_sp ltop = avma;
     491             :   GEN num, denom, result;
     492        5334 :   if (ell_is_inf(P) || ell_is_inf(Q) || F2x_equal(P,Q))
     493         539 :     return pol1_F2x(T[1]);
     494        4795 :   num    = F2xqE_Miller(P, Q, m, a2, T);
     495        4795 :   denom  = F2xqE_Miller(Q, P, m, a2, T);
     496        4795 :   result = F2xq_div(num, denom, T);
     497        4795 :   return gerepileupto(ltop, result);
     498             : }
     499             : 
     500             : GEN
     501          28 : F2xqE_tatepairing(GEN P, GEN Q, GEN m, GEN a2, GEN T)
     502             : {
     503          28 :   if (ell_is_inf(P) || ell_is_inf(Q))
     504           0 :     return pol1_F2x(T[1]);
     505          28 :   return F2xqE_Miller(P, Q, m, a2, T);
     506             : }
     507             : 
     508             : /***********************************************************************/
     509             : /**                                                                   **/
     510             : /**                          Point counting                           **/
     511             : /**                                                                   **/
     512             : /***********************************************************************/
     513             : 
     514             : static GEN
     515       72479 : Z2x_rshift(GEN y, long x)
     516             : {
     517             :   GEN z;
     518             :   long i, l;
     519       72479 :   if (!x) return pol0_Flx(y[1]);
     520       72479 :   z = cgetg_copy(y, &l); z[1] = y[1];
     521       72497 :   for(i=2; i<l; i++) z[i] = y[i]>>x;
     522       72497 :   return Flx_renormalize(z, l);
     523             : }
     524             : 
     525             : /* Solve the linear equation approximation in the Newton algorithm */
     526             : 
     527             : static GEN
     528      178423 : 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))
     529             : {
     530      178423 :   pari_sp av = avma;
     531             :   long N2, M;
     532             :   GEN VN2, V2, VM, bil;
     533      178423 :   ulong q = 1UL<<N;
     534      178423 :   if (N == 1) return invl(E, V);
     535       72494 :   V = Flx_red(V, q);
     536       72484 :   N2 = (N + 1)>>1; M = N - N2;
     537       72484 :   F = FlxT_red(F, q);
     538       72488 :   VN2 = gen_Z2x_Dixon(F, V, N2, E, lin, invl);
     539       72494 :   bil = lin(E, F, VN2, N);
     540       72491 :   V2 = Z2x_rshift(Flx_sub(V, bil, q), N2);
     541       72488 :   VM = gen_Z2x_Dixon(F, V2, M, E, lin, invl);
     542       72493 :   return gerepileupto(av, Flx_add(VN2, Flx_Fl_mul(VM, 1UL<<N2, q), q));
     543             : }
     544             : 
     545             : /* Solve F(X) = V mod 2^N
     546             :    F(Xn) = V [mod 2^n]
     547             :    Vm = (V-F(Xn))/(2^n)
     548             :    F(Xm) = Vm
     549             :    X = Xn + 2^n*Xm
     550             : */
     551             : 
     552             : static GEN
     553       33459 : gen_Z2X_Dixon(GEN F, GEN V, long N, void *E,
     554             :                      GEN lin(void *E, GEN F, GEN d, long N),
     555             :                      GEN lins(void *E, GEN F, GEN d, long N),
     556             :                      GEN invls(void *E, GEN d))
     557             : {
     558       33459 :   pari_sp av = avma;
     559             :   long n, m;
     560             :   GEN Xn, Xm, FXn, Vm;
     561       33459 :   if (N<BITS_IN_LONG)
     562             :   {
     563       33439 :     ulong q = 1UL<<N;
     564       33439 :     return Flx_to_ZX(gen_Z2x_Dixon(ZXT_to_FlxT(F,q), ZX_to_Flx(V,q),N,E,lins,invls));
     565             :   }
     566          20 :   V = ZX_remi2n(V, N);
     567          20 :   n = (N + 1)>>1; m = N - n;
     568          20 :   F = ZXT_remi2n(F, N);
     569          20 :   Xn = gen_Z2X_Dixon(F, V, n, E, lin, lins, invls);
     570          20 :   FXn = lin(E, F, Xn, N);
     571          20 :   Vm = ZX_shifti(ZX_sub(V, FXn), -n);
     572          20 :   Xm = gen_Z2X_Dixon(F, Vm, m, E, lin, lins, invls);
     573          20 :   return gerepileupto(av, ZX_remi2n(ZX_add(Xn, ZX_shifti(Xm, n)), N));
     574             : }
     575             : 
     576             : /* H -> H mod 2*/
     577             : 
     578       52678 : static GEN _can_invls(void *E, GEN V) {(void) E; return V; }
     579             : 
     580             : /* H -> H-(f0*H0-f1*H1) */
     581             : 
     582          10 : static GEN _can_lin(void *E, GEN F, GEN V, long N)
     583             : {
     584          10 :   pari_sp av=avma;
     585             :   GEN d0, d1, z;
     586             :   (void) E;
     587          10 :   RgX_even_odd(V, &d0, &d1);
     588          10 :   z =  ZX_sub(V, ZX_sub(ZX_mul(gel(F,1), d0), ZX_mul(gel(F,2), d1)));
     589          10 :   return gerepileupto(av, ZX_remi2n(z, N));
     590             : }
     591             : 
     592       36095 : static GEN _can_lins(void *E, GEN F, GEN V, long N)
     593             : {
     594       36095 :   GEN D=Flx_splitting(V, 2), z;
     595       36093 :   ulong q = 1UL<<N;
     596             :   (void) E;
     597       36093 :   z = Flx_sub(Flx_mul(gel(F,1), gel(D,1), q), Flx_mul(gel(F,2), gel(D,2), q), q);
     598       36093 :   return Flx_sub(V, z, q);
     599             : }
     600             : 
     601             : /* P -> P-(P0^2-X*P1^2) */
     602             : 
     603             : static GEN
     604       16573 : _can_iter(void *E, GEN f2, GEN q)
     605             : {
     606             :   GEN f0, f1, z;
     607             :   (void) E;
     608       16573 :   RgX_even_odd(f2, &f0, &f1);
     609       16573 :   z = ZX_add(ZX_sub(f2, FpX_sqr(f0, q)), RgX_shift_shallow(FpX_sqr(f1, q), 1));
     610       16573 :   return mkvec3(z,f0,f1);
     611             : }
     612             : 
     613             : /* H -> H-(2*P0*H0-2*X*P1*H1) */
     614             : 
     615             : static GEN
     616       16573 : _can_invd(void *E, GEN V, GEN v, GEN q, long M)
     617             : {
     618             :   GEN F;
     619             :   (void)E; (void)q;
     620       16573 :   F = mkvec2(ZX_shifti(gel(v,2),1), ZX_shifti(RgX_shift_shallow(gel(v,3),1),1));
     621       16573 :   return gen_Z2X_Dixon(F, V, M, NULL, _can_lin, _can_lins, _can_invls);
     622             : }
     623             : 
     624             : /* Lift P to Q such that Q(x^2)=Q(x)*Q(-x) mod 2^n
     625             :    if Q = Q0(X^2)+X*Q1(X^2), solve Q(x^2) = Q0^2-X*Q1^2
     626             : */
     627             : static GEN
     628        7213 : F2x_canonlift(GEN P, long n)
     629        7213 : { return gen_ZpX_Newton(F2x_to_ZX(P),gen_2, n, NULL, _can_iter, _can_invd); }
     630             : 
     631             : static GEN
     632       16856 : Z2XQ_frob(GEN x, GEN T, GEN q)
     633             : {
     634       16856 :   return FpX_rem(RgX_inflate(x, 2), T, q);
     635             : }
     636             : 
     637             : static GEN
     638       36398 : Z2xq_frob(GEN x, GEN T, ulong q)
     639             : {
     640       36398 :   return Flx_rem(Flx_inflate(x, 2), T, q);
     641             : }
     642             : 
     643             : struct _frob_lift
     644             : {
     645             :   GEN T, sqx;
     646             : };
     647             : 
     648             : /* H -> S^-1(H) mod 2 */
     649             : 
     650       53254 : static GEN _frob_invls(void *E, GEN V)
     651             : {
     652       53254 :   struct _frob_lift *F = (struct _frob_lift*) E;
     653       53254 :   GEN sqx = F->sqx;
     654       53254 :   return F2x_to_Flx(F2xq_sqrt_fast(Flx_to_F2x(V), gel(sqx,1), gel(sqx,2)));
     655             : }
     656             : 
     657             : /* H -> f1*S(H) + f2*H */
     658             : 
     659          10 : static GEN _frob_lin(void *E, GEN F, GEN x2, long N)
     660             : {
     661          10 :   GEN T = gel(F,3);
     662          10 :   GEN q = int2n(N);
     663          10 :   GEN y2  = Z2XQ_frob(x2, T, q);
     664          10 :   GEN lin = ZX_add(ZX_mul(gel(F,1), y2), ZX_mul(gel(F,2), x2));
     665             :   (void) E;
     666          10 :   return FpX_rem(ZX_remi2n(lin, N), T, q);
     667             : }
     668             : 
     669       36398 : static GEN _frob_lins(void *E, GEN F, GEN x2, long N)
     670             : {
     671       36398 :   GEN T = gel(F,3);
     672       36398 :   ulong q = 1UL<<N;
     673       36398 :   GEN y2  = Z2xq_frob(x2, T, q);
     674       36396 :   GEN lin = Flx_add(Flx_mul(gel(F,1), y2,q), Flx_mul(gel(F,2), x2,q),q);
     675             :   (void) E;
     676       36398 :   return Flx_rem(lin, T, q);
     677             : }
     678             : 
     679             : /* X -> P(X,S(X)) */
     680             : 
     681             : static GEN
     682       16846 : _lift_iter(void *E, GEN x2, GEN q)
     683             : {
     684       16846 :   struct _frob_lift *F = (struct _frob_lift*) E;
     685       16846 :   long N = expi(q);
     686       16846 :   GEN TN = ZXT_remi2n(F->T, N);
     687       16846 :   GEN y2 = Z2XQ_frob(x2, TN, q);
     688       16846 :   GEN x2y2 = FpX_rem(ZX_remi2n(ZX_mul(x2, y2), N), TN, q);
     689       16846 :   GEN s = ZX_add(ZX_add(x2, ZX_shifti(y2, 1)), ZX_shifti(x2y2, 3));
     690       16846 :   GEN V = ZX_add(ZX_add(ZX_sqr(s), y2), ZX_shifti(x2y2, 2));
     691       16846 :   return mkvec4(FpX_rem(ZX_remi2n(V, N), TN, q),x2,y2,s);
     692             : }
     693             : 
     694             : /* H -> Dx*H+Dy*S(H) */
     695             : 
     696             : static GEN
     697       16846 : _lift_invd(void *E, GEN V, GEN v, GEN qM, long M)
     698             : {
     699       16846 :   struct _frob_lift *F = (struct _frob_lift*) E;
     700       16846 :   GEN TM = ZXT_remi2n(F->T, M);
     701       16846 :   GEN x2 = gel(v,2), y2 = gel(v,3), s = gel(v,4), r;
     702       16846 :   GEN Dx = ZX_add(ZX_mul(ZX_Z_add(ZX_shifti(y2, 4), gen_2), s),
     703             :                          ZX_shifti(y2, 2));
     704       16846 :   GEN Dy = ZX_add(ZX_Z_add(ZX_mul(ZX_Z_add(ZX_shifti(x2, 4), utoi(4)), s),
     705             :                            gen_1), ZX_shifti(x2, 2));
     706       16846 :   Dx = FpX_rem(ZX_remi2n(Dx, M), TM, qM);
     707       16846 :   Dy = FpX_rem(ZX_remi2n(Dy, M), TM, qM);
     708       16846 :   r = mkvec3(Dy, Dx, TM);
     709       16846 :   return gen_Z2X_Dixon(r, V, M, E, _frob_lin, _frob_lins, _frob_invls);
     710             : }
     711             : 
     712             : /*
     713             :   Let P(X,Y)=(X+2*Y+8*X*Y)^2+Y+4*X*Y
     714             :   Solve   P(x,S(x))=0 [mod 2^n,T]
     715             :   assuming  x = x0    [mod 2,T]
     716             : 
     717             :   we set s = X+2*Y+8*X*Y, P = s^2+Y+4*X*Y
     718             :   Dx = dP/dx = (16*s+4)*x+(4*s+1)
     719             :   Dy = dP/dy = (16*y+2)*s+4*y
     720             : */
     721             : 
     722             : static GEN
     723        7451 : solve_AGM_eqn(GEN x0, long n, GEN T, GEN sqx)
     724             : {
     725             :   struct _frob_lift F;
     726        7451 :   F.T=T; F.sqx=sqx;
     727        7451 :   return gen_ZpX_Newton(x0, gen_2, n, &F, _lift_iter, _lift_invd);
     728             : }
     729             : 
     730             : static GEN
     731         238 : Z2XQ_invnorm_pcyc(GEN a, GEN T, long e)
     732             : {
     733         238 :   GEN q = int2n(e);
     734         238 :   GEN z = ZpXQ_norm_pcyc(a, T, q, gen_2);
     735         238 :   return Fp_inv(z, q);
     736             : }
     737             : 
     738             : /* Assume a = 1 [4] */
     739             : static GEN
     740        7213 : Z2XQ_invnorm(GEN a, GEN T, long e)
     741             : {
     742             :   pari_timer ti;
     743        7213 :   GEN pe = int2n(e), s;
     744        7213 :   if (degpol(a)==0)
     745          56 :     return Fp_inv(Fp_powu(gel(a,2), get_FpX_degree(T), pe), pe);
     746        7157 :   if (DEBUGLEVEL>=3) timer_start(&ti);
     747        7157 :   s = ZpXQ_log(a, T, gen_2, e);
     748        7157 :   if (DEBUGLEVEL>=3) timer_printf(&ti,"Z2XQ_log");
     749        7157 :   s = Fp_neg(FpXQ_trace(s, T, pe), pe);
     750        7157 :   if (DEBUGLEVEL>=3) timer_printf(&ti,"FpXQ_trace");
     751        7157 :   s = modii(gel(Qp_exp(cvtop(s, gen_2, e-2)),4),pe);
     752        7157 :   if (DEBUGLEVEL>=3) timer_printf(&ti,"Qp_exp");
     753        7157 :   return s;
     754             : }
     755             : 
     756             : /* Assume a2==0, so 4|E(F_p): if t^4 = a6 then (t,t^2) is of order 4
     757             :    8|E(F_p) <=> trace(a6)==0
     758             :  */
     759             : 
     760             : static GEN
     761        7633 : F2xq_elltrace_Harley(GEN a6, GEN T2)
     762             : {
     763        7633 :   pari_sp ltop = avma;
     764             :   pari_timer ti;
     765             :   GEN T, sqx;
     766             :   GEN x, x2, t;
     767        7633 :   long n = F2x_degree(T2), N = ((n + 1)>>1) + 2;
     768             :   long ispcyc;
     769        7633 :   if (n==1) return gen_m1;
     770        7605 :   if (n==2) return F2x_degree(a6) ? gen_1 : stoi(-3);
     771        7766 :   if (n==3) return F2x_degree(a6) ? (F2xq_trace(a6,T2) ?  stoi(-3): gen_1)
     772         203 :                                   : stoi(5);
     773        7451 :   timer_start(&ti);
     774        7451 :   sqx = mkvec2(F2xq_sqrt(polx_F2x(T2[1]),T2), T2);
     775        7451 :   if (DEBUGLEVEL>1) timer_printf(&ti,"Sqrtx");
     776        7451 :   ispcyc = zx_is_pcyc(F2x_to_Flx(T2));
     777        7451 :   T = ispcyc? F2x_to_ZX(T2): F2x_canonlift(T2, N-2);
     778        7451 :   if (DEBUGLEVEL>1) timer_printf(&ti,"Teich");
     779        7451 :   T = FpX_get_red(T, int2n(N));
     780        7451 :   if (DEBUGLEVEL>1) timer_printf(&ti,"Barrett");
     781        7451 :   x = solve_AGM_eqn(F2x_to_ZX(a6), N-2, T, sqx);
     782        7451 :   if (DEBUGLEVEL>1) timer_printf(&ti,"Lift");
     783        7451 :   x2 = ZX_Z_add_shallow(ZX_shifti(x,2), gen_1);
     784        7451 :   t = (ispcyc? Z2XQ_invnorm_pcyc: Z2XQ_invnorm)(x2, T, N);
     785        7451 :   if (DEBUGLEVEL>1) timer_printf(&ti,"Norm");
     786        7451 :   if (cmpii(sqri(t), int2n(n + 2)) > 0)
     787        3520 :     t = subii(t, int2n(N));
     788        7451 :   return gerepileuptoint(ltop, t);
     789             : }
     790             : 
     791             : static GEN
     792       23695 : get_v(GEN u, GEN a, GEN T)
     793             : {
     794       23695 :   GEN a4 = gel(a,2), a3i = gel(a,3);
     795       23695 :   GEN ui2 = F2xq_mul(u, a3i, T), ui4 = F2xq_sqr(ui2, T);
     796       23695 :   return F2xq_mul(a4, ui4, T);
     797             : }
     798             : 
     799             : static GEN
     800       10304 : get_r(GEN w, GEN u, GEN T)
     801             : {
     802       10304 :   return F2xq_sqr(F2xq_mul(F2xq_Artin_Schreier(w, T), u, T), T);
     803             : }
     804             : 
     805             : static GEN
     806       37723 : F2xq_elltracej(GEN a, GEN a6, GEN T, GEN q, long n)
     807             : {
     808       37723 :   GEN a3 = gel(a,1), a4 = gel(a,2), a3i = gel(a,3);
     809             :   GEN r, pi, rhs;
     810       37723 :   long t, s, m = n >> 1;
     811       37723 :   if (odd(n))
     812             :   {
     813             :     GEN u, v, w;
     814       16814 :     u = F2xq_pow(a3,diviuexact(subiu(shifti(q,1), 1), 3),T);
     815       16814 :     v = get_v(u, a, T);
     816       16814 :     if (F2xq_trace(v, T)==0) return gen_0;
     817        8589 :     w = F2xq_Artin_Schreier(F2x_1_add(v), T);
     818        8589 :     if (F2xq_trace(w, T)) w = F2x_1_add(w);
     819        8589 :     r = get_r(w, u, T);
     820        8589 :     pi = int2n(m+1);
     821        8589 :     s = (((m+3)&3L) <= 1) ? -1: 1;
     822             :   }
     823             :   else
     824             :   {
     825       20909 :     if (F2x_degree(F2xq_pow(a3,diviuexact(subiu(q, 1), 3),T))==0)
     826             :     {
     827             :       GEN u, v, w;
     828        6881 :       u = F2xq_sqrtn(a3, utoi(3), T, NULL);
     829        6881 :       v = get_v(u, a, T);
     830        6881 :       if (F2xq_trace(v, T)==1) return gen_0;
     831        3542 :       w = F2xq_Artin_Schreier(v, T);
     832        3542 :       if (F2xq_trace(w, T)==1) return gen_0;
     833        1715 :       r = get_r(w, u, T);
     834        1715 :       pi = int2n(m+1);
     835        1715 :       s = odd(m+1) ? -1: 1;
     836             :     }
     837             :     else
     838             :     {
     839       14028 :       long sv = T[1];
     840       14028 :       GEN P = mkpoln(5, pol1_F2x(sv), pol0_F2x(sv), pol0_F2x(sv), a3, a4);
     841       14028 :       r = F2xq_sqr(gel(F2xqX_roots(P,T), 1), T);
     842       14028 :       pi = int2n(m);
     843       14028 :       s = odd(m) ? -1: 1;
     844             :     }
     845             :   }
     846       24332 :   rhs = F2x_add(F2xq_mul(F2x_add(F2xq_sqr(r, T), a4), r, T), a6);
     847       24332 :   t = F2xq_trace(F2xq_mul(rhs, F2xq_sqr(a3i, T), T), T);
     848       24332 :   return (t==0)^(s==1)? pi: negi(pi);
     849             : }
     850             : 
     851             : GEN
     852       45440 : F2xq_ellcard(GEN a, GEN a6, GEN T)
     853             : {
     854       45440 :   pari_sp av = avma;
     855       45440 :   long n = F2x_degree(T);
     856             :   GEN c;
     857       45440 :   if (typ(a)==t_VECSMALL)
     858             :   {
     859        7633 :     GEN t = F2xq_elltrace_Harley(a6, T);
     860        7633 :     c = addii(int2u(n), F2xq_trace(a,T) ? addui(1,t): subui(1,t));
     861       37807 :   } else if (n==1)
     862             :   {
     863          84 :     long a4i = lgpol(gel(a,2)), a6i = lgpol(a6);
     864          84 :     return utoi(a4i? (a6i? 1: 5): 3);
     865             :   }
     866             :   else
     867             :   {
     868       37723 :     GEN q = int2u(n);
     869       37723 :     c = subii(addiu(q,1), F2xq_elltracej(a, a6, T, q, n));
     870             :   }
     871       45356 :   return gerepileuptoint(av, c);
     872             : }
     873             : 
     874             : /***********************************************************************/
     875             : /**                                                                   **/
     876             : /**                          Group structure                          **/
     877             : /**                                                                   **/
     878             : /***********************************************************************/
     879             : 
     880             : static GEN
     881         371 : _F2xqE_pairorder(void *E, GEN P, GEN Q, GEN m, GEN F)
     882             : {
     883         371 :   struct _F2xqE *e = (struct _F2xqE *) E;
     884         371 :   return  F2xq_order(F2xqE_weilpairing(P,Q,m,e->a2,e->T), F, e->T);
     885             : }
     886             : 
     887             : GEN
     888        3668 : F2xq_ellgroup(GEN a2, GEN a6, GEN N, GEN T, GEN *pt_m)
     889             : {
     890             :   struct _F2xqE e;
     891        3668 :   GEN q = int2u(F2x_degree(T));
     892        3668 :   e.a2=a2; e.a6=a6; e.T=T;
     893        3668 :   return gen_ellgroup(N, subiu(q,1), pt_m, (void*)&e, &F2xqE_group,
     894             :                                                       _F2xqE_pairorder);
     895             : }
     896             : 
     897             : GEN
     898        3598 : F2xq_ellgens(GEN a2, GEN a6, GEN ch, GEN D, GEN m, GEN T)
     899             : {
     900             :   GEN P;
     901        3598 :   pari_sp av = avma;
     902             :   struct _F2xqE e;
     903        3598 :   e.a2=a2; e.a6=a6; e.T=T;
     904        3598 :   switch(lg(D)-1)
     905             :   {
     906             :   case 0:
     907           7 :     return cgetg(1,t_VEC);
     908             :   case 1:
     909        3479 :     P = gen_gener(gel(D,1), (void*)&e, &F2xqE_group);
     910        3479 :     P = mkvec(F2xqE_changepoint(P, ch, T));
     911        3479 :     break;
     912             :   default:
     913         112 :     P = gen_ellgens(gel(D,1), gel(D,2), m, (void*)&e, &F2xqE_group,
     914             :                                                       _F2xqE_pairorder);
     915         112 :     gel(P,1) = F2xqE_changepoint(gel(P,1), ch, T);
     916         112 :     gel(P,2) = F2xqE_changepoint(gel(P,2), ch, T);
     917         112 :     break;
     918             :   }
     919        3591 :   return gerepilecopy(av, P);
     920             : }

Generated by: LCOV version 1.11