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.12.1 lcov report (development 25406-bf255ab81b) Lines: 538 577 93.2 %
Date: 2020-06-04 05:59:24 Functions: 36 36 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. It is distributed in the hope that it will be useful, but WITHOUT
       8             : ANY WARRANTY WHATSOEVER.
       9             : 
      10             : Check the License for details. You should have received a copy of it, along
      11             : with the package; see the file 'COPYING'. If not, write to the Free Software
      12             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      13             : 
      14             : /***********************************************************************/
      15             : /**                                                                   **/
      16             : /**             GENERIC ALGORITHMS ON BLACKBOX GROUP                  **/
      17             : /**                                                                   **/
      18             : /***********************************************************************/
      19             : #include "pari.h"
      20             : #include "paripriv.h"
      21             : #undef pow /* AIX: pow(a,b) is a macro, wrongly expanded on grp->pow(a,b,c) */
      22             : 
      23             : /***********************************************************************/
      24             : /**                                                                   **/
      25             : /**                    POWERING                                       **/
      26             : /**                                                                   **/
      27             : /***********************************************************************/
      28             : 
      29             : /* return (n>>(i+1-l)) & ((1<<l)-1) */
      30             : static ulong
      31     3950586 : int_block(GEN n, long i, long l)
      32             : {
      33     3950586 :   long q = divsBIL(i), r = remsBIL(i)+1, lr;
      34     3950718 :   GEN nw = int_W(n, q);
      35     3950718 :   ulong w = (ulong) *nw, w2;
      36     3950718 :   if (r>=l) return (w>>(r-l))&((1UL<<l)-1);
      37      295801 :   w &= (1UL<<r)-1; lr = l-r;
      38      295801 :   w2 = (ulong) *int_precW(nw); w2 >>= (BITS_IN_LONG-lr);
      39      295801 :   return (w<<lr)|w2;
      40             : }
      41             : 
      42             : /* assume n != 0, t_INT. Compute x^|n| using sliding window powering */
      43             : static GEN
      44     7216748 : sliding_window_powu(GEN x, ulong n, long e, void *E, GEN (*sqr)(void*,GEN),
      45             :                                                      GEN (*mul)(void*,GEN,GEN))
      46             : {
      47             :   pari_sp av;
      48     7216748 :   long i, l = expu(n), u = (1UL<<(e-1));
      49             :   long w, v;
      50     7216262 :   GEN tab = cgetg(1+u, t_VEC);
      51     7217372 :   GEN x2 = sqr(E, x), z = NULL, tw;
      52     7224974 :   gel(tab, 1) = x;
      53    20191940 :   for (i=2; i<=u; i++) gel(tab,i) = mul(E, gel(tab,i-1), x2);
      54     7207848 :   av = avma;
      55    56796306 :   while (l>=0)
      56             :   {
      57    48968993 :     if (e > l+1) e = l+1;
      58    48968993 :     w = (n>>(l+1-e)) & ((1UL<<e)-1); v = vals(w); l-=e;
      59    48982013 :     tw = gel(tab, 1+(w>>(v+1)));
      60    48982013 :     if (z)
      61             :     {
      62   114903421 :       for (i=1; i<=e-v; i++) z = sqr(E, z);
      63    41737180 :       z = mul(E, z, tw);
      64     7083379 :     } else z = tw;
      65    80945148 :     for (i=1; i<=v; i++) z = sqr(E, z);
      66    90210400 :     while (l>=0)
      67             :     {
      68    82487576 :       if (gc_needed(av,1))
      69             :       {
      70           0 :         if (DEBUGMEM>1) pari_warn(warnmem,"sliding_window_powu (%ld)", l);
      71           0 :         z = gerepilecopy(av, z);
      72             :       }
      73    83263140 :       if (n&(1UL<<l)) break;
      74    41397506 :       z = sqr(E, z); l--;
      75             :     }
      76             :   }
      77     7827313 :   return z;
      78             : }
      79             : 
      80             : /* assume n != 0, t_INT. Compute x^|n| using sliding window powering */
      81             : static GEN
      82       84793 : sliding_window_pow(GEN x, GEN n, long e, void *E, GEN (*sqr)(void*,GEN),
      83             :                                                   GEN (*mul)(void*,GEN,GEN))
      84             : {
      85             :   pari_sp av;
      86       84793 :   long i, l = expi(n), u = (1UL<<(e-1));
      87             :   long w, v;
      88       84792 :   GEN tab = cgetg(1+u, t_VEC);
      89       84792 :   GEN x2 = sqr(E, x), z = NULL, tw;
      90       84806 :   gel(tab, 1) = x;
      91     1414763 :   for (i=2; i<=u; i++) gel(tab,i) = mul(E, gel(tab,i-1), x2);
      92       84771 :   av = avma;
      93     3325684 :   while (l>=0)
      94             :   {
      95     3237909 :     if (e > l+1) e = l+1;
      96     3237909 :     w = int_block(n,l,e); v = vals(w); l-=e;
      97     3237966 :     tw = gel(tab, 1+(w>>(v+1)));
      98     3237966 :     if (z)
      99             :     {
     100    19263556 :       for (i=1; i<=e-v; i++) z = sqr(E, z);
     101     3146937 :       z = mul(E, z, tw);
     102       84771 :     } else z = tw;
     103     6291264 :     for (i=1; i<=v; i++) z = sqr(E, z);
     104    10382533 :     while (l>=0)
     105             :     {
     106    10294779 :       if (gc_needed(av,1))
     107             :       {
     108         459 :         if (DEBUGMEM>1) pari_warn(warnmem,"sliding_window_pow (%ld)", l);
     109         459 :         z = gerepilecopy(av, z);
     110             :       }
     111    10294779 :       if (int_bit(n,l)) break;
     112     7144165 :       z = sqr(E, z); l--;
     113             :     }
     114             :   }
     115       87775 :   return z;
     116             : }
     117             : 
     118             : /* assume n != 0, t_INT. Compute x^|n| using leftright binary powering */
     119             : static GEN
     120    49603638 : leftright_binary_powu(GEN x, ulong n, void *E, GEN (*sqr)(void*,GEN),
     121             :                                               GEN (*mul)(void*,GEN,GEN))
     122             : {
     123    49603638 :   pari_sp av = avma;
     124             :   GEN  y;
     125             :   int j;
     126             : 
     127    49603638 :   if (n == 1) return x;
     128    49603638 :   y = x; j = 1+bfffo(n);
     129             :   /* normalize, i.e set highest bit to 1 (we know n != 0) */
     130    49603638 :   n<<=j; j = BITS_IN_LONG-j;
     131             :   /* first bit is now implicit */
     132   145413217 :   for (; j; n<<=1,j--)
     133             :   {
     134    95819636 :     y = sqr(E,y);
     135    95809742 :     if (n & HIGHBIT) y = mul(E,y,x); /* first bit set: multiply by base */
     136    95809397 :     if (gc_needed(av,1))
     137             :     {
     138           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"leftright_powu (%d)", j);
     139           0 :       y = gerepilecopy(av, y);
     140             :     }
     141             :   }
     142    49593581 :   return y;
     143             : }
     144             : 
     145             : GEN
     146    57092474 : gen_powu_i(GEN x, ulong n, void *E, GEN (*sqr)(void*,GEN),
     147             :                                     GEN (*mul)(void*,GEN,GEN))
     148             : {
     149             :   long l;
     150    57092474 :   if (n == 1) return x;
     151    56818504 :   l = expu(n);
     152    56818332 :   if (l<=8)
     153    49599067 :     return leftright_binary_powu(x, n, E, sqr, mul);
     154             :   else
     155     7219265 :     return sliding_window_powu(x, n, l<=24? 2: 3, E, sqr, mul);
     156             : }
     157             : 
     158             : GEN
     159      176176 : gen_powu(GEN x, ulong n, void *E, GEN (*sqr)(void*,GEN),
     160             :                                   GEN (*mul)(void*,GEN,GEN))
     161             : {
     162      176176 :   pari_sp av = avma;
     163      176176 :   if (n == 1) return gcopy(x);
     164      152758 :   return gerepilecopy(av, gen_powu_i(x,n,E,sqr,mul));
     165             : }
     166             : 
     167             : GEN
     168    16837481 : gen_pow_i(GEN x, GEN n, void *E, GEN (*sqr)(void*,GEN),
     169             :                                  GEN (*mul)(void*,GEN,GEN))
     170             : {
     171             :   long l, e;
     172    16837481 :   if (lgefint(n)==3) return gen_powu_i(x, uel(n,2), E, sqr, mul);
     173       84786 :   l = expi(n);
     174       84793 :   if      (l<=64)  e = 3;
     175       61126 :   else if (l<=160) e = 4;
     176       26888 :   else if (l<=384) e = 5;
     177       18677 :   else if (l<=896) e = 6;
     178        9955 :   else             e = 7;
     179       84793 :   return sliding_window_pow(x, n, e, E, sqr, mul);
     180             : }
     181             : 
     182             : GEN
     183        4783 : gen_pow(GEN x, GEN n, void *E, GEN (*sqr)(void*,GEN),
     184             :                                GEN (*mul)(void*,GEN,GEN))
     185             : {
     186        4783 :   pari_sp av = avma;
     187        4783 :   return gerepilecopy(av, gen_pow_i(x,n,E,sqr,mul));
     188             : }
     189             : 
     190             : /* assume n > 0. Compute x^n using left-right binary powering */
     191             : GEN
     192      876562 : gen_powu_fold_i(GEN x, ulong n, void *E, GEN  (*sqr)(void*,GEN),
     193             :                                          GEN (*msqr)(void*,GEN))
     194             : {
     195      876562 :   pari_sp av = avma;
     196             :   GEN y;
     197             :   int j;
     198             : 
     199      876562 :   if (n == 1) return x;
     200      876562 :   y = x; j = 1+bfffo(n);
     201             :   /* normalize, i.e set highest bit to 1 (we know n != 0) */
     202      876562 :   n<<=j; j = BITS_IN_LONG-j;
     203             :   /* first bit is now implicit */
     204     4962976 :   for (; j; n<<=1,j--)
     205             :   {
     206     4086459 :     if (n & HIGHBIT) y = msqr(E,y); /* first bit set: multiply by base */
     207     2985653 :     else y = sqr(E,y);
     208     4086451 :     if (gc_needed(av,1))
     209             :     {
     210           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"gen_powu_fold (%d)", j);
     211           0 :       y = gerepilecopy(av, y);
     212             :     }
     213             :   }
     214      876517 :   return y;
     215             : }
     216             : GEN
     217        1270 : gen_powu_fold(GEN x, ulong n, void *E, GEN (*sqr)(void*,GEN),
     218             :                                        GEN (*msqr)(void*,GEN))
     219             : {
     220        1270 :   pari_sp av = avma;
     221        1270 :   if (n == 1) return gcopy(x);
     222        1270 :   return gerepilecopy(av, gen_powu_fold_i(x,n,E,sqr,msqr));
     223             : }
     224             : 
     225             : /* assume N != 0, t_INT. Compute x^|N| using left-right binary powering */
     226             : GEN
     227      224375 : gen_pow_fold_i(GEN x, GEN N, void *E, GEN (*sqr)(void*,GEN),
     228             :                                       GEN (*msqr)(void*,GEN))
     229             : {
     230      224375 :   long ln = lgefint(N);
     231      224375 :   if (ln == 3) return gen_powu_fold_i(x, N[2], E, sqr, msqr);
     232             :   else
     233             :   {
     234       99599 :     GEN nd = int_MSW(N), y = x;
     235       99599 :     ulong n = *nd;
     236             :     long i;
     237             :     int j;
     238       99599 :     pari_sp av = avma;
     239             : 
     240       99599 :     if (n == 1)
     241        6399 :       j = 0;
     242             :     else
     243             :     {
     244       93200 :       j = 1+bfffo(n); /* < BIL */
     245             :       /* normalize, i.e set highest bit to 1 (we know n != 0) */
     246       93200 :       n <<= j; j = BITS_IN_LONG - j;
     247             :     }
     248             :     /* first bit is now implicit */
     249       99599 :     for (i=ln-2;;)
     250             :     {
     251    30896718 :       for (; j; n<<=1,j--)
     252             :       {
     253    30520263 :         if (n & HIGHBIT) y = msqr(E,y); /* first bit set: multiply by base */
     254    20394278 :         else y = sqr(E,y);
     255    30426568 :         if (gc_needed(av,1))
     256             :         {
     257           0 :           if (DEBUGMEM>1) pari_warn(warnmem,"gen_pow_fold (%d)", j);
     258           0 :           y = gerepilecopy(av, y);
     259             :         }
     260             :       }
     261      458255 :       if (--i == 0) return y;
     262      515581 :       nd = int_precW(nd);
     263      515581 :       n = *nd; j = BITS_IN_LONG;
     264             :     }
     265             :   }
     266             : }
     267             : GEN
     268      124777 : gen_pow_fold(GEN x, GEN n, void *E, GEN (*sqr)(void*,GEN),
     269             :                                     GEN (*msqr)(void*,GEN))
     270             : {
     271      124777 :   pari_sp av = avma;
     272      124777 :   return gerepilecopy(av, gen_pow_fold_i(x,n,E,sqr,msqr));
     273             : }
     274             : 
     275             : GEN
     276         126 : gen_pow_init(GEN x, GEN n, long k, void *E, GEN (*sqr)(void*,GEN), GEN (*mul)(void*,GEN,GEN))
     277             : {
     278         126 :   long i, j, l = expi(n);
     279         126 :   long m = 1UL<<(k-1);
     280         126 :   GEN x2 = sqr(E, x), y = gcopy(x);
     281         126 :   GEN R = cgetg(m+1, t_VEC);
     282         609 :   for(i = 1; i <= m; i++)
     283             :   {
     284         483 :     GEN C = cgetg(l+1, t_VEC);
     285         483 :     gel(C,1) = y;
     286       27622 :     for(j = 2; j <= l; j++)
     287       27139 :       gel(C,j) = sqr(E, gel(C,j-1));
     288         483 :     gel(R,i) = C;
     289         483 :     y = mul(E, y, x2);
     290             :   }
     291         126 :   return R;
     292             : }
     293             : 
     294             : GEN
     295       64733 : gen_pow_table(GEN R, GEN n, void *E, GEN (*one)(void*), GEN (*mul)(void*,GEN,GEN))
     296             : {
     297       64733 :   long e = expu(lg(R)-1) + 1;
     298       64733 :   long l = expi(n);
     299             :   long i, w;
     300       64733 :   GEN z = one(E), tw;
     301     1466784 :   for(i=0; i<=l; )
     302             :   {
     303     1402051 :     if (int_bit(n, i)==0) { i++; continue; }
     304      712695 :     if (i+e-1>l) e = l+1-i;
     305      712695 :     w = int_block(n,i+e-1,e);
     306      712695 :     tw = gmael(R, 1+(w>>1), i+1);
     307      712695 :     z = mul(E, z, tw);
     308      712695 :     i += e;
     309             :   }
     310       64733 :   return z;
     311             : }
     312             : 
     313             : GEN
     314     8180543 : gen_powers(GEN x, long l, int use_sqr, void *E, GEN (*sqr)(void*,GEN),
     315             :                                       GEN (*mul)(void*,GEN,GEN), GEN (*one)(void*))
     316             : {
     317             :   long i;
     318     8180543 :   GEN V = cgetg(l+2,t_VEC);
     319     8180601 :   gel(V,1) = one(E); if (l==0) return V;
     320     8164302 :   gel(V,2) = gcopy(x); if (l==1) return V;
     321     4857341 :   gel(V,3) = sqr(E,x);
     322     4857349 :   if (use_sqr)
     323    13067316 :     for(i = 4; i < l+2; i++)
     324     9219906 :       gel(V,i) = (i&1)? sqr(E,gel(V, (i+1)>>1))
     325     9220487 :                       : mul(E,gel(V, i-1),x);
     326             :   else
     327     2738525 :     for(i = 4; i < l+2; i++)
     328     1728573 :       gel(V,i) = mul(E,gel(V,i-1),x);
     329     4856781 :   return V;
     330             : }
     331             : 
     332             : GEN
     333    51743555 : producttree_scheme(long n)
     334             : {
     335             :   GEN v, w;
     336             :   long i, j, k, u, l;
     337    51743555 :   if (n<=2) return mkvecsmall(n);
     338    43647745 :   u = expu(n-1);
     339    43647715 :   v = cgetg(n+1,t_VECSMALL);
     340    43647847 :   w = cgetg(n+1,t_VECSMALL);
     341    43648322 :   v[1] = n; l = 1;
     342   145721860 :   for (i=1; i<=u; i++)
     343             :   {
     344   365642215 :     for(j=1, k=1; j<=l; j++, k+=2)
     345             :     {
     346   263568677 :       long vj = v[j], v2 = vj>>1;
     347   263568677 :       w[k]    = vj-v2;
     348   263568677 :       w[k+1]  = v2;
     349             :     }
     350   102073538 :     swap(v,w); l<<=1;
     351             :   }
     352    43648322 :   fixlg(v, l+1); set_avma((pari_sp)v); return v;
     353             : }
     354             : 
     355             : GEN
     356    53939671 : gen_product(GEN x, void *E, GEN (*mul)(void *,GEN,GEN))
     357             : {
     358             :   pari_sp av;
     359    53939671 :   long i, k, l = lg(x);
     360             :   pari_timer ti;
     361             :   GEN y, v;
     362             : 
     363    53939671 :   if (l <= 2) return l == 1? gen_1: gcopy(gel(x,1));
     364    51680728 :   y = cgetg(l, t_VEC); av = avma;
     365    51681051 :   v = producttree_scheme(l-1);
     366    51681695 :   l = lg(v);
     367    51681695 :   if (DEBUGLEVEL>7) timer_start(&ti);
     368   366326521 :   for (k = i = 1; k < l; i += v[k++])
     369   314648715 :     gel(y,k) = v[k]==1? gel(x,i): mul(E, gel(x,i), gel(x,i+1));
     370   153582996 :   while (k > 2)
     371             :   {
     372   101901809 :     long n = k - 1;
     373   101901809 :     if (DEBUGLEVEL>7) timer_printf(&ti,"gen_product: remaining objects %ld",n);
     374   364855177 :     for (k = i = 1; i < n; i += 2) gel(y,k++) = mul(E, gel(y,i), gel(y,i+1));
     375   101903113 :     if (gc_needed(av,1)) gerepilecoeffs(av, y+1, k-1);
     376             :   }
     377    51681187 :   return gel(y,1);
     378             : }
     379             : 
     380             : /***********************************************************************/
     381             : /**                                                                   **/
     382             : /**                    DISCRETE LOGARITHM                             **/
     383             : /**                                                                   **/
     384             : /***********************************************************************/
     385             : static GEN
     386    39451053 : iter_rho(GEN x, GEN g, GEN q, GEN A, ulong h, void *E, const struct bb_group *grp)
     387             : {
     388    39451053 :   GEN a = gel(A,1), b = gel(A,2), c = gel(A,3);
     389    39451053 :   switch((h | grp->hash(a)) % 3UL)
     390             :   {
     391    13163028 :     case 0: return mkvec3(grp->pow(E,a,gen_2), Fp_mulu(b,2,q), Fp_mulu(c,2,q));
     392    13151796 :     case 1: return mkvec3(grp->mul(E,a,x), addiu(b,1), c);
     393    13136229 :     case 2: return mkvec3(grp->mul(E,a,g), b, addiu(c,1));
     394             :   }
     395             :   return NULL; /* LCOV_EXCL_LINE */
     396             : }
     397             : 
     398             : /*Generic Pollard rho discrete log algorithm*/
     399             : static GEN
     400          49 : gen_Pollard_log(GEN x, GEN g, GEN q, void *E, const struct bb_group *grp)
     401             : {
     402          49 :   pari_sp av=avma;
     403          49 :   GEN A, B, l, sqrt4q = sqrti(shifti(q,4));
     404          49 :   ulong i, h = 0, imax = itou_or_0(sqrt4q);
     405          49 :   if (!imax) imax = ULONG_MAX;
     406             :   do {
     407          49 :  rho_restart:
     408          49 :     A = B = mkvec3(x,gen_1,gen_0);
     409          49 :     i=0;
     410             :     do {
     411    13150351 :       if (i>imax)
     412             :       {
     413           0 :         h++;
     414           0 :         if (DEBUGLEVEL)
     415           0 :           pari_warn(warner,"changing Pollard rho hash seed to %ld",h);
     416           0 :         goto rho_restart;
     417             :       }
     418    13150351 :       A = iter_rho(x, g, q, A, h, E, grp);
     419    13150351 :       B = iter_rho(x, g, q, B, h, E, grp);
     420    13150351 :       B = iter_rho(x, g, q, B, h, E, grp);
     421    13150351 :       if (gc_needed(av,2))
     422             :       {
     423        1000 :         if(DEBUGMEM>1) pari_warn(warnmem,"gen_Pollard_log");
     424        1000 :         gerepileall(av, 2, &A, &B);
     425             :       }
     426    13150351 :       i++;
     427    13150351 :     } while (!grp->equal(gel(A,1), gel(B,1)));
     428          49 :     gel(A,2) = modii(gel(A,2), q);
     429          49 :     gel(B,2) = modii(gel(B,2), q);
     430          49 :     h++;
     431          49 :   } while (equalii(gel(A,2), gel(B,2)));
     432          49 :   l = Fp_div(Fp_sub(gel(B,3), gel(A,3),q),Fp_sub(gel(A,2), gel(B,2), q), q);
     433          49 :   return gerepileuptoint(av, l);
     434             : }
     435             : 
     436             : /* compute a hash of g^(i-1), 1<=i<=n. Return [sorted hash, perm, g^-n] */
     437             : GEN
     438     2679171 : gen_Shanks_init(GEN g, long n, void *E, const struct bb_group *grp)
     439             : {
     440     2679171 :   GEN p1 = g, G, perm, table = cgetg(n+1,t_VECSMALL);
     441     2679171 :   pari_sp av=avma;
     442             :   long i;
     443     2679171 :   table[1] = grp->hash(grp->pow(E,g,gen_0));
     444    13416837 :   for (i=2; i<=n; i++)
     445             :   {
     446    10737666 :     table[i] = grp->hash(p1);
     447    10737666 :     p1 = grp->mul(E,p1,g);
     448    10737666 :     if (gc_needed(av,2))
     449             :     {
     450           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_log, baby = %ld", i);
     451           0 :       p1 = gerepileupto(av, p1);
     452             :     }
     453             :   }
     454     2679171 :   G = gerepileupto(av, grp->pow(E,p1,gen_m1)); /* g^-n */
     455     2679171 :   perm = vecsmall_indexsort(table);
     456     2679171 :   table = vecsmallpermute(table,perm);
     457     2679171 :   return mkvec4(table,perm,g,G);
     458             : }
     459             : /* T from gen_Shanks_init(g,n). Return v < n*N such that x = g^v or NULL */
     460             : GEN
     461     2679619 : gen_Shanks(GEN T, GEN x, ulong N, void *E, const struct bb_group *grp)
     462             : {
     463     2679619 :   pari_sp av=avma;
     464     2679619 :   GEN table = gel(T,1), perm = gel(T,2), g = gel(T,3), G = gel(T,4);
     465     2679619 :   GEN p1 = x;
     466     2679619 :   long n = lg(table)-1;
     467             :   ulong k;
     468    14967656 :   for (k=0; k<N; k++)
     469             :   { /* p1 = x G^k, G = g^-n */
     470    14673411 :     long h = grp->hash(p1), i = zv_search(table, h);
     471    14673411 :     if (i)
     472             :     {
     473     2386119 :       do i--; while (i && table[i] == h);
     474     2385374 :       for (i++; i <= n && table[i] == h; i++)
     475             :       {
     476     2385374 :         GEN v = addiu(muluu(n,k), perm[i]-1);
     477     2385374 :         if (grp->equal(grp->pow(E,g,v),x)) return gerepileuptoint(av,v);
     478           0 :         if (DEBUGLEVEL)
     479           0 :           err_printf("gen_Shanks_log: false positive %lu, %lu\n", k,h);
     480             :       }
     481             :     }
     482    12288037 :     p1 = grp->mul(E,p1,G);
     483    12288037 :     if (gc_needed(av,2))
     484             :     {
     485           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_log, k = %lu", k);
     486           0 :       p1 = gerepileupto(av, p1);
     487             :     }
     488             :   }
     489      294245 :   return NULL;
     490             : }
     491             : /* Generic Shanks baby-step/giant-step algorithm. Return log_g(x), ord g = q.
     492             :  * One-shot: use gen_Shanks_init/log if many logs are desired; early abort
     493             :  * if log < sqrt(q) */
     494             : static GEN
     495      351950 : gen_Shanks_log(GEN x, GEN g, GEN q, void *E, const struct bb_group *grp)
     496             : {
     497      351950 :   pari_sp av=avma, av1;
     498             :   long lbaby, i, k;
     499             :   GEN p1, table, giant, perm, ginv;
     500      351950 :   p1 = sqrti(q);
     501      351950 :   if (abscmpiu(p1,LGBITS) >= 0)
     502           0 :     pari_err_OVERFLOW("gen_Shanks_log [order too large]");
     503      351950 :   lbaby = itos(p1)+1; table = cgetg(lbaby+1,t_VECSMALL);
     504      351950 :   ginv = grp->pow(E,g,gen_m1);
     505      351950 :   av1 = avma;
     506      351950 :   for (p1=x, i=1;;i++)
     507             :   {
     508     1588099 :     if (grp->equal1(p1)) { set_avma(av); return stoi(i-1); }
     509     1540919 :     table[i] = grp->hash(p1); if (i==lbaby) break;
     510     1236149 :     p1 = grp->mul(E,p1,ginv);
     511     1236149 :     if (gc_needed(av1,2))
     512             :     {
     513           7 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_log, baby = %ld", i);
     514           7 :       p1 = gerepileupto(av1, p1);
     515             :     }
     516             :   }
     517      304770 :   p1 = giant = gerepileupto(av1, grp->mul(E,x,grp->pow(E, p1, gen_m1)));
     518      304770 :   perm = vecsmall_indexsort(table);
     519      304770 :   table = vecsmallpermute(table,perm);
     520      304770 :   av1 = avma;
     521      649502 :   for (k=1; k<= lbaby; k++)
     522             :   {
     523      649502 :     long h = grp->hash(p1), i = zv_search(table, h);
     524      649502 :     if (i)
     525             :     {
     526      609540 :       while (table[i] == h && i) i--;
     527      304770 :       for (i++; i <= lbaby && table[i] == h; i++)
     528             :       {
     529      304770 :         GEN v = addiu(mulss(lbaby-1,k),perm[i]-1);
     530      304770 :         if (grp->equal(grp->pow(E,g,v),x)) return gerepileuptoint(av,v);
     531           0 :         if (DEBUGLEVEL)
     532           0 :           err_printf("gen_Shanks_log: false positive %ld, %lu\n", k,h);
     533             :       }
     534             :     }
     535      344732 :     p1 = grp->mul(E,p1,giant);
     536      344732 :     if (gc_needed(av1,2))
     537             :     {
     538           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_log, k = %ld", k);
     539           0 :       p1 = gerepileupto(av1, p1);
     540             :     }
     541             :   }
     542           0 :   set_avma(av); return cgetg(1, t_VEC); /* no solution */
     543             : }
     544             : 
     545             : /*Generic discrete logarithme in a group of prime order p*/
     546             : GEN
     547     1463371 : gen_plog(GEN x, GEN g, GEN p, void *E, const struct bb_group *grp)
     548             : {
     549     1463371 :   if (grp->easylog)
     550             :   {
     551     1439326 :     GEN e = grp->easylog(E, x, g, p);
     552     1439326 :     if (e) return e;
     553             :   }
     554      574459 :   if (grp->equal1(x)) return gen_0;
     555      574417 :   if (grp->equal(x,g)) return gen_1;
     556      351999 :   if (expi(p)<32) return gen_Shanks_log(x,g,p,E,grp);
     557          49 :   return gen_Pollard_log(x, g, p, E, grp);
     558             : }
     559             : 
     560             : GEN
     561     7990162 : get_arith_ZZM(GEN o)
     562             : {
     563     7990162 :   if (!o) return NULL;
     564     7990162 :   switch(typ(o))
     565             :   {
     566     5000445 :     case t_INT:
     567     5000445 :       if (signe(o) > 0) return mkvec2(o, Z_factor(o));
     568           7 :       break;
     569     1380788 :     case t_MAT:
     570     1380788 :       if (is_Z_factorpos(o)) return mkvec2(factorback(o), o);
     571          14 :       break;
     572     1608922 :     case t_VEC:
     573     1608922 :       if (lg(o) == 3 && signe(gel(o,1)) > 0 && is_Z_factorpos(gel(o,2))) return o;
     574           0 :       break;
     575             :   }
     576          28 :   pari_err_TYPE("generic discrete logarithm (order factorization)",o);
     577             :   return NULL; /* LCOV_EXCL_LINE */
     578             : }
     579             : GEN
     580      397054 : get_arith_Z(GEN o)
     581             : {
     582      397054 :   if (!o) return NULL;
     583      397054 :   switch(typ(o))
     584             :   {
     585      306887 :     case t_INT:
     586      306887 :       if (signe(o) > 0) return o;
     587           7 :       break;
     588          14 :     case t_MAT:
     589          14 :       o = factorback(o);
     590           0 :       if (typ(o) == t_INT && signe(o) > 0) return o;
     591           0 :       break;
     592       90146 :     case t_VEC:
     593       90146 :       if (lg(o) != 3) break;
     594       90146 :       o = gel(o,1);
     595       90146 :       if (typ(o) == t_INT && signe(o) > 0) return o;
     596           0 :       break;
     597             :   }
     598          14 :   pari_err_TYPE("generic discrete logarithm (order factorization)",o);
     599             :   return NULL; /* LCOV_EXCL_LINE */
     600             : }
     601             : 
     602             : /* Generic Pohlig-Hellman discrete logarithm: smallest integer n >= 0 such that
     603             :  * g^n=a. Assume ord(g) | ord; grp->easylog() is an optional trapdoor
     604             :  * function that catches easy logarithms */
     605             : GEN
     606     1292836 : gen_PH_log(GEN a, GEN g, GEN ord, void *E, const struct bb_group *grp)
     607             : {
     608     1292836 :   pari_sp av = avma;
     609             :   GEN v, ginv, fa, ex;
     610             :   long i, j, l;
     611             : 
     612     1292836 :   if (grp->equal(g, a)) /* frequent special case */
     613      234769 :     return grp->equal1(g)? gen_0: gen_1;
     614     1058067 :   if (grp->easylog)
     615             :   {
     616     1057955 :     GEN e = grp->easylog(E, a, g, ord);
     617     1057927 :     if (e) return e;
     618             :   }
     619      461503 :   v = get_arith_ZZM(ord);
     620      461503 :   ord= gel(v,1);
     621      461503 :   fa = gel(v,2);
     622      461503 :   ex = gel(fa,2);
     623      461503 :   fa = gel(fa,1); l = lg(fa);
     624      461503 :   ginv = grp->pow(E,g,gen_m1);
     625      461503 :   v = cgetg(l, t_VEC);
     626     1429485 :   for (i = 1; i < l; i++)
     627             :   {
     628      967989 :     GEN q = gel(fa,i), qj, gq, nq, ginv0, a0, t0;
     629      967989 :     long e = itos(gel(ex,i));
     630      967989 :     if (DEBUGLEVEL>5)
     631           0 :       err_printf("Pohlig-Hellman: DL mod %Ps^%ld\n",q,e);
     632      967989 :     qj = new_chunk(e+1);
     633      967989 :     gel(qj,0) = gen_1;
     634      967989 :     gel(qj,1) = q;
     635     1279082 :     for (j = 2; j <= e; j++) gel(qj,j) = mulii(gel(qj,j-1), q);
     636      967989 :     t0 = diviiexact(ord, gel(qj,e));
     637      967989 :     a0 = grp->pow(E, a, t0);
     638      967989 :     ginv0 = grp->pow(E, ginv, t0); /* ord(ginv0) | q^e */
     639      967989 :     if (grp->equal1(ginv0)) { gel(v,i) = mkintmod(gen_0, gen_1); continue; }
     640      967982 :     do gq = grp->pow(E,g, mulii(t0, gel(qj,--e))); while (grp->equal1(gq));
     641             :     /* ord(gq) = q */
     642      967975 :     nq = gen_0;
     643      967975 :     for (j = 0;; j++)
     644      311058 :     { /* nq = sum_{i<j} b_i q^i */
     645     1279033 :       GEN b = grp->pow(E,a0, gel(qj,e-j));
     646             :       /* cheap early abort: wrong local order */
     647     1279033 :       if (j == 0 && !grp->equal1(grp->pow(E,b,q))) {
     648           7 :         set_avma(av); return cgetg(1, t_VEC);
     649             :       }
     650     1279026 :       b = gen_plog(b, gq, q, E, grp);
     651     1279026 :       if (typ(b) != t_INT) { set_avma(av); return cgetg(1, t_VEC); }
     652     1279026 :       nq = addii(nq, mulii(b, gel(qj,j)));
     653     1279026 :       if (j == e) break;
     654             : 
     655      311058 :       a0 = grp->mul(E,a0, grp->pow(E,ginv0, b));
     656      311058 :       ginv0 = grp->pow(E,ginv0, q);
     657             :     }
     658      967968 :     gel(v,i) = mkintmod(nq, gel(qj,e+1));
     659             :   }
     660      461496 :   return gerepileuptoint(av, lift(chinese1_coprime_Z(v)));
     661             : }
     662             : 
     663             : /***********************************************************************/
     664             : /**                                                                   **/
     665             : /**                    ORDER OF AN ELEMENT                            **/
     666             : /**                                                                   **/
     667             : /***********************************************************************/
     668             : /*Find the exact order of a assuming a^o==1*/
     669             : GEN
     670     3243300 : gen_order(GEN a, GEN o, void *E, const struct bb_group *grp)
     671             : {
     672     3243300 :   pari_sp av = avma;
     673             :   long i, l;
     674             :   GEN m;
     675             : 
     676     3243300 :   m = get_arith_ZZM(o);
     677     3243297 :   if (!m) pari_err_TYPE("gen_order [missing order]",a);
     678     3243297 :   o = gel(m,1);
     679     3243297 :   m = gel(m,2); l = lgcols(m);
     680    10114879 :   for (i = l-1; i; i--)
     681             :   {
     682     6871607 :     GEN t, y, p = gcoeff(m,i,1);
     683     6871607 :     long j, e = itos(gcoeff(m,i,2));
     684     6871610 :     if (l == 2) {
     685      679662 :       t = gen_1;
     686      679662 :       y = a;
     687             :     } else {
     688     6191948 :       t = diviiexact(o, powiu(p,e));
     689     6191837 :       y = grp->pow(E, a, t);
     690             :     }
     691     6871598 :     if (grp->equal1(y)) o = t;
     692             :     else {
     693     6378263 :       for (j = 1; j < e; j++)
     694             :       {
     695     2177986 :         y = grp->pow(E, y, p);
     696     2177991 :         if (grp->equal1(y)) break;
     697             :       }
     698     4723658 :       if (j < e) {
     699      523381 :         if (j > 1) p = powiu(p, j);
     700      523381 :         o = mulii(t, p);
     701             :       }
     702             :     }
     703             :   }
     704     3243272 :   return gerepilecopy(av, o);
     705             : }
     706             : 
     707             : /*Find the exact order of a assuming a^o==1, return [order,factor(order)] */
     708             : GEN
     709     2777051 : gen_factored_order(GEN a, GEN o, void *E, const struct bb_group *grp)
     710             : {
     711     2777051 :   pari_sp av = avma;
     712             :   long i, l, ind;
     713             :   GEN m, F, P;
     714             : 
     715     2777051 :   m = get_arith_ZZM(o);
     716     2777051 :   if (!m) pari_err_TYPE("gen_factored_order [missing order]",a);
     717     2777051 :   o = gel(m,1);
     718     2777051 :   m = gel(m,2); l = lgcols(m);
     719     2777051 :   P = cgetg(l, t_COL); ind = 1;
     720     2777051 :   F = cgetg(l, t_COL);
     721     6673150 :   for (i = l-1; i; i--)
     722             :   {
     723     3896099 :     GEN t, y, p = gcoeff(m,i,1);
     724     3896099 :     long j, e = itos(gcoeff(m,i,2));
     725     3896099 :     if (l == 2) {
     726     1702992 :       t = gen_1;
     727     1702992 :       y = a;
     728             :     } else {
     729     2193107 :       t = diviiexact(o, powiu(p,e));
     730     2193107 :       y = grp->pow(E, a, t);
     731             :     }
     732     3896099 :     if (grp->equal1(y)) o = t;
     733             :     else {
     734     4884401 :       for (j = 1; j < e; j++)
     735             :       {
     736     1037313 :         y = grp->pow(E, y, p);
     737     1037313 :         if (grp->equal1(y)) break;
     738             :       }
     739     3860155 :       gel(P,ind) = p;
     740     3860155 :       gel(F,ind) = utoipos(j);
     741     3860155 :       if (j < e) {
     742       13067 :         if (j > 1) p = powiu(p, j);
     743       13067 :         o = mulii(t, p);
     744             :       }
     745     3860155 :       ind++;
     746             :     }
     747             :   }
     748     2777051 :   setlg(P, ind); P = vecreverse(P);
     749     2777051 :   setlg(F, ind); F = vecreverse(F);
     750     2777051 :   return gerepilecopy(av, mkvec2(o, mkmat2(P,F)));
     751             : }
     752             : 
     753             : /* E has order o[1], ..., or o[#o], draw random points until all solutions
     754             :  * but one are eliminated */
     755             : GEN
     756         945 : gen_select_order(GEN o, void *E, const struct bb_group *grp)
     757             : {
     758         945 :   pari_sp ltop = avma, btop;
     759             :   GEN lastgood, so, vo;
     760         945 :   long lo = lg(o), nbo=lo-1;
     761         945 :   if (nbo == 1) return icopy(gel(o,1));
     762         413 :   so = ZV_indexsort(o); /* minimize max( o[i+1] - o[i] ) */
     763         413 :   vo = zero_zv(lo);
     764         413 :   lastgood = gel(o, so[nbo]);
     765         413 :   btop = avma;
     766             :   for(;;)
     767           0 :   {
     768         413 :     GEN lasto = gen_0;
     769         413 :     GEN P = grp->rand(E), t = mkvec(gen_0);
     770             :     long i;
     771         525 :     for (i = 1; i < lo; i++)
     772             :     {
     773         525 :       GEN newo = gel(o, so[i]);
     774         525 :       if (vo[i]) continue;
     775         525 :       t = grp->mul(E,t, grp->pow(E, P, subii(newo,lasto)));/*P^o[i]*/
     776         525 :       lasto = newo;
     777         525 :       if (!grp->equal1(t))
     778             :       {
     779         455 :         if (--nbo == 1) { set_avma(ltop); return icopy(lastgood); }
     780          42 :         vo[i] = 1;
     781             :       }
     782             :       else
     783          70 :         lastgood = lasto;
     784             :     }
     785           0 :     set_avma(btop);
     786             :   }
     787             : }
     788             : 
     789             : /*******************************************************************/
     790             : /*                                                                 */
     791             : /*                          n-th ROOT                              */
     792             : /*                                                                 */
     793             : /*******************************************************************/
     794             : /* Assume l is prime. Return a generator of the l-th Sylow and set *zeta to an element
     795             :  * of order l.
     796             :  *
     797             :  * q = l^e*r, e>=1, (r,l)=1
     798             :  * UNCLEAN */
     799             : static GEN
     800      269315 : gen_lgener(GEN l, long e, GEN r,GEN *zeta, void *E, const struct bb_group *grp)
     801             : {
     802      269315 :   const pari_sp av1 = avma;
     803             :   GEN m, m1;
     804             :   long i;
     805      210324 :   for (;; set_avma(av1))
     806             :   {
     807      479638 :     m1 = m = grp->pow(E, grp->rand(E), r);
     808      479638 :     if (grp->equal1(m)) continue;
     809      875723 :     for (i=1; i<e; i++)
     810             :     {
     811      606407 :       m = grp->pow(E,m,l);
     812      606408 :       if (grp->equal1(m)) break;
     813             :     }
     814      390519 :     if (i==e) break;
     815             :   }
     816      269315 :   *zeta = m; return m1;
     817             : }
     818             : 
     819             : /* Let G be a cyclic group of order o>1. Returns a (random) generator */
     820             : 
     821             : GEN
     822       15876 : gen_gener(GEN o, void *E, const struct bb_group *grp)
     823             : {
     824       15876 :   pari_sp ltop = avma, av;
     825             :   long i, lpr;
     826       15876 :   GEN F, N, pr, z=NULL;
     827       15876 :   F = get_arith_ZZM(o);
     828       15876 :   N = gel(F,1); pr = gel(F,2); lpr = lgcols(pr);
     829       15876 :   av = avma;
     830             : 
     831       51527 :   for (i = 1; i < lpr; i++)
     832             :   {
     833       35651 :     GEN l = gcoeff(pr,i,1);
     834       35651 :     long e = itos(gcoeff(pr,i,2));
     835       35651 :     GEN r = diviiexact(N,powis(l,e));
     836       35651 :     GEN zetan, zl = gen_lgener(l,e,r,&zetan,E,grp);
     837       35651 :     z = i==1 ? zl: grp->mul(E,z,zl);
     838       35651 :     if (gc_needed(av,2))
     839             :     { /* n can have lots of prime factors*/
     840           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_gener");
     841           0 :       z = gerepileupto(av, z);
     842             :     }
     843             :   }
     844       15876 :   return gerepileupto(ltop, z);
     845             : }
     846             : 
     847             : /* solve x^l = a , l prime in G of order q.
     848             :  *
     849             :  * q =  (l^e)*r, e >= 1, (r,l) = 1
     850             :  * y is not an l-th power, hence generates the l-Sylow of G
     851             :  * m = y^(q/l) != 1 */
     852             : static GEN
     853      234497 : gen_Shanks_sqrtl(GEN a, GEN l, long e, GEN r, GEN y, GEN m,void *E,
     854             :                  const struct bb_group *grp)
     855             : {
     856      234497 :   pari_sp av = avma;
     857             :   long k;
     858             :   GEN p1, u1, u2, v, w, z, dl;
     859             : 
     860      234497 :   (void)bezout(r,l,&u1,&u2);
     861      234497 :   v = grp->pow(E,a,u2);
     862      234497 :   w = grp->pow(E,v,l);
     863      234497 :   w = grp->mul(E,w,grp->pow(E,a,gen_m1));
     864      418842 :   while (!grp->equal1(w))
     865             :   {
     866      187208 :     k = 0;
     867      187208 :     p1 = w;
     868             :     do
     869             :     {
     870      323843 :       z = p1; p1 = grp->pow(E,p1,l);
     871      323843 :       k++;
     872      323843 :     } while(!grp->equal1(p1));
     873      187208 :     if (k==e) return gc_NULL(av);
     874      184345 :     dl = gen_plog(z,m,l,E,grp);
     875      184345 :     if (typ(dl) != t_INT) return gc_NULL(av);
     876      184345 :     dl = negi(dl);
     877      184345 :     p1 = grp->pow(E, grp->pow(E,y, dl), powiu(l,e-k-1));
     878      184345 :     m = grp->pow(E,m,dl);
     879      184345 :     e = k;
     880      184345 :     v = grp->mul(E,p1,v);
     881      184345 :     y = grp->pow(E,p1,l);
     882      184345 :     w = grp->mul(E,y,w);
     883      184345 :     if (gc_needed(av,1))
     884             :     {
     885           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_sqrtl");
     886           0 :       gerepileall(av,4, &y,&v,&w,&m);
     887             :     }
     888             :   }
     889      231634 :   return gerepilecopy(av, v);
     890             : }
     891             : /* Return one solution of x^n = a in a cyclic group of order q
     892             :  *
     893             :  * 1) If there is no solution, return NULL.
     894             :  *
     895             :  * 2) If there is a solution, there are exactly m of them [m = gcd(q-1,n)].
     896             :  * If zetan!=NULL, *zetan is set to a primitive m-th root of unity so that
     897             :  * the set of solutions is { x*zetan^k; k=0..m-1 }
     898             :  */
     899             : GEN
     900      243093 : gen_Shanks_sqrtn(GEN a, GEN n, GEN q, GEN *zetan, void *E, const struct bb_group *grp)
     901             : {
     902      243093 :   pari_sp ltop = avma;
     903             :   GEN m, u1, u2, z;
     904             :   int is_1;
     905             : 
     906      243093 :   if (is_pm1(n))
     907             :   {
     908           0 :     if (zetan) *zetan = grp->pow(E,a,gen_0);
     909           0 :     return signe(n) < 0? grp->pow(E,a,gen_m1): gcopy(a);
     910             :   }
     911      243093 :   is_1 = grp->equal1(a);
     912      243093 :   if (is_1 && !zetan) return gcopy(a);
     913             : 
     914      235392 :   m = bezout(n,q,&u1,&u2);
     915      235392 :   z = grp->pow(E,a,gen_0);
     916      235392 :   if (!is_pm1(m))
     917             :   {
     918      233509 :     GEN F = Z_factor(m);
     919             :     long i, j, e;
     920             :     GEN r, zeta, y, l;
     921      233510 :     pari_sp av1 = avma;
     922      464311 :     for (i = nbrows(F); i; i--)
     923             :     {
     924      233664 :       l = gcoeff(F,i,1);
     925      233664 :       j = itos(gcoeff(F,i,2));
     926      233664 :       e = Z_pvalrem(q,l,&r);
     927      233664 :       y = gen_lgener(l,e,r,&zeta,E,grp);
     928      233664 :       if (zetan) z = grp->mul(E,z, grp->pow(E,y,powiu(l,e-j)));
     929      233664 :       if (!is_1) {
     930             :         do
     931             :         {
     932      234497 :           a = gen_Shanks_sqrtl(a,l,e,r,y,zeta,E,grp);
     933      234497 :           if (!a) return gc_NULL(ltop);
     934      231634 :         } while (--j);
     935             :       }
     936      230801 :       if (gc_needed(ltop,1))
     937             :       { /* n can have lots of prime factors*/
     938           0 :         if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_sqrtn");
     939           0 :         gerepileall(av1, zetan? 2: 1, &a, &z);
     940             :       }
     941             :     }
     942             :   }
     943      232530 :   if (!equalii(m, n))
     944        1946 :     a = grp->pow(E,a,modii(u1,q));
     945      232530 :   if (zetan)
     946             :   {
     947         315 :     *zetan = z;
     948         315 :     gerepileall(ltop,2,&a,zetan);
     949             :   }
     950             :   else /* is_1 is 0: a was modified above -> gerepileupto valid */
     951      232215 :     a = gerepileupto(ltop, a);
     952      232530 :   return a;
     953             : }
     954             : 
     955             : /*******************************************************************/
     956             : /*                                                                 */
     957             : /*               structure of groups with pairing                  */
     958             : /*                                                                 */
     959             : /*******************************************************************/
     960             : 
     961             : static GEN
     962       41188 : ellgroup_d2(GEN N, GEN d)
     963             : {
     964       41188 :   GEN r = gcdii(N, d);
     965       41188 :   GEN F1 = gel(Z_factor(r), 1);
     966       41188 :   long i, j, l1 = lg(F1);
     967       41188 :   GEN F = cgetg(3, t_MAT);
     968       41188 :   gel(F,1) = cgetg(l1, t_COL);
     969       41188 :   gel(F,2) = cgetg(l1, t_COL);
     970       72310 :   for (i = 1, j = 1; i < l1; ++i)
     971             :   {
     972       31122 :     long v = Z_pval(N, gel(F1, i));
     973       31122 :     if (v<=1) continue;
     974       15988 :     gcoeff(F, j  , 1) = gel(F1, i);
     975       15988 :     gcoeff(F, j++, 2) = stoi(v);
     976             :   }
     977       41188 :   setlg(F[1],j); setlg(F[2],j);
     978       41188 :   return j==1 ? NULL : mkvec2(factorback(F), F);
     979             : }
     980             : 
     981             : GEN
     982       41349 : gen_ellgroup(GEN N, GEN d, GEN *pt_m, void *E, const struct bb_group *grp,
     983             :              GEN pairorder(void *E, GEN P, GEN Q, GEN m, GEN F))
     984             : {
     985       41349 :   pari_sp av = avma;
     986             :   GEN N0, N1, F;
     987       41349 :   if (pt_m) *pt_m = gen_1;
     988       41349 :   if (is_pm1(N)) return cgetg(1,t_VEC);
     989       41188 :   F = ellgroup_d2(N, d);
     990       41188 :   if (!F) {set_avma(av); return mkveccopy(N);}
     991       15260 :   N0 = gel(F,1); N1 = diviiexact(N, N0);
     992             :   while(1)
     993       11656 :   {
     994       26916 :     pari_sp av2 = avma;
     995             :     GEN P, Q, d, s, t, m;
     996             : 
     997       26916 :     P = grp->pow(E,grp->rand(E), N1);
     998       26916 :     s = gen_order(P, F, E, grp); if (equalii(s, N0)) {set_avma(av); return mkveccopy(N);}
     999             : 
    1000       21136 :     Q = grp->pow(E,grp->rand(E), N1);
    1001       21136 :     t = gen_order(Q, F, E, grp); if (equalii(t, N0)) {set_avma(av); return mkveccopy(N);}
    1002             : 
    1003       18250 :     m = lcmii(s, t);
    1004       18250 :     d = pairorder(E, P, Q, m, F);
    1005             :     /* structure is [N/d, d] iff m d == N0. Note that N/d = N1 m */
    1006       18250 :     if (is_pm1(d) && equalii(m, N0)) {set_avma(av); return mkveccopy(N);}
    1007       18243 :     if (equalii(mulii(m, d), N0))
    1008             :     {
    1009        6587 :       GEN g = mkvec2(mulii(N1,m), d);
    1010        6587 :       if (pt_m) *pt_m = m;
    1011        6587 :       gerepileall(av,pt_m?2:1,&g,pt_m);
    1012        6587 :       return g;
    1013             :     }
    1014       11656 :     set_avma(av2);
    1015             :   }
    1016             : }
    1017             : 
    1018             : GEN
    1019        2716 : gen_ellgens(GEN D1, GEN d2, GEN m, void *E, const struct bb_group *grp,
    1020             :              GEN pairorder(void *E, GEN P, GEN Q, GEN m, GEN F))
    1021             : {
    1022        2716 :   pari_sp ltop = avma, av;
    1023             :   GEN F, d1, dm;
    1024             :   GEN P, Q, d, s;
    1025        2716 :   F = get_arith_ZZM(D1);
    1026        2716 :   d1 = gel(F, 1), dm =  diviiexact(d1,m);
    1027        2716 :   av = avma;
    1028             :   do
    1029             :   {
    1030        6754 :     set_avma(av);
    1031        6754 :     P = grp->rand(E);
    1032        6754 :     s = gen_order(P, F, E, grp);
    1033        6754 :   } while (!equalii(s, d1));
    1034        2716 :   av = avma;
    1035             :   do
    1036             :   {
    1037        5112 :     set_avma(av);
    1038        5112 :     Q = grp->rand(E);
    1039        5112 :     d = pairorder(E, grp->pow(E, P, dm), grp->pow(E, Q, dm), m, F);
    1040        5112 :   } while (!equalii(d, d2));
    1041        2716 :   return gerepilecopy(ltop, mkvec2(P,Q));
    1042             : }

Generated by: LCOV version 1.13