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.18.0 lcov report (development 29685-209b4888d8) Lines: 869 915 95.0 %
Date: 2024-11-05 09:09:42 Functions: 74 75 98.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; either version 2 of the License, or (at your option) any later
       8             : version. It is distributed in the hope that it will be useful, but WITHOUT
       9             : ANY WARRANTY WHATSOEVER.
      10             : 
      11             : Check the License for details. You should have received a copy of it, along
      12             : with the package; see the file 'COPYING'. If not, write to the Free Software
      13             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      14             : 
      15             : /********************************************************************/
      16             : /**                                                                **/
      17             : /**                     HYPERELLIPTIC CURVES                       **/
      18             : /**                                                                **/
      19             : /********************************************************************/
      20             : #include "pari.h"
      21             : #include "paripriv.h"
      22             : 
      23             : #define DEBUGLEVEL DEBUGLEVEL_hyperell
      24             : 
      25             : /* Implementation of Kedlaya Algorithm for counting point on hyperelliptic
      26             : curves by Bill Allombert based on a GP script by Bernadette Perrin-Riou.
      27             : 
      28             : References:
      29             : Pierrick Gaudry and Nicolas G\"urel
      30             : Counting Points in Medium Characteristic Using Kedlaya's Algorithm
      31             : Experiment. Math.  Volume 12, Number 4 (2003), 395-402.
      32             :    http://projecteuclid.org/euclid.em/1087568016
      33             : 
      34             : Harrison, M. An extension of Kedlaya's algorithm for hyperelliptic
      35             :   curves. Journal of Symbolic Computation, 47 (1) (2012), 89-101.
      36             :   http://arxiv.org/pdf/1006.4206v3.pdf
      37             : */
      38             : 
      39             : /* We use the basis of differentials (x^i*dx/y^k) (i=1 to 2*g-1),
      40             :    with k either 1 or 3, depending on p and d, see Harrison paper */
      41             : 
      42             : static long
      43        1764 : get_basis(long p, long d)
      44             : {
      45        1764 :   if (odd(d))
      46         868 :     return p < d-1 ? 3 : 1;
      47             :   else
      48         896 :     return 2*p <= d-2 ? 3 : 1;
      49             : }
      50             : 
      51             : static GEN
      52       20265 : FpXXQ_red(GEN S, GEN T, GEN p)
      53             : {
      54       20265 :   pari_sp av = avma;
      55       20265 :   long i, dS = degpol(S);
      56             :   GEN A, C;
      57       20265 :   if (signe(S)==0) return pol_0(varn(T));
      58       20265 :   A = cgetg(dS+3, t_POL);
      59       20265 :   C = pol_0(varn(T));
      60     1520393 :   for(i=dS; i>0; i--)
      61             :   {
      62     1500128 :     GEN Si = FpX_add(C, gel(S,i+2), p);
      63     1500128 :     GEN R, Q = FpX_divrem(Si, T, p, &R);
      64     1500128 :     gel(A,i+2) = R;
      65     1500128 :     C = Q;
      66             :   }
      67       20265 :   gel(A,2) = FpX_add(C, gel(S,2), p);
      68       20265 :   A[1] = S[1];
      69       20265 :   return gerepilecopy(av, FpXX_renormalize(A,dS+3));
      70             : }
      71             : 
      72             : static GEN
      73        3402 : FpXXQ_sqr(GEN x, GEN T, GEN p)
      74             : {
      75        3402 :   pari_sp av = avma;
      76        3402 :   long n = degpol(T);
      77        3402 :   GEN z = FpX_red(ZXX_sqr_Kronecker(x, n), p);
      78        3402 :   z = Kronecker_to_ZXX(z, n, varn(T));
      79        3402 :   return gerepileupto(av, FpXXQ_red(z, T, p));
      80             : }
      81             : 
      82             : static GEN
      83       16863 : FpXXQ_mul(GEN x, GEN y, GEN T, GEN p)
      84             : {
      85       16863 :   pari_sp av = avma;
      86       16863 :   long n = degpol(T);
      87       16863 :   GEN z = FpX_red(ZXX_mul_Kronecker(x, y, n), p);
      88       16863 :   z = Kronecker_to_ZXX(z, n, varn(T));
      89       16863 :   return gerepileupto(av, FpXXQ_red(z, T, p));
      90             : }
      91             : 
      92             : static GEN
      93        1309 : ZpXXQ_invsqrt(GEN S, GEN T, ulong p, long e)
      94             : {
      95        1309 :   pari_sp av = avma, av2;
      96             :   ulong mask;
      97        1309 :   long v = varn(S), n=1;
      98        1309 :   GEN a = pol_1(v);
      99        1309 :   if (e <= 1) return gerepilecopy(av, a);
     100        1309 :   mask = quadratic_prec_mask(e);
     101        1309 :   av2 = avma;
     102        4676 :   for (;mask>1;)
     103             :   {
     104             :     GEN q, q2, q22, f, fq, afq;
     105        3367 :     long n2 = n;
     106        3367 :     n<<=1; if (mask & 1) n--;
     107        3367 :     mask >>= 1;
     108        3367 :     q = powuu(p,n); q2 = powuu(p,n2);
     109        3367 :     f = RgX_sub(FpXXQ_mul(FpXX_red(S, q), FpXXQ_sqr(a, T, q), T, q), pol_1(v));
     110        3367 :     fq = ZXX_Z_divexact(f, q2);
     111        3367 :     q22 = shifti(addiu(q2,1),-1);
     112        3367 :     afq = FpXX_Fp_mul(FpXXQ_mul(a, fq, T, q2), q22, q2);
     113        3367 :     a = RgX_sub(a, ZXX_Z_mul(afq, q2));
     114        3367 :     if (gc_needed(av2,1))
     115             :     {
     116           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXXQ_invsqrt, e = %ld", n);
     117           0 :       a = gerepileupto(av2, a);
     118             :     }
     119             :   }
     120        1309 :   return gerepileupto(av, a);
     121             : }
     122             : 
     123             : static GEN
     124     1029007 : to_ZX(GEN a, long v) { return typ(a)==t_INT? scalarpol(a,v): a; }
     125             : 
     126             : static void
     127          14 : is_sing(GEN H, ulong p)
     128             : {
     129          14 :   pari_err_DOMAIN("hyperellpadicfrobenius","H","is singular at",utoi(p),H);
     130           0 : }
     131             : 
     132             : static void
     133        1309 : get_UV(GEN *U, GEN *V, GEN T, ulong p, long e)
     134             : {
     135        1309 :   GEN q = powuu(p,e), d;
     136        1309 :   GEN dT = FpX_deriv(T, q);
     137        1309 :   GEN R = polresultantext(T, dT);
     138        1309 :   long v = varn(T);
     139        1309 :   if (dvdiu(gel(R,3),p)) is_sing(T, p);
     140        1309 :   d = Zp_inv(gel(R,3), utoi(p), e);
     141        1309 :   *U = FpX_Fp_mul(FpX_red(to_ZX(gel(R,1),v),q),d,q);
     142        1309 :   *V = FpX_Fp_mul(FpX_red(to_ZX(gel(R,2),v),q),d,q);
     143        1309 : }
     144             : 
     145             : static GEN
     146      133847 : frac_to_Fp(GEN a, GEN b, GEN p)
     147             : {
     148      133847 :   GEN d = gcdii(a, b);
     149      133847 :   return Fp_div(diviiexact(a, d), diviiexact(b, d), p);
     150             : }
     151             : 
     152             : static GEN
     153       10094 : ZpXXQ_frob(GEN S, GEN U, GEN V, long k, GEN T, ulong p, long e)
     154             : {
     155       10094 :   pari_sp av = avma, av2;
     156       10094 :   long i, pr = degpol(S), dT = degpol(T), vT = varn(T);
     157       10094 :   GEN q = powuu(p,e);
     158       10094 :   GEN Tp = FpX_deriv(T, q), Tp1 = RgX_shift_shallow(Tp, 1);
     159       10094 :   GEN M = to_ZX(gel(S,pr+2),vT) , R;
     160       10094 :   av2 = avma;
     161      987868 :   for(i = pr-1; i>=k; i--)
     162             :   {
     163             :     GEN A, B, H, Bc;
     164             :     ulong v, r;
     165      977774 :     H = FpX_divrem(FpX_mul(V,M,q), T, q, &B);
     166      977774 :     A = FpX_add(FpX_mul(U,M,q), FpX_mul(H, Tp, q),q);
     167      977774 :     v = u_lvalrem(2*i+1,p,&r);
     168      977774 :     Bc = ZX_deriv(B);
     169      977774 :     Bc = FpX_Fp_mul(ZX_divuexact(Bc,upowuu(p,v)),Fp_divu(gen_2, r, q), q);
     170      977774 :     M = FpX_add(to_ZX(gel(S,i+2),vT), FpX_add(A, Bc, q), q);
     171      977774 :     if (gc_needed(av2,1))
     172             :     {
     173           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXXQ_frob, step 1, i = %ld", i);
     174           0 :       M = gerepileupto(av2, M);
     175             :     }
     176             :   }
     177       10094 :   if (degpol(M)<dT-1)
     178        5488 :     return gerepileupto(av, M);
     179        4606 :   R = RgX_shift_shallow(M,dT-degpol(M)-2);
     180        4606 :   av2 = avma;
     181      237629 :   for(i = degpol(M)-dT+2; i>=1; i--)
     182             :   {
     183             :     GEN B, c;
     184      233023 :     R = RgX_shift_shallow(R, 1);
     185      233023 :     gel(R,2) = gel(M, i+1);
     186      233023 :     if (degpol(R) < dT) continue;
     187      130935 :     B = FpX_add(FpX_mulu(T, 2*i, q), Tp1, q);
     188      130935 :     c = frac_to_Fp(leading_coeff(R), leading_coeff(B), q);
     189      130935 :     R = FpX_sub(R, FpX_Fp_mul(B, c, q), q);
     190      130935 :     if (gc_needed(av2,1))
     191             :     {
     192           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXXQ_frob, step 2, i = %ld", i);
     193           0 :       R = gerepileupto(av2, R);
     194             :     }
     195             :   }
     196        4606 :   if (degpol(R)==dT-1)
     197             :   {
     198        2912 :     GEN c = frac_to_Fp(leading_coeff(R), leading_coeff(Tp), q);
     199        2912 :     R = FpX_sub(R, FpX_Fp_mul(Tp, c, q), q);
     200        2912 :     return gerepileupto(av, R);
     201             :   } else
     202        1694 :     return gerepilecopy(av, R);
     203             : }
     204             : 
     205             : static GEN
     206       12026 : revdigits(GEN v)
     207             : {
     208       12026 :   long i, n = lg(v)-1;
     209       12026 :   GEN w = cgetg(n+2, t_POL);
     210       12026 :   w[1] = evalsigne(1)|evalvarn(0);
     211      168784 :   for (i=0; i<n; i++)
     212      156758 :     gel(w,i+2) = gel(v,n-i);
     213       12026 :   return FpXX_renormalize(w, n+2);
     214             : }
     215             : 
     216             : static GEN
     217       10094 : diff_red(GEN s, GEN A, long m, GEN T, GEN p)
     218             : {
     219       10094 :   long v, n, vT = varn(T);
     220             :   GEN Q, sQ, qS;
     221             :   pari_timer ti;
     222       10094 :   if (DEBUGLEVEL>1) timer_start(&ti);
     223       10094 :   Q = revdigits(FpX_digits(A,T,p));
     224       10094 :   n = degpol(Q);
     225       10094 :   if (DEBUGLEVEL>1) timer_printf(&ti,"reddigits");
     226       10094 :   sQ = FpXXQ_mul(s,Q,T,p);
     227       10094 :   if (DEBUGLEVEL>1) timer_printf(&ti,"redmul");
     228       10094 :   qS = RgX_shift_shallow(sQ,m-n);
     229       10094 :   v = ZX_val(sQ);
     230       10094 :   if (n > m + v)
     231             :   {
     232        4564 :     long i, l = n-m-v;
     233        4564 :     GEN rS = cgetg(l+1,t_VEC);
     234       29190 :     for (i = l-1; i >=0 ; i--)
     235       24626 :       gel(rS,i+1) = to_ZX(gel(sQ, 1+v+l-i), vT);
     236        4564 :     rS = FpXV_FpX_fromdigits(rS,T,p);
     237        4564 :     gel(qS,2) = FpX_add(FpX_mul(rS, T, p), gel(qS, 2), p);
     238        4564 :     if (DEBUGLEVEL>1) timer_printf(&ti,"redadd");
     239             :   }
     240       10094 :   return qS;
     241             : }
     242             : 
     243             : static GEN
     244       10094 : ZC_to_padic(GEN C, GEN q)
     245             : {
     246       10094 :   long i, l = lg(C);
     247       10094 :   GEN V = cgetg(l,t_COL);
     248      102914 :   for(i = 1; i < l; i++)
     249       92820 :     gel(V, i) = gadd(gel(C, i), q);
     250       10094 :   return V;
     251             : }
     252             : 
     253             : static GEN
     254        1309 : ZM_to_padic(GEN M, GEN q)
     255             : {
     256        1309 :   long i, l = lg(M);
     257        1309 :   GEN V = cgetg(l,t_MAT);
     258       11403 :   for(i = 1; i < l; i++)
     259       10094 :     gel(V, i) = ZC_to_padic(gel(M, i), q);
     260        1309 :   return V;
     261             : }
     262             : 
     263             : static GEN
     264        1743 : ZX_to_padic(GEN P, GEN q)
     265             : {
     266        1743 :   long i, l = lg(P);
     267        1743 :   GEN Q = cgetg(l, t_POL);
     268        1743 :   Q[1] = P[1];
     269        5978 :   for (i=2; i<l ;i++)
     270        4235 :     gel(Q,i) = gadd(gel(P,i), q);
     271        1743 :   return normalizepol(Q);
     272             : }
     273             : 
     274             : static GEN
     275         469 : ZXC_to_padic(GEN x, GEN q)
     276        2212 : { pari_APPLY_type(t_COL, ZX_to_padic(gel(x, i), q)) }
     277             : 
     278             : static GEN
     279         147 : ZXM_to_padic(GEN x, GEN q)
     280         616 : { pari_APPLY_same(ZXC_to_padic(gel(x, i), q)) }
     281             : 
     282             : static GEN
     283        1309 : ZlX_hyperellpadicfrobenius(GEN H, ulong p, long n)
     284             : {
     285        1309 :   pari_sp av = avma;
     286             :   long k, N, i, d;
     287             :   GEN F, s, Q, pN1, U, V;
     288             :   pari_timer ti;
     289        1309 :   if (typ(H) != t_POL) pari_err_TYPE("hyperellpadicfrobenius",H);
     290        1309 :   if (p == 2) is_sing(H, 2);
     291        1309 :   d = degpol(H);
     292        1309 :   if (d <= 0)
     293           0 :     pari_err_CONSTPOL("hyperellpadicfrobenius");
     294        1309 :   if (n < 1)
     295           0 :     pari_err_DOMAIN("hyperellpadicfrobenius","n","<", gen_1, utoi(n));
     296        1309 :   k = get_basis(p, d);
     297        1309 :   N = n + ulogint(2*n, p) + 1;
     298        1309 :   pN1 = powuu(p,N+1);
     299        1309 :   Q = RgX_to_FpX(H, pN1);
     300        1309 :   if (dvdiu(leading_coeff(Q),p)) is_sing(H, p);
     301        1309 :   setvarn(Q,1);
     302        1309 :   if (DEBUGLEVEL>1) timer_start(&ti);
     303        1309 :   s = revdigits(FpX_digits(RgX_inflate(Q, p), Q, pN1));
     304        1309 :   if (DEBUGLEVEL>1) timer_printf(&ti,"s1");
     305        1309 :   s = ZpXXQ_invsqrt(s, Q, p, N);
     306        1309 :   if (k==3)
     307          35 :     s = FpXXQ_mul(s, FpXXQ_sqr(s, Q, pN1), Q, pN1);
     308        1309 :   if (DEBUGLEVEL>1) timer_printf(&ti,"invsqrt");
     309        1309 :   get_UV(&U, &V, Q, p, N+1);
     310        1309 :   F = cgetg(d, t_MAT);
     311       11403 :   for (i = 1; i < d; i++)
     312             :   {
     313       10094 :     pari_sp av2 = avma;
     314             :     GEN M, D;
     315       10094 :     D = diff_red(s, monomial(utoipos(p),p*i-1,1),(k*p-1)>>1, Q, pN1);
     316       10094 :     if (DEBUGLEVEL>1) timer_printf(&ti,"red");
     317       10094 :     M = ZpXXQ_frob(D, U, V, (k-1)>>1, Q, p, N + 1);
     318       10094 :     if (DEBUGLEVEL>1) timer_printf(&ti,"frob");
     319       10094 :     gel(F, i) = gerepilecopy(av2, RgX_to_RgC(M, d-1));
     320             :   }
     321        1309 :   return gerepileupto(av, F);
     322             : }
     323             : 
     324             : GEN
     325        1309 : hyperellpadicfrobenius(GEN H, ulong p, long n)
     326             : {
     327        1309 :   pari_sp av = avma;
     328        1309 :   GEN M = ZlX_hyperellpadicfrobenius(H, p, n);
     329        1309 :   GEN q = zeropadic_shallow(utoipos(p),n);
     330        1309 :   return gerepileupto(av, ZM_to_padic(M, q));
     331             : }
     332             : 
     333             : INLINE GEN
     334        2247 : FpXXX_renormalize(GEN x, long lx)  { return ZXX_renormalize(x,lx); }
     335             : 
     336             : static GEN
     337        1806 : ZpXQXXQ_red(GEN F, GEN S, GEN T, GEN q, GEN p, long e)
     338             : {
     339        1806 :   pari_sp av = avma;
     340        1806 :   long i, dF = degpol(F);
     341             :   GEN A, C;
     342        1806 :   if (signe(F)==0) return pol_0(varn(S));
     343        1806 :   A = cgetg(dF+3, t_POL);
     344        1806 :   C = pol_0(varn(S));
     345       96404 :   for(i=dF; i>0; i--)
     346             :   {
     347       94598 :     GEN Fi = FpXX_add(C, gel(F,i+2), q);
     348       94598 :     GEN R, Q = ZpXQX_divrem(Fi, S, T, q, p, e, &R);
     349       94598 :     gel(A,i+2) = R;
     350       94598 :     C = Q;
     351             :   }
     352        1806 :   gel(A,2) = FpXX_add(C, gel(F,2), q);
     353        1806 :   A[1] = F[1];
     354        1806 :   return gerepilecopy(av, FpXXX_renormalize(A,dF+3));
     355             : }
     356             : 
     357             : static GEN
     358         448 : ZpXQXXQ_sqr(GEN x, GEN S, GEN T, GEN q, GEN p, long e)
     359             : {
     360         448 :   pari_sp av = avma;
     361             :   GEN z, kx;
     362         448 :   long n = degpol(S);
     363         448 :   kx = RgXX_to_Kronecker(x, n);
     364         448 :   z = Kronecker_to_ZXX(FpXQX_sqr(kx, T, q), n, varn(S));
     365         448 :   return gerepileupto(av, ZpXQXXQ_red(z, S, T, q, p, e));
     366             : }
     367             : 
     368             : static GEN
     369        1358 : ZpXQXXQ_mul(GEN x, GEN y, GEN S, GEN T, GEN q, GEN p, long e)
     370             : {
     371        1358 :   pari_sp av = avma;
     372             :   GEN z, kx, ky;
     373        1358 :   long n = degpol(S);
     374        1358 :   kx = RgXX_to_Kronecker(x, n);
     375        1358 :   ky = RgXX_to_Kronecker(y, n);
     376        1358 :   z = Kronecker_to_ZXX(FpXQX_mul(ky, kx, T, q), n, varn(S));
     377        1358 :   return gerepileupto(av, ZpXQXXQ_red(z, S, T, q, p, e));
     378             : }
     379             : 
     380             : static GEN
     381         441 : FpXXX_red(GEN z, GEN p)
     382             : {
     383             :   GEN res;
     384         441 :   long i, l = lg(z);
     385         441 :   res = cgetg(l,t_POL); res[1] = z[1];
     386       17388 :   for (i=2; i<l; i++)
     387             :   {
     388       16947 :     GEN zi = gel(z,i);
     389       16947 :     if (typ(zi)==t_INT)
     390           0 :       gel(res,i) = modii(zi,p);
     391             :     else
     392       16947 :      gel(res,i) = FpXX_red(zi,p);
     393             :   }
     394         441 :   return FpXXX_renormalize(res,lg(res));
     395             : }
     396             : 
     397             : static GEN
     398         441 : FpXXX_Fp_mul(GEN z, GEN a, GEN p)
     399             : {
     400         441 :   return FpXXX_red(RgX_Rg_mul(z, a), p);
     401             : }
     402             : 
     403             : static GEN
     404         154 : ZpXQXXQ_invsqrt(GEN F, GEN S, GEN T, ulong p, long e)
     405             : {
     406         154 :   pari_sp av = avma, av2, av3;
     407             :   ulong mask;
     408         154 :   long v = varn(F), n=1;
     409             :   pari_timer ti;
     410         154 :   GEN a = pol_1(v), pp = utoipos(p);
     411         154 :   if (DEBUGLEVEL>1) timer_start(&ti);
     412         154 :   if (e <= 1) return gerepilecopy(av, a);
     413         154 :   mask = quadratic_prec_mask(e);
     414         154 :   av2 = avma;
     415         595 :   for (;mask>1;)
     416             :   {
     417             :     GEN q, q2, q22, f, fq, afq;
     418         441 :     long n2 = n;
     419         441 :     n<<=1; if (mask & 1) n--;
     420         441 :     mask >>= 1;
     421         441 :     q = powuu(p,n); q2 = powuu(p,n2);
     422         441 :     av3 = avma;
     423         441 :     f = RgX_sub(ZpXQXXQ_mul(F, ZpXQXXQ_sqr(a, S, T, q, pp, n), S, T, q, pp, n), pol_1(v));
     424         441 :     fq = gerepileupto(av3, RgX_Rg_divexact(f, q2));
     425         441 :     q22 = shifti(addiu(q2,1),-1);
     426         441 :     afq = FpXXX_Fp_mul(ZpXQXXQ_mul(a, fq, S, T, q2, pp, n2), q22, q2);
     427         441 :     a = RgX_sub(a, RgX_Rg_mul(afq, q2));
     428         441 :     if (gc_needed(av2,1))
     429             :     {
     430           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXQXXQ_invsqrt, e = %ld", n);
     431           0 :       a = gerepileupto(av2, a);
     432             :     }
     433             :   }
     434         154 :   return gerepileupto(av, a);
     435             : }
     436             : 
     437             : static GEN
     438        6573 : frac_to_Fq(GEN a, GEN b, GEN T, GEN q, GEN p, long e)
     439             : {
     440        6573 :   GEN d = gcdii(ZX_content(a), ZX_content(b));
     441        6573 :   return ZpXQ_div(ZX_Z_divexact(a, d), ZX_Z_divexact(b, d), T, q, p, e);
     442             : }
     443             : 
     444             : static GEN
     445         469 : ZpXQXXQ_frob(GEN F, GEN U, GEN V, long k, GEN S, GEN T, ulong p, long e)
     446             : {
     447         469 :   pari_sp av = avma, av2;
     448         469 :   long i, pr = degpol(F), dS = degpol(S), v = varn(T);
     449         469 :   GEN q = powuu(p,e), pp = utoipos(p);
     450         469 :   GEN Sp = RgX_deriv(S), Sp1 = RgX_shift_shallow(Sp, 1);
     451         469 :   GEN M = gel(F,pr+2), R;
     452         469 :   av2 = avma;
     453       52311 :   for(i = pr-1; i>=k; i--)
     454             :   {
     455             :     GEN A, B, H, Bc;
     456             :     ulong v, r;
     457       51842 :     H = ZpXQX_divrem(FpXQX_mul(V, M, T, q), S, T, q, utoipos(p), e, &B);
     458       51842 :     A = FpXX_add(FpXQX_mul(U, M, T, q), FpXQX_mul(H, Sp, T, q),q);
     459       51842 :     v = u_lvalrem(2*i+1,p,&r);
     460       51842 :     Bc = RgX_deriv(B);
     461       51842 :     Bc = FpXX_Fp_mul(ZXX_Z_divexact(Bc,powuu(p,v)), Fp_divu(gen_2, r, q), q);
     462       51842 :     M = FpXX_add(gel(F,i+2), FpXX_add(A, Bc, q), q);
     463       51842 :     if (gc_needed(av2,1))
     464             :     {
     465           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXQXXQ_frob, step 1, i = %ld", i);
     466           0 :       M = gerepileupto(av2, M);
     467             :     }
     468             :   }
     469         469 :   if (degpol(M)<dS-1)
     470         266 :     return gerepileupto(av, M);
     471         203 :   R = RgX_shift_shallow(M,dS-degpol(M)-2);
     472         203 :   av2 = avma;
     473        7175 :   for(i = degpol(M)-dS+2; i>=1; i--)
     474             :   {
     475             :     GEN B, c;
     476        6972 :     R = RgX_shift_shallow(R, 1);
     477        6972 :     gel(R,2) = gel(M, i+1);
     478        6972 :     if (degpol(R) < dS) continue;
     479        6412 :     B = FpXX_add(FpXX_mulu(S, 2*i, q), Sp1, q);
     480        6412 :     c = frac_to_Fq(to_ZX(leading_coeff(R),v), to_ZX(leading_coeff(B),v), T, q, pp, e);
     481        6412 :     R = FpXX_sub(R, FpXQX_FpXQ_mul(B, c, T, q), q);
     482        6412 :     if (gc_needed(av2,1))
     483             :     {
     484           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXXQ_frob, step 2, i = %ld", i);
     485           0 :       R = gerepileupto(av2, R);
     486             :     }
     487             :   }
     488         203 :   if (degpol(R)==dS-1)
     489             :   {
     490         161 :     GEN c = frac_to_Fq(to_ZX(leading_coeff(R),v), to_ZX(leading_coeff(Sp),v), T, q, pp, e);
     491         161 :     R = FpXX_sub(R, FpXQX_FpXQ_mul(Sp, c, T, q), q);
     492         161 :     return gerepileupto(av, R);
     493             :   } else
     494          42 :     return gerepilecopy(av, R);
     495             : }
     496             : 
     497             : static GEN
     498         469 : Fq_diff_red(GEN s, GEN A, long m, GEN S, GEN T, GEN q, GEN p, long e)
     499             : {
     500             :   long v, n;
     501             :   GEN Q, sQ, qS;
     502             :   pari_timer ti;
     503         469 :   if (DEBUGLEVEL>1) timer_start(&ti);
     504         469 :   Q = revdigits(ZpXQX_digits(A, S, T, q, p, e));
     505         469 :   n = degpol(Q);
     506         469 :   if (DEBUGLEVEL>1) timer_printf(&ti,"reddigits");
     507         469 :   sQ = ZpXQXXQ_mul(s, Q, S, T, q, p, e);
     508         469 :   if (DEBUGLEVEL>1) timer_printf(&ti,"redmul");
     509         469 :   qS = RgX_shift_shallow(sQ,m-n);
     510         469 :   v = ZX_val(sQ);
     511         469 :   if (n > m + v)
     512             :   {
     513         189 :     long i, l = n-m-v;
     514         189 :     GEN rS = cgetg(l+1,t_VEC);
     515        1547 :     for (i = l-1; i >=0 ; i--)
     516        1358 :       gel(rS,i+1) = gel(sQ, 1+v+l-i);
     517         189 :     rS = FpXQXV_FpXQX_fromdigits(rS, S, T, q);
     518         189 :     gel(qS,2) = FpXX_add(FpXQX_mul(rS, S, T, q), gel(qS, 2), q);
     519         189 :     if (DEBUGLEVEL>1) timer_printf(&ti,"redadd");
     520             :   }
     521         469 :   return qS;
     522             : }
     523             : 
     524             : static void
     525         154 : Fq_get_UV(GEN *U, GEN *V, GEN S, GEN T, ulong p, long e)
     526             : {
     527         154 :   GEN q = powuu(p, e), pp = utoipos(p), d;
     528         154 :   GEN dS = RgX_deriv(S), R  = polresultantext(S, dS), C;
     529         154 :   long v = varn(S);
     530         154 :   if (signe(FpX_red(to_ZX(gel(R,3),v), pp))==0) is_sing(S, p);
     531         147 :   C = FpXQ_red(to_ZX(gel(R, 3),v), T, q);
     532         147 :   d = ZpXQ_inv(C, T, pp, e);
     533         147 :   *U = FpXQX_FpXQ_mul(FpXQX_red(to_ZX(gel(R,1),v),T,q),d,T,q);
     534         147 :   *V = FpXQX_FpXQ_mul(FpXQX_red(to_ZX(gel(R,2),v),T,q),d,T,q);
     535         147 : }
     536             : 
     537             : static GEN
     538         469 : ZXX_to_FpXC(GEN x, long N, GEN p, long v)
     539             : {
     540             :   long i, l;
     541             :   GEN z;
     542         469 :   l = lg(x)-1; x++;
     543         469 :   if (l > N+1) l = N+1; /* truncate higher degree terms */
     544         469 :   z = cgetg(N+1,t_COL);
     545        2170 :   for (i=1; i<l ; i++)
     546             :   {
     547        1701 :     GEN xi = gel(x, i);
     548        1701 :     gel(z,i) = typ(xi)==t_INT? scalarpol(Fp_red(xi, p), v): FpX_red(xi, p);
     549             :   }
     550         511 :   for (   ; i<=N ; i++)
     551          42 :     gel(z,i) = pol_0(v);
     552         469 :   return z;
     553             : }
     554             : 
     555             : GEN
     556         154 : ZlXQX_hyperellpadicfrobenius(GEN H, GEN T, ulong p, long n)
     557             : {
     558         154 :   pari_sp av = avma;
     559             :   long k, N, i, d, N1;
     560             :   GEN xp, F, s, q, Q, pN1, U, V, pp;
     561             :   pari_timer ti;
     562         154 :   if (typ(H) != t_POL) pari_err_TYPE("hyperellpadicfrobenius",H);
     563         154 :   if (p == 2) is_sing(H, 2);
     564         154 :   d = degpol(H);
     565         154 :   if (d <= 0) pari_err_CONSTPOL("hyperellpadicfrobenius");
     566         154 :   if (n < 1) pari_err_DOMAIN("hyperellpadicfrobenius","n","<", gen_1, utoi(n));
     567         154 :   k = get_basis(p, d); pp = utoipos(p);
     568         154 :   N = n + ulogint(2*n, p) + 1;
     569         154 :   q = powuu(p,n); N1 = N+1;
     570         154 :   pN1 = powuu(p,N1); T = FpX_get_red(T, pN1);
     571         154 :   Q = RgX_to_FqX(H, T, pN1);
     572         154 :   if (signe(FpX_red(to_ZX(leading_coeff(Q),varn(Q)),pp))==0) is_sing(H, p);
     573         154 :   if (DEBUGLEVEL>1) timer_start(&ti);
     574         154 :   xp = ZpX_Frobenius(T, pp, N1);
     575         154 :   s = RgX_inflate(FpXY_FpXQ_evalx(Q, xp, T, pN1), p);
     576         154 :   s = revdigits(ZpXQX_digits(s, Q, T, pN1, pp, N1));
     577         154 :   if (DEBUGLEVEL>1) timer_printf(&ti,"s1");
     578         154 :   s = ZpXQXXQ_invsqrt(s, Q, T, p, N);
     579         154 :   if (k==3)
     580           7 :     s = ZpXQXXQ_mul(s, ZpXQXXQ_sqr(s, Q, T, pN1, pp, N1), Q, T, pN1, pp, N1);
     581         154 :   if (DEBUGLEVEL>1) timer_printf(&ti,"invsqrt");
     582         154 :   Fq_get_UV(&U, &V, Q, T, p, N+1);
     583         147 :   if (DEBUGLEVEL>1) timer_printf(&ti,"get_UV");
     584         147 :   F = cgetg(d, t_MAT);
     585         616 :   for (i = 1; i < d; i++)
     586             :   {
     587         469 :     pari_sp av2 = avma;
     588             :     GEN M, D;
     589         469 :     D = Fq_diff_red(s, monomial(pp,p*i-1,1),(k*p-1)>>1, Q, T, pN1, pp, N1);
     590         469 :     if (DEBUGLEVEL>1) timer_printf(&ti,"red");
     591         469 :     M = ZpXQXXQ_frob(D, U, V, (k - 1)>>1, Q, T, p, N1);
     592         469 :     if (DEBUGLEVEL>1) timer_printf(&ti,"frob");
     593         469 :     gel(F, i) = gerepileupto(av2, ZXX_to_FpXC(M, d-1, q, varn(T)));
     594             :   }
     595         147 :   return gerepileupto(av, F);
     596             : }
     597             : 
     598             : GEN
     599         154 : nfhyperellpadicfrobenius(GEN H, GEN T, ulong p, long n)
     600             : {
     601         154 :   pari_sp av = avma;
     602         154 :   GEN pp = utoipos(p), q = zeropadic_shallow(pp, n);
     603         154 :   GEN M = ZlXQX_hyperellpadicfrobenius(lift_shallow(H),T,p,n);
     604         147 :   GEN MM = ZpXQM_prodFrobenius(M, T, pp, n);
     605         147 :   GEN m = gmul(ZXM_to_padic(MM, q), gmodulo(gen_1, T));
     606         147 :   return gerepileupto(av, m);
     607             : }
     608             : 
     609             : GEN
     610         595 : hyperellpadicfrobenius0(GEN H, GEN Tp, long n)
     611             : {
     612             :   GEN T, p;
     613         595 :   if (!ff_parse_Tp(Tp, &T,&p,0)) pari_err_TYPE("hyperellpadicfrobenius", Tp);
     614         595 :   if (lgefint(p) > 3) pari_err_IMPL("large prime in hyperellpadicfrobenius");
     615           7 :   return T? nfhyperellpadicfrobenius(H, T, itou(p), n)
     616         602 :           : hyperellpadicfrobenius(H, itou(p), n);
     617             : }
     618             : 
     619             : static GEN
     620          84 : F2x_genus2charpoly_naive(GEN P, GEN Q)
     621             : {
     622          84 :   long a, b = 1, c = 0;
     623          84 :   GEN T = mkvecsmall2(P[1], 7);
     624          84 :   GEN PT = F2x_rem(P, T), QT = F2x_rem(Q, T);
     625          84 :   long q0 = F2x_eval(Q, 0), q1 = F2x_eval(Q, 1);
     626          84 :   long dP = F2x_degree(P), dQ = F2x_degree(Q);
     627          84 :   a= dQ<3 ? 0: dP<=5 ? 1: -1;
     628          84 :   a += (q0? F2x_eval(P, 0)? -1: 1: 0) + (q1? F2x_eval(P, 1)? -1: 1: 0);
     629          84 :   b += q0 + q1;
     630          84 :   if (lgpol(QT))
     631          70 :     c = (F2xq_trace(F2xq_div(PT, F2xq_sqr(QT, T), T), T)==0 ? 1: -1);
     632          84 :   return mkvecsmalln(6, 0UL, 4UL, 2*a, (b+2*c+a*a)>>1, a, 1UL);
     633             : }
     634             : 
     635             : static GEN
     636         252 : Flx_difftable(GEN P, ulong p)
     637             : {
     638         252 :   long i, n = degpol(P);
     639         252 :   GEN V = cgetg(n+2, t_VEC);
     640         252 :   gel(V, n+1) = P;
     641        1729 :   for(i = n; i >= 1; i--)
     642        1477 :     gel(V, i) = Flx_diff1(gel(V, i+1), p);
     643         252 :   return V;
     644             : }
     645             : 
     646             : static GEN
     647        1561 : FlxV_Fl2_eval_pre(GEN V, GEN x, ulong D, ulong p, ulong pi)
     648             : {
     649        1561 :   long i, n = lg(V)-1;
     650        1561 :   GEN r = cgetg(n+1, t_VEC);
     651       11963 :   for (i = 1; i <= n; i++)
     652       10402 :     gel(r, i) = Flx_Fl2_eval_pre(gel(V, i), x, D, p, pi);
     653        1561 :   return r;
     654             : }
     655             : 
     656             : static GEN
     657       44590 : Fl2V_next(GEN V, ulong p)
     658             : {
     659       44590 :   long i, n = lg(V)-1;
     660       44590 :   GEN r = cgetg(n+1, t_VEC);
     661       44590 :   gel(r, 1) = gel(V, 1);
     662      286300 :   for (i = 2; i <= n; i++)
     663      241710 :     gel(r, i) = Flv_add(gel(V, i), gel(V, i-1), p);
     664       44590 :   return r;
     665             : }
     666             : 
     667             : static GEN
     668         252 : Flx_genus2charpoly_naive(GEN H, ulong p)
     669             : {
     670         252 :   pari_sp av = avma, av2;
     671         252 :   ulong pi = get_Fl_red(p);
     672         252 :   ulong i, j, p2 = p>>1, D = 2, e = ((p&2UL) == 0) ? -1 : 1;
     673         252 :   long a, b, c = 0, n = degpol(H);
     674         252 :   GEN t, k = const_vecsmall(p, -1);
     675         252 :   k[1] = 0;
     676        1813 :   for (i=1, j=1; i < p; i += 2, j = Fl_add(j, i, p)) k[j+1] = 1;
     677         294 :   while (k[1+D] >= 0) D++;
     678         252 :   b = n == 5 ? 0 : 1;
     679         252 :   a = b ? k[1+Flx_lead(H)]: 0;
     680         252 :   t = Flx_difftable(H, p);
     681         252 :   av2 = avma;
     682        3626 :   for (i=0; i < p; i++)
     683             :   {
     684        3374 :     ulong v = Flx_eval(H, i, p);
     685        3374 :     a += k[1+v];
     686        3374 :     b += !!v;
     687             :   }
     688        1813 :   for (j=1; j <= p2; j++)
     689             :   {
     690        1561 :     GEN V = FlxV_Fl2_eval_pre(t, mkvecsmall2(0, j), D, p, pi);
     691        1561 :     for (i=0;; i++)
     692       44590 :     {
     693       46151 :       GEN r2 = gel(V, n+1);
     694       92302 :       c += uel(r2,2) ?
     695       43890 :         (uel(r2,1) ? uel(k,1+Fl2_norm_pre(r2, D, p, pi)): e)
     696       90041 :          : !!uel(r2,1);
     697       46151 :       if (i == p-1) break;
     698       44590 :       V = Fl2V_next(V, p);
     699             :     }
     700        1561 :     set_avma(av2);
     701             :   }
     702         252 :   set_avma(av);
     703         252 :   return mkvecsmalln(6, 0UL, p*p, a*p, (b+2*c+a*a)>>1, a, 1UL);
     704             : }
     705             : 
     706             : static GEN
     707         679 : charpoly_funceq(GEN P, GEN q)
     708             : {
     709         679 :   long i, l, g = degpol(P)>>1;
     710         679 :   GEN Q = cgetg_copy(P, &l);
     711         679 :   Q[1] = P[1];
     712        3843 :   for (i=0; i<=g; i++)
     713        3164 :     gel(Q, i+2) = mulii(gel(P, 2*g-i+2), powiu(q, g-i));
     714        3164 :   for (; i<=2*g; i++)
     715        2485 :     gel(Q, i+2) = icopy(gel(P, i+2));
     716         679 :   return Q;
     717             : }
     718             : 
     719             : static long
     720         686 : hyperell_Weil_bound(GEN q, ulong g, GEN p)
     721             : {
     722         686 :   pari_sp av = avma;
     723         686 :   GEN w = mulii(binomialuu(2*g,g),sqrtint(shifti(powiu(q, g),2)));
     724         686 :   return gc_long(av, logint(w,p) + 1);
     725             : }
     726             : 
     727             : /* return 4P + Q^2 */
     728             : static GEN
     729      287368 : check_hyperell(GEN PQ)
     730             : {
     731             :   GEN H;
     732      287368 :   if (is_vec_t(typ(PQ)) && lg(PQ)==3)
     733      225651 :     H = gadd(gsqr(gel(PQ, 2)), gmul2n(gel(PQ, 1), 2));
     734             :   else
     735       61717 :     H = gmul2n(PQ, 2);
     736      287368 :   return typ(H) == t_POL? H: NULL;
     737             : }
     738             : 
     739             : GEN
     740        1029 : hyperellcharpoly(GEN PQ)
     741             : {
     742        1029 :   pari_sp av = avma;
     743        1029 :   GEN M, R, T=NULL, pp=NULL, q;
     744        1029 :   long d, n, eps = 0;
     745             :   ulong p;
     746        1029 :   GEN H = check_hyperell(PQ);
     747        1029 :   if (!H || !RgX_is_FpXQX(H, &T, &pp) || !pp)
     748           0 :     pari_err_TYPE("hyperellcharpoly", PQ);
     749        1029 :   p = itou(pp);
     750        1029 :   if (!T)
     751             :   {
     752         882 :     if (p==2 && is_vec_t(typ(PQ)))
     753             :     {
     754          84 :       long dP, dQ, v = varn(H);
     755          84 :       GEN P = gel(PQ,1), Q = gel(PQ,2);
     756          84 :       if (typ(P)!=t_POL)  P = scalarpol(P, v);
     757          84 :       if (typ(Q)!=t_POL)  Q = scalarpol(Q, v);
     758          84 :       dP = degpol(P); dQ = degpol(Q);
     759          84 :       if (dP<=6 && dQ <=3 && (dQ==3 || dP>=5))
     760             :       {
     761          84 :         GEN P2 = RgX_to_F2x(P), Q2 = RgX_to_F2x(Q);
     762          84 :         GEN D = F2x_add(F2x_mul(P2, F2x_sqr(F2x_deriv(Q2))), F2x_sqr(F2x_deriv(P2)));
     763          84 :         if (F2x_degree(F2x_gcd(D, Q2))) is_sing(PQ, 2);
     764          84 :         if (dP==6 && dQ<3 && F2x_coeff(P2,5)==F2x_coeff(Q2,2))
     765           0 :           is_sing(PQ, 2); /* The curve is singular at infinity */
     766          84 :         R = zx_to_ZX(F2x_genus2charpoly_naive(P2, Q2));
     767          84 :         return gerepileupto(av, R);
     768             :       }
     769             :     }
     770         798 :     H = RgX_to_FpX(H, pp);
     771         798 :     d = degpol(H);
     772         798 :     if (d <= 0) is_sing(H, p);
     773         798 :     if (p > 2 && ((d == 5 && p < 17500) || (d == 6 && p < 24500)))
     774             :     {
     775         259 :       GEN Hp = ZX_to_Flx(H, p);
     776         259 :       if (!Flx_is_squarefree(Hp, p)) is_sing(H, p);
     777         252 :       R = zx_to_ZX(Flx_genus2charpoly_naive(Hp, p));
     778         252 :       return gerepileupto(av, R);
     779             :     }
     780         539 :     n = hyperell_Weil_bound(pp, (d-1)>>1, pp);
     781         539 :     eps = odd(d)? 0: Fp_issquare(leading_coeff(H), pp);
     782         539 :     M = hyperellpadicfrobenius(H, p, n);
     783         539 :     R = centerlift(carberkowitz(M, 0));
     784         539 :     q = pp;
     785             :   }
     786             :   else
     787             :   {
     788             :     int fixvar;
     789         147 :     T = typ(T)==t_FFELT? FF_mod(T): RgX_to_FpX(T, pp);
     790         147 :     q = powuu(p, degpol(T));
     791         147 :     fixvar = (varncmp(varn(T),varn(H)) <= 0);
     792         147 :     if (fixvar) setvarn(T, fetch_var());
     793         147 :     H = RgX_to_FpXQX(H, T, pp);
     794         147 :     d = degpol(H);
     795         147 :     if (d <= 0) is_sing(H, p);
     796         147 :     eps = odd(d)? 0: Fq_issquare(leading_coeff(H), T, pp);
     797         147 :     n = hyperell_Weil_bound(q, (d-1)>>1, pp);
     798         147 :     M = nfhyperellpadicfrobenius(H, T, p, n);
     799         140 :     R = simplify_shallow(centerlift(liftpol_shallow(carberkowitz(M, 0))));
     800         140 :     if (fixvar) (void)delete_var();
     801             :   }
     802         679 :   if (!odd(d))
     803             :   {
     804         301 :     GEN b = get_basis(p, d) == 3 ? gen_1 : q;
     805         301 :     GEN pn = powuu(p, n);
     806         301 :     R = FpX_div_by_X_x(R, eps? b: negi(b), pn, NULL);
     807         301 :     R = FpX_center_i(R, pn, shifti(pn,-1));
     808             :   }
     809         679 :   R = charpoly_funceq(R, q);
     810         679 :   return gerepilecopy(av, R);
     811             : }
     812             : 
     813             : int
     814        3493 : hyperellisoncurve(GEN W, GEN P)
     815             : {
     816        3493 :   pari_sp av = avma;
     817             :   long res;
     818             :   GEN x, y;
     819        3493 :   if (typ(P)!=t_VEC || lg(P)!=3) pari_err_TYPE("hyperellisoncurve",P);
     820        3493 :   x = gel(P,1); y = gel(P,2);
     821        3493 :   if (typ(W)==t_POL)
     822           0 :     res = gequal(gsqr(y), poleval(W,x));
     823             :   else
     824             :   {
     825        3493 :     if (typ(W)!=t_VEC || lg(W)!=3) pari_err_TYPE("hyperellisoncurve",W);
     826        3493 :     res = gequal(gmul(y, gadd(y,poleval(gel(W,2), x))), poleval(gel(W,1), x));
     827             :   }
     828        3493 :   return gc_int(av, res);
     829             : }
     830             : 
     831             : GEN
     832          35 : hyperellordinate(GEN W, GEN x)
     833             : {
     834          35 :   pari_sp av = avma;
     835          35 :   if (typ(W)==t_POL)
     836             :   {
     837          14 :     GEN d = poleval(W,x), y;
     838          14 :     if (gequal0(d)) { return gerepilecopy(av, mkvec(d)); }
     839          14 :     if (!issquareall(d, &y)) { set_avma(av); return cgetg(1,t_VEC); }
     840           7 :     return gerepilecopy(av, mkvec2(y, gneg(y)));
     841             :   }
     842             :   else
     843             :   {
     844             :     GEN b, c, d, rd, y;
     845          21 :     if (typ(W)!=t_VEC || lg(W)!=3) pari_err_TYPE("hyperellisoncurve",W);
     846          21 :     b = poleval(gel(W,2), x); c = poleval(gel(W,1), x);
     847          21 :     d = gadd(gsqr(b), gmul2n(c, 2));
     848          21 :     if (gequal0(d)) { return gerepilecopy(av, mkvec(gmul2n(gneg(b),-1))); }
     849          14 :     if (!issquareall(d, &rd)) { set_avma(av); return cgetg(1,t_VEC); }
     850           7 :     y = gmul2n(gsub(rd, b), -1);
     851           7 :     return gerepilecopy(av, mkvec2(y, gsub(y,rd)));
     852             :   }
     853             : }
     854             : 
     855             : GEN
     856      118068 : hyperelldisc(GEN PQ)
     857             : {
     858      118068 :   pari_sp av = avma;
     859      118068 :   GEN D, H = check_hyperell(PQ);
     860             :   long d, g;
     861      118068 :   if (!H || signe(H)==0) pari_err_TYPE("hyperelldisc",PQ);
     862      118068 :   d = degpol(H); g = ((d+1)>>1)-1;
     863      118068 :   D = gmul2n(RgX_disc(H),-4*(g+1));
     864      118068 :   if (odd(d)) D = gmul(D, gsqr(leading_coeff(H)));
     865      118068 :   return gerepileupto(av, D);
     866             : }
     867             : 
     868             : static long
     869      126502 : get_ep(GEN W)
     870             : {
     871      126502 :   GEN P = gel(W,1), Q = gel(W,2);
     872      126502 :   if (signe(Q)==0) return ZX_lval(P,2);
     873       86307 :   return minss(ZX_lval(P,2), ZX_lval(Q,2));
     874             : }
     875             : 
     876             : static GEN
     877       50798 : algo51(GEN W, GEN M)
     878             : {
     879       50798 :   GEN P = gel(W,1), Q = gel(W,2);
     880             :   for(;;)
     881       10640 :   {
     882       61438 :     long vP = ZX_lval(P,2);
     883       61438 :     long vQ = signe(Q) ? ZX_lval(Q,2): vP+1;
     884             :     long r;
     885             :     /* 1 */
     886       61438 :     if (vQ==0) break;
     887             :     /* 2 */
     888       36120 :     if (vP==0)
     889             :     {
     890             :       GEN H, H1;
     891             :       /* a */
     892       29602 :       RgX_even_odd(FpX_red(P,gen_2),&H, &H1);
     893       29602 :       if (signe(H1)) break;
     894             :       /* b */
     895       14951 :       P = ZX_add(P, ZX_mul(H, ZX_sub(Q, H)));
     896       14951 :       Q = ZX_sub(Q, ZX_mulu(H, 2));
     897       14951 :       vP = ZX_lval(P,2);
     898       14951 :       vQ = signe(Q) ? ZX_lval(Q,2): vP+1;
     899             :     }
     900             :     /* 2c */
     901       21469 :     if (vP==1) break;
     902             :     /* 2d */
     903       10640 :     r = minss(2*vQ, vP)>>1;
     904       10640 :     if (M) gel(M,1) = shifti(gel(M,1), r);
     905       10640 :     P = ZX_shifti(P, -2*r);
     906       10640 :     Q = ZX_shifti(Q, -r);
     907             :   }
     908       50798 :   return mkvec2(P,Q);
     909             : }
     910             : 
     911             : static GEN
     912      103343 : algo52(GEN W, GEN c, long *pt_lambda)
     913             : {
     914             :   long lambda;
     915      103343 :   GEN P = gel(W,1), Q = gel(W,2);
     916             :   for(;;)
     917      116959 :   {
     918             :     GEN H, H1;
     919             :     /* 1 */
     920      220302 :     GEN Pc = ZX_affine(P,gen_2,c), Qc = ZX_affine(Q,gen_2,c);
     921      220302 :     long mP = ZX_lval(Pc,2), mQ = signe(Qc) ? ZX_lval(Qc,2): mP+1;
     922             :     /* 2 */
     923      220302 :     if (2*mQ <= mP) { lambda = 2*mQ; break; }
     924             :     /* 3 */
     925      188031 :     if (odd(mP)) { lambda = mP; break; }
     926             :     /* 4 */
     927      127718 :     RgX_even_odd(FpX_red(ZX_shifti(Pc, -mP),gen_2),&H, &H1);
     928      127718 :     if (signe(H1)) { lambda = mP; break; }
     929             :     /* 5 */
     930      116959 :      P = ZX_add(P, ZX_mul(H, ZX_sub(Q, H)));
     931      116959 :      Q = ZX_sub(Q, ZX_mulu(H, 2));
     932             :   }
     933      103343 :   *pt_lambda = lambda;
     934      103343 :   return mkvec2(P,Q);
     935             : }
     936             : 
     937             : static long
     938      146791 : test53(long lambda, long ep, long g)
     939             : {
     940      146791 :   return (lambda <= g+1) || (odd(g) && lambda<g+3 && ep==1);
     941             : }
     942             : 
     943             : static long
     944      189382 : test55(GEN W, long ep, long g)
     945             : {
     946      189382 :   GEN P = gel(W,1), Q = gel(W,2);
     947      189382 :   GEN Pe = FpX_red(ep ? ZX_shifti(P,-1): P, gen_2);
     948      189382 :   GEN Qe = FpX_red(ep ? ZX_shifti(Q,-1): Q, gen_2);
     949      189382 :   if (ep==0)
     950             :   {
     951      149101 :     if (signe(Qe)!=0) return ZX_val(Qe) >= (g + 3)>>1;
     952       90723 :     else return ZX_val(FpX_deriv(Pe, gen_2)) >= g+1;
     953             :   }
     954             :   else
     955       40281 :     return ZX_val(Qe) >= (g+1)>>1 && ZX_val(Pe) >= g + 1;
     956             : }
     957             : 
     958             : static GEN
     959       50798 : hyperell_reverse(GEN W, long g)
     960             : {
     961       50798 :   return mkvec2(RgXn_recip_shallow(gel(W,1),2*g+3),
     962       50798 :                 RgXn_recip_shallow(gel(W,2),g+2));
     963             : }
     964             : 
     965             : static GEN
     966       50784 : algo56(GEN W, long g)
     967             : {
     968             :   long ep;
     969       50784 :   GEN M = mkvec2(gen_1, matid(2)), Woo;
     970       50784 :   W = algo51(W, M);
     971       50784 :   Woo = hyperell_reverse(W, g);
     972       50784 :   ep = get_ep(Woo);
     973       50784 :   if (test55(Woo,ep,g))
     974             :   {
     975             :     long lambda;
     976       11737 :     Woo = algo52(Woo, gen_0, &lambda);
     977       11737 :     if (!test53(lambda,ep,g))
     978             :     {
     979        5969 :       long r = lambda>>1;
     980        5969 :       gel(M,1) = shifti(gel(M,1), r);
     981        5969 :       gel(M,2) = ZM2_mul(gel(M,2), mkmat22(gen_0, gen_1, gen_2, gen_0));
     982        5969 :       W = mkvec2(ZX_shifti(ZX_unscale(gel(Woo,1), gen_2), -2*r),
     983        5969 :                  ZX_shifti(ZX_unscale(gel(Woo,2), gen_2), -r));
     984             :     }
     985             :   }
     986             :   for(;;)
     987       24892 :   {
     988       75676 :     long j, ep = get_ep(W);
     989      189340 :     for (j = 0; j < 2; j++)
     990             :     {
     991             :       long lambda;
     992      138556 :       GEN c = utoi(j);
     993      138556 :       GEN Pc = ZX_affine(gel(W,1), gen_2, c);
     994      138556 :       GEN Qc = ZX_affine(gel(W,2), gen_2, c);
     995      138556 :       if (test55(mkvec2(Pc, Qc), ep, g))
     996             :       {
     997       91564 :         GEN Wc = algo52(W, c, &lambda);
     998       91564 :         if (!test53(lambda,ep,g))
     999             :         {
    1000       24892 :           long r = lambda>>1;
    1001       24892 :           gel(M,1) = shifti(gel(M,1), r);
    1002       24892 :           gel(M,2) = ZM2_mul(gel(M,2), mkmat22(gen_2, c, gen_0, gen_1));
    1003       24892 :           W = mkvec2(ZX_shifti(ZX_affine(gel(Wc,1), gen_2,c), -2*r),
    1004       24892 :                      ZX_shifti(ZX_affine(gel(Wc,2), gen_2,c), -r));
    1005       24892 :           break;
    1006             :         }
    1007             :       }
    1008             :     }
    1009       75676 :     if (j==2) break;
    1010             :   }
    1011       50784 :   return mkvec2(W, M);
    1012             : }
    1013             : 
    1014             : static GEN
    1015          14 : algo56bis(GEN W, long g, long inf, long thr)
    1016             : {
    1017          14 :   pari_sp av = avma;
    1018          14 :   GEN vl = cgetg(3,t_VEC);
    1019          14 :   long nl = 1;
    1020          14 :   W = algo51(W, NULL);
    1021          14 :   if (inf)
    1022             :   {
    1023          14 :     GEN Woo = hyperell_reverse(W, g);
    1024          14 :     GEN Pc = ZX_unscale(gel(W,1), gen_2);
    1025          14 :     GEN Qc = ZX_unscale(gel(W,2), gen_2);
    1026          14 :     long ep = get_ep(Woo);
    1027          14 :     if (test55(mkvec2(Pc, Qc), ep, g))
    1028             :     {
    1029             :       long lambda;
    1030          14 :       Woo = algo52(Woo, gen_0, &lambda);
    1031          14 :       if (lambda == thr)
    1032             :       {
    1033           0 :         long r = lambda>>1;
    1034           0 :         gel(vl,nl++) = mkvec2(ZX_shifti(ZX_unscale(gel(Woo,1), gen_2), -2*r),
    1035           0 :                               ZX_shifti(ZX_unscale(gel(Woo,2), gen_2), -r));
    1036             :       }
    1037             :     }
    1038             :   }
    1039             :   {
    1040          14 :     long j, ep = get_ep(W);
    1041          42 :     for (j = 0; j < 2; j++)
    1042             :     {
    1043             :       long lambda;
    1044          28 :       GEN c = utoi(j);
    1045          28 :       GEN Pc = ZX_affine(gel(W,1), gen_2, c);
    1046          28 :       GEN Qc = ZX_affine(gel(W,2), gen_2, c);
    1047          28 :       if (test55(mkvec2(Pc, Qc), ep, g))
    1048             :       {
    1049          28 :         GEN Wc = algo52(W, c, &lambda);
    1050          28 :         if (lambda == thr)
    1051             :         {
    1052           0 :           long r = lambda>>1;
    1053           0 :           gel(vl,nl++) = mkvec2(ZX_shifti(ZX_affine(gel(Wc,1), gen_2,c), -2*r),
    1054           0 :                                 ZX_shifti(ZX_affine(gel(Wc,2), gen_2,c), -r));
    1055             :         }
    1056             :       }
    1057             :     }
    1058             :   }
    1059          14 :   setlg(vl, nl);
    1060          14 :   return gerepilecopy(av,vl);
    1061             : }
    1062             : 
    1063             : /* return the (degree 2) apolar invariant (the nth transvectant of P and P) */
    1064             : static GEN
    1065          84 : ZX_apolar(GEN P, long n)
    1066             : {
    1067          84 :   pari_sp av = avma;
    1068          84 :   long d = degpol(P), i;
    1069          84 :   GEN s = gen_0, g = cgetg(n+2,t_VEC);
    1070          84 :   gel(g,1) = gen_1;
    1071         588 :   for (i = 1; i <= n; i++) gel(g,i+1) = muliu(gel(g,i),i); /* g[i+1] = i! */
    1072         658 :   for (i = n-d; i <= d; i++)
    1073             :   {
    1074         574 :      GEN a = mulii(mulii(gel(g,i+1),gel(g,n-i+1)),
    1075         574 :                    mulii(gel(P,i+2),gel(P,n-i+2)));
    1076         574 :      s = odd(i)? subii(s, a): addii(s, a);
    1077             :   }
    1078          84 :   return gerepileuptoint(av,s);
    1079             : }
    1080             : 
    1081             : static GEN
    1082       52135 : algo57(GEN F, long g, GEN pr)
    1083             : {
    1084             :   long i, l;
    1085       52135 :   GEN D, C = content(F);
    1086       52135 :   GEN e = gel(core2(shifti(C,-vali(C))),2);
    1087       52135 :   GEN M = mkvec2(e, matid(2));
    1088       52135 :   long minvd = (2*g+1)>>(odd(g) ? 4:2);
    1089       52135 :   F = ZX_Z_divexact(F, sqri(e));
    1090       52135 :   D = absi(hyperelldisc(F));
    1091       52135 :   if (!pr)
    1092             :   {
    1093          84 :     GEN A = gcdii(D, ZX_apolar(F, 2*g+2));
    1094          84 :     pr = gel(factor(shifti(A, -vali(A))),1);
    1095             :   }
    1096       52135 :   l = lg(pr);
    1097      311008 :   for (i = 1; i < l; i++)
    1098             :   {
    1099             :     long ep;
    1100      258873 :     GEN p = gel(pr, i), ps2 = shifti(p,-1), Fe;
    1101      258873 :     if (equaliu(p,2) || Z_pval(D,p) < minvd) continue;
    1102      196658 :     ep = ZX_pvalrem(F,p, &Fe); Fe = FpX_red(Fe, p);
    1103      196658 :     if (degpol(Fe) < g+1+ep)
    1104             :     {
    1105        6406 :       GEN Fi = ZX_unscale(RgXn_recip_shallow(F,2*g+3), p);
    1106        6406 :       long lambda = ZX_pval(Fi,p);
    1107        6406 :       if (!test53(lambda,ep,g))
    1108             :       {
    1109        3815 :         GEN ppr = powiu(p,lambda>>1);
    1110        3815 :         F = ZX_Z_divexact(Fi,sqri(ppr));
    1111        3815 :         gel(M,1) = mulii(gel(M,1), ppr);
    1112        3815 :         gel(M,2) = ZM2_mul(gel(M,2), mkmat22(gen_0,gen_1,p,gen_0));
    1113             :       }
    1114             :     }
    1115             :     for(;;)
    1116       24997 :     {
    1117             :       GEN Fe, R;
    1118      221655 :       long j, lR, ep = ZX_pvalrem(F,p, &Fe);
    1119      221655 :       R = FpX_roots_mult(FpX_red(Fe, p), g+2-ep, p); lR = lg(R);
    1120      233742 :       for (j = 1; j<lR; j++)
    1121             :       {
    1122       37084 :         GEN c = Fp_center(gel(R,j), p, ps2);
    1123       37084 :         GEN Fi = ZX_affine(F,p,c);
    1124       37084 :         long lambda = ZX_pval(Fi,p);
    1125       37084 :         if (!test53(lambda,ep,g))
    1126             :         {
    1127       24997 :           GEN ppr = powiu(p,lambda>>1);
    1128       24997 :           F = ZX_Z_divexact(Fi, sqri(ppr));
    1129       24997 :           gel(M,1) = mulii(gel(M,1), ppr);
    1130       24997 :           gel(M,2) = ZM2_mul(gel(M,2), mkmat22(p,c,gen_0,gen_1));
    1131       24997 :           break;
    1132             :         }
    1133             :       }
    1134      221655 :       if (j==lR) break;
    1135             :     }
    1136             :   }
    1137       52135 :   return mkvec2(F, M);
    1138             : }
    1139             : 
    1140             : /* if inf=0, ignore point at infinity */
    1141             : static GEN
    1142          42 : algo57bis(GEN F, long g, GEN p, long inf, long thr)
    1143             : {
    1144          42 :   pari_sp av = avma;
    1145          42 :   GEN vl = cgetg(3,t_VEC), Fe;
    1146          42 :   long nl = 1, ep = ZX_pvalrem(F,p, &Fe);
    1147          42 :   Fe = FpX_red(Fe, p);
    1148             :   {
    1149          42 :     GEN R = FpX_roots_mult(Fe, thr-ep, p);
    1150          42 :     long j, lR = lg(R);
    1151          63 :     for (j = 1; j<lR; j++)
    1152             :     {
    1153          21 :       GEN Fj = ZX_affine(F, p, gel(R,j));
    1154          21 :       long lambda = ZX_pvalrem(Fj, p, &Fj);
    1155          21 :       if (lambda == thr) gel(vl,nl++) = odd(lambda)? ZX_Z_mul(Fj, p): Fj;
    1156             :     }
    1157             :   }
    1158          42 :   if (inf==1 && 2*g+2-degpol(Fe) >= thr-ep)
    1159             :   {
    1160           0 :     GEN Fj = ZX_unscale(RgXn_recip_shallow(F,2*g+3), p);
    1161           0 :     long lambda = ZX_pvalrem(Fj, p, &Fj);
    1162           0 :     if (lambda == thr) gel(vl,nl++) = odd(lambda)? ZX_Z_mul(Fj, p): Fj;
    1163             :   }
    1164          42 :   setlg(vl, nl);
    1165          42 :   return gerepilecopy(av,vl);
    1166             : }
    1167             : 
    1168             : static GEN
    1169          56 : next_model(GEN G, long g, GEN p, long inf, long thr)
    1170             : {
    1171          70 :   return equaliu(p,2) ? algo56bis(G, g,    inf, thr)
    1172          70 :                       : algo57bis(G, g, p, inf, thr);
    1173             : }
    1174             : 
    1175             : static GEN
    1176           0 : get_extremal(GEN F, GEN G, long g, GEN p)
    1177             : {
    1178             :   while (1)
    1179           0 :   {
    1180             :     GEN Wi;
    1181           0 :     Wi = next_model(G, g, p, 0, g+2);
    1182           0 :     if (lg(Wi)==1) return F;
    1183           0 :     F = gel(Wi,1);
    1184           0 :     Wi = next_model(F, g, p, 0, g+1);
    1185           0 :     if (lg(Wi)==1) return F;
    1186           0 :     G = gel(Wi,1);
    1187             :   }
    1188             : }
    1189             : 
    1190             : GEN
    1191          63 : hyperellextremalmodels(GEN F, long g, GEN p)
    1192             : {
    1193          63 :   pari_sp av = avma;
    1194             :   GEN R, W;
    1195             :   long l;
    1196          63 :   if (equaliu(p,2))
    1197             :   {
    1198          14 :     if (get_ep(F)>0) return mkvec(F);
    1199             :   } else
    1200          49 :     if( ZX_pval(F,p) > 0) return mkvec(F);
    1201          56 :   W = next_model(F, g, p, 1, g+1); l = lg(W);
    1202          56 :   if (l==1) { set_avma(av); return mkvec(F); }
    1203           0 :   R = cgetg(3, t_VEC);
    1204           0 :   gel(R,1) = get_extremal(F, gel(W,1), g, p);
    1205           0 :   gel(R,2) = l==3 ? get_extremal(F, gel(W,2), g, p) : F;
    1206           0 :   if (gel(R,2) == gel(R,1)) setlg(R,2);
    1207           0 :   return gerepilecopy(av, R);
    1208             : }
    1209             : 
    1210             : static GEN
    1211      301955 : RgX_RgM2_eval(GEN P, GEN A, GEN Bp, long d)
    1212             : {
    1213      301955 :   if (signe(P)==0)
    1214       78952 :     return P;
    1215             :   else
    1216             :   {
    1217      223003 :     long dP = degpol(P);
    1218      223003 :     GEN R = RgX_homogenous_evalpow(P, A, Bp);
    1219      223003 :     if (d > dP)
    1220       16948 :       R = gmul(R, gel(Bp,1+d-dP));
    1221      223003 :     return R;
    1222             :   }
    1223             : }
    1224             : 
    1225             : static GEN
    1226       52149 : minimalmodel_merge(GEN W2, GEN Modd, long g, long v)
    1227             : {
    1228       52149 :   GEN P = gel(W2,1), Q = gel(W2,2);
    1229       52149 :   GEN e = gel(Modd,1), M = gel(Modd,2);
    1230       52149 :   GEN A = deg1pol_shallow(gcoeff(M,1,1), gcoeff(M,1,2), v);
    1231       52149 :   GEN B = deg1pol_shallow(gcoeff(M,2,1), gcoeff(M,2,2), v);
    1232       52149 :   GEN Bp = gpowers(B, 2*g+2);
    1233       52149 :   long f = mod4(e)==1 ? 1: -1;
    1234       52149 :   GEN m = shifti(f > 0 ? subui(1,e): addui(1,e), -2);
    1235       52149 :   GEN  m24 = subii(shifti(m,1), shifti(sqri(m),2));
    1236       52149 :   P = RgX_RgM2_eval(P, A, Bp, 2*g+2);
    1237       52149 :   Q = RgX_RgM2_eval(Q, A, Bp, g+1);
    1238       52149 :   P = ZX_Z_divexact(ZX_add(P, ZX_Z_mul(ZX_sqr(Q), m24)),sqri(e));
    1239       52149 :   if (f < 0) Q = ZX_neg(Q);
    1240       52149 :   return mkvec2(P,Q);
    1241             : }
    1242             : 
    1243             : static GEN
    1244      104284 : hyperell_redQ(GEN W)
    1245             : {
    1246      104284 :   GEN P = gel(W,1), Q = gel(W,2);
    1247      104284 :   GEN Pr, Qr = FpX_red(Q, gen_2);
    1248      104284 :   Pr = ZX_add(P, ZX_shifti(ZX_mul(ZX_sub(Q, Qr),ZX_add(Q, Qr)),-2));
    1249      104284 :   return mkvec2(Pr, Qr);
    1250             : }
    1251             : 
    1252             : static GEN
    1253       50735 : minimalmodel_getH(GEN W, GEN Qn, GEN e, GEN M, long g, long v)
    1254             : {
    1255       50735 :   GEN Q = gel(W,2);
    1256       50735 :   GEN A = deg1pol_shallow(gcoeff(M,1,1), gcoeff(M,1,2), v);
    1257       50735 :   GEN B = deg1pol_shallow(gcoeff(M,2,1), gcoeff(M,2,2), v);
    1258       50735 :   GEN Bp = gpowers(B, g+1);
    1259       50735 :   return ZX_shifti(ZX_sub(ZX_Z_mul(Qn,e),RgX_RgM2_eval(Q, A, Bp, g+1)), -1);
    1260             : }
    1261             : 
    1262             : static void
    1263       52191 : check_hyperell_Q(const char *fun, GEN *pW, GEN *pF)
    1264             : {
    1265       52191 :   GEN W = *pW, F = check_hyperell(W);
    1266             :   long v, d;
    1267       52191 :   if (!F || !signe(F) || !RgX_is_ZX(F)) pari_err_TYPE(fun, W);
    1268       52184 :   if (!signe(ZX_disc(F))) pari_err_DOMAIN(fun,"disc(W)","==",gen_0,W);
    1269       52177 :   v = varn(F); d = degpol(F);
    1270       52177 :   if (typ(W)==t_POL) W = mkvec2(W, pol_0(v));
    1271             :   else
    1272             :   {
    1273       43603 :     GEN P = gel(W, 1), Q = gel(W, 2);
    1274       43603 :     long g = ((d+1) >> 1) - 1;
    1275       43603 :     if (typ(P)!=t_POL) P = scalarpol_shallow(P, v);
    1276       43603 :     if (typ(Q)!=t_POL) Q = scalarpol_shallow(Q, v);
    1277       43603 :     if (!RgX_is_ZX(P) || !RgX_is_ZX(Q)) pari_err_TYPE(fun,W);
    1278       43603 :     if (degpol(P) > 2*g+2) pari_err_DOMAIN(fun, "deg(P)", ">", utoi(2*g+2), P);
    1279       43603 :     if (degpol(Q) > g+1) pari_err_DOMAIN(fun, "deg(Q)", ">", utoi(g+1), Q);
    1280       43603 :     W = mkvec2(P, Q);
    1281             :   }
    1282       52177 :   if (d < 3) pari_err_DOMAIN(fun, "genus", "=", gen_0, gen_0);
    1283       52163 :   *pW = W; *pF = F;
    1284       52163 : }
    1285             : 
    1286             : GEN
    1287       52149 : hyperellminimalmodel(GEN W, GEN *pM, GEN pr)
    1288             : {
    1289       52149 :   pari_sp av = avma;
    1290             :   GEN Wr, F, WM2, F2, W2, M2, Modd, Wf, ef, Mf, Hf;
    1291             :   long d, g, v;
    1292       52149 :   check_hyperell_Q("hyperellminimalmodel",&W, &F);
    1293       52149 :   if (pr && (!is_vec_t(typ(pr)) || !RgV_is_ZV(pr)))
    1294          14 :     pari_err_TYPE("hyperellminimalmodel",pr);
    1295       52135 :   d = degpol(F); g = ((d+1)>>1)-1; v = varn(F);
    1296       52135 :   Wr = hyperell_redQ(W);
    1297       52135 :   if (!pr || RgV_isin(pr, gen_2))
    1298             :   {
    1299       50784 :     WM2 = algo56(Wr,g); W2 = gel(WM2, 1); M2 = gel(WM2, 2);
    1300       50784 :     F2 = check_hyperell(W2);
    1301             :   }
    1302             :   else
    1303             :   {
    1304        1351 :     W2 = Wr; F2 = F; M2 = mkvec2(gen_1, matid(2));
    1305             :   }
    1306       52135 :   Modd = gel(algo57(F2, g, pr), 2);
    1307       52135 :   Wf = hyperell_redQ(minimalmodel_merge(W2, Modd, g, v));
    1308       52135 :   if (!pM) return gerepilecopy(av, Wf);
    1309       50721 :   ef = mulii(gel(M2,1), gel(Modd,1));
    1310       50721 :   Mf = ZM2_mul(gel(M2,2), gel(Modd,2));
    1311       50721 :   Hf = minimalmodel_getH(W, gel(Wf,2), ef, Mf, g, v);
    1312       50721 :   *pM =  mkvec3(ef, Mf, Hf);
    1313       50721 :   return gc_all(av, 2, &Wf, pM);
    1314             : }
    1315             : 
    1316             : GEN
    1317          14 : hyperellminimaldisc(GEN W, GEN pr)
    1318             : {
    1319          14 :   pari_sp av = avma;
    1320          14 :   GEN C = hyperellminimalmodel(W, NULL, pr);
    1321          14 :   return gerepileuptoint(av, hyperelldisc(C));
    1322             : }
    1323             : 
    1324             : static GEN
    1325          35 : redqfbsplit(GEN a, GEN b, GEN c, GEN d)
    1326             : {
    1327          35 :   GEN p = subii(d,b), q = shifti(a,1);
    1328          35 :   GEN U, Q, u, v, w = bezout(p, q, &u, &v);
    1329             : 
    1330          35 :   if (!equali1(w)) { p = diviiexact(p, w); q = diviiexact(q, w); }
    1331          35 :   U = mkmat22(p, negi(v), q, u);
    1332          35 :   Q = qfb_ZM_apply(mkvec3(a,b,c), U);
    1333          35 :   b = gel(Q, 2); c = gel(Q,3);
    1334          35 :   if (signe(b) < 0) gel(U,2) = mkcol2(v, negi(u));
    1335          35 :   gel(U,2) = ZC_lincomb(gen_1, truedivii(negi(c), d), gel(U,2), gel(U,1));
    1336          35 :   return U;
    1337             : }
    1338             : 
    1339             : static GEN
    1340       16386 : polreduce(GEN P, GEN M)
    1341             : {
    1342       16386 :   long v = varn(P), dP = degpol(P), d = odd(dP) ? dP+1: dP;
    1343       16386 :   GEN A = deg1pol_shallow(gcoeff(M,1,1), gcoeff(M,1,2), v);
    1344       16386 :   GEN B = deg1pol_shallow(gcoeff(M,2,1), gcoeff(M,2,2), v);
    1345       16386 :   return RgX_RgM2_eval(P, A, gpowers(B, d), d);
    1346             : }
    1347             : 
    1348             : /* assume deg(P) > 2 */
    1349             : static GEN
    1350        8193 : red_Cremona_Stoll(GEN P, GEN *pM)
    1351             : {
    1352             :   GEN q1, q2, q3, M, R;
    1353        8193 :   long i, prec = nbits2prec(2*gexpo(P)) + EXTRAPRECWORD, d = degpol(P);
    1354        8193 :   GEN dP = ZX_deriv(P);
    1355             :   for (;;)
    1356           0 :   {
    1357        8193 :     GEN r = QX_complex_roots(P, prec);
    1358        8193 :     q1 = gen_0; q2 = gen_0; q3 = gen_0;
    1359       41000 :     for (i = 1; i <= d; i++)
    1360             :     {
    1361       32807 :       GEN ri = gel(r,i);
    1362       32807 :       GEN s = ginv(gabs(RgX_cxeval(dP,ri,NULL), prec));
    1363       32807 :       if (d!=4) s = gpow(s, gdivgs(gen_2,d-2), prec);
    1364       32807 :       q1 = gadd(q1, s);
    1365       32807 :       q2 = gsub(q2, gmul(real_i(ri), s));
    1366       32807 :       q3 = gadd(q3, gmul(gnorm(ri), s));
    1367             :     }
    1368        8193 :     M = lllgram(mkmat22(q1,q2,q2,q3));
    1369        8193 :     if (M && lg(M) == 3) break;
    1370           0 :     prec = precdbl(prec);
    1371             :   }
    1372        8193 :   R = polreduce(P, M);
    1373        8193 :   *pM = M;
    1374        8193 :   return R;
    1375             : }
    1376             : 
    1377             : /* assume deg(P) > 2 */
    1378             : GEN
    1379        8193 : ZX_hyperellred(GEN P, GEN *pM)
    1380             : {
    1381        8193 :   pari_sp av = avma;
    1382        8193 :   long d = degpol(P);
    1383             :   GEN q1, q2, q3, D, vD;
    1384        8193 :   GEN a = gel(P,d+2), b = gel(P,d+1), c = gel(P, d);
    1385             :   GEN M, R, M2;
    1386             : 
    1387        8193 :   q1 = muliu(sqri(a), d);
    1388        8193 :   q2 = shifti(mulii(a,b), 1);
    1389        8193 :   q3 = subii(sqri(b), shifti(mulii(a,c), 1));
    1390        8193 :   D = gcdii(gcdii(q1, q2), q3);
    1391        8193 :   if (!equali1(D))
    1392             :   {
    1393        8172 :     q1 = diviiexact(q1, D);
    1394        8172 :     q2 = diviiexact(q2, D);
    1395        8172 :     q3 = diviiexact(q3, D);
    1396             :   }
    1397        8193 :   D = qfb_disc3(q1, q2, q3);
    1398        8193 :   if (!signe(D))
    1399          49 :     M = mkmat22(gen_1, truedivii(negi(q2),shifti(q1,1)), gen_0, gen_1);
    1400        8144 :   else if (issquareall(D,&vD))
    1401          35 :     M = redqfbsplit(q1, q2, q3, vD);
    1402             :   else
    1403        8109 :     M = gel(qfbredsl2(mkqfb(q1,q2,q3,D), NULL), 2);
    1404        8193 :   R = red_Cremona_Stoll(polreduce(P, M), &M2);
    1405        8193 :   if (pM) *pM = gmul(M, M2);
    1406        8193 :   return gc_all(av, pM ? 2: 1, &R, pM);
    1407             : }
    1408             : 
    1409             : GEN
    1410          42 : hyperellred(GEN W, GEN *pM)
    1411             : {
    1412          42 :   pari_sp av = avma;
    1413             :   long g, d, v;
    1414             :   GEN F, M, Wf, Hf;
    1415          42 :   check_hyperell_Q("hyperellred", &W, &F);
    1416          14 :   d = degpol(F); g = ((d+1)>>1)-1; v = varn(F);
    1417          14 :   (void) ZX_hyperellred(F, &M);
    1418          14 :   Wf = hyperell_redQ(minimalmodel_merge(W, mkvec2(gen_1, M), g, v));
    1419          14 :   Hf = minimalmodel_getH(W, gel(Wf,2), gen_1, M, g, v);
    1420          14 :   if (pM) *pM = mkvec3(gen_1, M, Hf);
    1421          14 :   return gc_all(av, pM ? 2: 1, &Wf, pM);
    1422             : }
    1423             : 
    1424             : static void
    1425       65296 : check_hyperell_Rg(const char *fun, GEN *pW, GEN *pF)
    1426             : {
    1427       65296 :   GEN W = *pW, F = check_hyperell(W);
    1428             :   long v;
    1429       65296 :   if (!F)
    1430           7 :     pari_err_TYPE(fun, W);
    1431       65289 :   if (degpol(F) <= 0) pari_err_CONSTPOL(fun);
    1432       65282 :   v = varn(F);
    1433       65282 :   if (typ(W)==t_POL) W = mkvec2(W, pol_0(v));
    1434             :   else
    1435             :   {
    1436       65254 :     GEN P = gel(W, 1), Q = gel(W, 2);
    1437       65254 :     long g = ((degpol(F)+1)>>1)-1;
    1438       65254 :     if( typ(P)!=t_POL) P = scalarpol(P, v);
    1439       65254 :     if( typ(Q)!=t_POL) Q = scalarpol(Q, v);
    1440       65254 :     if (degpol(P) > 2*g+2)
    1441           0 :       pari_err_DOMAIN(fun, "poldegree(P)", ">", utoi(2*g+2), P);
    1442       65254 :     if (degpol(Q) > g+1)
    1443           0 :       pari_err_DOMAIN(fun, "poldegree(Q)", ">", utoi(g+1), Q);
    1444             : 
    1445       65254 :     W = mkvec2(P, Q);
    1446             :   }
    1447       65282 :   if (pF) *pF = F;
    1448       65282 :   *pW = W;
    1449       65282 : }
    1450             : 
    1451             : static void
    1452       65282 : check_hyperell_vc(const char *fun, GEN C, long v, GEN *e, GEN *M, GEN *H)
    1453             : {
    1454       65282 :   if (typ(C) != t_VEC || lg(C) != 4) pari_err_TYPE(fun,C);
    1455       65275 :   *e = gel(C,1); *M = gel(C,2); *H = gel(C,3);
    1456       65275 :   if (typ(*M) != t_MAT || lg(*M) != 3 || lgcols(*M) != 3) pari_err_TYPE(fun,C);
    1457       65268 :   if (typ(*H)!=t_POL || varncmp(varn(*H),v) > 0) *H = scalarpol_shallow(*H,v);
    1458       65268 : }
    1459             : 
    1460             : GEN
    1461       65296 : hyperellchangecurve(GEN W, GEN C)
    1462             : {
    1463       65296 :   pari_sp av = avma;
    1464             :   GEN F, P, Q, A, B, Bp, e, M, H;
    1465             :   long d, g, v;
    1466       65296 :   check_hyperell_Rg("hyperellchangecurve",&W,&F);
    1467       65282 :   P = gel(W,1); Q = gel(W,2);
    1468       65282 :   d = degpol(F); g = ((d+1)>>1)-1; v = varn(F);
    1469       65282 :   check_hyperell_vc("hyperellchangecurve", C, v, &e, &M, &H);
    1470       65268 :   if (varncmp(gvar(M),v) <= 0)
    1471           0 :     pari_err_PRIORITY("hyperellchangecurve",M,"<=",v);
    1472       65268 :   A = deg1pol_shallow(gcoeff(M,1,1), gcoeff(M,1,2), v);
    1473       65268 :   B = deg1pol_shallow(gcoeff(M,2,1), gcoeff(M,2,2), v);
    1474       65268 :   Bp = gpowers(B, 2*g+2);
    1475       65268 :   P = RgX_RgM2_eval(P, A, Bp, 2*g+2);
    1476       65268 :   Q = RgX_RgM2_eval(Q, A, Bp, g+1);
    1477       65268 :   P = RgX_Rg_div(RgX_sub(P, RgX_mul(H,RgX_add(Q,H))), gsqr(e));
    1478       65268 :   Q = RgX_Rg_div(RgX_add(Q, RgX_mul2n(H,1)), e);
    1479       65268 :   return gerepilecopy(av, mkvec2(P,Q));
    1480             : }

Generated by: LCOV version 1.16