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.0 lcov report (development 23339-b1c33c51a) Lines: 301 333 90.4 %
Date: 2018-12-11 05:41:34 Functions: 40 48 83.3 %
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    20685937 : 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    20685937 :   X1 = P[1]; Y1 = P[2]; Z1 = P[3];
      40             : 
      41    20685937 :   if (Z1 == 0) { Q[1] = X1; Q[2] = Y1; Q[3] = Z1; return; }
      42             : 
      43    20545953 :   XX = Fl_sqr_pre(X1, p, pi);
      44    20543759 :   YY = Fl_sqr_pre(Y1, p, pi);
      45    20540902 :   YYYY = Fl_sqr_pre(YY, p, pi);
      46    20540105 :   ZZ = Fl_sqr_pre(Z1, p, pi);
      47    20540652 :   S = Fl_double(Fl_sub(Fl_sqr_pre(Fl_add(X1, YY, p), p, pi),
      48             :                        Fl_add(XX, YYYY, p), p), p);
      49    20539245 :   M = Fl_addmul_pre(Fl_triple(XX, p), a4, Fl_sqr_pre(ZZ, p, pi), p, pi);
      50    20546289 :   T = Fl_sub(Fl_sqr_pre(M, p, pi), Fl_double(S, p), p);
      51    20541824 :   Q[1] = T;
      52    20541824 :   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    20540606 :   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    17539690 : Flj_dbl_pre_inplace(GEN P, ulong a4, ulong p, ulong pi)
      60             : {
      61    17539690 :   Flj_dbl_indir_pre(P, P, a4, p, pi);
      62    17539779 : }
      63             : 
      64             : GEN
      65     3143916 : Flj_dbl_pre(GEN P, ulong a4, ulong p, ulong pi)
      66             : {
      67     3143916 :   GEN Q = cgetg(4, t_VECSMALL);
      68     3143665 :   Flj_dbl_indir_pre(P, Q, a4, p, pi);
      69     3143663 :   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     6203835 : 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     6203835 :   X1 = P[1]; Y1 = P[2]; Z1 = P[3];
      80     6203835 :   X2 = Q[1]; Y2 = Q[2]; Z2 = Q[3];
      81             : 
      82     6203835 :   if (Z2 == 0) { R[1] = X1; R[2] = Y1; R[3] = Z1; return; }
      83     6203708 :   if (Z1 == 0) { R[1] = X2; R[2] = Y2; R[3] = Z2; return; }
      84             : 
      85     6193790 :   Z1Z1 = Fl_sqr_pre(Z1, p, pi);
      86     6193042 :   Z2Z2 = Fl_sqr_pre(Z2, p, pi);
      87     6192779 :   U1 = Fl_mul_pre(X1, Z2Z2, p, pi);
      88     6192773 :   U2 = Fl_mul_pre(X2, Z1Z1, p, pi);
      89     6192727 :   S1 = Fl_mul_pre(Y1, Fl_mul_pre(Z2, Z2Z2, p, pi), p, pi);
      90     6192691 :   S2 = Fl_mul_pre(Y2, Fl_mul_pre(Z1, Z1Z1, p, pi), p, pi);
      91     6192940 :   H = Fl_sub(U2, U1, p);
      92     6192864 :   r = Fl_double(Fl_sub(S2, S1, p), p);
      93             : 
      94     6193046 :   if (H == 0) {
      95      469536 :     if (r == 0) Flj_dbl_indir_pre(P, R, a4, p, pi); /* P = Q */
      96      467060 :     else { R[1] = R[2] = 1; R[3] = 0; } /* P = -Q */
      97      469536 :     return;
      98             :   }
      99     5723510 :   I = Fl_sqr_pre(Fl_double(H, p), p, pi);
     100     5723711 :   J = Fl_mul_pre(H, I, p, pi);
     101     5723519 :   V = Fl_mul_pre(U1, I, p, pi);
     102     5723484 :   W = Fl_sub(Fl_sqr_pre(r, p, pi), Fl_add(J, Fl_double(V, p), p), p);
     103     5723611 :   R[1] = W;
     104     5723611 :   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     5723569 :   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     6202693 : Flj_add_pre_inplace(GEN P, GEN Q, ulong a4, ulong p, ulong pi)
     112     6202693 : { 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     1938307 : Flj_neg(GEN Q, ulong p)
     124     1938307 : { 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     3512558 : naf_repr(naf_t *x, ulong a)
     136             : {
     137     3512558 :   ulong pbits = 0, nbits = 0, c0 = 0, c1, a0;
     138             :   long t, i;
     139             : 
     140    32976237 :   for (i = 0; a; a >>= 1, ++i) {
     141    29463679 :     a0 = a & 1;
     142    29463679 :     c1 = (c0 + a0 + ((a & 2) >> 1)) >> 1;
     143    29463679 :     t = c0 + a0 - (c1 << 1);
     144    29463679 :     if (t < 0)
     145     4540631 :       nbits |= (1UL << i);
     146    24923048 :     else if (t > 0)
     147     5385138 :       pbits |= (1UL << i);
     148    29463679 :     c0 = c1;
     149             :   }
     150     3512558 :   c1 = c0 >> 1;
     151     3512558 :   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     3512558 :   if (t > 0 && i != BITS_IN_LONG) pbits |= (1UL << i);
     155     3512558 :   x->pbits = pbits;
     156     3512558 :   x->nbits = nbits;
     157     3512558 :   x->lnzb = t? i-2: i-3;
     158     3512558 : }
     159             : 
     160             : /* Standard left-to-right signed double-and-add to compute [n]P. */
     161             : static GEN
     162     3391728 : 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     3391728 :   if (n == 0) return mkvecsmall3(1, 1, 0);
     169     3391683 :   if (n == 1) return Flv_copy(P);
     170             : 
     171     3143945 :   R = Flj_dbl_pre(P, a4, p, pi);
     172     3143742 :   if (n == 2) return R;
     173             : 
     174     2437127 :   pbits = x->pbits;
     175     2437127 :   nbits = x->nbits;
     176     2437127 :   Pi = nbits? Flj_neg(P, p): NULL;
     177     2436445 :   m = (1UL << x->lnzb);
     178    19977329 :   for ( ; m; m >>= 1) {
     179    17540220 :     Flj_dbl_pre_inplace(R, a4, p, pi);
     180    17544005 :     if (m & pbits)
     181     2725309 :       Flj_add_pre_inplace(R, P, a4, p, pi);
     182    14818696 :     else if (m & nbits)
     183     3478757 :       Flj_add_pre_inplace(R, Pi, a4, p, pi);
     184             :   }
     185     2437109 :   set_avma((pari_sp)R); return R;
     186             : }
     187             : 
     188             : GEN
     189     2326138 : Flj_mulu_pre(GEN P, ulong n, ulong a4, ulong p, ulong pi)
     190             : {
     191     2326138 :   naf_t x; naf_repr(&x, n);
     192     2326484 :   return Flj_mulu_pre_naf(P, n, a4, p, pi, &x);
     193             : }
     194             : 
     195             : ulong
     196      246084 : Flj_order_ufact(GEN P, ulong n, GEN F, ulong a4, ulong p, ulong pi)
     197             : {
     198      246084 :   pari_sp av = avma;
     199      246084 :   ulong res = 1;
     200             :   long i, nfactors;
     201             :   GEN primes, exps;
     202             : 
     203      246084 :   primes = gel(F, 1);
     204      246084 :   nfactors = lg(primes);
     205      246084 :   exps = gel(F, 2);
     206             : 
     207      701903 :   for (i = 1; i < nfactors; ++i) {
     208      562031 :     ulong q, pp = primes[i];
     209      562031 :     long j, k, ei = exps[i];
     210             :     naf_t x;
     211             :     GEN b;
     212             : 
     213      562031 :     for (q = pp, j = 1; j < ei; ++j) q *= pp;
     214      562031 :     b = Flj_mulu_pre(P, n / q, a4, p, pi);
     215             : 
     216      562031 :     naf_repr(&x, pp);
     217     1627302 :     for (j = 0; j < ei && b[3]; ++j)
     218     1065271 :       b = Flj_mulu_pre_naf(b, pp, a4, p, pi, &x);
     219      562031 :     if (b[3]) return 0;
     220      455819 :     for (k = 0; k < j; ++k) res *= pp;
     221      455819 :     set_avma(av);
     222             :   }
     223      139872 :   return res;
     224             : }
     225             : 
     226             : GEN
     227     1164616 : Fle_to_Flj(GEN P)
     228     2329212 : { return ell_is_inf(P) ? mkvecsmall3(1UL, 1UL, 0UL):
     229     1164596 :                          mkvecsmall3(P[1], P[2], 1UL);
     230             : }
     231             : 
     232             : GEN
     233     1164548 : Flj_to_Fle_pre(GEN P, ulong p, ulong pi)
     234             : {
     235     1164548 :   if (P[3] == 0) return ellinf();
     236             :   else
     237             :   {
     238     1055452 :     ulong Z = Fl_inv(P[3], p);
     239     1055627 :     ulong Z2 = Fl_sqr_pre(Z, p, pi);
     240     1055479 :     ulong X3 = Fl_mul_pre(P[1], Z2, p, pi);
     241     1055482 :     ulong Y3 = Fl_mul_pre(P[2], Fl_mul_pre(Z, Z2, p, pi), p, pi);
     242     1055447 :     return mkvecsmall2(X3, Y3);
     243             :   }
     244             : }
     245             : 
     246             : INLINE void
     247     6467592 : random_Fle_pre_indir(ulong a4, ulong a6, ulong p, ulong pi,
     248             :                      ulong *pt_x, ulong *pt_y)
     249             : {
     250             :   ulong x, x2, y, rhs;
     251             :   do
     252             :   {
     253     6467592 :     x   = random_Fl(p); /*  x^3+a4*x+a6 = x*(x^2+a4)+a6  */
     254     6467623 :     x2  = Fl_sqr_pre(x, p, pi);
     255     6467576 :     rhs = Fl_addmul_pre(a6, x, Fl_add(x2, a4, p), p, pi);
     256     6467579 :   } while ((!rhs && !Fl_add(Fl_triple(x2,p),a4,p)) || krouu(rhs, p) < 0);
     257     3241791 :   y = Fl_sqrt_pre(rhs, p, pi);
     258     3241779 :   *pt_x = x; *pt_y = y;
     259     3241779 : }
     260             : 
     261             : GEN
     262      416560 : random_Flj_pre(ulong a4, ulong a6, ulong p, ulong pi)
     263             : {
     264             :   ulong x, y;
     265      416560 :   random_Fle_pre_indir(a4, a6, p, pi, &x, &y);
     266      416551 :   return mkvecsmall3(x, y, 1);
     267             : }
     268             : 
     269             : /***********************************************************************/
     270             : /**                                                                   **/
     271             : /**                              Fle                                  **/
     272             : /**                                                                   **/
     273             : /***********************************************************************/
     274             : GEN
     275         712 : Fle_changepoint(GEN P, GEN ch, ulong p)
     276             : {
     277             :   ulong c, u, r, s, t, v, v2, v3;
     278             :   GEN z;
     279         712 :   if (ell_is_inf(P)) return P;
     280         712 :   u = ch[1]; r = ch[2];
     281         712 :   s = ch[3]; t = ch[4];
     282         712 :   v = Fl_inv(u, p); v2 = Fl_sqr(v,p); v3 = Fl_mul(v,v2,p);
     283         712 :   c = Fl_sub(P[1],r,p);
     284         712 :   z = cgetg(3,t_VECSMALL);
     285         712 :   z[1] = Fl_mul(v2, c, p);
     286         712 :   z[2] = Fl_mul(v3, Fl_sub(P[2], Fl_add(Fl_mul(s,c, p),t, p),p),p);
     287         712 :   return z;
     288             : }
     289             : 
     290             : GEN
     291        2025 : Fle_changepointinv(GEN P, GEN ch, ulong p)
     292             : {
     293             :   ulong c, u, r, s, t, u2, u3;
     294             :   GEN z;
     295        2025 :   if (ell_is_inf(P)) return P;
     296        2025 :   u = ch[1]; r = ch[2];
     297        2025 :   s = ch[3]; t = ch[4];
     298        2025 :   u2 = Fl_sqr(u, p); u3 = Fl_mul(u,u2,p);
     299        2025 :   c = Fl_mul(u2,P[1], p);
     300        2025 :   z = cgetg(3, t_VECSMALL);
     301        2025 :   z[1] = Fl_add(c,r,p);
     302        2025 :   z[2] = Fl_add(Fl_mul(u3,P[2],p), Fl_add(Fl_mul(s,c,p), t, p), p);
     303        2025 :   return z;
     304             : }
     305             : static GEN
     306      420773 : Fle_dbl_slope(GEN P, ulong a4, ulong p, ulong *slope)
     307             : {
     308             :   ulong x, y, Qx, Qy;
     309      420773 :   if (ell_is_inf(P) || !P[2]) return ellinf();
     310      368207 :   x = P[1]; y = P[2];
     311      368207 :   *slope = Fl_div(Fl_add(Fl_triple(Fl_sqr(x,p), p), a4, p),
     312             :                   Fl_double(y, p), p);
     313      368219 :   Qx = Fl_sub(Fl_sqr(*slope, p), Fl_double(x, p), p);
     314      368213 :   Qy = Fl_sub(Fl_mul(*slope, Fl_sub(x, Qx, p), p), y, p);
     315      368205 :   return mkvecsmall2(Qx, Qy);
     316             : }
     317             : 
     318             : GEN
     319      343536 : Fle_dbl(GEN P, ulong a4, ulong p)
     320             : {
     321             :   ulong slope;
     322      343536 :   return Fle_dbl_slope(P,a4,p,&slope);
     323             : }
     324             : 
     325             : static GEN
     326      672129 : Fle_add_slope(GEN P, GEN Q, ulong a4, ulong p, ulong *slope)
     327             : {
     328             :   ulong Px, Py, Qx, Qy, Rx, Ry;
     329      672129 :   if (ell_is_inf(P)) return Q;
     330      672141 :   if (ell_is_inf(Q)) return P;
     331      672188 :   Px = P[1]; Py = P[2];
     332      672188 :   Qx = Q[1]; Qy = Q[2];
     333      672188 :   if (Px==Qx) return Py==Qy ? Fle_dbl_slope(P, a4, p, slope): ellinf();
     334      594875 :   *slope = Fl_div(Fl_sub(Py, Qy, p), Fl_sub(Px, Qx, p), p);
     335      594995 :   Rx = Fl_sub(Fl_sub(Fl_sqr(*slope, p), Px, p), Qx, p);
     336      594955 :   Ry = Fl_sub(Fl_mul(*slope, Fl_sub(Px, Rx, p), p), Py, p);
     337      594926 :   return mkvecsmall2(Rx, Ry);
     338             : }
     339             : 
     340             : GEN
     341      672114 : Fle_add(GEN P, GEN Q, ulong a4, ulong p)
     342             : {
     343             :   ulong slope;
     344      672114 :   return Fle_add_slope(P,Q,a4,p,&slope);
     345             : }
     346             : 
     347             : static GEN
     348         112 : Fle_neg(GEN P, ulong p)
     349             : {
     350         112 :   if (ell_is_inf(P)) return P;
     351         112 :   return mkvecsmall2(P[1], Fl_neg(P[2], p));
     352             : }
     353             : 
     354             : GEN
     355           0 : Fle_sub(GEN P, GEN Q, ulong a4, ulong p)
     356             : {
     357           0 :   pari_sp av = avma;
     358             :   ulong slope;
     359           0 :   return gerepileupto(av, Fle_add_slope(P, Fle_neg(Q, p), a4, p, &slope));
     360             : }
     361             : 
     362             : struct _Fle { ulong a4, a6, p; };
     363             : 
     364             : static GEN
     365           0 : _Fle_dbl(void *E, GEN P)
     366             : {
     367           0 :   struct _Fle *ell = (struct _Fle *) E;
     368           0 :   return Fle_dbl(P, ell->a4, ell->p);
     369             : }
     370             : 
     371             : static GEN
     372        7791 : _Fle_add(void *E, GEN P, GEN Q)
     373             : {
     374        7791 :   struct _Fle *ell=(struct _Fle *) E;
     375        7791 :   return Fle_add(P, Q, ell->a4, ell->p);
     376             : }
     377             : 
     378             : GEN
     379     1509143 : Fle_mulu(GEN P, ulong n, ulong a4, ulong p)
     380             : {
     381             :   ulong pi;
     382     1509143 :   if (!n || ell_is_inf(P)) return ellinf();
     383     1509198 :   if (n==1) return zv_copy(P);
     384     1508001 :   if (n==2) return Fle_dbl(P, a4, p);
     385     1164625 :   pi = get_Fl_red(p);
     386     1164624 :   return Flj_to_Fle_pre(Flj_mulu_pre(Fle_to_Flj(P), n, a4, p, pi), p, pi);
     387             : }
     388             : 
     389             : static GEN
     390      872806 : _Fle_mul(void *E, GEN P, GEN n)
     391             : {
     392      872806 :   pari_sp av = avma;
     393      872806 :   struct _Fle *e=(struct _Fle *) E;
     394      872806 :   long s = signe(n);
     395             :   GEN Q;
     396      872806 :   if (!s || ell_is_inf(P)) return ellinf();
     397      872838 :   if (s < 0) P = Fle_neg(P, e->p);
     398      872838 :   if (is_pm1(n)) return s > 0? zv_copy(P): P;
     399      872318 :   Q = (lgefint(n)==3) ? Fle_mulu(P, uel(n,2), e->a4, e->p):
     400             :                         gen_pow(P, n, (void*)e, &_Fle_dbl, &_Fle_add);
     401      872287 :   return s > 0? Q: gerepileuptoleaf(av, Q);
     402             : }
     403             : 
     404             : GEN
     405         133 : Fle_mul(GEN P, GEN n, ulong a4, ulong p)
     406             : {
     407             :   struct _Fle E;
     408         133 :   E.a4 = a4; E.p = p;
     409         133 :   return _Fle_mul(&E, P, n);
     410             : }
     411             : 
     412             : /* Finds a random non-singular point on E */
     413             : GEN
     414     2825227 : random_Fle_pre(ulong a4, ulong a6, ulong p, ulong pi)
     415             : {
     416             :   ulong x, y;
     417     2825227 :   random_Fle_pre_indir(a4, a6, p, pi, &x, &y);
     418     2825227 :   return mkvecsmall2(x, y);
     419             : }
     420             : 
     421             : GEN
     422           0 : random_Fle(ulong a4, ulong a6, ulong p)
     423           0 : { return random_Fle_pre(a4, a6, p, get_Fl_red(p)); }
     424             : 
     425             : static GEN
     426           0 : _Fle_rand(void *E)
     427             : {
     428           0 :   struct _Fle *e=(struct _Fle *) E;
     429           0 :   return random_Fle(e->a4, e->a6, e->p);
     430             : }
     431             : 
     432             : static const struct bb_group Fle_group={_Fle_add,_Fle_mul,_Fle_rand,hash_GEN,zv_equal,ell_is_inf,NULL};
     433             : 
     434             : GEN
     435      219105 : Fle_order(GEN z, GEN o, ulong a4, ulong p)
     436             : {
     437      219105 :   pari_sp av = avma;
     438             :   struct _Fle e;
     439      219105 :   e.a4=a4;
     440      219105 :   e.p=p;
     441      219105 :   return gerepileuptoint(av, gen_order(z, o, (void*)&e, &Fle_group));
     442             : }
     443             : 
     444             : GEN
     445          49 : Fle_log(GEN a, GEN b, GEN o, ulong a4, ulong p)
     446             : {
     447          49 :   pari_sp av = avma;
     448             :   struct _Fle e;
     449          49 :   e.a4=a4;
     450          49 :   e.p=p;
     451          49 :   return gerepileuptoint(av, gen_PH_log(a, b, o, (void*)&e, &Fle_group));
     452             : }
     453             : 
     454             : ulong
     455           0 : Fl_ellj(ulong a4, ulong a6, ulong p)
     456             : {
     457           0 :   if (SMALL_ULONG(p))
     458             :   { /* a43 = 4 a4^3 */
     459           0 :     ulong a43 = Fl_double(Fl_double(Fl_mul(a4, Fl_sqr(a4, p), p), p), p);
     460             :     /* a62 = 27 a6^2 */
     461           0 :     ulong a62 = Fl_mul(Fl_sqr(a6, p), 27 % p, p);
     462           0 :     ulong z1 = Fl_mul(a43, 1728 % p, p);
     463           0 :     ulong z2 = Fl_add(a43, a62, p);
     464           0 :     return Fl_div(z1, z2, p);
     465             :   }
     466           0 :   return Fl_ellj_pre(a4, a6, p, get_Fl_red(p));
     467             : }
     468             : 
     469             : void
     470      122098 : Fl_ellj_to_a4a6(ulong j, ulong p, ulong *pt_a4, ulong *pt_a6)
     471             : {
     472      122098 :   ulong zagier = 1728 % p;
     473      122098 :   if (j == 0)           { *pt_a4 = 0; *pt_a6 =1; }
     474      122098 :   else if (j == zagier) { *pt_a4 = 1; *pt_a6 =0; }
     475             :   else
     476             :   {
     477      122098 :     ulong k = Fl_sub(zagier, j, p);
     478      122097 :     ulong kj = Fl_mul(k, j, p);
     479      122097 :     ulong k2j = Fl_mul(kj, k, p);
     480      122098 :     *pt_a4 = Fl_triple(kj, p);
     481      122098 :     *pt_a6 = Fl_double(k2j, p);
     482             :   }
     483      122099 : }
     484             : 
     485             : ulong
     486     2451080 : Fl_elldisc_pre(ulong a4, ulong a6, ulong p, ulong pi)
     487             : { /* D = -(4A^3 + 27B^2) */
     488             :   ulong t1, t2;
     489     2451080 :   t1 = Fl_mul_pre(a4, Fl_sqr_pre(a4, p, pi), p, pi);
     490     2451080 :   t1 = Fl_double(Fl_double(t1, p), p);
     491     2451080 :   t2 = Fl_mul_pre(27 % p, Fl_sqr_pre(a6, p, pi), p, pi);
     492     2451080 :   return Fl_neg(Fl_add(t1, t2, p), p);
     493             : }
     494             : 
     495             : ulong
     496           0 : Fl_elldisc(ulong a4, ulong a6, ulong p)
     497             : {
     498           0 :   if (SMALL_ULONG(p))
     499             :   { /* D = -(4A^3 + 27B^2) */
     500             :     ulong t1, t2;
     501           0 :     t1 = Fl_mul(a4, Fl_sqr(a4, p), p);
     502           0 :     t1 = Fl_double(Fl_double(t1, p), p);
     503           0 :     t2 = Fl_mul(27 % p, Fl_sqr(a6, p), p);
     504           0 :     return Fl_neg(Fl_add(t1, t2, p), p);
     505             :   }
     506           0 :   return Fl_elldisc_pre(a4, a6, p, get_Fl_red(p));
     507             : }
     508             : 
     509             : void
     510      210416 : Fl_elltwist_disc(ulong a4, ulong a6, ulong D, ulong p, ulong *pa4, ulong *pa6)
     511             : {
     512      210416 :   ulong D2 = Fl_sqr(D, p);
     513      210415 :   *pa4 = Fl_mul(a4, D2, p);
     514      210418 :   *pa6 = Fl_mul(a6, Fl_mul(D, D2, p), p);
     515      210416 : }
     516             : 
     517             : void
     518           0 : Fl_elltwist(ulong a4, ulong a6, ulong p, ulong *pt_a4, ulong *pt_a6)
     519           0 : { Fl_elltwist_disc(a4, a6, nonsquare_Fl(p), p, pt_a4, pt_a6); }
     520             : 
     521             : static void
     522    41739905 : Fle_dbl_sinv_pre_inplace(GEN P, ulong a4, ulong sinv, ulong p, ulong pi)
     523             : {
     524             :   ulong x, y, slope;
     525    41739905 :   if (uel(P,1)==p) return;
     526    41534554 :   if (!P[2]) { P[1] = p; return; }
     527    41411035 :   x = P[1]; y = P[2];
     528    41411035 :   slope = Fl_mul_pre(Fl_add(Fl_triple(Fl_sqr_pre(x, p, pi), p), a4, p),
     529             :                 sinv, p, pi);
     530    41411035 :   P[1] = Fl_sub(Fl_sqr_pre(slope, p, pi), Fl_double(x, p), p);
     531    41411035 :   P[2] = Fl_sub(Fl_mul_pre(slope, Fl_sub(x, P[1], p), p, pi), y, p);
     532             : }
     533             : 
     534             : static void
     535     5496826 : Fle_add_sinv_pre_inplace(GEN P, GEN Q, ulong a4, ulong sinv, ulong p, ulong pi)
     536             : {
     537             :   ulong Px, Py, Qx, Qy, slope;
     538     5496826 :   if (uel(P,1)==p) { P[1] = Q[1]; P[2] = Q[2]; }
     539     5496826 :   if (ell_is_inf(Q)) return;
     540     5496826 :   Px = P[1]; Py = P[2];
     541     5496826 :   Qx = Q[1]; Qy = Q[2];
     542     5496826 :   if (Px==Qx)
     543             :   {
     544       23641 :     if (Py==Qy) Fle_dbl_sinv_pre_inplace(P, a4, sinv, p, pi);
     545       11476 :     else P[1] = p;
     546       23641 :     return;
     547             :   }
     548     5473185 :   slope = Fl_mul_pre(Fl_sub(Py, Qy, p), sinv, p, pi);
     549     5473185 :   P[1] = Fl_sub(Fl_sub(Fl_sqr_pre(slope, p, pi), Px, p), Qx, p);
     550     5473185 :   P[2] = Fl_sub(Fl_mul_pre(slope, Fl_sub(Px, P[1], p), p, pi), Py, p);
     551             : }
     552             : 
     553             : static void
     554     6199654 : Fle_sub_sinv_pre_inplace(GEN P, GEN Q, ulong a4, ulong sinv, ulong p, ulong pi)
     555             : {
     556             :   ulong Px, Py, Qx, Qy, slope;
     557     6199654 :   if (uel(P,1)==p) { P[1] = Q[1]; P[2] = Fl_neg(Q[2], p); }
     558     6199654 :   if (ell_is_inf(Q)) return;
     559     6199654 :   Px = P[1]; Py = P[2];
     560     6199654 :   Qx = Q[1]; Qy = Q[2];
     561     6199654 :   if (Px==Qx)
     562             :   {
     563       27432 :     if (Py==Qy) P[1] = p;
     564             :     else
     565       10726 :       Fle_dbl_sinv_pre_inplace(P, a4, sinv, p, pi);
     566       27432 :     return;
     567             :   }
     568     6172222 :   slope = Fl_mul_pre(Fl_add(Py, Qy, p), sinv, p, pi);
     569     6172222 :   P[1] = Fl_sub(Fl_sub(Fl_sqr_pre(slope, p, pi), Px, p), Qx, p);
     570     6172222 :   P[2] = Fl_sub(Fl_mul_pre(slope, Fl_sub(Px, P[1], p), p, pi), Py, p);
     571             : }
     572             : 
     573             : static long
     574    53186665 : skipzero(long n) { return n ? n:1; }
     575             : 
     576             : void
     577      954749 : FleV_add_pre_inplace(GEN P, GEN Q, GEN a4, ulong p, ulong pi)
     578             : {
     579      954749 :   long i, l=lg(a4);
     580      954749 :   GEN sinv = cgetg(l, t_VECSMALL);
     581     6451575 :   for(i=1; i<l; i++)
     582     5496826 :     uel(sinv,i) = umael(P,i,1)==p? 1: skipzero(Fl_sub(mael(P,i,1), mael(Q,i,1), p));
     583      954749 :   Flv_inv_pre_inplace(sinv, p, pi);
     584     6451575 :   for (i=1; i<l; i++)
     585     5496826 :     Fle_add_sinv_pre_inplace(gel(P,i), gel(Q,i), uel(a4,i), uel(sinv,i), p, pi);
     586      954749 : }
     587             : 
     588             : void
     589     1093093 : FleV_sub_pre_inplace(GEN P, GEN Q, GEN a4, ulong p, ulong pi)
     590             : {
     591     1093093 :   long i, l=lg(a4);
     592     1093093 :   GEN sinv = cgetg(l, t_VECSMALL);
     593     7292747 :   for(i=1; i<l; i++)
     594     6199654 :     uel(sinv,i) = umael(P,i,1)==p? 1: skipzero(Fl_sub(mael(P,i,1), mael(Q,i,1), p));
     595     1093093 :   Flv_inv_pre_inplace(sinv, p, pi);
     596     7292747 :   for (i=1; i<l; i++)
     597     6199654 :     Fle_sub_sinv_pre_inplace(gel(P,i), gel(Q,i), uel(a4,i), uel(sinv,i), p, pi);
     598     1093093 : }
     599             : 
     600             : void
     601     7588438 : FleV_dbl_pre_inplace(GEN P, GEN a4, ulong p, ulong pi)
     602             : {
     603     7588438 :   long i, l=lg(a4);
     604     7588438 :   GEN sinv = cgetg(l, t_VECSMALL);
     605    49305452 :   for(i=1; i<l; i++)
     606    41717014 :     uel(sinv,i) = umael(P,i,1)==p? 1: skipzero(Fl_double(umael(P,i,2), p));
     607     7588438 :   Flv_inv_pre_inplace(sinv, p, pi);
     608    49305452 :   for(i=1; i<l; i++)
     609    41717014 :     Fle_dbl_sinv_pre_inplace(gel(P,i), uel(a4,i), uel(sinv,i), p, pi);
     610     7588438 : }
     611             : 
     612             : static void
     613      623995 : FleV_mulu_pre_naf_inplace(GEN P, ulong n, GEN a4, ulong p, ulong pi, const naf_t *x)
     614             : {
     615      623995 :   pari_sp av = avma;
     616             :   ulong pbits, nbits, m;
     617             :   GEN R;
     618      623995 :   if (n == 1) return;
     619             : 
     620      623995 :   R = P; P = gcopy(P);
     621      623995 :   FleV_dbl_pre_inplace(R, a4, p, pi);
     622      623995 :   if (n == 2) return;
     623             : 
     624      623892 :   pbits = x->pbits;
     625      623892 :   nbits = x->nbits;
     626      623892 :   m = (1UL << x->lnzb);
     627     7588335 :   for ( ; m; m >>= 1) {
     628     6964443 :     FleV_dbl_pre_inplace(R, a4, p, pi);
     629     6964443 :     if (m & pbits)
     630      954749 :       FleV_add_pre_inplace(R, P, a4, p, pi);
     631     6009694 :     else if (m & nbits)
     632     1093093 :       FleV_sub_pre_inplace(R, P, a4, p, pi);
     633             :   }
     634      623892 :   set_avma(av);
     635             : }
     636             : 
     637             : void
     638      623995 : FleV_mulu_pre_inplace(GEN P, ulong n, GEN a4, ulong p, ulong pi)
     639             : {
     640      623995 :   naf_t x; naf_repr(&x, n);
     641      623995 :   FleV_mulu_pre_naf_inplace(P, n, a4, p, pi, &x);
     642      623995 : }

Generated by: LCOV version 1.13