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-bordeaux1.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 - FlxqE.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.8.0 lcov report (development 17908-5dc2363) Lines: 878 930 94.4 %
Date: 2015-07-04 Functions: 94 96 97.9 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 309 414 74.6 %

           Branch data     Line data    Source code
       1                 :            : /* Copyright (C) 2012  The PARI group.
       2                 :            : 
       3                 :            : This file is part of the PARI/GP package.
       4                 :            : 
       5                 :            : PARI/GP is free software; you can redistribute it and/or modify it under the
       6                 :            : terms of the GNU General Public License as published by the Free Software
       7                 :            : Foundation. 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 Fq,
      18                 :            : small characteristic. */
      19                 :            : 
      20                 :            : /***********************************************************************/
      21                 :            : /**                                                                   **/
      22                 :            : /**                              FlxqE                                **/
      23                 :            : /**                                                                   **/
      24                 :            : /***********************************************************************/
      25                 :            : 
      26                 :            : /* Theses functions deal with point over elliptic curves over Fq defined
      27                 :            :  * by an equation of the form y^2=x^3+a4*x+a6.
      28                 :            :  * Most of the time a6 is omitted since it can be recovered from any point
      29                 :            :  * on the curve.
      30                 :            :  */
      31                 :            : 
      32                 :            : GEN
      33                 :      63700 : RgE_to_FlxqE(GEN x, GEN T, ulong p)
      34                 :            : {
      35         [ -  + ]:      63700 :   if (ell_is_inf(x)) return x;
      36                 :      63700 :   retmkvec2(Rg_to_Flxq(gel(x,1),T,p),Rg_to_Flxq(gel(x,2),T,p));
      37                 :            : }
      38                 :            : 
      39                 :            : GEN
      40                 :     152887 : FlxqE_changepoint(GEN x, GEN ch, GEN T, ulong p)
      41                 :            : {
      42                 :     152887 :   pari_sp av = avma;
      43                 :            :   GEN p1,z,u,r,s,t,v,v2,v3;
      44         [ +  + ]:     152887 :   if (ell_is_inf(x)) return x;
      45                 :      90734 :   u = gel(ch,1); r = gel(ch,2);
      46                 :      90734 :   s = gel(ch,3); t = gel(ch,4);
      47                 :      90734 :   v = Flxq_inv(u, T, p); v2 = Flxq_sqr(v, T, p); v3 = Flxq_mul(v,v2, T, p);
      48                 :      90734 :   p1 = Flx_sub(gel(x,1),r, p);
      49                 :      90734 :   z = cgetg(3,t_VEC);
      50                 :      90734 :   gel(z,1) = Flxq_mul(v2, p1, T, p);
      51                 :      90734 :   gel(z,2) = Flxq_mul(v3, Flx_sub(gel(x,2), Flx_add(Flxq_mul(s, p1, T, p),t, p), p), T, p);
      52                 :     152887 :   return gerepileupto(av, z);
      53                 :            : }
      54                 :            : 
      55                 :            : GEN
      56                 :      63700 : FlxqE_changepointinv(GEN x, GEN ch, GEN T, ulong p)
      57                 :            : {
      58                 :            :   GEN u, r, s, t, X, Y, u2, u3, u2X, z;
      59         [ -  + ]:      63700 :   if (ell_is_inf(x)) return x;
      60                 :      63700 :   X = gel(x,1); Y = gel(x,2);
      61                 :      63700 :   u = gel(ch,1); r = gel(ch,2);
      62                 :      63700 :   s = gel(ch,3); t = gel(ch,4);
      63                 :      63700 :   u2 = Flxq_sqr(u, T, p); u3 = Flxq_mul(u,u2, T, p);
      64                 :      63700 :   u2X = Flxq_mul(u2,X, T, p);
      65                 :      63700 :   z = cgetg(3, t_VEC);
      66                 :      63700 :   gel(z,1) = Flx_add(u2X,r, p);
      67                 :      63700 :   gel(z,2) = Flx_add(Flxq_mul(u3,Y, T, p), Flx_add(Flxq_mul(s,u2X, T, p), t, p), p);
      68                 :      63700 :   return z;
      69                 :            : }
      70                 :            : 
      71                 :            : static ulong
      72                 :      20503 : nonsquare_Fl(ulong p)
      73                 :            : {
      74                 :            :   ulong a;
      75                 :            :   do
      76                 :      20503 :     a = random_Fl(p);
      77         [ +  + ]:      20503 :   while (krouu(a, p) >= 0);
      78                 :       7686 :   return a;
      79                 :            : }
      80                 :            : 
      81                 :            : static GEN
      82                 :      22834 : nonsquare_Flxq(GEN T, ulong p)
      83                 :            : {
      84                 :      22834 :   pari_sp av = avma;
      85                 :      22834 :   long n = degpol(T), vs = T[1];
      86                 :            :   GEN a;
      87         [ +  + ]:      22834 :   if (odd(n))
      88                 :       7686 :     return mkvecsmall2(vs, nonsquare_Fl(p));
      89                 :            :   do
      90                 :            :   {
      91                 :      29932 :     avma = av;
      92                 :      29932 :     a = random_Flx(n, vs, p);
      93         [ +  + ]:      29932 :   } while (Flxq_issquare(a, T, p));
      94                 :      22834 :   return a;
      95                 :            : }
      96                 :            : 
      97                 :            : void
      98                 :      22834 : Flxq_elltwist(GEN a, GEN a6, GEN T, ulong p, GEN *pt_a, GEN *pt_a6)
      99                 :            : {
     100                 :      22834 :   GEN d = nonsquare_Flxq(T, p);
     101                 :      22834 :   GEN d2 = Flxq_sqr(d, T, p), d3 = Flxq_mul(d2, d, T, p);
     102         [ +  + ]:      22834 :   if (typ(a)==t_VECSMALL)
     103                 :            :   {
     104                 :      15232 :     *pt_a  = Flxq_mul(a,  d2, T, p);
     105                 :      15232 :     *pt_a6 = Flxq_mul(a6, d3, T, p);
     106                 :            :   } else
     107                 :            :   {
     108                 :       7602 :     *pt_a  = mkvec(Flxq_mul(gel(a,1), d, T, p));
     109                 :       7602 :     *pt_a6 = Flxq_mul(a6, d3, T, p);
     110                 :            :   }
     111                 :      22834 : }
     112                 :            : 
     113                 :            : static GEN
     114                 :    1245862 : FlxqE_dbl_slope(GEN P, GEN a4, GEN T, ulong p, GEN *slope)
     115                 :            : {
     116                 :            :   GEN x, y, Q;
     117 [ +  + ][ +  + ]:    1245862 :   if (ell_is_inf(P) || !lgpol(gel(P,2))) return ellinf();
     118                 :    1144689 :   x = gel(P,1); y = gel(P,2);
     119         [ +  + ]:    1144689 :   if (p==3UL)
     120                 :    1026166 :     *slope = typ(a4)==t_VEC ? Flxq_div(Flxq_mul(x, gel(a4, 1), T, p), y, T, p)
     121         [ +  + ]:    1026166 :                             : Flxq_div(a4, Flx_neg(y, p), T, p);
     122                 :            :   else
     123                 :            :   {
     124                 :     622604 :     GEN sx = Flx_add(Flx_triple(Flxq_sqr(x, T, p), p), a4, p);
     125                 :     622604 :     *slope = Flxq_div(sx, Flx_double(y, p), T, p);
     126                 :            :   }
     127                 :    1144689 :   Q = cgetg(3,t_VEC);
     128                 :    1144689 :   gel(Q, 1) = Flx_sub(Flxq_sqr(*slope, T, p), Flx_double(x, p), p);
     129         [ +  + ]:    1144689 :   if (typ(a4)==t_VEC) gel(Q, 1) = Flx_sub(gel(Q, 1), gel(a4, 1), p);
     130                 :    1144689 :   gel(Q, 2) = Flx_sub(Flxq_mul(*slope, Flx_sub(x, gel(Q, 1), p), T, p), y, p);
     131                 :    1245862 :   return Q;
     132                 :            : }
     133                 :            : 
     134                 :            : GEN
     135                 :    1219882 : FlxqE_dbl(GEN P, GEN a4, GEN T, ulong p)
     136                 :            : {
     137                 :    1219882 :   pari_sp av = avma;
     138                 :            :   GEN slope;
     139                 :    1219882 :   return gerepileupto(av, FlxqE_dbl_slope(P,a4, T, p,&slope));
     140                 :            : }
     141                 :            : 
     142                 :            : static GEN
     143                 :     509776 : FlxqE_add_slope(GEN P, GEN Q, GEN a4, GEN T, ulong p, GEN *slope)
     144                 :            : {
     145                 :            :   GEN Px, Py, Qx, Qy, R;
     146         [ +  + ]:     509776 :   if (ell_is_inf(P)) return Q;
     147         [ +  + ]:     505877 :   if (ell_is_inf(Q)) return P;
     148                 :     505646 :   Px = gel(P,1); Py = gel(P,2);
     149                 :     505646 :   Qx = gel(Q,1); Qy = gel(Q,2);
     150         [ +  + ]:     505646 :   if (Flx_equal(Px, Qx))
     151                 :            :   {
     152         [ +  + ]:      45506 :     if (Flx_equal(Py, Qy))
     153                 :        645 :       return FlxqE_dbl_slope(P, a4, T, p, slope);
     154                 :            :     else
     155                 :      44861 :       return ellinf();
     156                 :            :   }
     157                 :     460140 :   *slope = Flxq_div(Flx_sub(Py, Qy, p), Flx_sub(Px, Qx, p), T, p);
     158                 :     460140 :   R = cgetg(3,t_VEC);
     159                 :     460140 :   gel(R, 1) = Flx_sub(Flx_sub(Flxq_sqr(*slope, T, p), Px, p), Qx, p);
     160         [ +  + ]:     460140 :   if (typ(a4)==t_VEC) gel(R, 1) = Flx_sub(gel(R, 1),gel(a4, 1), p);
     161                 :     460140 :   gel(R, 2) = Flx_sub(Flxq_mul(*slope, Flx_sub(Px, gel(R, 1), p), T, p), Py, p);
     162                 :     509776 :   return R;
     163                 :            : }
     164                 :            : 
     165                 :            : GEN
     166                 :     507070 : FlxqE_add(GEN P, GEN Q, GEN a4, GEN T, ulong p)
     167                 :            : {
     168                 :     507070 :   pari_sp av = avma;
     169                 :            :   GEN slope;
     170                 :     507070 :   return gerepileupto(av, FlxqE_add_slope(P,Q,a4, T, p,&slope));
     171                 :            : }
     172                 :            : 
     173                 :            : static GEN
     174                 :         14 : FlxqE_neg_i(GEN P, ulong p)
     175                 :            : {
     176         [ -  + ]:         14 :   if (ell_is_inf(P)) return P;
     177                 :         14 :   return mkvec2(gel(P,1), Flx_neg(gel(P,2), p));
     178                 :            : }
     179                 :            : 
     180                 :            : GEN
     181                 :        322 : FlxqE_neg(GEN P, GEN T, ulong p)
     182                 :            : {
     183                 :            :   (void) T;
     184         [ -  + ]:        322 :   if (ell_is_inf(P)) return ellinf();
     185                 :        322 :   return mkvec2(gcopy(gel(P,1)), Flx_neg(gel(P,2), p));
     186                 :            : }
     187                 :            : 
     188                 :            : GEN
     189                 :         14 : FlxqE_sub(GEN P, GEN Q, GEN a4, GEN T, ulong p)
     190                 :            : {
     191                 :         14 :   pari_sp av = avma;
     192                 :            :   GEN slope;
     193                 :         14 :   return gerepileupto(av, FlxqE_add_slope(P, FlxqE_neg_i(Q, p), a4, T, p, &slope));
     194                 :            : }
     195                 :            : 
     196                 :            : struct _FlxqE
     197                 :            : {
     198                 :            :   GEN a4, a6;
     199                 :            :   GEN T;
     200                 :            :   ulong p;
     201                 :            : };
     202                 :            : 
     203                 :            : static GEN
     204                 :    1219882 : _FlxqE_dbl(void *E, GEN P)
     205                 :            : {
     206                 :    1219882 :   struct _FlxqE *ell = (struct _FlxqE *) E;
     207                 :    1219882 :   return FlxqE_dbl(P, ell->a4, ell->T, ell->p);
     208                 :            : }
     209                 :            : 
     210                 :            : static GEN
     211                 :     505859 : _FlxqE_add(void *E, GEN P, GEN Q)
     212                 :            : {
     213                 :     505859 :   struct _FlxqE *ell=(struct _FlxqE *) E;
     214                 :     505859 :   return FlxqE_add(P, Q, ell->a4, ell->T, ell->p);
     215                 :            : }
     216                 :            : 
     217                 :            : static GEN
     218                 :     211259 : _FlxqE_mul(void *E, GEN P, GEN n)
     219                 :            : {
     220                 :     211259 :   pari_sp av = avma;
     221                 :     211259 :   struct _FlxqE *e=(struct _FlxqE *) E;
     222                 :     211259 :   long s = signe(n);
     223 [ +  + ][ +  + ]:     211259 :   if (!s || ell_is_inf(P)) return ellinf();
     224         [ +  + ]:     211182 :   if (s<0) P = FlxqE_neg(P, e->T, e->p);
     225 [ +  + ][ +  + ]:     211182 :   if (is_pm1(n)) return s>0? gcopy(P): P;
     226                 :     211259 :   return gerepileupto(av, gen_pow(P, n, e, &_FlxqE_dbl, &_FlxqE_add));
     227                 :            : }
     228                 :            : 
     229                 :            : GEN
     230                 :      62230 : FlxqE_mul(GEN P, GEN n, GEN a4, GEN T, ulong p)
     231                 :            : {
     232                 :            :   struct _FlxqE E;
     233                 :      62230 :   E.a4= a4; E.T = T; E.p = p;
     234                 :      62230 :   return _FlxqE_mul(&E, P, n);
     235                 :            : }
     236                 :            : 
     237                 :            : /* 3*x^2+2*a2*x = -a2*x, and a2!=0 */
     238                 :            : 
     239                 :            : /* Finds a random non-singular point on E */
     240                 :            : static GEN
     241                 :      75596 : random_F3xqE(GEN a2, GEN a6, GEN T)
     242                 :            : {
     243                 :      75596 :   pari_sp ltop = avma;
     244                 :            :   GEN x, y, rhs;
     245                 :      75596 :   const ulong p=3;
     246                 :            :   do
     247                 :            :   {
     248                 :     150114 :     avma= ltop;
     249                 :     150114 :     x   = random_Flx(get_Flx_degree(T),get_Flx_var(T),p);
     250                 :     150114 :     rhs = Flx_add(Flxq_mul(Flxq_sqr(x, T, p), Flx_add(x, a2, p), T, p), a6, p);
     251 [ +  + ][ -  + ]:     150114 :   } while ((!lgpol(rhs) && !lgpol(x)) || !Flxq_issquare(rhs, T, p));
                 [ +  + ]
     252                 :      75596 :   y = Flxq_sqrt(rhs, T, p);
     253         [ -  + ]:      75596 :   if (!y) pari_err_PRIME("random_F3xqE", T);
     254                 :      75596 :   return gerepilecopy(ltop, mkvec2(x, y));
     255                 :            : }
     256                 :            : 
     257                 :            : /* Finds a random non-singular point on E */
     258                 :            : GEN
     259                 :     141409 : random_FlxqE(GEN a4, GEN a6, GEN T, ulong p)
     260                 :            : {
     261                 :     141409 :   pari_sp ltop = avma;
     262                 :            :   GEN x, x2, y, rhs;
     263         [ +  + ]:     141409 :   if (typ(a4)==t_VEC)
     264                 :      75596 :     return random_F3xqE(gel(a4,1), a6, T);
     265                 :            :   do
     266                 :            :   {
     267                 :     130042 :     avma= ltop;
     268                 :     130042 :     x   = random_Flx(get_Flx_degree(T),get_Flx_var(T),p);
     269                 :     130042 :     x2  = Flxq_sqr(x, T, p); /*  x^3+a4*x+a6 = x*(x^2+a4)+a6  */
     270                 :     130042 :     rhs = Flx_add(Flxq_mul(x, Flx_add(x2, a4, p), T, p), a6, p);
     271         [ -  + ]:     131099 :   } while ((!lgpol(rhs) && !lgpol(Flx_add(Flx_triple(x2, p), a4, p)))
     272 [ +  + ][ +  + ]:     131099 :           || !Flxq_issquare(rhs, T, p));
     273                 :      65813 :   y = Flxq_sqrt(rhs, T, p);
     274         [ -  + ]:      65813 :   if (!y) pari_err_PRIME("random_FlxqE", T);
     275                 :     141409 :   return gerepilecopy(ltop, mkvec2(x, y));
     276                 :            : }
     277                 :            : 
     278                 :            : static GEN
     279                 :      66313 : _FlxqE_rand(void *E)
     280                 :            : {
     281                 :      66313 :   struct _FlxqE *ell=(struct _FlxqE *) E;
     282                 :      66313 :   return random_FlxqE(ell->a4, ell->a6, ell->T, ell->p);
     283                 :            : }
     284                 :            : 
     285                 :            : static const struct bb_group FlxqE_group={_FlxqE_add,_FlxqE_mul,_FlxqE_rand,hash_GEN,zvV_equal,ell_is_inf, NULL};
     286                 :            : 
     287                 :            : const struct bb_group *
     288                 :         21 : get_FlxqE_group(void ** pt_E, GEN a4, GEN a6, GEN T, ulong p)
     289                 :            : {
     290                 :         21 :   struct _FlxqE *e = (struct _FlxqE *) stack_malloc(sizeof(struct _FlxqE));
     291                 :         21 :   e->a4 = a4; e->a6 = a6; e->T = Flx_get_red(T, p); e->p = p;
     292                 :         21 :   *pt_E = (void *) e;
     293                 :         21 :   return &FlxqE_group;
     294                 :            : }
     295                 :            : 
     296                 :            : GEN
     297                 :       1442 : FlxqE_order(GEN z, GEN o, GEN a4, GEN T, ulong p)
     298                 :            : {
     299                 :       1442 :   pari_sp av = avma;
     300                 :            :   struct _FlxqE e;
     301                 :       1442 :   e.a4=a4; e.T=T; e.p=p;
     302                 :       1442 :   return gerepileuptoint(av, gen_order(z, o, (void*)&e, &FlxqE_group));
     303                 :            : }
     304                 :            : 
     305                 :            : GEN
     306                 :         42 : FlxqE_log(GEN a, GEN b, GEN o, GEN a4, GEN T, ulong p)
     307                 :            : {
     308                 :         42 :   pari_sp av = avma;
     309                 :            :   struct _FlxqE e;
     310                 :         42 :   e.a4=a4; e.T=T; e.p=p;
     311                 :         42 :   return gerepileuptoint(av, gen_PH_log(a, b, o, (void*)&e, &FlxqE_group));
     312                 :            : }
     313                 :            : 
     314                 :            : /***********************************************************************/
     315                 :            : /**                                                                   **/
     316                 :            : /**                            Pairings                               **/
     317                 :            : /**                                                                   **/
     318                 :            : /***********************************************************************/
     319                 :            : 
     320                 :            : /* Derived from APIP from and by Jerome Milan, 2012 */
     321                 :            : 
     322                 :            : static GEN
     323                 :      65112 : FlxqE_vert(GEN P, GEN Q, GEN T, ulong p)
     324                 :            : {
     325         [ +  + ]:      65112 :   if (ell_is_inf(P))
     326                 :      20123 :     return pol1_Flx(get_Flx_var(T));
     327                 :      65112 :   return Flx_sub(gel(Q, 1), gel(P, 1), p);
     328                 :            : }
     329                 :            : 
     330                 :            : /* Computes the equation of the line tangent to R and returns its
     331                 :            :    evaluation at the point Q. Also doubles the point R.
     332                 :            :  */
     333                 :            : 
     334                 :            : static GEN
     335                 :      44001 : FlxqE_tangent_update(GEN R, GEN Q, GEN a4, GEN T, ulong p, GEN *pt_R)
     336                 :            : {
     337         [ +  + ]:      44001 :   if (ell_is_inf(R))
     338                 :            :   {
     339                 :       3371 :     *pt_R = ellinf();
     340                 :       3371 :     return pol1_Flx(get_Flx_var(T));
     341                 :            :   }
     342         [ +  + ]:      40630 :   else if (!lgpol(gel(R,2)))
     343                 :            :   {
     344                 :      15295 :     *pt_R = ellinf();
     345                 :      15295 :     return FlxqE_vert(R, Q, T, p);
     346                 :            :   } else {
     347                 :            :     GEN slope, tmp1, tmp2;
     348                 :      25335 :     *pt_R = FlxqE_dbl_slope(R, a4, T, p, &slope);
     349                 :      25335 :     tmp1 = Flx_sub(gel(Q, 1), gel(R, 1), p);
     350                 :      25335 :     tmp2 = Flx_add(Flxq_mul(tmp1, slope, T, p), gel(R,2), p);
     351                 :      44001 :     return Flx_sub(gel(Q, 2), tmp2, p);
     352                 :            :   }
     353                 :            : }
     354                 :            : 
     355                 :            : /* Computes the equation of the line through R and P, and returns its
     356                 :            :    evaluation at the point Q. Also adds P to the point R.
     357                 :            :  */
     358                 :            : 
     359                 :            : static GEN
     360                 :       4261 : FlxqE_chord_update(GEN R, GEN P, GEN Q, GEN a4, GEN T, ulong p, GEN *pt_R)
     361                 :            : {
     362         [ +  + ]:       4261 :   if (ell_is_inf(R))
     363                 :            :   {
     364                 :        105 :     *pt_R = gcopy(P);
     365                 :        105 :     return FlxqE_vert(P, Q, T, p);
     366                 :            :   }
     367         [ -  + ]:       4156 :   else if (ell_is_inf(P))
     368                 :            :   {
     369                 :          0 :     *pt_R = gcopy(R);
     370                 :          0 :     return FlxqE_vert(R, Q, T, p);
     371                 :            :   }
     372         [ +  + ]:       4156 :   else if (Flx_equal(gel(P, 1), gel(R, 1)))
     373                 :            :   {
     374         [ +  + ]:       1464 :     if (Flx_equal(gel(P, 2), gel(R, 2)))
     375                 :          7 :       return FlxqE_tangent_update(R, Q, a4, T, p, pt_R);
     376                 :            :     else
     377                 :            :     {
     378                 :       1457 :       *pt_R = ellinf();
     379                 :       1457 :       return FlxqE_vert(R, Q, T, p);
     380                 :            :     }
     381                 :            :   } else {
     382                 :            :     GEN slope, tmp1, tmp2;
     383                 :       2692 :     *pt_R = FlxqE_add_slope(P, R, a4, T, p, &slope);
     384                 :       2692 :     tmp1  = Flxq_mul(Flx_sub(gel(Q, 1), gel(R, 1), p), slope, T, p);
     385                 :       2692 :     tmp2  = Flx_add(tmp1, gel(R, 2), p);
     386                 :       4261 :     return Flx_sub(gel(Q, 2), tmp2, p);
     387                 :            :   }
     388                 :            : }
     389                 :            : 
     390                 :            : /* Returns the Miller function f_{m, Q} evaluated at the point P using
     391                 :            :    the standard Miller algorithm.
     392                 :            :  */
     393                 :            : 
     394                 :            : struct _FlxqE_miller
     395                 :            : {
     396                 :            :   ulong p;
     397                 :            :   GEN T, a4, P;
     398                 :            : };
     399                 :            : 
     400                 :            : static GEN
     401                 :      43994 : FlxqE_Miller_dbl(void* E, GEN d)
     402                 :            : {
     403                 :      43994 :   struct _FlxqE_miller *m = (struct _FlxqE_miller *)E;
     404                 :      43994 :   ulong p  = m->p;
     405                 :      43994 :   GEN T = m->T, a4 = m->a4, P = m->P;
     406                 :            :   GEN v, line;
     407                 :      43994 :   GEN num = Flxq_sqr(gel(d,1), T, p);
     408                 :      43994 :   GEN denom = Flxq_sqr(gel(d,2), T, p);
     409                 :      43994 :   GEN point = gel(d,3);
     410                 :      43994 :   line = FlxqE_tangent_update(point, P, a4, T, p, &point);
     411                 :      43994 :   num  = Flxq_mul(num, line, T, p);
     412                 :      43994 :   v = FlxqE_vert(point, P, T, p);
     413                 :      43994 :   denom = Flxq_mul(denom, v, T, p);
     414                 :      43994 :   return mkvec3(num, denom, point);
     415                 :            : }
     416                 :            : 
     417                 :            : static GEN
     418                 :       4261 : FlxqE_Miller_add(void* E, GEN va, GEN vb)
     419                 :            : {
     420                 :       4261 :   struct _FlxqE_miller *m = (struct _FlxqE_miller *)E;
     421                 :       4261 :   ulong p = m->p;
     422                 :       4261 :   GEN T = m->T, a4 = m->a4, P = m->P;
     423                 :            :   GEN v, line, point;
     424                 :       4261 :   GEN na = gel(va,1), da = gel(va,2), pa = gel(va,3);
     425                 :       4261 :   GEN nb = gel(vb,1), db = gel(vb,2), pb = gel(vb,3);
     426                 :       4261 :   GEN num   = Flxq_mul(na, nb, T, p);
     427                 :       4261 :   GEN denom = Flxq_mul(da, db, T, p);
     428                 :       4261 :   line = FlxqE_chord_update(pa, pb, P, a4, T, p, &point);
     429                 :       4261 :   num  = Flxq_mul(num, line, T, p);
     430                 :       4261 :   v = FlxqE_vert(point, P, T, p);
     431                 :       4261 :   denom = Flxq_mul(denom, v, T, p);
     432                 :       4261 :   return mkvec3(num, denom, point);
     433                 :            : }
     434                 :            : 
     435                 :            : static GEN
     436                 :      16647 : FlxqE_Miller(GEN Q, GEN P, GEN m, GEN a4, GEN T, ulong p)
     437                 :            : {
     438                 :      16647 :   pari_sp ltop = avma;
     439                 :            :   struct _FlxqE_miller d;
     440                 :            :   GEN v, num, denom, g1;
     441                 :            : 
     442                 :      16647 :   d.a4 = a4; d.T = T; d.p = p; d.P = P;
     443                 :      16647 :   g1 = pol1_Flx(get_Flx_var(T));
     444                 :      16647 :   v = gen_pow(mkvec3(g1,g1,Q), m, (void*)&d, FlxqE_Miller_dbl, FlxqE_Miller_add);
     445                 :      16647 :   num = gel(v,1); denom = gel(v,2);
     446 [ +  + ][ -  + ]:      16647 :   if (!lgpol(num) || !lgpol(denom)) { avma = ltop; return NULL; }
     447                 :      16647 :   return gerepileupto(ltop, Flxq_div(num, denom, T, p));
     448                 :            : }
     449                 :            : 
     450                 :            : GEN
     451                 :      12011 : FlxqE_weilpairing(GEN P, GEN Q, GEN m, GEN a4, GEN T, ulong p)
     452                 :            : {
     453                 :      12011 :   pari_sp ltop = avma;
     454                 :            :   GEN num, denom, result;
     455 [ +  + ][ +  + ]:      12011 :   if (ell_is_inf(P) || ell_is_inf(Q) || Flx_equal(P,Q))
                 [ -  + ]
     456                 :       2498 :     return pol1_Flx(get_Flx_var(T));
     457                 :       9513 :   num    = FlxqE_Miller(P, Q, m, a4, T, p);
     458         [ +  + ]:       9513 :   if (!num) return pol1_Flx(get_Flx_var(T));
     459                 :       7134 :   denom  = FlxqE_Miller(Q, P, m, a4, T, p);
     460         [ +  + ]:       7134 :   if (!denom) {avma = ltop; return pol1_Flx(get_Flx_var(T)); }
     461                 :       6840 :   result = Flxq_div(num, denom, T, p);
     462         [ +  + ]:       6840 :   if (mpodd(m))
     463                 :        504 :     result  = Flx_neg(result, p);
     464                 :      12011 :   return gerepileupto(ltop, result);
     465                 :            : }
     466                 :            : 
     467                 :            : GEN
     468                 :          0 : FlxqE_tatepairing(GEN P, GEN Q, GEN m, GEN a4, GEN T, ulong p)
     469                 :            : {
     470                 :            :   GEN num;
     471 [ #  # ][ #  # ]:          0 :   if (ell_is_inf(P) || ell_is_inf(Q))
     472                 :          0 :     return pol1_Flx(get_Flx_var(T));
     473                 :          0 :   num = FlxqE_Miller(P, Q, m, a4, T, p);
     474         [ #  # ]:          0 :   return num? num: pol1_Flx(get_Flx_var(T));
     475                 :            : }
     476                 :            : 
     477                 :            : static GEN
     478                 :      12011 : _FlxqE_pairorder(void *E, GEN P, GEN Q, GEN m, GEN F)
     479                 :            : {
     480                 :      12011 :   struct _FlxqE *e = (struct _FlxqE *) E;
     481                 :      12011 :   return  Flxq_order(FlxqE_weilpairing(P,Q,m,e->a4,e->T,e->p), F, e->T, e->p);
     482                 :            : }
     483                 :            : 
     484                 :            : GEN
     485                 :      14385 : Flxq_ellgroup(GEN a4, GEN a6, GEN N, GEN T, ulong p, GEN *pt_m)
     486                 :            : {
     487                 :            :   struct _FlxqE e;
     488                 :      14385 :   GEN q = powuu(p, get_Flx_degree(T));
     489                 :      14385 :   e.a4=a4; e.a6=a6; e.T=T; e.p=p;
     490                 :      14385 :   return gen_ellgroup(N, subis(q,1), pt_m, (void*)&e, &FlxqE_group, _FlxqE_pairorder);
     491                 :            : }
     492                 :            : 
     493                 :            : GEN
     494                 :      13153 : Flxq_ellgens(GEN a4, GEN a6, GEN ch, GEN D, GEN m, GEN T, ulong p)
     495                 :            : {
     496                 :            :   GEN P;
     497                 :      13153 :   pari_sp av = avma;
     498                 :            :   struct _FlxqE e;
     499                 :      13153 :   e.a4=a4; e.a6=a6; e.T=T; e.p=p;
     500         [ +  + ]:      13153 :   switch(lg(D)-1)
     501                 :            :   {
     502                 :            :   case 1:
     503                 :      10703 :     P = gen_gener(gel(D,1), (void*)&e, &FlxqE_group);
     504                 :      10703 :     P = mkvec(FlxqE_changepoint(P, ch, T, p));
     505                 :      10703 :     break;
     506                 :            :   default:
     507                 :       2450 :     P = gen_ellgens(gel(D,1), gel(D,2), m, (void*)&e, &FlxqE_group, _FlxqE_pairorder);
     508                 :       2450 :     gel(P,1) = FlxqE_changepoint(gel(P,1), ch, T, p);
     509                 :       2450 :     gel(P,2) = FlxqE_changepoint(gel(P,2), ch, T, p);
     510                 :       2450 :     break;
     511                 :            :   }
     512                 :      13153 :   return gerepilecopy(av, P);
     513                 :            : }
     514                 :            : /***********************************************************************/
     515                 :            : /**                                                                   **/
     516                 :            : /**                          Point counting                           **/
     517                 :            : /**                                                                   **/
     518                 :            : /***********************************************************************/
     519                 :            : 
     520                 :      11130 : static GEN _can_invl(void *E, GEN V) {(void) E; return V; }
     521                 :            : 
     522                 :       3654 : static GEN _can_lin(void *E, GEN F, GEN V, GEN q)
     523                 :            : {
     524                 :       3654 :   GEN v = RgX_splitting(V, 3);
     525                 :            :   (void) E;
     526                 :       3654 :   return FpX_sub(V,ZXV_dotproduct(v, F), q);
     527                 :            : }
     528                 :            : 
     529                 :            : static GEN
     530                 :       7476 : _can_iter(void *E, GEN f, GEN q)
     531                 :            : {
     532                 :       7476 :   GEN h = RgX_splitting(f,3);
     533                 :       7476 :   GEN h1s = ZX_sqr(gel(h,1)), h2s = ZX_sqr(gel(h,2)), h3s = ZX_sqr(gel(h,3));
     534                 :       7476 :   GEN h12 = ZX_mul(gel(h,1), gel(h,2));
     535                 :       7476 :   GEN h13 = ZX_mul(gel(h,1), gel(h,3));
     536                 :       7476 :   GEN h23 = ZX_mul(gel(h,2), gel(h,3));
     537                 :       7476 :   GEN h1c = ZX_mul(gel(h,1), h1s);
     538                 :       7476 :   GEN h3c = ZX_mul(gel(h,3), h3s);
     539                 :       7476 :   GEN th = ZX_mul(ZX_sub(h2s,ZX_mulu(h13,3)),gel(h,2));
     540                 :       7476 :   GEN y = FpX_sub(f,ZX_add(RgX_shift_shallow(h3c,2),ZX_add(RgX_shift_shallow(th,1),h1c)),q);
     541                 :            :   (void) E;
     542                 :       7476 :   return mkvecn(7,y,h1s,h2s,h3s,h12,h13,h23);
     543                 :            : }
     544                 :            : 
     545                 :            : static GEN
     546                 :       7476 : _can_invd(void *E, GEN V, GEN v, GEN qM, long M)
     547                 :            : {
     548                 :       7476 :   GEN h1s=gel(v,2), h2s=gel(v,3), h3s=gel(v,4);
     549                 :       7476 :   GEN h12=gel(v,5), h13=gel(v,6), h23=gel(v,7);
     550                 :       7476 :   GEN F = mkvec3(ZX_sub(h1s,RgX_shift_shallow(h23,1)),RgX_shift_shallow(ZX_sub(h2s,h13),1),
     551                 :            :                  ZX_sub(RgX_shift_shallow(h3s,2),RgX_shift_shallow(h12,1)));
     552                 :            :   (void)E;
     553                 :       7476 :   return gen_ZpX_Dixon(ZXV_Z_mul(F, utoi(3)), V, qM, utoi(3), M, NULL,
     554                 :            :                                                  _can_lin, _can_invl);
     555                 :            : }
     556                 :            : 
     557                 :            : static GEN
     558                 :       3717 : F3x_canonlift(GEN P, long n)
     559                 :       3717 : { return gen_ZpX_Newton(Flx_to_ZX(P),utoi(3), n, NULL, _can_iter, _can_invd); }
     560                 :            : 
     561                 :      29050 : static GEN _can5_invl(void *E, GEN V) {(void) E; return V; }
     562                 :            : 
     563                 :       8750 : static GEN _can5_lin(void *E, GEN F, GEN V, GEN q)
     564                 :            : {
     565                 :       8750 :   ulong p = *(ulong*)E;
     566                 :       8750 :   GEN v = RgX_splitting(V, p);
     567                 :       8750 :   return FpX_sub(V,ZXV_dotproduct(v, F), q);
     568                 :            : }
     569                 :            : 
     570                 :            : /* P(X,t) -> P(X*t^n,t) mod (t^p-1) */
     571                 :            : static GEN
     572                 :      61131 : _shift(GEN P, long n, ulong p, long v)
     573                 :            : {
     574                 :      61131 :   long i, l=lg(P);
     575                 :      61131 :   GEN r = cgetg(l,t_POL); r[1] = P[1];
     576         [ +  + ]:     469924 :   for(i=2;i<l;i++)
     577                 :            :   {
     578                 :     408793 :     long s = n*(i-2)%p;
     579                 :     408793 :     GEN ci = gel(P,i);
     580         [ +  + ]:     408793 :     if (typ(ci)==t_INT)
     581                 :     101878 :       gel(r,i) = monomial(ci, s, v);
     582                 :            :     else
     583                 :     306915 :       gel(r,i) = RgX_rotate_shallow(ci, s, p);
     584                 :            :   }
     585                 :      61131 :   return FpXX_renormalize(r, l);
     586                 :            : }
     587                 :            : 
     588                 :            : struct _can_mul
     589                 :            : {
     590                 :            :   GEN T, q;
     591                 :            :   ulong p;
     592                 :            : };
     593                 :            : 
     594                 :            : static GEN
     595                 :      40831 : _can5_mul(void *E, GEN A, GEN B)
     596                 :            : {
     597                 :      40831 :   struct _can_mul *d = (struct _can_mul *)E;
     598                 :      40831 :   GEN a = gel(A,1), b = gel(B,1);
     599                 :      40831 :   long n = itos(gel(A,2));
     600                 :      40831 :   GEN bn = _shift(b, n, d->p, get_FpX_var(d->T));
     601                 :      40831 :   GEN c = FpXQX_mul(a, bn, d->T, d->q);
     602                 :      40831 :   return mkvec2(c, addii(gel(A,2), gel(B,2)));
     603                 :            : }
     604                 :            : 
     605                 :            : static GEN
     606                 :      40691 : _can5_sqr(void *E, GEN A)
     607                 :            : {
     608                 :      40691 :   return _can5_mul(E,A,A);
     609                 :            : }
     610                 :            : 
     611                 :            : static GEN
     612                 :      20300 : _can5_iter(void *E, GEN f, GEN q)
     613                 :            : {
     614                 :      20300 :   pari_sp av = avma;
     615                 :            :   struct _can_mul D;
     616                 :      20300 :   ulong p = *(ulong*)E;
     617                 :      20300 :   long i, vT = fetch_var();
     618                 :            :   GEN N, P, d, V, fs;
     619                 :      20300 :   D.q = q; D.T = ZX_Z_sub(monomial(gen_1,p,vT),gen_1);
     620                 :      20300 :   D.p = p;
     621                 :      20300 :   fs = mkvec2(_shift(f, 1, p, vT), gen_1);
     622                 :      20300 :   N = gel(gen_powu(fs,p-1,(void*)&D,_can5_sqr,_can5_mul),1);
     623                 :      20300 :   N = simplify_shallow(FpXQX_red(N,polcyclo(p,vT),q));
     624                 :      20300 :   P = FpX_mul(N,f,q);
     625                 :      20300 :   P = RgX_deflate(P, p);
     626                 :      20300 :   d = RgX_splitting(N, p);
     627                 :      20300 :   V = cgetg(p+1,t_VEC);
     628                 :      20300 :   gel(V,1) = ZX_mulu(gel(d,1), p);
     629         [ +  + ]:     102214 :   for(i=2; i<= (long)p; i++)
     630                 :      81914 :     gel(V,i) = ZX_mulu(RgX_shift_shallow(gel(d,p+2-i), 1), p);
     631                 :      20300 :   (void)delete_var(); return gerepilecopy(av, mkvec2(ZX_sub(f,P),V));
     632                 :            : }
     633                 :            : 
     634                 :            : static GEN
     635                 :      20300 : _can5_invd(void *E, GEN H, GEN v, GEN qM, long M)
     636                 :            : {
     637                 :      20300 :   ulong p = *(long*)E;
     638                 :      20300 :   return gen_ZpX_Dixon(gel(v,2), H, qM, utoi(p), M, E, _can5_lin, _can5_invl);
     639                 :            : }
     640                 :            : 
     641                 :            : static GEN
     642                 :      13832 : Flx_canonlift(GEN P, long n, ulong p)
     643                 :            : {
     644         [ +  + ]:      23947 :   return p==3 ? F3x_canonlift(P,n):
     645                 :      10115 :          gen_ZpX_Newton(Flx_to_ZX(P),utoi(p), n, &p, _can5_iter, _can5_invd);
     646                 :            : }
     647                 :            : 
     648                 :            : /* assume a and n  are coprime */
     649                 :            : static GEN
     650                 :      76118 : RgX_circular_shallow(GEN P, long a, long n)
     651                 :            : {
     652                 :      76118 :   long i, l = lgpol(P);
     653                 :      76118 :   GEN Q = cgetg(2+n,t_POL);
     654                 :      76118 :   Q[1] = P[1];
     655         [ +  + ]:     510923 :   for(i=0; i<l; i++)
     656                 :     434805 :     gel(Q,2+(i*a)%n) = gel(P,2+i);
     657         [ +  + ]:     168399 :   for(   ; i<n; i++)
     658                 :      92281 :     gel(Q,2+(i*a)%n) = gen_0;
     659                 :      76118 :   return normalizepol_lg(Q,2+n);
     660                 :            : }
     661                 :            : 
     662                 :            : static GEN
     663                 :      76118 : ZpXQ_frob_cyc(GEN x, GEN T, GEN q, ulong p)
     664                 :            : {
     665                 :      76118 :   long n = get_FpX_degree(T);
     666                 :      76118 :   return FpX_rem(RgX_circular_shallow(x,p,n+1), T, q);
     667                 :            : }
     668                 :            : 
     669                 :            : static GEN
     670                 :     112588 : ZpXQ_frob(GEN x, GEN Xm, GEN T, GEN q, ulong p)
     671                 :            : {
     672         [ +  + ]:     112588 :   if (lg(Xm)==1)
     673                 :      43344 :     return ZpXQ_frob_cyc(x, T, q, p);
     674                 :            :   else
     675                 :            :   {
     676                 :      69244 :     long n = get_FpX_degree(T);
     677                 :      69244 :     GEN V = RgX_blocks(RgX_inflate(x, p), n, p);
     678                 :      69244 :     GEN W = ZXV_dotproduct(V, Xm);
     679                 :     112588 :     return FpX_rem(W, T, q);
     680                 :            :   }
     681                 :            : }
     682                 :            : 
     683                 :            : struct _lift_lin
     684                 :            : {
     685                 :            :   ulong p;
     686                 :            :   GEN sqx, Tp;
     687                 :            :   GEN ai, Xm;
     688                 :            : };
     689                 :            : 
     690                 :      83524 : static GEN _lift_invl(void *E, GEN x)
     691                 :            : {
     692                 :      83524 :   struct _lift_lin *d = (struct _lift_lin *) E;
     693                 :      83524 :   GEN T = d->Tp;
     694                 :      83524 :   ulong p = d->p;
     695                 :      83524 :   GEN xai = Flxq_mul(ZX_to_Flx(x, p), d->ai, T, p);
     696                 :      83524 :   return Flx_to_ZX(Flxq_lroot_fast(xai, d->sqx, T, p));
     697                 :            : }
     698                 :            : 
     699                 :      23492 : static GEN _lift_lin(void *E, GEN F, GEN x2, GEN q)
     700                 :            : {
     701                 :      23492 :   struct _lift_lin *d = (struct _lift_lin *) E;
     702                 :      23492 :   pari_sp av = avma;
     703                 :      23492 :   GEN T = gel(F,3), Xm = gel(F,4);
     704                 :      23492 :   GEN y2  = ZpXQ_frob(x2, Xm, T, q, d->p);
     705                 :      23492 :   GEN lin = FpX_add(ZX_mul(gel(F,1), y2), ZX_mul(gel(F,2), x2), q);
     706                 :      23492 :   return gerepileupto(av, FpX_rem(lin, T, q));
     707                 :            : }
     708                 :            : 
     709                 :            : static GEN
     710                 :     180096 : FpM_FpXV_bilinear(GEN P, GEN X, GEN Y, GEN p)
     711                 :            : {
     712                 :     180096 :    pari_sp av = avma;
     713                 :     180096 :    GEN s =  ZX_mul(FpXV_FpC_mul(X,gel(P,1),p),gel(Y,1));
     714                 :     180096 :    long i, l = lg(P);
     715         [ +  + ]:     844494 :    for(i=2; i<l; i++)
     716                 :     664398 :      s = ZX_add(s, ZX_mul(FpXV_FpC_mul(X,gel(P,i),p),gel(Y,i)));
     717                 :     180096 :    return gerepileupto(av, FpX_red(s, p));
     718                 :            : }
     719                 :            : 
     720                 :            : static GEN
     721                 :     180096 : FpM_FpXQV_bilinear(GEN P, GEN X, GEN Y, GEN T, GEN p)
     722                 :            : {
     723                 :     180096 :   return FpX_rem(FpM_FpXV_bilinear(P,X,Y,p),T,p);
     724                 :            : }
     725                 :            : 
     726                 :            : static GEN
     727                 :     120064 : FpXC_powderiv(GEN M, GEN p)
     728                 :            : {
     729                 :            :   long i, l;
     730                 :     120064 :   long v = varn(gel(M,2));
     731                 :     120064 :   GEN m = cgetg_copy(M, &l);
     732                 :     120064 :   gel(m,1) = pol_0(v);
     733                 :     120064 :   gel(m,2) = pol_1(v);
     734         [ +  + ]:     442932 :   for(i=2; i<l-1; i++)
     735                 :     322868 :     gel(m,i+1) = FpX_Fp_mul(gel(M,i),utoi(i), p);
     736                 :     120064 :   return m;
     737                 :            : }
     738                 :            : 
     739                 :            : struct _lift_iso
     740                 :            : {
     741                 :            :   GEN phi;
     742                 :            :   GEN Xm,T;
     743                 :            :   GEN sqx, Tp;
     744                 :            :   ulong p;
     745                 :            : };
     746                 :            : 
     747                 :            : static GEN
     748                 :      60032 : _lift_iter(void *E, GEN x2, GEN q)
     749                 :            : {
     750                 :      60032 :   struct _lift_iso *d = (struct _lift_iso *) E;
     751                 :      60032 :   ulong p = d->p;
     752                 :      60032 :   long n = lg(d->phi)-2;
     753                 :      60032 :   GEN TN = FpXT_red(d->T, q), XN = FpXV_red(d->Xm, q);
     754                 :      60032 :   GEN y2 = ZpXQ_frob(x2, XN, TN, q, p);
     755                 :      60032 :   GEN xp = FpXQ_powers(x2, n, TN, q);
     756                 :      60032 :   GEN yp = FpXQ_powers(y2, n, TN, q);
     757                 :      60032 :   GEN V  = FpM_FpXQV_bilinear(d->phi,xp,yp,TN,q);
     758                 :      60032 :   return mkvec3(V,xp,yp);
     759                 :            : }
     760                 :            : 
     761                 :            : static GEN
     762                 :      60032 : _lift_invd(void *E, GEN V, GEN v, GEN qM, long M)
     763                 :            : {
     764                 :      60032 :   struct _lift_iso *d = (struct _lift_iso *) E;
     765                 :            :   struct _lift_lin e;
     766                 :      60032 :   ulong p = d->p;
     767                 :      60032 :   GEN TM = FpXT_red(d->T, qM), XM = FpXV_red(d->Xm, qM);
     768                 :      60032 :   GEN xp = FpXV_red(gel(v,2), qM);
     769                 :      60032 :   GEN yp = FpXV_red(gel(v,3), qM);
     770                 :      60032 :   GEN Dx = FpM_FpXQV_bilinear(d->phi, FpXC_powderiv(xp, qM), yp, TM, qM);
     771                 :      60032 :   GEN Dy = FpM_FpXQV_bilinear(d->phi, xp, FpXC_powderiv(yp, qM), TM, qM);
     772                 :      60032 :   GEN F = mkvec4(Dy, Dx, TM, XM);
     773                 :      60032 :   e.ai = Flxq_inv(ZX_to_Flx(Dy,p),d->Tp,p);
     774                 :      60032 :   e.sqx = d->sqx; e.Tp = d->Tp; e.p=p; e.Xm = XM;
     775                 :      60032 :   return gen_ZpX_Dixon(F,V,qM,utoi(p),M,(void*) &e, _lift_lin, _lift_invl);
     776                 :            : }
     777                 :            : 
     778                 :            : static GEN
     779                 :      24920 : lift_isogeny(GEN phi, GEN x0, long n, GEN Xm, GEN T, GEN sqx, GEN Tp, ulong p)
     780                 :            : {
     781                 :            :   struct _lift_iso d;
     782                 :      24920 :   d.phi=phi;
     783                 :      24920 :   d.Xm=Xm; d.T=T;
     784                 :      24920 :   d.sqx=sqx; d.Tp=Tp; d.p=p;
     785                 :      24920 :   return gen_ZpX_Newton(x0, utoi(p), n,(void*)&d, _lift_iter, _lift_invd);
     786                 :            : }
     787                 :            : 
     788                 :            : static GEN
     789                 :      24906 : getc2(GEN act, GEN X, GEN T, GEN q, ulong p, long N)
     790                 :            : {
     791                 :      24906 :   GEN A1 = RgV_to_RgX(gel(act,1),0), A2 =  RgV_to_RgX(gel(act,2),0);
     792                 :      24906 :   long n = brent_kung_optpow(maxss(degpol(A1),degpol(A2)),2,1);
     793                 :      24906 :   GEN xp = FpXQ_powers(X,n,T,q);
     794                 :      24906 :   GEN P  = FpX_FpXQV_eval(A1, xp, T, q);
     795                 :      24906 :   GEN Q  = FpX_FpXQV_eval(A2, xp, T, q);
     796                 :      24906 :   return FpXQ_mul(P,ZpXQ_inv(Q,T,utoi(p),N),T,q);
     797                 :            : }
     798                 :            : 
     799                 :            : struct _ZpXQ_norm
     800                 :            : {
     801                 :            :   long n;
     802                 :            :   GEN T, p;
     803                 :            : };
     804                 :            : 
     805                 :            : static GEN
     806                 :      32774 : ZpXQ_norm_mul(void *E, GEN x, GEN y)
     807                 :            : {
     808                 :      32774 :   struct _ZpXQ_norm *D = (struct _ZpXQ_norm*)E;
     809                 :      32774 :   GEN P = gel(x,1), Q = gel(y,1);
     810                 :      32774 :   long a = mael(x,2,1), b = mael(y,2,1);
     811                 :      32774 :   retmkvec2(FpXQ_mul(P,ZpXQ_frob_cyc(Q, D->T, D->p, a), D->T, D->p),
     812                 :            :             mkvecsmall((a*b)%D->n));
     813                 :            : }
     814                 :            : 
     815                 :            : static GEN
     816                 :      22680 : ZpXQ_norm_sqr(void *E, GEN x)
     817                 :            : {
     818                 :      22680 :   return ZpXQ_norm_mul(E, x, x);
     819                 :            : }
     820                 :            : 
     821                 :            : /* Assume T = Phi_(n) and n prime */
     822                 :            : GEN
     823                 :      11326 : ZpXQ_norm_pcyc(GEN x, GEN T, GEN q, GEN p)
     824                 :            : {
     825                 :            :   GEN z;
     826                 :            :   struct _ZpXQ_norm D;
     827                 :      11326 :   long d = get_FpX_degree(T);
     828                 :      11326 :   D.T = T; D.p = q; D.n = d+1;
     829         [ -  + ]:      11326 :   if (d==1) return ZX_copy(x);
     830                 :      11326 :   z = mkvec2(x,mkvecsmall(p[2]));
     831                 :      11326 :   z = gen_powu(z,d,(void*)&D,ZpXQ_norm_sqr,ZpXQ_norm_mul);
     832                 :      11326 :   return gmael(z,1,2);
     833                 :            : }
     834                 :            : 
     835                 :            : /* Assume T = Phi_(n) and n prime */
     836                 :            : static GEN
     837                 :      11088 : ZpXQ_sqrtnorm_pcyc(GEN x, GEN T, GEN q, GEN p, long e)
     838                 :            : {
     839                 :      11088 :   GEN z = ZpXQ_norm_pcyc(x, T, q, p);
     840                 :      11088 :   return Zp_sqrtlift(z,Fp_sqrt(z,p),p,e);
     841                 :            : }
     842                 :            : 
     843                 :            : /* Assume a = 1 [p], return the square root of the norm */
     844                 :            : static GEN
     845                 :      13832 : ZpXQ_sqrtnorm(GEN a, GEN T, GEN q, GEN p, long e)
     846                 :            : {
     847                 :      13832 :   GEN s = Fp_div(FpXQ_trace(ZpXQ_log(a, T, p, e), T, q), gen_2, q);
     848                 :      13832 :   return modii(gel(Qp_exp(cvtop(s, p, e-1)),4), q);
     849                 :            : }
     850                 :            : 
     851                 :            : struct _teich_lin
     852                 :            : {
     853                 :            :   ulong p;
     854                 :            :   GEN sqx, Tp;
     855                 :            :   long m;
     856                 :            : };
     857                 :            : 
     858                 :            : static GEN
     859                 :      29036 : _teich_invl(void *E, GEN x)
     860                 :            : {
     861                 :      29036 :   struct _teich_lin *d = (struct _teich_lin *) E;
     862                 :      29036 :   ulong p = d->p;
     863                 :      29036 :   GEN T = d->Tp;
     864                 :      29036 :   return Flx_to_ZX(Flxq_lroot_fast(ZX_to_Flx(x, p), d->sqx, T, p));
     865                 :            : }
     866                 :            : 
     867                 :            : static GEN
     868                 :       8736 : _teich_lin(void *E, GEN F, GEN x2, GEN q)
     869                 :            : {
     870                 :       8736 :   struct _teich_lin *d = (struct _teich_lin *) E;
     871                 :       8736 :   pari_sp av = avma;
     872                 :       8736 :   GEN T = gel(F,2), Xm = gel(F,3);
     873                 :       8736 :   GEN y2  = ZpXQ_frob(x2, Xm, T, q, d->p);
     874                 :       8736 :   GEN lin = FpX_sub(y2, ZX_mulu(ZX_mul(gel(F,1), x2), d->p), q);
     875                 :       8736 :   return gerepileupto(av, FpX_rem(lin, T, q));
     876                 :            : }
     877                 :            : 
     878                 :            : struct _teich_iso
     879                 :            : {
     880                 :            :   GEN Xm, T;
     881                 :            :   GEN sqx, Tp;
     882                 :            :   ulong p;
     883                 :            : };
     884                 :            : 
     885                 :            : static GEN
     886                 :      20300 : _teich_iter(void *E, GEN x2, GEN q)
     887                 :            : {
     888                 :      20300 :   struct _teich_iso *d = (struct _teich_iso *) E;
     889                 :      20300 :   ulong p = d->p;
     890                 :      20300 :   GEN TN = FpXT_red(d->T, q), XN = FpXV_red(d->Xm, q);
     891                 :      20300 :   GEN y2 = ZpXQ_frob(x2, XN, TN, q, d->p);
     892                 :      20300 :   GEN x1 = FpXQ_powu(x2, p-1, TN, q);
     893                 :      20300 :   GEN xp = FpXQ_mul(x2, x1, TN, q);
     894                 :      20300 :   GEN V = FpX_sub(y2,xp,q);
     895                 :      20300 :   return mkvec2(V,x1);
     896                 :            : }
     897                 :            : 
     898                 :            : static GEN
     899                 :      20300 : _teich_invd(void *E, GEN V, GEN v, GEN qM, long M)
     900                 :            : {
     901                 :      20300 :   struct _teich_iso *d = (struct _teich_iso *) E;
     902                 :            :   struct _teich_lin e;
     903                 :      20300 :   ulong p = d->p;
     904                 :      20300 :   GEN TM = FpXT_red(d->T, qM), XM = FpXV_red(d->Xm, qM);
     905                 :      20300 :   GEN x1 = FpX_red(gel(v,2), qM);
     906                 :      20300 :   GEN F = mkvec3(x1, TM, XM);
     907                 :      20300 :   e.sqx = d->sqx; e.Tp = d->Tp; e.p=p;
     908                 :      20300 :   return gen_ZpX_Dixon(F,V,qM,utoi(p),M,(void*) &e, _teich_lin, _teich_invl);
     909                 :            : }
     910                 :            : 
     911                 :            : static GEN
     912                 :      10115 : Teichmuller_lift(GEN x, GEN Xm, GEN T, GEN sqx, GEN Tp, ulong p, long N)
     913                 :            : {
     914                 :            :   struct _teich_iso d;
     915                 :      10115 :   d.Xm = Xm; d.T = T; d.sqx = sqx; d.Tp = Tp; d.p = p;
     916                 :      10115 :   return gen_ZpX_Newton(x,utoi(p), N,(void*)&d, _teich_iter, _teich_invd);
     917                 :            : }
     918                 :            : 
     919                 :            : static GEN
     920                 :      24920 : get_norm(GEN a4, GEN a6, GEN T, ulong p, long N)
     921                 :            : {
     922                 :      24920 :   long sv=T[1];
     923                 :            :   GEN a;
     924         [ +  + ]:      24920 :   if (p==3) a = gel(a4,1);
     925                 :            :   else
     926                 :            :   {
     927                 :      10115 :     GEN P = mkpoln(4, pol1_Flx(sv), pol0_Flx(sv), a4, a6);
     928                 :      10115 :     a = gel(FlxqX_pow(P,p>>1,T,p),2+p-1);
     929                 :            :   }
     930                 :      24920 :   return Zp_sqrtnlift(gen_1,subss(p,1),utoi(Flxq_norm(a,T,p)),utoi(p), N);
     931                 :            : }
     932                 :            : 
     933                 :            : static GEN
     934                 :      24906 : fill_pols(long n, const long *v, long m, const long *vn,
     935                 :            :           const long *vd, GEN *act)
     936                 :            : {
     937                 :            :   long i, j;
     938                 :      24906 :   long d = upowuu(n,12/(n-1));
     939                 :      24906 :   GEN N, D, M = zeromatcopy(n+1,n+1);
     940                 :      24906 :   gmael(M,1,n+1) = gen_1;
     941         [ +  + ]:     119910 :   for(i=2;i<=n+1;i++)
     942         [ +  + ]:     336063 :     for(j=i-1;j<=n;j++)
     943                 :     241059 :       gmael(M,i,j) = mulis(powuu(d,i-2),v[j-i+1]);
     944                 :      24906 :   N = cgetg(m+1,t_COL);
     945                 :      24906 :   D = cgetg(m+1,t_COL);
     946         [ +  + ]:     134701 :   for(i=1;i<=m;i++)
     947                 :            :   {
     948                 :     109795 :     gel(N,i) = stoi(*vn++);
     949                 :     109795 :     gel(D,i) = stoi(*vd++);
     950                 :            :   }
     951                 :      24906 :   *act = mkmat2(N,D);
     952                 :      24906 :   return M;
     953                 :            : }
     954                 :            : 
     955                 :            : /*
     956                 :            :   These polynomials were extracted from the ECHIDNA databases
     957                 :            :   available at <http://echidna.maths.usyd.edu.au/echidna/>
     958                 :            :   and computed by David R. Kohel.
     959                 :            :   Return the matrix of the modular polynomial, set act to the parametrization,
     960                 :            :   and set dj to the opposite of the supersingular j-invariant.
     961                 :            : */
     962                 :            : static GEN
     963                 :      24906 : get_Kohel_polynomials(ulong p, GEN *act, long *dj)
     964                 :            : {
     965                 :      24906 :   const long mat3[] = {-1,-36,-270};
     966                 :      24906 :   const long num3[] = {1,-483,-21141,-59049};
     967                 :      24906 :   const long den3[] = {1,261, 4347, -6561};
     968                 :      24906 :   const long mat5[] = {-1,-30,-315,-1300,-1575};
     969                 :      24906 :   const long num5[] = {-1,490,20620,158750,78125};
     970                 :      24906 :   const long den5[] = {-1,-254,-4124,-12250,3125};
     971                 :      24906 :   const long mat7[] = {-1,-28,-322,-1904,-5915,-8624,-4018};
     972                 :      24906 :   const long num7[] = {1,-485,-24058,-343833,-2021642,-4353013,-823543};
     973                 :      24906 :   const long den7[] = {1,259,5894,49119,168406,166355,-16807};
     974                 :      24906 :   const long mat13[]= {-1,-26,-325,-2548,-13832,-54340,-157118,-333580,-509366,
     975                 :            :                        -534820,-354536,-124852,-15145};
     976                 :      24906 :   const long num13[]= {1,-487,-24056,-391463,-3396483,-18047328,-61622301,
     977                 :            :                        -133245853,-168395656,-95422301,-4826809};
     978                 :      24906 :   const long den13[]= {1,257,5896,60649,364629,1388256,3396483,5089019,4065464,
     979                 :            :                        1069939,-28561};
     980   [ +  +  +  +  :      24906 :   switch(p)
                      - ]
     981                 :            :   {
     982                 :            :   case 3:
     983                 :      14805 :     *dj = 0;
     984                 :      14805 :     return fill_pols(3,mat3,4,num3,den3,act);
     985                 :            :   case 5:
     986                 :      10080 :     *dj = 0;
     987                 :      10080 :     return fill_pols(5,mat5,5,num5,den5,act);
     988                 :            :   case 7:
     989                 :         14 :     *dj = 1;
     990                 :         14 :     return fill_pols(7,mat7,7,num7,den7,act);
     991                 :            :   case 13:
     992                 :          7 :     *dj = 8;
     993                 :          7 :     return fill_pols(13,mat13,11,num13,den13,act);
     994                 :            :   }
     995                 :          0 :   *dj=0; *act = NULL;
     996                 :      24906 :   return NULL;
     997                 :            : }
     998                 :            : 
     999                 :            : long
    1000                 :      32066 : zx_is_pcyc(GEN T)
    1001                 :            : {
    1002                 :      32066 :   long i, n = degpol(T);
    1003         [ +  + ]:      32066 :   if (!uisprime(n+1))
    1004                 :      11443 :     return 0;
    1005         [ +  + ]:      98994 :   for (i=0; i<=n; i++)
    1006         [ +  + ]:      87668 :     if (T[i+2]!=1UL)
    1007                 :       9296 :       return 0;
    1008                 :      32065 :   return 1;
    1009                 :            : }
    1010                 :            : 
    1011                 :            : static GEN
    1012                 :      24906 : Flxq_ellcard_Kohel(GEN a4, GEN a6, GEN T, ulong p)
    1013                 :            : {
    1014                 :      24906 :   pari_sp av = avma, av2;
    1015                 :            :   pari_timer ti;
    1016                 :      24906 :   long n = get_Flx_degree(T), N = (n+4)/2, dj;
    1017                 :      24906 :   GEN q = powuu(p, N);
    1018                 :            :   GEN T2, Xm, s1, c2, t, lr;
    1019                 :            :   GEN S1, sqx;
    1020                 :            :   GEN Nc2, Np;
    1021                 :      24906 :   GEN act, phi = get_Kohel_polynomials(p, &act, &dj);
    1022                 :      24906 :   long ispcyc = zx_is_pcyc(get_Flx_mod(T));
    1023                 :      24906 :   timer_start(&ti);
    1024         [ +  + ]:      24906 :   if (!ispcyc)
    1025                 :            :   {
    1026                 :      13818 :     T2 = Flx_canonlift(get_Flx_mod(T),N,p);
    1027         [ -  + ]:      13818 :     if (DEBUGLEVEL) timer_printf(&ti,"Teich");
    1028                 :            :   } else
    1029                 :      11088 :     T2 = Flx_to_ZX(get_Flx_mod(T));
    1030                 :      24906 :   T2 = FpX_get_red(T2, q); T = ZXT_to_FlxT(T2, p);
    1031                 :      24906 :   av2 = avma;
    1032         [ -  + ]:      24906 :   if (DEBUGLEVEL) timer_printf(&ti,"Barrett");
    1033         [ +  + ]:      24906 :   if (!ispcyc)
    1034                 :            :   {
    1035                 :      13818 :     Xm = FpXQ_powers(monomial(gen_1,n,get_FpX_var(T2)),p-1,T2,q);
    1036         [ -  + ]:      13818 :     if (DEBUGLEVEL) timer_printf(&ti,"Xm");
    1037                 :            :   } else
    1038                 :      11088 :     Xm = cgetg(1,t_VEC);
    1039                 :      24906 :   s1 = Flxq_inv(Flx_Fl_add(Flxq_ellj(a4,a6,T,p),dj, p),T,p);
    1040                 :      24906 :   lr = Flxq_lroot(polx_Flx(get_Flx_var(T)), T, p);
    1041                 :      24906 :   sqx = Flxq_powers(lr, p-1, T, p);
    1042                 :      24906 :   S1 = lift_isogeny(phi, Flx_to_ZX(s1), N, Xm, T2, sqx, T ,p);
    1043         [ -  + ]:      24906 :   if (DEBUGLEVEL) timer_printf(&ti,"Lift isogeny");
    1044                 :      24906 :   c2 = getc2(act, S1, T2, q, p, N);
    1045         [ -  + ]:      24906 :   if (DEBUGLEVEL) timer_printf(&ti,"c^2");
    1046 [ +  + ][ +  - ]:      24906 :   if (p>3 && !ispcyc)
    1047                 :            :   {
    1048                 :      10101 :     GEN c2p = Flx_to_ZX(Flxq_inv(ZX_to_Flx(c2,p),T,p));
    1049                 :      10101 :     GEN tc2 = Teichmuller_lift(c2p,Xm, T2,sqx,T,p,N);
    1050         [ -  + ]:      10101 :     if (DEBUGLEVEL) timer_printf(&ti,"Teichmuller/Fq");
    1051                 :      10101 :     c2 = FpX_rem(FpX_mul(tc2,c2,q),T2,q);
    1052                 :            :   }
    1053                 :      24906 :   c2 = gerepileupto(av2, c2);
    1054         [ -  + ]:      24906 :   if (DEBUGLEVEL) timer_printf(&ti,"tc2");
    1055         [ +  + ]:      24906 :   Nc2 = (ispcyc? ZpXQ_sqrtnorm_pcyc: ZpXQ_sqrtnorm)(c2, T2, q, utoi(p), N);
    1056         [ -  + ]:      24906 :   if (DEBUGLEVEL) timer_printf(&ti,"Norm");
    1057                 :      24906 :   Np = get_norm(a4,a6,T,p,N);
    1058 [ +  + ][ -  + ]:      24906 :   if (p>3 && ispcyc)
    1059                 :            :   {
    1060                 :          0 :     GEN Ncpi =  utoi(Fl_inv(umodiu(Nc2,p), p));
    1061                 :          0 :     GEN tNc2 = Zp_sqrtnlift(gen_1, subss(p,1), Ncpi, utoi(p),N);
    1062         [ #  # ]:          0 :     if (DEBUGLEVEL) timer_printf(&ti,"Teichmuller/Fp");
    1063                 :          0 :     Nc2 = Fp_mul(Nc2,tNc2,q);
    1064                 :            :   }
    1065                 :      24906 :   t = Fp_center(Fp_mul(Nc2,Np,q),q,shifti(q,-1));
    1066                 :      24906 :   return gerepileupto(av, subii(addis(powuu(p,n),1),t));
    1067                 :            : }
    1068                 :            : 
    1069                 :            : static void
    1070                 :         14 : liftcurve(GEN J, GEN T, GEN q, ulong p, long N, GEN *A4, GEN *A6)
    1071                 :            : {
    1072                 :         14 :   pari_sp av = avma;
    1073                 :         14 :   GEN r = ZpXQ_inv(Z_ZX_sub(utoi(1728),J),T,utoi(p),N);
    1074                 :         14 :   GEN g = FpXQ_mul(J,r,T,q);
    1075                 :         14 :   *A4 = FpX_mulu(g,3,q);
    1076                 :         14 :   *A6 = FpX_mulu(g,2,q);
    1077                 :         14 :   gerepileall(av,2,A4,A6);
    1078                 :         14 : }
    1079                 :            : 
    1080                 :            : static GEN
    1081                 :         14 : getc5(GEN H, GEN A40, GEN A60, GEN A41, GEN A61, GEN T, GEN q, ulong p, long N)
    1082                 :            : {
    1083                 :         14 :   long d = lg(H)-1;
    1084         [ -  + ]:         14 :   GEN s1 = gel(H,d-1), s2 = gel(H,d-2), s3 = d<5 ? pol_0(varn(T)): gel(H,d-3);
    1085                 :         14 :   GEN s12 = FpXQ_sqr(s1,T,q);
    1086                 :         14 :   GEN h2 = ZX_sub(ZX_shifti(s2,1),s12); /*2*s2-s1^2*/
    1087                 :         14 :   GEN h3 = ZX_sub(FpXQ_mul(ZX_add(h2,s2),s1,T,q),ZX_mulu(s3,3));
    1088                 :            :                                         /*3*s2*s1-s1^3-3s3*/
    1089                 :         14 :   GEN alpha= ZX_sub(ZX_mulu(h2,30), ZX_mulu(A40,5*p-6)); /* 30*h2+A40*(6-5*p)*/
    1090                 :         14 :   GEN beta = ZX_sub(ZX_sub(ZX_mulu(FpXQ_mul(A40,s1,T,q),42),ZX_mulu(A60,14*p-15)),
    1091                 :            :                     ZX_mulu(h3,70)); /* 42*A40*s1-A60*(14*p-15)-70*h3 */
    1092                 :         14 :   GEN u2 = FpXQ_mul(FpXQ_mul(A41,beta,T,q),
    1093                 :            :                     ZpXQ_inv(FpXQ_mul(A61,alpha,T,q),T,utoi(p),N),T,q);
    1094                 :         14 :   return u2;
    1095                 :            : }
    1096                 :            : 
    1097                 :            : static GEN
    1098                 :         14 : ZpXQX_liftrootmod_vald(GEN f, GEN H, long v, GEN T, GEN p, long e)
    1099                 :            : {
    1100                 :         14 :   pari_sp av = avma, av2, lim;
    1101                 :         14 :   GEN pv = p, q, qv, W, df, Tq, fr, dfr;
    1102                 :            :   ulong mask;
    1103                 :            :   pari_timer ti;
    1104         [ -  + ]:         14 :   if (e <= v+1) return H;
    1105                 :         14 :   df = RgX_deriv(f);
    1106         [ +  - ]:         14 :   if (v) { pv = powiu(p,v); qv = mulii(pv,p); df = ZXX_Z_divexact(df, pv); }
    1107                 :          0 :   else qv = p;
    1108                 :         14 :   mask = quadratic_prec_mask(e-v);
    1109                 :         14 :   Tq = FpXT_red(T, qv); dfr = FpXQX_red(df, Tq, p);
    1110         [ -  + ]:         14 :   if (DEBUGLEVEL) timer_start(&ti);
    1111                 :         14 :   W = FpXQXQ_inv(FpXQX_rem(dfr, H, Tq, p), H, Tq, p); /* 1/f'(a) mod (T,p) */
    1112         [ -  + ]:         14 :   if (DEBUGLEVEL) timer_printf(&ti,"FpXQXQ_inv");
    1113                 :         14 :   q = p;
    1114                 :         14 :   av2 = avma; lim = stack_lim(av2, 2);
    1115                 :            :   for (;;)
    1116                 :            :   {
    1117                 :            :     GEN u, fa, qv, q2v, Tq2, fadH;
    1118                 :         56 :     GEN H2 = H, q2 = q;
    1119                 :         56 :     q = sqri(q);
    1120         [ +  + ]:         56 :     if (mask & 1) q = diviiexact(q,p);
    1121                 :         56 :     mask >>= 1;
    1122         [ +  - ]:         56 :     if (v) { qv = mulii(q, pv); q2v = mulii(q2, pv); }
    1123                 :          0 :     else { qv = q; q2v = q2; }
    1124                 :         56 :     Tq2 = FpXT_red(T, q2v); Tq = FpXT_red(T, qv);
    1125                 :         56 :     fr = FpXQX_red(f, Tq, qv);
    1126                 :         56 :     fa = FpXQX_rem(fr, H, Tq, qv);
    1127                 :         56 :     fa = ZXX_Z_divexact(fa, q2v);
    1128                 :         56 :     fadH = FpXQXQ_mul(RgX_deriv(H),fa,H,Tq2,q2);
    1129                 :         56 :     H = FpXX_add(H, gmul(FpXQXQ_mul(W, fadH, H, Tq2, q2v), q2), qv);
    1130         [ +  + ]:         56 :     if (mask == 1) return gerepileupto(av, H);
    1131                 :         42 :     dfr = FpXQX_rem(FpXQX_red(df, Tq, q),H,Tq,q);
    1132                 :         42 :     u = ZXX_Z_divexact(ZXX_Z_add_shallow(FpXQXQ_mul(W,dfr,H,Tq,q),gen_m1),q2);
    1133                 :         42 :     W = gsub(W,gmul(FpXQXQ_mul(u,W,H2,Tq2,q2),q2));
    1134         [ -  + ]:         42 :     if (low_stack(lim, stack_lim(av2,2)))
    1135                 :            :     {
    1136         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXQX_liftroot, e = %ld", e);
    1137                 :          0 :       gerepileall(av2, 3, &H, &W, &q);
    1138                 :            :     }
    1139                 :         56 :   }
    1140                 :            : }
    1141                 :            : 
    1142                 :            : static GEN
    1143                 :         14 : get_H1(GEN A41, GEN A61, GEN T2, ulong p)
    1144                 :            : {
    1145                 :         14 :   GEN q = utoi(p), T = FpXT_red(T2,q);
    1146                 :         14 :   GEN pol = FpXQ_elldivpol(FpX_red(A41,q),FpX_red(A61,q),p,T,q);
    1147                 :         14 :   return FqX_normalize(RgX_deflate(pol,p),T,q);
    1148                 :            : }
    1149                 :            : 
    1150                 :            : static GEN
    1151                 :         14 : Flxq_ellcard_Harley(GEN a4, GEN a6, GEN T, ulong p)
    1152                 :            : {
    1153                 :         14 :   pari_sp av = avma, av2;
    1154                 :            :   pari_timer ti;
    1155                 :         14 :   long n = get_Flx_degree(T), N = (n+5)/2;
    1156                 :         14 :   GEN q = powuu(p, N);
    1157                 :            :   GEN T2, j, t;
    1158                 :            :   GEN J1,A40,A41,A60,A61, sqx,Xm;
    1159                 :            :   GEN pol, h1, H;
    1160                 :            :   GEN c2, tc2, c2p, Nc2, Np;
    1161                 :         14 :   long ispcyc = zx_is_pcyc(get_Flx_mod(T));
    1162                 :         14 :   timer_start(&ti);
    1163         [ +  - ]:         14 :   if (!ispcyc)
    1164                 :            :   {
    1165                 :         14 :     T2 = Flx_canonlift(get_Flx_mod(T),N,p);
    1166         [ -  + ]:         14 :     if (DEBUGLEVEL) timer_printf(&ti,"Teich");
    1167                 :            :   } else
    1168                 :          0 :     T2 = Flx_to_ZX(get_Flx_mod(T));
    1169                 :         14 :   T2 = FpX_get_red(T2, q); T = ZXT_to_FlxT(T2, p);
    1170                 :         14 :   av2 = avma;
    1171         [ -  + ]:         14 :   if (DEBUGLEVEL) timer_printf(&ti,"Barrett");
    1172         [ +  - ]:         14 :   if (!ispcyc)
    1173                 :            :   {
    1174                 :         14 :     Xm = FpXQ_powers(monomial(gen_1,n,get_FpX_var(T2)),p-1,T2,q);
    1175         [ -  + ]:         14 :     if (DEBUGLEVEL) timer_printf(&ti,"Xm");
    1176                 :            :   } else
    1177                 :          0 :     Xm = cgetg(1,t_VEC);
    1178         [ -  + ]:         14 :   if (DEBUGLEVEL) timer_printf(&ti,"Xm");
    1179                 :         14 :   j = Flxq_ellj(a4,a6,T,p);
    1180                 :         14 :   sqx = Flxq_powers(Flxq_lroot(polx_Flx(T[1]), T, p), p-1, T, p);
    1181                 :         14 :   J1 = lift_isogeny(polmodular_ZM(p, 0), Flx_to_ZX(j), N, Xm, T2,sqx,T,p);
    1182         [ -  + ]:         14 :   if (DEBUGLEVEL) timer_printf(&ti,"Lift isogeny");
    1183                 :         14 :   liftcurve(J1,T2,q,p,N,&A41,&A61);
    1184                 :         14 :   A40 = ZpXQ_frob(A41, Xm, T2, q, p);
    1185                 :         14 :   A60 = ZpXQ_frob(A61, Xm, T2, q, p);
    1186         [ -  + ]:         14 :   if (DEBUGLEVEL) timer_printf(&ti,"liftcurve");
    1187                 :         14 :   pol = FpXQ_elldivpol(A40,A60,p,T2,q);
    1188         [ -  + ]:         14 :   if (DEBUGLEVEL) timer_printf(&ti,"p-division");
    1189                 :         14 :   h1 = get_H1(A41,A61,T2,p);
    1190                 :         14 :   H = ZpXQX_liftrootmod_vald(pol,h1,1,T2,utoi(p),N);
    1191                 :         14 :   q = diviuexact(q,p); N--;
    1192         [ -  + ]:         14 :   if (DEBUGLEVEL) timer_printf(&ti,"kernel");
    1193                 :         14 :   c2 = getc5(H,A40,A60,A41,A61,T2,q,p,N);
    1194         [ -  + ]:         14 :   if (DEBUGLEVEL) timer_printf(&ti,"c^2");
    1195         [ +  - ]:         14 :   if (!ispcyc)
    1196                 :            :   {
    1197                 :         14 :     c2p = Flx_to_ZX(Flxq_inv(ZX_to_Flx(c2,p),T,p));
    1198                 :         14 :     tc2 = Teichmuller_lift(c2p,Xm, T2,sqx,T,p,N);
    1199         [ -  + ]:         14 :     if (DEBUGLEVEL) timer_printf(&ti,"teichmuller");
    1200                 :         14 :     c2 = FpX_rem(FpX_mul(tc2,c2,q),T2,q);
    1201                 :            :   }
    1202                 :         14 :   c2 = gerepileupto(av2, c2);
    1203                 :         14 :   q = powuu(p, N);
    1204         [ -  + ]:         14 :   Nc2 = (ispcyc? ZpXQ_sqrtnorm_pcyc: ZpXQ_sqrtnorm)(c2, T2, q, utoi(p), N);
    1205         [ -  + ]:         14 :   if (DEBUGLEVEL) timer_printf(&ti,"Norm");
    1206                 :         14 :   Np = get_norm(a4,a6,T,p,N);
    1207         [ -  + ]:         14 :   if (ispcyc)
    1208                 :            :   {
    1209                 :          0 :     GEN Ncpi = utoi(Fl_inv(umodiu(Nc2,p), p));
    1210                 :          0 :     GEN tNc2 = Zp_sqrtnlift(gen_1, subss(p,1), Ncpi, utoi(p), N);
    1211         [ #  # ]:          0 :     if (DEBUGLEVEL) timer_printf(&ti,"Teichmuller/Fp");
    1212                 :          0 :     Nc2 = Fp_mul(Nc2,tNc2,q);
    1213                 :            :   }
    1214                 :         14 :   t = Fp_center(Fp_mul(Nc2,Np,q),q,shifti(q,-1));
    1215                 :         14 :   return gerepileupto(av, subii(addis(powuu(p,n),1),t));
    1216                 :            : }
    1217                 :            : 
    1218                 :            : /***************************************************************************/
    1219                 :            : /*                                                                         */
    1220                 :            : /*                          Shanks Mestre                                  */
    1221                 :            : /*                                                                         */
    1222                 :            : /***************************************************************************/
    1223                 :            : 
    1224                 :            : /* Return the lift of a (mod b), which is closest to h */
    1225                 :            : static GEN
    1226                 :         28 : closest_lift(GEN a, GEN b, GEN h)
    1227                 :            : {
    1228                 :         28 :   return addii(a, mulii(b, diviiround(subii(h,a), b)));
    1229                 :            : }
    1230                 :            : 
    1231                 :            : static GEN
    1232                 :         14 : FlxqE_find_order(GEN f, GEN h, GEN bound, GEN B, GEN a4, GEN T, ulong p)
    1233                 :            : {
    1234                 :         14 :   pari_sp av = avma, av1;
    1235                 :            :   pari_timer Ti;
    1236                 :         14 :   long s = itos( gceil(gsqrt(gdiv(bound,B),DEFAULTPREC)) ) >> 1;
    1237                 :            :   GEN tx, ti;
    1238                 :         14 :   GEN fh = FlxqE_mul(f, h, a4, T, p);
    1239                 :         14 :   GEN F, P = fh, fg;
    1240                 :            :   long i;
    1241         [ -  + ]:         14 :   if (DEBUGLEVEL >= 6) timer_start(&Ti);
    1242         [ -  + ]:         14 :   if (ell_is_inf(fh)) return h;
    1243                 :         14 :   F = FlxqE_mul(f, B, a4, T, p);
    1244         [ -  + ]:         14 :   if (s < 3)
    1245                 :            :   { /* we're nearly done: naive search */
    1246                 :          0 :     GEN Q = P;
    1247                 :          0 :     for (i=1;; i++)
    1248                 :            :     {
    1249                 :          0 :       P = FlxqE_add(P, F, a4, T, p); /* h.f + i.F */
    1250         [ #  # ]:          0 :       if (ell_is_inf(P)) return gerepileupto(av, addii(h, mului(i,B)));
    1251                 :          0 :       Q = FlxqE_sub(Q, F, a4, T, p); /* h.f - i.F */
    1252         [ #  # ]:          0 :       if (ell_is_inf(Q)) return gerepileupto(av, subii(h, mului(i,B)));
    1253                 :          0 :     }
    1254                 :            :   }
    1255                 :         14 :   tx = cgetg(s+1,t_VECSMALL);
    1256                 :            :   /* Baby Step/Giant Step */
    1257                 :         14 :   av1 = avma;
    1258         [ +  + ]:        665 :   for (i=1; i<=s; i++)
    1259                 :            :   { /* baby steps */
    1260                 :        651 :     tx[i] = hash_GEN(gel(P, 1));
    1261                 :        651 :     P = FlxqE_add(P, F, a4, T, p); /* h.f + i.F */
    1262         [ -  + ]:        651 :     if (ell_is_inf(P)) return gerepileupto(av, addii(h, mului(i,B)));
    1263         [ -  + ]:        651 :     if (gc_needed(av1,3))
    1264                 :            :     {
    1265         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"[Flxq_ellcard] baby steps, i=%ld",i);
    1266                 :          0 :       P = gerepileupto(av1,P);
    1267                 :            :     }
    1268                 :            :   }
    1269         [ -  + ]:         14 :   if (DEBUGLEVEL >= 6) timer_printf(&Ti, "[Flxq_ellcard] baby steps, s = %ld",s);
    1270                 :            :   /* giant steps: fg = s.F */
    1271                 :         14 :   fg = gerepileupto(av1, FlxqE_sub(P, fh, a4, T, p));
    1272         [ -  + ]:         14 :   if (ell_is_inf(fg)) return gerepileupto(av,mului(s,B));
    1273                 :         14 :   ti = vecsmall_indexsort(tx); /* = permutation sorting tx */
    1274                 :         14 :   tx = perm_mul(tx,ti);
    1275         [ -  + ]:         14 :   if (DEBUGLEVEL >= 6) timer_printf(&Ti, "[Flxq_ellcard] sorting");
    1276                 :         14 :   av1 = avma;
    1277                 :         14 :   for (P=fg, i=1; ; i++)
    1278                 :            :   {
    1279                 :        560 :     long k = hash_GEN(gel(P,1));
    1280                 :        560 :     long r = zv_search(tx, k);
    1281         [ +  + ]:        560 :     if (r)
    1282                 :            :     {
    1283 [ +  - ][ +  + ]:         28 :       while (r && tx[r] == k) r--;
    1284 [ +  - ][ +  - ]:         14 :       for (r++; r <= s && tx[r] == k; r++)
    1285                 :            :       {
    1286                 :         14 :         long j = ti[r]-1;
    1287                 :         14 :         GEN Q = FlxqE_add(FlxqE_mul(F, stoi(j), a4, T, p), fh, a4, T, p);
    1288         [ -  + ]:         14 :         if (DEBUGLEVEL >= 6)
    1289                 :          0 :           timer_printf(&Ti, "[Flxq_ellcard] giant steps, i = %ld",i);
    1290         [ +  - ]:         14 :         if (Flx_equal(gel(P,1), gel(Q,1)))
    1291                 :            :         {
    1292         [ +  - ]:         14 :           if (Flx_equal(gel(P,2), gel(Q,2))) i = -i;
    1293                 :         14 :           return gerepileupto(av,addii(h, mulii(addis(mulss(s,i), j), B)));
    1294                 :            :         }
    1295                 :            :       }
    1296                 :            :     }
    1297                 :        546 :     P = FlxqE_add(P,fg,a4,T,p);
    1298         [ -  + ]:        546 :     if (gc_needed(av1,3))
    1299                 :            :     {
    1300         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"[Flxq_ellcard] giants steps, i=%ld",i);
    1301                 :          0 :       P = gerepileupto(av1,P);
    1302                 :            :     }
    1303                 :        560 :   }
    1304                 :            : }
    1305                 :            : 
    1306                 :            : static void
    1307                 :      20181 : Flx_next(GEN t, ulong p)
    1308                 :            : {
    1309                 :            :   long i;
    1310                 :      20181 :   for(i=2;;i++)
    1311         [ +  + ]:      25690 :     if (uel(t,i)==p-1)
    1312                 :       5509 :       t[i]=0;
    1313                 :            :     else
    1314                 :            :     {
    1315                 :      20181 :       t[i]++;
    1316                 :      20181 :       break;
    1317                 :       5509 :     }
    1318                 :      20181 : }
    1319                 :            : 
    1320                 :            : static void
    1321                 :      20181 : Flx_renormalize_ip(GEN x, long lx)
    1322                 :            : {
    1323                 :            :   long i;
    1324         [ +  + ]:      25690 :   for (i = lx-1; i>=2; i--)
    1325         [ +  + ]:      23919 :     if (x[i]) break;
    1326                 :      20181 :   setlg(x, i+1);
    1327                 :      20181 : }
    1328                 :            : 
    1329                 :            : static ulong
    1330                 :       1204 : F3xq_ellcard_naive(GEN a2, GEN a6, GEN T)
    1331                 :            : {
    1332                 :       1204 :   pari_sp av = avma;
    1333                 :       1204 :   long i, d = get_Flx_degree(T), lx = d+2;
    1334                 :       1204 :   long q = upowuu(3, d), a;
    1335                 :       1204 :   GEN x = zero_zv(lx); x[1] = get_Flx_var(T);
    1336         [ +  + ]:       6538 :   for(a=1, i=0; i<q; i++)
    1337                 :            :   {
    1338                 :            :     GEN rhs;
    1339                 :       5334 :     Flx_renormalize_ip(x, lx);
    1340                 :       5334 :     rhs = Flx_add(Flxq_mul(Flxq_sqr(x, T, 3), Flx_add(x, a2, 3), T, 3), a6, 3);
    1341 [ +  + ][ +  + ]:       5334 :     if (!lgpol(rhs)) a++; else if (Flxq_issquare(rhs, T, 3)) a+=2;
    1342                 :       5334 :     Flx_next(x, 3);
    1343                 :            :   }
    1344                 :       1204 :   avma = av;
    1345                 :       1204 :   return a;
    1346                 :            : }
    1347                 :            : 
    1348                 :            : static ulong
    1349                 :        567 : Flxq_ellcard_naive(GEN a4, GEN a6, GEN T, ulong p)
    1350                 :            : {
    1351                 :        567 :   pari_sp av = avma;
    1352                 :        567 :   long i, d = get_Flx_degree(T), lx = d+2;
    1353                 :        567 :   long q = upowuu(p, d), a;
    1354                 :        567 :   GEN x = zero_zv(lx); x[1] = get_Flx_var(T);
    1355         [ +  + ]:      15414 :   for(a=1, i=0; i<q; i++)
    1356                 :            :   {
    1357                 :            :     GEN x2, rhs;
    1358                 :      14847 :     Flx_renormalize_ip(x, lx);
    1359                 :      14847 :     x2  = Flxq_sqr(x, T, p);
    1360                 :      14847 :     rhs = Flx_add(Flxq_mul(x, Flx_add(x2, a4, p), T, p), a6, p);
    1361 [ +  + ][ +  + ]:      14847 :     if (!lgpol(rhs)) a++; else if (Flxq_issquare(rhs,T,p)) a+=2;
    1362                 :      14847 :     Flx_next(x,p);
    1363                 :            :   }
    1364                 :        567 :   avma = av;
    1365                 :        567 :   return a;
    1366                 :            : }
    1367                 :            : 
    1368                 :            : /* assume T irreducible mod p, m = (q-1)/(p-1) */
    1369                 :            : static int
    1370                 :         27 : Flxq_kronecker(GEN x, GEN m, GEN T, ulong p)
    1371                 :            : {
    1372                 :            :   pari_sp av;
    1373                 :            :   ulong z;
    1374         [ -  + ]:         27 :   if (lgpol(x) == 0) return 0;
    1375                 :         27 :   av = avma;
    1376                 :         27 :   z = Flxq_pow(x, m, T, p)[2];
    1377                 :         27 :   avma = av; return krouu(z, p);
    1378                 :            : }
    1379                 :            : 
    1380                 :            : /* Find x such that kronecker(u = x^3+a4x+a6, p) is KRO.
    1381                 :            :  * Return point [x*u,u^2] on E (KRO=1) / E^twist (KRO=-1) */
    1382                 :            : static GEN
    1383                 :         27 : Flxq_ellpoint(long KRO, GEN a4, GEN a6, GEN m, long n, long vn, GEN T, ulong p)
    1384                 :            : {
    1385                 :            :   for(;;)
    1386                 :            :   {
    1387                 :         27 :     GEN x = random_Flx(n,vn,p);
    1388                 :         27 :     GEN u = Flx_add(a6, Flxq_mul(Flx_add(a4, Flxq_sqr(x,T,p), p), x, T,p), p);
    1389         [ +  + ]:         27 :     if (Flxq_kronecker(u, m,T,p) == KRO)
    1390                 :         14 :       return mkvec2(Flxq_mul(u,x, T,p), Flxq_sqr(u, T,p));
    1391                 :         13 :   }
    1392                 :            : }
    1393                 :            : 
    1394                 :            : static GEN
    1395                 :         14 : Flxq_ellcard_Shanks(GEN a4, GEN a6, GEN q, GEN T, ulong p)
    1396                 :            : {
    1397                 :         14 :   pari_sp av = avma;
    1398                 :         14 :   long vn = get_Flx_var(T), n = get_Flx_degree(T), KRO = -1;
    1399                 :            :   GEN h,f, ta4, A, B, m;
    1400                 :         14 :   GEN q1p = addsi(1, q), q2p = shifti(q1p, 1);
    1401                 :         14 :   GEN bound = addis(sqrti(gmul2n(q,4)), 1); /* ceil( 4sqrt(q) ) */
    1402                 :            :   /* once #E(Flxq) is know mod B >= bound, it is completely determined */
    1403                 :            :   /* how many 2-torsion points ? */
    1404      [ +  -  + ]:         14 :   switch(FlxqX_nbroots(mkpoln(4, pol1_Flx(vn), pol0_Flx(vn), a4, a6), T, p))
    1405                 :            :   {
    1406                 :          7 :   case 3:  A = gen_0; B = utoipos(4); break;
    1407                 :          0 :   case 1:  A = gen_0; B = gen_2; break;
    1408                 :          7 :   default: A = gen_1; B = gen_2; break; /* 0 */
    1409                 :            :   }
    1410                 :         14 :   m = diviuexact(subiu(powuu(p,n), 1), p-1);
    1411                 :            :   for(;;)
    1412                 :            :   {
    1413                 :         14 :     h = closest_lift(A, B, q1p);
    1414                 :            :     /* [ux, u^2] is on E_u: y^2 = x^3 + c4 u^2 x + c6 u^3
    1415                 :            :      * E_u isomorphic to E (resp. E') iff KRO = 1 (resp. -1)
    1416                 :            :      * #E(F_p) = p+1 - a_p, #E'(F_p) = p+1 + a_p
    1417                 :            :      *
    1418                 :            :      * #E_u(Flxq) = A (mod B),  h is close to #E_u(Flxq) */
    1419                 :         14 :     KRO = -KRO;
    1420                 :         14 :     f = Flxq_ellpoint(KRO, a4,a6, m,n,vn, T,p);
    1421                 :            : 
    1422                 :         14 :     ta4 = Flxq_mul(a4, gel(f,2), T, p); /* a4 for E_u */
    1423                 :         14 :     h = FlxqE_find_order(f, h, bound, B, ta4,T,p);
    1424                 :         14 :     h = FlxqE_order(f, h, ta4, T, p);
    1425                 :            :     /* h | #E_u(Flxq) = A (mod B) */
    1426                 :         14 :     A = Z_chinese_all(A, gen_0, B, h, &B);
    1427         [ +  - ]:         14 :     if (cmpii(B, bound) >= 0) break;
    1428                 :            :     /* not done, update A mod B for the _next_ curve, isomorphic to
    1429                 :            :      * the quadratic twist of this one */
    1430                 :          0 :     A = remii(subii(q2p,A), B); /* #E(Fq)+#E'(Fq) = 2q+2 */
    1431                 :          0 :   }
    1432                 :         14 :   h = closest_lift(A, B, q1p);
    1433         [ -  + ]:         14 :   return gerepileuptoint(av, KRO == 1? h: subii(q2p,h));
    1434                 :            : }
    1435                 :            : 
    1436                 :            : static GEN
    1437                 :      16009 : F3xq_ellcard(GEN a2, GEN a6, GEN T)
    1438                 :            : {
    1439                 :      16009 :   long n = get_Flx_degree(T);
    1440         [ +  + ]:      16009 :   if (n <= 2)
    1441                 :        917 :     return utoi(F3xq_ellcard_naive(a2, a6, T));
    1442                 :            :   else
    1443                 :            :   {
    1444                 :      15092 :     GEN q1 = addis(powuu(3, get_Flx_degree(T)), 1), t;
    1445                 :      15092 :     GEN a = Flxq_div(a6,Flxq_powu(a2,3,T,3),T,3);
    1446         [ +  + ]:      15092 :     if (Flx_equal1(Flxq_powu(a, 8, T, 3)))
    1447                 :            :     {
    1448                 :        287 :       GEN P = Flxq_minpoly(a,T,3);
    1449                 :        287 :       long dP = degpol(P); /* dP <= 2 */
    1450                 :        287 :       ulong q = upowuu(3,dP);
    1451                 :        287 :       GEN A2 = pol1_Flx(P[1]), A6 = Flx_rem(polx_Flx(P[1]), P, 3);
    1452                 :        287 :       long tP = q + 1 - F3xq_ellcard_naive(A2, A6, P);
    1453                 :        287 :       t = elltrace_extension(stoi(tP), n/dP, utoi(q));
    1454         [ -  + ]:        287 :       if (umodiu(t, 3)!=1) t = negi(t);
    1455 [ +  + ][ +  + ]:        287 :       return Flx_equal1(a2) || Flxq_issquare(a2,T,3) ? subii(q1,t): addii(q1,t);
    1456                 :            :     }
    1457                 :      16009 :     else return Flxq_ellcard_Kohel(mkvec(a2), a6, T, 3);
    1458                 :            :   }
    1459                 :            : }
    1460                 :            : 
    1461                 :            : static GEN
    1462                 :      10682 : Flxq_ellcard_Satoh(GEN a4, GEN a6, GEN j, GEN T, ulong p)
    1463                 :            : {
    1464                 :      10682 :   long n = get_Flx_degree(T);
    1465         [ +  + ]:      10682 :   if (n <= 2)
    1466                 :        287 :     return utoi(Flxq_ellcard_naive(a4, a6, T, p));
    1467                 :            :   else
    1468                 :            :   {
    1469                 :      10395 :     GEN jp = Flxq_powu(j, p, T, p);
    1470                 :      10395 :     GEN s = Flx_add(j, jp, p);
    1471         [ +  + ]:      10395 :     if (degpol(s) <= 0)
    1472                 :            :     { /* it is assumed j not in F_p */
    1473                 :        280 :       GEN m = Flxq_mul(j, jp, T, p);
    1474         [ +  - ]:        280 :       if (degpol(m) <= 0)
    1475                 :            :       {
    1476                 :        280 :         GEN q = sqru(p);
    1477                 :        280 :         GEN q1 = addis(powuu(p, get_Flx_degree(T)), 1);
    1478                 :        280 :         GEN sk = Flx_Fl_add(Flx_neg(j, p), 1728%p, p);
    1479                 :        280 :         GEN sA4 = Flx_triple(Flxq_mul(sk, j, T, p), p);
    1480                 :        280 :         GEN u = Flxq_div(a4, sA4, T, p);
    1481         [ +  + ]:        280 :         ulong ns = lgpol(s) ? Fl_neg(s[2], p): 0UL;
    1482                 :        280 :         GEN P = mkvecsmall4(T[1], m[2], ns, 1L);
    1483                 :            :         GEN A4, A6, t, tP;
    1484                 :        280 :         Flxq_ellj_to_a4a6(polx_Flx(T[1]), P, p, &A4, &A6);
    1485                 :        280 :         tP = addis(q, 1 - Flxq_ellcard_naive(A4, A6, P, p));
    1486                 :        280 :         t = elltrace_extension(tP, n>>1, q);
    1487         [ +  + ]:        280 :         return Flxq_is2npower(u, 2, T, p) ? subii(q1,t): addii(q1,t);
    1488                 :            :       }
    1489                 :            :     }
    1490 [ +  + ][ +  + ]:      10115 :     if (p<=7 || p==13 ) return Flxq_ellcard_Kohel(a4, a6, T, p);
    1491                 :      10682 :     else return Flxq_ellcard_Harley(a4, a6, T, p);
    1492                 :            :   }
    1493                 :            : }
    1494                 :            : 
    1495                 :            : static GEN
    1496                 :          0 : Flxq_ellcard_Kedlaya(GEN a4, GEN a6, GEN T, ulong p)
    1497                 :            : {
    1498                 :          0 :   pari_sp av = avma;
    1499                 :          0 :   GEN H = mkpoln(4, gen_1, gen_0, Flx_to_ZX(a4), Flx_to_ZX(a6));
    1500                 :          0 :   GEN Tp = Flx_to_ZX(get_Flx_mod(T));
    1501         [ #  # ]:          0 :   long n = degpol(Tp), e = ((p < 16 ? n+1: n)>>1)+1;
    1502                 :          0 :   GEN M = ZlXQX_hyperellpadicfrobenius(H, Tp, p, e);
    1503                 :          0 :   GEN N = ZpXQM_prodFrobenius(M, Tp, utoi(p), e);
    1504                 :          0 :   GEN q = powuu(p, e);
    1505                 :          0 :   GEN tp = Fq_add(gcoeff(N,1,1), gcoeff(N,2,2), Tp, q);
    1506         [ #  # ]:          0 :   GEN t = Fp_center(typ(tp)==t_INT ? tp: leading_term(tp), q, shifti(q,-1));
    1507                 :          0 :   return gerepileupto(av, subii(addis(powuu(p, n), 1), t));
    1508                 :            : }
    1509                 :            : 
    1510                 :            : GEN
    1511                 :      49706 : Flxq_ellj(GEN a4, GEN a6, GEN T, ulong p)
    1512                 :            : {
    1513                 :      49706 :   pari_sp av=avma;
    1514         [ +  + ]:      49706 :   if (p==3)
    1515                 :            :   {
    1516                 :            :     GEN J;
    1517         [ -  + ]:      14805 :     if (typ(a4)!=t_VEC) return pol0_Flx(get_Flx_var(T));
    1518                 :      14805 :     J = Flxq_div(Flxq_powu(gel(a4,1),3, T, p),Flx_neg(a6,p), T, p);
    1519                 :      14805 :     return gerepileuptoleaf(av, J);
    1520                 :            :   }
    1521                 :            :   else
    1522                 :            :   {
    1523                 :      34901 :     pari_sp av=avma;
    1524                 :      34901 :     GEN a43 = Flxq_mul(a4,Flxq_sqr(a4,T,p),T,p);
    1525                 :      34901 :     GEN a62 = Flxq_sqr(a6,T,p);
    1526                 :      34901 :     GEN num = Flx_mulu(a43,6912,p);
    1527                 :      34901 :     GEN den = Flx_add(Flx_mulu(a43,4,p),Flx_mulu(a62,27,p),p);
    1528                 :      49706 :     return gerepileuptoleaf(av, Flxq_div(num, den, T, p));
    1529                 :            :   }
    1530                 :            : }
    1531                 :            : 
    1532                 :            : void
    1533                 :        280 : Flxq_ellj_to_a4a6(GEN j, GEN T, ulong p, GEN *pt_a4, GEN *pt_a6)
    1534                 :            : {
    1535                 :        280 :   ulong zagier = 1728 % p;
    1536         [ -  + ]:        280 :   if (lgpol(j)==0)
    1537                 :          0 :     { *pt_a4 = pol0_Flx(T[1]); *pt_a6 =pol1_Flx(T[1]); }
    1538 [ -  + ][ #  # ]:        280 :   else if (lgpol(j)==1 && uel(j,2) == zagier)
    1539                 :          0 :     { *pt_a4 = pol1_Flx(T[1]); *pt_a6 =pol0_Flx(T[1]); }
    1540                 :            :   else
    1541                 :            :   {
    1542                 :        280 :     GEN k = Flx_Fl_add(Flx_neg(j, p), zagier, p);
    1543                 :        280 :     GEN kj = Flxq_mul(k, j, T, p);
    1544                 :        280 :     GEN k2j = Flxq_mul(kj, k, T, p);
    1545                 :        280 :     *pt_a4 = Flx_triple(kj, p);
    1546                 :        280 :     *pt_a6 = Flx_double(k2j, p);
    1547                 :            :   }
    1548                 :        280 : }
    1549                 :            : 
    1550                 :            : static GEN
    1551                 :       6027 : F3xq_ellcardj(GEN a4, GEN a6, GEN T, GEN q, long n)
    1552                 :            : {
    1553                 :       6027 :   const ulong p = 3;
    1554                 :            :   ulong t;
    1555                 :       6027 :   GEN q1 = addis(q,1);
    1556                 :       6027 :   GEN na4 = Flx_neg(a4,p), ra4;
    1557         [ +  + ]:       6027 :   if (!Flxq_issquare(na4,T,p))
    1558                 :       2975 :     return q1;
    1559                 :       3052 :   ra4 = Flxq_sqrt(na4,T,p);
    1560                 :       3052 :   t = Flxq_trace(Flxq_div(a6,Flxq_mul(na4,ra4,T,p),T,p),T,p);
    1561         [ +  + ]:       3052 :   if (n%2==1)
    1562                 :            :   {
    1563                 :            :     GEN q3;
    1564         [ +  + ]:        938 :     if (t==0) return q1;
    1565                 :        168 :     q3 = powuu(p,(n+1)>>1);
    1566         [ +  + ]:        168 :     return (t==1)^(n%4==1) ? subii(q1,q3): addii(q1,q3);
    1567                 :            :   }
    1568                 :            :   else
    1569                 :            :   {
    1570                 :       2114 :     GEN q22, q2 = powuu(p,n>>1);
    1571                 :       2114 :     GEN W = Flxq_pow(a4,shifti(q,-2),T,p);
    1572                 :       2114 :     long s = (W[2]==1)^(n%4==2);
    1573 [ -  + ][ #  # ]:       2114 :     if (t!=0) return s ? addii(q1,q2): subii(q1, q2);
    1574                 :       2114 :     q22 = shifti(q2,1);
    1575         [ +  + ]:       6027 :     return s ? subii(q1,q22):  addii(q1, q22);
    1576                 :            :   }
    1577                 :            : }
    1578                 :            : 
    1579                 :            : static GEN
    1580                 :      14063 : Flxq_ellcardj(GEN a4, GEN a6, ulong j, GEN T, GEN q, ulong p, long n)
    1581                 :            : {
    1582                 :      14063 :   GEN q1 = addis(q,1);
    1583         [ +  + ]:      14063 :   if (j==0)
    1584                 :            :   {
    1585                 :            :     ulong w;
    1586                 :            :     GEN W, t, N;
    1587         [ +  + ]:       5614 :     if (umodiu(q,6)!=1) return q1;
    1588                 :       4207 :     N = Fp_ffellcard(gen_0,gen_1,q,n,utoi(p));
    1589                 :       4207 :     t = subii(q1, N);
    1590                 :       4207 :     W = Flxq_pow(a6,diviuexact(shifti(q,-1), 3),T,p);
    1591         [ +  + ]:       4207 :     if (degpol(W)>0) /*p=5 mod 6*/
    1592         [ +  + ]:       1393 :       return Flx_equal1(Flxq_powu(W,3,T,p)) ? addii(q1,shifti(t,-1)):
    1593                 :        462 :                                               subii(q1,shifti(t,-1));
    1594                 :       3276 :     w = W[2];
    1595         [ +  + ]:       3276 :     if (w==1)   return N;
    1596         [ +  + ]:       2583 :     if (w==p-1) return addii(q1,t);
    1597                 :            :     else /*p=1 mod 6*/
    1598                 :            :     {
    1599                 :       1890 :       GEN u = shifti(t,-1), v = sqrtint(diviuexact(subii(q,sqri(u)),3));
    1600                 :       1890 :       GEN a = addii(u,v), b = shifti(v,1);
    1601         [ +  + ]:       1890 :       if (Fl_powu(w,3,p)==1)
    1602                 :            :       {
    1603         [ +  + ]:        945 :         if (Fl_add(umodiu(a,p),Fl_mul(w,umodiu(b,p),p),p)==0)
    1604                 :        427 :           return subii(q1,subii(shifti(b,1),a));
    1605                 :            :         else
    1606                 :        518 :           return addii(q1,addii(a,b));
    1607                 :            :       }
    1608                 :            :       else
    1609                 :            :       {
    1610         [ +  + ]:        945 :         if (Fl_sub(umodiu(a,p),Fl_mul(w,umodiu(b,p),p),p)==0)
    1611                 :        427 :           return subii(q1,subii(a,shifti(b,1)));
    1612                 :            :         else
    1613                 :        518 :           return subii(q1,addii(a,b));
    1614                 :            :       }
    1615                 :            :     }
    1616         [ +  + ]:       8449 :   } else if (j==1728%p)
    1617                 :            :   {
    1618                 :            :     ulong w;
    1619                 :            :     GEN W, N, t;
    1620         [ +  + ]:       5607 :     if (mod4(q)==3) return q1;
    1621                 :       4207 :     W = Flxq_pow(a4,shifti(q,-2),T,p);
    1622         [ +  + ]:       4207 :     if (degpol(W)>0) return q1; /*p=3 mod 4*/
    1623                 :       3591 :     w = W[2];
    1624                 :       3591 :     N = Fp_ffellcard(gen_1,gen_0,q,n,utoi(p));
    1625         [ +  + ]:       3591 :     if(w==1) return N;
    1626                 :       2478 :     t = subii(q1, N);
    1627         [ +  + ]:       2478 :     if(w==p-1) return addii(q1, t);
    1628                 :            :     else /*p=1 mod 4*/
    1629                 :            :     {
    1630                 :       1358 :       GEN u = shifti(t,-1), v = sqrtint(subii(q,sqri(u)));
    1631         [ +  + ]:       1358 :       if (Fl_add(umodiu(u,p),Fl_mul(w,umodiu(v,p),p),p)==0)
    1632                 :        679 :         return subii(q1,shifti(v,1));
    1633                 :            :       else
    1634                 :        679 :         return addii(q1,shifti(v,1));
    1635                 :            :     }
    1636                 :            :   } else
    1637                 :            :   {
    1638                 :       2842 :     ulong g = Fl_div(j, Fl_sub(1728%p, j, p), p);
    1639                 :       2842 :     GEN l = Flxq_div(Flx_triple(a6,p),Flx_double(a4,p),T,p);
    1640                 :       2842 :     GEN N = Fp_ffellcard(utoi(Fl_triple(g,p)),utoi(Fl_double(g,p)),q,n,utoi(p));
    1641         [ +  + ]:       2842 :     if (Flxq_issquare(l,T,p)) return N;
    1642                 :      14063 :     return subii(shifti(q1,1),N);
    1643                 :            :   }
    1644                 :            : }
    1645                 :            : 
    1646                 :            : GEN
    1647                 :      47039 : Flxq_ellcard(GEN a4, GEN a6, GEN T, ulong p)
    1648                 :            : {
    1649                 :      47039 :   pari_sp av = avma;
    1650                 :      47039 :   long n = get_Flx_degree(T);
    1651                 :      47039 :   GEN J, r, q = powuu(p,  n);
    1652         [ +  + ]:      47039 :   if (typ(a4)==t_VEC)
    1653                 :      16009 :     r = F3xq_ellcard(gel(a4,1), a6, T);
    1654         [ +  + ]:      31030 :   else if (p==3)
    1655                 :       6027 :     r = F3xq_ellcardj(a4, a6, T, q, n);
    1656 [ +  + ][ +  + ]:      25003 :   else if (degpol(a4)<=0 && degpol(a6)<=0)
    1657                 :        217 :     r = Fp_ffellcard(utoi(Flx_eval(a4,0,p)),utoi(Flx_eval(a6,0,p)),q,n,utoi(p));
    1658         [ +  + ]:      24786 :   else if (degpol(J=Flxq_ellj(a4,a6,T,p))<=0)
    1659         [ +  + ]:      14063 :     r = Flxq_ellcardj(a4,a6,lgpol(J)?J[2]:0,T,q,p,n);
    1660         [ +  + ]:      10723 :   else if (p <= 7)
    1661                 :      10654 :     r = Flxq_ellcard_Satoh(a4, a6, J, T, p);
    1662         [ -  + ]:         69 :   else if (cmpis(q,100)<0)
    1663                 :          0 :     r = utoi(Flxq_ellcard_naive(a4, a6, T, p));
    1664 [ +  + ][ -  + ]:         69 :   else if (p <= 13 || (7*p <= (ulong)10*n && (BITS_IN_LONG==64 || p <= 31)))
                 [ #  # ]
    1665                 :         28 :     r = Flxq_ellcard_Satoh(a4, a6, J, T, p);
    1666         [ -  + ]:         41 :   else if (p <= (ulong)2*n)
    1667                 :          0 :     r = Flxq_ellcard_Kedlaya(a4, a6, T, p);
    1668         [ +  + ]:         41 :   else if (expi(q)<=62)
    1669                 :         14 :     r = Flxq_ellcard_Shanks(a4, a6, q, T, p);
    1670                 :            :   else
    1671                 :            :   {
    1672                 :         27 :     r = Fq_ellcard_SEA(Flx_to_ZX(a4),Flx_to_ZX(a6),q,Flx_to_ZX(T),utoi(p),0);
    1673         [ -  + ]:         27 :     if (!r) pari_err_PACKAGE("seadata");
    1674                 :            :   }
    1675                 :      47039 :   return gerepileuptoint(av, r);
    1676                 :            : }

Generated by: LCOV version 1.9