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 - Fle.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.12.1 lcov report (development 25406-bf255ab81b) Lines: 301 358 84.1 %
Date: 2020-06-04 05:59:24 Functions: 40 52 76.9 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Copyright (C) 2014  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 Fl */
      18             : 
      19             : /***********************************************************************/
      20             : /**                                                                   **/
      21             : /**                              Flj                                  **/
      22             : /**                                                                   **/
      23             : /***********************************************************************/
      24             : 
      25             : /* Arithmetic is implemented using Jacobian coordinates, representing
      26             :  * a projective point (x : y : z) on E by [z*x , z^2*y , z].  This is
      27             :  * probably not the fastest representation available for the given
      28             :  * problem, but they're easy to implement and up to 60% faster than
      29             :  * the school-book method. */
      30             : 
      31             : /* Cost: 1M + 8S + 1*a + 10add + 1*8 + 2*2 + 1*3.
      32             :  * http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-2007-bl */
      33             : INLINE void
      34    20726983 : Flj_dbl_indir_pre(GEN P, GEN Q, ulong a4, ulong p, ulong pi)
      35             : {
      36             :   ulong X1, Y1, Z1;
      37             :   ulong XX, YY, YYYY, ZZ, S, M, T;
      38             : 
      39    20726983 :   X1 = P[1]; Y1 = P[2]; Z1 = P[3];
      40             : 
      41    20726983 :   if (Z1 == 0) { Q[1] = X1; Q[2] = Y1; Q[3] = Z1; return; }
      42             : 
      43    20586496 :   XX = Fl_sqr_pre(X1, p, pi);
      44    20589017 :   YY = Fl_sqr_pre(Y1, p, pi);
      45    20585108 :   YYYY = Fl_sqr_pre(YY, p, pi);
      46    20584575 :   ZZ = Fl_sqr_pre(Z1, p, pi);
      47    20583950 :   S = Fl_double(Fl_sub(Fl_sqr_pre(Fl_add(X1, YY, p), p, pi),
      48             :                        Fl_add(XX, YYYY, p), p), p);
      49    20581891 :   M = Fl_addmul_pre(Fl_triple(XX, p), a4, Fl_sqr_pre(ZZ, p, pi), p, pi);
      50    20588160 :   T = Fl_sub(Fl_sqr_pre(M, p, pi), Fl_double(S, p), p);
      51    20584913 :   Q[1] = T;
      52    20584913 :   Q[2] = Fl_sub(Fl_mul_pre(M, Fl_sub(S, T, p), p, pi),
      53             :                 Fl_double(Fl_double(Fl_double(YYYY, p), p), p), p);
      54    20581314 :   Q[3] = Fl_sub(Fl_sqr_pre(Fl_add(Y1, Z1, p), p, pi),
      55             :                 Fl_add(YY, ZZ, p), p);
      56             : }
      57             : 
      58             : INLINE void
      59    17569921 : Flj_dbl_pre_inplace(GEN P, ulong a4, ulong p, ulong pi)
      60             : {
      61    17569921 :   Flj_dbl_indir_pre(P, P, a4, p, pi);
      62    17569451 : }
      63             : 
      64             : GEN
      65     3155009 : Flj_dbl_pre(GEN P, ulong a4, ulong p, ulong pi)
      66             : {
      67     3155009 :   GEN Q = cgetg(4, t_VECSMALL);
      68     3154972 :   Flj_dbl_indir_pre(P, Q, a4, p, pi);
      69     3154714 :   return Q;
      70             : }
      71             : 
      72             : /* Cost: 11M + 5S + 9add + 4*2.
      73             :  * http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#addition-add-2007-bl */
      74             : INLINE void
      75     6218680 : Flj_add_indir_pre(GEN P, GEN Q, GEN R, ulong a4, ulong p, ulong pi)
      76             : {
      77             :   ulong X1, Y1, Z1, X2, Y2, Z2;
      78             :   ulong Z1Z1, Z2Z2, U1, U2, S1, S2, H, I, J, r, V, W;
      79     6218680 :   X1 = P[1]; Y1 = P[2]; Z1 = P[3];
      80     6218680 :   X2 = Q[1]; Y2 = Q[2]; Z2 = Q[3];
      81             : 
      82     6218680 :   if (Z2 == 0) { R[1] = X1; R[2] = Y1; R[3] = Z1; return; }
      83     6218487 :   if (Z1 == 0) { R[1] = X2; R[2] = Y2; R[3] = Z2; return; }
      84             : 
      85     6207552 :   Z1Z1 = Fl_sqr_pre(Z1, p, pi);
      86     6207919 :   Z2Z2 = Fl_sqr_pre(Z2, p, pi);
      87     6207726 :   U1 = Fl_mul_pre(X1, Z2Z2, p, pi);
      88     6207692 :   U2 = Fl_mul_pre(X2, Z1Z1, p, pi);
      89     6207757 :   S1 = Fl_mul_pre(Y1, Fl_mul_pre(Z2, Z2Z2, p, pi), p, pi);
      90     6207755 :   S2 = Fl_mul_pre(Y2, Fl_mul_pre(Z1, Z1Z1, p, pi), p, pi);
      91     6207793 :   H = Fl_sub(U2, U1, p);
      92     6207610 :   r = Fl_double(Fl_sub(S2, S1, p), p);
      93             : 
      94     6207752 :   if (H == 0) {
      95      471827 :     if (r == 0) Flj_dbl_indir_pre(P, R, a4, p, pi); /* P = Q */
      96      468966 :     else { R[1] = R[2] = 1; R[3] = 0; } /* P = -Q */
      97      471827 :     return;
      98             :   }
      99     5735925 :   I = Fl_sqr_pre(Fl_double(H, p), p, pi);
     100     5736252 :   J = Fl_mul_pre(H, I, p, pi);
     101     5736143 :   V = Fl_mul_pre(U1, I, p, pi);
     102     5736131 :   W = Fl_sub(Fl_sqr_pre(r, p, pi), Fl_add(J, Fl_double(V, p), p), p);
     103     5736048 :   R[1] = W;
     104     5736048 :   R[2] = Fl_sub(Fl_mul_pre(r, Fl_sub(V, W, p), p, pi),
     105             :                 Fl_double(Fl_mul_pre(S1, J, p, pi), p), p);
     106     5736169 :   R[3] = Fl_mul_pre(Fl_sub(Fl_sqr_pre(Fl_add(Z1, Z2, p), p, pi),
     107             :                            Fl_add(Z1Z1, Z2Z2, p), p), H, p, pi);
     108             : }
     109             : 
     110             : INLINE void
     111     6218246 : Flj_add_pre_inplace(GEN P, GEN Q, ulong a4, ulong p, ulong pi)
     112     6218246 : { Flj_add_indir_pre(P, Q, P, a4, p, pi); }
     113             : 
     114             : GEN
     115           0 : Flj_add_pre(GEN P, GEN Q, ulong a4, ulong p, ulong pi)
     116             : {
     117           0 :   GEN R = cgetg(4, t_VECSMALL);
     118           0 :   Flj_add_indir_pre(P, Q, R, a4, p, pi);
     119           0 :   return R;
     120             : }
     121             : 
     122             : GEN
     123     1944817 : Flj_neg(GEN Q, ulong p)
     124     1944817 : { return mkvecsmall3(Q[1], Fl_neg(Q[2], p), Q[3]); }
     125             : 
     126             : typedef struct {
     127             :   ulong pbits, nbits;  /* Positive bits and negative bits */
     128             :   ulong lnzb; /* Leading non-zero bit */
     129             : } naf_t;
     130             : 
     131             : /* Return the signed binary representation (i.e. the Non-Adjacent Form
     132             :  * in base 2) of a; a = x.pbits - x.nbits (+ 2^BILif < 0; this
     133             :  * exceptional case can happen if a > 2^(BIL-1)) */
     134             : static void
     135     3525262 : naf_repr(naf_t *x, ulong a)
     136             : {
     137     3525262 :   ulong pbits = 0, nbits = 0, c0 = 0, c1, a0;
     138             :   long t, i;
     139             : 
     140    33036374 :   for (i = 0; a; a >>= 1, ++i) {
     141    29511112 :     a0 = a & 1;
     142    29511112 :     c1 = (c0 + a0 + ((a & 2) >> 1)) >> 1;
     143    29511112 :     t = c0 + a0 - (c1 << 1);
     144    29511112 :     if (t < 0)
     145     4548607 :       nbits |= (1UL << i);
     146    24962505 :     else if (t > 0)
     147     5399495 :       pbits |= (1UL << i);
     148    29511112 :     c0 = c1;
     149             :   }
     150     3525262 :   c1 = c0 >> 1;
     151     3525262 :   t = c0 - (c1 << 1);
     152             :   /* since a >= 0, we have t >= 0; if i = BIL, pbits (virtually) overflows;
     153             :    * that leading overflowed bit is implied and not recorded in pbits */
     154     3525262 :   if (t > 0 && i != BITS_IN_LONG) pbits |= (1UL << i);
     155     3525262 :   x->pbits = pbits;
     156     3525262 :   x->nbits = nbits;
     157     3525262 :   x->lnzb = t? i-2: i-3;
     158     3525262 : }
     159             : 
     160             : /* Standard left-to-right signed double-and-add to compute [n]P. */
     161             : static GEN
     162     3404401 : Flj_mulu_pre_naf(GEN P, ulong n, ulong a4, ulong p, ulong pi, const naf_t *x)
     163             : {
     164             :   GEN R, Pi;
     165             :   ulong pbits, nbits;
     166             :   ulong m;
     167             : 
     168     3404401 :   if (n == 0) return mkvecsmall3(1, 1, 0);
     169     3404356 :   if (n == 1) return Flv_copy(P);
     170             : 
     171     3155032 :   R = Flj_dbl_pre(P, a4, p, pi);
     172     3154684 :   if (n == 2) return R;
     173             : 
     174     2446108 :   pbits = x->pbits;
     175     2446108 :   nbits = x->nbits;
     176     2446108 :   Pi = nbits? Flj_neg(P, p): NULL;
     177     2446242 :   m = (1UL << x->lnzb);
     178    20016376 :   for ( ; m; m >>= 1) {
     179    17571063 :     Flj_dbl_pre_inplace(R, a4, p, pi);
     180    17569175 :     if (m & pbits)
     181     2732108 :       Flj_add_pre_inplace(R, P, a4, p, pi);
     182    14837067 :     else if (m & nbits)
     183     3487567 :       Flj_add_pre_inplace(R, Pi, a4, p, pi);
     184             :   }
     185     2445313 :   set_avma((pari_sp)R); return R;
     186             : }
     187             : 
     188             : GEN
     189     2336059 : Flj_mulu_pre(GEN P, ulong n, ulong a4, ulong p, ulong pi)
     190             : {
     191     2336059 :   naf_t x; naf_repr(&x, n);
     192     2336217 :   return Flj_mulu_pre_naf(P, n, a4, p, pi, &x);
     193             : }
     194             : 
     195             : struct _Flj { ulong a4, p, pi; };
     196             : 
     197             : static GEN
     198           0 : _Flj_add(void *E, GEN P, GEN Q)
     199             : {
     200           0 :   struct _Flj *ell=(struct _Flj *) E;
     201           0 :   return Flj_add_pre(P, Q, ell->a4, ell->p, ell->pi);
     202             : }
     203             : 
     204             : static GEN
     205           0 : _Flj_mul(void *E, GEN P, GEN n)
     206             : {
     207           0 :   struct _Flj *ell = (struct _Flj *) E;
     208           0 :   long s = signe(n);
     209             :   GEN Q;
     210           0 :   if (s==0) return mkvecsmall3(1, 1, 0);
     211           0 :   Q = Flj_mulu_pre(P, itou(n), ell->a4, ell->p, ell->pi);
     212           0 :   return s>0 ? Q : Flj_neg(Q, ell->p);
     213             : }
     214             : 
     215             : GEN
     216           0 : FljV_factorback_pre(GEN P, GEN L, ulong a4, ulong p, ulong pi)
     217             : {
     218             :   struct _Flj E;
     219           0 :   E.a4 = a4; E.p = p; E.pi = pi;
     220           0 :   return gen_factorback(P, L, (void*)&E, &_Flj_add, &_Flj_mul);
     221             : }
     222             : 
     223             : ulong
     224      248016 : Flj_order_ufact(GEN P, ulong n, GEN F, ulong a4, ulong p, ulong pi)
     225             : {
     226      248016 :   pari_sp av = avma;
     227      248016 :   ulong res = 1;
     228             :   long i, nfactors;
     229             :   GEN primes, exps;
     230             : 
     231      248016 :   primes = gel(F, 1);
     232      248016 :   nfactors = lg(primes);
     233      248016 :   exps = gel(F, 2);
     234             : 
     235      706524 :   for (i = 1; i < nfactors; ++i) {
     236      565389 :     ulong q, pp = primes[i];
     237      565389 :     long j, k, ei = exps[i];
     238             :     naf_t x;
     239             :     GEN b;
     240             : 
     241     1339869 :     for (q = pp, j = 1; j < ei; ++j) q *= pp;
     242      565389 :     b = Flj_mulu_pre(P, n / q, a4, p, pi);
     243             : 
     244      565389 :     naf_repr(&x, pp);
     245     1633589 :     for (j = 0; j < ei && b[3]; ++j)
     246     1068200 :       b = Flj_mulu_pre_naf(b, pp, a4, p, pi, &x);
     247      565389 :     if (b[3]) return 0;
     248     1133502 :     for (k = 0; k < j; ++k) res *= pp;
     249      458508 :     set_avma(av);
     250             :   }
     251      141135 :   return res;
     252             : }
     253             : 
     254             : GEN
     255     1169703 : Fle_to_Flj(GEN P)
     256     2339428 : { return ell_is_inf(P) ? mkvecsmall3(1UL, 1UL, 0UL):
     257     1169681 :                          mkvecsmall3(P[1], P[2], 1UL);
     258             : }
     259             : 
     260             : GEN
     261     1169500 : Flj_to_Fle_pre(GEN P, ulong p, ulong pi)
     262             : {
     263     1169500 :   if (P[3] == 0) return ellinf();
     264             :   else
     265             :   {
     266     1059876 :     ulong Z = Fl_inv(P[3], p);
     267     1060143 :     ulong Z2 = Fl_sqr_pre(Z, p, pi);
     268     1060037 :     ulong X3 = Fl_mul_pre(P[1], Z2, p, pi);
     269     1060034 :     ulong Y3 = Fl_mul_pre(P[2], Fl_mul_pre(Z, Z2, p, pi), p, pi);
     270     1060047 :     return mkvecsmall2(X3, Y3);
     271             :   }
     272             : }
     273             : 
     274             : INLINE void
     275     6437360 : random_Fle_pre_indir(ulong a4, ulong a6, ulong p, ulong pi,
     276             :                      ulong *pt_x, ulong *pt_y)
     277             : {
     278             :   ulong x, x2, y, rhs;
     279             :   do
     280             :   {
     281     6437360 :     x   = random_Fl(p); /*  x^3+a4*x+a6 = x*(x^2+a4)+a6  */
     282     6437440 :     x2  = Fl_sqr_pre(x, p, pi);
     283     6437421 :     rhs = Fl_addmul_pre(a6, x, Fl_add(x2, a4, p), p, pi);
     284     6437427 :   } while ((!rhs && !Fl_add(Fl_triple(x2,p),a4,p)) || krouu(rhs, p) < 0);
     285     3226621 :   y = Fl_sqrt_pre(rhs, p, pi);
     286     3226614 :   *pt_x = x; *pt_y = y;
     287     3226614 : }
     288             : 
     289             : GEN
     290      418071 : random_Flj_pre(ulong a4, ulong a6, ulong p, ulong pi)
     291             : {
     292             :   ulong x, y;
     293      418071 :   random_Fle_pre_indir(a4, a6, p, pi, &x, &y);
     294      418051 :   return mkvecsmall3(x, y, 1);
     295             : }
     296             : 
     297             : GEN
     298           0 : Flj_changepointinv_pre(GEN P, GEN ch, ulong p, ulong pi)
     299             : {
     300             :   ulong c, u, r, s, t, u2, u3;
     301           0 :   ulong x  = uel(P,1), y = uel(P,2), z = uel(P,3);
     302             :   GEN w;
     303           0 :   if (z == 0) return Flv_copy(P);
     304           0 :   u = ch[1]; r = ch[2];
     305           0 :   s = ch[3]; t = ch[4];
     306           0 :   u2 = Fl_sqr_pre(u, p, pi); u3 = Fl_mul_pre(u, u2, p, pi);
     307           0 :   c = Fl_mul_pre(u2, x, p, pi);
     308           0 :   w = cgetg(4, t_VECSMALL);
     309           0 :   uel(w,1) = Fl_add(c, Fl_mul_pre(r, Fl_sqr_pre(z, p, pi), p, pi), p);
     310           0 :   uel(w,2) = Fl_add(Fl_mul_pre(u3 ,y, p, pi),
     311             :                     Fl_mul_pre(z, Fl_add(Fl_mul_pre(s,c,p,pi),
     312             :                                          Fl_mul_pre(z,t,p,pi), p), p, pi), p);
     313           0 :   uel(w,3) = z;
     314           0 :   return w;
     315             : }
     316             : 
     317             : /***********************************************************************/
     318             : /**                                                                   **/
     319             : /**                              Fle                                  **/
     320             : /**                                                                   **/
     321             : /***********************************************************************/
     322             : GEN
     323         712 : Fle_changepoint(GEN P, GEN ch, ulong p)
     324             : {
     325             :   ulong c, u, r, s, t, v, v2, v3;
     326             :   GEN z;
     327         712 :   if (ell_is_inf(P)) return ellinf();
     328         712 :   u = ch[1]; r = ch[2];
     329         712 :   s = ch[3]; t = ch[4];
     330         712 :   v = Fl_inv(u, p); v2 = Fl_sqr(v,p); v3 = Fl_mul(v,v2,p);
     331         712 :   c = Fl_sub(uel(P,1),r,p);
     332         712 :   z = cgetg(3,t_VECSMALL);
     333         712 :   z[1] = Fl_mul(v2, c, p);
     334         712 :   z[2] = Fl_mul(v3, Fl_sub(uel(P,2), Fl_add(Fl_mul(s,c, p),t, p),p),p);
     335         712 :   return z;
     336             : }
     337             : 
     338             : GEN
     339        2200 : Fle_changepointinv(GEN P, GEN ch, ulong p)
     340             : {
     341             :   ulong c, u, r, s, t, u2, u3;
     342             :   GEN z;
     343        2200 :   if (ell_is_inf(P)) return ellinf();
     344        2200 :   u = ch[1]; r = ch[2];
     345        2200 :   s = ch[3]; t = ch[4];
     346        2200 :   u2 = Fl_sqr(u, p); u3 = Fl_mul(u,u2,p);
     347        2200 :   c = Fl_mul(u2,uel(P,1), p);
     348        2200 :   z = cgetg(3, t_VECSMALL);
     349        2200 :   z[1] = Fl_add(c,r,p);
     350        2200 :   z[2] = Fl_add(Fl_mul(u3,uel(P,2),p), Fl_add(Fl_mul(s,c,p), t, p), p);
     351        2200 :   return z;
     352             : }
     353             : static GEN
     354      422321 : Fle_dbl_slope(GEN P, ulong a4, ulong p, ulong *slope)
     355             : {
     356             :   ulong x, y, Qx, Qy;
     357      422321 :   if (ell_is_inf(P) || !P[2]) return ellinf();
     358      369495 :   x = P[1]; y = P[2];
     359      369495 :   *slope = Fl_div(Fl_add(Fl_triple(Fl_sqr(x,p), p), a4, p),
     360             :                   Fl_double(y, p), p);
     361      369499 :   Qx = Fl_sub(Fl_sqr(*slope, p), Fl_double(x, p), p);
     362      369495 :   Qy = Fl_sub(Fl_mul(*slope, Fl_sub(x, Qx, p), p), y, p);
     363      369483 :   return mkvecsmall2(Qx, Qy);
     364             : }
     365             : 
     366             : GEN
     367      345181 : Fle_dbl(GEN P, ulong a4, ulong p)
     368             : {
     369             :   ulong slope;
     370      345181 :   return Fle_dbl_slope(P,a4,p,&slope);
     371             : }
     372             : 
     373             : static GEN
     374      672664 : Fle_add_slope(GEN P, GEN Q, ulong a4, ulong p, ulong *slope)
     375             : {
     376             :   ulong Px, Py, Qx, Qy, Rx, Ry;
     377      672664 :   if (ell_is_inf(P)) return Q;
     378      672673 :   if (ell_is_inf(Q)) return P;
     379      672662 :   Px = P[1]; Py = P[2];
     380      672662 :   Qx = Q[1]; Qy = Q[2];
     381      672662 :   if (Px==Qx) return Py==Qy ? Fle_dbl_slope(P, a4, p, slope): ellinf();
     382      595446 :   *slope = Fl_div(Fl_sub(Py, Qy, p), Fl_sub(Px, Qx, p), p);
     383      595610 :   Rx = Fl_sub(Fl_sub(Fl_sqr(*slope, p), Px, p), Qx, p);
     384      595551 :   Ry = Fl_sub(Fl_mul(*slope, Fl_sub(Px, Rx, p), p), Py, p);
     385      595546 :   return mkvecsmall2(Rx, Ry);
     386             : }
     387             : 
     388             : GEN
     389      672653 : Fle_add(GEN P, GEN Q, ulong a4, ulong p)
     390             : {
     391             :   ulong slope;
     392      672653 :   return Fle_add_slope(P,Q,a4,p,&slope);
     393             : }
     394             : 
     395             : static GEN
     396         112 : Fle_neg(GEN P, ulong p)
     397             : {
     398         112 :   if (ell_is_inf(P)) return P;
     399         112 :   return mkvecsmall2(P[1], Fl_neg(P[2], p));
     400             : }
     401             : 
     402             : GEN
     403           0 : Fle_sub(GEN P, GEN Q, ulong a4, ulong p)
     404             : {
     405           0 :   pari_sp av = avma;
     406             :   ulong slope;
     407           0 :   return gerepileupto(av, Fle_add_slope(P, Fle_neg(Q, p), a4, p, &slope));
     408             : }
     409             : 
     410             : struct _Fle { ulong a4, a6, p; };
     411             : 
     412             : static GEN
     413           0 : _Fle_dbl(void *E, GEN P)
     414             : {
     415           0 :   struct _Fle *ell = (struct _Fle *) E;
     416           0 :   return Fle_dbl(P, ell->a4, ell->p);
     417             : }
     418             : 
     419             : static GEN
     420        7791 : _Fle_add(void *E, GEN P, GEN Q)
     421             : {
     422        7791 :   struct _Fle *ell=(struct _Fle *) E;
     423        7791 :   return Fle_add(P, Q, ell->a4, ell->p);
     424             : }
     425             : 
     426             : GEN
     427     1515837 : Fle_mulu(GEN P, ulong n, ulong a4, ulong p)
     428             : {
     429             :   ulong pi;
     430     1515837 :   if (!n || ell_is_inf(P)) return ellinf();
     431     1515796 :   if (n==1) return zv_copy(P);
     432     1514585 :   if (n==2) return Fle_dbl(P, a4, p);
     433     1169635 :   pi = get_Fl_red(p);
     434     1169707 :   return Flj_to_Fle_pre(Flj_mulu_pre(Fle_to_Flj(P), n, a4, p, pi), p, pi);
     435             : }
     436             : 
     437             : static GEN
     438      876542 : _Fle_mul(void *E, GEN P, GEN n)
     439             : {
     440      876542 :   pari_sp av = avma;
     441      876542 :   struct _Fle *e=(struct _Fle *) E;
     442      876542 :   long s = signe(n);
     443             :   GEN Q;
     444      876542 :   if (!s || ell_is_inf(P)) return ellinf();
     445      876622 :   if (s < 0) P = Fle_neg(P, e->p);
     446      876622 :   if (is_pm1(n)) return s > 0? zv_copy(P): P;
     447      876050 :   Q = (lgefint(n)==3) ? Fle_mulu(P, uel(n,2), e->a4, e->p):
     448           0 :                         gen_pow(P, n, (void*)e, &_Fle_dbl, &_Fle_add);
     449      876084 :   return s > 0? Q: gerepileuptoleaf(av, Q);
     450             : }
     451             : 
     452             : GEN
     453         238 : Fle_mul(GEN P, GEN n, ulong a4, ulong p)
     454             : {
     455             :   struct _Fle E;
     456         238 :   E.a4 = a4; E.p = p;
     457         238 :   return _Fle_mul(&E, P, n);
     458             : }
     459             : 
     460             : /* Finds a random non-singular point on E */
     461             : GEN
     462     2808562 : random_Fle_pre(ulong a4, ulong a6, ulong p, ulong pi)
     463             : {
     464             :   ulong x, y;
     465     2808562 :   random_Fle_pre_indir(a4, a6, p, pi, &x, &y);
     466     2808562 :   return mkvecsmall2(x, y);
     467             : }
     468             : 
     469             : GEN
     470           0 : random_Fle(ulong a4, ulong a6, ulong p)
     471           0 : { return random_Fle_pre(a4, a6, p, get_Fl_red(p)); }
     472             : 
     473             : static GEN
     474           0 : _Fle_rand(void *E)
     475             : {
     476           0 :   struct _Fle *e=(struct _Fle *) E;
     477           0 :   return random_Fle(e->a4, e->a6, e->p);
     478             : }
     479             : 
     480             : static const struct bb_group Fle_group={_Fle_add,_Fle_mul,_Fle_rand,hash_GEN,zv_equal,ell_is_inf,NULL};
     481             : 
     482             : GEN
     483      220175 : Fle_order(GEN z, GEN o, ulong a4, ulong p)
     484             : {
     485      220175 :   pari_sp av = avma;
     486             :   struct _Fle e;
     487      220175 :   e.a4=a4;
     488      220175 :   e.p=p;
     489      220175 :   return gerepileuptoint(av, gen_order(z, o, (void*)&e, &Fle_group));
     490             : }
     491             : 
     492             : GEN
     493          49 : Fle_log(GEN a, GEN b, GEN o, ulong a4, ulong p)
     494             : {
     495          49 :   pari_sp av = avma;
     496             :   struct _Fle e;
     497          49 :   e.a4=a4;
     498          49 :   e.p=p;
     499          49 :   return gerepileuptoint(av, gen_PH_log(a, b, o, (void*)&e, &Fle_group));
     500             : }
     501             : 
     502             : ulong
     503           0 : Fl_ellj(ulong a4, ulong a6, ulong p)
     504             : {
     505           0 :   if (SMALL_ULONG(p))
     506             :   { /* a43 = 4 a4^3 */
     507           0 :     ulong a43 = Fl_double(Fl_double(Fl_mul(a4, Fl_sqr(a4, p), p), p), p);
     508             :     /* a62 = 27 a6^2 */
     509           0 :     ulong a62 = Fl_mul(Fl_sqr(a6, p), 27 % p, p);
     510           0 :     ulong z1 = Fl_mul(a43, 1728 % p, p);
     511           0 :     ulong z2 = Fl_add(a43, a62, p);
     512           0 :     return Fl_div(z1, z2, p);
     513             :   }
     514           0 :   return Fl_ellj_pre(a4, a6, p, get_Fl_red(p));
     515             : }
     516             : 
     517             : void
     518      114680 : Fl_ellj_to_a4a6(ulong j, ulong p, ulong *pt_a4, ulong *pt_a6)
     519             : {
     520      114680 :   ulong zagier = 1728 % p;
     521      114680 :   if (j == 0)           { *pt_a4 = 0; *pt_a6 =1; }
     522      114680 :   else if (j == zagier) { *pt_a4 = 1; *pt_a6 =0; }
     523             :   else
     524             :   {
     525      114680 :     ulong k = Fl_sub(zagier, j, p);
     526      114678 :     ulong kj = Fl_mul(k, j, p);
     527      114680 :     ulong k2j = Fl_mul(kj, k, p);
     528      114678 :     *pt_a4 = Fl_triple(kj, p);
     529      114680 :     *pt_a6 = Fl_double(k2j, p);
     530             :   }
     531      114680 : }
     532             : 
     533             : ulong
     534     2440825 : Fl_elldisc_pre(ulong a4, ulong a6, ulong p, ulong pi)
     535             : { /* D = -(4A^3 + 27B^2) */
     536             :   ulong t1, t2;
     537     2440825 :   t1 = Fl_mul_pre(a4, Fl_sqr_pre(a4, p, pi), p, pi);
     538     2440825 :   t1 = Fl_double(Fl_double(t1, p), p);
     539     2440825 :   t2 = Fl_mul_pre(27 % p, Fl_sqr_pre(a6, p, pi), p, pi);
     540     2440825 :   return Fl_neg(Fl_add(t1, t2, p), p);
     541             : }
     542             : 
     543             : ulong
     544           0 : Fl_elldisc(ulong a4, ulong a6, ulong p)
     545             : {
     546           0 :   if (SMALL_ULONG(p))
     547             :   { /* D = -(4A^3 + 27B^2) */
     548             :     ulong t1, t2;
     549           0 :     t1 = Fl_mul(a4, Fl_sqr(a4, p), p);
     550           0 :     t1 = Fl_double(Fl_double(t1, p), p);
     551           0 :     t2 = Fl_mul(27 % p, Fl_sqr(a6, p), p);
     552           0 :     return Fl_neg(Fl_add(t1, t2, p), p);
     553             :   }
     554           0 :   return Fl_elldisc_pre(a4, a6, p, get_Fl_red(p));
     555             : }
     556             : 
     557             : void
     558      210909 : Fl_elltwist_disc(ulong a4, ulong a6, ulong D, ulong p, ulong *pa4, ulong *pa6)
     559             : {
     560      210909 :   ulong D2 = Fl_sqr(D, p);
     561      210908 :   *pa4 = Fl_mul(a4, D2, p);
     562      210909 :   *pa6 = Fl_mul(a6, Fl_mul(D, D2, p), p);
     563      210906 : }
     564             : 
     565             : void
     566           0 : Fl_elltwist(ulong a4, ulong a6, ulong p, ulong *pt_a4, ulong *pt_a6)
     567           0 : { Fl_elltwist_disc(a4, a6, nonsquare_Fl(p), p, pt_a4, pt_a6); }
     568             : 
     569             : static void
     570    41511803 : Fle_dbl_sinv_pre_inplace(GEN P, ulong a4, ulong sinv, ulong p, ulong pi)
     571             : {
     572             :   ulong x, y, slope;
     573    41511803 :   if (uel(P,1)==p) return;
     574    41305390 :   if (!P[2]) { P[1] = p; return; }
     575    41181136 :   x = P[1]; y = P[2];
     576    41181136 :   slope = Fl_mul_pre(Fl_add(Fl_triple(Fl_sqr_pre(x, p, pi), p), a4, p),
     577             :                 sinv, p, pi);
     578    41181136 :   P[1] = Fl_sub(Fl_sqr_pre(slope, p, pi), Fl_double(x, p), p);
     579    41181136 :   P[2] = Fl_sub(Fl_mul_pre(slope, Fl_sub(x, P[1], p), p, pi), y, p);
     580             : }
     581             : 
     582             : static void
     583     5464639 : Fle_add_sinv_pre_inplace(GEN P, GEN Q, ulong a4, ulong sinv, ulong p, ulong pi)
     584             : {
     585             :   ulong Px, Py, Qx, Qy, slope;
     586     5464639 :   if (uel(P,1)==p) { P[1] = Q[1]; P[2] = Q[2]; }
     587     5464639 :   if (ell_is_inf(Q)) return;
     588     5464639 :   Px = P[1]; Py = P[2];
     589     5464639 :   Qx = Q[1]; Qy = Q[2];
     590     5464639 :   if (Px==Qx)
     591             :   {
     592       23797 :     if (Py==Qy) Fle_dbl_sinv_pre_inplace(P, a4, sinv, p, pi);
     593       11664 :     else P[1] = p;
     594       23797 :     return;
     595             :   }
     596     5440842 :   slope = Fl_mul_pre(Fl_sub(Py, Qy, p), sinv, p, pi);
     597     5440842 :   P[1] = Fl_sub(Fl_sub(Fl_sqr_pre(slope, p, pi), Px, p), Qx, p);
     598     5440842 :   P[2] = Fl_sub(Fl_mul_pre(slope, Fl_sub(Px, P[1], p), p, pi), Py, p);
     599             : }
     600             : 
     601             : static void
     602     6160656 : Fle_sub_sinv_pre_inplace(GEN P, GEN Q, ulong a4, ulong sinv, ulong p, ulong pi)
     603             : {
     604             :   ulong Px, Py, Qx, Qy, slope;
     605     6160656 :   if (uel(P,1)==p) { P[1] = Q[1]; P[2] = Fl_neg(Q[2], p); }
     606     6160656 :   if (ell_is_inf(Q)) return;
     607     6160656 :   Px = P[1]; Py = P[2];
     608     6160656 :   Qx = Q[1]; Qy = Q[2];
     609     6160656 :   if (Px==Qx)
     610             :   {
     611       28598 :     if (Py==Qy) P[1] = p;
     612             :     else
     613       11672 :       Fle_dbl_sinv_pre_inplace(P, a4, sinv, p, pi);
     614       28598 :     return;
     615             :   }
     616     6132058 :   slope = Fl_mul_pre(Fl_add(Py, Qy, p), sinv, p, pi);
     617     6132058 :   P[1] = Fl_sub(Fl_sub(Fl_sqr_pre(slope, p, pi), Px, p), Qx, p);
     618     6132058 :   P[2] = Fl_sub(Fl_mul_pre(slope, Fl_sub(Px, P[1], p), p, pi), Py, p);
     619             : }
     620             : 
     621             : static long
     622    52884637 : skipzero(long n) { return n ? n:1; }
     623             : 
     624             : void
     625      954244 : FleV_add_pre_inplace(GEN P, GEN Q, GEN a4, ulong p, ulong pi)
     626             : {
     627      954244 :   long i, l=lg(a4);
     628      954244 :   GEN sinv = cgetg(l, t_VECSMALL);
     629     6418883 :   for(i=1; i<l; i++)
     630     5464639 :     uel(sinv,i) = umael(P,i,1)==p? 1: skipzero(Fl_sub(mael(P,i,1), mael(Q,i,1), p));
     631      954244 :   Flv_inv_pre_inplace(sinv, p, pi);
     632     6418883 :   for (i=1; i<l; i++)
     633     5464639 :     Fle_add_sinv_pre_inplace(gel(P,i), gel(Q,i), uel(a4,i), uel(sinv,i), p, pi);
     634      954244 : }
     635             : 
     636             : void
     637     1091657 : FleV_sub_pre_inplace(GEN P, GEN Q, GEN a4, ulong p, ulong pi)
     638             : {
     639     1091657 :   long i, l=lg(a4);
     640     1091657 :   GEN sinv = cgetg(l, t_VECSMALL);
     641     7252313 :   for(i=1; i<l; i++)
     642     6160656 :     uel(sinv,i) = umael(P,i,1)==p? 1: skipzero(Fl_sub(mael(P,i,1), mael(Q,i,1), p));
     643     1091657 :   Flv_inv_pre_inplace(sinv, p, pi);
     644     7252313 :   for (i=1; i<l; i++)
     645     6160656 :     Fle_sub_sinv_pre_inplace(gel(P,i), gel(Q,i), uel(a4,i), uel(sinv,i), p, pi);
     646     1091657 : }
     647             : 
     648             : void
     649     7583837 : FleV_dbl_pre_inplace(GEN P, GEN a4, ulong p, ulong pi)
     650             : {
     651     7583837 :   long i, l=lg(a4);
     652     7583837 :   GEN sinv = cgetg(l, t_VECSMALL);
     653    49071835 :   for(i=1; i<l; i++)
     654    41487998 :     uel(sinv,i) = umael(P,i,1)==p? 1: skipzero(Fl_double(umael(P,i,2), p));
     655     7583837 :   Flv_inv_pre_inplace(sinv, p, pi);
     656    49071835 :   for(i=1; i<l; i++)
     657    41487998 :     Fle_dbl_sinv_pre_inplace(gel(P,i), uel(a4,i), uel(sinv,i), p, pi);
     658     7583837 : }
     659             : 
     660             : static void
     661      623817 : FleV_mulu_pre_naf_inplace(GEN P, ulong n, GEN a4, ulong p, ulong pi, const naf_t *x)
     662             : {
     663      623817 :   pari_sp av = avma;
     664             :   ulong pbits, nbits, m;
     665             :   GEN R;
     666      623817 :   if (n == 1) return;
     667             : 
     668      623817 :   R = P; P = gcopy(P);
     669      623817 :   FleV_dbl_pre_inplace(R, a4, p, pi);
     670      623817 :   if (n == 2) return;
     671             : 
     672      623713 :   pbits = x->pbits;
     673      623713 :   nbits = x->nbits;
     674      623713 :   m = (1UL << x->lnzb);
     675     7583733 :   for ( ; m; m >>= 1) {
     676     6960020 :     FleV_dbl_pre_inplace(R, a4, p, pi);
     677     6960020 :     if (m & pbits)
     678      954244 :       FleV_add_pre_inplace(R, P, a4, p, pi);
     679     6005776 :     else if (m & nbits)
     680     1091657 :       FleV_sub_pre_inplace(R, P, a4, p, pi);
     681             :   }
     682      623713 :   set_avma(av);
     683             : }
     684             : 
     685             : void
     686      623817 : FleV_mulu_pre_inplace(GEN P, ulong n, GEN a4, ulong p, ulong pi)
     687             : {
     688      623817 :   naf_t x; naf_repr(&x, n);
     689      623817 :   FleV_mulu_pre_naf_inplace(P, n, a4, p, pi, &x);
     690      623817 : }

Generated by: LCOV version 1.13