Code coverage tests

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

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

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

LCOV - code coverage report
Current view: top level - basemath - F2xqE.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.16.2 lcov report (development 29115-f22e516b23) Lines: 419 447 93.7 %
Date: 2024-03-19 08:06:49 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; either version 2 of the License, or (at your option) any later
       8             : version. It is distributed in the hope that it will be useful, but WITHOUT
       9             : ANY WARRANTY WHATSOEVER.
      10             : 
      11             : Check the License for details. You should have received a copy of it, along
      12             : with the package; see the file 'COPYING'. If not, write to the Free Software
      13             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      14             : 
      15             : #include "pari.h"
      16             : #include "paripriv.h"
      17             : 
      18             : #define DEBUGLEVEL DEBUGLEVEL_ellcard
      19             : 
      20             : /* Not so fast arithmetic with points over elliptic curves over F_2^n */
      21             : 
      22             : /***********************************************************************/
      23             : /**                                                                   **/
      24             : /**                              F2xqE                                **/
      25             : /**                                                                   **/
      26             : /***********************************************************************/
      27             : 
      28             : /* Theses functions deal with point over elliptic curves over F_2^n defined
      29             :  * by an equation of the form:
      30             :  ** y^2+x*y=x^3+a_2*x^2+a_6 if the curve is ordinary.
      31             :  ** y^2+a_3*y=x^3+a_4*x+a_6 if the curve is supersingular.
      32             :  * Most of the time a6 is omitted since it can be recovered from any point
      33             :  * on the curve.
      34             :  * For supersingular curves, the parameter a2 is replaced by [a3,a4,a3^-1].
      35             :  */
      36             : 
      37             : GEN
      38      194544 : RgE_to_F2xqE(GEN x, GEN T)
      39             : {
      40      194544 :   if (ell_is_inf(x)) return x;
      41      194061 :   retmkvec2(Rg_to_F2xq(gel(x,1),T),Rg_to_F2xq(gel(x,2),T));
      42             : }
      43             : 
      44             : GEN
      45      355838 : F2xqE_changepoint(GEN x, GEN ch, GEN T)
      46             : {
      47      355838 :   pari_sp av = avma;
      48             :   GEN p1,z,u,r,s,t,v,v2,v3;
      49      355838 :   if (ell_is_inf(x)) return x;
      50      187215 :   u = gel(ch,1); r = gel(ch,2);
      51      187215 :   s = gel(ch,3); t = gel(ch,4);
      52      187215 :   v = F2xq_inv(u, T); v2 = F2xq_sqr(v, T); v3 = F2xq_mul(v,v2, T);
      53      187215 :   p1 = F2x_add(gel(x,1),r);
      54      187215 :   z = cgetg(3,t_VEC);
      55      187215 :   gel(z,1) = F2xq_mul(v2, p1, T);
      56      187215 :   gel(z,2) = F2xq_mul(v3, F2x_add(gel(x,2), F2x_add(F2xq_mul(s, p1, T),t)), T);
      57      187215 :   return gerepileupto(av, z);
      58             : }
      59             : 
      60             : GEN
      61      194544 : F2xqE_changepointinv(GEN x, GEN ch, GEN T)
      62             : {
      63             :   GEN u, r, s, t, X, Y, u2, u3, u2X, z;
      64      194544 :   if (ell_is_inf(x)) return x;
      65      194061 :   X = gel(x,1); Y = gel(x,2);
      66      194061 :   u = gel(ch,1); r = gel(ch,2);
      67      194061 :   s = gel(ch,3); t = gel(ch,4);
      68      194061 :   u2 = F2xq_sqr(u, T); u3 = F2xq_mul(u,u2, T);
      69      194061 :   u2X = F2xq_mul(u2,X, T);
      70      194061 :   z = cgetg(3, t_VEC);
      71      194061 :   gel(z,1) = F2x_add(u2X,r);
      72      194061 :   gel(z,2) = F2x_add(F2xq_mul(u3,Y, T), F2x_add(F2xq_mul(s,u2X, T), t));
      73      194061 :   return z;
      74             : }
      75             : 
      76             : static GEN
      77        3514 : nonzerotrace_F2xq(GEN T)
      78             : {
      79        3514 :   pari_sp av = avma;
      80        3514 :   long n = F2x_degree(T), vs = T[1];
      81             :   GEN a;
      82        3514 :   if (odd(n))
      83        1162 :     return pol1_F2x(vs);
      84             :   do
      85             :   {
      86        4515 :     set_avma(av);
      87        4515 :     a = random_F2x(n, vs);
      88        4515 :   } while (F2xq_trace(a, T)==0);
      89        2352 :   return a;
      90             : }
      91             : 
      92             : void
      93        3514 : F2xq_elltwist(GEN a, GEN a6, GEN T, GEN *pt_a, GEN *pt_a6)
      94             : {
      95        3514 :   pari_sp av = avma;
      96        3514 :   GEN n = nonzerotrace_F2xq(T);
      97        3514 :   if (typ(a)==t_VECSMALL)
      98             :   {
      99        3514 :     *pt_a = gerepileuptoleaf(av, F2x_add(n, a));
     100        3514 :     *pt_a6 = vecsmall_copy(a6);
     101             :   } else
     102             :   {
     103           0 :     GEN a6t = F2x_add(a6, F2xq_mul(n, F2xq_sqr(gel(a,1), T), T));
     104           0 :     *pt_a6 = gerepileuptoleaf(av, a6t);
     105           0 :     *pt_a = vecsmall_copy(a);
     106             :   }
     107        3514 : }
     108             : 
     109             : static GEN
     110     1073275 : F2xqE_dbl_slope(GEN P, GEN a, GEN T, GEN *slope)
     111             : {
     112             :   GEN x, y, Q;
     113     1073275 :   if (ell_is_inf(P)) return ellinf();
     114     1059730 :   x = gel(P,1); y = gel(P,2);
     115     1059730 :   if (typ(a)==t_VECSMALL)
     116             :   {
     117      207515 :     GEN a2 = a;
     118      207515 :     if (!lgpol(gel(P,1))) { *slope = NULL; return ellinf(); }
     119      191128 :     *slope = F2x_add(x, F2xq_div(y, x, T));
     120      191128 :     Q = cgetg(3,t_VEC);
     121      191128 :     gel(Q, 1) = F2x_add(F2xq_sqr(*slope, T), F2x_add(*slope, a2));
     122      191128 :     gel(Q, 2) = F2x_add(F2xq_mul(*slope, F2x_add(x, gel(Q, 1)), T), F2x_add(y, gel(Q, 1)));
     123             :   }
     124             :   else
     125             :   {
     126      852215 :     GEN a3 = gel(a,1), a4 = gel(a,2), a3i = gel(a,3);
     127      852215 :     *slope = F2xq_mul(F2x_add(a4, F2xq_sqr(x, T)), a3i, T);
     128      852215 :     Q = cgetg(3,t_VEC);
     129      852215 :     gel(Q, 1) = F2xq_sqr(*slope, T);
     130      852215 :     gel(Q, 2) = F2x_add(F2xq_mul(*slope, F2x_add(x, gel(Q, 1)), T), F2x_add(y, a3));
     131             :   }
     132     1043343 :   return Q;
     133             : }
     134             : 
     135             : GEN
     136     1054858 : F2xqE_dbl(GEN P, GEN a, GEN T)
     137             : {
     138     1054858 :   pari_sp av = avma;
     139             :   GEN slope;
     140     1054858 :   return gerepileupto(av, F2xqE_dbl_slope(P, a, T,&slope));
     141             : }
     142             : 
     143             : static GEN
     144      354662 : F2xqE_add_slope(GEN P, GEN Q, GEN a, GEN T, GEN *slope)
     145             : {
     146             :   GEN Px, Py, Qx, Qy, R;
     147      354662 :   if (ell_is_inf(P)) { *slope = NULL; return Q; }
     148      353080 :   if (ell_is_inf(Q)) { *slope = NULL; return P; }
     149      353073 :   Px = gel(P,1); Py = gel(P,2);
     150      353073 :   Qx = gel(Q,1); Qy = gel(Q,2);
     151      353073 :   if (F2x_equal(Px, Qx))
     152             :   {
     153      156499 :     if (F2x_equal(Py, Qy))
     154        1582 :       return F2xqE_dbl_slope(P, a, T, slope);
     155             :     else
     156      154917 :       { *slope = NULL; return ellinf(); }
     157             :   }
     158      196574 :   *slope = F2xq_div(F2x_add(Py, Qy), F2x_add(Px, Qx), T);
     159      196574 :   R = cgetg(3,t_VEC);
     160      196574 :   if (typ(a)==t_VECSMALL)
     161             :   {
     162       66437 :     GEN a2 = a;
     163       66437 :     gel(R, 1) = F2x_add(F2x_add(F2x_add(F2x_add(F2xq_sqr(*slope, T), *slope), Px), Qx), a2);
     164       66437 :     gel(R, 2) = F2x_add(F2xq_mul(*slope, F2x_add(Px, gel(R, 1)), T), F2x_add(Py, gel(R, 1)));
     165             :   }
     166             :   else
     167             :   {
     168      130137 :     GEN a3 = gel(a,1);
     169      130137 :     gel(R, 1) = F2x_add(F2x_add(F2xq_sqr(*slope, T), Px), Qx);
     170      130137 :     gel(R, 2) = F2x_add(F2xq_mul(*slope, F2x_add(Px, gel(R, 1)), T), F2x_add(Py, a3));
     171             :   }
     172      196574 :   return R;
     173             : }
     174             : 
     175             : GEN
     176      354627 : F2xqE_add(GEN P, GEN Q, GEN a, GEN T)
     177             : {
     178      354627 :   pari_sp av = avma;
     179             :   GEN slope;
     180      354627 :   return gerepileupto(av, F2xqE_add_slope(P, Q, a, T, &slope));
     181             : }
     182             : 
     183             : static GEN
     184           0 : F2xqE_neg_i(GEN P, GEN a)
     185             : {
     186             :   GEN LHS;
     187           0 :   if (ell_is_inf(P)) return P;
     188           0 :   LHS = typ(a)==t_VECSMALL ? gel(P,1): gel(a,1);
     189           0 :   return mkvec2(gel(P,1), F2x_add(LHS, gel(P,2)));
     190             : }
     191             : 
     192             : GEN
     193          84 : F2xqE_neg(GEN P, GEN a, GEN T)
     194             : {
     195             :   GEN LHS;
     196             :   (void) T;
     197          84 :   if (ell_is_inf(P)) return ellinf();
     198          84 :   LHS = typ(a)==t_VECSMALL ? gel(P,1): gel(a,1);
     199          84 :   return mkvec2(gcopy(gel(P,1)), F2x_add(LHS, gel(P,2)));
     200             : }
     201             : 
     202             : GEN
     203           0 : F2xqE_sub(GEN P, GEN Q, GEN a2, GEN T)
     204             : {
     205           0 :   pari_sp av = avma;
     206             :   GEN slope;
     207           0 :   return gerepileupto(av, F2xqE_add_slope(P, F2xqE_neg_i(Q, a2), a2, T, &slope));
     208             : }
     209             : 
     210             : struct _F2xqE
     211             : {
     212             :   GEN a2, a6;
     213             :   GEN T;
     214             : };
     215             : 
     216             : static GEN
     217     1054858 : _F2xqE_dbl(void *E, GEN P)
     218             : {
     219     1054858 :   struct _F2xqE *ell = (struct _F2xqE *) E;
     220     1054858 :   return F2xqE_dbl(P, ell->a2, ell->T);
     221             : }
     222             : 
     223             : static GEN
     224      354627 : _F2xqE_add(void *E, GEN P, GEN Q)
     225             : {
     226      354627 :   struct _F2xqE *ell=(struct _F2xqE *) E;
     227      354627 :   return F2xqE_add(P, Q, ell->a2, ell->T);
     228             : }
     229             : 
     230             : static GEN
     231      212835 : _F2xqE_mul(void *E, GEN P, GEN n)
     232             : {
     233      212835 :   pari_sp av = avma;
     234      212835 :   struct _F2xqE *e=(struct _F2xqE *) E;
     235      212835 :   long s = signe(n);
     236      212835 :   if (!s || ell_is_inf(P)) return ellinf();
     237      208558 :   if (s<0) P = F2xqE_neg(P, e->a2, e->T);
     238      208558 :   if (is_pm1(n)) return s>0? gcopy(P): P;
     239      203049 :   return gerepilecopy(av, gen_pow_i(P, n, e, &_F2xqE_dbl, &_F2xqE_add));
     240             : }
     241             : 
     242             : GEN
     243      184184 : F2xqE_mul(GEN P, GEN n, GEN a2, GEN T)
     244             : {
     245             :   struct _F2xqE E;
     246      184184 :   E.a2 = a2; E.T = T;
     247      184184 :   return _F2xqE_mul(&E, P, n);
     248             : }
     249             : 
     250             : /* Finds a random nonsingular point on E */
     251             : GEN
     252      181580 : random_F2xqE(GEN a, GEN a6, GEN T)
     253             : {
     254      181580 :   pari_sp ltop = avma;
     255             :   GEN x, y, rhs, u;
     256             :   do
     257             :   {
     258      376271 :     set_avma(ltop);
     259      376271 :     x   = random_F2x(F2x_degree(T),T[1]);
     260      376271 :     if (typ(a) == t_VECSMALL)
     261             :     {
     262       62958 :       GEN a2 = a, x2;
     263       62958 :       if (!lgpol(x))
     264         714 :         { set_avma(ltop); retmkvec2(pol0_Flx(T[1]), F2xq_sqrt(a6,T)); }
     265       62244 :       u = x; x2  = F2xq_sqr(x, T);
     266       62244 :       rhs = F2x_add(F2xq_mul(x2,F2x_add(x,a2),T),a6);
     267       62244 :       rhs = F2xq_div(rhs,x2,T);
     268             :     }
     269             :     else
     270             :     {
     271      313313 :       GEN a3 = gel(a,1), a4 = gel(a,2), a3i = gel(a,3), u2i;
     272      313313 :       u = a3; u2i = F2xq_sqr(a3i,T);
     273      313313 :       rhs = F2x_add(F2xq_mul(x,F2x_add(F2xq_sqr(x,T),a4),T),a6);
     274      313313 :       rhs = F2xq_mul(rhs,u2i,T);
     275             :     }
     276      375557 :   } while (F2xq_trace(rhs,T));
     277      180866 :   y = F2xq_mul(F2xq_Artin_Schreier(rhs, T), u, T);
     278      180866 :   return gerepilecopy(ltop, mkvec2(x, y));
     279             : }
     280             : 
     281             : static GEN
     282       13748 : _F2xqE_rand(void *E)
     283             : {
     284       13748 :   struct _F2xqE *ell=(struct _F2xqE *) E;
     285       13748 :   return random_F2xqE(ell->a2, ell->a6, ell->T);
     286             : }
     287             : 
     288             : static const struct bb_group F2xqE_group={_F2xqE_add,_F2xqE_mul,_F2xqE_rand,hash_GEN,zvV_equal,ell_is_inf, NULL};
     289             : 
     290             : const struct bb_group *
     291           0 : get_F2xqE_group(void ** pt_E, GEN a2, GEN a6, GEN T)
     292             : {
     293           0 :   struct _F2xqE *e = (struct _F2xqE *) stack_malloc(sizeof(struct _F2xqE));
     294           0 :   e->a2 = a2; e->a6 = a6; e->T = T;
     295           0 :   *pt_E = (void *) e;
     296           0 :   return &F2xqE_group;
     297             : }
     298             : 
     299             : GEN
     300         280 : F2xqE_order(GEN z, GEN o, GEN a2, GEN T)
     301             : {
     302         280 :   pari_sp av = avma;
     303             :   struct _F2xqE e;
     304         280 :   e.a2=a2; e.T=T;
     305         280 :   return gerepileuptoint(av, gen_order(z, o, (void*)&e, &F2xqE_group));
     306             : }
     307             : 
     308             : GEN
     309          42 : F2xqE_log(GEN a, GEN b, GEN o, GEN a2, GEN T)
     310             : {
     311          42 :   pari_sp av = avma;
     312             :   struct _F2xqE e;
     313          42 :   e.a2=a2; e.T=T;
     314          42 :   return gerepileuptoint(av, gen_PH_log(a, b, o, (void*)&e, &F2xqE_group));
     315             : }
     316             : 
     317             : /***********************************************************************/
     318             : /**                                                                   **/
     319             : /**                            Pairings                               **/
     320             : /**                                                                   **/
     321             : /***********************************************************************/
     322             : 
     323             : /* Derived from APIP from and by Jerome Milan, 2012 */
     324             : 
     325             : static long
     326       19187 : is_2_torsion(GEN Q, GEN a)
     327             : {
     328       19187 :   return (typ(a)==t_VEC || lgpol(gel(Q, 1))) ? 0: 1;
     329             : }
     330             : 
     331             : static GEN
     332       34916 : F2xqE_vert(GEN P, GEN Q, GEN a, GEN T)
     333             : {
     334       34916 :   long vT = T[1];
     335       34916 :   if (ell_is_inf(P))
     336        9023 :     return pol1_F2x(T[1]);
     337       25893 :   if (!F2x_equal(gel(Q, 1), gel(P, 1)))
     338       24255 :     return F2x_add(gel(Q, 1), gel(P, 1));
     339        1638 :   if (is_2_torsion(Q, a))
     340           0 :     return F2xq_inv(gel(Q,2), T);
     341        1638 :   return pol1_F2x(vT);
     342             : }
     343             : 
     344             : static GEN
     345       16870 : F2xqE_Miller_line(GEN R, GEN Q, GEN slope, GEN a, GEN T)
     346             : {
     347       16870 :   long vT = T[1];
     348       16870 :   GEN x = gel(Q, 1), y = gel(Q, 2);
     349       16870 :   GEN tmp1 = F2x_add(x, gel(R, 1));
     350       16870 :   GEN tmp2 = F2x_add(F2xq_mul(tmp1, slope, T), gel(R, 2));
     351             :   GEN s1, s2, ix;
     352       16870 :   if (!F2x_equal(y, tmp2))
     353       16156 :     return F2x_add(y, tmp2);
     354         714 :   if (is_2_torsion(Q, a)) return pol1_F2x(vT);
     355         714 :   if (typ(a)==t_VEC)
     356             :   {
     357         700 :     GEN a4 = gel(a,2), a3i = gel(a,3);
     358         700 :     s1 = F2xq_mul(F2x_add(a4, F2xq_sqr(x, T)), a3i, T);
     359         700 :     if (!F2x_equal(s1, slope))
     360         350 :       return F2x_add(s1, slope);
     361         350 :     s2 = F2xq_mul(F2x_add(x, F2xq_sqr(s1, T)), a3i, T);
     362         350 :     if (lgpol(s2)) return s2;
     363           0 :     return zv_copy(a3i);
     364             :   } else
     365             :   {
     366          14 :     GEN a2 = a ;
     367          14 :     ix = F2xq_inv(x, T);
     368          14 :     s1 = F2x_add(x, F2xq_mul(y, ix, T));
     369          14 :     if (!F2x_equal(s1, slope))
     370           7 :       return F2x_add(s1, slope);
     371           7 :     s2 =F2x_add(a2, F2x_add(F2xq_sqr(s1,T), s1));
     372           7 :     if (!F2x_equal(s2, x))
     373           7 :       return  F2x_add(pol1_F2x(vT), F2xq_mul(s2, ix, T));
     374           0 :     return ix;
     375             :   }
     376             : }
     377             : 
     378             : /* Computes the equation of the line tangent to R and returns its
     379             :    evaluation at the point Q. Also doubles the point R.
     380             :  */
     381             : 
     382             : static GEN
     383       16835 : F2xqE_tangent_update(GEN R, GEN Q, GEN a2, GEN T, GEN *pt_R)
     384             : {
     385       16835 :   if (ell_is_inf(R))
     386             :   {
     387           0 :     *pt_R = ellinf();
     388           0 :     return pol1_F2x(T[1]);
     389             :   }
     390       16835 :   else if (is_2_torsion(R, a2))
     391             :   {
     392           0 :     *pt_R = ellinf();
     393           0 :     return F2xqE_vert(R, Q, a2, T);
     394             :   } else {
     395             :     GEN slope;
     396       16835 :     *pt_R = F2xqE_dbl_slope(R, a2, T, &slope);
     397       16835 :     return F2xqE_Miller_line(R, Q, slope, a2, T);
     398             :   }
     399             : }
     400             : 
     401             : /* Computes the equation of the line through R and P, and returns its
     402             :    evaluation at the point Q. Also adds P to the point R.
     403             :  */
     404             : 
     405             : static GEN
     406        9058 : F2xqE_chord_update(GEN R, GEN P, GEN Q, GEN a2, GEN T, GEN *pt_R)
     407             : {
     408        9058 :   if (ell_is_inf(R))
     409             :   {
     410           0 :     *pt_R = gcopy(P);
     411           0 :     return F2xqE_vert(P, Q, a2, T);
     412             :   }
     413        9058 :   else if (ell_is_inf(P))
     414             :   {
     415           0 :     *pt_R = gcopy(R);
     416           0 :     return F2xqE_vert(R, Q, a2, T);
     417             :   }
     418        9058 :   else if (F2x_equal(gel(P, 1), gel(R, 1)))
     419             :   {
     420        9023 :     if (F2x_equal(gel(P, 2), gel(R, 2)))
     421           0 :       return F2xqE_tangent_update(R, Q, a2, T, pt_R);
     422             :     else
     423             :     {
     424        9023 :       *pt_R = ellinf();
     425        9023 :       return F2xqE_vert(R, Q, a2, T);
     426             :     }
     427             :   } else {
     428             :     GEN slope;
     429          35 :     *pt_R = F2xqE_add_slope(P, R, a2, T, &slope);
     430          35 :     return F2xqE_Miller_line(R, Q, slope, a2, T);
     431             :   }
     432             : }
     433             : 
     434             : struct _F2xqE_miller { GEN T, a2, P; };
     435             : 
     436             : static GEN
     437       16835 : F2xqE_Miller_dbl(void* E, GEN d)
     438             : {
     439       16835 :   struct _F2xqE_miller *m = (struct _F2xqE_miller *)E;
     440       16835 :   GEN T = m->T, a2 = m->a2, P = m->P;
     441       16835 :   GEN v, line, point = gel(d,3);
     442       16835 :   GEN N = F2xq_sqr(gel(d,1), T);
     443       16835 :   GEN D = F2xq_sqr(gel(d,2), T);
     444       16835 :   line = F2xqE_tangent_update(point, P, a2, T, &point);
     445       16835 :   N = F2xq_mul(N, line, T);
     446       16835 :   v = F2xqE_vert(point, P, a2, T);
     447       16835 :   D = F2xq_mul(D, v, T); return mkvec3(N, D, point);
     448             : }
     449             : static GEN
     450        9058 : F2xqE_Miller_add(void* E, GEN va, GEN vb)
     451             : {
     452        9058 :   struct _F2xqE_miller *m = (struct _F2xqE_miller *)E;
     453        9058 :   GEN T = m->T, a2 = m->a2, P = m->P;
     454             :   GEN v, line, point;
     455        9058 :   GEN na = gel(va,1), da = gel(va,2), pa = gel(va,3);
     456        9058 :   GEN nb = gel(vb,1), db = gel(vb,2), pb = gel(vb,3);
     457        9058 :   GEN N = F2xq_mul(na, nb, T);
     458        9058 :   GEN D = F2xq_mul(da, db, T);
     459        9058 :   line = F2xqE_chord_update(pa, pb, P, a2, T, &point);
     460        9058 :   N  = F2xq_mul(N, line, T);
     461        9058 :   v = F2xqE_vert(point, P, a2, T);
     462        9058 :   D = F2xq_mul(D, v, T); return mkvec3(N, D, point);
     463             : }
     464             : /* Returns the Miller function f_{m, Q} evaluated at the point P using
     465             :  * the standard Miller algorithm. */
     466             : static GEN
     467        9058 : F2xqE_Miller(GEN Q, GEN P, GEN m, GEN a2, GEN T)
     468             : {
     469        9058 :   pari_sp av = avma;
     470             :   struct _F2xqE_miller d;
     471             :   GEN v, N, D, g1;
     472             : 
     473        9058 :   d.a2 = a2; d.T = T; d.P = P;
     474        9058 :   g1 = pol1_F2x(T[1]);
     475        9058 :   v = gen_pow_i(mkvec3(g1,g1,Q), m, (void*)&d, F2xqE_Miller_dbl, F2xqE_Miller_add);
     476        9058 :   N = gel(v,1); D = gel(v,2);
     477        9058 :   return gerepileupto(av, F2xq_div(N, D, T));
     478             : }
     479             : 
     480             : GEN
     481        5341 : F2xqE_weilpairing(GEN P, GEN Q, GEN m, GEN a2, GEN T)
     482             : {
     483        5341 :   pari_sp av = avma;
     484             :   GEN N, D;
     485        5341 :   if (ell_is_inf(P) || ell_is_inf(Q)
     486        4802 :     || (F2x_equal(gel(P,1),gel(Q,1)) && F2x_equal(gel(P,2),gel(Q,2))))
     487         826 :     return pol1_F2x(T[1]);
     488        4515 :   N    = F2xqE_Miller(P, Q, m, a2, T);
     489        4515 :   D  = F2xqE_Miller(Q, P, m, a2, T);
     490        4515 :   return gerepileupto(av, F2xq_div(N, D, T));
     491             : }
     492             : 
     493             : GEN
     494          28 : F2xqE_tatepairing(GEN P, GEN Q, GEN m, GEN a2, GEN T)
     495             : {
     496          28 :   if (ell_is_inf(P) || ell_is_inf(Q))
     497           0 :     return pol1_F2x(T[1]);
     498          28 :   return F2xqE_Miller(P, Q, m, a2, T);
     499             : }
     500             : 
     501             : /***********************************************************************/
     502             : /**                                                                   **/
     503             : /**                          Point counting                           **/
     504             : /**                                                                   **/
     505             : /***********************************************************************/
     506             : 
     507             : static GEN
     508       67609 : Z2x_rshift(GEN y, long x)
     509             : {
     510             :   GEN z;
     511             :   long i, l;
     512       67609 :   if (!x) return pol0_Flx(y[1]);
     513       67609 :   z = cgetg_copy(y, &l); z[1] = y[1];
     514     7509761 :   for(i=2; i<l; i++) z[i] = y[i]>>x;
     515       67606 :   return Flx_renormalize(z, l);
     516             : }
     517             : 
     518             : /* Solve the linear equation approximation in the Newton algorithm */
     519             : 
     520             : static GEN
     521      168147 : 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))
     522             : {
     523      168147 :   pari_sp av = avma;
     524             :   long N2, M;
     525             :   GEN VN2, V2, VM, bil;
     526      168147 :   ulong q = 1UL<<N;
     527      168147 :   if (N == 1) return invl(E, V);
     528       67582 :   V = Flx_red(V, q);
     529       67609 :   N2 = (N + 1)>>1; M = N - N2;
     530       67609 :   F = FlxT_red(F, q);
     531       67622 :   VN2 = gen_Z2x_Dixon(F, V, N2, E, lin, invl);
     532       67626 :   bil = lin(E, F, VN2, N);
     533       67623 :   V2 = Z2x_rshift(Flx_sub(V, bil, q), N2);
     534       67622 :   VM = gen_Z2x_Dixon(F, V2, M, E, lin, invl);
     535       67623 :   return gerepileupto(av, Flx_add(VN2, Flx_Fl_mul(VM, 1UL<<N2, q), q));
     536             : }
     537             : 
     538             : /* Solve F(X) = V mod 2^N
     539             :    F(Xn) = V [mod 2^n]
     540             :    Vm = (V-F(Xn))/(2^n)
     541             :    F(Xm) = Vm
     542             :    X = Xn + 2^n*Xm
     543             : */
     544             : 
     545             : static GEN
     546       32971 : gen_Z2X_Dixon(GEN F, GEN V, long N, void *E,
     547             :                      GEN lin(void *E, GEN F, GEN d, long N),
     548             :                      GEN lins(void *E, GEN F, GEN d, long N),
     549             :                      GEN invls(void *E, GEN d))
     550             : {
     551       32971 :   pari_sp av = avma;
     552             :   long n, m;
     553             :   GEN Xn, Xm, FXn, Vm;
     554       32971 :   if (N<BITS_IN_LONG)
     555             :   {
     556       32951 :     ulong q = 1UL<<N;
     557       32951 :     return Flx_to_ZX(gen_Z2x_Dixon(ZXT_to_FlxT(F,q), ZX_to_Flx(V,q),N,E,lins,invls));
     558             :   }
     559          20 :   V = ZX_remi2n(V, N);
     560          20 :   n = (N + 1)>>1; m = N - n;
     561          20 :   F = ZXT_remi2n(F, N);
     562          20 :   Xn = gen_Z2X_Dixon(F, V, n, E, lin, lins, invls);
     563          20 :   FXn = lin(E, F, Xn, N);
     564          20 :   Vm = ZX_shifti(ZX_sub(V, FXn), -n);
     565          20 :   Xm = gen_Z2X_Dixon(F, Vm, m, E, lin, lins, invls);
     566          20 :   return gerepileupto(av, ZX_remi2n(ZX_add(Xn, ZX_shifti(Xm, n)), N));
     567             : }
     568             : 
     569             : /* H -> H mod 2*/
     570             : 
     571       50025 : static GEN _can_invls(void *E, GEN V) {(void) E; return V; }
     572             : 
     573             : /* H -> H-(f0*H0-f1*H1) */
     574             : 
     575          10 : static GEN _can_lin(void *E, GEN F, GEN V, long N)
     576             : {
     577          10 :   pari_sp av=avma;
     578             :   GEN d0, d1, z;
     579             :   (void) E;
     580          10 :   RgX_even_odd(V, &d0, &d1);
     581          10 :   z =  ZX_sub(V, ZX_sub(ZX_mul(gel(F,1), d0), ZX_mul(gel(F,2), d1)));
     582          10 :   return gerepileupto(av, ZX_remi2n(z, N));
     583             : }
     584             : 
     585       33677 : static GEN _can_lins(void *E, GEN F, GEN V, long N)
     586             : {
     587       33677 :   GEN D=Flx_splitting(V, 2), z;
     588       33672 :   ulong q = 1UL<<N;
     589             :   (void) E;
     590       33672 :   z = Flx_sub(Flx_mul(gel(F,1), gel(D,1), q), Flx_mul(gel(F,2), gel(D,2), q), q);
     591       33679 :   return Flx_sub(V, z, q);
     592             : }
     593             : 
     594             : /* P -> P-(P0^2-X*P1^2) */
     595             : 
     596             : static GEN
     597       16341 : _can_iter(void *E, GEN f2, GEN q)
     598             : {
     599             :   GEN f0, f1, z;
     600             :   (void) E;
     601       16341 :   RgX_even_odd(f2, &f0, &f1);
     602       16342 :   z = ZX_add(ZX_sub(f2, FpX_sqr(f0, q)), RgX_shift_shallow(FpX_sqr(f1, q), 1));
     603       16342 :   return mkvec3(z,f0,f1);
     604             : }
     605             : 
     606             : /* H -> H-(2*P0*H0-2*X*P1*H1) */
     607             : 
     608             : static GEN
     609       16343 : _can_invd(void *E, GEN V, GEN v, GEN q, long M)
     610             : {
     611             :   GEN F;
     612             :   (void)E; (void)q;
     613       16343 :   F = mkvec2(ZX_shifti(gel(v,2),1), ZX_shifti(RgX_shift_shallow(gel(v,3),1),1));
     614       16343 :   return gen_Z2X_Dixon(F, V, M, NULL, _can_lin, _can_lins, _can_invls);
     615             : }
     616             : 
     617             : /* Lift P to Q such that Q(x^2)=Q(x)*Q(-x) mod 2^n
     618             :    if Q = Q0(X^2)+X*Q1(X^2), solve Q(X^2) = Q0^2-X*Q1^2
     619             : */
     620             : GEN
     621        7177 : F2x_Teichmuller(GEN P, long n)
     622        7177 : { return gen_ZpX_Newton(F2x_to_ZX(P),gen_2, n, NULL, _can_iter, _can_invd); }
     623             : 
     624             : static GEN
     625       16597 : Z2XQ_frob(GEN x, GEN T, GEN q)
     626             : {
     627       16597 :   return FpX_rem(RgX_inflate(x, 2), T, q);
     628             : }
     629             : 
     630             : static GEN
     631       33949 : Z2xq_frob(GEN x, GEN T, ulong q)
     632             : {
     633       33949 :   return Flx_rem(Flx_inflate(x, 2), T, q);
     634             : }
     635             : 
     636             : struct _frob_lift
     637             : {
     638             :   GEN T, sqx;
     639             : };
     640             : 
     641             : /* H -> S^-1(H) mod 2 */
     642             : 
     643       50546 : static GEN _frob_invls(void *E, GEN V)
     644             : {
     645       50546 :   struct _frob_lift *F = (struct _frob_lift*) E;
     646       50546 :   GEN sqx = F->sqx;
     647       50546 :   return F2x_to_Flx(F2xq_sqrt_fast(Flx_to_F2x(V), gel(sqx,1), gel(sqx,2)));
     648             : }
     649             : 
     650             : /* H -> f1*S(H) + f2*H */
     651             : 
     652          10 : static GEN _frob_lin(void *E, GEN F, GEN x2, long N)
     653             : {
     654          10 :   GEN T = gel(F,3);
     655          10 :   GEN q = int2n(N);
     656          10 :   GEN y2  = Z2XQ_frob(x2, T, q);
     657          10 :   GEN lin = ZX_add(ZX_mul(gel(F,1), y2), ZX_mul(gel(F,2), x2));
     658             :   (void) E;
     659          10 :   return FpX_rem(ZX_remi2n(lin, N), T, q);
     660             : }
     661             : 
     662       33949 : static GEN _frob_lins(void *E, GEN F, GEN x2, long N)
     663             : {
     664       33949 :   GEN T = gel(F,3);
     665       33949 :   ulong q = 1UL<<N;
     666       33949 :   GEN y2  = Z2xq_frob(x2, T, q);
     667       33949 :   GEN lin = Flx_add(Flx_mul(gel(F,1), y2,q), Flx_mul(gel(F,2), x2,q),q);
     668             :   (void) E;
     669       33947 :   return Flx_rem(lin, T, q);
     670             : }
     671             : 
     672             : /* X -> P(X,S(X)) */
     673             : 
     674             : static GEN
     675       16588 : _lift_iter(void *E, GEN x2, GEN q)
     676             : {
     677       16588 :   struct _frob_lift *F = (struct _frob_lift*) E;
     678       16588 :   long N = expi(q);
     679       16588 :   GEN TN = ZXT_remi2n(F->T, N);
     680       16587 :   GEN y2 = Z2XQ_frob(x2, TN, q);
     681       16588 :   GEN x2y2 = FpX_rem(ZX_remi2n(ZX_mul(x2, y2), N), TN, q);
     682       16587 :   GEN s = ZX_add(ZX_add(x2, ZX_shifti(y2, 1)), ZX_shifti(x2y2, 3));
     683       16588 :   GEN V = ZX_add(ZX_add(ZX_sqr(s), y2), ZX_shifti(x2y2, 2));
     684       16588 :   return mkvec4(FpX_rem(ZX_remi2n(V, N), TN, q),x2,y2,s);
     685             : }
     686             : 
     687             : /* H -> Dx*H+Dy*S(H) */
     688             : 
     689             : static GEN
     690       16586 : _lift_invd(void *E, GEN V, GEN v, GEN qM, long M)
     691             : {
     692       16586 :   struct _frob_lift *F = (struct _frob_lift*) E;
     693       16586 :   GEN TM = ZXT_remi2n(F->T, M);
     694       16588 :   GEN x2 = gel(v,2), y2 = gel(v,3), s = gel(v,4), r;
     695       16588 :   GEN Dx = ZX_add(ZX_mul(ZX_Z_add(ZX_shifti(y2, 4), gen_2), s),
     696             :                          ZX_shifti(y2, 2));
     697       16588 :   GEN Dy = ZX_add(ZX_Z_add(ZX_mul(ZX_Z_add(ZX_shifti(x2, 4), utoi(4)), s),
     698             :                            gen_1), ZX_shifti(x2, 2));
     699       16588 :   Dx = FpX_rem(ZX_remi2n(Dx, M), TM, qM);
     700       16588 :   Dy = FpX_rem(ZX_remi2n(Dy, M), TM, qM);
     701       16588 :   r = mkvec3(Dy, Dx, TM);
     702       16588 :   return gen_Z2X_Dixon(r, V, M, E, _frob_lin, _frob_lins, _frob_invls);
     703             : }
     704             : 
     705             : /*
     706             :   Let P(X,Y)=(X+2*Y+8*X*Y)^2+Y+4*X*Y
     707             :   Solve   P(x,S(x))=0 [mod 2^n,T]
     708             :   assuming  x = x0    [mod 2,T]
     709             : 
     710             :   we set s = X+2*Y+8*X*Y, P = s^2+Y+4*X*Y
     711             :   Dx = dP/dx = (16*s+4)*x+(4*s+1)
     712             :   Dy = dP/dy = (16*y+2)*s+4*y
     713             : */
     714             : 
     715             : static GEN
     716        7408 : solve_AGM_eqn(GEN x0, long n, GEN T, GEN sqx)
     717             : {
     718             :   struct _frob_lift F;
     719        7408 :   F.T=T; F.sqx=sqx;
     720        7408 :   return gen_ZpX_Newton(x0, gen_2, n, &F, _lift_iter, _lift_invd);
     721             : }
     722             : 
     723             : static GEN
     724         238 : Z2XQ_invnorm_pcyc(GEN a, GEN T, long e)
     725             : {
     726         238 :   GEN q = int2n(e);
     727         238 :   GEN z = ZpXQ_norm_pcyc(a, T, q, gen_2);
     728         238 :   return Zp_inv(z, gen_2, e);
     729             : }
     730             : 
     731             : /* Assume a = 1 [4] */
     732             : static GEN
     733        7170 : Z2XQ_invnorm(GEN a, GEN T, long e)
     734             : {
     735             :   pari_timer ti;
     736        7170 :   GEN pe = int2n(e), s;
     737        7170 :   if (degpol(a)==0)
     738          56 :     return Zp_inv(Fp_powu(gel(a,2), get_FpX_degree(T), pe), gen_2, e);
     739        7114 :   if (DEBUGLEVEL>=3) timer_start(&ti);
     740        7114 :   s = ZpXQ_log(a, T, gen_2, e);
     741        7114 :   if (DEBUGLEVEL>=3) timer_printf(&ti,"Z2XQ_log");
     742        7114 :   s = Fp_neg(FpXQ_trace(s, T, pe), pe);
     743        7114 :   if (DEBUGLEVEL>=3) timer_printf(&ti,"FpXQ_trace");
     744        7114 :   s = modii(gel(Qp_exp(cvtop(s, gen_2, e-2)),4),pe);
     745        7114 :   if (DEBUGLEVEL>=3) timer_printf(&ti,"Qp_exp");
     746        7114 :   return s;
     747             : }
     748             : 
     749             : /* Assume a2==0, so 4|E(F_p): if t^4 = a6 then (t,t^2) is of order 4
     750             :    8|E(F_p) <=> trace(a6)==0
     751             :  */
     752             : 
     753             : static GEN
     754        7646 : F2xq_elltrace_Harley(GEN a6, GEN T2)
     755             : {
     756        7646 :   pari_sp ltop = avma;
     757             :   pari_timer ti;
     758             :   GEN T, sqx;
     759             :   GEN x, x2, t;
     760        7646 :   long n = F2x_degree(T2), N = ((n + 1)>>1) + 2;
     761             :   long ispcyc;
     762        7646 :   if (n==1) return gen_m1;
     763        7562 :   if (n==2) return F2x_degree(a6) ? gen_1 : stoi(-3);
     764        7611 :   if (n==3) return F2x_degree(a6) ? (F2xq_trace(a6,T2) ?  stoi(-3): gen_1)
     765         203 :                                   : stoi(5);
     766        7408 :   timer_start(&ti);
     767        7408 :   sqx = mkvec2(F2xq_sqrt(polx_F2x(T2[1]),T2), T2);
     768        7408 :   if (DEBUGLEVEL>1) timer_printf(&ti,"Sqrtx");
     769        7408 :   ispcyc = zx_is_pcyc(F2x_to_Flx(T2));
     770        7408 :   T = ispcyc? F2x_to_ZX(T2): F2x_Teichmuller(T2, N-2);
     771        7408 :   if (DEBUGLEVEL>1) timer_printf(&ti,"Teich");
     772        7408 :   T = FpX_get_red(T, int2n(N));
     773        7408 :   if (DEBUGLEVEL>1) timer_printf(&ti,"Barrett");
     774        7408 :   x = solve_AGM_eqn(F2x_to_ZX(a6), N-2, T, sqx);
     775        7408 :   if (DEBUGLEVEL>1) timer_printf(&ti,"Lift");
     776        7408 :   x2 = ZX_Z_add_shallow(ZX_shifti(x,2), gen_1);
     777        7408 :   t = (ispcyc? Z2XQ_invnorm_pcyc: Z2XQ_invnorm)(x2, T, N);
     778        7408 :   if (DEBUGLEVEL>1) timer_printf(&ti,"Norm");
     779        7408 :   if (cmpii(sqri(t), int2n(n + 2)) > 0)
     780        3495 :     t = subii(t, int2n(N));
     781        7408 :   return gerepileuptoint(ltop, t);
     782             : }
     783             : 
     784             : static GEN
     785       23737 : get_v(GEN u, GEN a, GEN T)
     786             : {
     787       23737 :   GEN a4 = gel(a,2), a3i = gel(a,3);
     788       23737 :   GEN ui2 = F2xq_mul(u, a3i, T), ui4 = F2xq_sqr(ui2, T);
     789       23737 :   return F2xq_mul(a4, ui4, T);
     790             : }
     791             : 
     792             : static GEN
     793       10493 : get_r(GEN w, GEN u, GEN T)
     794             : {
     795       10493 :   return F2xq_sqr(F2xq_mul(F2xq_Artin_Schreier(w, T), u, T), T);
     796             : }
     797             : 
     798             : static GEN
     799       37695 : F2xq_elltracej(GEN a, GEN a6, GEN T, GEN q, long n)
     800             : {
     801       37695 :   GEN a3 = gel(a,1), a4 = gel(a,2), a3i = gel(a,3);
     802             :   GEN r, pi, rhs;
     803       37695 :   long t, s, m = n >> 1;
     804       37695 :   if (odd(n))
     805             :   {
     806             :     GEN u, v, w;
     807       16856 :     u = F2xq_pow(a3,diviuexact(subiu(shifti(q,1), 1), 3),T);
     808       16856 :     v = get_v(u, a, T);
     809       16856 :     if (F2xq_trace(v, T)==0) return gen_0;
     810        8757 :     w = F2xq_Artin_Schreier(F2x_1_add(v), T);
     811        8757 :     if (F2xq_trace(w, T)) w = F2x_1_add(w);
     812        8757 :     r = get_r(w, u, T);
     813        8757 :     pi = int2n(m+1);
     814        8757 :     s = (((m+3)&3L) <= 1) ? -1: 1;
     815             :   }
     816             :   else
     817             :   {
     818       20839 :     if (F2x_degree(F2xq_pow(a3,diviuexact(subiu(q, 1), 3),T))==0)
     819             :     {
     820             :       GEN u, v, w;
     821        6881 :       u = F2xq_sqrtn(a3, utoi(3), T, NULL);
     822        6881 :       v = get_v(u, a, T);
     823        6881 :       if (F2xq_trace(v, T)==1) return gen_0;
     824        3507 :       w = F2xq_Artin_Schreier(v, T);
     825        3507 :       if (F2xq_trace(w, T)==1) return gen_0;
     826        1736 :       r = get_r(w, u, T);
     827        1736 :       pi = int2n(m+1);
     828        1736 :       s = odd(m+1) ? -1: 1;
     829             :     }
     830             :     else
     831             :     {
     832       13958 :       long sv = T[1];
     833       13958 :       GEN P = mkpoln(5, pol1_F2x(sv), pol0_F2x(sv), pol0_F2x(sv), a3, a4);
     834       13958 :       r = F2xq_sqr(gel(F2xqX_roots(P,T), 1), T);
     835       13958 :       pi = int2n(m);
     836       13958 :       s = odd(m) ? -1: 1;
     837             :     }
     838             :   }
     839       24451 :   rhs = F2x_add(F2xq_mul(F2x_add(F2xq_sqr(r, T), a4), r, T), a6);
     840       24451 :   t = F2xq_trace(F2xq_mul(rhs, F2xq_sqr(a3i, T), T), T);
     841       24451 :   return (t==0)^(s==1)? pi: negi(pi);
     842             : }
     843             : 
     844             : GEN
     845       45495 : F2xq_ellcard(GEN a, GEN a6, GEN T)
     846             : {
     847       45495 :   pari_sp av = avma;
     848       45495 :   long n = F2x_degree(T);
     849             :   GEN c;
     850       45495 :   if (typ(a)==t_VECSMALL)
     851             :   {
     852        7646 :     GEN t = F2xq_elltrace_Harley(a6, T);
     853        7646 :     c = addii(int2u(n), F2xq_trace(a,T) ? addui(1,t): subui(1,t));
     854       37849 :   } else if (n==1)
     855             :   {
     856         154 :     long a4i = lgpol(gel(a,2)), a6i = lgpol(a6);
     857         154 :     return utoi(a4i? (a6i? 1: 5): 3);
     858             :   }
     859             :   else
     860             :   {
     861       37695 :     GEN q = int2u(n);
     862       37695 :     c = subii(addiu(q,1), F2xq_elltracej(a, a6, T, q, n));
     863             :   }
     864       45341 :   return gerepileuptoint(av, c);
     865             : }
     866             : 
     867             : /***********************************************************************/
     868             : /**                                                                   **/
     869             : /**                          Group structure                          **/
     870             : /**                                                                   **/
     871             : /***********************************************************************/
     872             : 
     873             : static GEN
     874         371 : _F2xqE_pairorder(void *E, GEN P, GEN Q, GEN m, GEN F)
     875             : {
     876         371 :   struct _F2xqE *e = (struct _F2xqE *) E;
     877         371 :   return  F2xq_order(F2xqE_weilpairing(P,Q,m,e->a2,e->T), F, e->T);
     878             : }
     879             : 
     880             : GEN
     881        3808 : F2xq_ellgroup(GEN a2, GEN a6, GEN N, GEN T, GEN *pt_m)
     882             : {
     883             :   struct _F2xqE e;
     884        3808 :   GEN q = int2u(F2x_degree(T));
     885        3808 :   e.a2=a2; e.a6=a6; e.T=T;
     886        3808 :   return gen_ellgroup(N, subiu(q,1), pt_m, (void*)&e, &F2xqE_group,
     887             :                                                       _F2xqE_pairorder);
     888             : }
     889             : 
     890             : GEN
     891        3738 : F2xq_ellgens(GEN a2, GEN a6, GEN ch, GEN D, GEN m, GEN T)
     892             : {
     893             :   GEN P;
     894        3738 :   pari_sp av = avma;
     895             :   struct _F2xqE e;
     896        3738 :   e.a2=a2; e.a6=a6; e.T=T;
     897        3738 :   switch(lg(D)-1)
     898             :   {
     899          28 :   case 0:
     900          28 :     return cgetg(1,t_VEC);
     901        3598 :   case 1:
     902        3598 :     P = gen_gener(gel(D,1), (void*)&e, &F2xqE_group);
     903        3598 :     P = mkvec(F2xqE_changepoint(P, ch, T));
     904        3598 :     break;
     905         112 :   default:
     906         112 :     P = gen_ellgens(gel(D,1), gel(D,2), m, (void*)&e, &F2xqE_group,
     907             :                                                       _F2xqE_pairorder);
     908         112 :     gel(P,1) = F2xqE_changepoint(gel(P,1), ch, T);
     909         112 :     gel(P,2) = F2xqE_changepoint(gel(P,2), ch, T);
     910         112 :     break;
     911             :   }
     912        3710 :   return gerepilecopy(av, P);
     913             : }

Generated by: LCOV version 1.14