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 23036-b751c0af5) Lines: 292 334 87.4 %
Date: 2018-09-26 05:46:06 Functions: 39 48 81.2 %
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    20685195 : 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    20685195 :   X1 = P[1]; Y1 = P[2]; Z1 = P[3];
      40             : 
      41    20685195 :   if (Z1 == 0) { Q[1] = X1; Q[2] = Y1; Q[3] = Z1; return; }
      42             : 
      43    20545766 :   XX = Fl_sqr_pre(X1, p, pi);
      44    20545149 :   YY = Fl_sqr_pre(Y1, p, pi);
      45    20543827 :   YYYY = Fl_sqr_pre(YY, p, pi);
      46    20543513 :   ZZ = Fl_sqr_pre(Z1, p, pi);
      47    20543679 :   S = Fl_double(Fl_sub(Fl_sqr_pre(Fl_add(X1, YY, p), p, pi),
      48             :                        Fl_add(XX, YYYY, p), p), p);
      49    20543102 :   M = Fl_addmul_pre(Fl_triple(XX, p), a4, Fl_sqr_pre(ZZ, p, pi), p, pi);
      50    20545318 :   T = Fl_sub(Fl_sqr_pre(M, p, pi), Fl_double(S, p), p);
      51    20544166 :   Q[1] = T;
      52    20544166 :   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    20543858 :   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    17543181 : Flj_dbl_pre_inplace(GEN P, ulong a4, ulong p, ulong pi)
      60             : {
      61    17543181 :   Flj_dbl_indir_pre(P, P, a4, p, pi);
      62    17542971 : }
      63             : 
      64             : GEN
      65     3139453 : Flj_dbl_pre(GEN P, ulong a4, ulong p, ulong pi)
      66             : {
      67     3139453 :   GEN Q = cgetg(4, t_VECSMALL);
      68     3139428 :   Flj_dbl_indir_pre(P, Q, a4, p, pi);
      69     3139386 :   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     6202344 : 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     6202344 :   X1 = P[1]; Y1 = P[2]; Z1 = P[3];
      80     6202344 :   X2 = Q[1]; Y2 = Q[2]; Z2 = Q[3];
      81             : 
      82     6202344 :   if (Z2 == 0) { R[1] = X1; R[2] = Y1; R[3] = Z1; return; }
      83     6202235 :   if (Z1 == 0) { R[1] = X2; R[2] = Y2; R[3] = Z2; return; }
      84             : 
      85     6192183 :   Z1Z1 = Fl_sqr_pre(Z1, p, pi);
      86     6192035 :   Z2Z2 = Fl_sqr_pre(Z2, p, pi);
      87     6191940 :   U1 = Fl_mul_pre(X1, Z2Z2, p, pi);
      88     6191944 :   U2 = Fl_mul_pre(X2, Z1Z1, p, pi);
      89     6191981 :   S1 = Fl_mul_pre(Y1, Fl_mul_pre(Z2, Z2Z2, p, pi), p, pi);
      90     6191936 :   S2 = Fl_mul_pre(Y2, Fl_mul_pre(Z1, Z1Z1, p, pi), p, pi);
      91     6191972 :   H = Fl_sub(U2, U1, p);
      92     6191947 :   r = Fl_double(Fl_sub(S2, S1, p), p);
      93             : 
      94     6191977 :   if (H == 0) {
      95      469572 :     if (r == 0) Flj_dbl_indir_pre(P, R, a4, p, pi); /* P = Q */
      96      467052 :     else { R[1] = R[2] = 1; R[3] = 0; } /* P = -Q */
      97      469572 :     return;
      98             :   }
      99     5722405 :   I = Fl_sqr_pre(Fl_double(H, p), p, pi);
     100     5722545 :   J = Fl_mul_pre(H, I, p, pi);
     101     5722471 :   V = Fl_mul_pre(U1, I, p, pi);
     102     5722454 :   W = Fl_sub(Fl_sqr_pre(r, p, pi), Fl_add(J, Fl_double(V, p), p), p);
     103     5722448 :   R[1] = W;
     104     5722448 :   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     5722399 :   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     6202034 : Flj_add_pre_inplace(GEN P, GEN Q, ulong a4, ulong p, ulong pi)
     112     6202034 : { 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     1937351 : Flj_neg(GEN Q, ulong p)
     124     1937351 : { 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     3504872 : naf_repr(naf_t *x, ulong a)
     136             : {
     137     3504872 :   ulong pbits = 0, nbits = 0, c0 = 0, c1, a0;
     138             :   long t, i;
     139             : 
     140    32930711 :   for (i = 0; a; a >>= 1, ++i) {
     141    29425839 :     a0 = a & 1;
     142    29425839 :     c1 = (c0 + a0 + ((a & 2) >> 1)) >> 1;
     143    29425839 :     t = c0 + a0 - (c1 << 1);
     144    29425839 :     if (t < 0)
     145     4532336 :       nbits |= (1UL << i);
     146    24893503 :     else if (t > 0)
     147     5378252 :       pbits |= (1UL << i);
     148    29425839 :     c0 = c1;
     149             :   }
     150     3504872 :   c1 = c0 >> 1;
     151     3504872 :   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     3504872 :   if (t > 0 && i != BITS_IN_LONG) pbits |= (1UL << i);
     155     3504872 :   x->pbits = pbits;
     156     3504872 :   x->nbits = nbits;
     157     3504872 :   x->lnzb = t? i-2: i-3;
     158     3504872 : }
     159             : 
     160             : /* Standard left-to-right signed double-and-add to compute [n]P. */
     161             : static GEN
     162     3386276 : 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     3386276 :   if (n == 0) return mkvecsmall3(1, 1, 0);
     169     3386244 :   if (n == 1) return Flv_copy(P);
     170             : 
     171     3139456 :   R = Flj_dbl_pre(P, a4, p, pi);
     172     3139393 :   if (n == 2) return R;
     173             : 
     174     2435856 :   pbits = x->pbits;
     175     2435856 :   nbits = x->nbits;
     176     2435856 :   Pi = nbits? Flj_neg(P, p): NULL;
     177     2435944 :   m = (1UL << x->lnzb);
     178    19979222 :   for ( ; m; m >>= 1) {
     179    17543342 :     Flj_dbl_pre_inplace(R, a4, p, pi);
     180    17544370 :     if (m & pbits)
     181     2725214 :       Flj_add_pre_inplace(R, P, a4, p, pi);
     182    14819156 :     else if (m & nbits)
     183     3477209 :       Flj_add_pre_inplace(R, Pi, a4, p, pi);
     184             :   }
     185     2435880 :   avma = (pari_sp)R; return R;
     186             : }
     187             : 
     188             : GEN
     189     2323812 : Flj_mulu_pre(GEN P, ulong n, ulong a4, ulong p, ulong pi)
     190             : {
     191     2323812 :   naf_t x; naf_repr(&x, n);
     192     2323868 :   return Flj_mulu_pre_naf(P, n, a4, p, pi, &x);
     193             : }
     194             : 
     195             : ulong
     196      245053 : Flj_order_ufact(GEN P, ulong n, GEN F, ulong a4, ulong p, ulong pi)
     197             : {
     198      245053 :   pari_sp av = avma;
     199      245053 :   ulong res = 1;
     200             :   long i, nfactors;
     201             :   GEN primes, exps;
     202             : 
     203      245053 :   primes = gel(F, 1);
     204      245053 :   nfactors = lg(primes);
     205      245053 :   exps = gel(F, 2);
     206             : 
     207      699704 :   for (i = 1; i < nfactors; ++i) {
     208      560259 :     ulong q, pp = primes[i];
     209      560259 :     long j, k, ei = exps[i];
     210             :     naf_t x;
     211             :     GEN b;
     212             : 
     213      560259 :     for (q = pp, j = 1; j < ei; ++j) q *= pp;
     214      560259 :     b = Flj_mulu_pre(P, n / q, a4, p, pi);
     215             : 
     216      560259 :     naf_repr(&x, pp);
     217     1622670 :     for (j = 0; j < ei && b[3]; ++j)
     218     1062411 :       b = Flj_mulu_pre_naf(b, pp, a4, p, pi, &x);
     219      560259 :     if (b[3]) return 0;
     220      454651 :     for (k = 0; k < j; ++k) res *= pp;
     221      454651 :     set_avma(av);
     222             :   }
     223      139445 :   return res;
     224             : }
     225             : 
     226             : GEN
     227     1164732 : Fle_to_Flj(GEN P)
     228     2329464 : { return ell_is_inf(P) ? mkvecsmall3(1UL, 1UL, 0UL):
     229     1164732 :                          mkvecsmall3(P[1], P[2], 1UL);
     230             : }
     231             : 
     232             : GEN
     233     1164732 : Flj_to_Fle_pre(GEN P, ulong p, ulong pi)
     234             : {
     235     1164732 :   if (P[3] == 0) return ellinf();
     236             :   else
     237             :   {
     238     1055642 :     ulong Z = Fl_inv(P[3], p);
     239     1055642 :     ulong Z2 = Fl_sqr_pre(Z, p, pi);
     240     1055642 :     ulong X3 = Fl_mul_pre(P[1], Z2, p, pi);
     241     1055642 :     ulong Y3 = Fl_mul_pre(P[2], Fl_mul_pre(Z, Z2, p, pi), p, pi);
     242     1055642 :     return mkvecsmall2(X3, Y3);
     243             :   }
     244             : }
     245             : 
     246             : INLINE void
     247     6469927 : 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     6469927 :     x   = random_Fl(p); /*  x^3+a4*x+a6 = x*(x^2+a4)+a6  */
     254     6469972 :     x2  = Fl_sqr_pre(x, p, pi);
     255     6469938 :     rhs = Fl_addmul_pre(a6, x, Fl_add(x2, a4, p), p, pi);
     256     6469944 :   } while ((!rhs && !Fl_add(Fl_triple(x2,p),a4,p)) || krouu(rhs, p) < 0);
     257     3241795 :   y = Fl_sqrt_pre(rhs, p, pi);
     258     3241803 :   *pt_x = x; *pt_y = y;
     259     3241803 : }
     260             : 
     261             : GEN
     262      415607 : random_Flj_pre(ulong a4, ulong a6, ulong p, ulong pi)
     263             : {
     264             :   ulong x, y;
     265      415607 :   random_Fle_pre_indir(a4, a6, p, pi, &x, &y);
     266      415616 :   return mkvecsmall3(x, y, 1);
     267             : }
     268             : 
     269             : /***********************************************************************/
     270             : /**                                                                   **/
     271             : /**                              Fle                                  **/
     272             : /**                                                                   **/
     273             : /***********************************************************************/
     274             : GEN
     275           0 : Fle_changepoint(GEN x, GEN ch, ulong p)
     276             : {
     277             :   ulong p1,u,r,s,t,v,v2,v3;
     278             :   GEN z;
     279           0 :   if (ell_is_inf(x)) return x;
     280           0 :   u = ch[1]; r = ch[2];
     281           0 :   s = ch[3]; t = ch[4];
     282           0 :   v = Fl_inv(u, p); v2 = Fl_sqr(v,p); v3 = Fl_mul(v,v2,p);
     283           0 :   p1 = Fl_sub(x[1],r,p);
     284           0 :   z = cgetg(3,t_VECSMALL);
     285           0 :   z[1] = Fl_mul(v2, p1, p);
     286           0 :   z[2] = Fl_mul(v3, Fl_sub(x[2], Fl_add(Fl_mul(s,p1, p),t, p),p),p);
     287           0 :   return z;
     288             : }
     289             : 
     290             : GEN
     291         294 : Fle_changepointinv(GEN x, GEN ch, ulong p)
     292             : {
     293             :   ulong u, r, s, t, X, Y, u2, u3, u2X;
     294             :   GEN z;
     295         294 :   if (ell_is_inf(x)) return x;
     296         294 :   X = x[1]; Y = x[2];
     297         294 :   u = ch[1]; r = ch[2];
     298         294 :   s = ch[3]; t = ch[4];
     299         294 :   u2 = Fl_sqr(u, p); u3 = Fl_mul(u,u2,p);
     300         294 :   u2X = Fl_mul(u2,X, p);
     301         294 :   z = cgetg(3, t_VECSMALL);
     302         294 :   z[1] = Fl_add(u2X,r,p);
     303         294 :   z[2] = Fl_add(Fl_mul(u3,Y,p), Fl_add(Fl_mul(s,u2X,p), t, p), p);
     304         294 :   return z;
     305             : }
     306             : static GEN
     307      420778 : Fle_dbl_slope(GEN P, ulong a4, ulong p, ulong *slope)
     308             : {
     309             :   ulong x, y, Qx, Qy;
     310      420778 :   if (ell_is_inf(P) || !P[2]) return ellinf();
     311      368211 :   x = P[1]; y = P[2];
     312      368211 :   *slope = Fl_div(Fl_add(Fl_triple(Fl_sqr(x,p), p), a4, p),
     313             :                   Fl_double(y, p), p);
     314      368211 :   Qx = Fl_sub(Fl_sqr(*slope, p), Fl_double(x, p), p);
     315      368209 :   Qy = Fl_sub(Fl_mul(*slope, Fl_sub(x, Qx, p), p), y, p);
     316      368210 :   return mkvecsmall2(Qx, Qy);
     317             : }
     318             : 
     319             : GEN
     320      343543 : Fle_dbl(GEN P, ulong a4, ulong p)
     321             : {
     322             :   ulong slope;
     323      343543 :   return Fle_dbl_slope(P,a4,p,&slope);
     324             : }
     325             : 
     326             : static GEN
     327      672560 : Fle_add_slope(GEN P, GEN Q, ulong a4, ulong p, ulong *slope)
     328             : {
     329             :   ulong Px, Py, Qx, Qy, Rx, Ry;
     330      672560 :   if (ell_is_inf(P)) return Q;
     331      672580 :   if (ell_is_inf(Q)) return P;
     332      672605 :   Px = P[1]; Py = P[2];
     333      672605 :   Qx = Q[1]; Qy = Q[2];
     334      672605 :   if (Px==Qx) return Py==Qy ? Fle_dbl_slope(P, a4, p, slope): ellinf();
     335      595301 :   *slope = Fl_div(Fl_sub(Py, Qy, p), Fl_sub(Px, Qx, p), p);
     336      595372 :   Rx = Fl_sub(Fl_sub(Fl_sqr(*slope, p), Px, p), Qx, p);
     337      595322 :   Ry = Fl_sub(Fl_mul(*slope, Fl_sub(Px, Rx, p), p), Py, p);
     338      595315 :   return mkvecsmall2(Rx, Ry);
     339             : }
     340             : 
     341             : GEN
     342      672536 : Fle_add(GEN P, GEN Q, ulong a4, ulong p)
     343             : {
     344             :   ulong slope;
     345      672536 :   return Fle_add_slope(P,Q,a4,p,&slope);
     346             : }
     347             : 
     348             : static GEN
     349          98 : Fle_neg(GEN P, ulong p)
     350             : {
     351          98 :   if (ell_is_inf(P)) return P;
     352          98 :   return mkvecsmall2(P[1], Fl_neg(P[2], p));
     353             : }
     354             : 
     355             : GEN
     356           0 : Fle_sub(GEN P, GEN Q, ulong a4, ulong p)
     357             : {
     358           0 :   pari_sp av = avma;
     359             :   ulong slope;
     360           0 :   return gerepileupto(av, Fle_add_slope(P, Fle_neg(Q, p), a4, p, &slope));
     361             : }
     362             : 
     363             : struct _Fle { ulong a4, a6, p; };
     364             : 
     365             : static GEN
     366           0 : _Fle_dbl(void *E, GEN P)
     367             : {
     368           0 :   struct _Fle *ell = (struct _Fle *) E;
     369           0 :   return Fle_dbl(P, ell->a4, ell->p);
     370             : }
     371             : 
     372             : static GEN
     373        7777 : _Fle_add(void *E, GEN P, GEN Q)
     374             : {
     375        7777 :   struct _Fle *ell=(struct _Fle *) E;
     376        7777 :   return Fle_add(P, Q, ell->a4, ell->p);
     377             : }
     378             : 
     379             : GEN
     380     1509311 : Fle_mulu(GEN P, ulong n, ulong a4, ulong p)
     381             : {
     382             :   ulong pi;
     383     1509311 :   if (!n || ell_is_inf(P)) return ellinf();
     384     1509311 :   if (n==1) return zv_copy(P);
     385     1508114 :   if (n==2) return Fle_dbl(P, a4, p);
     386     1164732 :   pi = get_Fl_red(p);
     387     1164732 :   return Flj_to_Fle_pre(Flj_mulu_pre(Fle_to_Flj(P), n, a4, p, pi), p, pi);
     388             : }
     389             : 
     390             : static GEN
     391      872906 : _Fle_mul(void *E, GEN P, GEN n)
     392             : {
     393      872906 :   pari_sp av = avma;
     394      872906 :   struct _Fle *e=(struct _Fle *) E;
     395      872906 :   long s = signe(n);
     396             :   GEN Q;
     397      872906 :   if (!s || ell_is_inf(P)) return ellinf();
     398      872892 :   if (s < 0) P = Fle_neg(P, e->p);
     399      872892 :   if (is_pm1(n)) return s > 0? zv_copy(P): P;
     400      872402 :   Q = (lgefint(n)==3) ? Fle_mulu(P, uel(n,2), e->a4, e->p):
     401             :                         gen_pow(P, n, (void*)e, &_Fle_dbl, &_Fle_add);
     402      872402 :   return s > 0? Q: gerepileuptoleaf(av, Q);
     403             : }
     404             : 
     405             : GEN
     406         133 : Fle_mul(GEN P, GEN n, ulong a4, ulong p)
     407             : {
     408             :   struct _Fle E;
     409         133 :   E.a4 = a4; E.p = p;
     410         133 :   return _Fle_mul(&E, P, n);
     411             : }
     412             : 
     413             : /* Finds a random non-singular point on E */
     414             : GEN
     415     2826186 : random_Fle_pre(ulong a4, ulong a6, ulong p, ulong pi)
     416             : {
     417             :   ulong x, y;
     418     2826186 :   random_Fle_pre_indir(a4, a6, p, pi, &x, &y);
     419     2826186 :   return mkvecsmall2(x, y);
     420             : }
     421             : 
     422             : GEN
     423           0 : random_Fle(ulong a4, ulong a6, ulong p)
     424           0 : { return random_Fle_pre(a4, a6, p, get_Fl_red(p)); }
     425             : 
     426             : static GEN
     427           0 : _Fle_rand(void *E)
     428             : {
     429           0 :   struct _Fle *e=(struct _Fle *) E;
     430           0 :   return random_Fle(e->a4, e->a6, e->p);
     431             : }
     432             : 
     433             : static const struct bb_group Fle_group={_Fle_add,_Fle_mul,_Fle_rand,hash_GEN,zv_equal,ell_is_inf,NULL};
     434             : 
     435             : GEN
     436      219106 : Fle_order(GEN z, GEN o, ulong a4, ulong p)
     437             : {
     438      219106 :   pari_sp av = avma;
     439             :   struct _Fle e;
     440      219106 :   e.a4=a4;
     441      219106 :   e.p=p;
     442      219106 :   return gerepileuptoint(av, gen_order(z, o, (void*)&e, &Fle_group));
     443             : }
     444             : 
     445             : GEN
     446          42 : Fle_log(GEN a, GEN b, GEN o, ulong a4, ulong p)
     447             : {
     448          42 :   pari_sp av = avma;
     449             :   struct _Fle e;
     450          42 :   e.a4=a4;
     451          42 :   e.p=p;
     452          42 :   return gerepileuptoint(av, gen_PH_log(a, b, o, (void*)&e, &Fle_group));
     453             : }
     454             : 
     455             : ulong
     456           0 : Fl_ellj(ulong a4, ulong a6, ulong p)
     457             : {
     458           0 :   if (SMALL_ULONG(p))
     459             :   { /* a43 = 4 a4^3 */
     460           0 :     ulong a43 = Fl_double(Fl_double(Fl_mul(a4, Fl_sqr(a4, p), p), p), p);
     461             :     /* a62 = 27 a6^2 */
     462           0 :     ulong a62 = Fl_mul(Fl_sqr(a6, p), 27 % p, p);
     463           0 :     ulong z1 = Fl_mul(a43, 1728 % p, p);
     464           0 :     ulong z2 = Fl_add(a43, a62, p);
     465           0 :     return Fl_div(z1, z2, p);
     466             :   }
     467           0 :   return Fl_ellj_pre(a4, a6, p, get_Fl_red(p));
     468             : }
     469             : 
     470             : void
     471      130180 : Fl_ellj_to_a4a6(ulong j, ulong p, ulong *pt_a4, ulong *pt_a6)
     472             : {
     473      130180 :   ulong zagier = 1728 % p;
     474      130180 :   if (j == 0)           { *pt_a4 = 0; *pt_a6 =1; }
     475      130180 :   else if (j == zagier) { *pt_a4 = 1; *pt_a6 =0; }
     476             :   else
     477             :   {
     478      130180 :     ulong k = Fl_sub(zagier, j, p);
     479      130180 :     ulong kj = Fl_mul(k, j, p);
     480      130178 :     ulong k2j = Fl_mul(kj, k, p);
     481      130180 :     *pt_a4 = Fl_triple(kj, p);
     482      130179 :     *pt_a6 = Fl_double(k2j, p);
     483             :   }
     484      130180 : }
     485             : 
     486             : ulong
     487     2439464 : Fl_elldisc_pre(ulong a4, ulong a6, ulong p, ulong pi)
     488             : { /* D = -(4A^3 + 27B^2) */
     489             :   ulong t1, t2;
     490     2439464 :   t1 = Fl_mul_pre(a4, Fl_sqr_pre(a4, p, pi), p, pi);
     491     2439464 :   t1 = Fl_double(Fl_double(t1, p), p);
     492     2439464 :   t2 = Fl_mul_pre(27 % p, Fl_sqr_pre(a6, p, pi), p, pi);
     493     2439464 :   return Fl_neg(Fl_add(t1, t2, p), p);
     494             : }
     495             : 
     496             : ulong
     497           0 : Fl_elldisc(ulong a4, ulong a6, ulong p)
     498             : {
     499           0 :   if (SMALL_ULONG(p))
     500             :   { /* D = -(4A^3 + 27B^2) */
     501             :     ulong t1, t2;
     502           0 :     t1 = Fl_mul(a4, Fl_sqr(a4, p), p);
     503           0 :     t1 = Fl_double(Fl_double(t1, p), p);
     504           0 :     t2 = Fl_mul(27 % p, Fl_sqr(a6, p), p);
     505           0 :     return Fl_neg(Fl_add(t1, t2, p), p);
     506             :   }
     507           0 :   return Fl_elldisc_pre(a4, a6, p, get_Fl_red(p));
     508             : }
     509             : 
     510             : void
     511      210143 : Fl_elltwist_disc(ulong a4, ulong a6, ulong D, ulong p, ulong *pa4, ulong *pa6)
     512             : {
     513      210143 :   ulong D2 = Fl_sqr(D, p);
     514      210143 :   *pa4 = Fl_mul(a4, D2, p);
     515      210144 :   *pa6 = Fl_mul(a6, Fl_mul(D, D2, p), p);
     516      210146 : }
     517             : 
     518             : void
     519           0 : Fl_elltwist(ulong a4, ulong a6, ulong p, ulong *pt_a4, ulong *pt_a6)
     520           0 : { Fl_elltwist_disc(a4, a6, nonsquare_Fl(p), p, pt_a4, pt_a6); }
     521             : 
     522             : static void
     523    41560911 : Fle_dbl_sinv_pre_inplace(GEN P, ulong a4, ulong sinv, ulong p, ulong pi)
     524             : {
     525             :   ulong x, y, slope;
     526    41560911 :   if (uel(P,1)==p) return;
     527    41356941 :   if (!P[2]) { P[1] = p; return; }
     528    41234517 :   x = P[1]; y = P[2];
     529    41234517 :   slope = Fl_mul_pre(Fl_add(Fl_triple(Fl_sqr_pre(x, p, pi), p), a4, p),
     530             :                 sinv, p, pi);
     531    41234517 :   P[1] = Fl_sub(Fl_sqr_pre(slope, p, pi), Fl_double(x, p), p);
     532    41234517 :   P[2] = Fl_sub(Fl_mul_pre(slope, Fl_sub(x, P[1], p), p, pi), y, p);
     533             : }
     534             : 
     535             : static void
     536     5494593 : Fle_add_sinv_pre_inplace(GEN P, GEN Q, ulong a4, ulong sinv, ulong p, ulong pi)
     537             : {
     538             :   ulong Px, Py, Qx, Qy, slope;
     539     5494593 :   if (uel(P,1)==p) { P[1] = Q[1]; P[2] = Q[2]; }
     540     5494593 :   if (ell_is_inf(Q)) return;
     541     5494593 :   Px = P[1]; Py = P[2];
     542     5494593 :   Qx = Q[1]; Qy = Q[2];
     543     5494593 :   if (Px==Qx)
     544             :   {
     545       22678 :     if (Py==Qy) Fle_dbl_sinv_pre_inplace(P, a4, sinv, p, pi);
     546       11112 :     else P[1] = p;
     547       22678 :     return;
     548             :   }
     549     5471915 :   slope = Fl_mul_pre(Fl_sub(Py, Qy, p), sinv, p, pi);
     550     5471915 :   P[1] = Fl_sub(Fl_sub(Fl_sqr_pre(slope, p, pi), Px, p), Qx, p);
     551     5471915 :   P[2] = Fl_sub(Fl_mul_pre(slope, Fl_sub(Px, P[1], p), p, pi), Py, p);
     552             : }
     553             : 
     554             : static void
     555     6159246 : Fle_sub_sinv_pre_inplace(GEN P, GEN Q, ulong a4, ulong sinv, ulong p, ulong pi)
     556             : {
     557             :   ulong Px, Py, Qx, Qy, slope;
     558     6159246 :   if (uel(P,1)==p) { P[1] = Q[1]; P[2] = Fl_neg(Q[2], p); }
     559     6159246 :   if (ell_is_inf(Q)) return;
     560     6159246 :   Px = P[1]; Py = P[2];
     561     6159246 :   Qx = Q[1]; Qy = Q[2];
     562     6159246 :   if (Px==Qx)
     563             :   {
     564       27223 :     if (Py==Qy) P[1] = p;
     565             :     else
     566       10325 :       Fle_dbl_sinv_pre_inplace(P, a4, sinv, p, pi);
     567       27223 :     return;
     568             :   }
     569     6132023 :   slope = Fl_mul_pre(Fl_add(Py, Qy, p), sinv, p, pi);
     570     6132023 :   P[1] = Fl_sub(Fl_sub(Fl_sqr_pre(slope, p, pi), Px, p), Qx, p);
     571     6132023 :   P[2] = Fl_sub(Fl_mul_pre(slope, Fl_sub(Px, P[1], p), p, pi), Py, p);
     572             : }
     573             : 
     574             : static long
     575    52968113 : skipzero(long n) { return n ? n:1; }
     576             : 
     577             : void
     578      951165 : FleV_add_pre_inplace(GEN P, GEN Q, GEN a4, ulong p, ulong pi)
     579             : {
     580      951165 :   long i, l=lg(a4);
     581      951165 :   GEN sinv = cgetg(l, t_VECSMALL);
     582     6445758 :   for(i=1; i<l; i++)
     583     5494593 :     uel(sinv,i) = umael(P,i,1)==p? 1: skipzero(Fl_sub(mael(P,i,1), mael(Q,i,1), p));
     584      951165 :   Flv_inv_pre_inplace(sinv, p, pi);
     585     6445758 :   for (i=1; i<l; i++)
     586     5494593 :     Fle_add_sinv_pre_inplace(gel(P,i), gel(Q,i), uel(a4,i), uel(sinv,i), p, pi);
     587      951165 : }
     588             : 
     589             : void
     590     1087892 : FleV_sub_pre_inplace(GEN P, GEN Q, GEN a4, ulong p, ulong pi)
     591             : {
     592     1087892 :   long i, l=lg(a4);
     593     1087892 :   GEN sinv = cgetg(l, t_VECSMALL);
     594     7247138 :   for(i=1; i<l; i++)
     595     6159246 :     uel(sinv,i) = umael(P,i,1)==p? 1: skipzero(Fl_sub(mael(P,i,1), mael(Q,i,1), p));
     596     1087892 :   Flv_inv_pre_inplace(sinv, p, pi);
     597     7247138 :   for (i=1; i<l; i++)
     598     6159246 :     Fle_sub_sinv_pre_inplace(gel(P,i), gel(Q,i), uel(a4,i), uel(sinv,i), p, pi);
     599     1087892 : }
     600             : 
     601             : void
     602     7565264 : FleV_dbl_pre_inplace(GEN P, GEN a4, ulong p, ulong pi)
     603             : {
     604     7565264 :   long i, l=lg(a4);
     605     7565264 :   GEN sinv = cgetg(l, t_VECSMALL);
     606    49104284 :   for(i=1; i<l; i++)
     607    41539020 :     uel(sinv,i) = umael(P,i,1)==p? 1: skipzero(Fl_double(umael(P,i,2), p));
     608     7565264 :   Flv_inv_pre_inplace(sinv, p, pi);
     609    49104284 :   for(i=1; i<l; i++)
     610    41539020 :     Fle_dbl_sinv_pre_inplace(gel(P,i), uel(a4,i), uel(sinv,i), p, pi);
     611     7565264 : }
     612             : 
     613             : static void
     614      620733 : FleV_mulu_pre_naf_inplace(GEN P, ulong n, GEN a4, ulong p, ulong pi, const naf_t *x)
     615             : {
     616      620733 :   pari_sp av = avma;
     617             :   ulong pbits, nbits, m;
     618             :   GEN R;
     619      620733 :   if (n == 1) return;
     620             : 
     621      620733 :   R = P; P = gcopy(P);
     622      620733 :   FleV_dbl_pre_inplace(R, a4, p, pi);
     623      620733 :   if (n == 2) return;
     624             : 
     625      620629 :   pbits = x->pbits;
     626      620629 :   nbits = x->nbits;
     627      620629 :   m = (1UL << x->lnzb);
     628     7565160 :   for ( ; m; m >>= 1) {
     629     6944531 :     FleV_dbl_pre_inplace(R, a4, p, pi);
     630     6944531 :     if (m & pbits)
     631      951165 :       FleV_add_pre_inplace(R, P, a4, p, pi);
     632     5993366 :     else if (m & nbits)
     633     1087892 :       FleV_sub_pre_inplace(R, P, a4, p, pi);
     634             :   }
     635      620629 :   set_avma(av);
     636             : }
     637             : 
     638             : void
     639      620733 : FleV_mulu_pre_inplace(GEN P, ulong n, GEN a4, ulong p, ulong pi)
     640             : {
     641      620733 :   naf_t x; naf_repr(&x, n);
     642      620733 :   FleV_mulu_pre_naf_inplace(P, n, a4, p, pi, &x);
     643      620733 : }

Generated by: LCOV version 1.13