Code coverage tests

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

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

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

LCOV - code coverage report
Current view: top level - basemath - hyperell.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.8.0 lcov report (development 19041-b30db16) Lines: 498 519 96.0 %
Date: 2016-06-24 Functions: 43 43 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 216 288 75.0 %

           Branch data     Line data    Source code
       1                 :            : /* Copyright (C) 2014  The PARI group.
       2                 :            : 
       3                 :            : This file is part of the PARI/GP package.
       4                 :            : 
       5                 :            : PARI/GP is free software; you can redistribute it and/or modify it under the
       6                 :            : terms of the GNU General Public License as published by the Free Software
       7                 :            : Foundation. It is distributed in the hope that it will be useful, but WITHOUT
       8                 :            : ANY WARRANTY WHATSOEVER.
       9                 :            : 
      10                 :            : Check the License for details. You should have received a copy of it, along
      11                 :            : with the package; see the file 'COPYING'. If not, write to the Free Software
      12                 :            : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      13                 :            : 
      14                 :            : /********************************************************************/
      15                 :            : /**                                                                **/
      16                 :            : /**                     HYPERELLIPTIC CURVES                       **/
      17                 :            : /**                                                                **/
      18                 :            : /********************************************************************/
      19                 :            : #include "pari.h"
      20                 :            : #include "paripriv.h"
      21                 :            : 
      22                 :            : /* Implementation of Kedlaya Algorithm for counting point on hyperelliptic
      23                 :            : curves by Bill Allombert based on a GP script by Bernadette Perrin-Riou.
      24                 :            : 
      25                 :            : References:
      26                 :            : Pierrick Gaudry and Nicolas G\"urel
      27                 :            : Counting Points in Medium Characteristic Using Kedlaya's Algorithm
      28                 :            : Experiment. Math.  Volume 12, Number 4 (2003), 395-402.
      29                 :            :    http://projecteuclid.org/euclid.em/1087568016
      30                 :            : 
      31                 :            : Harrison, M. An extension of Kedlaya's algorithm for hyperelliptic
      32                 :            :   curves. Journal of Symbolic Computation, 47 (1) (2012), 89-101.
      33                 :            :   http://arxiv.org/pdf/1006.4206v3.pdf
      34                 :            : */
      35                 :            : 
      36                 :            : /* We use the basis of differentials (x^i*dx/y^k) (i=1 to 2*g-1),
      37                 :            :    with k either 1 or 3, depending on p and d, see Harrison paper */
      38                 :            : 
      39                 :            : static long
      40                 :       1120 : get_basis(long p, long d)
      41                 :            : {
      42         [ +  + ]:       1120 :   if (odd(d))
      43         [ -  + ]:        560 :     return p < d-1 ? 3 : 1;
      44                 :            :   else
      45         [ +  + ]:       1120 :     return 2*p <= d-2 ? 3 : 1;
      46                 :            : }
      47                 :            : 
      48                 :            : static GEN
      49                 :      11137 : FpXXQ_red(GEN S, GEN T, GEN p)
      50                 :            : {
      51                 :      11137 :   pari_sp av = avma;
      52                 :      11137 :   long i, dS = degpol(S);
      53                 :            :   GEN A, C;
      54         [ -  + ]:      11137 :   if (signe(S)==0) return pol_0(varn(T));
      55                 :      11137 :   A = cgetg(dS+3, t_POL);
      56                 :      11137 :   C = pol_0(varn(T));
      57         [ +  + ]:     989394 :   for(i=dS; i>0; i--)
      58                 :            :   {
      59                 :     978257 :     GEN Si = FpX_add(C, gel(S,i+2), p);
      60                 :     978257 :     GEN R, Q = FpX_divrem(Si, T, p, &R);
      61                 :     978257 :     gel(A,i+2) = R;
      62                 :     978257 :     C = Q;
      63                 :            :   }
      64                 :      11137 :   gel(A,2) = FpX_add(C, gel(S,2), p);
      65                 :      11137 :   A[1] = S[1];
      66                 :      11137 :   return gerepilecopy(av, FpXX_renormalize(A,dS+3));
      67                 :            : }
      68                 :            : 
      69                 :            : static GEN
      70                 :       2065 : FpXXQ_sqr(GEN x, GEN T, GEN p)
      71                 :            : {
      72                 :       2065 :   pari_sp av = avma;
      73                 :       2065 :   long n = degpol(T);
      74                 :       2065 :   GEN z = FpX_red(ZXX_sqr_Kronecker(x, n), p);
      75                 :       2065 :   z = Kronecker_to_ZXX(z, n, varn(T));
      76                 :       2065 :   return gerepileupto(av, FpXXQ_red(z, T, p));
      77                 :            : }
      78                 :            : 
      79                 :            : static GEN
      80                 :       9072 : FpXXQ_mul(GEN x, GEN y, GEN T, GEN p)
      81                 :            : {
      82                 :       9072 :   pari_sp av = avma;
      83                 :       9072 :   long n = degpol(T);
      84                 :       9072 :   GEN z = FpX_red(ZXX_mul_Kronecker(x, y, n), p);
      85                 :       9072 :   z = Kronecker_to_ZXX(z, n, varn(T));
      86                 :       9072 :   return gerepileupto(av, FpXXQ_red(z, T, p));
      87                 :            : }
      88                 :            : 
      89                 :            : static GEN
      90                 :        693 : ZpXXQ_invsqrt(GEN S, GEN T, ulong p, long e)
      91                 :            : {
      92                 :        693 :   pari_sp av = avma, av2;
      93                 :            :   ulong mask;
      94                 :        693 :   long v = varn(S), n=1;
      95                 :        693 :   GEN a = pol_1(v);
      96         [ -  + ]:        693 :   if (e <= 1) return gerepilecopy(av, a);
      97                 :        693 :   mask = quadratic_prec_mask(e);
      98                 :        693 :   av2 = avma;
      99         [ +  + ]:       2751 :   for (;mask>1;)
     100                 :            :   {
     101                 :            :     GEN q, q2, q22, f, fq, afq;
     102                 :       2058 :     long n2 = n;
     103         [ +  + ]:       2058 :     n<<=1; if (mask & 1) n--;
     104                 :       2058 :     mask >>= 1;
     105                 :       2058 :     q = powuu(p,n); q2 = powuu(p,n2);
     106                 :       2058 :     f = RgX_sub(FpXXQ_mul(S, FpXXQ_sqr(a, T, q), T, q), pol_1(v));
     107                 :       2058 :     fq = ZXX_Z_divexact(f, q2);
     108                 :       2058 :     q22 = shifti(addis(q2,1),-1);
     109                 :       2058 :     afq = FpXX_Fp_mul(FpXXQ_mul(a, fq, T, q2), q22, q2);
     110                 :       2058 :     a = RgX_sub(a, ZXX_Z_mul(afq, q2));
     111         [ -  + ]:       2058 :     if (gc_needed(av2,1))
     112                 :            :     {
     113         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXXQ_invsqrt, e = %ld", n);
     114                 :          0 :       a = gerepileupto(av2, a);
     115                 :            :     }
     116                 :            :   }
     117                 :        693 :   return gerepileupto(av, a);
     118                 :            : }
     119                 :            : 
     120                 :            : static GEN
     121         [ +  + ]:      15246 : to_ZX(GEN a, long v) { return typ(a)==t_INT? scalarpol(a,v): a; }
     122                 :            : 
     123                 :            : static void
     124                 :         14 : is_sing(GEN H, ulong p)
     125                 :            : {
     126                 :         14 :   pari_err_DOMAIN("hyperellpadicfrobenius","H","is singular at",utoi(p),H);
     127                 :          0 : }
     128                 :            : 
     129                 :            : static void
     130                 :        693 : get_UV(GEN *U, GEN *V, GEN T, ulong p, long e)
     131                 :            : {
     132                 :        693 :   GEN q = powuu(p,e), d;
     133                 :        693 :   GEN dT = FpX_deriv(T, q);
     134                 :        693 :   GEN R = polresultantext(T, dT);
     135                 :        693 :   long v = varn(T);
     136         [ -  + ]:        693 :   if (dvdiu(gel(R,3),p)) is_sing(T, p);
     137                 :        693 :   d = Fp_inv(gel(R,3), q);
     138                 :        693 :   *U = FpX_Fp_mul(FpX_red(to_ZX(gel(R,1),v),q),d,q);
     139                 :        693 :   *V = FpX_Fp_mul(FpX_red(to_ZX(gel(R,2),v),q),d,q);
     140                 :        693 : }
     141                 :            : 
     142                 :            : static GEN
     143                 :      68936 : frac_to_Fp(GEN a, GEN b, GEN p)
     144                 :            : {
     145                 :      68936 :   GEN d = gcdii(a, b);
     146                 :      68936 :   return Fp_div(diviiexact(a, d), diviiexact(b, d), p);
     147                 :            : }
     148                 :            : 
     149                 :            : static GEN
     150                 :       4949 : ZpXXQ_frob(GEN S, GEN U, GEN V, long k, GEN T, ulong p, long e)
     151                 :            : {
     152                 :       4949 :   pari_sp av = avma, av2;
     153                 :       4949 :   long i, pr = degpol(S), dT = degpol(T);
     154                 :       4949 :   GEN q = powuu(p,e);
     155                 :       4949 :   GEN Tp = FpX_deriv(T, q), Tp1 = RgX_shift_shallow(Tp, 1);
     156                 :       4949 :   GEN M = gel(S,pr+2), R;
     157                 :       4949 :   av2 = avma;
     158         [ +  + ]:     596988 :   for(i = pr-1; i>=k; i--)
     159                 :            :   {
     160                 :            :     GEN A, B, H, Bc;
     161                 :            :     ulong v, r;
     162                 :     592039 :     H = FpX_divrem(FpX_mul(V,M,q), T, q, &B);
     163                 :     592039 :     A = FpX_add(FpX_mul(U,M,q), FpX_mul(H, Tp, q),q);
     164                 :     592039 :     v = u_lvalrem(2*i+1,p,&r);
     165                 :     592039 :     Bc = FpX_deriv(B, q);
     166                 :     592039 :     Bc = FpX_Fp_mul(ZX_Z_divexact(Bc,powuu(p,v)),Fp_div(gen_2, utoi(r), q), q);
     167                 :     592039 :     M = FpX_add(gel(S,i+2), FpX_add(A, Bc, q), q);
     168         [ -  + ]:     592039 :     if (gc_needed(av2,1))
     169                 :            :     {
     170         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXXQ_frob, step 1, i = %ld", i);
     171                 :          0 :       M = gerepileupto(av2, M);
     172                 :            :     }
     173                 :            :   }
     174         [ +  + ]:       4949 :   if (degpol(M)<dT-1)
     175                 :       2625 :     return gerepileupto(av, M);
     176                 :       2324 :   R = RgX_shift_shallow(M,dT-degpol(M)-2);
     177                 :       2324 :   av2 = avma;
     178         [ +  + ]:     120302 :   for(i = degpol(M)-dT+2; i>=1; i--)
     179                 :            :   {
     180                 :            :     GEN B, c;
     181                 :     117978 :     R = RgX_shift_shallow(R, 1);
     182                 :     117978 :     gel(R,2) = gel(M, i+1);
     183         [ +  + ]:     117978 :     if (degpol(R) < dT) continue;
     184                 :      67431 :     B = FpX_add(FpX_mulu(T, 2*i, q), Tp1, q);
     185                 :      67431 :     c = frac_to_Fp(leading_coeff(R), leading_coeff(B), q);
     186                 :      67431 :     R = FpX_sub(R, FpX_Fp_mul(B, c, q), q);
     187         [ -  + ]:      67431 :     if (gc_needed(av2,1))
     188                 :            :     {
     189         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXXQ_frob, step 2, i = %ld", i);
     190                 :          0 :       R = gerepileupto(av2, R);
     191                 :            :     }
     192                 :            :   }
     193         [ +  + ]:       2324 :   if (degpol(R)==dT-1)
     194                 :            :   {
     195                 :       1505 :     GEN c = frac_to_Fp(leading_coeff(R), leading_coeff(Tp), q);
     196                 :       1505 :     R = FpX_sub(R, FpX_Fp_mul(Tp, c, q), q);
     197                 :       1505 :     return gerepileupto(av, R);
     198                 :            :   } else
     199                 :       4949 :     return gerepilecopy(av, R);
     200                 :            : }
     201                 :            : 
     202                 :            : static GEN
     203                 :       6230 : revdigits(GEN v)
     204                 :            : {
     205                 :       6230 :   long i, n = lg(v)-1;
     206                 :       6230 :   GEN w = cgetg(n+2, t_POL);
     207                 :       6230 :   w[1] = evalsigne(1)|evalvarn(0);
     208         [ +  + ]:      92071 :   for (i=0; i<n; i++)
     209                 :      85841 :     gel(w,i+2) = gel(v,n-i);
     210                 :       6230 :   return FpXX_renormalize(w, n+2);
     211                 :            : }
     212                 :            : 
     213                 :            : static GEN
     214                 :       4949 : diff_red(GEN s, GEN A, long m, GEN T, GEN p)
     215                 :            : {
     216                 :            :   long v, n;
     217                 :            :   GEN Q, sQ, qS;
     218                 :            :   pari_timer ti;
     219         [ -  + ]:       4949 :   if (DEBUGLEVEL>1) timer_start(&ti);
     220                 :       4949 :   Q = revdigits(FpX_digits(A,T,p));
     221                 :       4949 :   n = degpol(Q);
     222         [ -  + ]:       4949 :   if (DEBUGLEVEL>1) timer_printf(&ti,"reddigits");
     223                 :       4949 :   sQ = FpXXQ_mul(s,Q,T,p);
     224         [ -  + ]:       4949 :   if (DEBUGLEVEL>1) timer_printf(&ti,"redmul");
     225                 :       4949 :   qS = RgX_shift_shallow(sQ,m-n);
     226                 :       4949 :   v = ZX_val(sQ);
     227         [ +  + ]:       4949 :   if (n > m + v)
     228                 :            :   {
     229                 :       2296 :     long i, l = n-m-v;
     230                 :       2296 :     GEN rS = cgetg(l+1,t_VEC);
     231         [ +  + ]:      14833 :     for (i = l-1; i >=0 ; i--)
     232                 :      12537 :       gel(rS,i+1) = gel(sQ, 1+v+l-i);
     233                 :       2296 :     rS = FpX_fromdigits(rS,T,p);
     234                 :       2296 :     gel(qS,2) = FpX_add(FpX_mul(rS, T, p), gel(qS, 2), p);
     235         [ -  + ]:       2296 :     if (DEBUGLEVEL>1) timer_printf(&ti,"redadd");
     236                 :            :   }
     237                 :       4949 :   return qS;
     238                 :            : }
     239                 :            : 
     240                 :            : static GEN
     241                 :       4949 : ZC_to_padic(GEN C, GEN q)
     242                 :            : {
     243                 :       4949 :   long i, l = lg(C);
     244                 :       4949 :   GEN V = cgetg(l,t_COL);
     245         [ +  + ]:      49770 :   for(i = 1; i < l; i++)
     246                 :      44821 :     gel(V, i) = gadd(gel(C, i), q);
     247                 :       4949 :   return V;
     248                 :            : }
     249                 :            : 
     250                 :            : static GEN
     251                 :        693 : ZM_to_padic(GEN M, GEN q)
     252                 :            : {
     253                 :        693 :   long i, l = lg(M);
     254                 :        693 :   GEN V = cgetg(l,t_MAT);
     255         [ +  + ]:       5642 :   for(i = 1; i < l; i++)
     256                 :       4949 :     gel(V, i) = ZC_to_padic(gel(M, i), q);
     257                 :        693 :   return V;
     258                 :            : }
     259                 :            : 
     260                 :            : static GEN
     261                 :       1631 : ZX_to_padic(GEN P, GEN q)
     262                 :            : {
     263                 :       1631 :   long i, l = lg(P);
     264                 :       1631 :   GEN Q = cgetg(l, t_POL);
     265                 :       1631 :   Q[1] = P[1];
     266         [ +  + ]:       5656 :   for (i=2; i<l ;i++)
     267                 :       4025 :     gel(Q,i) = gadd(gel(P,i), q);
     268                 :       1631 :   return normalizepol(Q);
     269                 :            : }
     270                 :            : 
     271                 :            : static GEN
     272                 :        441 : ZXC_to_padic(GEN C, GEN q)
     273                 :            : {
     274                 :        441 :   long i, l = lg(C);
     275                 :        441 :   GEN V = cgetg(l,t_COL);
     276         [ +  + ]:       2072 :   for(i = 1; i < l; i++)
     277                 :       1631 :     gel(V, i) = ZX_to_padic(gel(C, i), q);
     278                 :        441 :   return V;
     279                 :            : }
     280                 :            : 
     281                 :            : static GEN
     282                 :        140 : ZXM_to_padic(GEN M, GEN q)
     283                 :            : {
     284                 :        140 :   long i, l = lg(M);
     285                 :        140 :   GEN V = cgetg(l,t_MAT);
     286         [ +  + ]:        581 :   for(i = 1; i < l; i++)
     287                 :        441 :     gel(V, i) = ZXC_to_padic(gel(M, i), q);
     288                 :        140 :   return V;
     289                 :            : }
     290                 :            : 
     291                 :            : static GEN
     292                 :        693 : ZlX_hyperellpadicfrobenius(GEN H, ulong p, long n)
     293                 :            : {
     294                 :        693 :   pari_sp av = avma;
     295                 :            :   long k, N, i, d;
     296                 :            :   GEN F, s, Q, pN1, U, V;
     297                 :            :   pari_timer ti;
     298         [ -  + ]:        693 :   if (typ(H) != t_POL) pari_err_TYPE("hyperellpadicfrobenius",H);
     299         [ -  + ]:        693 :   if (p == 2) is_sing(H, 2);
     300                 :        693 :   d = degpol(H);
     301         [ -  + ]:        693 :   if (d <= 0)
     302                 :          0 :     pari_err_CONSTPOL("hyperellpadicfrobenius");
     303         [ -  + ]:        693 :   if (n < 1)
     304                 :          0 :     pari_err_DOMAIN("hyperellpadicfrobenius","n","<", gen_1, utoi(n));
     305                 :        693 :   k = get_basis(p, d);
     306                 :        693 :   N = n + logint(stoi(2*n), stoi(p), NULL);
     307                 :        693 :   pN1 = powuu(p,N+1);
     308                 :        693 :   Q = RgX_to_FpX(H, pN1);
     309         [ -  + ]:        693 :   if (dvdiu(leading_coeff(Q),p)) is_sing(H, p);
     310                 :        693 :   setvarn(Q,1);
     311         [ -  + ]:        693 :   if (DEBUGLEVEL>1) timer_start(&ti);
     312                 :        693 :   s = revdigits(FpX_digits(RgX_inflate(Q, p), Q, pN1));
     313         [ -  + ]:        693 :   if (DEBUGLEVEL>1) timer_printf(&ti,"s1");
     314                 :        693 :   s = ZpXXQ_invsqrt(s, Q, p, N);
     315         [ +  + ]:        693 :   if (k==3)
     316                 :          7 :     s = FpXXQ_mul(s, FpXXQ_sqr(s, Q, pN1), Q, pN1);
     317         [ -  + ]:        693 :   if (DEBUGLEVEL>1) timer_printf(&ti,"invsqrt");
     318                 :        693 :   get_UV(&U, &V, Q, p, N+1);
     319                 :        693 :   F = cgetg(d, t_MAT);
     320         [ +  + ]:       5642 :   for (i = 1; i < d; i++)
     321                 :            :   {
     322                 :       4949 :     pari_sp av2 = avma;
     323                 :            :     GEN M, D;
     324                 :       4949 :     D = diff_red(s, monomial(utoi(p),p*i-1,1),(k*p-1)>>1, Q, pN1);
     325         [ -  + ]:       4949 :     if (DEBUGLEVEL>1) timer_printf(&ti,"red");
     326                 :       4949 :     M = ZpXXQ_frob(D, U, V, (k-1)>>1, Q, p, N + 1);
     327         [ -  + ]:       4949 :     if (DEBUGLEVEL>1) timer_printf(&ti,"frob");
     328                 :       4949 :     gel(F, i) = gerepilecopy(av2, RgX_to_RgC(M, d-1));
     329                 :            :   }
     330                 :        693 :   return gerepileupto(av, F);
     331                 :            : }
     332                 :            : 
     333                 :            : GEN
     334                 :        693 : hyperellpadicfrobenius(GEN H, ulong p, long n)
     335                 :            : {
     336                 :        693 :   pari_sp av = avma;
     337                 :        693 :   GEN M = ZlX_hyperellpadicfrobenius(H, p, n);
     338                 :        693 :   GEN q = zeropadic(utoi(p),n);
     339                 :        693 :   return gerepileupto(av, ZM_to_padic(M, q));
     340                 :            : }
     341                 :            : 
     342                 :            : INLINE GEN
     343                 :       2072 : FpXXX_renormalize(GEN x, long lx)  { return ZXX_renormalize(x,lx); }
     344                 :            : 
     345                 :            : static GEN
     346                 :       1680 : ZpXQXXQ_red(GEN F, GEN S, GEN T, GEN q, GEN p, long e)
     347                 :            : {
     348                 :       1680 :   pari_sp av = avma;
     349                 :       1680 :   long i, dF = degpol(F);
     350                 :            :   GEN A, C;
     351         [ +  + ]:       1680 :   if (signe(F)==0) return pol_0(varn(S));
     352                 :       1659 :   A = cgetg(dF+3, t_POL);
     353                 :       1659 :   C = pol_0(varn(S));
     354         [ +  + ]:      93331 :   for(i=dF; i>0; i--)
     355                 :            :   {
     356                 :      91672 :     GEN Fi = FpXX_add(C, gel(F,i+2), q);
     357                 :      91672 :     GEN R, Q = ZpXQX_divrem(Fi, S, T, q, p, e, &R);
     358                 :      91672 :     gel(A,i+2) = R;
     359                 :      91672 :     C = Q;
     360                 :            :   }
     361                 :       1659 :   gel(A,2) = FpXX_add(C, gel(F,2), q);
     362                 :       1659 :   A[1] = F[1];
     363                 :       1680 :   return gerepilecopy(av, FpXXX_renormalize(A,dF+3));
     364                 :            : }
     365                 :            : 
     366                 :            : static GEN
     367                 :        413 : ZpXQXXQ_sqr(GEN x, GEN S, GEN T, GEN q, GEN p, long e)
     368                 :            : {
     369                 :        413 :   pari_sp av = avma;
     370                 :            :   GEN z, kx;
     371                 :        413 :   long n = degpol(S);
     372                 :        413 :   kx = ZXX_to_Kronecker(x, n);
     373                 :        413 :   z = Kronecker_to_ZXX(FpXQX_sqr(kx, T, q), n, varn(S));
     374                 :        413 :   return gerepileupto(av, ZpXQXXQ_red(z, S, T, q, p, e));
     375                 :            : }
     376                 :            : 
     377                 :            : static GEN
     378                 :       1267 : ZpXQXXQ_mul(GEN x, GEN y, GEN S, GEN T, GEN q, GEN p, long e)
     379                 :            : {
     380                 :       1267 :   pari_sp av = avma;
     381                 :            :   GEN z, kx, ky;
     382                 :       1267 :   long n = degpol(S);
     383                 :       1267 :   kx = ZXX_to_Kronecker(x, n);
     384                 :       1267 :   ky = ZXX_to_Kronecker(y, n);
     385                 :       1267 :   z = Kronecker_to_ZXX(FpXQX_mul(ky, kx, T, q), n, varn(S));
     386                 :       1267 :   return gerepileupto(av, ZpXQXXQ_red(z, S, T, q, p, e));
     387                 :            : }
     388                 :            : 
     389                 :            : static GEN
     390                 :        413 : FpXXX_red(GEN z, GEN p)
     391                 :            : {
     392                 :            :   GEN res;
     393                 :        413 :   long i, l = lg(z);
     394                 :        413 :   res = cgetg(l,t_POL); res[1] = z[1];
     395         [ +  + ]:      16807 :   for (i=2; i<l; i++)
     396                 :            :   {
     397                 :      16394 :     GEN zi = gel(z,i);
     398         [ -  + ]:      16394 :     if (typ(zi)==t_INT)
     399                 :          0 :       gel(res,i) = modii(zi,p);
     400                 :            :     else
     401                 :      16394 :      gel(res,i) = FpXX_red(zi,p);
     402                 :            :   }
     403                 :        413 :   return FpXXX_renormalize(res,lg(res));
     404                 :            : }
     405                 :            : 
     406                 :            : static GEN
     407                 :        413 : FpXXX_Fp_mul(GEN z, GEN a, GEN p)
     408                 :            : {
     409                 :        413 :   return FpXXX_red(RgX_Rg_mul(z, a), p);
     410                 :            : }
     411                 :            : 
     412                 :            : static GEN
     413                 :        147 : ZpXQXXQ_invsqrt(GEN F, GEN S, GEN T, ulong p, long e)
     414                 :            : {
     415                 :        147 :   pari_sp av = avma, av2, av3;
     416                 :            :   ulong mask;
     417                 :        147 :   long v = varn(F), n=1;
     418                 :            :   pari_timer ti;
     419                 :        147 :   GEN a = pol_1(v), pp = utoi(p);
     420         [ -  + ]:        147 :   if (DEBUGLEVEL>1) timer_start(&ti);
     421         [ -  + ]:        147 :   if (e <= 1) return gerepilecopy(av, a);
     422                 :        147 :   mask = quadratic_prec_mask(e);
     423                 :        147 :   av2 = avma;
     424         [ +  + ]:        560 :   for (;mask>1;)
     425                 :            :   {
     426                 :            :     GEN q, q2, q22, f, fq, afq;
     427                 :        413 :     long n2 = n;
     428         [ +  + ]:        413 :     n<<=1; if (mask & 1) n--;
     429                 :        413 :     mask >>= 1;
     430                 :        413 :     q = powuu(p,n); q2 = powuu(p,n2);
     431                 :        413 :     av3 = avma;
     432                 :        413 :     f = RgX_sub(ZpXQXXQ_mul(F, ZpXQXXQ_sqr(a, S, T, q, pp, n), S, T, q, pp, n), pol_1(v));
     433                 :        413 :     fq = gerepileupto(av3, RgX_Rg_divexact(f, q2));
     434                 :        413 :     q22 = shifti(addis(q2,1),-1);
     435                 :        413 :     afq = FpXXX_Fp_mul(ZpXQXXQ_mul(a, fq, S, T, q2, pp, n2), q22, q2);
     436                 :        413 :     a = RgX_sub(a, RgX_Rg_mul(afq, q2));
     437         [ -  + ]:        413 :     if (gc_needed(av2,1))
     438                 :            :     {
     439         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXQXXQ_invsqrt, e = %ld", n);
     440                 :          0 :       a = gerepileupto(av2, a);
     441                 :            :     }
     442                 :            :   }
     443                 :        147 :   return gerepileupto(av, a);
     444                 :            : }
     445                 :            : 
     446                 :            : static GEN
     447                 :       6573 : frac_to_Fq(GEN a, GEN b, GEN T, GEN q, GEN p, long e)
     448                 :            : {
     449                 :       6573 :   GEN d = gcdii(ZX_content(a), ZX_content(b));
     450                 :       6573 :   return ZpXQ_div(ZX_Z_divexact(a, d), ZX_Z_divexact(b, d), T, q, p, e);
     451                 :            : }
     452                 :            : 
     453                 :            : static GEN
     454                 :        441 : ZpXQXXQ_frob(GEN F, GEN U, GEN V, long k, GEN S, GEN T, ulong p, long e)
     455                 :            : {
     456                 :        441 :   pari_sp av = avma, av2;
     457                 :        441 :   long i, pr = degpol(F), dS = degpol(S), v = varn(T);
     458                 :        441 :   GEN q = powuu(p,e), pp = utoi(p);
     459                 :        441 :   GEN Sp = RgX_deriv(S), Sp1 = RgX_shift_shallow(Sp, 1);
     460                 :        441 :   GEN M = gel(F,pr+2), R;
     461                 :        441 :   av2 = avma;
     462         [ +  + ]:      51191 :   for(i = pr-1; i>=k; i--)
     463                 :            :   {
     464                 :            :     GEN A, B, H, Bc;
     465                 :            :     ulong v, r;
     466                 :      50750 :     H = ZpXQX_divrem(FpXQX_mul(V, M, T, q), S, T, q, utoi(p), e, &B);
     467                 :      50750 :     A = FpXX_add(FpXQX_mul(U, M, T, q), FpXQX_mul(H, Sp, T, q),q);
     468                 :      50750 :     v = u_lvalrem(2*i+1,p,&r);
     469                 :      50750 :     Bc = RgX_deriv(B);
     470                 :      50750 :     Bc = FpXX_Fp_mul(ZXX_Z_divexact(Bc,powuu(p,v)), Fp_div(gen_2, utoi(r), q), q);
     471                 :      50750 :     M = FpXX_add(gel(F,i+2), FpXX_add(A, Bc, q), q);
     472         [ -  + ]:      50750 :     if (gc_needed(av2,1))
     473                 :            :     {
     474         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXQXXQ_frob, step 1, i = %ld", i);
     475                 :          0 :       M = gerepileupto(av2, M);
     476                 :            :     }
     477                 :            :   }
     478         [ +  + ]:        441 :   if (degpol(M)<dS-1)
     479                 :        238 :     return gerepileupto(av, M);
     480                 :        203 :   R = RgX_shift_shallow(M,dS-degpol(M)-2);
     481                 :        203 :   av2 = avma;
     482         [ +  + ]:       7175 :   for(i = degpol(M)-dS+2; i>=1; i--)
     483                 :            :   {
     484                 :            :     GEN B, c;
     485                 :       6972 :     R = RgX_shift_shallow(R, 1);
     486                 :       6972 :     gel(R,2) = gel(M, i+1);
     487         [ +  + ]:       6972 :     if (degpol(R) < dS) continue;
     488                 :       6412 :     B = FpXX_add(FpXX_mulu(S, 2*i, q), Sp1, q);
     489                 :       6412 :     c = frac_to_Fq(to_ZX(leading_coeff(R),v), to_ZX(leading_coeff(B),v), T, q, pp, e);
     490                 :       6412 :     R = FpXX_sub(R, FpXQX_FpXQ_mul(B, c, T, q), q);
     491         [ -  + ]:       6412 :     if (gc_needed(av2,1))
     492                 :            :     {
     493         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXXQ_frob, step 2, i = %ld", i);
     494                 :          0 :       R = gerepileupto(av2, R);
     495                 :            :     }
     496                 :            :   }
     497         [ +  + ]:        203 :   if (degpol(R)==dS-1)
     498                 :            :   {
     499                 :        161 :     GEN c = frac_to_Fq(to_ZX(leading_coeff(R),v), to_ZX(leading_coeff(Sp),v), T, q, pp, e);
     500                 :        161 :     R = FpXX_sub(R, FpXQX_FpXQ_mul(Sp, c, T, q), q);
     501                 :        161 :     return gerepileupto(av, R);
     502                 :            :   } else
     503                 :        441 :     return gerepilecopy(av, R);
     504                 :            : }
     505                 :            : 
     506                 :            : 
     507                 :            : static GEN
     508                 :        441 : Fq_diff_red(GEN s, GEN A, long m, GEN S, GEN T, GEN q, GEN p, long e)
     509                 :            : {
     510                 :            :   long v, n;
     511                 :            :   GEN Q, sQ, qS;
     512                 :            :   pari_timer ti;
     513         [ -  + ]:        441 :   if (DEBUGLEVEL>1) timer_start(&ti);
     514                 :        441 :   Q = revdigits(ZpXQX_digits(A, S, T, q, p, e));
     515                 :        441 :   n = degpol(Q);
     516         [ -  + ]:        441 :   if (DEBUGLEVEL>1) timer_printf(&ti,"reddigits");
     517                 :        441 :   sQ = ZpXQXXQ_mul(s, Q, S, T, q, p, e);
     518         [ -  + ]:        441 :   if (DEBUGLEVEL>1) timer_printf(&ti,"redmul");
     519                 :        441 :   qS = RgX_shift_shallow(sQ,m-n);
     520                 :        441 :   v = ZX_val(sQ);
     521         [ +  + ]:        441 :   if (n > m + v)
     522                 :            :   {
     523                 :        189 :     long i, l = n-m-v;
     524                 :        189 :     GEN rS = cgetg(l+1,t_VEC);
     525         [ +  + ]:       1547 :     for (i = l-1; i >=0 ; i--)
     526                 :       1358 :       gel(rS,i+1) = gel(sQ, 1+v+l-i);
     527                 :        189 :     rS = FpXQX_fromdigits(rS,S,T,q);
     528                 :        189 :     gel(qS,2) = FpXX_add(FpXQX_mul(rS, S, T, q), gel(qS, 2), q);
     529         [ -  + ]:        189 :     if (DEBUGLEVEL>1) timer_printf(&ti,"redadd");
     530                 :            :   }
     531                 :        441 :   return qS;
     532                 :            : }
     533                 :            : 
     534                 :            : static void
     535                 :        147 : Fq_get_UV(GEN *U, GEN *V, GEN S, GEN T, ulong p, long e)
     536                 :            : {
     537                 :        147 :   GEN q = powuu(p, e), d;
     538                 :        147 :   GEN dS = RgX_deriv(S);
     539                 :        147 :   GEN R  = polresultantext(S, dS), C;
     540                 :        147 :   long v = varn(S);
     541         [ +  + ]:        147 :   if (signe(FpX_red(to_ZX(gel(R,3),v),utoi(p)))==0) is_sing(S, p);
     542                 :        140 :   C = FpXQ_red(to_ZX(gel(R, 3),v), T, q);
     543                 :        140 :   d = ZpXQ_inv(C, T, utoi(p), e);
     544                 :        140 :   *U = FpXQX_FpXQ_mul(FpXQX_red(to_ZX(gel(R,1),v),T,q),d,T,q);
     545                 :        140 :   *V = FpXQX_FpXQ_mul(FpXQX_red(to_ZX(gel(R,2),v),T,q),d,T,q);
     546                 :        140 : }
     547                 :            : 
     548                 :            : static GEN
     549                 :        441 : ZXX_to_FpXC(GEN x, long N, GEN p, long v)
     550                 :            : {
     551                 :            :   long i, l;
     552                 :            :   GEN z;
     553                 :        441 :   l = lg(x)-1; x++;
     554         [ -  + ]:        441 :   if (l > N+1) l = N+1; /* truncate higher degree terms */
     555                 :        441 :   z = cgetg(N+1,t_COL);
     556         [ +  + ]:       2030 :   for (i=1; i<l ; i++)
     557                 :            :   {
     558                 :       1589 :     GEN xi = gel(x, i);
     559         [ -  + ]:       1589 :     gel(z,i) = typ(xi)==t_INT? scalarpol(Fp_red(xi, p), v): FpX_red(xi, p);
     560                 :            :   }
     561         [ +  + ]:        483 :   for (   ; i<=N ; i++)
     562                 :         42 :     gel(z,i) = pol_0(v);
     563                 :        441 :   return z;
     564                 :            : }
     565                 :            : 
     566                 :            : GEN
     567                 :        147 : ZlXQX_hyperellpadicfrobenius(GEN H, GEN T, ulong p, long n)
     568                 :            : {
     569                 :        147 :   pari_sp av = avma;
     570                 :            :   long k, N, i, d, N1;
     571                 :            :   GEN xp, F, s, q, Q, pN1, U, V, pp;
     572                 :            :   pari_timer ti;
     573         [ -  + ]:        147 :   if (typ(H) != t_POL) pari_err_TYPE("hyperellpadicfrobenius",H);
     574         [ -  + ]:        147 :   if (p == 2) is_sing(H, 2);
     575                 :        147 :   d = degpol(H);
     576         [ -  + ]:        147 :   if (d <= 0)
     577                 :          0 :     pari_err_CONSTPOL("hyperellpadicfrobenius");
     578         [ -  + ]:        147 :   if (n < 1)
     579                 :          0 :     pari_err_DOMAIN("hyperellpadicfrobenius","n","<", gen_1, utoi(n));
     580                 :        147 :   k = get_basis(p, d); pp = utoi(p);
     581                 :        147 :   N = n + logint(stoi(2*n), pp, NULL);
     582                 :        147 :   q = powuu(p,n); N1 = N+1;
     583                 :        147 :   pN1 = powuu(p,N1); T = FpX_get_red(T, pN1);
     584                 :        147 :   Q = RgX_to_FqX(H, T, pN1);
     585         [ -  + ]:        147 :   if (signe(FpX_red(to_ZX(leading_coeff(Q),varn(Q)),pp))==0) is_sing(H, p);
     586         [ -  + ]:        147 :   if (DEBUGLEVEL>1) timer_start(&ti);
     587                 :        147 :   xp = ZpX_Frobenius(T, pp, N1);
     588                 :        147 :   s = RgX_inflate(FpXY_FpXQ_evalx(Q, xp, T, pN1), p);
     589                 :        147 :   s = revdigits(ZpXQX_digits(s, Q, T, pN1, pp, N1));
     590         [ -  + ]:        147 :   if (DEBUGLEVEL>1) timer_printf(&ti,"s1");
     591                 :        147 :   s = ZpXQXXQ_invsqrt(s, Q, T, p, N);
     592         [ -  + ]:        147 :   if (k==3)
     593                 :          0 :     s = ZpXQXXQ_mul(s, ZpXQXXQ_sqr(s, Q, T, pN1, pp, N1), Q, T, pN1, pp, N1);
     594         [ -  + ]:        147 :   if (DEBUGLEVEL>1) timer_printf(&ti,"invsqrt");
     595                 :        147 :   Fq_get_UV(&U, &V, Q, T, p, N+1);
     596         [ -  + ]:        140 :   if (DEBUGLEVEL>1) timer_printf(&ti,"get_UV");
     597                 :        140 :   F = cgetg(d, t_MAT);
     598         [ +  + ]:        581 :   for (i = 1; i < d; i++)
     599                 :            :   {
     600                 :        441 :     pari_sp av2 = avma;
     601                 :            :     GEN M, D;
     602                 :        441 :     D = Fq_diff_red(s, monomial(pp,p*i-1,1),(k*p-1)>>1, Q, T, pN1, pp, N1);
     603         [ -  + ]:        441 :     if (DEBUGLEVEL>1) timer_printf(&ti,"red");
     604                 :        441 :     M = ZpXQXXQ_frob(D, U, V, (k - 1)>>1, Q, T, p, N1);
     605         [ -  + ]:        441 :     if (DEBUGLEVEL>1) timer_printf(&ti,"frob");
     606                 :        441 :     gel(F, i) = gerepileupto(av2, ZXX_to_FpXC(M, d-1, q, varn(T)));
     607                 :            :   }
     608                 :        140 :   return gerepileupto(av, F);
     609                 :            : }
     610                 :            : 
     611                 :            : GEN
     612                 :        147 : nfhyperellpadicfrobenius(GEN H, GEN T, ulong p, long n)
     613                 :            : {
     614                 :        147 :   pari_sp av = avma;
     615                 :        147 :   GEN M = ZlXQX_hyperellpadicfrobenius(lift(H),T,p,n);
     616                 :        140 :   GEN MM = ZpXQM_prodFrobenius(M, T, utoi(p), n);
     617                 :        140 :   GEN q = zeropadic(utoi(p),n);
     618                 :        140 :   GEN m = gmul(ZXM_to_padic(MM, q), gmodulo(gen_1, T));
     619                 :        140 :   return gerepileupto(av, m);
     620                 :            : }
     621                 :            : 
     622                 :            : static GEN
     623                 :         70 : F2x_genus2charpoly_naive(GEN P, GEN Q)
     624                 :            : {
     625                 :         70 :   long a, b = 1, c = 0;
     626                 :         70 :   GEN T = mkvecsmall2(P[1], 7);
     627                 :         70 :   GEN PT = F2x_rem(P, T), QT = F2x_rem(Q, T);
     628                 :         70 :   long q0 = F2x_eval(Q, 0), q1 = F2x_eval(Q, 1);
     629                 :         70 :   long dP = F2x_degree(P), dQ = F2x_degree(Q);
     630 [ +  + ][ +  + ]:         70 :   a= dQ<3 ? 0: dP<=5 ? 1: -1;
     631 [ +  + ][ +  + ]:         70 :   a += (q0? F2x_eval(P, 0)? -1: 1: 0) + (q1? F2x_eval(P, 1)? -1: 1: 0);
         [ +  + ][ +  + ]
     632                 :         70 :   b += q0 + q1;
     633         [ +  + ]:         70 :   if (lgpol(QT))
     634         [ +  + ]:         63 :     c = (F2xq_trace(F2xq_div(PT, F2xq_sqr(QT, T), T), T)==0 ? 1: -1);
     635                 :         70 :   return mkvecsmalln(6, 0UL, 4, 2*a, (b+2*c+a*a)>>1, a, 1UL);
     636                 :            : }
     637                 :            : 
     638                 :            : static GEN
     639                 :      10129 : Flx_translate1(GEN P, ulong p)
     640                 :            : {
     641                 :      10129 :   long i, k, n = degpol(P);
     642                 :      10129 :   GEN R = Flx_copy(P);
     643         [ +  + ]:      44779 :   for (i=1; i<=n; i++)
     644         [ +  + ]:     127176 :     for (k=n-i; k<n; k++)
     645                 :      92526 :       uel(R,k+2) = Fl_add(uel(R,k+2), uel(R,k+3), p);
     646                 :      10129 :   return R;
     647                 :            : }
     648                 :            : 
     649                 :            : static GEN
     650                 :      10129 : Flx_diff1(GEN P, ulong p)
     651                 :            : {
     652                 :      10129 :   return Flx_sub(Flx_translate1(P, p), P, p);
     653                 :            : }
     654                 :            : 
     655                 :            : static GEN
     656                 :       1694 : Flx_difftable(GEN P, ulong p)
     657                 :            : {
     658                 :       1694 :   long i, n = degpol(P);
     659                 :       1694 :   GEN V = cgetg(n+2, t_VEC);
     660                 :       1694 :   gel(V, n+1) = P;
     661         [ +  + ]:      11823 :   for(i = n; i >= 1; i--)
     662                 :      10129 :     gel(V, i) = Flx_diff1(gel(V, i+1), p);
     663                 :       1694 :   return V;
     664                 :            : }
     665                 :            : 
     666                 :            : static GEN
     667                 :     109431 : FlxV_Fl2_eval_pre(GEN V, GEN x, ulong D, ulong p, ulong pi)
     668                 :            : {
     669                 :     109431 :   long i, n = lg(V)-1;
     670                 :     109431 :   GEN r = cgetg(n+1, t_VEC);
     671         [ +  + ]:     874923 :   for (i = 1; i <= n; i++)
     672                 :     765492 :     gel(r, i) = Flx_Fl2_eval_pre(gel(V, i), x, D, p, pi);
     673                 :     109431 :   return r;
     674                 :            : }
     675                 :            : 
     676                 :            : static GEN
     677                 :   21630014 : Fl2V_next(GEN V, ulong p)
     678                 :            : {
     679                 :   21630014 :   long i, n = lg(V)-1;
     680                 :   21630014 :   GEN r = cgetg(n+1, t_VEC);
     681                 :   21630014 :   gel(r, 1) = gel(V, 1);
     682         [ +  + ]:  151384268 :   for (i = 2; i <= n; i++)
     683                 :  129754254 :     gel(r, i) = Flv_add(gel(V, i), gel(V, i-1), p);
     684                 :   21630014 :   return r;
     685                 :            : }
     686                 :            : 
     687                 :            : static GEN
     688                 :       1694 : Flx_genus2charpoly_naive(GEN H, ulong p)
     689                 :            : {
     690                 :       1694 :   pari_sp av = avma, av2;
     691                 :       1694 :   ulong pi = get_Fl_red(p);
     692         [ +  + ]:       1694 :   ulong i, j, p2 = p>>1, D = 2, e = ((p&2UL) == 0) ? -1 : 1;
     693                 :       1694 :   long a, b, c = 0, n = degpol(H);
     694                 :       1694 :   GEN t, k = const_vecsmall(p, -1);
     695                 :       1694 :   k[1] = 0;
     696         [ +  + ]:     111125 :   for (i=1, j=1; i < p; i += 2, j = Fl_add(j, i, p)) k[j+1] = 1;
     697         [ +  + ]:       3311 :   while (k[1+D] >= 0) D++;
     698                 :       1694 :   b = n == 5 ? 0 : 1;
     699         [ +  + ]:       1694 :   a = b ? k[1+Flx_lead(H)]: 0;
     700                 :       1694 :   t = Flx_difftable(H, p);
     701                 :       1694 :   av2 = avma;
     702         [ +  + ]:     222250 :   for (i=0; i < p; i++)
     703                 :            :   {
     704                 :     220556 :     ulong v = Flx_eval(H, i, p);
     705                 :     220556 :     a += k[1+v];
     706                 :     220556 :     b += !!v;
     707                 :            :   }
     708         [ +  + ]:     111125 :   for (j=1; j <= p2; j++)
     709                 :            :   {
     710                 :     109431 :     GEN V = FlxV_Fl2_eval_pre(t, mkvecsmall2(0, j), D, p, pi);
     711                 :     109431 :     for (i=0;; i++)
     712                 :            :     {
     713                 :   21739445 :       GEN r2 = gel(V, n+1);
     714                 :   43478890 :       c += uel(r2,2) ?
     715         [ +  + ]:   21513779 :         (uel(r2,1) ? k[1+Fl2_norm_pre(r2, D, p, pi)]: e)
     716         [ +  + ]:   43253224 :          : !!uel(r2,1);
     717         [ +  + ]:   21739445 :       if (i == p-1) break;
     718                 :   21630014 :       V = Fl2V_next(V, p);
     719                 :   21630014 :     }
     720                 :     109431 :     avma = av2;
     721                 :            :   }
     722                 :       1694 :   avma = av;
     723                 :       1694 :   return mkvecsmalln(6, 0UL, p*p, a*p, (b+2*c+a*a)>>1, a, 1UL);
     724                 :            : }
     725                 :            : 
     726                 :            : static GEN
     727                 :        658 : charpoly_funceq(GEN P, GEN q)
     728                 :            : {
     729                 :        658 :   long i, l, g = degpol(P)>>1;
     730                 :        658 :   GEN Q = cgetg_copy(P, &l);
     731                 :        658 :   Q[1] = P[1];
     732         [ +  + ]:       3696 :   for (i=0; i<=g; i++)
     733                 :       3038 :     gel(Q, i+2) = mulii(gel(P, 2*g-i+2), powiu(q, g-i));
     734         [ +  + ]:       3038 :   for (; i<=2*g; i++)
     735                 :       2380 :     gel(Q, i+2) = icopy(gel(P, i+2));
     736                 :        658 :   return Q;
     737                 :            : }
     738                 :            : 
     739                 :            : static long
     740                 :        665 : hyperell_Weil_bound(GEN q, long g, GEN p)
     741                 :            : {
     742                 :        665 :   pari_sp av = avma;
     743                 :        665 :   GEN w = mulii(binomialuu(2*g,g),sqrtint(shifti(powiu(q, g),2)));
     744                 :        665 :   long e = logint(w, p, NULL);
     745                 :        665 :   avma = av; return e;
     746                 :            : }
     747                 :            : 
     748                 :            : GEN
     749                 :       2436 : hyperellcharpoly(GEN PQ)
     750                 :            : {
     751                 :       2436 :   pari_sp av = avma;
     752                 :       2436 :   GEN H, M, R, T=NULL, pp=NULL, q;
     753                 :       2436 :   long d, g, n, eps = 0;
     754                 :            :   ulong p;
     755 [ +  + ][ +  - ]:       2436 :   if (is_vec_t(typ(PQ)) && lg(PQ)==3)
     756                 :         77 :     H = gadd(gsqr(gel(PQ, 2)), gmul2n(gel(PQ, 1), 2));
     757                 :            :   else
     758                 :       2359 :     H = PQ;
     759 [ +  - ][ +  - ]:       2436 :   if (typ(H)!=t_POL || !RgX_is_FpXQX(H, &T, &pp) || !pp)
                 [ -  + ]
     760                 :          0 :     pari_err_TYPE("hyperellcharpoly",H);
     761                 :       2436 :   p = itou(pp);
     762         [ +  + ]:       2436 :   if (!T)
     763                 :            :   {
     764 [ +  + ][ +  - ]:       2289 :     if (p==2 && is_vec_t(typ(PQ)))
     765                 :            :     {
     766                 :         70 :       long dP, dQ, v = varn(H);
     767                 :         70 :       GEN P = gel(PQ,1), Q = gel(PQ,2);
     768         [ -  + ]:         70 :       if (typ(P)!=t_POL)  P = scalarpol(P, v);
     769         [ -  + ]:         70 :       if (typ(Q)!=t_POL)  Q = scalarpol(Q, v);
     770                 :         70 :       dP = degpol(P); dQ = degpol(Q);
     771 [ +  - ][ +  - ]:         70 :       if (dP<=6 && dQ <=3 && (dQ==3 || dP>=5))
         [ +  + ][ +  - ]
     772                 :            :       {
     773                 :         70 :         GEN P2 = RgX_to_F2x(P), Q2 = RgX_to_F2x(Q);
     774                 :         70 :         GEN D = F2x_add(F2x_mul(P2, F2x_sqr(F2x_deriv(Q2))), F2x_sqr(F2x_deriv(P2)));
     775         [ -  + ]:         70 :         if (F2x_degree(F2x_gcd(D, Q2))) is_sing(PQ, 2);
     776 [ +  + ][ +  + ]:         70 :         if (dP==6 && dQ<3 && F2x_coeff(P2,5)==F2x_coeff(Q2,2))
                 [ -  + ]
     777                 :          0 :           is_sing(PQ, 2); /* The curve is singular at infinity */
     778                 :         70 :         R = zx_to_ZX(F2x_genus2charpoly_naive(P2, Q2));
     779                 :         70 :         return gerepileupto(av, R);
     780                 :            :       }
     781                 :            :     }
     782                 :       2219 :     H = RgX_to_FpX(H, pp);
     783                 :       2219 :     d = degpol(H); g = (d-1)>>1;
     784 [ +  - ][ +  + ]:       2219 :     if (p > 2 && ((d == 5 && p < 17500) || (d == 6 && p < 24500)))
         [ -  + ][ +  + ]
                 [ +  - ]
     785                 :            :     {
     786                 :       1701 :       GEN Hp = ZX_to_Flx(H, p);
     787         [ +  + ]:       1701 :       if (!Flx_is_squarefree(Hp, p)) is_sing(H, p);
     788                 :       1694 :       R = zx_to_ZX(Flx_genus2charpoly_naive(Hp, p));
     789                 :       1694 :       return gerepileupto(av, R);
     790                 :            :     }
     791                 :        518 :     n = hyperell_Weil_bound(pp, g, pp);
     792         [ +  + ]:        518 :     eps = odd(d)? 0: Fp_issquare(leading_coeff(H), pp);
     793                 :        518 :     M = hyperellpadicfrobenius(H, p, n);
     794                 :        518 :     R = centerlift(carberkowitz(M, 0));
     795                 :        518 :     q = pp;
     796                 :            :   }
     797                 :            :   else
     798                 :            :   {
     799                 :            :     int fixvar;
     800         [ +  + ]:        147 :     T = typ(T)==t_FFELT? FF_mod(T): RgX_to_FpX(T, pp);
     801                 :        147 :     q = powuu(p, degpol(T));
     802                 :        147 :     fixvar = (varncmp(varn(T),varn(H)) <= 0);
     803         [ +  + ]:        147 :     if (fixvar) setvarn(T, fetch_var());
     804                 :        147 :     H = RgX_to_FpXQX(H, T, pp);
     805         [ +  + ]:        147 :     d = degpol(H); eps = odd(d)? 0: Fq_issquare(leading_coeff(H), T, pp);
     806                 :        147 :     g = (d-1)>>1;
     807                 :        147 :     n = hyperell_Weil_bound(q, g, pp);
     808                 :        147 :     M = nfhyperellpadicfrobenius(H, T, p, n);
     809                 :        140 :     R = simplify_shallow(centerlift(liftpol_shallow(carberkowitz(M, 0))));
     810         [ +  + ]:        140 :     if (fixvar) (void)delete_var();
     811                 :            :   }
     812         [ +  + ]:        658 :   if (!odd(d))
     813                 :            :   {
     814         [ +  + ]:        280 :     GEN b = get_basis(p, d) == 3 ? gen_1 : q;
     815                 :        280 :     GEN pn = powuu(p, n);
     816         [ +  + ]:        280 :     R = FpX_div_by_X_x(R, eps? b: negi(b), pn, NULL);
     817                 :        280 :     R = FpX_center(R, pn, shifti(pn,-1));
     818                 :            :   }
     819                 :        658 :   R = charpoly_funceq(R, q);
     820                 :       2422 :   return gerepilecopy(av, R);
     821                 :            : }

Generated by: LCOV version 1.9