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 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.10.0 lcov report (development 19825-b77c7f8) Lines: 519 562 92.3 %
Date: 2016-12-04 05:49:01 Functions: 33 34 97.1 %
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      912431 : int_block(GEN n, long i, long l)
      32             : {
      33      912431 :   long q = divsBIL(i), r = remsBIL(i)+1, lr;
      34      912555 :   GEN nw = int_W(n, q);
      35      912555 :   ulong w = (ulong) *nw, w2;
      36      912555 :   if (r>=l) return (w>>(r-l))&((1UL<<l)-1);
      37       58612 :   w &= (1UL<<r)-1; lr = l-r;
      38       58612 :   w2 = (ulong) *int_precW(nw); w2 >>= (BITS_IN_LONG-lr);
      39       58612 :   return (w<<lr)|w2;
      40             : }
      41             : 
      42             : /* assume n != 0, t_INT. Compute x^|n| using sliding window powering */
      43             : static GEN
      44     7449476 : 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     7449476 :   long i, l = expu(n), u = (1UL<<(e-1));
      49             :   long w, v;
      50     7450007 :   GEN tab = cgetg(1+u, t_VEC);
      51     7450200 :   GEN x2 = sqr(E, x), z = NULL, tw;
      52     7263681 :   gel(tab, 1) = x;
      53     7263681 :   for (i=2; i<=u; i++) gel(tab,i) = mul(E, gel(tab,i-1), x2);
      54     7261417 :   av = avma;
      55    66269093 :   while (l>=0)
      56             :   {
      57    51558650 :     if (e > l+1) e = l+1;
      58    51558650 :     w = (n>>(l+1-e)) & ((1UL<<e)-1); v = vals(w); l-=e;
      59    51680560 :     tw = gel(tab, 1+(w>>(v+1)));
      60    51680560 :     if (z)
      61             :     {
      62    44231331 :       for (i=1; i<=e-v; i++) z = sqr(E, z);
      63    44117094 :       z = mul(E, z, tw);
      64     7449229 :     } else z = tw;
      65    51551303 :     for (i=1; i<=v; i++) z = sqr(E, z);
      66   146388053 :     while (l>=0)
      67             :     {
      68    87225447 :       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    87432929 :       if (n&(1UL<<l)) break;
      74    43300338 :       z = sqr(E, z); l--;
      75             :     }
      76             :   }
      77     7449026 :   return z;
      78             : }
      79             : 
      80             : 
      81             : /* assume n != 0, t_INT. Compute x^|n| using sliding window powering */
      82             : static GEN
      83       72791 : sliding_window_pow(GEN x, GEN n, long e, void *E, GEN (*sqr)(void*,GEN),
      84             :                                                   GEN (*mul)(void*,GEN,GEN))
      85             : {
      86             :   pari_sp av;
      87       72791 :   long i, l = expi(n), u = (1UL<<(e-1));
      88             :   long w, v;
      89       72791 :   GEN tab = cgetg(1+u, t_VEC);
      90       72792 :   GEN x2 = sqr(E, x), z = NULL, tw;
      91       72348 :   gel(tab, 1) = x;
      92       72348 :   for (i=2; i<=u; i++) gel(tab,i) = mul(E, gel(tab,i-1), x2);
      93       72333 :   av = avma;
      94     1057635 :   while (l>=0)
      95             :   {
      96      912557 :     if (e > l+1) e = l+1;
      97      912557 :     w = int_block(n,l,e); v = vals(w); l-=e;
      98      915650 :     tw = gel(tab, 1+(w>>(v+1)));
      99      915650 :     if (z)
     100             :     {
     101      842859 :       for (i=1; i<=e-v; i++) z = sqr(E, z);
     102      839601 :       z = mul(E, z, tw);
     103       72791 :     } else z = tw;
     104      912468 :     for (i=1; i<=v; i++) z = sqr(E, z);
     105     6229064 :     while (l>=0)
     106             :     {
     107     5243458 :       if (gc_needed(av,1))
     108             :       {
     109          54 :         if (DEBUGMEM>1) pari_warn(warnmem,"sliding_window_pow (%ld)", l);
     110          54 :         z = gerepilecopy(av, z);
     111             :       }
     112     5243458 :       if (int_bit(n,l)) break;
     113     4405396 :       z = sqr(E, z); l--;
     114             :     }
     115             :   }
     116       72745 :   return z;
     117             : }
     118             : 
     119             : /* assume n != 0, t_INT. Compute x^|n| using leftright binary powering */
     120             : static GEN
     121    41448271 : leftright_binary_powu(GEN x, ulong n, void *E, GEN (*sqr)(void*,GEN),
     122             :                                               GEN (*mul)(void*,GEN,GEN))
     123             : {
     124    41448271 :   pari_sp av = avma;
     125             :   GEN  y;
     126             :   int j;
     127             : 
     128    41448271 :   if (n == 1) return x;
     129    41448271 :   y = x; j = 1+bfffo(n);
     130             :   /* normalize, i.e set highest bit to 1 (we know n != 0) */
     131    41448271 :   n<<=j; j = BITS_IN_LONG-j;
     132             :   /* first bit is now implicit */
     133   115813339 :   for (; j; n<<=1,j--)
     134             :   {
     135    74365230 :     y = sqr(E,y);
     136    74365024 :     if (n & HIGHBIT) y = mul(E,y,x); /* first bit set: multiply by base */
     137    74365068 :     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    41448109 :   return y;
     144             : }
     145             : 
     146             : GEN
     147    48965178 : gen_powu_i(GEN x, ulong n, void *E, GEN (*sqr)(void*,GEN),
     148             :                                     GEN (*mul)(void*,GEN,GEN))
     149             : {
     150             :   long l;
     151    48965178 :   if (n == 1) return x;
     152    48896850 :   l = expu(n);
     153    48898334 :   if (l<=8)
     154    41448247 :     return leftright_binary_powu(x, n, E, sqr, mul);
     155             :   else
     156     7450087 :     return sliding_window_powu(x, n, l<=24? 2: 3, E, sqr, mul);
     157             : }
     158             : 
     159             : GEN
     160     1077202 : gen_powu(GEN x, ulong n, void *E, GEN (*sqr)(void*,GEN),
     161             :                                   GEN (*mul)(void*,GEN,GEN))
     162             : {
     163     1077202 :   pari_sp av = avma;
     164     1077202 :   if (n == 1) return gcopy(x);
     165     1057799 :   return gerepilecopy(av, gen_powu_i(x,n,E,sqr,mul));
     166             : }
     167             : 
     168             : GEN
     169    16851157 : gen_pow_i(GEN x, GEN n, void *E, GEN (*sqr)(void*,GEN),
     170             :                                  GEN (*mul)(void*,GEN,GEN))
     171             : {
     172             :   long l, e;
     173    16851157 :   if (lgefint(n)==3) return gen_powu_i(x, uel(n,2), E, sqr, mul);
     174       72790 :   l = expi(n);
     175       72792 :   if      (l<=64)  e = 3;
     176       34260 :   else if (l<=160) e = 4;
     177        6080 :   else if (l<=384) e = 5;
     178        1166 :   else if (l<=896) e = 6;
     179         648 :   else             e = 7;
     180       72792 :   return sliding_window_pow(x, n, e, E, sqr, mul);
     181             : }
     182             : 
     183             : GEN
     184     1048180 : gen_pow(GEN x, GEN n, void *E, GEN (*sqr)(void*,GEN),
     185             :                                GEN (*mul)(void*,GEN,GEN))
     186             : {
     187     1048180 :   pari_sp av = avma;
     188     1048180 :   return gerepilecopy(av, gen_pow_i(x,n,E,sqr,mul));
     189             : }
     190             : 
     191             : /* assume n > 0. Compute x^n using left-right binary powering */
     192             : GEN
     193      204610 : gen_powu_fold_i(GEN x, ulong n, void *E, GEN  (*sqr)(void*,GEN),
     194             :                                          GEN (*msqr)(void*,GEN))
     195             : {
     196      204610 :   pari_sp av = avma;
     197             :   GEN y;
     198             :   int j;
     199             : 
     200      204610 :   if (n == 1) return x;
     201      204610 :   y = x; j = 1+bfffo(n);
     202             :   /* normalize, i.e set highest bit to 1 (we know n != 0) */
     203      204610 :   n<<=j; j = BITS_IN_LONG-j;
     204             :   /* first bit is now implicit */
     205     2650457 :   for (; j; n<<=1,j--)
     206             :   {
     207     2445847 :     if (n & HIGHBIT) y = msqr(E,y); /* first bit set: multiply by base */
     208     1933586 :     else y = sqr(E,y);
     209     2445847 :     if (gc_needed(av,1))
     210             :     {
     211           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"gen_powu_fold (%d)", j);
     212           0 :       y = gerepilecopy(av, y);
     213             :     }
     214             :   }
     215      204610 :   return y;
     216             : }
     217             : GEN
     218           0 : gen_powu_fold(GEN x, ulong n, void *E, GEN (*sqr)(void*,GEN),
     219             :                                        GEN (*msqr)(void*,GEN))
     220             : {
     221           0 :   pari_sp av = avma;
     222           0 :   if (n == 1) return gcopy(x);
     223           0 :   return gerepilecopy(av, gen_powu_fold_i(x,n,E,sqr,msqr));
     224             : }
     225             : 
     226             : /* assume N != 0, t_INT. Compute x^|N| using left-right binary powering */
     227             : GEN
     228      137347 : gen_pow_fold_i(GEN x, GEN N, void *E, GEN (*sqr)(void*,GEN),
     229             :                                       GEN (*msqr)(void*,GEN))
     230             : {
     231      137347 :   long ln = lgefint(N);
     232      137347 :   if (ln == 3) return gen_powu_fold_i(x, N[2], E, sqr, msqr);
     233             :   else
     234             :   {
     235       66223 :     GEN nd = int_MSW(N), y = x;
     236       66223 :     ulong n = *nd;
     237             :     long i;
     238             :     int j;
     239       66223 :     pari_sp av = avma;
     240             : 
     241       66223 :     if (n == 1)
     242        6466 :       j = 0;
     243             :     else
     244             :     {
     245       59757 :       j = 1+bfffo(n); /* < BIL */
     246             :       /* normalize, i.e set highest bit to 1 (we know n != 0) */
     247       59757 :       n <<= j; j = BITS_IN_LONG - j;
     248             :     }
     249             :     /* first bit is now implicit */
     250       66223 :     for (i=ln-2;;)
     251             :     {
     252     7476711 :       for (; j; n<<=1,j--)
     253             :       {
     254     7302128 :         if (n & HIGHBIT) y = msqr(E,y); /* first bit set: multiply by base */
     255     6436278 :         else y = sqr(E,y);
     256     7301467 :         if (gc_needed(av,1))
     257             :         {
     258           0 :           if (DEBUGMEM>1) pari_warn(warnmem,"gen_pow_fold (%d)", j);
     259           0 :           y = gerepilecopy(av, y);
     260             :         }
     261             :       }
     262      174583 :       if (--i == 0) return y;
     263      109021 :       nd = int_precW(nd);
     264      109021 :       n = *nd; j = BITS_IN_LONG;
     265      109021 :     }
     266             :   }
     267             : }
     268             : GEN
     269       71125 : gen_pow_fold(GEN x, GEN n, void *E, GEN (*sqr)(void*,GEN),
     270             :                                     GEN (*msqr)(void*,GEN))
     271             : {
     272       71125 :   pari_sp av = avma;
     273       71125 :   return gerepilecopy(av, gen_pow_fold_i(x,n,E,sqr,msqr));
     274             : }
     275             : 
     276             : GEN
     277     3840025 : gen_powers(GEN x, long l, int use_sqr, void *E, GEN (*sqr)(void*,GEN),
     278             :                                       GEN (*mul)(void*,GEN,GEN), GEN (*one)(void*))
     279             : {
     280             :   long i;
     281     3840025 :   GEN V = cgetg(l+2,t_VEC);
     282     3840026 :   gel(V,1) = one(E); if (l==0) return V;
     283     3828417 :   gel(V,2) = gcopy(x); if (l==1) return V;
     284     2463349 :   gel(V,3) = sqr(E,x);
     285     2463350 :   if (use_sqr)
     286     5401228 :     for(i = 4; i < l+2; i++)
     287     9220492 :       gel(V,i) = (i&1)? sqr(E,gel(V, (i+1)>>1))
     288     5431961 :                       : mul(E,gel(V, i-1),x);
     289             :   else
     290     2158003 :     for(i = 4; i < l+2; i++)
     291     1307353 :       gel(V,i) = mul(E,gel(V,i-1),x);
     292     2463348 :   return V;
     293             : }
     294             : 
     295             : GEN
     296     2599506 : producttree_scheme(long n)
     297             : {
     298             :   GEN v, w;
     299             :   long i, j, k, u, l;
     300     2599506 :   if (n<=2) return mkvecsmall(n);
     301     1537250 :   u = expu(n-1);
     302     1537247 :   v = cgetg(n+1,t_VECSMALL);
     303     1537220 :   w = cgetg(n+1,t_VECSMALL);
     304     1537314 :   v[1] = n; l = 1;
     305     4368446 :   for (i=1; i<=u; i++)
     306             :   {
     307    11503601 :     for(j=1, k=1; j<=l; j++, k+=2)
     308             :     {
     309     8672469 :       long vj = v[j], v2 = vj>>1;
     310     8672469 :       w[k]    = vj-v2;
     311     8672469 :       w[k+1]  = v2;
     312             :     }
     313     2831132 :     swap(v,w); l<<=1;
     314             :   }
     315     1537314 :   fixlg(v, l+1);
     316     1537245 :   avma = (pari_sp) v;
     317     1537245 :   return v;
     318             : }
     319             : 
     320             : GEN
     321     2738147 : gen_product(GEN x, void *data, GEN (*mul)(void *,GEN,GEN))
     322             : {
     323             :   pari_sp ltop;
     324     2738147 :   long i,k,lx = lg(x),lv;
     325             :   pari_timer ti;
     326             :   GEN v;
     327     2738147 :   if (DEBUGLEVEL>7) timer_start(&ti);
     328             : 
     329     2738172 :   if (lx == 1) return gen_1;
     330     2737522 :   if (lx == 2) return gcopy(gel(x,1));
     331     2563378 :   x = leafcopy(x); k = lx;
     332     2563427 :   v = producttree_scheme(lx-1); lv = lg(v);
     333     2563592 :   ltop = avma;
     334    13332463 :   for (k=1, i=1; k<lv; i+=v[k++])
     335    10769205 :     gel(x,k) = v[k]==1 ? gel(x,i): mul(data,gel(x,i),gel(x,i+1));
     336     7840052 :   while (k > 2)
     337             :   {
     338     2713541 :     if (DEBUGLEVEL>7)
     339           0 :       timer_printf(&ti,"gen_product: remaining objects %ld",k-1);
     340     2713734 :     lx = k; k = 1;
     341    10917405 :     for (i=1; i<lx-1; i+=2)
     342     8203906 :       gel(x,k++) = mul(data,gel(x,i),gel(x,i+1));
     343     2713499 :     if (i < lx) gel(x,k++) = gel(x,i);
     344     2713499 :     if (gc_needed(ltop,1))
     345           8 :       gerepilecoeffs(ltop,x+1,k-1);
     346             :   }
     347     2563253 :   return gel(x,1);
     348             : }
     349             : 
     350             : /***********************************************************************/
     351             : /**                                                                   **/
     352             : /**                    DISCRETE LOGARITHM                             **/
     353             : /**                                                                   **/
     354             : /***********************************************************************/
     355             : 
     356             : static GEN
     357    38321295 : iter_rho(GEN x, GEN g, GEN q, GEN A, ulong h, void *E, const struct bb_group *grp)
     358             : {
     359    38321295 :   GEN a = gel(A,1);
     360    38321295 :   switch((h|grp->hash(a))%3UL)
     361             :   {
     362             :     case 0:
     363    12786299 :       return mkvec3(grp->pow(E,a,gen_2),Fp_mulu(gel(A,2),2,q),
     364    12786299 :                                         Fp_mulu(gel(A,3),2,q));
     365             :     case 1:
     366    12769136 :       return mkvec3(grp->mul(E,a,x),addis(gel(A,2),1),gel(A,3));
     367             :     case 2:
     368    12765860 :       return mkvec3(grp->mul(E,a,g),gel(A,2),addis(gel(A,3),1));
     369             :   }
     370           0 :   return NULL;
     371             : }
     372             : 
     373             : /*Generic Pollard rho discrete log algorithm*/
     374             : static GEN
     375          49 : gen_Pollard_log(GEN x, GEN g, GEN q, void *E, const struct bb_group *grp)
     376             : {
     377          49 :   pari_sp av=avma;
     378          49 :   GEN A, B, l, sqrt4q = sqrti(shifti(q,4));
     379          49 :   ulong i, h = 0, imax = itou_or_0(sqrt4q);
     380          49 :   if (!imax) imax = ULONG_MAX;
     381             :   do {
     382             :  rho_restart:
     383          49 :     A = B = mkvec3(x,gen_1,gen_0);
     384          49 :     i=0;
     385             :     do {
     386    12773765 :       if (i>imax)
     387             :       {
     388           0 :         h++;
     389           0 :         if (DEBUGLEVEL)
     390           0 :           pari_warn(warner,"changing Pollard rho hash seed to %ld",h);
     391           0 :         goto rho_restart;
     392             :       }
     393    12773765 :       A = iter_rho(x, g, q, A, h, E, grp);
     394    12773765 :       B = iter_rho(x, g, q, B, h, E, grp);
     395    12773765 :       B = iter_rho(x, g, q, B, h, E, grp);
     396    12773765 :       if (gc_needed(av,2))
     397             :       {
     398        1123 :         if(DEBUGMEM>1) pari_warn(warnmem,"gen_Pollard_log");
     399        1123 :         gerepileall(av, 2, &A, &B);
     400             :       }
     401    12773765 :       i++;
     402    12773765 :     } while (!grp->equal(gel(A,1), gel(B,1)));
     403          49 :     gel(A,2) = modii(gel(A,2), q);
     404          49 :     gel(B,2) = modii(gel(B,2), q);
     405          49 :     h++;
     406          49 :   } while (equalii(gel(A,2), gel(B,2)));
     407          49 :   l = Fp_div(Fp_sub(gel(B,3), gel(A,3),q),Fp_sub(gel(A,2), gel(B,2), q), q);
     408          49 :   return gerepileuptoint(av, l);
     409             : }
     410             : 
     411             : /* compute a hash of g^(i-1), 1<=i<=n. Return [sorted hash, perm, g^-n] */
     412             : GEN
     413     2185937 : gen_Shanks_init(GEN g, long n, void *E, const struct bb_group *grp)
     414             : {
     415     2185937 :   GEN p1 = g, G, perm, table = cgetg(n+1,t_VECSMALL);
     416     2185937 :   pari_sp av=avma;
     417             :   long i;
     418     2185937 :   table[1] = grp->hash(grp->pow(E,g,gen_0));
     419    11000752 :   for (i=2; i<=n; i++)
     420             :   {
     421     8814815 :     table[i] = grp->hash(p1);
     422     8814815 :     p1 = grp->mul(E,p1,g);
     423     8814815 :     if (gc_needed(av,2))
     424             :     {
     425           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_log, baby = %ld", i);
     426           0 :       p1 = gerepileupto(av, p1);
     427             :     }
     428             :   }
     429     2185937 :   G = gerepileupto(av, grp->pow(E,p1,gen_m1)); /* g^-n */
     430     2185937 :   perm = vecsmall_indexsort(table);
     431     2185937 :   table = vecsmallpermute(table,perm);
     432     2185937 :   return mkvec4(table,perm,g,G);
     433             : }
     434             : /* T from gen_Shanks_init(g,n). Return v < n*N such that x = g^v or NULL */
     435             : GEN
     436     2186385 : gen_Shanks(GEN T, GEN x, ulong N, void *E, const struct bb_group *grp)
     437             : {
     438     2186385 :   pari_sp av=avma;
     439     2186385 :   GEN table = gel(T,1), perm = gel(T,2), g = gel(T,3), G = gel(T,4);
     440     2186385 :   GEN p1 = x;
     441     2186385 :   long n = lg(table)-1;
     442             :   ulong k;
     443    12254113 :   for (k=0; k<N; k++)
     444             :   { /* p1 = x G^k, G = g^-n */
     445    12013306 :     long h = grp->hash(p1), i = zv_search(table, h);
     446    12013306 :     if (i)
     447             :     {
     448     1946323 :       do i--; while (i && table[i] == h);
     449     1945578 :       for (i++; i <= n && table[i] == h; i++)
     450             :       {
     451     1945578 :         GEN v = addiu(muluu(n,k), perm[i]-1);
     452     1945578 :         if (grp->equal(grp->pow(E,g,v),x)) return gerepileuptoint(av,v);
     453           0 :         if (DEBUGLEVEL)
     454           0 :           err_printf("gen_Shanks_log: false positive %lu, %lu\n", k,h);
     455             :       }
     456             :     }
     457    10067728 :     p1 = grp->mul(E,p1,G);
     458    10067728 :     if (gc_needed(av,2))
     459             :     {
     460           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_log, k = %lu", k);
     461           0 :       p1 = gerepileupto(av, p1);
     462             :     }
     463             :   }
     464      240807 :   return NULL;
     465             : }
     466             : /* Generic Shanks baby-step/giant-step algorithm. Return log_g(x), ord g = q.
     467             :  * One-shot: use gen_Shanks_init/log if many logs are desired; early abort
     468             :  * if log < sqrt(q) */
     469             : static GEN
     470       93959 : gen_Shanks_log(GEN x, GEN g, GEN q, void *E, const struct bb_group *grp)
     471             : {
     472       93959 :   pari_sp av=avma, av1;
     473             :   long lbaby, i, k;
     474             :   GEN p1, table, giant, perm, ginv;
     475       93959 :   p1 = sqrti(q);
     476       93959 :   if (abscmpiu(p1,LGBITS) >= 0)
     477           0 :     pari_err_OVERFLOW("gen_Shanks_log [order too large]");
     478       93959 :   lbaby = itos(p1)+1; table = cgetg(lbaby+1,t_VECSMALL);
     479       93959 :   ginv = grp->pow(E,g,gen_m1);
     480       93959 :   av1 = avma;
     481      898187 :   for (p1=x, i=1;;i++)
     482             :   {
     483      898187 :     if (grp->equal1(p1)) { avma = av; return stoi(i-1); }
     484      888489 :     table[i] = grp->hash(p1); if (i==lbaby) break;
     485      804228 :     p1 = grp->mul(E,p1,ginv);
     486      804228 :     if (gc_needed(av1,2))
     487             :     {
     488           7 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_log, baby = %ld", i);
     489           7 :       p1 = gerepileupto(av1, p1);
     490             :     }
     491      804228 :   }
     492       84261 :   p1 = giant = gerepileupto(av1, grp->mul(E,x,grp->pow(E, p1, gen_m1)));
     493       84261 :   perm = vecsmall_indexsort(table);
     494       84261 :   table = vecsmallpermute(table,perm);
     495       84261 :   av1 = avma;
     496      564474 :   for (k=1; k<= lbaby; k++)
     497             :   {
     498      564466 :     long h = grp->hash(p1), i = zv_search(table, h);
     499      564466 :     if (i)
     500             :     {
     501       84254 :       while (table[i] == h && i) i--;
     502       84255 :       for (i++; i <= lbaby && table[i] == h; i++)
     503             :       {
     504       84254 :         GEN v = addiu(mulss(lbaby-1,k),perm[i]-1);
     505       84254 :         if (grp->equal(grp->pow(E,g,v),x)) return gerepileuptoint(av,v);
     506           1 :         if (DEBUGLEVEL)
     507           0 :           err_printf("gen_Shanks_log: false positive %ld, %lu\n", k,h);
     508             :       }
     509             :     }
     510      480213 :     p1 = grp->mul(E,p1,giant);
     511      480213 :     if (gc_needed(av1,2))
     512             :     {
     513           7 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_log, k = %ld", k);
     514           7 :       p1 = gerepileupto(av1, p1);
     515             :     }
     516             :   }
     517           8 :   avma = av; return cgetg(1, t_VEC); /* no solution */
     518             : }
     519             : 
     520             : /*Generic discrete logarithme in a group of prime order p*/
     521             : GEN
     522      439740 : gen_plog(GEN x, GEN g, GEN p, void *E, const struct bb_group *grp)
     523             : {
     524      439740 :   if (grp->easylog)
     525             :   {
     526      400510 :     GEN e = grp->easylog(E, x, g, p);
     527      400510 :     if (e) return e;
     528             :   }
     529      121194 :   if (grp->equal1(x)) return gen_0;
     530      121152 :   if (grp->equal(x,g)) return gen_1;
     531       94008 :   if (expi(p)<32) return gen_Shanks_log(x,g,p,E,grp);
     532          49 :   return gen_Pollard_log(x, g, p, E, grp);
     533             : }
     534             : 
     535             : GEN
     536     5547242 : get_arith_ZZM(GEN o)
     537             : {
     538     5547242 :   if (!o) return NULL;
     539     5547242 :   switch(typ(o))
     540             :   {
     541             :     case t_INT:
     542     3989545 :       if (signe(o) > 0) return mkvec2(o, Z_factor(o));
     543           7 :       break;
     544             :     case t_MAT:
     545     1132585 :       if (is_Z_factorpos(o)) return mkvec2(factorback(o), o);
     546          14 :       break;
     547             :     case t_VEC:
     548      425105 :       if (lg(o) == 3 && signe(gel(o,1)) > 0 && is_Z_factorpos(gel(o,2))) return o;
     549           0 :       break;
     550             :   }
     551          28 :   pari_err_TYPE("generic discrete logarithm (order factorization)",o);
     552           0 :   return NULL; /* not reached */
     553             : }
     554             : GEN
     555       60313 : get_arith_Z(GEN o)
     556             : {
     557       60313 :   if (!o) return NULL;
     558       60313 :   switch(typ(o))
     559             :   {
     560             :     case t_INT:
     561       43188 :       if (signe(o) > 0) return o;
     562           7 :       break;
     563             :     case t_MAT:
     564          14 :       o = factorback(o);
     565           0 :       if (typ(o) == t_INT && signe(o) > 0) return o;
     566           0 :       break;
     567             :     case t_VEC:
     568       17104 :       if (lg(o) != 3) break;
     569       17104 :       o = gel(o,1);
     570       17104 :       if (typ(o) == t_INT && signe(o) > 0) return o;
     571           0 :       break;
     572             :   }
     573          14 :   pari_err_TYPE("generic discrete logarithm (order factorization)",o);
     574           0 :   return NULL; /* not reached */
     575             : }
     576             : 
     577             : /* grp->easylog() is an optional trapdoor function that catch easy logarithms*/
     578             : /* Generic Pohlig-Hellman discrete logarithm*/
     579             : /* smallest integer n such that g^n=a. Assume g has order ord */
     580             : GEN
     581      184536 : gen_PH_log(GEN a, GEN g, GEN ord, void *E, const struct bb_group *grp)
     582             : {
     583      184536 :   pari_sp av = avma;
     584             :   GEN v,t0,a0,b,q,g_q,n_q,ginv0,qj,ginv;
     585             :   GEN fa, ex;
     586             :   long e,i,j,l;
     587             : 
     588      184536 :   if (grp->equal(g, a)) /* frequent special case */
     589       35283 :     return grp->equal1(g)? gen_0: gen_1;
     590      149253 :   if (grp->easylog)
     591             :   {
     592      149155 :     GEN e = grp->easylog(E, a, g, ord);
     593      149127 :     if (e) return e;
     594             :   }
     595       96467 :   v = get_arith_ZZM(ord);
     596       96467 :   ord= gel(v,1);
     597       96467 :   fa = gel(v,2);
     598       96467 :   ex = gel(fa,2);
     599       96467 :   fa = gel(fa,1); l = lg(fa);
     600       96467 :   ginv = grp->pow(E,g,gen_m1);
     601       96467 :   v = cgetg(l, t_VEC);
     602      258203 :   for (i=1; i<l; i++)
     603             :   {
     604      162069 :     q = gel(fa,i);
     605      162069 :     e = itos(gel(ex,i));
     606      162069 :     if (DEBUGLEVEL>5)
     607           0 :       err_printf("Pohlig-Hellman: DL mod %Ps^%ld\n",q,e);
     608      162069 :     qj = new_chunk(e+1);
     609      162069 :     gel(qj,0) = gen_1;
     610      162069 :     gel(qj,1) = q;
     611      162069 :     for (j=2; j<=e; j++) gel(qj,j) = mulii(gel(qj,j-1), q);
     612      162069 :     t0 = diviiexact(ord, gel(qj,e));
     613      162069 :     a0 = grp->pow(E, a, t0);
     614      162069 :     ginv0 = grp->pow(E, ginv, t0); /* order q^e */
     615      162069 :     if (grp->equal1(ginv0))
     616             :     {
     617          14 :       gel(v,i) = mkintmod(gen_0, gen_1);
     618          14 :       continue;
     619             :     }
     620      162062 :     do { g_q = grp->pow(E,g, mulii(t0, gel(qj,--e))); /* order q */
     621      162062 :     } while (grp->equal1(g_q));
     622      162055 :     n_q = gen_0;
     623      247207 :     for (j=0;; j++)
     624             :     { /* n_q = sum_{i<j} b_i q^i */
     625      247207 :       b = grp->pow(E,a0, gel(qj,e-j));
     626             :       /* early abort: cheap and very effective */
     627      247207 :       if (j == 0 && !grp->equal1(grp->pow(E,b,q))) {
     628         325 :         avma = av; return cgetg(1, t_VEC);
     629             :       }
     630      246882 :       b = gen_plog(b, g_q, q, E, grp);
     631      246882 :       if (typ(b) != t_INT) { avma = av; return cgetg(1, t_VEC); }
     632      246874 :       n_q = addii(n_q, mulii(b, gel(qj,j)));
     633      246874 :       if (j == e) break;
     634             : 
     635       85152 :       a0 = grp->mul(E,a0, grp->pow(E,ginv0, b));
     636       85152 :       ginv0 = grp->pow(E,ginv0, q);
     637       85152 :     }
     638      161722 :     gel(v,i) = mkintmod(n_q, gel(qj,e+1));
     639             :   }
     640       96134 :   return gerepileuptoint(av, lift(chinese1_coprime_Z(v)));
     641             : }
     642             : 
     643             : /***********************************************************************/
     644             : /**                                                                   **/
     645             : /**                    ORDER OF AN ELEMENT                            **/
     646             : /**                                                                   **/
     647             : /***********************************************************************/
     648             : /*Find the exact order of a assuming a^o==1*/
     649             : GEN
     650     2901639 : gen_order(GEN a, GEN o, void *E, const struct bb_group *grp)
     651             : {
     652     2901639 :   pari_sp av = avma;
     653             :   long i, l;
     654             :   GEN m;
     655             : 
     656     2901639 :   m = get_arith_ZZM(o);
     657     2901639 :   if (!m) pari_err_TYPE("gen_order [missing order]",a);
     658     2901639 :   o = gel(m,1);
     659     2901639 :   m = gel(m,2); l = lgcols(m);
     660     9276921 :   for (i = l-1; i; i--)
     661             :   {
     662     6375282 :     GEN t, y, p = gcoeff(m,i,1);
     663     6375282 :     long j, e = itos(gcoeff(m,i,2));
     664     6375282 :     if (l == 2) {
     665      569714 :       t = gen_1;
     666      569714 :       y = a;
     667             :     } else {
     668     5805568 :       t = diviiexact(o, powiu(p,e));
     669     5805568 :       y = grp->pow(E, a, t);
     670             :     }
     671     6375282 :     if (grp->equal1(y)) o = t;
     672             :     else {
     673     6032641 :       for (j = 1; j < e; j++)
     674             :       {
     675     2030292 :         y = grp->pow(E, y, p);
     676     2030292 :         if (grp->equal1(y)) break;
     677             :       }
     678     4507352 :       if (j < e) {
     679      505003 :         if (j > 1) p = powiu(p, j);
     680      505003 :         o = mulii(t, p);
     681             :       }
     682             :     }
     683             :   }
     684     2901639 :   return gerepilecopy(av, o);
     685             : }
     686             : 
     687             : /*Find the exact order of a assuming a^o==1, return [order,factor(order)] */
     688             : GEN
     689     2255754 : gen_factored_order(GEN a, GEN o, void *E, const struct bb_group *grp)
     690             : {
     691     2255754 :   pari_sp av = avma;
     692             :   long i, l, ind;
     693             :   GEN m, F, P;
     694             : 
     695     2255754 :   m = get_arith_ZZM(o);
     696     2255754 :   if (!m) pari_err_TYPE("gen_factored_order [missing order]",a);
     697     2255754 :   o = gel(m,1);
     698     2255754 :   m = gel(m,2); l = lgcols(m);
     699     2255754 :   P = cgetg(l, t_COL); ind = 1;
     700     2255754 :   F = cgetg(l, t_COL);
     701     5420304 :   for (i = l-1; i; i--)
     702             :   {
     703     3164550 :     GEN t, y, p = gcoeff(m,i,1);
     704     3164550 :     long j, e = itos(gcoeff(m,i,2));
     705     3164550 :     if (l == 2) {
     706     1383386 :       t = gen_1;
     707     1383386 :       y = a;
     708             :     } else {
     709     1781164 :       t = diviiexact(o, powiu(p,e));
     710     1781164 :       y = grp->pow(E, a, t);
     711             :     }
     712     3164550 :     if (grp->equal1(y)) o = t;
     713             :     else {
     714     3968738 :       for (j = 1; j < e; j++)
     715             :       {
     716      843917 :         y = grp->pow(E, y, p);
     717      843917 :         if (grp->equal1(y)) break;
     718             :       }
     719     3135445 :       gel(P,ind) = p;
     720     3135445 :       gel(F,ind) = utoipos(j);
     721     3135445 :       if (j < e) {
     722       10624 :         if (j > 1) p = powiu(p, j);
     723       10624 :         o = mulii(t, p);
     724             :       }
     725     3135445 :       ind++;
     726             :     }
     727             :   }
     728     2255754 :   setlg(P, ind); P = vecreverse(P);
     729     2255754 :   setlg(F, ind); F = vecreverse(F);
     730     2255754 :   return gerepilecopy(av, mkvec2(o, mkmat2(P,F)));
     731             : }
     732             : 
     733             : /* E has order o[1], ..., or o[#o], draw random points until all solutions
     734             :  * but one are eliminated */
     735             : GEN
     736         882 : gen_select_order(GEN o, void *E, const struct bb_group *grp)
     737             : {
     738         882 :   pari_sp ltop = avma, btop;
     739             :   GEN lastgood, so, vo;
     740         882 :   long lo = lg(o), nbo=lo-1;
     741         882 :   if (nbo == 1) return icopy(gel(o,1));
     742         413 :   so = ZV_indexsort(o); /* minimize max( o[i+1] - o[i] ) */
     743         413 :   vo = zero_zv(lo);
     744         413 :   lastgood = gel(o, so[nbo]);
     745         413 :   btop = avma;
     746             :   for(;;)
     747             :   {
     748         413 :     GEN lasto = gen_0;
     749         413 :     GEN P = grp->rand(E), t = mkvec(gen_0);
     750             :     long i;
     751         518 :     for (i = 1; i < lo; i++)
     752             :     {
     753         518 :       GEN newo = gel(o, so[i]);
     754         518 :       if (vo[i]) continue;
     755         518 :       t = grp->mul(E,t, grp->pow(E, P, subii(newo,lasto)));/*P^o[i]*/
     756         518 :       lasto = newo;
     757         518 :       if (!grp->equal1(t))
     758             :       {
     759         455 :         if (--nbo == 1) { avma=ltop; return icopy(lastgood); }
     760          42 :         vo[i] = 1;
     761             :       }
     762             :       else
     763          63 :         lastgood = lasto;
     764             :     }
     765           0 :     avma = btop;
     766           0 :   }
     767             : }
     768             : 
     769             : /*******************************************************************/
     770             : /*                                                                 */
     771             : /*                          n-th ROOT                              */
     772             : /*                                                                 */
     773             : /*******************************************************************/
     774             : /* Assume l is prime. Return a generator of the l-th Sylow and set *zeta to an element
     775             :  * of order l.
     776             :  *
     777             :  * q = l^e*r, e>=1, (r,l)=1
     778             :  * UNCLEAN */
     779             : static GEN
     780      296114 : gen_lgener(GEN l, long e, GEN r,GEN *zeta, void *E, const struct bb_group *grp)
     781             : {
     782      296114 :   const pari_sp av1 = avma;
     783             :   GEN m, m1;
     784             :   long i;
     785      223664 :   for (;; avma = av1)
     786             :   {
     787      519778 :     m1 = m = grp->pow(E, grp->rand(E), r);
     788      519780 :     if (grp->equal1(m)) continue;
     789      923210 :     for (i=1; i<e; i++)
     790             :     {
     791      627093 :       m = grp->pow(E,m,l);
     792      627093 :       if (grp->equal1(m)) break;
     793             :     }
     794      420553 :     if (i==e) break;
     795      223664 :   }
     796      296117 :   *zeta = m; return m1;
     797             : }
     798             : 
     799             : /* Let G be a cyclic group of order o>1. Returns a (random) generator */
     800             : 
     801             : GEN
     802       14665 : gen_gener(GEN o, void *E, const struct bb_group *grp)
     803             : {
     804       14665 :   pari_sp ltop = avma, av;
     805             :   long i, lpr;
     806       14665 :   GEN F, N, pr, z=NULL;
     807       14665 :   F = get_arith_ZZM(o);
     808       14665 :   N = gel(F,1); pr = gel(F,2); lpr = lgcols(pr);
     809       14665 :   av = avma;
     810             : 
     811       48811 :   for (i = 1; i < lpr; i++)
     812             :   {
     813       34146 :     GEN l = gcoeff(pr,i,1);
     814       34146 :     long e = itos(gcoeff(pr,i,2));
     815       34146 :     GEN r = diviiexact(N,powis(l,e));
     816       34146 :     GEN zetan, zl = gen_lgener(l,e,r,&zetan,E,grp);
     817       34146 :     z = i==1 ? zl: grp->mul(E,z,zl);
     818       34146 :     if (gc_needed(av,2))
     819             :     { /* n can have lots of prime factors*/
     820           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_gener");
     821           0 :       z = gerepileupto(av, z);
     822             :     }
     823             :   }
     824       14665 :   return gerepileupto(ltop, z);
     825             : }
     826             : 
     827             : /* solve x^l = a , l prime in G of order q.
     828             :  *
     829             :  * q =  (l^e)*r, e >= 1, (r,l) = 1
     830             :  * y is not an l-th power, hence generates the l-Sylow of G
     831             :  * m = y^(q/l) != 1 */
     832             : static GEN
     833      261676 : gen_Shanks_sqrtl(GEN a, GEN l, long e, GEN r, GEN y, GEN m,void *E,
     834             :                  const struct bb_group *grp)
     835             : {
     836      261676 :   pari_sp av = avma;
     837             :   long k;
     838             :   GEN p1, u1, u2, v, w, z, dl;
     839             : 
     840      261676 :   (void)bezout(r,l,&u1,&u2);
     841      261676 :   v = grp->pow(E,a,u2);
     842      261676 :   w = grp->pow(E,v,l);
     843      261675 :   w = grp->mul(E,w,grp->pow(E,a,gen_m1));
     844      716182 :   while (!grp->equal1(w))
     845             :   {
     846      198669 :     k = 0;
     847      198669 :     p1 = w;
     848             :     do
     849             :     {
     850      338062 :       z = p1; p1 = grp->pow(E,p1,l);
     851      338062 :       k++;
     852      338062 :     } while(!grp->equal1(p1));
     853      198669 :     if (k==e) { avma = av; return NULL; }
     854      192858 :     dl = gen_plog(z,m,l,E,grp);
     855      192858 :     if (typ(dl) != t_INT) { avma = av; return NULL; }
     856      192858 :     dl = negi(dl);
     857      192858 :     p1 = grp->pow(E, grp->pow(E,y, dl), powiu(l,e-k-1));
     858      192857 :     m = grp->pow(E,m,dl);
     859      192858 :     e = k;
     860      192858 :     v = grp->mul(E,p1,v);
     861      192858 :     y = grp->pow(E,p1,l);
     862      192858 :     w = grp->mul(E,y,w);
     863      192858 :     if (gc_needed(av,1))
     864             :     {
     865           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_sqrtl");
     866           0 :       gerepileall(av,4, &y,&v,&w,&m);
     867             :     }
     868             :   }
     869      255851 :   return gerepilecopy(av, v);
     870             : }
     871             : /* Return one solution of x^n = a in a cyclic group of order q
     872             :  *
     873             :  * 1) If there is no solution, return NULL.
     874             :  *
     875             :  * 2) If there is a solution, there are exactly m of them [m = gcd(q-1,n)].
     876             :  * If zetan!=NULL, *zetan is set to a primitive m-th root of unity so that
     877             :  * the set of solutions is { x*zetan^k; k=0..m-1 }
     878             :  */
     879             : GEN
     880      279428 : gen_Shanks_sqrtn(GEN a, GEN n, GEN q, GEN *zetan, void *E, const struct bb_group *grp)
     881             : {
     882      279428 :   pari_sp ltop = avma;
     883             :   GEN m, u1, u2, z;
     884             :   int is_1;
     885             : 
     886      279428 :   if (is_pm1(n))
     887             :   {
     888           0 :     if (zetan) *zetan = grp->pow(E,a,gen_0);
     889           0 :     return signe(n) < 0? grp->pow(E,a,gen_m1): gcopy(a);
     890             :   }
     891      279427 :   is_1 = grp->equal1(a);
     892      279427 :   if (is_1 && !zetan) return gcopy(a);
     893             : 
     894      268339 :   m = bezout(n,q,&u1,&u2);
     895      268339 :   z = grp->pow(E,a,gen_0);
     896      268337 :   if (!is_pm1(m))
     897             :   {
     898      261918 :     GEN F = Z_factor(m);
     899             :     long i, j, e;
     900             :     GEN r, zeta, y, l;
     901      261920 :     pari_sp av1 = avma;
     902      518066 :     for (i = nbrows(F); i; i--)
     903             :     {
     904      261968 :       l = gcoeff(F,i,1);
     905      261968 :       j = itos(gcoeff(F,i,2));
     906      261970 :       e = Z_pvalrem(q,l,&r);
     907      261969 :       y = gen_lgener(l,e,r,&zeta,E,grp);
     908      261971 :       if (zetan) z = grp->mul(E,z, grp->pow(E,y,powiu(l,e-j)));
     909      261971 :       if (!is_1) {
     910             :         do
     911             :         {
     912      261676 :           a = gen_Shanks_sqrtl(a,l,e,r,y,zeta,E,grp);
     913      261662 :           if (!a) { avma = ltop; return NULL;}
     914      255851 :         } while (--j);
     915             :       }
     916      256146 :       if (gc_needed(ltop,1))
     917             :       { /* n can have lots of prime factors*/
     918           0 :         if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_sqrtn");
     919           0 :         gerepileall(av1, zetan? 2: 1, &a, &z);
     920             :       }
     921             :     }
     922             :   }
     923      262516 :   if (!equalii(m, n))
     924        6440 :     a = grp->pow(E,a,modii(u1,q));
     925      262516 :   if (zetan)
     926             :   {
     927         540 :     *zetan = z;
     928         540 :     gerepileall(ltop,2,&a,zetan);
     929             :   }
     930             :   else /* is_1 is 0: a was modified above -> gerepileupto valid */
     931      261976 :     a = gerepileupto(ltop, a);
     932      262516 :   return a;
     933             : }
     934             : 
     935             : /*******************************************************************/
     936             : /*                                                                 */
     937             : /*               structure of groups with pairing                  */
     938             : /*                                                                 */
     939             : /*******************************************************************/
     940             : 
     941             : static GEN
     942       39494 : ellgroup_d2(GEN N, GEN d)
     943             : {
     944       39494 :   GEN r = gcdii(N, d);
     945       39494 :   GEN F1 = gel(Z_factor(r), 1);
     946       39494 :   long i, j, l1 = lg(F1);
     947       39494 :   GEN F = cgetg(3, t_MAT);
     948       39494 :   gel(F,1) = cgetg(l1, t_COL);
     949       39494 :   gel(F,2) = cgetg(l1, t_COL);
     950       69524 :   for (i = 1, j = 1; i < l1; ++i)
     951             :   {
     952       30030 :     long v = Z_pval(N, gel(F1, i));
     953       30030 :     if (v<=1) continue;
     954       15547 :     gcoeff(F, j  , 1) = gel(F1, i);
     955       15547 :     gcoeff(F, j++, 2) = stoi(v);
     956             :   }
     957       39494 :   setlg(F[1],j); setlg(F[2],j);
     958       39494 :   return j==1 ? NULL : mkvec2(factorback(F), F);
     959             : }
     960             : 
     961             : GEN
     962       39571 : gen_ellgroup(GEN N, GEN d, GEN *pt_m, void *E, const struct bb_group *grp,
     963             :              GEN pairorder(void *E, GEN P, GEN Q, GEN m, GEN F))
     964             : {
     965       39571 :   pari_sp av = avma;
     966             :   GEN N0, N1, F;
     967       39571 :   if (pt_m) *pt_m = gen_1;
     968       39571 :   if (is_pm1(N)) return cgetg(1,t_VEC);
     969       39494 :   F = ellgroup_d2(N, d);
     970       39494 :   if (!F) {avma = av; return mkveccopy(N);}
     971       14833 :   N0 = gel(F,1); N1 = diviiexact(N, N0);
     972             :   while(1)
     973             :   {
     974       26218 :     pari_sp av2 = avma;
     975             :     GEN P, Q, d, s, t, m;
     976             : 
     977       26218 :     P = grp->pow(E,grp->rand(E), N1);
     978       26218 :     s = gen_order(P, F, E, grp); if (equalii(s, N0)) {avma = av; return mkveccopy(N);}
     979             : 
     980       20503 :     Q = grp->pow(E,grp->rand(E), N1);
     981       20503 :     t = gen_order(Q, F, E, grp); if (equalii(t, N0)) {avma = av; return mkveccopy(N);}
     982             : 
     983       17881 :     m = lcmii(s, t);
     984       17881 :     d = pairorder(E, P, Q, m, F);
     985             :     /* structure is [N/d, d] iff m d == N0. Note that N/d = N1 m */
     986       17881 :     if (is_pm1(d) && equalii(m, N0)) {avma = av; return mkveccopy(N);}
     987       17853 :     if (equalii(mulii(m, d), N0))
     988             :     {
     989        6468 :       GEN g = mkvec2(mulii(N1,m), d);
     990        6468 :       if (pt_m) *pt_m = m;
     991        6468 :       gerepileall(av,pt_m?2:1,&g,pt_m);
     992        6468 :       return g;
     993             :     }
     994       11385 :     avma = av2;
     995       11385 :   }
     996             : }
     997             : 
     998             : GEN
     999        2646 : gen_ellgens(GEN D1, GEN d2, GEN m, void *E, const struct bb_group *grp,
    1000             :              GEN pairorder(void *E, GEN P, GEN Q, GEN m, GEN F))
    1001             : {
    1002        2646 :   pari_sp ltop = avma, av;
    1003             :   GEN F, d1, dm;
    1004             :   GEN P, Q, d, s;
    1005        2646 :   F = get_arith_ZZM(D1);
    1006        2646 :   d1 = gel(F, 1), dm =  diviiexact(d1,m);
    1007        2646 :   av = avma;
    1008             :   do
    1009             :   {
    1010        7027 :     avma = av;
    1011        7027 :     P = grp->rand(E);
    1012        7027 :     s = gen_order(P, F, E, grp);
    1013        7027 :   } while (!equalii(s, d1));
    1014        2646 :   av = avma;
    1015             :   do
    1016             :   {
    1017        5172 :     avma = av;
    1018        5172 :     Q = grp->rand(E);
    1019        5172 :     d = pairorder(E, grp->pow(E, P, dm), grp->pow(E, Q, dm), m, F);
    1020        5172 :   } while (!equalii(d, d2));
    1021        2646 :   return gerepilecopy(ltop, mkvec2(P,Q));
    1022             : }

Generated by: LCOV version 1.11