Code coverage tests

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

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

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

LCOV - code coverage report
Current view: top level - basemath - Fle.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.10.0 lcov report (development 21059-cbe0d6a) Lines: 232 279 83.2 %
Date: 2017-09-22 06:24:58 Functions: 30 40 75.0 %
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 used in Fle_mulu().
      30             :  */
      31             : 
      32             : /*
      33             :  * Cost: 1M + 8S + 1*a + 10add + 1*8 + 2*2 + 1*3.
      34             :  * Source: http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-2007-bl
      35             :  */
      36             : 
      37             : INLINE void
      38    91881925 : Flj_dbl_indir_pre(GEN P, GEN Q, ulong a4, ulong p, ulong pi)
      39             : {
      40             :   ulong X1, Y1, Z1;
      41             :   ulong XX, YY, YYYY, ZZ, S, M, T;
      42             : 
      43    91881925 :   X1 = P[1]; Y1 = P[2]; Z1 = P[3];
      44             : 
      45    91881925 :   if (Z1 == 0)
      46             :   {
      47      238330 :     Q[1] = X1; Q[2] = Y1; Q[3] = Z1;
      48    92115522 :     return;
      49             :   }
      50             : 
      51    91643595 :   XX = Fl_sqr_pre(X1, p, pi);
      52    91640253 :   YY = Fl_sqr_pre(Y1, p, pi);
      53    91640210 :   YYYY = Fl_sqr_pre(YY, p, pi);
      54    91640330 :   ZZ = Fl_sqr_pre(Z1, p, pi);
      55    91640329 :   S = Fl_double(Fl_sub(Fl_sqr_pre(Fl_add(X1, YY, p), p, pi),
      56             :                        Fl_add(XX, YYYY, p), p), p);
      57    91638720 :   M = Fl_addmul_pre(Fl_triple(XX, p), a4, Fl_sqr_pre(ZZ, p, pi), p, pi);
      58    91639841 :   T = Fl_sub(Fl_sqr_pre(M, p, pi), Fl_double(S, p), p);
      59    91638517 :   Q[1] = T;
      60    91638517 :   Q[2] = Fl_sub(Fl_mul_pre(M, Fl_sub(S, T, p), p, pi),
      61             :                 Fl_double(Fl_double(Fl_double(YYYY, p), p), p), p);
      62    91638189 :   Q[3] = Fl_sub(Fl_sqr_pre(Fl_add(Y1, Z1, p), p, pi),
      63             :                 Fl_add(YY, ZZ, p), p);
      64             : }
      65             : 
      66             : INLINE void
      67    82332617 : Flj_dbl_pre_inplace(GEN P, ulong a4, ulong p, ulong pi)
      68             : {
      69    82332617 :   Flj_dbl_indir_pre(P, P, a4, p, pi);
      70    82330882 : }
      71             : 
      72             : GEN
      73     9537575 : Flj_dbl_pre(GEN P, ulong a4, ulong p, ulong pi)
      74             : {
      75     9537575 :   GEN Q = cgetg(4, t_VECSMALL);
      76     9537497 :   Flj_dbl_indir_pre(P, Q, a4, p, pi);
      77     9537492 :   return Q;
      78             : }
      79             : 
      80             : /*
      81             :  * Cost: 11M + 5S + 9add + 4*2.
      82             :  * Source: http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#addition-add-2007-bl
      83             :  */
      84             : 
      85             : INLINE void
      86    27440041 : Flj_add_indir_pre(GEN P, GEN Q, GEN R, ulong a4, ulong p, ulong pi)
      87             : {
      88             :   ulong X1, Y1, Z1, X2, Y2, Z2;
      89             :   ulong Z1Z1, Z2Z2, U1, U2, S1, S2, H, I, J, r, V, W;
      90    27440041 :   X1 = P[1]; Y1 = P[2]; Z1 = P[3];
      91    27440041 :   X2 = Q[1]; Y2 = Q[2]; Z2 = Q[3];
      92             : 
      93    27440041 :   if (Z2 == 0) {
      94          50 :     R[1] = X1; R[2] = Y1; R[3] = Z1;
      95          50 :     return;
      96             :   }
      97             : 
      98    27439991 :   if (Z1 == 0) {
      99       77146 :     R[1] = X2; R[2] = Y2; R[3] = Z2;
     100       77146 :     return;
     101             :   }
     102             : 
     103    27362845 :   Z1Z1 = Fl_sqr_pre(Z1, p, pi);
     104    27362528 :   Z2Z2 = Fl_sqr_pre(Z2, p, pi);
     105    27362565 :   U1 = Fl_mul_pre(X1, Z2Z2, p, pi);
     106    27362540 :   U2 = Fl_mul_pre(X2, Z1Z1, p, pi);
     107    27362592 :   S1 = Fl_mul_pre(Y1, Fl_mul_pre(Z2, Z2Z2, p, pi), p, pi);
     108    27362597 :   S2 = Fl_mul_pre(Y2, Fl_mul_pre(Z1, Z1Z1, p, pi), p, pi);
     109    27362614 :   H = Fl_sub(U2, U1, p);
     110    27362492 :   r = Fl_double(Fl_sub(S2, S1, p), p);
     111             : 
     112             :   /* If points are equal we must double. */
     113    27362665 :   if (H == 0) {
     114      419803 :     if (r == 0) {
     115             :       /* Points are equal so double. */
     116       10134 :       Flj_dbl_indir_pre(P, R, a4, p, pi);
     117             :     } else {
     118             :       /* Points are opposite so return zero. */
     119      409669 :       R[1] = R[2] = 1; R[3] = 0;
     120             :     }
     121      419803 :     return;
     122             :   }
     123    26942862 :   I = Fl_sqr_pre(Fl_double(H, p), p, pi);
     124    26942824 :   J = Fl_mul_pre(H, I, p, pi);
     125    26942821 :   V = Fl_mul_pre(U1, I, p, pi);
     126    26942830 :   W = Fl_sub(Fl_sqr_pre(r, p, pi), Fl_add(J, Fl_double(V, p), p), p);
     127    26942803 :   R[1] = W;
     128    26942803 :   R[2] = Fl_sub(Fl_mul_pre(r, Fl_sub(V, W, p), p, pi),
     129             :                 Fl_double(Fl_mul_pre(S1, J, p, pi), p), p);
     130    26942793 :   R[3] = Fl_mul_pre(Fl_sub(Fl_sqr_pre(Fl_add(Z1, Z2, p), p, pi),
     131             :                            Fl_add(Z1Z1, Z2Z2, p), p), H, p, pi);
     132             : }
     133             : 
     134             : INLINE void
     135    27439768 : Flj_add_pre_inplace(GEN P, GEN Q, ulong a4, ulong p, ulong pi)
     136             : {
     137    27439768 :   Flj_add_indir_pre(P, Q, P, a4, p, pi);
     138    27439760 : }
     139             : 
     140             : GEN
     141           0 : Flj_add_pre(GEN P, GEN Q, ulong a4, ulong p, ulong pi)
     142             : {
     143           0 :   GEN R = cgetg(4, t_VECSMALL);
     144           0 :   Flj_add_indir_pre(P, Q, R, a4, p, pi);
     145           0 :   return R;
     146             : }
     147             : 
     148             : GEN
     149     8790520 : Flj_neg(GEN Q, ulong p)
     150             : {
     151     8790520 :   return mkvecsmall3(Q[1], Fl_neg(Q[2], p), Q[3]);
     152             : }
     153             : 
     154             : typedef struct {
     155             :   ulong n; /* The number being represented */
     156             :   ulong pbits, nbits;  /* Positive bits and negative bits */
     157             :   ulong lnzb; /* Leading non-zero bit */
     158             : } naf_t;
     159             : 
     160             : /*
     161             :  * Return the signed binary representation (i.e. the Non-Adjacent Form
     162             :  * in base 2) of 0 <= a < 2^63.
     163             :  */
     164             : static void
     165     9264476 : naf_repr(naf_t *x, ulong a)
     166             : {
     167             :   long t, i;
     168             :   ulong pbits, nbits;
     169     9264476 :   ulong c0 = 0, c1, a0;
     170             : 
     171     9264476 :   x->n = a;
     172     9264476 :   pbits = nbits = 0;
     173   104837168 :   for (i = 0; a; a >>= 1, ++i) {
     174    95572692 :     a0 = a & 1;
     175    95572692 :     c1 = (c0 + a0 + ((a & 2) >> 1)) >> 1;
     176    95572692 :     t = c0 + a0 - (c1 << 1);
     177    95572692 :     if (t < 0)
     178    14985065 :       nbits |= (1UL << i);
     179    80587627 :     else if (t > 0)
     180    16655630 :       pbits |= (1UL << i);
     181    95572692 :     c0 = c1;
     182             :   }
     183     9264476 :   c1 = c0 >> 1;
     184     9264476 :   t = c0 - (c1 << 1);
     185             :   /* Note that we don't need to check whether t < 0, since a >= 0 implies
     186             :    * that this most significant signed bit must be non-negative. */
     187             : #if 0
     188             :   if (t < 0)
     189             :     nbits |= (1UL << i);
     190             :   else
     191             : #endif
     192     9264476 :   if (t > 0)
     193     5042376 :     pbits |= (1UL << i);
     194             : 
     195     9264476 :   x->pbits = pbits;
     196     9264476 :   x->nbits = nbits;
     197             :   /* Note that expu returns the least nonzero bit in the argument,
     198             :    * like the bit-scan-rev instruction on Intel architectures. */
     199             :   /* Using pbits here is justified by the fact that a >= 0, so the
     200             :    * most significant bit must be positive. */
     201     9264476 :   x->lnzb = expu(pbits) - 2;
     202     9264451 : }
     203             : 
     204             : /*
     205             :  * Standard left-to-right signed double-and-add to compute [n]P.
     206             :  */
     207             : 
     208             : static GEN
     209     9772836 : Flj_mulu_pre_naf(GEN P, ulong n, ulong a4, ulong p, ulong pi, const naf_t *x)
     210             : {
     211             :   GEN R, Pinv;
     212             :   ulong pbits, nbits, lnzb;
     213             :   ulong m;
     214             : 
     215     9772836 :   if (n == 0)
     216          26 :     return mkvecsmall3(1, 1, 0);
     217     9772810 :   if (n == 1)
     218      235240 :     return Flv_copy(P);
     219             : 
     220     9537570 :   R = Flj_dbl_pre(P, a4, p, pi);
     221     9537492 :   if (n == 2)
     222      746981 :     return R;
     223             : 
     224     8790511 :   pbits = x->pbits;
     225     8790511 :   nbits = x->nbits;
     226     8790511 :   lnzb = x->lnzb;
     227             : 
     228     8790511 :   Pinv = Flj_neg(P, p);
     229     8790355 :   m = (1UL << lnzb);
     230    91121764 :   for ( ; m; m >>= 1) {
     231    82331190 :     Flj_dbl_pre_inplace(R, a4, p, pi);
     232    82332193 :     if (m & pbits)
     233    12434685 :       Flj_add_pre_inplace(R, P, a4, p, pi);
     234    69897508 :     else if (m & nbits)
     235    15005263 :       Flj_add_pre_inplace(R, Pinv, a4, p, pi);
     236             :   }
     237     8790574 :   avma = (pari_sp)R; return R;
     238             : }
     239             : 
     240             : GEN
     241     8768138 : Flj_mulu_pre(GEN P, ulong n, ulong a4, ulong p, ulong pi)
     242             : {
     243             :   naf_t x;
     244     8768138 :   naf_repr(&x, n);
     245     8768164 :   return Flj_mulu_pre_naf(P, n, a4, p, pi, &x);
     246             : }
     247             : 
     248             : ulong
     249      233761 : Flj_order_ufact(GEN P, ulong n, GEN F, ulong a4, ulong p, ulong pi)
     250             : {
     251      233761 :   pari_sp av = avma;
     252      233761 :   ulong res = 1;
     253             :   long i, nfactors;
     254             :   GEN primes, exps;
     255             : 
     256      233761 :   primes = gel(F, 1);
     257      233761 :   nfactors = lg(primes);
     258      233761 :   exps = gel(F, 2);
     259             : 
     260      626848 :   for (i = 1; i < nfactors; ++i) {
     261      496274 :     ulong q, pp = primes[i];
     262      496274 :     long ei = exps[i];
     263             :     long j, k;
     264             :     naf_t x;
     265             :     GEN b;
     266             : 
     267     1251282 :     for (q = pp, j = 1; j < ei; ++j)
     268      755008 :       q *= pp;
     269      496274 :     b = Flj_mulu_pre(P, n / q, a4, p, pi);
     270             : 
     271      496274 :     naf_repr(&x, pp);
     272     1500956 :     for (j = 0; j < ei && b[3] != 0; ++j)
     273     1004682 :       b = Flj_mulu_pre_naf(b, pp, a4, p, pi, &x);
     274      496274 :     if (b[3] != 0)
     275      103187 :       return 0;
     276     1047068 :     for (k = 0; k < j; ++k)
     277      653981 :       res *= pp;
     278      393087 :     avma = av;
     279             :   }
     280      130574 :   return res;
     281             : }
     282             : 
     283             : GEN
     284     1055441 : Fle_to_Flj(GEN P)
     285     2110882 : { return ell_is_inf(P) ? mkvecsmall3(1UL, 1UL, 0UL):
     286     1055441 :                          mkvecsmall3(P[1], P[2], 1UL);
     287             : }
     288             : 
     289             : GEN
     290     1055441 : Flj_to_Fle_pre(GEN P, ulong p, ulong pi)
     291             : {
     292     1055441 :   if (P[3] == 0) return ellinf();
     293             :   else
     294             :   {
     295      960007 :     ulong Z = Fl_inv(P[3], p);
     296      960007 :     ulong Z2 = Fl_sqr_pre(Z, p, pi);
     297      960007 :     ulong X3 = Fl_mul_pre(P[1], Z2, p, pi);
     298      960007 :     ulong Y3 = Fl_mul_pre(P[2], Fl_mul_pre(Z, Z2, p, pi), p, pi);
     299      960007 :     return mkvecsmall2(X3, Y3);
     300             :   }
     301             : }
     302             : 
     303             : INLINE void
     304     8402985 : random_Fle_pre_indir(ulong a4, ulong a6, ulong p, ulong pi,
     305             :                      ulong *pt_x, ulong *pt_y)
     306             : {
     307             :   ulong x, x2, y, rhs;
     308             :   do
     309             :   {
     310     8402985 :     x   = random_Fl(p); /*  x^3+a4*x+a6 = x*(x^2+a4)+a6  */
     311     8403014 :     x2  = Fl_sqr_pre(x, p, pi);
     312     8402952 :     rhs = Fl_addmul_pre(a6, x, Fl_add(x2, a4, p), p, pi);
     313     8402944 :   } while ((!rhs && !Fl_add(Fl_triple(x2,p),a4,p)) || krouu(rhs, p) < 0);
     314     4207095 :   y = Fl_sqrt_pre(rhs, p, pi);
     315     4207088 :   *pt_x = x; *pt_y = y;
     316     4207088 : }
     317             : 
     318             : GEN
     319     3718947 : random_Flj_pre(ulong a4, ulong a6, ulong p, ulong pi)
     320             : {
     321             :   ulong x, y;
     322     3718947 :   random_Fle_pre_indir(a4, a6, p, pi, &x, &y);
     323     3718938 :   return mkvecsmall3(x, y, 1);
     324             : }
     325             : 
     326             : /***********************************************************************/
     327             : /**                                                                   **/
     328             : /**                              Fle                                  **/
     329             : /**                                                                   **/
     330             : /***********************************************************************/
     331             : GEN
     332           0 : Fle_changepoint(GEN x, GEN ch, ulong p)
     333             : {
     334             :   ulong p1,u,r,s,t,v,v2,v3;
     335             :   GEN z;
     336           0 :   if (ell_is_inf(x)) return x;
     337           0 :   u = ch[1]; r = ch[2];
     338           0 :   s = ch[3]; t = ch[4];
     339           0 :   v = Fl_inv(u, p); v2 = Fl_sqr(v,p); v3 = Fl_mul(v,v2,p);
     340           0 :   p1 = Fl_sub(x[1],r,p);
     341           0 :   z = cgetg(3,t_VECSMALL);
     342           0 :   z[1] = Fl_mul(v2, p1, p);
     343           0 :   z[2] = Fl_mul(v3, Fl_sub(x[2], Fl_add(Fl_mul(s,p1, p),t, p),p),p);
     344           0 :   return z;
     345             : }
     346             : 
     347             : GEN
     348         371 : Fle_changepointinv(GEN x, GEN ch, ulong p)
     349             : {
     350             :   ulong u, r, s, t, X, Y, u2, u3, u2X;
     351             :   GEN z;
     352         371 :   if (ell_is_inf(x)) return x;
     353         371 :   X = x[1]; Y = x[2];
     354         371 :   u = ch[1]; r = ch[2];
     355         371 :   s = ch[3]; t = ch[4];
     356         371 :   u2 = Fl_sqr(u, p); u3 = Fl_mul(u,u2,p);
     357         371 :   u2X = Fl_mul(u2,X, p);
     358         371 :   z = cgetg(3, t_VECSMALL);
     359         371 :   z[1] = Fl_add(u2X,r,p);
     360         371 :   z[2] = Fl_add(Fl_mul(u3,Y,p), Fl_add(Fl_mul(s,u2X,p), t, p), p);
     361         371 :   return z;
     362             : }
     363             : static GEN
     364      384544 : Fle_dbl_slope(GEN P, ulong a4, ulong p, ulong *slope)
     365             : {
     366             :   ulong x, y, Qx, Qy;
     367      384544 :   if (ell_is_inf(P) || !P[2]) return ellinf();
     368      338789 :   x = P[1]; y = P[2];
     369      338789 :   *slope = Fl_div(Fl_add(Fl_triple(Fl_sqr(x,p), p), a4, p),
     370             :                   Fl_double(y, p), p);
     371      338790 :   Qx = Fl_sub(Fl_sqr(*slope, p), Fl_double(x, p), p);
     372      338791 :   Qy = Fl_sub(Fl_mul(*slope, Fl_sub(x, Qx, p), p), y, p);
     373      338793 :   return mkvecsmall2(Qx, Qy);
     374             : }
     375             : 
     376             : GEN
     377      311484 : Fle_dbl(GEN P, ulong a4, ulong p)
     378             : {
     379             :   ulong slope;
     380      311484 :   return Fle_dbl_slope(P,a4,p,&slope);
     381             : }
     382             : 
     383             : static GEN
     384      652540 : Fle_add_slope(GEN P, GEN Q, ulong a4, ulong p, ulong *slope)
     385             : {
     386             :   ulong Px, Py, Qx, Qy, Rx, Ry;
     387      652540 :   if (ell_is_inf(P)) return Q;
     388      652527 :   if (ell_is_inf(Q)) return P;
     389      652535 :   Px = P[1]; Py = P[2];
     390      652535 :   Qx = Q[1]; Qy = Q[2];
     391      652535 :   if (Px==Qx)
     392       73130 :     return Py==Qy ? Fle_dbl_slope(P, a4, p, slope): ellinf();
     393      579405 :   *slope = Fl_div(Fl_sub(Py, Qy, p), Fl_sub(Px, Qx, p), p);
     394      579431 :   Rx = Fl_sub(Fl_sub(Fl_sqr(*slope, p), Px, p), Qx, p);
     395      579445 :   Ry = Fl_sub(Fl_mul(*slope, Fl_sub(Px, Rx, p), p), Py, p);
     396      579451 :   return mkvecsmall2(Rx, Ry);
     397             : }
     398             : 
     399             : GEN
     400      652516 : Fle_add(GEN P, GEN Q, ulong a4, ulong p)
     401             : {
     402             :   ulong slope;
     403      652516 :   return Fle_add_slope(P,Q,a4,p,&slope);
     404             : }
     405             : 
     406             : static GEN
     407          98 : Fle_neg(GEN P, ulong p)
     408             : {
     409          98 :   if (ell_is_inf(P)) return P;
     410          98 :   return mkvecsmall2(P[1], Fl_neg(P[2], p));
     411             : }
     412             : 
     413             : GEN
     414           0 : Fle_sub(GEN P, GEN Q, ulong a4, ulong p)
     415             : {
     416           0 :   pari_sp av = avma;
     417             :   ulong slope;
     418           0 :   return gerepileupto(av, Fle_add_slope(P, Fle_neg(Q, p), a4, p, &slope));
     419             : }
     420             : 
     421             : struct _Fle
     422             : {
     423             :   ulong a4,a6;
     424             :   ulong p;
     425             : };
     426             : 
     427             : static GEN
     428           0 : _Fle_dbl(void *E, GEN P)
     429             : {
     430           0 :   struct _Fle *ell = (struct _Fle *) E;
     431           0 :   return Fle_dbl(P, ell->a4, ell->p);
     432             : }
     433             : 
     434             : static GEN
     435        7777 : _Fle_add(void *E, GEN P, GEN Q)
     436             : {
     437        7777 :   struct _Fle *ell=(struct _Fle *) E;
     438        7777 :   return Fle_add(P, Q, ell->a4, ell->p);
     439             : }
     440             : 
     441             : GEN
     442     1367527 : Fle_mulu(GEN P, ulong n, ulong a4, ulong p)
     443             : {
     444             :   ulong pi;
     445     1367527 :   if (!n || ell_is_inf(P)) return ellinf();
     446     1367527 :   if (n==1) return zv_copy(P);
     447     1366687 :   if (n==2) return Fle_dbl(P, a4, p);
     448     1055441 :   pi = get_Fl_red(p);
     449     1055441 :   return Flj_to_Fle_pre(Flj_mulu_pre(Fle_to_Flj(P), n, a4, p, pi), p, pi);
     450             : }
     451             : 
     452             : static GEN
     453      785365 : _Fle_mul(void *E, GEN P, GEN n)
     454             : {
     455      785365 :   pari_sp av = avma;
     456      785365 :   struct _Fle *e=(struct _Fle *) E;
     457      785365 :   long s = signe(n);
     458             :   GEN Q;
     459      785365 :   if (!s || ell_is_inf(P)) return ellinf();
     460      785351 :   if (s < 0) P = Fle_neg(P, e->p);
     461      785351 :   if (is_pm1(n)) return s > 0? zv_copy(P): P;
     462      784910 :   Q = (lgefint(n)==3) ? Fle_mulu(P, uel(n,2), e->a4, e->p):
     463             :                         gen_pow(P, n, (void*)e, &_Fle_dbl, &_Fle_add);
     464      784910 :   return s > 0? Q: gerepileuptoleaf(av, Q);
     465             : }
     466             : 
     467             : GEN
     468         133 : Fle_mul(GEN P, GEN n, ulong a4, ulong p)
     469             : {
     470             :   struct _Fle E;
     471         133 :   E.a4 = a4; E.p = p;
     472         133 :   return _Fle_mul(&E, P, n);
     473             : }
     474             : 
     475             : /* Finds a random non-singular point on E */
     476             : 
     477             : GEN
     478      488149 : random_Fle_pre(ulong a4, ulong a6, ulong p, ulong pi)
     479             : {
     480             :   ulong x, y;
     481      488149 :   random_Fle_pre_indir(a4, a6, p, pi, &x, &y);
     482      488149 :   return mkvecsmall2(x, y);
     483             : }
     484             : 
     485             : GEN
     486           0 : random_Fle(ulong a4, ulong a6, ulong p)
     487           0 : { return random_Fle_pre(a4, a6, p, get_Fl_red(p)); }
     488             : 
     489             : static GEN
     490           0 : _Fle_rand(void *E)
     491             : {
     492           0 :   struct _Fle *e=(struct _Fle *) E;
     493           0 :   return random_Fle(e->a4, e->a6, e->p);
     494             : }
     495             : 
     496             : static const struct bb_group Fle_group={_Fle_add,_Fle_mul,_Fle_rand,hash_GEN,zv_equal,ell_is_inf,NULL};
     497             : 
     498             : GEN
     499      199870 : Fle_order(GEN z, GEN o, ulong a4, ulong p)
     500             : {
     501      199870 :   pari_sp av = avma;
     502             :   struct _Fle e;
     503      199870 :   e.a4=a4;
     504      199870 :   e.p=p;
     505      199870 :   return gerepileuptoint(av, gen_order(z, o, (void*)&e, &Fle_group));
     506             : }
     507             : 
     508             : GEN
     509          42 : Fle_log(GEN a, GEN b, GEN o, ulong a4, ulong p)
     510             : {
     511          42 :   pari_sp av = avma;
     512             :   struct _Fle e;
     513          42 :   e.a4=a4;
     514          42 :   e.p=p;
     515          42 :   return gerepileuptoint(av, gen_PH_log(a, b, o, (void*)&e, &Fle_group));
     516             : }
     517             : 
     518             : ulong
     519           0 : Fl_ellj(ulong a4, ulong a6, ulong p)
     520             : {
     521           0 :   if (SMALL_ULONG(p))
     522             :   {
     523             :     /* a43 = 4 a4^3 */
     524           0 :     ulong a43 = Fl_double(Fl_double(Fl_mul(a4, Fl_sqr(a4, p), p), p), p);
     525             :     /* a62 = 27 a6^2 */
     526           0 :     ulong a62 = Fl_mul(Fl_sqr(a6, p), 27 % p, p);
     527           0 :     ulong z1 = Fl_mul(a43, 1728 % p, p);
     528           0 :     ulong z2 = Fl_add(a43, a62, p);
     529           0 :     return Fl_div(z1, z2, p);
     530             :   } else
     531           0 :     return Fl_ellj_pre(a4, a6, p, get_Fl_red(p));
     532             : }
     533             : 
     534             : void
     535      553817 : Fl_ellj_to_a4a6(ulong j, ulong p, ulong *pt_a4, ulong *pt_a6)
     536             : {
     537      553817 :   ulong zagier = 1728 % p;
     538      553817 :   if (j == 0)           { *pt_a4 = 0; *pt_a6 =1; }
     539      553817 :   else if (j == zagier) { *pt_a4 = 1; *pt_a6 =0; }
     540             :   else
     541             :   {
     542      553817 :     ulong k = Fl_sub(zagier, j, p);
     543      553815 :     ulong kj = Fl_mul(k, j, p);
     544      553819 :     ulong k2j = Fl_mul(kj, k, p);
     545      553818 :     *pt_a4 = Fl_triple(kj, p);
     546      553817 :     *pt_a6 = Fl_double(k2j, p);
     547             :   }
     548      553815 : }
     549             : 
     550             : ulong
     551     3804734 : Fl_elldisc_pre(ulong a4, ulong a6, ulong p, ulong pi)
     552             : {
     553             :   /* D = -(4A^3 + 27B^2) */
     554             :   ulong t1, t2;
     555     3804734 :   t1 = Fl_mul_pre(a4, Fl_sqr_pre(a4, p, pi), p, pi);
     556     3804734 :   t1 = Fl_double(Fl_double(t1, p), p);
     557     3804734 :   t2 = Fl_mul_pre(27 % p, Fl_sqr_pre(a6, p, pi), p, pi);
     558     3804734 :   return Fl_neg(Fl_add(t1, t2, p), p);
     559             : }
     560             : 
     561             : ulong
     562           0 : Fl_elldisc(ulong a4, ulong a6, ulong p)
     563             : {
     564           0 :   if (SMALL_ULONG(p))
     565             :   {
     566             :     /* D = -(4A^3 + 27B^2) */
     567             :     ulong t1, t2;
     568           0 :     t1 = Fl_mul(a4, Fl_sqr(a4, p), p);
     569           0 :     t1 = Fl_double(Fl_double(t1, p), p);
     570           0 :     t2 = Fl_mul(27 % p, Fl_sqr(a6, p), p);
     571           0 :     return Fl_neg(Fl_add(t1, t2, p), p);
     572             :   } else
     573           0 :     return Fl_elldisc_pre(a4, a6, p, get_Fl_red(p));
     574             : }
     575             : 
     576             : static ulong
     577           0 : nonsquare_Fl(ulong p)
     578             : {
     579             :   ulong a;
     580             :   do
     581           0 :     a = random_Fl(p);
     582           0 :   while (krouu(a, p) >= 0);
     583           0 :   return a;
     584             : }
     585             : 
     586             : void
     587      203305 : Fl_elltwist_disc(ulong a4, ulong a6, ulong D, ulong p, ulong *pt_a4, ulong *pt_a6)
     588             : {
     589      203305 :   ulong D2 = Fl_sqr(D, p);
     590      203303 :   *pt_a4 = Fl_mul(a4, D2, p);
     591      203305 :   *pt_a6 = Fl_mul(a6, Fl_mul(D, D2, p), p);
     592      203307 : }
     593             : 
     594             : void
     595           0 : Fl_elltwist(ulong a4, ulong a6, ulong p, ulong *pt_a4, ulong *pt_a6)
     596             : {
     597           0 :   Fl_elltwist_disc(a4, a6, nonsquare_Fl(p), p, pt_a4, pt_a6);
     598           0 : }

Generated by: LCOV version 1.11