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 - hyperell.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.8.0 lcov report (development 17727-c4b959b) Lines: 410 432 94.9 %
Date: 2015-04-21 Functions: 34 34 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 171 238 71.8 %

           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                 :            : static GEN
      37                 :      11396 : FpXXQ_red(GEN S, GEN T, GEN p)
      38                 :            : {
      39                 :      11396 :   pari_sp av = avma;
      40                 :      11396 :   long i, dS = degpol(S);
      41                 :            :   GEN A, C;
      42         [ -  + ]:      11396 :   if (signe(S)==0) return pol_0(varn(T));
      43                 :      11396 :   A = cgetg(dS+3, t_POL);
      44                 :      11396 :   C = pol_0(varn(T));
      45         [ +  + ]:    1238650 :   for(i=dS; i>0; i--)
      46                 :            :   {
      47                 :    1227254 :     GEN Si = FpX_add(C, gel(S,i+2), p);
      48                 :    1227254 :     GEN R, Q = FpX_divrem(Si, T, p, &R);
      49                 :    1227254 :     gel(A,i+2) = R;
      50                 :    1227254 :     C = Q;
      51                 :            :   }
      52                 :      11396 :   gel(A,2) = FpX_add(C, gel(S,2), p);
      53                 :      11396 :   A[1] = S[1];
      54                 :      11396 :   return gerepilecopy(av, FpXX_renormalize(A,dS+3));
      55                 :            : }
      56                 :            : 
      57                 :            : static GEN
      58                 :       2170 : FpXXQ_sqr(GEN x, GEN T, GEN p)
      59                 :            : {
      60                 :       2170 :   pari_sp av = avma;
      61                 :       2170 :   long n = degpol(T);
      62                 :       2170 :   GEN z = FpX_red(ZXX_sqr_Kronecker(x, n), p);
      63                 :       2170 :   z = Kronecker_to_ZXX(z, n, varn(T));
      64                 :       2170 :   return gerepileupto(av, FpXXQ_red(z, T, p));
      65                 :            : }
      66                 :            : 
      67                 :            : static GEN
      68                 :       9226 : FpXXQ_mul(GEN x, GEN y, GEN T, GEN p)
      69                 :            : {
      70                 :       9226 :   pari_sp av = avma;
      71                 :       9226 :   long n = degpol(T);
      72                 :       9226 :   GEN z = FpX_red(ZXX_mul_Kronecker(x, y, n), p);
      73                 :       9226 :   z = Kronecker_to_ZXX(z, n, varn(T));
      74                 :       9226 :   return gerepileupto(av, FpXXQ_red(z, T, p));
      75                 :            : }
      76                 :            : 
      77                 :            : static GEN
      78                 :        686 : ZpXXQ_invsqrt(GEN S, GEN T, ulong p, long e)
      79                 :            : {
      80                 :        686 :   pari_sp av = avma, av2;
      81                 :            :   ulong mask;
      82                 :        686 :   long v = varn(S), n=1;
      83                 :        686 :   GEN a = pol_1(v);
      84         [ -  + ]:        686 :   if (e <= 1) return gerepilecopy(av, a);
      85                 :        686 :   mask = quadratic_prec_mask(e);
      86                 :        686 :   av2 = avma;
      87         [ +  + ]:       2856 :   for (;mask>1;)
      88                 :            :   {
      89                 :            :     GEN q, q2, q22, f, fq, afq;
      90                 :       2170 :     long n2 = n;
      91         [ +  + ]:       2170 :     n<<=1; if (mask & 1) n--;
      92                 :       2170 :     mask >>= 1;
      93                 :       2170 :     q = powuu(p,n); q2 = powuu(p,n2);
      94                 :       2170 :     f = RgX_sub(FpXXQ_mul(S, FpXXQ_sqr(a, T, q), T, q), pol_1(v));
      95                 :       2170 :     fq = ZXX_Z_divexact(f, q2);
      96                 :       2170 :     q22 = shifti(addis(q2,1),-1);
      97                 :       2170 :     afq = FpXX_Fp_mul(FpXXQ_mul(a, fq, T, q2), q22, q2);
      98                 :       2170 :     a = RgX_sub(a, ZXX_Z_mul(afq, q2));
      99         [ -  + ]:       2170 :     if (gc_needed(av2,1))
     100                 :            :     {
     101         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXXQ_invsqrt, e = %ld", n);
     102                 :          0 :       a = gerepileupto(av2, a);
     103                 :            :     }
     104                 :            :   }
     105                 :        686 :   return gerepileupto(av, a);
     106                 :            : }
     107                 :            : 
     108                 :            : static GEN
     109         [ +  + ]:      14420 : to_ZX(GEN a, long v) { return typ(a)==t_INT? scalarpol(a,v): a; }
     110                 :            : 
     111                 :            : static void
     112                 :         14 : is_sing(GEN H, ulong p)
     113                 :            : {
     114                 :         14 :   pari_err_DOMAIN("hyperellpadicfrobenius","H","is singular at",utoi(p),H);
     115                 :          0 : }
     116                 :            : 
     117                 :            : static void
     118                 :        686 : get_UV(GEN *U, GEN *V, GEN T, ulong p, long e)
     119                 :            : {
     120                 :        686 :   GEN q = powuu(p,e), d;
     121                 :        686 :   GEN dT = FpX_deriv(T, q);
     122                 :        686 :   GEN R = polresultantext(T, dT);
     123                 :        686 :   long v = varn(T);
     124         [ -  + ]:        686 :   if (dvdiu(gel(R,3),p)) is_sing(T, p);
     125                 :        686 :   d = Fp_inv(gel(R,3), q);
     126                 :        686 :   *U = FpX_Fp_mul(FpX_red(to_ZX(gel(R,1),v),q),d,q);
     127                 :        686 :   *V = FpX_Fp_mul(FpX_red(to_ZX(gel(R,2),v),q),d,q);
     128                 :        686 : }
     129                 :            : 
     130                 :            : static GEN
     131                 :      68936 : frac_to_Fp(GEN a, GEN b, GEN p)
     132                 :            : {
     133                 :      68936 :   GEN d = gcdii(a, b);
     134                 :      68936 :   return Fp_div(diviiexact(a, d), diviiexact(b, d), p);
     135                 :            : }
     136                 :            : 
     137                 :            : static GEN
     138                 :       4886 : ZpXXQ_frob(GEN S, GEN U, GEN V, GEN T, ulong p, long e)
     139                 :            : {
     140                 :       4886 :   pari_sp av = avma, av2;
     141                 :       4886 :   long i, pr = degpol(S), dT = degpol(T);
     142                 :       4886 :   GEN q = powuu(p,e);
     143                 :       4886 :   GEN Tp = FpX_deriv(T, q), Tp1 = RgX_shift_shallow(Tp, 1);
     144                 :       4886 :   GEN M = gel(S,pr+2), R;
     145                 :       4886 :   av2 = avma;
     146         [ +  + ]:     759472 :   for(i = pr-1; i>=0; i--)
     147                 :            :   {
     148                 :            :     GEN A, B, H, Bc;
     149                 :            :     ulong v, r;
     150                 :     754586 :     H = FpX_divrem(FpX_mul(V,M,q), T, q, &B);
     151                 :     754586 :     A = FpX_add(FpX_mul(U,M,q), FpX_mul(H, Tp, q),q);
     152                 :     754586 :     v = u_lvalrem(2*i+1,p,&r);
     153                 :     754586 :     Bc = FpX_deriv(B, q);
     154                 :     754586 :     Bc = FpX_Fp_mul(ZX_Z_divexact(Bc,powuu(p,v)),Fp_div(gen_2, utoi(r), q), q);
     155                 :     754586 :     M = FpX_add(gel(S,i+2), FpX_add(A, Bc, q), q);
     156         [ -  + ]:     754586 :     if (gc_needed(av2,1))
     157                 :            :     {
     158         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXXQ_frob, step 1, i = %ld", i);
     159                 :          0 :       M = gerepileupto(av2, M);
     160                 :            :     }
     161                 :            :   }
     162         [ +  + ]:       4886 :   if (degpol(M)<dT-1)
     163                 :       2562 :     return gerepileupto(av, M);
     164                 :       2324 :   R = RgX_shift_shallow(M,dT-degpol(M)-2);
     165                 :       2324 :   av2 = avma;
     166         [ +  + ]:     120302 :   for(i = degpol(M)-dT+2; i>=1; i--)
     167                 :            :   {
     168                 :            :     GEN B, c;
     169                 :     117978 :     R = RgX_shift_shallow(R, 1);
     170                 :     117978 :     gel(R,2) = gel(M, i+1);
     171         [ +  + ]:     117978 :     if (degpol(R) < dT) continue;
     172                 :      67431 :     B = FpX_add(FpX_mulu(T, 2*i, q), Tp1, q);
     173                 :      67431 :     c = frac_to_Fp(leading_term(R), leading_term(B), q);
     174                 :      67431 :     R = FpX_sub(R, FpX_Fp_mul(B, c, q), q);
     175         [ -  + ]:      67431 :     if (gc_needed(av2,1))
     176                 :            :     {
     177         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXXQ_frob, step 2, i = %ld", i);
     178                 :          0 :       R = gerepileupto(av2, R);
     179                 :            :     }
     180                 :            :   }
     181         [ +  + ]:       2324 :   if (degpol(R)==dT-1)
     182                 :            :   {
     183                 :       1505 :     GEN c = frac_to_Fp(leading_term(R), leading_term(Tp), q);
     184                 :       1505 :     R = FpX_sub(R, FpX_Fp_mul(Tp, c, q), q);
     185                 :       1505 :     return gerepileupto(av, R);
     186                 :            :   } else
     187                 :       4886 :     return gerepilecopy(av, R);
     188                 :            : }
     189                 :            : 
     190                 :            : static GEN
     191                 :       5894 : revdigits(GEN v)
     192                 :            : {
     193                 :       5894 :   long i, n = lg(v)-1;
     194                 :       5894 :   GEN w = cgetg(n+2, t_POL);
     195                 :       5894 :   w[1] = evalsigne(1)|evalvarn(0);
     196         [ +  + ]:      90524 :   for (i=0; i<n; i++)
     197                 :      84630 :     gel(w,i+2) = gel(v,n-i);
     198                 :       5894 :   return FpXX_renormalize(w, n+2);
     199                 :            : }
     200                 :            : 
     201                 :            : static GEN
     202                 :       4886 : diff_red(GEN s, GEN A, long m, GEN T, GEN p)
     203                 :            : {
     204                 :            :   long v, n;
     205                 :            :   GEN Q, sQ, qS;
     206                 :            :   pari_timer ti;
     207         [ -  + ]:       4886 :   if (DEBUGLEVEL>1) timer_start(&ti);
     208                 :       4886 :   Q = revdigits(FpX_digits(A,T,p));
     209                 :       4886 :   n = degpol(Q);
     210         [ -  + ]:       4886 :   if (DEBUGLEVEL>1) timer_printf(&ti,"reddigits");
     211                 :       4886 :   sQ = FpXXQ_mul(s,Q,T,p);
     212         [ -  + ]:       4886 :   if (DEBUGLEVEL>1) timer_printf(&ti,"redmul");
     213                 :       4886 :   qS = RgX_shift_shallow(sQ,m-n);
     214                 :       4886 :   v = ZX_val(sQ);
     215         [ +  + ]:       4886 :   if (n > m + v)
     216                 :            :   {
     217                 :       2296 :     long i, l = n-m-v;
     218                 :       2296 :     GEN rS = cgetg(l+1,t_VEC);
     219         [ +  + ]:      14833 :     for (i = l-1; i >=0 ; i--)
     220                 :      12537 :       gel(rS,i+1) = gel(sQ, 1+v+l-i);
     221                 :       2296 :     rS = FpX_fromdigits(rS,T,p);
     222                 :       2296 :     gel(qS,2) = FpX_add(FpX_mul(rS, T, p), gel(qS, 2), p);
     223         [ -  + ]:       2296 :     if (DEBUGLEVEL>1) timer_printf(&ti,"redadd");
     224                 :            :   }
     225                 :       4886 :   return qS;
     226                 :            : }
     227                 :            : 
     228                 :            : static GEN
     229                 :       4886 : ZC_to_padic(GEN C, GEN q)
     230                 :            : {
     231                 :       4886 :   long i, l = lg(C);
     232                 :       4886 :   GEN V = cgetg(l,t_COL);
     233         [ +  + ]:      49140 :   for(i = 1; i < l; i++)
     234                 :      44254 :     gel(V, i) = gadd(gel(C, i), q);
     235                 :       4886 :   return V;
     236                 :            : }
     237                 :            : 
     238                 :            : static GEN
     239                 :        686 : ZM_to_padic(GEN M, GEN q)
     240                 :            : {
     241                 :        686 :   long i, l = lg(M);
     242                 :        686 :   GEN V = cgetg(l,t_MAT);
     243         [ +  + ]:       5572 :   for(i = 1; i < l; i++)
     244                 :       4886 :     gel(V, i) = ZC_to_padic(gel(M, i), q);
     245                 :        686 :   return V;
     246                 :            : }
     247                 :            : 
     248                 :            : static GEN
     249                 :       1211 : ZX_to_padic(GEN P, GEN q)
     250                 :            : {
     251                 :       1211 :   long i, l = lg(P);
     252                 :       1211 :   GEN Q = cgetg(l, t_POL);
     253                 :       1211 :   Q[1] = P[1];
     254         [ +  + ]:       3738 :   for (i=2; i<l ;i++)
     255                 :       2527 :     gel(Q,i) = gadd(gel(P,i), q);
     256                 :       1211 :   return normalizepol(Q);
     257                 :            : }
     258                 :            : 
     259                 :            : static GEN
     260                 :        259 : ZXC_to_padic(GEN C, GEN q)
     261                 :            : {
     262                 :        259 :   long i, l = lg(C);
     263                 :        259 :   GEN V = cgetg(l,t_COL);
     264         [ +  + ]:       1470 :   for(i = 1; i < l; i++)
     265                 :       1211 :     gel(V, i) = ZX_to_padic(gel(C, i), q);
     266                 :        259 :   return V;
     267                 :            : }
     268                 :            : 
     269                 :            : static GEN
     270                 :         56 : ZXM_to_padic(GEN M, GEN q)
     271                 :            : {
     272                 :         56 :   long i, l = lg(M);
     273                 :         56 :   GEN V = cgetg(l,t_MAT);
     274         [ +  + ]:        315 :   for(i = 1; i < l; i++)
     275                 :        259 :     gel(V, i) = ZXC_to_padic(gel(M, i), q);
     276                 :         56 :   return V;
     277                 :            : }
     278                 :            : 
     279                 :            : static GEN
     280                 :        686 : ZlX_hyperellpadicfrobenius(GEN H, ulong p, long n)
     281                 :            : {
     282                 :        686 :   pari_sp av = avma;
     283                 :            :   long N, i, d;
     284                 :            :   GEN F, s, Q, pN1, U, V;
     285                 :            :   pari_timer ti;
     286         [ -  + ]:        686 :   if (typ(H) != t_POL) pari_err_TYPE("hyperellpadicfrobenius",H);
     287         [ -  + ]:        686 :   if (p == 2) is_sing(H, 2);
     288                 :        686 :   d = degpol(H);
     289         [ -  + ]:        686 :   if (d <= 0)
     290                 :          0 :     pari_err_CONSTPOL("hyperellpadicfrobenius");
     291 [ +  + ][ -  + ]:        686 :   if (odd(d) &&  p < (ulong) d)
     292                 :          0 :     pari_err_DOMAIN("hyperellpadicfrobenius","p","<", utoi(d), utoi(p));
     293 [ +  + ][ -  + ]:        686 :   if (!odd(d) &&  2*p < (ulong) d)
     294                 :          0 :     pari_err_DOMAIN("hyperellpadicfrobenius","2*p","<", utoi(d), utoi(2*p));
     295         [ -  + ]:        686 :   if (n < 1)
     296                 :          0 :     pari_err_DOMAIN("hyperellpadicfrobenius","n","<", gen_1, utoi(n));
     297                 :        686 :   N = n + logint(stoi(2*n), stoi(p), NULL);
     298                 :        686 :   pN1 = powuu(p,N+1);
     299                 :        686 :   Q = RgX_to_FpX(H, pN1);
     300         [ -  + ]:        686 :   if (dvdiu(leading_term(Q),p)) is_sing(H, p);
     301                 :        686 :   setvarn(Q,1);
     302         [ -  + ]:        686 :   if (DEBUGLEVEL>1) timer_start(&ti);
     303                 :        686 :   s = revdigits(FpX_digits(RgX_inflate(Q, p), Q, pN1));
     304         [ -  + ]:        686 :   if (DEBUGLEVEL>1) timer_printf(&ti,"s1");
     305                 :        686 :   s = ZpXXQ_invsqrt(s, Q, p, N);
     306         [ -  + ]:        686 :   if (DEBUGLEVEL>1) timer_printf(&ti,"invsqrt");
     307                 :        686 :   get_UV(&U, &V, Q, p, N+1);
     308                 :        686 :   F = cgetg(d, t_MAT);
     309         [ +  + ]:       5572 :   for (i = 1; i < d; i++)
     310                 :            :   {
     311                 :       4886 :     pari_sp av2 = avma;
     312                 :            :     GEN M, D;
     313                 :       4886 :     D = diff_red(s, monomial(utoi(p),p*i-1,1),p>>1, Q, pN1);
     314         [ -  + ]:       4886 :     if (DEBUGLEVEL>1) timer_printf(&ti,"red");
     315                 :       4886 :     M = ZpXXQ_frob(D, U, V, Q, p, N + 1);
     316         [ -  + ]:       4886 :     if (DEBUGLEVEL>1) timer_printf(&ti,"frob");
     317                 :       4886 :     gel(F, i) = gerepilecopy(av2, RgX_to_RgC(M, d-1));
     318                 :            :   }
     319                 :        686 :   return gerepileupto(av, F);
     320                 :            : }
     321                 :            : 
     322                 :            : GEN
     323                 :        686 : hyperellpadicfrobenius(GEN H, ulong p, long n)
     324                 :            : {
     325                 :        686 :   pari_sp av = avma;
     326                 :        686 :   GEN M = ZlX_hyperellpadicfrobenius(H, p, n);
     327                 :        686 :   GEN q = zeropadic(utoi(p),n);
     328                 :        686 :   return gerepileupto(av, ZM_to_padic(M, q));
     329                 :            : }
     330                 :            : 
     331                 :            : INLINE GEN
     332                 :       1078 : FpXXX_renormalize(GEN x, long lx)  { return ZXX_renormalize(x,lx); }
     333                 :            : 
     334                 :            : static GEN
     335                 :        889 : FpXQXXQ_red(GEN F, GEN S, GEN T, GEN p)
     336                 :            : {
     337                 :        889 :   pari_sp av = avma;
     338                 :        889 :   long i, dF = degpol(F);
     339                 :            :   GEN A, C;
     340         [ +  + ]:        889 :   if (signe(F)==0) return pol_0(varn(S));
     341                 :        868 :   A = cgetg(dF+3, t_POL);
     342                 :        868 :   C = pol_0(varn(S));
     343         [ +  + ]:     178353 :   for(i=dF; i>0; i--)
     344                 :            :   {
     345                 :     177485 :     GEN Fi = FpXX_add(C, gel(F,i+2), p);
     346                 :     177485 :     GEN R, Q = FpXQX_divrem(Fi, S, T, p, &R);
     347                 :     177485 :     gel(A,i+2) = R;
     348                 :     177485 :     C = Q;
     349                 :            :   }
     350                 :        868 :   gel(A,2) = FpXX_add(C, gel(F,2), p);
     351                 :        868 :   A[1] = F[1];
     352                 :        889 :   return gerepilecopy(av, FpXXX_renormalize(A,dF+3));
     353                 :            : }
     354                 :            : 
     355                 :            : static GEN
     356                 :        210 : FpXQXXQ_sqr(GEN x, GEN S, GEN T, GEN p)
     357                 :            : {
     358                 :        210 :   pari_sp av = avma;
     359                 :            :   GEN z, kx;
     360                 :        210 :   long n = degpol(S);
     361                 :        210 :   kx = ZXX_to_Kronecker(x, n);
     362                 :        210 :   z = Kronecker_to_ZXX(FpXQX_sqr(kx, T, p), n, varn(S));
     363                 :        210 :   return gerepileupto(av, FpXQXXQ_red(z, S, T, p));
     364                 :            : }
     365                 :            : 
     366                 :            : static GEN
     367                 :        679 : FpXQXXQ_mul(GEN x, GEN y, GEN S, GEN T, GEN p)
     368                 :            : {
     369                 :        679 :   pari_sp av = avma;
     370                 :            :   GEN z, kx, ky;
     371                 :        679 :   long n = degpol(S);
     372                 :        679 :   kx = ZXX_to_Kronecker(x, n);
     373                 :        679 :   ky = ZXX_to_Kronecker(y, n);
     374                 :        679 :   z = Kronecker_to_ZXX(FpXQX_mul(ky, kx, T, p), n, varn(S));
     375                 :        679 :   return gerepileupto(av, FpXQXXQ_red(z, S, T, p));
     376                 :            : }
     377                 :            : 
     378                 :            : static GEN
     379                 :        210 : FpXXX_red(GEN z, GEN p)
     380                 :            : {
     381                 :            :   GEN res;
     382                 :        210 :   long i, l = lg(z);
     383                 :        210 :   res = cgetg(l,t_POL); res[1] = z[1];
     384         [ +  + ]:      32900 :   for (i=2; i<l; i++)
     385                 :            :   {
     386                 :      32690 :     GEN zi = gel(z,i);
     387         [ -  + ]:      32690 :     if (typ(zi)==t_INT)
     388                 :          0 :       gel(res,i) = modii(zi,p);
     389                 :            :     else
     390                 :      32690 :      gel(res,i) = FpXX_red(zi,p);
     391                 :            :   }
     392                 :        210 :   return FpXXX_renormalize(res,lg(res));
     393                 :            : }
     394                 :            : 
     395                 :            : static GEN
     396                 :        210 : FpXXX_Fp_mul(GEN z, GEN a, GEN p)
     397                 :            : {
     398                 :        210 :   return FpXXX_red(RgX_Rg_mul(z, a), p);
     399                 :            : }
     400                 :            : 
     401                 :            : static GEN
     402                 :         63 : ZpXQXXQ_invsqrt(GEN F, GEN S, GEN T, ulong p, long e)
     403                 :            : {
     404                 :         63 :   pari_sp av = avma, av2, av3;
     405                 :            :   ulong mask;
     406                 :         63 :   long v = varn(F), n=1;
     407                 :            :   pari_timer ti;
     408                 :         63 :   GEN a = pol_1(v);
     409         [ -  + ]:         63 :   if (DEBUGLEVEL>1) timer_start(&ti);
     410         [ -  + ]:         63 :   if (e <= 1) return gerepilecopy(av, a);
     411                 :         63 :   mask = quadratic_prec_mask(e);
     412                 :         63 :   av2 = avma;
     413         [ +  + ]:        273 :   for (;mask>1;)
     414                 :            :   {
     415                 :            :     GEN q, q2, q22, f, fq, afq;
     416                 :        210 :     long n2 = n;
     417         [ +  + ]:        210 :     n<<=1; if (mask & 1) n--;
     418                 :        210 :     mask >>= 1;
     419                 :        210 :     q = powuu(p,n); q2 = powuu(p,n2);
     420                 :        210 :     av3 = avma;
     421                 :        210 :     f = RgX_sub(FpXQXXQ_mul(F, FpXQXXQ_sqr(a, S, T, q), S, T, q), pol_1(v));
     422                 :        210 :     fq = gerepileupto(av3, RgX_Rg_divexact(f, q2));
     423                 :        210 :     q22 = shifti(addis(q2,1),-1);
     424                 :        210 :     afq = FpXXX_Fp_mul(FpXQXXQ_mul(a, fq, S, T, q2), q22, q2);
     425                 :        210 :     a = RgX_sub(a, RgX_Rg_mul(afq, q2));
     426         [ -  + ]:        210 :     if (gc_needed(av2,1))
     427                 :            :     {
     428         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXQXXQ_invsqrt, e = %ld", n);
     429                 :          0 :       a = gerepileupto(av2, a);
     430                 :            :     }
     431                 :            :   }
     432                 :         63 :   return gerepileupto(av, a);
     433                 :            : }
     434                 :            : 
     435                 :            : static GEN
     436                 :       6405 : frac_to_Fq(GEN a, GEN b, GEN T, GEN p)
     437                 :            : {
     438                 :       6405 :   GEN d = gcdii(ZX_content(a), ZX_content(b));
     439                 :       6405 :   return FpXQ_div(ZX_Z_divexact(a, d), ZX_Z_divexact(b, d), T, p);
     440                 :            : }
     441                 :            : 
     442                 :            : static GEN
     443                 :        259 : ZpXQXXQ_frob(GEN F, GEN U, GEN V, GEN S, GEN T, ulong p, long e)
     444                 :            : {
     445                 :        259 :   pari_sp av = avma, av2;
     446                 :        259 :   long i, pr = degpol(F), dS = degpol(S), v = varn(T);
     447                 :        259 :   GEN q = powuu(p,e);
     448                 :        259 :   GEN Sp = RgX_deriv(S), Sp1 = RgX_shift_shallow(Sp, 1);
     449                 :        259 :   GEN M = gel(F,pr+2), R;
     450                 :        259 :   av2 = avma;
     451         [ +  + ]:      90636 :   for(i = pr-1; i>=0; i--)
     452                 :            :   {
     453                 :            :     GEN A, B, H, Bc;
     454                 :            :     ulong v, r;
     455                 :      90377 :     H = FpXQX_divrem(FpXQX_mul(V, M, T, q), S, T, q, &B);
     456                 :      90377 :     A = FpXX_add(FpXQX_mul(U, M, T, q), FpXQX_mul(H, Sp, T, q),q);
     457                 :      90377 :     v = u_lvalrem(2*i+1,p,&r);
     458                 :      90377 :     Bc = RgX_deriv(B);
     459                 :      90377 :     Bc = FpXX_Fp_mul(ZXX_Z_divexact(Bc,powuu(p,v)), Fp_div(gen_2, utoi(r), q), q);
     460                 :      90377 :     M = FpXX_add(gel(F,i+2), FpXX_add(A, Bc, q), q);
     461         [ +  + ]:      90377 :     if (gc_needed(av2,1))
     462                 :            :     {
     463         [ -  + ]:         82 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXQXXQ_frob, step 1, i = %ld", i);
     464                 :         82 :       M = gerepileupto(av2, M);
     465                 :            :     }
     466                 :            :   }
     467         [ +  + ]:        259 :   if (degpol(M)<dS-1)
     468                 :        147 :     return gerepileupto(av, M);
     469                 :        112 :   R = RgX_shift_shallow(M,dS-degpol(M)-2);
     470                 :        112 :   av2 = avma;
     471         [ +  + ]:       6860 :   for(i = degpol(M)-dS+2; i>=1; i--)
     472                 :            :   {
     473                 :            :     GEN B, c;
     474                 :       6748 :     R = RgX_shift_shallow(R, 1);
     475                 :       6748 :     gel(R,2) = gel(M, i+1);
     476         [ +  + ]:       6748 :     if (degpol(R) < dS) continue;
     477                 :       6321 :     B = FpXX_add(FpXX_mulu(S, 2*i, q), Sp1, q);
     478                 :       6321 :     c = frac_to_Fq(to_ZX(leading_term(R),v), to_ZX(leading_term(B),v), T, q);
     479                 :       6321 :     R = FpXX_sub(R, FpXQX_FpXQ_mul(B, c, T, q), q);
     480         [ -  + ]:       6321 :     if (gc_needed(av2,1))
     481                 :            :     {
     482         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXXQ_frob, step 2, i = %ld", i);
     483                 :          0 :       R = gerepileupto(av2, R);
     484                 :            :     }
     485                 :            :   }
     486         [ +  + ]:        112 :   if (degpol(R)==dS-1)
     487                 :            :   {
     488                 :         84 :     GEN c = frac_to_Fq(to_ZX(leading_term(R),v), to_ZX(leading_term(Sp),v), T, q);
     489                 :         84 :     R = FpXX_sub(R, FpXQX_FpXQ_mul(Sp, c, T, q), q);
     490                 :         84 :     return gerepileupto(av, R);
     491                 :            :   } else
     492                 :        259 :     return gerepilecopy(av, R);
     493                 :            : }
     494                 :            : 
     495                 :            : 
     496                 :            : static GEN
     497                 :        259 : Fq_diff_red(GEN s, GEN A, long m, GEN S, GEN T, GEN p)
     498                 :            : {
     499                 :            :   long v, n;
     500                 :            :   GEN Q, sQ, qS;
     501                 :            :   pari_timer ti;
     502         [ -  + ]:        259 :   if (DEBUGLEVEL>1) timer_start(&ti);
     503                 :        259 :   Q = revdigits(FpXQX_digits(A, S, T, p));
     504                 :        259 :   n = degpol(Q);
     505         [ -  + ]:        259 :   if (DEBUGLEVEL>1) timer_printf(&ti,"reddigits");
     506                 :        259 :   sQ = FpXQXXQ_mul(s,Q,S,T,p);
     507         [ -  + ]:        259 :   if (DEBUGLEVEL>1) timer_printf(&ti,"redmul");
     508                 :        259 :   qS = RgX_shift_shallow(sQ,m-n);
     509                 :        259 :   v = ZX_val(sQ);
     510         [ +  + ]:        259 :   if (n > m + v)
     511                 :            :   {
     512                 :        105 :     long i, l = n-m-v;
     513                 :        105 :     GEN rS = cgetg(l+1,t_VEC);
     514         [ +  + ]:       1372 :     for (i = l-1; i >=0 ; i--)
     515                 :       1267 :       gel(rS,i+1) = gel(sQ, 1+v+l-i);
     516                 :        105 :     rS = FpXQX_fromdigits(rS,S,T,p);
     517                 :        105 :     gel(qS,2) = FpXX_add(FpXQX_mul(rS, S, T, p), gel(qS, 2), p);
     518         [ -  + ]:        105 :     if (DEBUGLEVEL>1) timer_printf(&ti,"redadd");
     519                 :            :   }
     520                 :        259 :   return qS;
     521                 :            : }
     522                 :            : 
     523                 :            : static void
     524                 :         63 : Fq_get_UV(GEN *U, GEN *V, GEN S, GEN T, ulong p, long e)
     525                 :            : {
     526                 :         63 :   GEN q = powuu(p, e), d;
     527                 :         63 :   GEN dS = RgX_deriv(S);
     528                 :         63 :   GEN R  = polresultantext(S, dS), C;
     529                 :         63 :   long v = varn(S);
     530         [ +  + ]:         63 :   if (signe(FpX_red(to_ZX(gel(R,3),v),utoi(p)))==0) is_sing(S, p);
     531                 :         56 :   C = FpXQ_red(gel(R, 3), T, q);
     532                 :         56 :   d = ZpXQ_inv(C, T, utoi(p), e);
     533                 :         56 :   *U = FpXQX_FpXQ_mul(FpXQX_red(to_ZX(gel(R,1),v),T,q),d,T,q);
     534                 :         56 :   *V = FpXQX_FpXQ_mul(FpXQX_red(to_ZX(gel(R,2),v),T,q),d,T,q);
     535                 :         56 : }
     536                 :            : 
     537                 :            : static GEN
     538                 :        259 : ZXX_to_FpXC(GEN x, long N, GEN p, long v)
     539                 :            : {
     540                 :            :   long i, l;
     541                 :            :   GEN z;
     542                 :        259 :   l = lg(x)-1; x++;
     543         [ -  + ]:        259 :   if (l > N+1) l = N+1; /* truncate higher degree terms */
     544                 :        259 :   z = cgetg(N+1,t_COL);
     545         [ +  + ]:       1470 :   for (i=1; i<l ; i++)
     546                 :            :   {
     547                 :       1211 :     GEN xi = gel(x, i);
     548         [ -  + ]:       1211 :     gel(z,i) = typ(xi)==t_INT? scalarpol(Fp_red(xi, p), v): FpX_red(xi, p);
     549                 :            :   }
     550         [ -  + ]:        259 :   for (   ; i<l ; i++)
     551                 :          0 :     gel(z,i) = pol_0(v);
     552                 :        259 :   return z;
     553                 :            : }
     554                 :            : 
     555                 :            : GEN
     556                 :         63 : ZlXQX_hyperellpadicfrobenius(GEN H, GEN T, ulong p, long n)
     557                 :            : {
     558                 :         63 :   pari_sp av = avma;
     559                 :            :   long N, i, d;
     560                 :            :   GEN xp, F, s, q, Q, pN1, U, V;
     561                 :            :   pari_timer ti;
     562         [ -  + ]:         63 :   if (typ(H) != t_POL) pari_err_TYPE("hyperellpadicfrobenius",H);
     563         [ -  + ]:         63 :   if (p == 2) is_sing(H, 2);
     564                 :         63 :   d = degpol(H);
     565         [ -  + ]:         63 :   if (d <= 0)
     566                 :          0 :     pari_err_CONSTPOL("hyperellpadicfrobenius");
     567 [ +  + ][ -  + ]:         63 :   if (odd(d) &&  p < (ulong) d)
     568                 :          0 :     pari_err_DOMAIN("hyperellpadicfrobenius","p","<", utoi(d), utoi(p));
     569 [ +  + ][ -  + ]:         63 :   if (!odd(d) && 2*p < (ulong) d)
     570                 :          0 :     pari_err_DOMAIN("hyperellpadicfrobenius","2*p","<", utoi(d), utoi(p));
     571         [ -  + ]:         63 :   if (n < 1)
     572                 :          0 :     pari_err_DOMAIN("hyperellpadicfrobenius","n","<", gen_1, utoi(n));
     573                 :         63 :   N = n + logint(stoi(2*n), stoi(p), NULL);
     574                 :         63 :   q = powuu(p,n); pN1 = powuu(p,N+1); T = FpX_get_red(T, pN1);
     575                 :         63 :   Q = RgX_to_FqX(H, T, pN1);
     576         [ -  + ]:         63 :   if (signe(FpX_red(to_ZX(leading_term(Q),varn(Q)),utoi(p)))==0) is_sing(H, p);
     577         [ -  + ]:         63 :   if (DEBUGLEVEL>1) timer_start(&ti);
     578                 :         63 :   xp = ZpX_Frobenius(T, utoi(p), N+1);
     579                 :         63 :   s = RgX_inflate(FpXY_FpXQ_evalx(Q, xp, T, pN1), p);
     580                 :         63 :   s = revdigits(FpXQX_digits(s, Q, T, pN1));
     581         [ -  + ]:         63 :   if (DEBUGLEVEL>1) timer_printf(&ti,"s1");
     582                 :         63 :   s = ZpXQXXQ_invsqrt(s, Q, T, p, N);
     583         [ -  + ]:         63 :   if (DEBUGLEVEL>1) timer_printf(&ti,"invsqrt");
     584                 :         63 :   Fq_get_UV(&U, &V, Q, T, p, N+1);
     585         [ -  + ]:         56 :   if (DEBUGLEVEL>1) timer_printf(&ti,"get_UV");
     586                 :         56 :   F = cgetg(d, t_MAT);
     587         [ +  + ]:        315 :   for (i = 1; i < d; i++)
     588                 :            :   {
     589                 :        259 :     pari_sp av2 = avma;
     590                 :            :     GEN M, D;
     591                 :        259 :     D = Fq_diff_red(s, monomial(utoi(p),p*i-1,1),p>>1, Q, T, pN1);
     592         [ -  + ]:        259 :     if (DEBUGLEVEL>1) timer_printf(&ti,"red");
     593                 :        259 :     M = ZpXQXXQ_frob(D, U, V, Q, T, p, N + 1);
     594         [ -  + ]:        259 :     if (DEBUGLEVEL>1) timer_printf(&ti,"frob");
     595                 :        259 :     gel(F, i) = gerepileupto(av2, ZXX_to_FpXC(M, d-1, q, varn(T)));
     596                 :            :   }
     597                 :         56 :   return gerepileupto(av, F);
     598                 :            : }
     599                 :            : 
     600                 :            : GEN
     601                 :         63 : nfhyperellpadicfrobenius(GEN H, GEN T, ulong p, long n)
     602                 :            : {
     603                 :         63 :   pari_sp av = avma;
     604                 :         63 :   GEN M = ZlXQX_hyperellpadicfrobenius(lift(H),T,p,n);
     605                 :         56 :   GEN MM = ZpXQM_prodFrobenius(M, T, utoi(p), n);
     606                 :         56 :   GEN q = zeropadic(utoi(p),n);
     607                 :         56 :   GEN m = gmul(ZXM_to_padic(MM, q), gmodulo(gen_1, T));
     608                 :         56 :   return gerepileupto(av, m);
     609                 :            : }
     610                 :            : 
     611                 :            : static GEN
     612                 :         91 : Flx_genus2charpoly_naive(GEN H, ulong p)
     613                 :            : {
     614                 :         91 :   pari_sp av = avma;
     615                 :         91 :   ulong pi = get_Fl_red(p);
     616         [ +  + ]:         91 :   ulong i, j, p2 = p>>1, D = 2, e = ((p&2UL) == 0) ? -1 : 1;
     617                 :         91 :   long a, b, c = 0;
     618         [ +  + ]:         91 :   if (degpol(H) == 5)
     619                 :         35 :     a = b = 0;
     620                 :            :   else
     621                 :            :   {
     622                 :         56 :     a = krouu(Flx_lead(H), p);
     623                 :         56 :     b = 1;
     624                 :            :   }
     625         [ +  + ]:        105 :   while (krouu(D, p) >= 0) D++;
     626         [ +  + ]:       2296 :   for (i=0; i < p; i++)
     627                 :            :   {
     628                 :       2205 :     ulong v = Flx_eval(H, i, p);
     629                 :       2205 :     a += krouu(v, p);
     630                 :       2205 :     b += !!v;
     631         [ +  + ]:      43008 :     for (j=1; j <= p2; j++)
     632                 :            :     {
     633                 :      40803 :       GEN r2 = Flx_Fl2_eval_pre(H, mkvecsmall2(i, j), D, p, pi);
     634                 :      81606 :       c += uel(r2,2) ?
     635         [ +  + ]:      39452 :            (uel(r2,1) ? krouu(Fl2_norm_pre(r2, D, p, pi), p): e)
     636         [ +  + ]:      80255 :          : !!uel(r2,1);
     637                 :      40803 :       avma = av;
     638                 :            :     }
     639                 :            :   }
     640                 :         91 :   return mkvecsmalln(6, 0UL, p*p, a*p, (b+2*c+a*a)>>1, a, 1UL);
     641                 :            : }
     642                 :            : 
     643                 :            : GEN
     644                 :        672 : hyperellcharpoly(GEN H)
     645                 :            : {
     646                 :        672 :   pari_sp av = avma;
     647                 :        672 :   GEN M, R, T=NULL, pp=NULL;
     648                 :        672 :   long d, n, eps = 0;
     649                 :            :   ulong p;
     650 [ +  + ][ +  - ]:        672 :   if (is_vec_t(typ(H)) && lg(H)==3)
     651                 :          7 :     H = gadd(gsqr(gel(H, 2)), gmul2n(gel(H, 1), 2));
     652 [ +  - ][ +  - ]:        672 :   if (typ(H)!=t_POL || !RgX_is_FpXQX(H, &T, &pp) || !pp)
                 [ -  + ]
     653                 :          0 :     pari_err_TYPE("hyperellcharpoly",H);
     654                 :        672 :   p = itou(pp);
     655         [ +  + ]:        672 :   if (!T)
     656                 :            :   {
     657                 :        609 :     H = RgX_to_FpX(H, pp);
     658                 :        609 :     d = degpol(H);
     659 [ +  - ][ +  + ]:        609 :     if (p > 2 && ((d == 5 && p < 3000) || (d == 6 && p < 5500)))
         [ -  + ][ +  + ]
                 [ +  - ]
     660                 :            :     {
     661                 :         98 :       GEN Hp = ZX_to_Flx(H, p);
     662         [ +  + ]:         98 :       if (!Flx_is_squarefree(Hp, p)) is_sing(H, p);
     663                 :         91 :       R = zx_to_ZX(Flx_genus2charpoly_naive(Hp, p));
     664                 :         91 :       return gerepileupto(av, R);
     665                 :            :     }
     666         [ +  + ]:        511 :     n = (d>>1) + 1; eps = odd(d)? 0: Fp_issquare(leading_term(H), pp);
     667                 :        511 :     M = hyperellpadicfrobenius(H, p, n);
     668                 :        511 :     R = centerlift(carberkowitz(M, 0));
     669                 :            :   }
     670                 :            :   else
     671                 :            :   {
     672                 :            :     int fixvar;
     673         [ +  + ]:         63 :     T = typ(T)==t_FFELT? FF_mod(T): RgX_to_FpX(T, pp);
     674                 :         63 :     fixvar = (varncmp(varn(T),varn(H)) <= 0);
     675         [ +  + ]:         63 :     if (fixvar) setvarn(T, fetch_var());
     676                 :         63 :     H = RgX_to_FpXQX(H, T, pp);
     677         [ +  + ]:         63 :     d = degpol(H); eps = odd(d)? 0: Fq_issquare(leading_term(H), T, pp);
     678                 :         63 :     n = ((degpol(T)*d)>>1) + 1;
     679                 :         63 :     M = nfhyperellpadicfrobenius(H, T, p, n);
     680                 :         56 :     R = centerlift(liftpol_shallow(carberkowitz(M, 0)));
     681         [ -  + ]:         56 :     if (fixvar) (void)delete_var();
     682                 :            :   }
     683         [ +  + ]:        567 :   if (!odd(d))
     684                 :            :   {
     685         [ +  + ]:        273 :     GEN q = T ? powuu(p, degpol(T)): pp;
     686         [ +  + ]:        273 :     GEN v, Rx = RgX_div_by_X_x(R, eps? q: negi(q), &v);
     687         [ -  + ]:        273 :     if (signe(v)) pari_err_BUG("hyperellcharpoly");
     688                 :        273 :     return gerepilecopy(av, Rx);
     689                 :            :   }
     690                 :        658 :   return gerepileupto(av, R);
     691                 :            : }

Generated by: LCOV version 1.9