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 - bb_group.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.18.0 lcov report (development 29806-4d001396c7) Lines: 553 587 94.2 %
Date: 2024-12-21 09:08:57 Functions: 37 37 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Copyright (C) 2000-2004  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             : /**             GENERIC ALGORITHMS ON BLACKBOX GROUP                  **/
      18             : /**                                                                   **/
      19             : /***********************************************************************/
      20             : #include "pari.h"
      21             : #include "paripriv.h"
      22             : #undef pow /* AIX: pow(a,b) is a macro, wrongly expanded on grp->pow(a,b,c) */
      23             : 
      24             : #define DEBUGLEVEL DEBUGLEVEL_bb_group
      25             : 
      26             : /***********************************************************************/
      27             : /**                                                                   **/
      28             : /**                    POWERING                                       **/
      29             : /**                                                                   **/
      30             : /***********************************************************************/
      31             : 
      32             : /* return (n>>(i+1-l)) & ((1<<l)-1) */
      33             : static ulong
      34     8294616 : int_block(GEN n, long i, long l)
      35             : {
      36     8294616 :   long q = divsBIL(i), r = remsBIL(i)+1, lr;
      37     8295311 :   GEN nw = int_W(n, q);
      38     8295311 :   ulong w = (ulong) *nw, w2;
      39     8295311 :   if (r>=l) return (w>>(r-l))&((1UL<<l)-1);
      40      570075 :   w &= (1UL<<r)-1; lr = l-r;
      41      570075 :   w2 = (ulong) *int_precW(nw); w2 >>= (BITS_IN_LONG-lr);
      42      570075 :   return (w<<lr)|w2;
      43             : }
      44             : 
      45             : /* assume n != 0, t_INT. Compute x^|n| using sliding window powering */
      46             : static GEN
      47     9294403 : sliding_window_powu(GEN x, ulong n, long e, void *E, GEN (*sqr)(void*,GEN),
      48             :                                                      GEN (*mul)(void*,GEN,GEN))
      49             : {
      50     9294403 :   long i, l = expu(n), u = (1UL<<(e-1));
      51     9294091 :   GEN tab = cgetg(1+u, t_VEC), x2 = sqr(E, x), z = NULL;
      52             : 
      53     9298158 :   gel(tab, 1) = x;
      54    24598471 :   for (i = 2; i <= u; i++) gel(tab,i) = mul(E, gel(tab,i-1), x2);
      55    68867971 :   while (l >= 0)
      56             :   {
      57             :     long w, v;
      58             :     GEN tw;
      59    59698641 :     if (e > l+1) e = l+1;
      60    59698641 :     w = (n>>(l+1-e)) & ((1UL<<e)-1); v = vals(w); l-=e;
      61    59712519 :     tw = gel(tab, 1 + (w>>(v+1)));
      62    59712519 :     if (!z) z = tw;
      63             :     else
      64             :     {
      65   137208643 :       for (i = 1; i <= e-v; i++) z = sqr(E, z);
      66    50301294 :       z = mul(E, z, tw);
      67             :     }
      68    97280429 :     for (i = 1; i <= v; i++) z = sqr(E, z);
      69   109707184 :     while (l >= 0)
      70             :     {
      71   100647978 :       if (n&(1UL<<l)) break;
      72    50122246 :       z = sqr(E, z); l--;
      73             :     }
      74             :   }
      75     9169330 :   return z;
      76             : }
      77             : 
      78             : /* assume n != 0, t_INT. Compute x^|n| using sliding window powering */
      79             : static GEN
      80      224198 : sliding_window_pow(GEN x, GEN n, long e, void *E, GEN (*sqr)(void*,GEN),
      81             :                                                   GEN (*mul)(void*,GEN,GEN))
      82             : {
      83             :   pari_sp av;
      84      224198 :   long i, l = expi(n), u = (1UL<<(e-1));
      85      224198 :   GEN tab = cgetg(1+u, t_VEC);
      86      224198 :   GEN x2 = sqr(E, x), z = NULL;
      87             : 
      88      224194 :   gel(tab, 1) = x;
      89     2980813 :   for (i=2; i<=u; i++) gel(tab,i) = mul(E, gel(tab,i-1), x2);
      90      224200 :   av = avma;
      91     7938437 :   while (l >= 0)
      92             :   {
      93             :     long w, v;
      94             :     GEN tw;
      95     7688907 :     if (e > l+1) e = l+1;
      96     7688907 :     w = int_block(n,l,e); v = vals(w); l-=e;
      97     7688495 :     tw = gel(tab, 1+(w>>(v+1)));
      98     7688495 :     if (!z) z = tw;
      99             :     else
     100             :     {
     101    40689680 :       for (i = 1; i <= e-v; i++) z = sqr(E, z);
     102     7461510 :       z = mul(E, z, tw);
     103             :     }
     104    14612048 :     for (i = 1; i <= v; i++) z = sqr(E, z);
     105    20668884 :     while (l >= 0)
     106             :     {
     107    20419647 :       if (gc_needed(av,1))
     108             :       {
     109        1041 :         if (DEBUGMEM>1) pari_warn(warnmem,"sliding_window_pow (%ld)", l);
     110        1041 :         z = gerepilecopy(av, z);
     111             :       }
     112    20419647 :       if (int_bit(n,l)) break;
     113    12939295 :       z = sqr(E, z); l--;
     114             :     }
     115             :   }
     116      249530 :   return z;
     117             : }
     118             : 
     119             : /* assume n != 0, t_INT. Compute x^|n| using leftright binary powering */
     120             : static GEN
     121   103716771 : leftright_binary_powu(GEN x, ulong n, void *E, GEN (*sqr)(void*,GEN),
     122             :                                                GEN (*mul)(void*,GEN,GEN))
     123             : {
     124   103716771 :   pari_sp av = avma;
     125             :   GEN  y;
     126             :   int j;
     127             : 
     128   103716771 :   if (n == 1) return x;
     129   103716771 :   y = x; j = 1+bfffo(n);
     130             :   /* normalize, i.e set highest bit to 1 (we know n != 0) */
     131   103716771 :   n<<=j; j = BITS_IN_LONG-j;
     132             :   /* first bit is now implicit */
     133   335375053 :   for (; j; n<<=1,j--)
     134             :   {
     135   231705474 :     y = sqr(E,y);
     136   231662290 :     if (n & HIGHBIT) y = mul(E,y,x); /* first bit set: multiply by base */
     137   231648407 :     if (gc_needed(av,1))
     138             :     {
     139           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"leftright_powu (%d)", j);
     140           0 :       y = gerepilecopy(av, y);
     141             :     }
     142             :   }
     143   103669579 :   return y;
     144             : }
     145             : 
     146             : GEN
     147   115963789 : gen_powu_i(GEN x, ulong n, void *E, GEN (*sqr)(void*,GEN),
     148             :                                     GEN (*mul)(void*,GEN,GEN))
     149             : {
     150   115963789 :   if (n == 1) return x;
     151   113007493 :   if (n < 512)
     152   103715842 :     return leftright_binary_powu(x, n, E, sqr, mul);
     153             :   else
     154     9291651 :     return sliding_window_powu(x, n, n < (1UL<<25)? 2: 3, E, sqr, mul);
     155             : }
     156             : 
     157             : GEN
     158      204892 : gen_powu(GEN x, ulong n, void *E, GEN (*sqr)(void*,GEN),
     159             :                                   GEN (*mul)(void*,GEN,GEN))
     160             : {
     161      204892 :   pari_sp av = avma;
     162      204892 :   if (n == 1) return gcopy(x);
     163      171272 :   return gerepilecopy(av, gen_powu_i(x,n,E,sqr,mul));
     164             : }
     165             : 
     166             : GEN
     167    44881592 : gen_pow_i(GEN x, GEN n, void *E, GEN (*sqr)(void*,GEN),
     168             :                                  GEN (*mul)(void*,GEN,GEN))
     169             : {
     170             :   long l, e;
     171    44881592 :   if (lgefint(n)==3) return gen_powu_i(x, uel(n,2), E, sqr, mul);
     172      224196 :   l = expi(n);
     173      224198 :   if      (l<=64)  e = 3;
     174      165986 :   else if (l<=160) e = 4;
     175       85760 :   else if (l<=384) e = 5;
     176       22999 :   else if (l<=896) e = 6;
     177       11528 :   else             e = 7;
     178      224198 :   return sliding_window_pow(x, n, e, E, sqr, mul);
     179             : }
     180             : 
     181             : GEN
     182    15252482 : gen_pow(GEN x, GEN n, void *E, GEN (*sqr)(void*,GEN),
     183             :                                GEN (*mul)(void*,GEN,GEN))
     184             : {
     185    15252482 :   pari_sp av = avma;
     186    15252482 :   return gerepilecopy(av, gen_pow_i(x,n,E,sqr,mul));
     187             : }
     188             : 
     189             : /* assume n > 0. Compute x^n using left-right binary powering */
     190             : GEN
     191     1325034 : gen_powu_fold_i(GEN x, ulong n, void *E, GEN  (*sqr)(void*,GEN),
     192             :                                          GEN (*msqr)(void*,GEN))
     193             : {
     194     1325034 :   pari_sp av = avma;
     195             :   GEN y;
     196             :   int j;
     197             : 
     198     1325034 :   if (n == 1) return x;
     199     1325034 :   y = x; j = 1+bfffo(n);
     200             :   /* normalize, i.e set highest bit to 1 (we know n != 0) */
     201     1325034 :   n<<=j; j = BITS_IN_LONG-j;
     202             :   /* first bit is now implicit */
     203     5894467 :   for (; j; n<<=1,j--)
     204             :   {
     205     4569506 :     if (n & HIGHBIT) y = msqr(E,y); /* first bit set: multiply by base */
     206     3346083 :     else y = sqr(E,y);
     207     4569446 :     if (gc_needed(av,1))
     208             :     {
     209           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"gen_powu_fold (%d)", j);
     210           0 :       y = gerepilecopy(av, y);
     211             :     }
     212             :   }
     213     1324961 :   return y;
     214             : }
     215             : GEN
     216        5026 : gen_powu_fold(GEN x, ulong n, void *E, GEN (*sqr)(void*,GEN),
     217             :                                        GEN (*msqr)(void*,GEN))
     218             : {
     219        5026 :   pari_sp av = avma;
     220        5026 :   if (n == 1) return gcopy(x);
     221        5026 :   return gerepilecopy(av, gen_powu_fold_i(x,n,E,sqr,msqr));
     222             : }
     223             : 
     224             : /* assume N != 0, t_INT. Compute x^|N| using left-right binary powering */
     225             : GEN
     226      688594 : gen_pow_fold_i(GEN x, GEN N, void *E, GEN (*sqr)(void*,GEN),
     227             :                                       GEN (*msqr)(void*,GEN))
     228             : {
     229      688594 :   long ln = lgefint(N);
     230      688594 :   if (ln == 3) return gen_powu_fold_i(x, N[2], E, sqr, msqr);
     231             :   else
     232             :   {
     233      145785 :     GEN nd = int_MSW(N), y = x;
     234      145785 :     ulong n = *nd;
     235             :     long i;
     236             :     int j;
     237      145785 :     pari_sp av = avma;
     238             : 
     239      145785 :     if (n == 1)
     240        7355 :       j = 0;
     241             :     else
     242             :     {
     243      138430 :       j = 1+bfffo(n); /* < BIL */
     244             :       /* normalize, i.e set highest bit to 1 (we know n != 0) */
     245      138430 :       n <<= j; j = BITS_IN_LONG - j;
     246             :     }
     247             :     /* first bit is now implicit */
     248      145785 :     for (i=ln-2;;)
     249             :     {
     250    54333022 :       for (; j; n<<=1,j--)
     251             :       {
     252    53537418 :         if (n & HIGHBIT) y = msqr(E,y); /* first bit set: multiply by base */
     253    37417344 :         else y = sqr(E,y);
     254    53572350 :         if (gc_needed(av,1))
     255             :         {
     256           0 :           if (DEBUGMEM>1) pari_warn(warnmem,"gen_pow_fold (%ld,%d)", i,j);
     257           0 :           y = gerepilecopy(av, y);
     258             :         }
     259             :       }
     260      843841 :       if (--i == 0) return y;
     261      883753 :       nd = int_precW(nd);
     262      883753 :       n = *nd; j = BITS_IN_LONG;
     263             :     }
     264             :   }
     265             : }
     266             : GEN
     267      542809 : gen_pow_fold(GEN x, GEN n, void *E, GEN (*sqr)(void*,GEN),
     268             :                                     GEN (*msqr)(void*,GEN))
     269             : {
     270      542809 :   pari_sp av = avma;
     271      542809 :   return gerepilecopy(av, gen_pow_fold_i(x,n,E,sqr,msqr));
     272             : }
     273             : 
     274             : GEN
     275         147 : gen_pow_init(GEN x, GEN n, long k, void *E, GEN (*sqr)(void*,GEN), GEN (*mul)(void*,GEN,GEN))
     276             : {
     277         147 :   long i, j, l = expi(n);
     278         147 :   long m = 1UL<<(k-1);
     279         147 :   GEN x2 = sqr(E, x), y = gcopy(x);
     280         147 :   GEN R = cgetg(m+1, t_VEC);
     281         644 :   for(i = 1; i <= m; i++)
     282             :   {
     283         497 :     GEN C = cgetg(l+1, t_VEC);
     284         497 :     gel(C,1) = y;
     285       27118 :     for(j = 2; j <= l; j++)
     286       26621 :       gel(C,j) = sqr(E, gel(C,j-1));
     287         497 :     gel(R,i) = C;
     288         497 :     y = mul(E, y, x2);
     289             :   }
     290         147 :   return R;
     291             : }
     292             : 
     293             : GEN
     294       53331 : gen_pow_table(GEN R, GEN n, void *E, GEN (*one)(void*), GEN (*mul)(void*,GEN,GEN))
     295             : {
     296       53331 :   long e = expu(lg(R)-1) + 1;
     297       53331 :   long l = expi(n);
     298             :   long i, w;
     299       53331 :   GEN z = one(E), tw;
     300     1241302 :   for(i=0; i<=l; )
     301             :   {
     302     1187971 :     if (int_bit(n, i)==0) { i++; continue; }
     303      605954 :     if (i+e-1>l) e = l+1-i;
     304      605954 :     w = int_block(n,i+e-1,e);
     305      605954 :     tw = gmael(R, 1+(w>>1), i+1);
     306      605954 :     z = mul(E, z, tw);
     307      605954 :     i += e;
     308             :   }
     309       53331 :   return z;
     310             : }
     311             : 
     312             : GEN
     313    28674235 : gen_powers(GEN x, long l, int use_sqr, void *E, GEN (*sqr)(void*,GEN),
     314             :                                       GEN (*mul)(void*,GEN,GEN), GEN (*one)(void*))
     315             : {
     316             :   long i;
     317    28674235 :   GEN V = cgetg(l+2,t_VEC);
     318    28674140 :   gel(V,1) = one(E); if (l==0) return V;
     319    28648047 :   gel(V,2) = gcopy(x); if (l==1) return V;
     320    12572833 :   gel(V,3) = sqr(E,x);
     321    12578677 :   if (use_sqr)
     322    40481474 :     for(i = 4; i < l+2; i++)
     323    30872036 :       gel(V,i) = (i&1)? sqr(E,gel(V, (i+1)>>1))
     324    30872728 :                       : mul(E,gel(V, i-1),x);
     325             :   else
     326     7295884 :     for(i = 4; i < l+2; i++)
     327     4326638 :       gel(V,i) = mul(E,gel(V,i-1),x);
     328    12577992 :   return V;
     329             : }
     330             : 
     331             : GEN
     332    57409169 : producttree_scheme(long n)
     333             : {
     334             :   GEN v, w;
     335             :   long i, j, k, u, l;
     336    57409169 :   if (n<=2) return mkvecsmall(n);
     337    47760424 :   u = expu(n-1);
     338    47760438 :   v = cgetg(n+1,t_VECSMALL);
     339    47760457 :   w = cgetg(n+1,t_VECSMALL);
     340    47760799 :   v[1] = n; l = 1;
     341   156046026 :   for (i=1; i<=u; i++)
     342             :   {
     343   416395285 :     for(j=1, k=1; j<=l; j++, k+=2)
     344             :     {
     345   308110058 :       long vj = v[j], v2 = vj>>1;
     346   308110058 :       w[k]    = vj-v2;
     347   308110058 :       w[k+1]  = v2;
     348             :     }
     349   108285227 :     swap(v,w); l<<=1;
     350             :   }
     351    47760799 :   fixlg(v, l+1); set_avma((pari_sp)v); return v;
     352             : }
     353             : 
     354             : GEN
     355    60845465 : gen_product(GEN x, void *E, GEN (*mul)(void *,GEN,GEN))
     356             : {
     357             :   pari_sp av;
     358    60845465 :   long i, k, l = lg(x);
     359             :   pari_timer ti;
     360             :   GEN y, v;
     361             : 
     362    60845465 :   if (l <= 2) return l == 1? gen_1: gcopy(gel(x,1));
     363    56751899 :   y = cgetg(l, t_VEC); av = avma;
     364    56752135 :   v = producttree_scheme(l-1);
     365    56752542 :   l = lg(v);
     366    56752542 :   if (DEBUGLEVEL>7) timer_start(&ti);
     367   414946502 :   for (k = i = 1; k < l; i += v[k++])
     368   358196455 :     gel(y,k) = v[k]==1? gel(x,i): mul(E, gel(x,i), gel(x,i+1));
     369   163272717 :   while (k > 2)
     370             :   {
     371   106520488 :     long n = k - 1;
     372   106520488 :     if (DEBUGLEVEL>7) timer_printf(&ti,"gen_product: remaining objects %ld",n);
     373   407949585 :     for (k = i = 1; i < n; i += 2) gel(y,k++) = mul(E, gel(y,i), gel(y,i+1));
     374   106521737 :     if (gc_needed(av,1)) gerepilecoeffs(av, y+1, k-1);
     375             :   }
     376    56752229 :   return gel(y,1);
     377             : }
     378             : 
     379             : /***********************************************************************/
     380             : /**                                                                   **/
     381             : /**                    DISCRETE LOGARITHM                             **/
     382             : /**                                                                   **/
     383             : /***********************************************************************/
     384             : static GEN
     385    68282826 : iter_rho(GEN x, GEN g, GEN q, GEN A, ulong h, void *E, const struct bb_group *grp)
     386             : {
     387    68282826 :   GEN a = gel(A,1), b = gel(A,2), c = gel(A,3);
     388    68282826 :   switch((h | grp->hash(a)) % 3UL)
     389             :   {
     390    22772457 :     case 0: return mkvec3(grp->pow(E,a,gen_2), Fp_mulu(b,2,q), Fp_mulu(c,2,q));
     391    22756130 :     case 1: return mkvec3(grp->mul(E,a,x), addiu(b,1), c);
     392    22754239 :     case 2: return mkvec3(grp->mul(E,a,g), b, addiu(c,1));
     393             :   }
     394             :   return NULL; /* LCOV_EXCL_LINE */
     395             : }
     396             : 
     397             : /*Generic Pollard rho discrete log algorithm*/
     398             : static GEN
     399          49 : gen_Pollard_log(GEN x, GEN g, GEN q, void *E, const struct bb_group *grp)
     400             : {
     401          49 :   pari_sp av=avma;
     402          49 :   GEN A, B, l, sqrt4q = sqrti(shifti(q,4));
     403          49 :   ulong i, h = 0, imax = itou_or_0(sqrt4q);
     404          49 :   if (!imax) imax = ULONG_MAX;
     405             :   do {
     406          49 :  rho_restart:
     407          49 :     A = B = mkvec3(x,gen_1,gen_0);
     408          49 :     i=0;
     409             :     do {
     410    22760942 :       if (i>imax)
     411             :       {
     412           0 :         h++;
     413           0 :         if (DEBUGLEVEL)
     414           0 :           pari_warn(warner,"changing Pollard rho hash seed to %ld",h);
     415           0 :         goto rho_restart;
     416             :       }
     417    22760942 :       A = iter_rho(x, g, q, A, h, E, grp);
     418    22760942 :       B = iter_rho(x, g, q, B, h, E, grp);
     419    22760942 :       B = iter_rho(x, g, q, B, h, E, grp);
     420    22760942 :       if (gc_needed(av,2))
     421             :       {
     422        1585 :         if(DEBUGMEM>1) pari_warn(warnmem,"gen_Pollard_log");
     423        1585 :         gerepileall(av, 2, &A, &B);
     424             :       }
     425    22760942 :       i++;
     426    22760942 :     } while (!grp->equal(gel(A,1), gel(B,1)));
     427          49 :     gel(A,2) = modii(gel(A,2), q);
     428          49 :     gel(B,2) = modii(gel(B,2), q);
     429          49 :     h++;
     430          49 :   } while (equalii(gel(A,2), gel(B,2)));
     431          49 :   l = Fp_div(Fp_sub(gel(B,3), gel(A,3),q),Fp_sub(gel(A,2), gel(B,2), q), q);
     432          49 :   return gerepileuptoint(av, l);
     433             : }
     434             : 
     435             : /* compute a hash of g^(i-1), 1<=i<=n. Return [sorted hash, perm, g^-n] */
     436             : GEN
     437      723137 : gen_Shanks_init(GEN g, long n, void *E, const struct bb_group *grp)
     438             : {
     439      723137 :   GEN p1 = g, G, perm, table = cgetg(n+1,t_VECSMALL);
     440      723137 :   pari_sp av=avma;
     441             :   long i;
     442      723137 :   table[1] = grp->hash(grp->pow(E,g,gen_0));
     443     4107090 :   for (i=2; i<=n; i++)
     444             :   {
     445     3383953 :     table[i] = grp->hash(p1);
     446     3383953 :     p1 = grp->mul(E,p1,g);
     447     3383953 :     if (gc_needed(av,2))
     448             :     {
     449           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_log, baby = %ld", i);
     450           0 :       p1 = gerepileupto(av, p1);
     451             :     }
     452             :   }
     453      723137 :   G = gerepileupto(av, grp->pow(E,p1,gen_m1)); /* g^-n */
     454      723137 :   perm = vecsmall_indexsort(table);
     455      723137 :   table = vecsmallpermute(table,perm);
     456      723137 :   return mkvec4(table,perm,g,G);
     457             : }
     458             : /* T from gen_Shanks_init(g,n). Return v < n*N such that x = g^v or NULL */
     459             : GEN
     460      728513 : gen_Shanks(GEN T, GEN x, ulong N, void *E, const struct bb_group *grp)
     461             : {
     462      728513 :   pari_sp av=avma;
     463      728513 :   GEN table = gel(T,1), perm = gel(T,2), g = gel(T,3), G = gel(T,4);
     464      728513 :   GEN p1 = x;
     465      728513 :   long n = lg(table)-1;
     466             :   ulong k;
     467     4360123 :   for (k=0; k<N; k++)
     468             :   { /* p1 = x G^k, G = g^-n */
     469     4025990 :     long h = grp->hash(p1), i = zv_search(table, h);
     470     4025990 :     if (i)
     471             :     {
     472      395190 :       do i--; while (i && table[i] == h);
     473      394380 :       for (i++; i <= n && table[i] == h; i++)
     474             :       {
     475      394380 :         GEN v = addiu(muluu(n,k), perm[i]-1);
     476      394380 :         if (grp->equal(grp->pow(E,g,v),x)) return gerepileuptoint(av,v);
     477           0 :         if (DEBUGLEVEL)
     478           0 :           err_printf("gen_Shanks_log: false positive %lu, %lu\n", k,h);
     479             :       }
     480             :     }
     481     3631610 :     p1 = grp->mul(E,p1,G);
     482     3631610 :     if (gc_needed(av,2))
     483             :     {
     484           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_log, k = %lu", k);
     485           0 :       p1 = gerepileupto(av, p1);
     486             :     }
     487             :   }
     488      334133 :   return NULL;
     489             : }
     490             : /* Generic Shanks baby-step/giant-step algorithm. Return log_g(x), ord g = q.
     491             :  * One-shot: use gen_Shanks_init/log if many logs are desired; early abort
     492             :  * if log < sqrt(q) */
     493             : static GEN
     494     1516390 : gen_Shanks_log(GEN x, GEN g, GEN q, void *E, const struct bb_group *grp)
     495             : {
     496     1516390 :   pari_sp av=avma, av1;
     497             :   long lbaby, i, k;
     498             :   GEN p1, table, giant, perm, ginv;
     499     1516390 :   p1 = sqrti(q);
     500     1516389 :   if (abscmpiu(p1,LGBITS) >= 0)
     501           0 :     pari_err_OVERFLOW("gen_Shanks_log [order too large]");
     502     1516389 :   lbaby = itos(p1)+1; table = cgetg(lbaby+1,t_VECSMALL);
     503     1516390 :   ginv = grp->pow(E,g,gen_m1);
     504     1516390 :   av1 = avma;
     505     5028928 :   for (p1=x, i=1;;i++)
     506             :   {
     507     5028928 :     if (grp->equal1(p1)) return gc_stoi(av, i-1);
     508     4878050 :     table[i] = grp->hash(p1); if (i==lbaby) break;
     509     3512537 :     p1 = grp->mul(E,p1,ginv);
     510     3512538 :     if (gc_needed(av1,2))
     511             :     {
     512           6 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_log, baby = %ld", i);
     513           6 :       p1 = gerepileupto(av1, p1);
     514             :     }
     515             :   }
     516     1365514 :   p1 = giant = gerepileupto(av1, grp->mul(E,x,grp->pow(E, p1, gen_m1)));
     517     1365514 :   perm = vecsmall_indexsort(table);
     518     1365514 :   table = vecsmallpermute(table,perm);
     519     1365514 :   av1 = avma;
     520     2214040 :   for (k=1; k<= lbaby; k++)
     521             :   {
     522     2214040 :     long h = grp->hash(p1), i = zv_search(table, h);
     523     2214040 :     if (i)
     524             :     {
     525     2731030 :       while (table[i] == h && i) i--;
     526     1365516 :       for (i++; i <= lbaby && table[i] == h; i++)
     527             :       {
     528     1365515 :         GEN v = addiu(mulss(lbaby-1,k),perm[i]-1);
     529     1365515 :         if (grp->equal(grp->pow(E,g,v),x)) return gerepileuptoint(av,v);
     530           1 :         if (DEBUGLEVEL)
     531           0 :           err_printf("gen_Shanks_log: false positive %ld, %lu\n", k,h);
     532             :       }
     533             :     }
     534      848526 :     p1 = grp->mul(E,p1,giant);
     535      848526 :     if (gc_needed(av1,2))
     536             :     {
     537           1 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_log, k = %ld", k);
     538           1 :       p1 = gerepileupto(av1, p1);
     539             :     }
     540             :   }
     541           0 :   set_avma(av); return cgetg(1, t_VEC); /* no solution */
     542             : }
     543             : 
     544             : /*Generic discrete logarithme in a group of prime order p*/
     545             : GEN
     546     6131092 : gen_plog(GEN x, GEN g, GEN p, void *E, const struct bb_group *grp)
     547             : {
     548     6131092 :   if (grp->easylog)
     549             :   {
     550     6053758 :     GEN e = grp->easylog(E, x, g, p);
     551     6053757 :     if (e) return e;
     552             :   }
     553     2754953 :   if (grp->equal1(x)) return gen_0;
     554     2748639 :   if (grp->equal(x,g)) return gen_1;
     555     1516439 :   if (expi(p)<32) return gen_Shanks_log(x,g,p,E,grp);
     556          49 :   return gen_Pollard_log(x, g, p, E, grp);
     557             : }
     558             : 
     559             : GEN
     560    11129185 : get_arith_ZZM(GEN o)
     561             : {
     562    11129185 :   if (!o) return NULL;
     563    11129185 :   switch(typ(o))
     564             :   {
     565     3703332 :     case t_INT:
     566     3703332 :       if (signe(o) > 0) return mkvec2(o, Z_factor(o));
     567           8 :       break;
     568     1369945 :     case t_MAT:
     569     1369945 :       if (is_Z_factorpos(o)) return mkvec2(factorback(o), o);
     570          14 :       break;
     571     6055910 :     case t_VEC:
     572     6055910 :       if (lg(o) == 3 && signe(gel(o,1)) > 0 && is_Z_factorpos(gel(o,2))) return o;
     573           0 :       break;
     574             :   }
     575          24 :   pari_err_TYPE("generic discrete logarithm (order factorization)",o);
     576             :   return NULL; /* LCOV_EXCL_LINE */
     577             : }
     578             : GEN
     579     1365886 : get_arith_Z(GEN o)
     580             : {
     581     1365886 :   if (!o) return NULL;
     582     1365886 :   switch(typ(o))
     583             :   {
     584     1118337 :     case t_INT:
     585     1118337 :       if (signe(o) > 0) return o;
     586           7 :       break;
     587          14 :     case t_MAT:
     588          14 :       o = factorback(o);
     589           0 :       if (typ(o) == t_INT && signe(o) > 0) return o;
     590           0 :       break;
     591      247528 :     case t_VEC:
     592      247528 :       if (lg(o) != 3) break;
     593      247528 :       o = gel(o,1);
     594      247528 :       if (typ(o) == t_INT && signe(o) > 0) return o;
     595           0 :       break;
     596             :   }
     597          14 :   pari_err_TYPE("generic discrete logarithm (order factorization)",o);
     598             :   return NULL; /* LCOV_EXCL_LINE */
     599             : }
     600             : 
     601             : /* Generic Pohlig-Hellman discrete logarithm: smallest integer n >= 0 such that
     602             :  * g^n=a. Assume ord(g) | ord; grp->easylog() is an optional trapdoor
     603             :  * function that catches easy logarithms */
     604             : GEN
     605     4689018 : gen_PH_log(GEN a, GEN g, GEN ord, void *E, const struct bb_group *grp)
     606             : {
     607     4689018 :   pari_sp av = avma;
     608             :   GEN v, ginv, fa, ex;
     609             :   long i, j, l;
     610             : 
     611     4689018 :   if (grp->equal(g, a)) /* frequent special case */
     612      978347 :     return grp->equal1(g)? gen_0: gen_1;
     613     3710673 :   if (grp->easylog)
     614             :   {
     615     3660777 :     GEN e = grp->easylog(E, a, g, ord);
     616     3660747 :     if (e) return e;
     617             :   }
     618     2151694 :   v = get_arith_ZZM(ord);
     619     2151731 :   ord= gel(v,1);
     620     2151731 :   fa = gel(v,2);
     621     2151731 :   ex = gel(fa,2);
     622     2151731 :   fa = gel(fa,1); l = lg(fa);
     623     2151731 :   ginv = grp->pow(E,g,gen_m1);
     624     2151731 :   v = cgetg(l, t_VEC);
     625     6243206 :   for (i = 1; i < l; i++)
     626             :   {
     627     4091482 :     GEN q = gel(fa,i), qj, gq, nq, ginv0, a0, t0;
     628     4091482 :     long e = itos(gel(ex,i));
     629     4091482 :     if (DEBUGLEVEL>5)
     630           0 :       err_printf("Pohlig-Hellman: DL mod %Ps^%ld\n",q,e);
     631     4091482 :     qj = new_chunk(e+1);
     632     4091482 :     gel(qj,0) = gen_1;
     633     4091482 :     gel(qj,1) = q;
     634     5929151 :     for (j = 2; j <= e; j++) gel(qj,j) = mulii(gel(qj,j-1), q);
     635     4091482 :     t0 = diviiexact(ord, gel(qj,e));
     636     4091481 :     a0 = grp->pow(E, a, t0);
     637     4091482 :     ginv0 = grp->pow(E, ginv, t0); /* ord(ginv0) | q^e */
     638     4091482 :     if (grp->equal1(ginv0)) { gel(v,i) = mkintmod(gen_0, gen_1); continue; }
     639     4091475 :     do gq = grp->pow(E,g, mulii(t0, gel(qj,--e))); while (grp->equal1(gq));
     640             :     /* ord(gq) = q */
     641     4091468 :     nq = gen_0;
     642     4091468 :     for (j = 0;; j++)
     643     1837633 :     { /* nq = sum_{i<j} b_i q^i */
     644     5929101 :       GEN b = grp->pow(E,a0, gel(qj,e-j));
     645             :       /* cheap early abort: wrong local order */
     646     5929102 :       if (j == 0 && !grp->equal1(grp->pow(E,b,q))) {
     647           7 :         set_avma(av); return cgetg(1, t_VEC);
     648             :       }
     649     5929095 :       b = gen_plog(b, gq, q, E, grp);
     650     5929095 :       if (typ(b) != t_INT) { set_avma(av); return cgetg(1, t_VEC); }
     651     5929095 :       nq = addii(nq, mulii(b, gel(qj,j)));
     652     5929094 :       if (j == e) break;
     653             : 
     654     1837634 :       a0 = grp->mul(E,a0, grp->pow(E,ginv0, b));
     655     1837632 :       ginv0 = grp->pow(E,ginv0, q);
     656             :     }
     657     4091460 :     gel(v,i) = mkintmod(nq, gel(qj,e+1));
     658             :   }
     659     2151724 :   return gerepileuptoint(av, lift(chinese1_coprime_Z(v)));
     660             : }
     661             : 
     662             : /***********************************************************************/
     663             : /**                                                                   **/
     664             : /**                    ORDER OF AN ELEMENT                            **/
     665             : /**                                                                   **/
     666             : /***********************************************************************/
     667             : 
     668             : static GEN
     669    11703308 : rec_order(GEN a, GEN o, GEN m,
     670             :           void *E, const struct bb_group *grp, long x, long y)
     671             : {
     672    11703308 :   pari_sp av = avma;
     673    11703308 :   if(grp->equal1(a)) return gen_1;
     674     9583657 :   if(x == y)
     675             :   {
     676     5773745 :     GEN b = a, p = gcoeff(m, x, 1);
     677     5773745 :     long i, e = itos(gcoeff(m,x,2));
     678    13614791 :     for (i = 0; i < e; i++)
     679             :     {
     680     8621711 :       if (grp->equal1(b)) return gerepilecopy(av, powiu(p, i));
     681     7840973 :       b = grp->pow(E, b, p);
     682             :     }
     683     4993080 :     return gerepilecopy(av, powiu(p, e));
     684             :   }
     685             :   else
     686             :   {
     687     3809912 :     GEN b, o1, o2, cof = gen_1;
     688     3809912 :     long i, z = (x+y)/2;
     689     8646134 :     for (i = x; i <= z; i++)
     690     4836055 :       cof = mulii(cof, powii(gcoeff(m, i, 1), gcoeff(m, i, 2)));
     691     3810079 :     b = grp->pow(E, a, cof);
     692     3810076 :     o1 = rec_order(b, diviiexact(o, cof), m, E, grp, z+1, y);
     693     3810091 :     b = grp->pow(E, a, o1);
     694     3810077 :     o2 = rec_order(b, diviiexact(o, o1), m, E, grp, x, z);
     695     3810105 :     return gerepilecopy(av, mulii(o1, o2));
     696             :   }
     697             : }
     698             : 
     699             : /*Find the exact order of a assuming a^o==1*/
     700             : GEN
     701     4083378 : gen_order(GEN a, GEN o, void *E, const struct bb_group *grp)
     702             : {
     703     4083378 :   pari_sp av = avma;
     704             :   long l;
     705             :   GEN m;
     706             : 
     707     4083378 :   m = get_arith_ZZM(o);
     708     4083381 :   if (!m) pari_err_TYPE("gen_order [missing order]",a);
     709     4083381 :   o = gel(m,1);
     710     4083381 :   m = gel(m,2); l = lgcols(m);
     711     4083380 :   return gerepilecopy(av, rec_order(a, o, m, E, grp, 1, l-1));
     712             : }
     713             : 
     714             : /*Find the exact order of a assuming a^o==1, return [order,factor(order)] */
     715             : GEN
     716        5467 : gen_factored_order(GEN a, GEN o, void *E, const struct bb_group *grp)
     717             : {
     718        5467 :   pari_sp av = avma;
     719             :   long i, l, ind;
     720             :   GEN m, F, P;
     721             : 
     722        5467 :   m = get_arith_ZZM(o);
     723        5467 :   if (!m) pari_err_TYPE("gen_factored_order [missing order]",a);
     724        5467 :   o = gel(m,1);
     725        5467 :   m = gel(m,2); l = lgcols(m);
     726        5467 :   P = cgetg(l, t_COL); ind = 1;
     727        5467 :   F = cgetg(l, t_COL);
     728       18879 :   for (i = l-1; i; i--)
     729             :   {
     730       13412 :     GEN t, y, p = gcoeff(m,i,1);
     731       13412 :     long j, e = itos(gcoeff(m,i,2));
     732       13412 :     if (l == 2) {
     733         672 :       t = gen_1;
     734         672 :       y = a;
     735             :     } else {
     736       12740 :       t = diviiexact(o, powiu(p,e));
     737       12740 :       y = grp->pow(E, a, t);
     738             :     }
     739       13412 :     if (grp->equal1(y)) o = t;
     740             :     else {
     741       16198 :       for (j = 1; j < e; j++)
     742             :       {
     743        4655 :         y = grp->pow(E, y, p);
     744        4655 :         if (grp->equal1(y)) break;
     745             :       }
     746       12250 :       gel(P,ind) = p;
     747       12250 :       gel(F,ind) = utoipos(j);
     748       12250 :       if (j < e) {
     749         707 :         if (j > 1) p = powiu(p, j);
     750         707 :         o = mulii(t, p);
     751             :       }
     752       12250 :       ind++;
     753             :     }
     754             :   }
     755        5467 :   setlg(P, ind); P = vecreverse(P);
     756        5467 :   setlg(F, ind); F = vecreverse(F);
     757        5467 :   return gerepilecopy(av, mkvec2(o, mkmat2(P,F)));
     758             : }
     759             : 
     760             : /* E has order o[1], ..., or o[#o], draw random points until all solutions
     761             :  * but one are eliminated */
     762             : GEN
     763         980 : gen_select_order(GEN o, void *E, const struct bb_group *grp)
     764             : {
     765         980 :   pari_sp ltop = avma, btop;
     766             :   GEN lastgood, so, vo;
     767         980 :   long lo = lg(o), nbo=lo-1;
     768         980 :   if (nbo == 1) return icopy(gel(o,1));
     769         441 :   so = ZV_indexsort(o); /* minimize max( o[i+1] - o[i] ) */
     770         441 :   vo = zero_zv(lo);
     771         441 :   lastgood = gel(o, so[nbo]);
     772         441 :   btop = avma;
     773             :   for(;;)
     774           0 :   {
     775         441 :     GEN lasto = gen_0;
     776         441 :     GEN P = grp->rand(E), t = mkvec(gen_0);
     777             :     long i;
     778         567 :     for (i = 1; i < lo; i++)
     779             :     {
     780         567 :       GEN newo = gel(o, so[i]);
     781         567 :       if (vo[i]) continue;
     782         567 :       t = grp->mul(E,t, grp->pow(E, P, subii(newo,lasto)));/*P^o[i]*/
     783         567 :       lasto = newo;
     784         567 :       if (!grp->equal1(t))
     785             :       {
     786         483 :         if (--nbo == 1) { set_avma(ltop); return icopy(lastgood); }
     787          42 :         vo[i] = 1;
     788             :       }
     789             :       else
     790          84 :         lastgood = lasto;
     791             :     }
     792           0 :     set_avma(btop);
     793             :   }
     794             : }
     795             : 
     796             : /*******************************************************************/
     797             : /*                                                                 */
     798             : /*                          n-th ROOT                              */
     799             : /*                                                                 */
     800             : /*******************************************************************/
     801             : /* Assume l is prime. Return a generator of the l-th Sylow and set *zeta to an element
     802             :  * of order l.
     803             :  *
     804             :  * q = l^e*r, e>=1, (r,l)=1
     805             :  * UNCLEAN */
     806             : static GEN
     807      283353 : gen_lgener(GEN l, long e, GEN r,GEN *zeta, void *E, const struct bb_group *grp)
     808             : {
     809      283353 :   const pari_sp av1 = avma;
     810             :   GEN m, m1;
     811             :   long i;
     812      220109 :   for (;; set_avma(av1))
     813             :   {
     814      503463 :     m1 = m = grp->pow(E, grp->rand(E), r);
     815      503464 :     if (grp->equal1(m)) continue;
     816      925633 :     for (i=1; i<e; i++)
     817             :     {
     818      642277 :       m = grp->pow(E,m,l);
     819      642278 :       if (grp->equal1(m)) break;
     820             :     }
     821      408087 :     if (i==e) break;
     822             :   }
     823      283357 :   *zeta = m; return m1;
     824             : }
     825             : 
     826             : /* Let G be a cyclic group of order o>1. Returns a (random) generator */
     827             : 
     828             : GEN
     829       15883 : gen_gener(GEN o, void *E, const struct bb_group *grp)
     830             : {
     831       15883 :   pari_sp ltop = avma, av;
     832             :   long i, lpr;
     833       15883 :   GEN F, N, pr, z=NULL;
     834       15883 :   F = get_arith_ZZM(o);
     835       15883 :   N = gel(F,1); pr = gel(F,2); lpr = lgcols(pr);
     836       15883 :   av = avma;
     837             : 
     838       51562 :   for (i = 1; i < lpr; i++)
     839             :   {
     840       35679 :     GEN l = gcoeff(pr,i,1);
     841       35679 :     long e = itos(gcoeff(pr,i,2));
     842       35679 :     GEN r = diviiexact(N,powis(l,e));
     843       35679 :     GEN zetan, zl = gen_lgener(l,e,r,&zetan,E,grp);
     844       35679 :     z = i==1 ? zl: grp->mul(E,z,zl);
     845       35679 :     if (gc_needed(av,2))
     846             :     { /* n can have lots of prime factors*/
     847           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_gener");
     848           0 :       z = gerepileupto(av, z);
     849             :     }
     850             :   }
     851       15883 :   return gerepileupto(ltop, z);
     852             : }
     853             : 
     854             : /* solve x^l = a , l prime in G of order q.
     855             :  *
     856             :  * q =  (l^e)*r, e >= 1, (r,l) = 1
     857             :  * y is not an l-th power, hence generates the l-Sylow of G
     858             :  * m = y^(q/l) != 1 */
     859             : static GEN
     860      263463 : gen_Shanks_sqrtl(GEN a, GEN l, long e, GEN r, GEN y, GEN m,void *E,
     861             :                  const struct bb_group *grp)
     862             : {
     863      263463 :   pari_sp av = avma;
     864             :   long k;
     865             :   GEN p1, u1, u2, v, w, z, dl;
     866             : 
     867      263463 :   (void)bezout(r,l,&u1,&u2);
     868      263464 :   v = grp->pow(E,a,u2);
     869      263461 :   w = grp->pow(E,v,l);
     870      263460 :   w = grp->mul(E,w,grp->pow(E,a,gen_m1));
     871      465459 :   while (!grp->equal1(w))
     872             :   {
     873      202166 :     k = 0;
     874      202166 :     p1 = w;
     875             :     do
     876             :     {
     877      360806 :       z = p1; p1 = grp->pow(E,p1,l);
     878      360805 :       k++;
     879      360805 :     } while(!grp->equal1(p1));
     880      202165 :     if (k==e) return gc_NULL(av);
     881      201997 :     dl = gen_plog(z,m,l,E,grp);
     882      201996 :     if (typ(dl) != t_INT) return gc_NULL(av);
     883      201996 :     dl = negi(dl);
     884      201997 :     p1 = grp->pow(E, grp->pow(E,y, dl), powiu(l,e-k-1));
     885      201998 :     m = grp->pow(E,m,dl);
     886      201996 :     e = k;
     887      201996 :     v = grp->mul(E,p1,v);
     888      201997 :     y = grp->pow(E,p1,l);
     889      201995 :     w = grp->mul(E,y,w);
     890      201996 :     if (gc_needed(av,1))
     891             :     {
     892           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_sqrtl");
     893           0 :       gerepileall(av,4, &y,&v,&w,&m);
     894             :     }
     895             :   }
     896      263291 :   return gerepilecopy(av, v);
     897             : }
     898             : /* Return one solution of x^n = a in a cyclic group of order q
     899             :  *
     900             :  * 1) If there is no solution, return NULL.
     901             :  *
     902             :  * 2) If there is a solution, there are exactly m of them [m = gcd(q-1,n)].
     903             :  * If zetan!=NULL, *zetan is set to a primitive m-th root of unity so that
     904             :  * the set of solutions is { x*zetan^k; k=0..m-1 }
     905             :  */
     906             : GEN
     907      253551 : gen_Shanks_sqrtn(GEN a, GEN n, GEN q, GEN *zetan, void *E, const struct bb_group *grp)
     908             : {
     909      253551 :   pari_sp ltop = avma;
     910             :   GEN m, u1, u2, z;
     911             :   int is_1;
     912             : 
     913      253551 :   if (is_pm1(n))
     914             :   {
     915           0 :     if (zetan) *zetan = grp->pow(E,a,gen_0);
     916           0 :     return signe(n) < 0? grp->pow(E,a,gen_m1): gcopy(a);
     917             :   }
     918      253553 :   is_1 = grp->equal1(a);
     919      253552 :   if (is_1 && !zetan) return gcopy(a);
     920             : 
     921      244885 :   m = bezout(n,q,&u1,&u2);
     922      244886 :   z = grp->pow(E,a,gen_0);
     923      244884 :   if (!is_pm1(m))
     924             :   {
     925      244485 :     GEN F = Z_factor(m);
     926             :     long i, j, e;
     927             :     GEN r, zeta, y, l;
     928      244489 :     pari_sp av1 = avma;
     929      491999 :     for (i = nbrows(F); i; i--)
     930             :     {
     931      247674 :       l = gcoeff(F,i,1);
     932      247674 :       j = itos(gcoeff(F,i,2));
     933      247674 :       e = Z_pvalrem(q,l,&r);
     934      247674 :       y = gen_lgener(l,e,r,&zeta,E,grp);
     935      247678 :       if (zetan) z = grp->mul(E,z, grp->pow(E,y,powiu(l,e-j)));
     936      247678 :       if (!is_1) {
     937             :         do
     938             :         {
     939      263464 :           a = gen_Shanks_sqrtl(a,l,e,r,y,zeta,E,grp);
     940      263463 :           if (!a) return gc_NULL(ltop);
     941      263295 :         } while (--j);
     942             :       }
     943      247509 :       if (gc_needed(ltop,1))
     944             :       { /* n can have lots of prime factors*/
     945           0 :         if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_sqrtn");
     946           0 :         gerepileall(av1, zetan? 2: 1, &a, &z);
     947             :       }
     948             :     }
     949             :   }
     950      244724 :   if (!equalii(m, n))
     951         462 :     a = grp->pow(E,a,modii(u1,q));
     952      244724 :   if (zetan)
     953             :   {
     954         252 :     *zetan = z;
     955         252 :     gerepileall(ltop,2,&a,zetan);
     956             :   }
     957             :   else /* is_1 is 0: a was modified above -> gerepileupto valid */
     958      244472 :     a = gerepileupto(ltop, a);
     959      244724 :   return a;
     960             : }
     961             : 
     962             : /*******************************************************************/
     963             : /*                                                                 */
     964             : /*               structure of groups with pairing                  */
     965             : /*                                                                 */
     966             : /*******************************************************************/
     967             : /* return c = \prod_{p^2 | (N,d^2)} p^{v_p(N)} and factor(c); multiple of d2 */
     968             : static GEN
     969      146671 : d2_multiple(GEN N, GEN d)
     970             : {
     971      146671 :   GEN P, E, Q = gel(Z_factor(gcdii(N,d)), 1);
     972      146671 :   long i, j, l = lg(Q);
     973      146671 :   P = cgetg(l, t_COL);
     974      146671 :   E = cgetg(l, t_COL);
     975      271747 :   for (i = 1, j = 1; i < l; i++)
     976             :   {
     977      125076 :     long v = Z_pval(N, gel(Q,i));
     978      125076 :     if (v <= 1) continue;
     979       68558 :     gel(P, j) = gel(Q,i);
     980       68558 :     gel(E, j) = utoipos(v); j++;
     981             :   }
     982      146671 :   if (j == 1) return NULL;
     983       65100 :   setlg(P,j); setlg(E,j);
     984       65100 :   return mkvec2(factorback2(P, E), mkmat2(P, E));
     985             : }
     986             : 
     987             : /* Return elementary divisors [d1, d2], d2 | d1, for group of order N.
     988             :  * We have d2 | d */
     989             : GEN
     990      146832 : gen_ellgroup(GEN N, GEN d, GEN *pm, void *E, const struct bb_group *grp,
     991             :              GEN pairorder(void *E, GEN P, GEN Q, GEN m, GEN F))
     992             : {
     993      146832 :   pari_sp av = avma;
     994      146832 :   GEN N0, N1, F, fa0, L0, E0, g1 = gen_1, g2 = gen_1;
     995      146832 :   long n = 0, n0, j;
     996             : 
     997      146832 :   if (pm) *pm = gen_1;
     998      146832 :   if (is_pm1(N)) return cgetg(1,t_VEC);
     999      146671 :   F = d2_multiple(N, d); if (!F) { set_avma(av); return mkveccopy(N); }
    1000       65100 :   N0 = gel(F,1); fa0 = gel(F,2); /* N0 a multiple of d2, fa0 = factor(N0) */
    1001       65100 :   N1 = diviiexact(N, N0); /* N1 | d1 */
    1002       65100 :   L0 = gel(fa0, 1); n0 = lg(L0)-1; /* primes dividing N0 */
    1003       65100 :   E0 = ZV_to_nv(gel(fa0, 2)); /* ... and their exponents */
    1004             :   while (1)
    1005       52201 :   { /* g1 | (d1/N1), g2 | d2 */
    1006      117301 :     pari_sp av2 = avma;
    1007             :     GEN P, Q, s, t, m, mo;
    1008             : 
    1009      117301 :     P = grp->pow(E,grp->rand(E), N1);
    1010      117301 :     s = gen_order(P, F, E, grp); /* s | N0 */
    1011      117301 :     if (equalii(s, N0)) { set_avma(av); return mkveccopy(N); }
    1012             : 
    1013       94134 :     Q = grp->pow(E,grp->rand(E), N1);
    1014       94134 :     t = gen_order(Q, F, E, grp); /* t | N0 */
    1015       94134 :     if (equalii(t, N0)) { set_avma(av); return mkveccopy(N); }
    1016             : 
    1017       82742 :     m = lcmii(s, t); /* m | N0 */
    1018       82742 :     mo = mulii(m, pairorder(E, P, Q, m, F));
    1019             : 
    1020             :     /* For each prime l dividing N0, check whether P and Q
    1021             :      * generate all rational points of order a power of l */
    1022      140486 :     for (j = 1; j <= n0; j++)
    1023             :     {
    1024             :       GEN l;
    1025       88285 :       ulong e = uel(E0, j);
    1026       88285 :       if (e == 0) continue;
    1027       86103 :       l = gel(L0, j);
    1028       86103 :       if ((ulong)Z_pval(mo, l) == e)
    1029             :       {
    1030       33362 :         long vm = Z_pval(m, l);
    1031       33362 :         g1 = mulii(g1, powiu(l, vm));
    1032       33362 :         g2 = mulii(g2, powiu(l, e - vm));
    1033       33362 :         if (++n == n0)
    1034             :         { /* done with all primes l */
    1035             :           GEN g;
    1036       30541 :           if (equali1(g2)) { set_avma(av); return mkveccopy(N); }
    1037       30296 :           if (pm) *pm = g1;
    1038       30296 :           g = mkvec2(mulii(g1, N1), g2);
    1039       30296 :           if (!pm) return gerepilecopy(av, g);
    1040       30296 :           *pm = m; return gc_all(av, 2, &g, pm);
    1041             :         }
    1042        2821 :         uel(E0, j) = 0; /* done with this prime l */
    1043             :       }
    1044             :     }
    1045       52201 :     gerepileall(av2, 2, &g1, &g2);
    1046             :   }
    1047             : }
    1048             : 
    1049             : GEN
    1050        2716 : gen_ellgens(GEN D1, GEN d2, GEN m, void *E, const struct bb_group *grp,
    1051             :              GEN pairorder(void *E, GEN P, GEN Q, GEN m, GEN F))
    1052             : {
    1053        2716 :   pari_sp ltop = avma, av;
    1054             :   GEN F, d1, dm;
    1055             :   GEN P, Q, d, s;
    1056        2716 :   F = get_arith_ZZM(D1);
    1057        2716 :   d1 = gel(F, 1), dm =  diviiexact(d1,m);
    1058        2716 :   av = avma;
    1059             :   do
    1060             :   {
    1061        6387 :     set_avma(av);
    1062        6387 :     P = grp->rand(E);
    1063        6387 :     s = gen_order(P, F, E, grp);
    1064        6387 :   } while (!equalii(s, d1));
    1065        2716 :   av = avma;
    1066             :   do
    1067             :   {
    1068        5087 :     set_avma(av);
    1069        5087 :     Q = grp->rand(E);
    1070        5087 :     d = pairorder(E, grp->pow(E, P, dm), grp->pow(E, Q, dm), m, F);
    1071        5087 :   } while (!equalii(d, d2));
    1072        2716 :   return gerepilecopy(ltop, mkvec2(P,Q));
    1073             : }

Generated by: LCOV version 1.16