Code coverage tests

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

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

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

LCOV - code coverage report
Current view: top level - basemath - hyperell.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.12.1 lcov report (development 24988-2584e74448) Lines: 489 534 91.6 %
Date: 2020-01-26 05:57:03 Functions: 42 43 97.7 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Copyright (C) 2014  The PARI group.
       2             : 
       3             : This file is part of the PARI/GP package.
       4             : 
       5             : PARI/GP is free software; you can redistribute it and/or modify it under the
       6             : terms of the GNU General Public License as published by the Free Software
       7             : Foundation. It is distributed in the hope that it will be useful, but WITHOUT
       8             : ANY WARRANTY WHATSOEVER.
       9             : 
      10             : Check the License for details. You should have received a copy of it, along
      11             : with the package; see the file 'COPYING'. If not, write to the Free Software
      12             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      13             : 
      14             : /********************************************************************/
      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        1764 : get_basis(long p, long d)
      41             : {
      42        1764 :   if (odd(d))
      43         868 :     return p < d-1 ? 3 : 1;
      44             :   else
      45         896 :     return 2*p <= d-2 ? 3 : 1;
      46             : }
      47             : 
      48             : static GEN
      49       20265 : FpXXQ_red(GEN S, GEN T, GEN p)
      50             : {
      51       20265 :   pari_sp av = avma;
      52       20265 :   long i, dS = degpol(S);
      53             :   GEN A, C;
      54       20265 :   if (signe(S)==0) return pol_0(varn(T));
      55       20265 :   A = cgetg(dS+3, t_POL);
      56       20265 :   C = pol_0(varn(T));
      57     1520358 :   for(i=dS; i>0; i--)
      58             :   {
      59     1500093 :     GEN Si = FpX_add(C, gel(S,i+2), p);
      60     1500093 :     GEN R, Q = FpX_divrem(Si, T, p, &R);
      61     1500093 :     gel(A,i+2) = R;
      62     1500093 :     C = Q;
      63             :   }
      64       20265 :   gel(A,2) = FpX_add(C, gel(S,2), p);
      65       20265 :   A[1] = S[1];
      66       20265 :   return gerepilecopy(av, FpXX_renormalize(A,dS+3));
      67             : }
      68             : 
      69             : static GEN
      70        3402 : FpXXQ_sqr(GEN x, GEN T, GEN p)
      71             : {
      72        3402 :   pari_sp av = avma;
      73        3402 :   long n = degpol(T);
      74        3402 :   GEN z = FpX_red(ZXX_sqr_Kronecker(x, n), p);
      75        3402 :   z = Kronecker_to_ZXX(z, n, varn(T));
      76        3402 :   return gerepileupto(av, FpXXQ_red(z, T, p));
      77             : }
      78             : 
      79             : static GEN
      80       16863 : FpXXQ_mul(GEN x, GEN y, GEN T, GEN p)
      81             : {
      82       16863 :   pari_sp av = avma;
      83       16863 :   long n = degpol(T);
      84       16863 :   GEN z = FpX_red(ZXX_mul_Kronecker(x, y, n), p);
      85       16863 :   z = Kronecker_to_ZXX(z, n, varn(T));
      86       16863 :   return gerepileupto(av, FpXXQ_red(z, T, p));
      87             : }
      88             : 
      89             : static GEN
      90        1309 : ZpXXQ_invsqrt(GEN S, GEN T, ulong p, long e)
      91             : {
      92        1309 :   pari_sp av = avma, av2;
      93             :   ulong mask;
      94        1309 :   long v = varn(S), n=1;
      95        1309 :   GEN a = pol_1(v);
      96        1309 :   if (e <= 1) return gerepilecopy(av, a);
      97        1309 :   mask = quadratic_prec_mask(e);
      98        1309 :   av2 = avma;
      99        5985 :   for (;mask>1;)
     100             :   {
     101             :     GEN q, q2, q22, f, fq, afq;
     102        3367 :     long n2 = n;
     103        3367 :     n<<=1; if (mask & 1) n--;
     104        3367 :     mask >>= 1;
     105        3367 :     q = powuu(p,n); q2 = powuu(p,n2);
     106        3367 :     f = RgX_sub(FpXXQ_mul(FpXX_red(S, q), FpXXQ_sqr(a, T, q), T, q), pol_1(v));
     107        3367 :     fq = ZXX_Z_divexact(f, q2);
     108        3367 :     q22 = shifti(addiu(q2,1),-1);
     109        3367 :     afq = FpXX_Fp_mul(FpXXQ_mul(a, fq, T, q2), q22, q2);
     110        3367 :     a = RgX_sub(a, ZXX_Z_mul(afq, q2));
     111        3367 :     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        1309 :   return gerepileupto(av, a);
     118             : }
     119             : 
     120             : static GEN
     121     1028986 : 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        1309 : get_UV(GEN *U, GEN *V, GEN T, ulong p, long e)
     131             : {
     132        1309 :   GEN q = powuu(p,e), d;
     133        1309 :   GEN dT = FpX_deriv(T, q);
     134        1309 :   GEN R = polresultantext(T, dT);
     135        1309 :   long v = varn(T);
     136        1309 :   if (dvdiu(gel(R,3),p)) is_sing(T, p);
     137        1309 :   d = Fp_inv(gel(R,3), q);
     138        1309 :   *U = FpX_Fp_mul(FpX_red(to_ZX(gel(R,1),v),q),d,q);
     139        1309 :   *V = FpX_Fp_mul(FpX_red(to_ZX(gel(R,2),v),q),d,q);
     140        1309 : }
     141             : 
     142             : static GEN
     143      133847 : frac_to_Fp(GEN a, GEN b, GEN p)
     144             : {
     145      133847 :   GEN d = gcdii(a, b);
     146      133847 :   return Fp_div(diviiexact(a, d), diviiexact(b, d), p);
     147             : }
     148             : 
     149             : static GEN
     150       10094 : ZpXXQ_frob(GEN S, GEN U, GEN V, long k, GEN T, ulong p, long e)
     151             : {
     152       10094 :   pari_sp av = avma, av2;
     153       10094 :   long i, pr = degpol(S), dT = degpol(T), vT = varn(T);
     154       10094 :   GEN q = powuu(p,e);
     155       10094 :   GEN Tp = FpX_deriv(T, q), Tp1 = RgX_shift_shallow(Tp, 1);
     156       10094 :   GEN M = to_ZX(gel(S,pr+2),vT) , R;
     157       10094 :   av2 = avma;
     158      987847 :   for(i = pr-1; i>=k; i--)
     159             :   {
     160             :     GEN A, B, H, Bc;
     161             :     ulong v, r;
     162      977753 :     H = FpX_divrem(FpX_mul(V,M,q), T, q, &B);
     163      977753 :     A = FpX_add(FpX_mul(U,M,q), FpX_mul(H, Tp, q),q);
     164      977753 :     v = u_lvalrem(2*i+1,p,&r);
     165      977753 :     Bc = ZX_deriv(B);
     166      977753 :     Bc = FpX_Fp_mul(ZX_Z_divexact(Bc,powuu(p,v)),Fp_divu(gen_2, r, q), q);
     167      977753 :     M = FpX_add(to_ZX(gel(S,i+2),vT), FpX_add(A, Bc, q), q);
     168      977753 :     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       10094 :   if (degpol(M)<dT-1)
     175        5488 :     return gerepileupto(av, M);
     176        4606 :   R = RgX_shift_shallow(M,dT-degpol(M)-2);
     177        4606 :   av2 = avma;
     178      237629 :   for(i = degpol(M)-dT+2; i>=1; i--)
     179             :   {
     180             :     GEN B, c;
     181      233023 :     R = RgX_shift_shallow(R, 1);
     182      233023 :     gel(R,2) = gel(M, i+1);
     183      233023 :     if (degpol(R) < dT) continue;
     184      130935 :     B = FpX_add(FpX_mulu(T, 2*i, q), Tp1, q);
     185      130935 :     c = frac_to_Fp(leading_coeff(R), leading_coeff(B), q);
     186      130935 :     R = FpX_sub(R, FpX_Fp_mul(B, c, q), q);
     187      130935 :     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        4606 :   if (degpol(R)==dT-1)
     194             :   {
     195        2912 :     GEN c = frac_to_Fp(leading_coeff(R), leading_coeff(Tp), q);
     196        2912 :     R = FpX_sub(R, FpX_Fp_mul(Tp, c, q), q);
     197        2912 :     return gerepileupto(av, R);
     198             :   } else
     199        1694 :     return gerepilecopy(av, R);
     200             : }
     201             : 
     202             : static GEN
     203       12026 : revdigits(GEN v)
     204             : {
     205       12026 :   long i, n = lg(v)-1;
     206       12026 :   GEN w = cgetg(n+2, t_POL);
     207       12026 :   w[1] = evalsigne(1)|evalvarn(0);
     208      168784 :   for (i=0; i<n; i++)
     209      156758 :     gel(w,i+2) = gel(v,n-i);
     210       12026 :   return FpXX_renormalize(w, n+2);
     211             : }
     212             : 
     213             : static GEN
     214       10094 : diff_red(GEN s, GEN A, long m, GEN T, GEN p)
     215             : {
     216       10094 :   long v, n, vT = varn(T);
     217             :   GEN Q, sQ, qS;
     218             :   pari_timer ti;
     219       10094 :   if (DEBUGLEVEL>1) timer_start(&ti);
     220       10094 :   Q = revdigits(FpX_digits(A,T,p));
     221       10094 :   n = degpol(Q);
     222       10094 :   if (DEBUGLEVEL>1) timer_printf(&ti,"reddigits");
     223       10094 :   sQ = FpXXQ_mul(s,Q,T,p);
     224       10094 :   if (DEBUGLEVEL>1) timer_printf(&ti,"redmul");
     225       10094 :   qS = RgX_shift_shallow(sQ,m-n);
     226       10094 :   v = ZX_val(sQ);
     227       10094 :   if (n > m + v)
     228             :   {
     229        4564 :     long i, l = n-m-v;
     230        4564 :     GEN rS = cgetg(l+1,t_VEC);
     231       29190 :     for (i = l-1; i >=0 ; i--)
     232       24626 :       gel(rS,i+1) = to_ZX(gel(sQ, 1+v+l-i), vT);
     233        4564 :     rS = FpXV_FpX_fromdigits(rS,T,p);
     234        4564 :     gel(qS,2) = FpX_add(FpX_mul(rS, T, p), gel(qS, 2), p);
     235        4564 :     if (DEBUGLEVEL>1) timer_printf(&ti,"redadd");
     236             :   }
     237       10094 :   return qS;
     238             : }
     239             : 
     240             : static GEN
     241       10094 : ZC_to_padic(GEN C, GEN q)
     242             : {
     243       10094 :   long i, l = lg(C);
     244       10094 :   GEN V = cgetg(l,t_COL);
     245      102914 :   for(i = 1; i < l; i++)
     246       92820 :     gel(V, i) = gadd(gel(C, i), q);
     247       10094 :   return V;
     248             : }
     249             : 
     250             : static GEN
     251        1309 : ZM_to_padic(GEN M, GEN q)
     252             : {
     253        1309 :   long i, l = lg(M);
     254        1309 :   GEN V = cgetg(l,t_MAT);
     255       11403 :   for(i = 1; i < l; i++)
     256       10094 :     gel(V, i) = ZC_to_padic(gel(M, i), q);
     257        1309 :   return V;
     258             : }
     259             : 
     260             : static GEN
     261        1743 : ZX_to_padic(GEN P, GEN q)
     262             : {
     263        1743 :   long i, l = lg(P);
     264        1743 :   GEN Q = cgetg(l, t_POL);
     265        1743 :   Q[1] = P[1];
     266        5992 :   for (i=2; i<l ;i++)
     267        4249 :     gel(Q,i) = gadd(gel(P,i), q);
     268        1743 :   return normalizepol(Q);
     269             : }
     270             : 
     271             : static GEN
     272         469 : ZXC_to_padic(GEN x, GEN q)
     273         469 : { pari_APPLY_type(t_COL, ZX_to_padic(gel(x, i), q)) }
     274             : 
     275             : static GEN
     276         147 : ZXM_to_padic(GEN x, GEN q)
     277         147 : { pari_APPLY_same(ZXC_to_padic(gel(x, i), q)) }
     278             : 
     279             : static GEN
     280        1309 : ZlX_hyperellpadicfrobenius(GEN H, ulong p, long n)
     281             : {
     282        1309 :   pari_sp av = avma;
     283             :   long k, N, i, d;
     284             :   GEN F, s, Q, pN1, U, V;
     285             :   pari_timer ti;
     286        1309 :   if (typ(H) != t_POL) pari_err_TYPE("hyperellpadicfrobenius",H);
     287        1309 :   if (p == 2) is_sing(H, 2);
     288        1309 :   d = degpol(H);
     289        1309 :   if (d <= 0)
     290           0 :     pari_err_CONSTPOL("hyperellpadicfrobenius");
     291        1309 :   if (n < 1)
     292           0 :     pari_err_DOMAIN("hyperellpadicfrobenius","n","<", gen_1, utoi(n));
     293        1309 :   k = get_basis(p, d);
     294        1309 :   N = n + ulogint(2*n, p) + 1;
     295        1309 :   pN1 = powuu(p,N+1);
     296        1309 :   Q = RgX_to_FpX(H, pN1);
     297        1309 :   if (dvdiu(leading_coeff(Q),p)) is_sing(H, p);
     298        1309 :   setvarn(Q,1);
     299        1309 :   if (DEBUGLEVEL>1) timer_start(&ti);
     300        1309 :   s = revdigits(FpX_digits(RgX_inflate(Q, p), Q, pN1));
     301        1309 :   if (DEBUGLEVEL>1) timer_printf(&ti,"s1");
     302        1309 :   s = ZpXXQ_invsqrt(s, Q, p, N);
     303        1309 :   if (k==3)
     304          35 :     s = FpXXQ_mul(s, FpXXQ_sqr(s, Q, pN1), Q, pN1);
     305        1309 :   if (DEBUGLEVEL>1) timer_printf(&ti,"invsqrt");
     306        1309 :   get_UV(&U, &V, Q, p, N+1);
     307        1309 :   F = cgetg(d, t_MAT);
     308       11403 :   for (i = 1; i < d; i++)
     309             :   {
     310       10094 :     pari_sp av2 = avma;
     311             :     GEN M, D;
     312       10094 :     D = diff_red(s, monomial(utoi(p),p*i-1,1),(k*p-1)>>1, Q, pN1);
     313       10094 :     if (DEBUGLEVEL>1) timer_printf(&ti,"red");
     314       10094 :     M = ZpXXQ_frob(D, U, V, (k-1)>>1, Q, p, N + 1);
     315       10094 :     if (DEBUGLEVEL>1) timer_printf(&ti,"frob");
     316       10094 :     gel(F, i) = gerepilecopy(av2, RgX_to_RgC(M, d-1));
     317             :   }
     318        1309 :   return gerepileupto(av, F);
     319             : }
     320             : 
     321             : GEN
     322        1309 : hyperellpadicfrobenius(GEN H, ulong p, long n)
     323             : {
     324        1309 :   pari_sp av = avma;
     325        1309 :   GEN M = ZlX_hyperellpadicfrobenius(H, p, n);
     326        1309 :   GEN q = zeropadic(utoi(p),n);
     327        1309 :   return gerepileupto(av, ZM_to_padic(M, q));
     328             : }
     329             : 
     330             : INLINE GEN
     331        2226 : FpXXX_renormalize(GEN x, long lx)  { return ZXX_renormalize(x,lx); }
     332             : 
     333             : static GEN
     334        1806 : ZpXQXXQ_red(GEN F, GEN S, GEN T, GEN q, GEN p, long e)
     335             : {
     336        1806 :   pari_sp av = avma;
     337        1806 :   long i, dF = degpol(F);
     338             :   GEN A, C;
     339        1806 :   if (signe(F)==0) return pol_0(varn(S));
     340        1785 :   A = cgetg(dF+3, t_POL);
     341        1785 :   C = pol_0(varn(S));
     342       96383 :   for(i=dF; i>0; i--)
     343             :   {
     344       94598 :     GEN Fi = FpXX_add(C, gel(F,i+2), q);
     345       94598 :     GEN R, Q = ZpXQX_divrem(Fi, S, T, q, p, e, &R);
     346       94598 :     gel(A,i+2) = R;
     347       94598 :     C = Q;
     348             :   }
     349        1785 :   gel(A,2) = FpXX_add(C, gel(F,2), q);
     350        1785 :   A[1] = F[1];
     351        1785 :   return gerepilecopy(av, FpXXX_renormalize(A,dF+3));
     352             : }
     353             : 
     354             : static GEN
     355         448 : ZpXQXXQ_sqr(GEN x, GEN S, GEN T, GEN q, GEN p, long e)
     356             : {
     357         448 :   pari_sp av = avma;
     358             :   GEN z, kx;
     359         448 :   long n = degpol(S);
     360         448 :   kx = ZXX_to_Kronecker(x, n);
     361         448 :   z = Kronecker_to_ZXX(FpXQX_sqr(kx, T, q), n, varn(S));
     362         448 :   return gerepileupto(av, ZpXQXXQ_red(z, S, T, q, p, e));
     363             : }
     364             : 
     365             : static GEN
     366        1358 : ZpXQXXQ_mul(GEN x, GEN y, GEN S, GEN T, GEN q, GEN p, long e)
     367             : {
     368        1358 :   pari_sp av = avma;
     369             :   GEN z, kx, ky;
     370        1358 :   long n = degpol(S);
     371        1358 :   kx = ZXX_to_Kronecker(x, n);
     372        1358 :   ky = ZXX_to_Kronecker(y, n);
     373        1358 :   z = Kronecker_to_ZXX(FpXQX_mul(ky, kx, T, q), n, varn(S));
     374        1358 :   return gerepileupto(av, ZpXQXXQ_red(z, S, T, q, p, e));
     375             : }
     376             : 
     377             : static GEN
     378         441 : FpXXX_red(GEN z, GEN p)
     379             : {
     380             :   GEN res;
     381         441 :   long i, l = lg(z);
     382         441 :   res = cgetg(l,t_POL); res[1] = z[1];
     383       17367 :   for (i=2; i<l; i++)
     384             :   {
     385       16926 :     GEN zi = gel(z,i);
     386       16926 :     if (typ(zi)==t_INT)
     387           0 :       gel(res,i) = modii(zi,p);
     388             :     else
     389       16926 :      gel(res,i) = FpXX_red(zi,p);
     390             :   }
     391         441 :   return FpXXX_renormalize(res,lg(res));
     392             : }
     393             : 
     394             : static GEN
     395         441 : FpXXX_Fp_mul(GEN z, GEN a, GEN p)
     396             : {
     397         441 :   return FpXXX_red(RgX_Rg_mul(z, a), p);
     398             : }
     399             : 
     400             : static GEN
     401         154 : ZpXQXXQ_invsqrt(GEN F, GEN S, GEN T, ulong p, long e)
     402             : {
     403         154 :   pari_sp av = avma, av2, av3;
     404             :   ulong mask;
     405         154 :   long v = varn(F), n=1;
     406             :   pari_timer ti;
     407         154 :   GEN a = pol_1(v), pp = utoi(p);
     408         154 :   if (DEBUGLEVEL>1) timer_start(&ti);
     409         154 :   if (e <= 1) return gerepilecopy(av, a);
     410         154 :   mask = quadratic_prec_mask(e);
     411         154 :   av2 = avma;
     412         749 :   for (;mask>1;)
     413             :   {
     414             :     GEN q, q2, q22, f, fq, afq;
     415         441 :     long n2 = n;
     416         441 :     n<<=1; if (mask & 1) n--;
     417         441 :     mask >>= 1;
     418         441 :     q = powuu(p,n); q2 = powuu(p,n2);
     419         441 :     av3 = avma;
     420         441 :     f = RgX_sub(ZpXQXXQ_mul(F, ZpXQXXQ_sqr(a, S, T, q, pp, n), S, T, q, pp, n), pol_1(v));
     421         441 :     fq = gerepileupto(av3, RgX_Rg_divexact(f, q2));
     422         441 :     q22 = shifti(addiu(q2,1),-1);
     423         441 :     afq = FpXXX_Fp_mul(ZpXQXXQ_mul(a, fq, S, T, q2, pp, n2), q22, q2);
     424         441 :     a = RgX_sub(a, RgX_Rg_mul(afq, q2));
     425         441 :     if (gc_needed(av2,1))
     426             :     {
     427           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXQXXQ_invsqrt, e = %ld", n);
     428           0 :       a = gerepileupto(av2, a);
     429             :     }
     430             :   }
     431         154 :   return gerepileupto(av, a);
     432             : }
     433             : 
     434             : static GEN
     435        6573 : frac_to_Fq(GEN a, GEN b, GEN T, GEN q, GEN p, long e)
     436             : {
     437        6573 :   GEN d = gcdii(ZX_content(a), ZX_content(b));
     438        6573 :   return ZpXQ_div(ZX_Z_divexact(a, d), ZX_Z_divexact(b, d), T, q, p, e);
     439             : }
     440             : 
     441             : static GEN
     442         469 : ZpXQXXQ_frob(GEN F, GEN U, GEN V, long k, GEN S, GEN T, ulong p, long e)
     443             : {
     444         469 :   pari_sp av = avma, av2;
     445         469 :   long i, pr = degpol(F), dS = degpol(S), v = varn(T);
     446         469 :   GEN q = powuu(p,e), pp = utoi(p);
     447         469 :   GEN Sp = RgX_deriv(S), Sp1 = RgX_shift_shallow(Sp, 1);
     448         469 :   GEN M = gel(F,pr+2), R;
     449         469 :   av2 = avma;
     450       52311 :   for(i = pr-1; i>=k; i--)
     451             :   {
     452             :     GEN A, B, H, Bc;
     453             :     ulong v, r;
     454       51842 :     H = ZpXQX_divrem(FpXQX_mul(V, M, T, q), S, T, q, utoi(p), e, &B);
     455       51842 :     A = FpXX_add(FpXQX_mul(U, M, T, q), FpXQX_mul(H, Sp, T, q),q);
     456       51842 :     v = u_lvalrem(2*i+1,p,&r);
     457       51842 :     Bc = RgX_deriv(B);
     458       51842 :     Bc = FpXX_Fp_mul(ZXX_Z_divexact(Bc,powuu(p,v)), Fp_divu(gen_2, r, q), q);
     459       51842 :     M = FpXX_add(gel(F,i+2), FpXX_add(A, Bc, q), q);
     460       51842 :     if (gc_needed(av2,1))
     461             :     {
     462           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXQXXQ_frob, step 1, i = %ld", i);
     463           0 :       M = gerepileupto(av2, M);
     464             :     }
     465             :   }
     466         469 :   if (degpol(M)<dS-1)
     467         266 :     return gerepileupto(av, M);
     468         203 :   R = RgX_shift_shallow(M,dS-degpol(M)-2);
     469         203 :   av2 = avma;
     470        7175 :   for(i = degpol(M)-dS+2; i>=1; i--)
     471             :   {
     472             :     GEN B, c;
     473        6972 :     R = RgX_shift_shallow(R, 1);
     474        6972 :     gel(R,2) = gel(M, i+1);
     475        6972 :     if (degpol(R) < dS) continue;
     476        6412 :     B = FpXX_add(FpXX_mulu(S, 2*i, q), Sp1, q);
     477        6412 :     c = frac_to_Fq(to_ZX(leading_coeff(R),v), to_ZX(leading_coeff(B),v), T, q, pp, e);
     478        6412 :     R = FpXX_sub(R, FpXQX_FpXQ_mul(B, c, T, q), q);
     479        6412 :     if (gc_needed(av2,1))
     480             :     {
     481           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXXQ_frob, step 2, i = %ld", i);
     482           0 :       R = gerepileupto(av2, R);
     483             :     }
     484             :   }
     485         203 :   if (degpol(R)==dS-1)
     486             :   {
     487         161 :     GEN c = frac_to_Fq(to_ZX(leading_coeff(R),v), to_ZX(leading_coeff(Sp),v), T, q, pp, e);
     488         161 :     R = FpXX_sub(R, FpXQX_FpXQ_mul(Sp, c, T, q), q);
     489         161 :     return gerepileupto(av, R);
     490             :   } else
     491          42 :     return gerepilecopy(av, R);
     492             : }
     493             : 
     494             : 
     495             : static GEN
     496         469 : Fq_diff_red(GEN s, GEN A, long m, GEN S, GEN T, GEN q, GEN p, long e)
     497             : {
     498             :   long v, n;
     499             :   GEN Q, sQ, qS;
     500             :   pari_timer ti;
     501         469 :   if (DEBUGLEVEL>1) timer_start(&ti);
     502         469 :   Q = revdigits(ZpXQX_digits(A, S, T, q, p, e));
     503         469 :   n = degpol(Q);
     504         469 :   if (DEBUGLEVEL>1) timer_printf(&ti,"reddigits");
     505         469 :   sQ = ZpXQXXQ_mul(s, Q, S, T, q, p, e);
     506         469 :   if (DEBUGLEVEL>1) timer_printf(&ti,"redmul");
     507         469 :   qS = RgX_shift_shallow(sQ,m-n);
     508         469 :   v = ZX_val(sQ);
     509         469 :   if (n > m + v)
     510             :   {
     511         189 :     long i, l = n-m-v;
     512         189 :     GEN rS = cgetg(l+1,t_VEC);
     513        1547 :     for (i = l-1; i >=0 ; i--)
     514        1358 :       gel(rS,i+1) = gel(sQ, 1+v+l-i);
     515         189 :     rS = FpXQXV_FpXQX_fromdigits(rS, S, T, q);
     516         189 :     gel(qS,2) = FpXX_add(FpXQX_mul(rS, S, T, q), gel(qS, 2), q);
     517         189 :     if (DEBUGLEVEL>1) timer_printf(&ti,"redadd");
     518             :   }
     519         469 :   return qS;
     520             : }
     521             : 
     522             : static void
     523         154 : Fq_get_UV(GEN *U, GEN *V, GEN S, GEN T, ulong p, long e)
     524             : {
     525         154 :   GEN q = powuu(p, e), d;
     526         154 :   GEN dS = RgX_deriv(S);
     527         154 :   GEN R  = polresultantext(S, dS), C;
     528         154 :   long v = varn(S);
     529         154 :   if (signe(FpX_red(to_ZX(gel(R,3),v),utoi(p)))==0) is_sing(S, p);
     530         147 :   C = FpXQ_red(to_ZX(gel(R, 3),v), T, q);
     531         147 :   d = ZpXQ_inv(C, T, utoi(p), e);
     532         147 :   *U = FpXQX_FpXQ_mul(FpXQX_red(to_ZX(gel(R,1),v),T,q),d,T,q);
     533         147 :   *V = FpXQX_FpXQ_mul(FpXQX_red(to_ZX(gel(R,2),v),T,q),d,T,q);
     534         147 : }
     535             : 
     536             : static GEN
     537         469 : ZXX_to_FpXC(GEN x, long N, GEN p, long v)
     538             : {
     539             :   long i, l;
     540             :   GEN z;
     541         469 :   l = lg(x)-1; x++;
     542         469 :   if (l > N+1) l = N+1; /* truncate higher degree terms */
     543         469 :   z = cgetg(N+1,t_COL);
     544        2170 :   for (i=1; i<l ; i++)
     545             :   {
     546        1701 :     GEN xi = gel(x, i);
     547        1701 :     gel(z,i) = typ(xi)==t_INT? scalarpol(Fp_red(xi, p), v): FpX_red(xi, p);
     548             :   }
     549         511 :   for (   ; i<=N ; i++)
     550          42 :     gel(z,i) = pol_0(v);
     551         469 :   return z;
     552             : }
     553             : 
     554             : GEN
     555         154 : ZlXQX_hyperellpadicfrobenius(GEN H, GEN T, ulong p, long n)
     556             : {
     557         154 :   pari_sp av = avma;
     558             :   long k, N, i, d, N1;
     559             :   GEN xp, F, s, q, Q, pN1, U, V, pp;
     560             :   pari_timer ti;
     561         154 :   if (typ(H) != t_POL) pari_err_TYPE("hyperellpadicfrobenius",H);
     562         154 :   if (p == 2) is_sing(H, 2);
     563         154 :   d = degpol(H);
     564         154 :   if (d <= 0)
     565           0 :     pari_err_CONSTPOL("hyperellpadicfrobenius");
     566         154 :   if (n < 1)
     567           0 :     pari_err_DOMAIN("hyperellpadicfrobenius","n","<", gen_1, utoi(n));
     568         154 :   k = get_basis(p, d); pp = utoi(p);
     569         154 :   N = n + ulogint(2*n, p) + 1;
     570         154 :   q = powuu(p,n); N1 = N+1;
     571         154 :   pN1 = powuu(p,N1); T = FpX_get_red(T, pN1);
     572         154 :   Q = RgX_to_FqX(H, T, pN1);
     573         154 :   if (signe(FpX_red(to_ZX(leading_coeff(Q),varn(Q)),pp))==0) is_sing(H, p);
     574         154 :   if (DEBUGLEVEL>1) timer_start(&ti);
     575         154 :   xp = ZpX_Frobenius(T, pp, N1);
     576         154 :   s = RgX_inflate(FpXY_FpXQ_evalx(Q, xp, T, pN1), p);
     577         154 :   s = revdigits(ZpXQX_digits(s, Q, T, pN1, pp, N1));
     578         154 :   if (DEBUGLEVEL>1) timer_printf(&ti,"s1");
     579         154 :   s = ZpXQXXQ_invsqrt(s, Q, T, p, N);
     580         154 :   if (k==3)
     581           7 :     s = ZpXQXXQ_mul(s, ZpXQXXQ_sqr(s, Q, T, pN1, pp, N1), Q, T, pN1, pp, N1);
     582         154 :   if (DEBUGLEVEL>1) timer_printf(&ti,"invsqrt");
     583         154 :   Fq_get_UV(&U, &V, Q, T, p, N+1);
     584         147 :   if (DEBUGLEVEL>1) timer_printf(&ti,"get_UV");
     585         147 :   F = cgetg(d, t_MAT);
     586         616 :   for (i = 1; i < d; i++)
     587             :   {
     588         469 :     pari_sp av2 = avma;
     589             :     GEN M, D;
     590         469 :     D = Fq_diff_red(s, monomial(pp,p*i-1,1),(k*p-1)>>1, Q, T, pN1, pp, N1);
     591         469 :     if (DEBUGLEVEL>1) timer_printf(&ti,"red");
     592         469 :     M = ZpXQXXQ_frob(D, U, V, (k - 1)>>1, Q, T, p, N1);
     593         469 :     if (DEBUGLEVEL>1) timer_printf(&ti,"frob");
     594         469 :     gel(F, i) = gerepileupto(av2, ZXX_to_FpXC(M, d-1, q, varn(T)));
     595             :   }
     596         147 :   return gerepileupto(av, F);
     597             : }
     598             : 
     599             : GEN
     600         154 : nfhyperellpadicfrobenius(GEN H, GEN T, ulong p, long n)
     601             : {
     602         154 :   pari_sp av = avma;
     603         154 :   GEN M = ZlXQX_hyperellpadicfrobenius(lift_shallow(H),T,p,n);
     604         147 :   GEN MM = ZpXQM_prodFrobenius(M, T, utoi(p), n);
     605         147 :   GEN q = zeropadic(utoi(p),n);
     606         147 :   GEN m = gmul(ZXM_to_padic(MM, q), gmodulo(gen_1, T));
     607         147 :   return gerepileupto(av, m);
     608             : }
     609             : 
     610             : GEN
     611         595 : hyperellpadicfrobenius0(GEN H, GEN Tp, long n)
     612             : {
     613             :   GEN T, p;
     614         595 :   if (!ff_parse_Tp(Tp, &T,&p,0)) pari_err_TYPE("hyperellpadicfrobenius", Tp);
     615         595 :   if (lgefint(p) > 3) pari_err_IMPL("large prime in hyperellpadicfrobenius");
     616         602 :   return T? nfhyperellpadicfrobenius(H, T, itou(p), n)
     617         602 :           : hyperellpadicfrobenius(H, itou(p), n);
     618             : }
     619             : 
     620             : static GEN
     621          77 : F2x_genus2charpoly_naive(GEN P, GEN Q)
     622             : {
     623          77 :   long a, b = 1, c = 0;
     624          77 :   GEN T = mkvecsmall2(P[1], 7);
     625          77 :   GEN PT = F2x_rem(P, T), QT = F2x_rem(Q, T);
     626          77 :   long q0 = F2x_eval(Q, 0), q1 = F2x_eval(Q, 1);
     627          77 :   long dP = F2x_degree(P), dQ = F2x_degree(Q);
     628          77 :   a= dQ<3 ? 0: dP<=5 ? 1: -1;
     629          77 :   a += (q0? F2x_eval(P, 0)? -1: 1: 0) + (q1? F2x_eval(P, 1)? -1: 1: 0);
     630          77 :   b += q0 + q1;
     631          77 :   if (lgpol(QT))
     632          63 :     c = (F2xq_trace(F2xq_div(PT, F2xq_sqr(QT, T), T), T)==0 ? 1: -1);
     633          77 :   return mkvecsmalln(6, 0UL, 4, 2*a, (b+2*c+a*a)>>1, a, 1UL);
     634             : }
     635             : 
     636             : static GEN
     637         217 : Flx_difftable(GEN P, ulong p)
     638             : {
     639         217 :   long i, n = degpol(P);
     640         217 :   GEN V = cgetg(n+2, t_VEC);
     641         217 :   gel(V, n+1) = P;
     642        1484 :   for(i = n; i >= 1; i--)
     643        1267 :     gel(V, i) = Flx_diff1(gel(V, i+1), p);
     644         217 :   return V;
     645             : }
     646             : 
     647             : static GEN
     648        1519 : FlxV_Fl2_eval_pre(GEN V, GEN x, ulong D, ulong p, ulong pi)
     649             : {
     650        1519 :   long i, n = lg(V)-1;
     651        1519 :   GEN r = cgetg(n+1, t_VEC);
     652       11627 :   for (i = 1; i <= n; i++)
     653       10108 :     gel(r, i) = Flx_Fl2_eval_pre(gel(V, i), x, D, p, pi);
     654        1519 :   return r;
     655             : }
     656             : 
     657             : static GEN
     658       44478 : Fl2V_next(GEN V, ulong p)
     659             : {
     660       44478 :   long i, n = lg(V)-1;
     661       44478 :   GEN r = cgetg(n+1, t_VEC);
     662       44478 :   gel(r, 1) = gel(V, 1);
     663      285516 :   for (i = 2; i <= n; i++)
     664      241038 :     gel(r, i) = Flv_add(gel(V, i), gel(V, i-1), p);
     665       44478 :   return r;
     666             : }
     667             : 
     668             : static GEN
     669         217 : Flx_genus2charpoly_naive(GEN H, ulong p)
     670             : {
     671         217 :   pari_sp av = avma, av2;
     672         217 :   ulong pi = get_Fl_red(p);
     673         217 :   ulong i, j, p2 = p>>1, D = 2, e = ((p&2UL) == 0) ? -1 : 1;
     674         217 :   long a, b, c = 0, n = degpol(H);
     675         217 :   GEN t, k = const_vecsmall(p, -1);
     676         217 :   k[1] = 0;
     677         217 :   for (i=1, j=1; i < p; i += 2, j = Fl_add(j, i, p)) k[j+1] = 1;
     678         217 :   while (k[1+D] >= 0) D++;
     679         217 :   b = n == 5 ? 0 : 1;
     680         217 :   a = b ? k[1+Flx_lead(H)]: 0;
     681         217 :   t = Flx_difftable(H, p);
     682         217 :   av2 = avma;
     683        3472 :   for (i=0; i < p; i++)
     684             :   {
     685        3255 :     ulong v = Flx_eval(H, i, p);
     686        3255 :     a += k[1+v];
     687        3255 :     b += !!v;
     688             :   }
     689        1736 :   for (j=1; j <= p2; j++)
     690             :   {
     691        1519 :     GEN V = FlxV_Fl2_eval_pre(t, mkvecsmall2(0, j), D, p, pi);
     692       45997 :     for (i=0;; i++)
     693       44478 :     {
     694       45997 :       GEN r2 = gel(V, n+1);
     695       91994 :       c += uel(r2,2) ?
     696       43764 :         (uel(r2,1) ? uel(k,1+Fl2_norm_pre(r2, D, p, pi)): e)
     697       89761 :          : !!uel(r2,1);
     698       45997 :       if (i == p-1) break;
     699       44478 :       V = Fl2V_next(V, p);
     700             :     }
     701        1519 :     set_avma(av2);
     702             :   }
     703         217 :   set_avma(av);
     704         217 :   return mkvecsmalln(6, 0UL, p*p, a*p, (b+2*c+a*a)>>1, a, 1UL);
     705             : }
     706             : 
     707             : static GEN
     708         679 : charpoly_funceq(GEN P, GEN q)
     709             : {
     710         679 :   long i, l, g = degpol(P)>>1;
     711         679 :   GEN Q = cgetg_copy(P, &l);
     712         679 :   Q[1] = P[1];
     713        3843 :   for (i=0; i<=g; i++)
     714        3164 :     gel(Q, i+2) = mulii(gel(P, 2*g-i+2), powiu(q, g-i));
     715        3164 :   for (; i<=2*g; i++)
     716        2485 :     gel(Q, i+2) = icopy(gel(P, i+2));
     717         679 :   return Q;
     718             : }
     719             : 
     720             : static long
     721         686 : hyperell_Weil_bound(GEN q, ulong g, GEN p)
     722             : {
     723         686 :   pari_sp av = avma;
     724         686 :   GEN w = mulii(binomialuu(2*g,g),sqrtint(shifti(powiu(q, g),2)));
     725         686 :   return gc_long(av, logint(w,p) + 1);
     726             : }
     727             : 
     728             : GEN
     729         987 : hyperellcharpoly(GEN PQ)
     730             : {
     731         987 :   pari_sp av = avma;
     732         987 :   GEN H, M, R, T=NULL, pp=NULL, q;
     733         987 :   long d, n, eps = 0;
     734             :   ulong p;
     735         987 :   if (is_vec_t(typ(PQ)) && lg(PQ)==3)
     736          84 :     H = gadd(gsqr(gel(PQ, 2)), gmul2n(gel(PQ, 1), 2));
     737             :   else
     738         903 :     H = PQ;
     739         987 :   if (typ(H)!=t_POL || !RgX_is_FpXQX(H, &T, &pp) || !pp)
     740           0 :     pari_err_TYPE("hyperellcharpoly",H);
     741         987 :   p = itou(pp);
     742         987 :   if (!T)
     743             :   {
     744         840 :     if (p==2 && is_vec_t(typ(PQ)))
     745             :     {
     746          77 :       long dP, dQ, v = varn(H);
     747          77 :       GEN P = gel(PQ,1), Q = gel(PQ,2);
     748          77 :       if (typ(P)!=t_POL)  P = scalarpol(P, v);
     749          77 :       if (typ(Q)!=t_POL)  Q = scalarpol(Q, v);
     750          77 :       dP = degpol(P); dQ = degpol(Q);
     751          77 :       if (dP<=6 && dQ <=3 && (dQ==3 || dP>=5))
     752             :       {
     753          77 :         GEN P2 = RgX_to_F2x(P), Q2 = RgX_to_F2x(Q);
     754          77 :         GEN D = F2x_add(F2x_mul(P2, F2x_sqr(F2x_deriv(Q2))), F2x_sqr(F2x_deriv(P2)));
     755          77 :         if (F2x_degree(F2x_gcd(D, Q2))) is_sing(PQ, 2);
     756          77 :         if (dP==6 && dQ<3 && F2x_coeff(P2,5)==F2x_coeff(Q2,2))
     757           0 :           is_sing(PQ, 2); /* The curve is singular at infinity */
     758          77 :         R = zx_to_ZX(F2x_genus2charpoly_naive(P2, Q2));
     759          77 :         return gerepileupto(av, R);
     760             :       }
     761             :     }
     762         763 :     H = RgX_to_FpX(H, pp);
     763         763 :     d = degpol(H);
     764         763 :     if (d <= 0) is_sing(H, p);
     765         763 :     if (p > 2 && ((d == 5 && p < 17500) || (d == 6 && p < 24500)))
     766             :     {
     767         224 :       GEN Hp = ZX_to_Flx(H, p);
     768         224 :       if (!Flx_is_squarefree(Hp, p)) is_sing(H, p);
     769         217 :       R = zx_to_ZX(Flx_genus2charpoly_naive(Hp, p));
     770         217 :       return gerepileupto(av, R);
     771             :     }
     772         539 :     n = hyperell_Weil_bound(pp, (d-1)>>1, pp);
     773         539 :     eps = odd(d)? 0: Fp_issquare(leading_coeff(H), pp);
     774         539 :     M = hyperellpadicfrobenius(H, p, n);
     775         539 :     R = centerlift(carberkowitz(M, 0));
     776         539 :     q = pp;
     777             :   }
     778             :   else
     779             :   {
     780             :     int fixvar;
     781         147 :     T = typ(T)==t_FFELT? FF_mod(T): RgX_to_FpX(T, pp);
     782         147 :     q = powuu(p, degpol(T));
     783         147 :     fixvar = (varncmp(varn(T),varn(H)) <= 0);
     784         147 :     if (fixvar) setvarn(T, fetch_var());
     785         147 :     H = RgX_to_FpXQX(H, T, pp);
     786         147 :     d = degpol(H);
     787         147 :     if (d <= 0) is_sing(H, p);
     788         147 :     eps = odd(d)? 0: Fq_issquare(leading_coeff(H), T, pp);
     789         147 :     n = hyperell_Weil_bound(q, (d-1)>>1, pp);
     790         147 :     M = nfhyperellpadicfrobenius(H, T, p, n);
     791         140 :     R = simplify_shallow(centerlift(liftpol_shallow(carberkowitz(M, 0))));
     792         140 :     if (fixvar) (void)delete_var();
     793             :   }
     794         679 :   if (!odd(d))
     795             :   {
     796         301 :     GEN b = get_basis(p, d) == 3 ? gen_1 : q;
     797         301 :     GEN pn = powuu(p, n);
     798         301 :     R = FpX_div_by_X_x(R, eps? b: negi(b), pn, NULL);
     799         301 :     R = FpX_center_i(R, pn, shifti(pn,-1));
     800             :   }
     801         679 :   R = charpoly_funceq(R, q);
     802         679 :   return gerepilecopy(av, R);
     803             : }
     804             : 
     805             : GEN
     806           0 : hyperell_redsl2(GEN Q)
     807             : {
     808           0 :   pari_sp av = avma;
     809           0 :   long d = degpol(Q), v = varn(Q);
     810           0 :   GEN den, P = Q_primitive_part(Q, &den);
     811           0 :   GEN a = gel(P,d+2), b = gel(P,d+1), c = gel(P, d);
     812             :   GEN q1, q2, q3, D, M, A, B, R;
     813           0 :   q1 = mulis(sqri(a), d);
     814           0 :   q2 = shifti(mulii(a,b), 1);
     815           0 :   q3 = subii(sqri(b),shifti(mulii(a,c), 1));
     816           0 :   D = gcdii(gcdii(q1, q2), q3);
     817           0 :   if (!equali1(D))
     818             :   {
     819           0 :     q1 = diviiexact(q1,D);
     820           0 :     q2 = diviiexact(q2,D);
     821           0 :     q3 = diviiexact(q3,D);
     822             :   }
     823           0 :   D = qfb_disc3(q1, q2, q3);
     824           0 :   if (!signe(D))
     825           0 :     M = mkmat22(gen_1,truedivii(negi(q2),shifti(q1,1)),gen_0,gen_1);
     826           0 :   else if (issquare(D))
     827           0 :     M = mkmat22(gen_1,divii(negi(q2),shifti(q1,1)),gen_0,gen_1);
     828             :   else
     829             :   {
     830           0 :     GEN Q = signe(D) < 0 ? qfi(q1,q2,q3): qfr(q1,q2,q3,real_0(DEFAULTPREC));
     831           0 :     M = gel(qfbredsl2(Q, NULL),2);
     832             :   }
     833           0 :   A = deg1pol(gcoeff(M,1,1),gcoeff(M,1,2),v);
     834           0 :   B = gpowers(deg1pol(gcoeff(M,2,1),gcoeff(M,2,2),v), d);
     835           0 :   R = gel(RgX_homogenous_evalpow(P, A, B),1);
     836           0 :   if (den) R = gmul(R, den);
     837           0 :   return gerepilecopy(av,mkvec2(R,M));
     838             : }

Generated by: LCOV version 1.13