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.0 lcov report (development 23339-b1c33c51a) Lines: 534 577 92.5 %
Date: 2018-12-11 05:41:34 Functions: 35 36 97.2 %
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     3900991 : int_block(GEN n, long i, long l)
      32             : {
      33     3900991 :   long q = divsBIL(i), r = remsBIL(i)+1, lr;
      34     3901160 :   GEN nw = int_W(n, q);
      35     3901160 :   ulong w = (ulong) *nw, w2;
      36     3901160 :   if (r>=l) return (w>>(r-l))&((1UL<<l)-1);
      37      292009 :   w &= (1UL<<r)-1; lr = l-r;
      38      292009 :   w2 = (ulong) *int_precW(nw); w2 >>= (BITS_IN_LONG-lr);
      39      292009 :   return (w<<lr)|w2;
      40             : }
      41             : 
      42             : /* assume n != 0, t_INT. Compute x^|n| using sliding window powering */
      43             : static GEN
      44     6925257 : 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     6925257 :   long i, l = expu(n), u = (1UL<<(e-1));
      49             :   long w, v;
      50     6924678 :   GEN tab = cgetg(1+u, t_VEC);
      51     6928547 :   GEN x2 = sqr(E, x), z = NULL, tw;
      52     6407352 :   gel(tab, 1) = x;
      53     6407352 :   for (i=2; i<=u; i++) gel(tab,i) = mul(E, gel(tab,i-1), x2);
      54     6398750 :   av = avma;
      55    60964966 :   while (l>=0)
      56             :   {
      57    47646520 :     if (e > l+1) e = l+1;
      58    47646520 :     w = (n>>(l+1-e)) & ((1UL<<e)-1); v = vals(w); l-=e;
      59    47855017 :     tw = gel(tab, 1+(w>>(v+1)));
      60    47855017 :     if (z)
      61             :     {
      62    40932129 :       for (i=1; i<=e-v; i++) z = sqr(E, z);
      63    40751110 :       z = mul(E, z, tw);
      64     6922888 :     } else z = tw;
      65    47663046 :     for (i=1; i<=v; i++) z = sqr(E, z);
      66   135619097 :     while (l>=0)
      67             :     {
      68    80618429 :       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    81193305 :       if (n&(1UL<<l)) break;
      74    40392983 :       z = sqr(E, z); l--;
      75             :     }
      76             :   }
      77     6919696 :   return z;
      78             : }
      79             : 
      80             : 
      81             : /* assume n != 0, t_INT. Compute x^|n| using sliding window powering */
      82             : static GEN
      83       82216 : 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       82216 :   long i, l = expi(n), u = (1UL<<(e-1));
      88             :   long w, v;
      89       82219 :   GEN tab = cgetg(1+u, t_VEC);
      90       82221 :   GEN x2 = sqr(E, x), z = NULL, tw;
      91       78176 :   gel(tab, 1) = x;
      92       78176 :   for (i=2; i<=u; i++) gel(tab,i) = mul(E, gel(tab,i-1), x2);
      93       78165 :   av = avma;
      94     3348616 :   while (l>=0)
      95             :   {
      96     3188285 :     if (e > l+1) e = l+1;
      97     3188285 :     w = int_block(n,l,e); v = vals(w); l-=e;
      98     3194475 :     tw = gel(tab, 1+(w>>(v+1)));
      99     3194475 :     if (z)
     100             :     {
     101     3112253 :       for (i=1; i<=e-v; i++) z = sqr(E, z);
     102     3105815 :       z = mul(E, z, tw);
     103       82222 :     } else z = tw;
     104     3187873 :     for (i=1; i<=v; i++) z = sqr(E, z);
     105    13425058 :     while (l>=0)
     106             :     {
     107    10150877 :       if (gc_needed(av,1))
     108             :       {
     109         444 :         if (DEBUGMEM>1) pari_warn(warnmem,"sliding_window_pow (%ld)", l);
     110         444 :         z = gerepilecopy(av, z);
     111             :       }
     112    10150877 :       if (int_bit(n,l)) break;
     113     7045783 :       z = sqr(E, z); l--;
     114             :     }
     115             :   }
     116       82166 :   return z;
     117             : }
     118             : 
     119             : /* assume n != 0, t_INT. Compute x^|n| using leftright binary powering */
     120             : static GEN
     121    54455281 : leftright_binary_powu(GEN x, ulong n, void *E, GEN (*sqr)(void*,GEN),
     122             :                                               GEN (*mul)(void*,GEN,GEN))
     123             : {
     124    54455281 :   pari_sp av = avma;
     125             :   GEN  y;
     126             :   int j;
     127             : 
     128    54455281 :   if (n == 1) return x;
     129    54455281 :   y = x; j = 1+bfffo(n);
     130             :   /* normalize, i.e set highest bit to 1 (we know n != 0) */
     131    54455281 :   n<<=j; j = BITS_IN_LONG-j;
     132             :   /* first bit is now implicit */
     133   150477162 :   for (; j; n<<=1,j--)
     134             :   {
     135    96026518 :     y = sqr(E,y);
     136    96021995 :     if (n & HIGHBIT) y = mul(E,y,x); /* first bit set: multiply by base */
     137    96021881 :     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    54450644 :   return y;
     144             : }
     145             : 
     146             : GEN
     147    61485573 : gen_powu_i(GEN x, ulong n, void *E, GEN (*sqr)(void*,GEN),
     148             :                                     GEN (*mul)(void*,GEN,GEN))
     149             : {
     150             :   long l;
     151    61485573 :   if (n == 1) return x;
     152    61376048 :   l = expu(n);
     153    61378543 :   if (l<=8)
     154    54451208 :     return leftright_binary_powu(x, n, E, sqr, mul);
     155             :   else
     156     6927335 :     return sliding_window_powu(x, n, l<=24? 2: 3, E, sqr, mul);
     157             : }
     158             : 
     159             : GEN
     160     1342340 : gen_powu(GEN x, ulong n, void *E, GEN (*sqr)(void*,GEN),
     161             :                                   GEN (*mul)(void*,GEN,GEN))
     162             : {
     163     1342340 :   pari_sp av = avma;
     164     1342340 :   if (n == 1) return gcopy(x);
     165     1209182 :   return gerepilecopy(av, gen_powu_i(x,n,E,sqr,mul));
     166             : }
     167             : 
     168             : GEN
     169    22649464 : 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    22649464 :   if (lgefint(n)==3) return gen_powu_i(x, uel(n,2), E, sqr, mul);
     174       82219 :   l = expi(n);
     175       82216 :   if      (l<=64)  e = 3;
     176       60284 :   else if (l<=160) e = 4;
     177       26546 :   else if (l<=384) e = 5;
     178       18545 :   else if (l<=896) e = 6;
     179        9844 :   else             e = 7;
     180       82216 :   return sliding_window_pow(x, n, e, E, sqr, mul);
     181             : }
     182             : 
     183             : GEN
     184     1085401 : gen_pow(GEN x, GEN n, void *E, GEN (*sqr)(void*,GEN),
     185             :                                GEN (*mul)(void*,GEN,GEN))
     186             : {
     187     1085401 :   pari_sp av = avma;
     188     1085401 :   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      301571 : gen_powu_fold_i(GEN x, ulong n, void *E, GEN  (*sqr)(void*,GEN),
     194             :                                          GEN (*msqr)(void*,GEN))
     195             : {
     196      301571 :   pari_sp av = avma;
     197             :   GEN y;
     198             :   int j;
     199             : 
     200      301571 :   if (n == 1) return x;
     201      301571 :   y = x; j = 1+bfffo(n);
     202             :   /* normalize, i.e set highest bit to 1 (we know n != 0) */
     203      301571 :   n<<=j; j = BITS_IN_LONG-j;
     204             :   /* first bit is now implicit */
     205     2832129 :   for (; j; n<<=1,j--)
     206             :   {
     207     2530558 :     if (n & HIGHBIT) y = msqr(E,y); /* first bit set: multiply by base */
     208     1937214 :     else y = sqr(E,y);
     209     2530558 :     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      301571 :   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      202262 : gen_pow_fold_i(GEN x, GEN N, void *E, GEN (*sqr)(void*,GEN),
     229             :                                       GEN (*msqr)(void*,GEN))
     230             : {
     231      202262 :   long ln = lgefint(N);
     232      202262 :   if (ln == 3) return gen_powu_fold_i(x, N[2], E, sqr, msqr);
     233             :   else
     234             :   {
     235       88967 :     GEN nd = int_MSW(N), y = x;
     236       88967 :     ulong n = *nd;
     237             :     long i;
     238             :     int j;
     239       88967 :     pari_sp av = avma;
     240             : 
     241       88967 :     if (n == 1)
     242        6550 :       j = 0;
     243             :     else
     244             :     {
     245       82417 :       j = 1+bfffo(n); /* < BIL */
     246             :       /* normalize, i.e set highest bit to 1 (we know n != 0) */
     247       82417 :       n <<= j; j = BITS_IN_LONG - j;
     248             :     }
     249             :     /* first bit is now implicit */
     250       88967 :     for (i=ln-2;;)
     251             :     {
     252    26349476 :       for (; j; n<<=1,j--)
     253             :       {
     254    25416682 :         if (n & HIGHBIT) y = msqr(E,y); /* first bit set: multiply by base */
     255    15649058 :         else y = sqr(E,y);
     256    25416485 :         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      510782 :       if (--i == 0) return y;
     263      422012 :       nd = int_precW(nd);
     264      422012 :       n = *nd; j = BITS_IN_LONG;
     265             :     }
     266             :   }
     267             : }
     268             : GEN
     269      113296 : gen_pow_fold(GEN x, GEN n, void *E, GEN (*sqr)(void*,GEN),
     270             :                                     GEN (*msqr)(void*,GEN))
     271             : {
     272      113296 :   pari_sp av = avma;
     273      113296 :   return gerepilecopy(av, gen_pow_fold_i(x,n,E,sqr,msqr));
     274             : }
     275             : 
     276             : GEN
     277         126 : gen_pow_init(GEN x, GEN n, long k, void *E, GEN (*sqr)(void*,GEN), GEN (*mul)(void*,GEN,GEN))
     278             : {
     279         126 :   long i, j, l = expi(n);
     280         126 :   long m = 1UL<<(k-1);
     281         126 :   GEN x2 = sqr(E, x), y = gcopy(x);
     282         126 :   GEN R = cgetg(m+1, t_VEC);
     283         609 :   for(i = 1; i <= m; i++)
     284             :   {
     285         483 :     GEN C = cgetg(l+1, t_VEC);
     286         483 :     gel(C,1) = y;
     287       27622 :     for(j = 2; j <= l; j++)
     288       27139 :       gel(C,j) = sqr(E, gel(C,j-1));
     289         483 :     gel(R,i) = C;
     290         483 :     y = mul(E, y, x2);
     291             :   }
     292         126 :   return R;
     293             : }
     294             : 
     295             : GEN
     296       64734 : gen_pow_table(GEN R, GEN n, void *E, GEN (*one)(void*), GEN (*mul)(void*,GEN,GEN))
     297             : {
     298       64734 :   long e = expu(lg(R)-1) + 1;
     299       64734 :   long l = expi(n);
     300             :   long i, w;
     301       64734 :   GEN z = one(E), tw;
     302     1531540 :   for(i=0; i<=l; )
     303             :   {
     304     1402072 :     if (int_bit(n, i)==0) { i++; continue; }
     305      712708 :     if (i+e-1>l) e = l+1-i;
     306      712708 :     w = int_block(n,i+e-1,e);
     307      712708 :     tw = gmael(R, 1+(w>>1), i+1);
     308      712708 :     z = mul(E, z, tw);
     309      712708 :     i += e;
     310             :   }
     311       64734 :   return z;
     312             : }
     313             : 
     314             : GEN
     315     7127174 : gen_powers(GEN x, long l, int use_sqr, void *E, GEN (*sqr)(void*,GEN),
     316             :                                       GEN (*mul)(void*,GEN,GEN), GEN (*one)(void*))
     317             : {
     318             :   long i;
     319     7127174 :   GEN V = cgetg(l+2,t_VEC);
     320     7127422 :   gel(V,1) = one(E); if (l==0) return V;
     321     7114231 :   gel(V,2) = gcopy(x); if (l==1) return V;
     322     4424825 :   gel(V,3) = sqr(E,x);
     323     4424642 :   if (use_sqr)
     324    12278041 :     for(i = 4; i < l+2; i++)
     325    21382812 :       gel(V,i) = (i&1)? sqr(E,gel(V, (i+1)>>1))
     326    12631473 :                       : mul(E,gel(V, i-1),x);
     327             :   else
     328     2525410 :     for(i = 4; i < l+2; i++)
     329     1627468 :       gel(V,i) = mul(E,gel(V,i-1),x);
     330     4424604 :   return V;
     331             : }
     332             : 
     333             : GEN
     334    50529779 : producttree_scheme(long n)
     335             : {
     336             :   GEN v, w;
     337             :   long i, j, k, u, l;
     338    50529779 :   if (n<=2) return mkvecsmall(n);
     339    43034623 :   u = expu(n-1);
     340    43034566 :   v = cgetg(n+1,t_VECSMALL);
     341    43034604 :   w = cgetg(n+1,t_VECSMALL);
     342    43034810 :   v[1] = n; l = 1;
     343   143770645 :   for (i=1; i<=u; i++)
     344             :   {
     345   359978259 :     for(j=1, k=1; j<=l; j++, k+=2)
     346             :     {
     347   259242424 :       long vj = v[j], v2 = vj>>1;
     348   259242424 :       w[k]    = vj-v2;
     349   259242424 :       w[k+1]  = v2;
     350             :     }
     351   100735835 :     swap(v,w); l<<=1;
     352             :   }
     353    43034810 :   fixlg(v, l+1); set_avma((pari_sp)v); return v;
     354             : }
     355             : 
     356             : GEN
     357    52200827 : gen_product(GEN x, void *data, GEN (*mul)(void *,GEN,GEN))
     358             : {
     359             :   pari_sp ltop;
     360    52200827 :   long i,k,lx = lg(x),lv;
     361             :   pari_timer ti;
     362             :   GEN v;
     363    52200827 :   if (DEBUGLEVEL>7) timer_start(&ti);
     364             : 
     365    52200858 :   if (lx == 1) return gen_1;
     366    52196146 :   if (lx == 2) return gcopy(gel(x,1));
     367    50474422 :   x = leafcopy(x); k = lx;
     368    50474725 :   v = producttree_scheme(lx-1); lv = lg(v);
     369    50475465 :   ltop = avma;
     370   359651168 :   for (k=1, i=1; k<lv; i+=v[k++])
     371   309176794 :     gel(x,k) = v[k]==1 ? gel(x,i): mul(data,gel(x,i),gel(x,i+1));
     372   201536388 :   while (k > 2)
     373             :   {
     374   100587393 :     if (DEBUGLEVEL>7)
     375           0 :       timer_printf(&ti,"gen_product: remaining objects %ld",k-1);
     376   100586797 :     lx = k; k = 1;
     377   359277527 :     for (i=1; i<lx-1; i+=2)
     378   258689579 :       gel(x,k++) = mul(data,gel(x,i),gel(x,i+1));
     379   100587948 :     if (i < lx) gel(x,k++) = gel(x,i);
     380   100587948 :     if (gc_needed(ltop,1))
     381           6 :       gerepilecoeffs(ltop,x+1,k-1);
     382             :   }
     383    50474621 :   return gel(x,1);
     384             : }
     385             : 
     386             : /***********************************************************************/
     387             : /**                                                                   **/
     388             : /**                    DISCRETE LOGARITHM                             **/
     389             : /**                                                                   **/
     390             : /***********************************************************************/
     391             : 
     392             : static GEN
     393    56872257 : iter_rho(GEN x, GEN g, GEN q, GEN A, ulong h, void *E, const struct bb_group *grp)
     394             : {
     395    56872257 :   GEN a = gel(A,1);
     396    56872257 :   switch((h|grp->hash(a))%3UL)
     397             :   {
     398             :     case 0:
     399    18960500 :       return mkvec3(grp->pow(E,a,gen_2),Fp_mulu(gel(A,2),2,q),
     400    18960500 :                                         Fp_mulu(gel(A,3),2,q));
     401             :     case 1:
     402    18953124 :       return mkvec3(grp->mul(E,a,x),addis(gel(A,2),1),gel(A,3));
     403             :     case 2:
     404    18958633 :       return mkvec3(grp->mul(E,a,g),gel(A,2),addiu(gel(A,3),1));
     405             :   }
     406           0 :   return NULL;
     407             : }
     408             : 
     409             : /*Generic Pollard rho discrete log algorithm*/
     410             : static GEN
     411          49 : gen_Pollard_log(GEN x, GEN g, GEN q, void *E, const struct bb_group *grp)
     412             : {
     413          49 :   pari_sp av=avma;
     414          49 :   GEN A, B, l, sqrt4q = sqrti(shifti(q,4));
     415          49 :   ulong i, h = 0, imax = itou_or_0(sqrt4q);
     416          49 :   if (!imax) imax = ULONG_MAX;
     417             :   do {
     418             :  rho_restart:
     419          49 :     A = B = mkvec3(x,gen_1,gen_0);
     420          49 :     i=0;
     421             :     do {
     422    18957419 :       if (i>imax)
     423             :       {
     424           0 :         h++;
     425           0 :         if (DEBUGLEVEL)
     426           0 :           pari_warn(warner,"changing Pollard rho hash seed to %ld",h);
     427           0 :         goto rho_restart;
     428             :       }
     429    18957419 :       A = iter_rho(x, g, q, A, h, E, grp);
     430    18957419 :       B = iter_rho(x, g, q, B, h, E, grp);
     431    18957419 :       B = iter_rho(x, g, q, B, h, E, grp);
     432    18957419 :       if (gc_needed(av,2))
     433             :       {
     434        1646 :         if(DEBUGMEM>1) pari_warn(warnmem,"gen_Pollard_log");
     435        1646 :         gerepileall(av, 2, &A, &B);
     436             :       }
     437    18957419 :       i++;
     438    18957419 :     } while (!grp->equal(gel(A,1), gel(B,1)));
     439          49 :     gel(A,2) = modii(gel(A,2), q);
     440          49 :     gel(B,2) = modii(gel(B,2), q);
     441          49 :     h++;
     442          49 :   } while (equalii(gel(A,2), gel(B,2)));
     443          49 :   l = Fp_div(Fp_sub(gel(B,3), gel(A,3),q),Fp_sub(gel(A,2), gel(B,2), q), q);
     444          49 :   return gerepileuptoint(av, l);
     445             : }
     446             : 
     447             : /* compute a hash of g^(i-1), 1<=i<=n. Return [sorted hash, perm, g^-n] */
     448             : GEN
     449     2679171 : gen_Shanks_init(GEN g, long n, void *E, const struct bb_group *grp)
     450             : {
     451     2679171 :   GEN p1 = g, G, perm, table = cgetg(n+1,t_VECSMALL);
     452     2679171 :   pari_sp av=avma;
     453             :   long i;
     454     2679171 :   table[1] = grp->hash(grp->pow(E,g,gen_0));
     455    13416837 :   for (i=2; i<=n; i++)
     456             :   {
     457    10737666 :     table[i] = grp->hash(p1);
     458    10737666 :     p1 = grp->mul(E,p1,g);
     459    10737666 :     if (gc_needed(av,2))
     460             :     {
     461           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_log, baby = %ld", i);
     462           0 :       p1 = gerepileupto(av, p1);
     463             :     }
     464             :   }
     465     2679171 :   G = gerepileupto(av, grp->pow(E,p1,gen_m1)); /* g^-n */
     466     2679171 :   perm = vecsmall_indexsort(table);
     467     2679171 :   table = vecsmallpermute(table,perm);
     468     2679171 :   return mkvec4(table,perm,g,G);
     469             : }
     470             : /* T from gen_Shanks_init(g,n). Return v < n*N such that x = g^v or NULL */
     471             : GEN
     472     2679619 : gen_Shanks(GEN T, GEN x, ulong N, void *E, const struct bb_group *grp)
     473             : {
     474     2679619 :   pari_sp av=avma;
     475     2679619 :   GEN table = gel(T,1), perm = gel(T,2), g = gel(T,3), G = gel(T,4);
     476     2679619 :   GEN p1 = x;
     477     2679619 :   long n = lg(table)-1;
     478             :   ulong k;
     479    14967656 :   for (k=0; k<N; k++)
     480             :   { /* p1 = x G^k, G = g^-n */
     481    14673411 :     long h = grp->hash(p1), i = zv_search(table, h);
     482    14673411 :     if (i)
     483             :     {
     484     2386119 :       do i--; while (i && table[i] == h);
     485     2385374 :       for (i++; i <= n && table[i] == h; i++)
     486             :       {
     487     2385374 :         GEN v = addiu(muluu(n,k), perm[i]-1);
     488     2385374 :         if (grp->equal(grp->pow(E,g,v),x)) return gerepileuptoint(av,v);
     489           0 :         if (DEBUGLEVEL)
     490           0 :           err_printf("gen_Shanks_log: false positive %lu, %lu\n", k,h);
     491             :       }
     492             :     }
     493    12288037 :     p1 = grp->mul(E,p1,G);
     494    12288037 :     if (gc_needed(av,2))
     495             :     {
     496           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_log, k = %lu", k);
     497           0 :       p1 = gerepileupto(av, p1);
     498             :     }
     499             :   }
     500      294245 :   return NULL;
     501             : }
     502             : /* Generic Shanks baby-step/giant-step algorithm. Return log_g(x), ord g = q.
     503             :  * One-shot: use gen_Shanks_init/log if many logs are desired; early abort
     504             :  * if log < sqrt(q) */
     505             : static GEN
     506      379275 : gen_Shanks_log(GEN x, GEN g, GEN q, void *E, const struct bb_group *grp)
     507             : {
     508      379275 :   pari_sp av=avma, av1;
     509             :   long lbaby, i, k;
     510             :   GEN p1, table, giant, perm, ginv;
     511      379275 :   p1 = sqrti(q);
     512      379275 :   if (abscmpiu(p1,LGBITS) >= 0)
     513           0 :     pari_err_OVERFLOW("gen_Shanks_log [order too large]");
     514      379275 :   lbaby = itos(p1)+1; table = cgetg(lbaby+1,t_VECSMALL);
     515      379275 :   ginv = grp->pow(E,g,gen_m1);
     516      379275 :   av1 = avma;
     517     1703798 :   for (p1=x, i=1;;i++)
     518             :   {
     519     3028321 :     if (grp->equal1(p1)) { set_avma(av); return stoi(i-1); }
     520     1654002 :     table[i] = grp->hash(p1); if (i==lbaby) break;
     521     1324523 :     p1 = grp->mul(E,p1,ginv);
     522     1324523 :     if (gc_needed(av1,2))
     523             :     {
     524           7 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_log, baby = %ld", i);
     525           7 :       p1 = gerepileupto(av1, p1);
     526             :     }
     527             :   }
     528      329479 :   p1 = giant = gerepileupto(av1, grp->mul(E,x,grp->pow(E, p1, gen_m1)));
     529      329479 :   perm = vecsmall_indexsort(table);
     530      329479 :   table = vecsmallpermute(table,perm);
     531      329479 :   av1 = avma;
     532      573972 :   for (k=1; k<= lbaby; k++)
     533             :   {
     534      573963 :     long h = grp->hash(p1), i = zv_search(table, h);
     535      573963 :     if (i)
     536             :     {
     537      329471 :       while (table[i] == h && i) i--;
     538      329472 :       for (i++; i <= lbaby && table[i] == h; i++)
     539             :       {
     540      329471 :         GEN v = addiu(mulss(lbaby-1,k),perm[i]-1);
     541      329471 :         if (grp->equal(grp->pow(E,g,v),x)) return gerepileuptoint(av,v);
     542           1 :         if (DEBUGLEVEL)
     543           0 :           err_printf("gen_Shanks_log: false positive %ld, %lu\n", k,h);
     544             :       }
     545             :     }
     546      244493 :     p1 = grp->mul(E,p1,giant);
     547      244493 :     if (gc_needed(av1,2))
     548             :     {
     549           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_log, k = %ld", k);
     550           0 :       p1 = gerepileupto(av1, p1);
     551             :     }
     552             :   }
     553           9 :   set_avma(av); return cgetg(1, t_VEC); /* no solution */
     554             : }
     555             : 
     556             : /*Generic discrete logarithme in a group of prime order p*/
     557             : GEN
     558     1565017 : gen_plog(GEN x, GEN g, GEN p, void *E, const struct bb_group *grp)
     559             : {
     560     1565017 :   if (grp->easylog)
     561             :   {
     562     1541066 :     GEN e = grp->easylog(E, x, g, p);
     563     1541066 :     if (e) return e;
     564             :   }
     565      586607 :   if (grp->equal1(x)) return gen_0;
     566      586565 :   if (grp->equal(x,g)) return gen_1;
     567      379324 :   if (expi(p)<32) return gen_Shanks_log(x,g,p,E,grp);
     568          49 :   return gen_Pollard_log(x, g, p, E, grp);
     569             : }
     570             : 
     571             : GEN
     572     7961675 : get_arith_ZZM(GEN o)
     573             : {
     574     7961675 :   if (!o) return NULL;
     575     7961675 :   switch(typ(o))
     576             :   {
     577             :     case t_INT:
     578     4905017 :       if (signe(o) > 0) return mkvec2(o, Z_factor(o));
     579           7 :       break;
     580             :     case t_MAT:
     581     1379851 :       if (is_Z_factorpos(o)) return mkvec2(factorback(o), o);
     582          14 :       break;
     583             :     case t_VEC:
     584     1676800 :       if (lg(o) == 3 && signe(gel(o,1)) > 0 && is_Z_factorpos(gel(o,2))) return o;
     585           0 :       break;
     586             :   }
     587          28 :   pari_err_TYPE("generic discrete logarithm (order factorization)",o);
     588             :   return NULL; /* LCOV_EXCL_LINE */
     589             : }
     590             : GEN
     591      399738 : get_arith_Z(GEN o)
     592             : {
     593      399738 :   if (!o) return NULL;
     594      399738 :   switch(typ(o))
     595             :   {
     596             :     case t_INT:
     597      323923 :       if (signe(o) > 0) return o;
     598           7 :       break;
     599             :     case t_MAT:
     600          14 :       o = factorback(o);
     601           0 :       if (typ(o) == t_INT && signe(o) > 0) return o;
     602           0 :       break;
     603             :     case t_VEC:
     604       75794 :       if (lg(o) != 3) break;
     605       75794 :       o = gel(o,1);
     606       75794 :       if (typ(o) == t_INT && signe(o) > 0) return o;
     607           0 :       break;
     608             :   }
     609          14 :   pari_err_TYPE("generic discrete logarithm (order factorization)",o);
     610             :   return NULL; /* LCOV_EXCL_LINE */
     611             : }
     612             : 
     613             : /* Generic Pohlig-Hellman discrete logarithm: smallest integer n >= 0 such that
     614             :  * g^n=a. Assume ord(g) | ord; grp->easylog() is an optional trapdoor
     615             :  * function that catches easy logarithms */
     616             : GEN
     617     1098827 : gen_PH_log(GEN a, GEN g, GEN ord, void *E, const struct bb_group *grp)
     618             : {
     619     1098827 :   pari_sp av = avma;
     620             :   GEN v, ginv, fa, ex;
     621             :   long i, j, l;
     622             : 
     623     1098827 :   if (grp->equal(g, a)) /* frequent special case */
     624      174184 :     return grp->equal1(g)? gen_0: gen_1;
     625      924643 :   if (grp->easylog)
     626             :   {
     627      924531 :     GEN e = grp->easylog(E, a, g, ord);
     628      924503 :     if (e) return e;
     629             :   }
     630      481626 :   v = get_arith_ZZM(ord);
     631      481626 :   ord= gel(v,1);
     632      481626 :   fa = gel(v,2);
     633      481626 :   ex = gel(fa,2);
     634      481626 :   fa = gel(fa,1); l = lg(fa);
     635      481626 :   ginv = grp->pow(E,g,gen_m1);
     636      481626 :   v = cgetg(l, t_VEC);
     637     1493717 :   for (i = 1; i < l; i++)
     638             :   {
     639     1012390 :     GEN q = gel(fa,i), qj, gq, nq, ginv0, a0, t0;
     640     1012390 :     long e = itos(gel(ex,i));
     641     1012390 :     if (DEBUGLEVEL>5)
     642           0 :       err_printf("Pohlig-Hellman: DL mod %Ps^%ld\n",q,e);
     643     1012390 :     qj = new_chunk(e+1);
     644     1012390 :     gel(qj,0) = gen_1;
     645     1012390 :     gel(qj,1) = q;
     646     1012390 :     for (j = 2; j <= e; j++) gel(qj,j) = mulii(gel(qj,j-1), q);
     647     1012390 :     t0 = diviiexact(ord, gel(qj,e));
     648     1012390 :     a0 = grp->pow(E, a, t0);
     649     1012390 :     ginv0 = grp->pow(E, ginv, t0); /* ord(ginv0) | q^e */
     650     1012390 :     if (grp->equal1(ginv0)) { gel(v,i) = mkintmod(gen_0, gen_1); continue; }
     651     1012383 :     do gq = grp->pow(E,g, mulii(t0, gel(qj,--e))); while (grp->equal1(gq));
     652             :     /* ord(gq) = q */
     653     1012376 :     nq = gen_0;
     654     1384224 :     for (j = 0;; j++)
     655      371848 :     { /* nq = sum_{i<j} b_i q^i */
     656     1384224 :       GEN b = grp->pow(E,a0, gel(qj,e-j));
     657             :       /* cheap early abort: wrong local order */
     658     1384224 :       if (j == 0 && !grp->equal1(grp->pow(E,b,q))) {
     659         290 :         set_avma(av); return cgetg(1, t_VEC);
     660             :       }
     661     1383934 :       b = gen_plog(b, gq, q, E, grp);
     662     1383934 :       if (typ(b) != t_INT) { set_avma(av); return cgetg(1, t_VEC); }
     663     1383925 :       nq = addii(nq, mulii(b, gel(qj,j)));
     664     1383925 :       if (j == e) break;
     665             : 
     666      371848 :       a0 = grp->mul(E,a0, grp->pow(E,ginv0, b));
     667      371848 :       ginv0 = grp->pow(E,ginv0, q);
     668             :     }
     669     1012077 :     gel(v,i) = mkintmod(nq, gel(qj,e+1));
     670             :   }
     671      481327 :   return gerepileuptoint(av, lift(chinese1_coprime_Z(v)));
     672             : }
     673             : 
     674             : /***********************************************************************/
     675             : /**                                                                   **/
     676             : /**                    ORDER OF AN ELEMENT                            **/
     677             : /**                                                                   **/
     678             : /***********************************************************************/
     679             : /*Find the exact order of a assuming a^o==1*/
     680             : GEN
     681     3241568 : gen_order(GEN a, GEN o, void *E, const struct bb_group *grp)
     682             : {
     683     3241568 :   pari_sp av = avma;
     684             :   long i, l;
     685             :   GEN m;
     686             : 
     687     3241568 :   m = get_arith_ZZM(o);
     688     3241574 :   if (!m) pari_err_TYPE("gen_order [missing order]",a);
     689     3241574 :   o = gel(m,1);
     690     3241574 :   m = gel(m,2); l = lgcols(m);
     691    10109158 :   for (i = l-1; i; i--)
     692             :   {
     693     6867592 :     GEN t, y, p = gcoeff(m,i,1);
     694     6867592 :     long j, e = itos(gcoeff(m,i,2));
     695     6867614 :     if (l == 2) {
     696      679360 :       t = gen_1;
     697      679360 :       y = a;
     698             :     } else {
     699     6188254 :       t = diviiexact(o, powiu(p,e));
     700     6188203 :       y = grp->pow(E, a, t);
     701             :     }
     702     6867574 :     if (grp->equal1(y)) o = t;
     703             :     else {
     704     6370650 :       for (j = 1; j < e; j++)
     705             :       {
     706     2173218 :         y = grp->pow(E, y, p);
     707     2173222 :         if (grp->equal1(y)) break;
     708             :       }
     709     4719971 :       if (j < e) {
     710      522539 :         if (j > 1) p = powiu(p, j);
     711      522539 :         o = mulii(t, p);
     712             :       }
     713             :     }
     714             :   }
     715     3241566 :   return gerepilecopy(av, o);
     716             : }
     717             : 
     718             : /*Find the exact order of a assuming a^o==1, return [order,factor(order)] */
     719             : GEN
     720     2777051 : gen_factored_order(GEN a, GEN o, void *E, const struct bb_group *grp)
     721             : {
     722     2777051 :   pari_sp av = avma;
     723             :   long i, l, ind;
     724             :   GEN m, F, P;
     725             : 
     726     2777051 :   m = get_arith_ZZM(o);
     727     2777051 :   if (!m) pari_err_TYPE("gen_factored_order [missing order]",a);
     728     2777051 :   o = gel(m,1);
     729     2777051 :   m = gel(m,2); l = lgcols(m);
     730     2777051 :   P = cgetg(l, t_COL); ind = 1;
     731     2777051 :   F = cgetg(l, t_COL);
     732     6673150 :   for (i = l-1; i; i--)
     733             :   {
     734     3896099 :     GEN t, y, p = gcoeff(m,i,1);
     735     3896099 :     long j, e = itos(gcoeff(m,i,2));
     736     3896099 :     if (l == 2) {
     737     1702992 :       t = gen_1;
     738     1702992 :       y = a;
     739             :     } else {
     740     2193107 :       t = diviiexact(o, powiu(p,e));
     741     2193107 :       y = grp->pow(E, a, t);
     742             :     }
     743     3896099 :     if (grp->equal1(y)) o = t;
     744             :     else {
     745     4884401 :       for (j = 1; j < e; j++)
     746             :       {
     747     1037313 :         y = grp->pow(E, y, p);
     748     1037313 :         if (grp->equal1(y)) break;
     749             :       }
     750     3860155 :       gel(P,ind) = p;
     751     3860155 :       gel(F,ind) = utoipos(j);
     752     3860155 :       if (j < e) {
     753       13067 :         if (j > 1) p = powiu(p, j);
     754       13067 :         o = mulii(t, p);
     755             :       }
     756     3860155 :       ind++;
     757             :     }
     758             :   }
     759     2777051 :   setlg(P, ind); P = vecreverse(P);
     760     2777051 :   setlg(F, ind); F = vecreverse(F);
     761     2777051 :   return gerepilecopy(av, mkvec2(o, mkmat2(P,F)));
     762             : }
     763             : 
     764             : /* E has order o[1], ..., or o[#o], draw random points until all solutions
     765             :  * but one are eliminated */
     766             : GEN
     767         945 : gen_select_order(GEN o, void *E, const struct bb_group *grp)
     768             : {
     769         945 :   pari_sp ltop = avma, btop;
     770             :   GEN lastgood, so, vo;
     771         945 :   long lo = lg(o), nbo=lo-1;
     772         945 :   if (nbo == 1) return icopy(gel(o,1));
     773         413 :   so = ZV_indexsort(o); /* minimize max( o[i+1] - o[i] ) */
     774         413 :   vo = zero_zv(lo);
     775         413 :   lastgood = gel(o, so[nbo]);
     776         413 :   btop = avma;
     777             :   for(;;)
     778           0 :   {
     779         413 :     GEN lasto = gen_0;
     780         413 :     GEN P = grp->rand(E), t = mkvec(gen_0);
     781             :     long i;
     782         525 :     for (i = 1; i < lo; i++)
     783             :     {
     784         525 :       GEN newo = gel(o, so[i]);
     785         525 :       if (vo[i]) continue;
     786         525 :       t = grp->mul(E,t, grp->pow(E, P, subii(newo,lasto)));/*P^o[i]*/
     787         525 :       lasto = newo;
     788         525 :       if (!grp->equal1(t))
     789             :       {
     790         455 :         if (--nbo == 1) { set_avma(ltop); return icopy(lastgood); }
     791          42 :         vo[i] = 1;
     792             :       }
     793             :       else
     794          70 :         lastgood = lasto;
     795             :     }
     796           0 :     set_avma(btop);
     797             :   }
     798             : }
     799             : 
     800             : /*******************************************************************/
     801             : /*                                                                 */
     802             : /*                          n-th ROOT                              */
     803             : /*                                                                 */
     804             : /*******************************************************************/
     805             : /* Assume l is prime. Return a generator of the l-th Sylow and set *zeta to an element
     806             :  * of order l.
     807             :  *
     808             :  * q = l^e*r, e>=1, (r,l)=1
     809             :  * UNCLEAN */
     810             : static GEN
     811      268140 : gen_lgener(GEN l, long e, GEN r,GEN *zeta, void *E, const struct bb_group *grp)
     812             : {
     813      268140 :   const pari_sp av1 = avma;
     814             :   GEN m, m1;
     815             :   long i;
     816      211234 :   for (;; set_avma(av1))
     817             :   {
     818      690608 :     m1 = m = grp->pow(E, grp->rand(E), r);
     819      479375 :     if (grp->equal1(m)) continue;
     820      872889 :     for (i=1; i<e; i++)
     821             :     {
     822      604748 :       m = grp->pow(E,m,l);
     823      604748 :       if (grp->equal1(m)) break;
     824             :     }
     825      389411 :     if (i==e) break;
     826             :   }
     827      268141 :   *zeta = m; return m1;
     828             : }
     829             : 
     830             : /* Let G be a cyclic group of order o>1. Returns a (random) generator */
     831             : 
     832             : GEN
     833       15869 : gen_gener(GEN o, void *E, const struct bb_group *grp)
     834             : {
     835       15869 :   pari_sp ltop = avma, av;
     836             :   long i, lpr;
     837       15869 :   GEN F, N, pr, z=NULL;
     838       15869 :   F = get_arith_ZZM(o);
     839       15869 :   N = gel(F,1); pr = gel(F,2); lpr = lgcols(pr);
     840       15869 :   av = avma;
     841             : 
     842       51478 :   for (i = 1; i < lpr; i++)
     843             :   {
     844       35609 :     GEN l = gcoeff(pr,i,1);
     845       35609 :     long e = itos(gcoeff(pr,i,2));
     846       35609 :     GEN r = diviiexact(N,powis(l,e));
     847       35609 :     GEN zetan, zl = gen_lgener(l,e,r,&zetan,E,grp);
     848       35609 :     z = i==1 ? zl: grp->mul(E,z,zl);
     849       35609 :     if (gc_needed(av,2))
     850             :     { /* n can have lots of prime factors*/
     851           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_gener");
     852           0 :       z = gerepileupto(av, z);
     853             :     }
     854             :   }
     855       15869 :   return gerepileupto(ltop, z);
     856             : }
     857             : 
     858             : /* solve x^l = a , l prime in G of order q.
     859             :  *
     860             :  * q =  (l^e)*r, e >= 1, (r,l) = 1
     861             :  * y is not an l-th power, hence generates the l-Sylow of G
     862             :  * m = y^(q/l) != 1 */
     863             : static GEN
     864      233224 : gen_Shanks_sqrtl(GEN a, GEN l, long e, GEN r, GEN y, GEN m,void *E,
     865             :                  const struct bb_group *grp)
     866             : {
     867      233224 :   pari_sp av = avma;
     868             :   long k;
     869             :   GEN p1, u1, u2, v, w, z, dl;
     870             : 
     871      233224 :   (void)bezout(r,l,&u1,&u2);
     872      233224 :   v = grp->pow(E,a,u2);
     873      233224 :   w = grp->pow(E,v,l);
     874      233224 :   w = grp->mul(E,w,grp->pow(E,a,gen_m1));
     875      647531 :   while (!grp->equal1(w))
     876             :   {
     877      183953 :     k = 0;
     878      183953 :     p1 = w;
     879             :     do
     880             :     {
     881      317949 :       z = p1; p1 = grp->pow(E,p1,l);
     882      317949 :       k++;
     883      317949 :     } while(!grp->equal1(p1));
     884      183953 :     if (k==e) return gc_NULL(av);
     885      181083 :     dl = gen_plog(z,m,l,E,grp);
     886      181083 :     if (typ(dl) != t_INT) return gc_NULL(av);
     887      181083 :     dl = negi(dl);
     888      181083 :     p1 = grp->pow(E, grp->pow(E,y, dl), powiu(l,e-k-1));
     889      181083 :     m = grp->pow(E,m,dl);
     890      181083 :     e = k;
     891      181083 :     v = grp->mul(E,p1,v);
     892      181083 :     y = grp->pow(E,p1,l);
     893      181083 :     w = grp->mul(E,y,w);
     894      181083 :     if (gc_needed(av,1))
     895             :     {
     896           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_sqrtl");
     897           0 :       gerepileall(av,4, &y,&v,&w,&m);
     898             :     }
     899             :   }
     900      230353 :   return gerepilecopy(av, v);
     901             : }
     902             : /* Return one solution of x^n = a in a cyclic group of order q
     903             :  *
     904             :  * 1) If there is no solution, return NULL.
     905             :  *
     906             :  * 2) If there is a solution, there are exactly m of them [m = gcd(q-1,n)].
     907             :  * If zetan!=NULL, *zetan is set to a primitive m-th root of unity so that
     908             :  * the set of solutions is { x*zetan^k; k=0..m-1 }
     909             :  */
     910             : GEN
     911      241633 : gen_Shanks_sqrtn(GEN a, GEN n, GEN q, GEN *zetan, void *E, const struct bb_group *grp)
     912             : {
     913      241633 :   pari_sp ltop = avma;
     914             :   GEN m, u1, u2, z;
     915             :   int is_1;
     916             : 
     917      241633 :   if (is_pm1(n))
     918             :   {
     919           0 :     if (zetan) *zetan = grp->pow(E,a,gen_0);
     920           0 :     return signe(n) < 0? grp->pow(E,a,gen_m1): gcopy(a);
     921             :   }
     922      241633 :   is_1 = grp->equal1(a);
     923      241633 :   if (is_1 && !zetan) return gcopy(a);
     924             : 
     925      234254 :   m = bezout(n,q,&u1,&u2);
     926      234254 :   z = grp->pow(E,a,gen_0);
     927      234254 :   if (!is_pm1(m))
     928             :   {
     929      232392 :     GEN F = Z_factor(m);
     930             :     long i, j, e;
     931             :     GEN r, zeta, y, l;
     932      232392 :     pari_sp av1 = avma;
     933      462053 :     for (i = nbrows(F); i; i--)
     934             :     {
     935      232532 :       l = gcoeff(F,i,1);
     936      232532 :       j = itos(gcoeff(F,i,2));
     937      232531 :       e = Z_pvalrem(q,l,&r);
     938      232531 :       y = gen_lgener(l,e,r,&zeta,E,grp);
     939      232532 :       if (zetan) z = grp->mul(E,z, grp->pow(E,y,powiu(l,e-j)));
     940      232532 :       if (!is_1) {
     941             :         do
     942             :         {
     943      233224 :           a = gen_Shanks_sqrtl(a,l,e,r,y,zeta,E,grp);
     944      233223 :           if (!a) return gc_NULL(ltop);
     945      230353 :         } while (--j);
     946             :       }
     947      229661 :       if (gc_needed(ltop,1))
     948             :       { /* n can have lots of prime factors*/
     949           0 :         if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_sqrtn");
     950           0 :         gerepileall(av1, zetan? 2: 1, &a, &z);
     951             :       }
     952             :     }
     953             :   }
     954      231383 :   if (!equalii(m, n))
     955        1925 :     a = grp->pow(E,a,modii(u1,q));
     956      231384 :   if (zetan)
     957             :   {
     958         364 :     *zetan = z;
     959         364 :     gerepileall(ltop,2,&a,zetan);
     960             :   }
     961             :   else /* is_1 is 0: a was modified above -> gerepileupto valid */
     962      231020 :     a = gerepileupto(ltop, a);
     963      231383 :   return a;
     964             : }
     965             : 
     966             : /*******************************************************************/
     967             : /*                                                                 */
     968             : /*               structure of groups with pairing                  */
     969             : /*                                                                 */
     970             : /*******************************************************************/
     971             : 
     972             : static GEN
     973       40873 : ellgroup_d2(GEN N, GEN d)
     974             : {
     975       40873 :   GEN r = gcdii(N, d);
     976       40873 :   GEN F1 = gel(Z_factor(r), 1);
     977       40873 :   long i, j, l1 = lg(F1);
     978       40873 :   GEN F = cgetg(3, t_MAT);
     979       40873 :   gel(F,1) = cgetg(l1, t_COL);
     980       40873 :   gel(F,2) = cgetg(l1, t_COL);
     981       71729 :   for (i = 1, j = 1; i < l1; ++i)
     982             :   {
     983       30856 :     long v = Z_pval(N, gel(F1, i));
     984       30856 :     if (v<=1) continue;
     985       15876 :     gcoeff(F, j  , 1) = gel(F1, i);
     986       15876 :     gcoeff(F, j++, 2) = stoi(v);
     987             :   }
     988       40873 :   setlg(F[1],j); setlg(F[2],j);
     989       40873 :   return j==1 ? NULL : mkvec2(factorback(F), F);
     990             : }
     991             : 
     992             : GEN
     993       41034 : gen_ellgroup(GEN N, GEN d, GEN *pt_m, void *E, const struct bb_group *grp,
     994             :              GEN pairorder(void *E, GEN P, GEN Q, GEN m, GEN F))
     995             : {
     996       41034 :   pari_sp av = avma;
     997             :   GEN N0, N1, F;
     998       41034 :   if (pt_m) *pt_m = gen_1;
     999       41034 :   if (is_pm1(N)) return cgetg(1,t_VEC);
    1000       40873 :   F = ellgroup_d2(N, d);
    1001       40873 :   if (!F) {set_avma(av); return mkveccopy(N);}
    1002       15148 :   N0 = gel(F,1); N1 = diviiexact(N, N0);
    1003             :   while(1)
    1004       11745 :   {
    1005       26893 :     pari_sp av2 = avma;
    1006             :     GEN P, Q, d, s, t, m;
    1007             : 
    1008       26893 :     P = grp->pow(E,grp->rand(E), N1);
    1009       26893 :     s = gen_order(P, F, E, grp); if (equalii(s, N0)) {set_avma(av); return mkveccopy(N);}
    1010             : 
    1011       21056 :     Q = grp->pow(E,grp->rand(E), N1);
    1012       21056 :     t = gen_order(Q, F, E, grp); if (equalii(t, N0)) {set_avma(av); return mkveccopy(N);}
    1013             : 
    1014       18311 :     m = lcmii(s, t);
    1015       18311 :     d = pairorder(E, P, Q, m, F);
    1016             :     /* structure is [N/d, d] iff m d == N0. Note that N/d = N1 m */
    1017       18311 :     if (is_pm1(d) && equalii(m, N0)) {set_avma(av); return mkveccopy(N);}
    1018       18283 :     if (equalii(mulii(m, d), N0))
    1019             :     {
    1020        6538 :       GEN g = mkvec2(mulii(N1,m), d);
    1021        6538 :       if (pt_m) *pt_m = m;
    1022        6538 :       gerepileall(av,pt_m?2:1,&g,pt_m);
    1023        6538 :       return g;
    1024             :     }
    1025       11745 :     set_avma(av2);
    1026             :   }
    1027             : }
    1028             : 
    1029             : GEN
    1030        2723 : gen_ellgens(GEN D1, GEN d2, GEN m, void *E, const struct bb_group *grp,
    1031             :              GEN pairorder(void *E, GEN P, GEN Q, GEN m, GEN F))
    1032             : {
    1033        2723 :   pari_sp ltop = avma, av;
    1034             :   GEN F, d1, dm;
    1035             :   GEN P, Q, d, s;
    1036        2723 :   F = get_arith_ZZM(D1);
    1037        2723 :   d1 = gel(F, 1), dm =  diviiexact(d1,m);
    1038        2723 :   av = avma;
    1039             :   do
    1040             :   {
    1041        6735 :     set_avma(av);
    1042        6735 :     P = grp->rand(E);
    1043        6735 :     s = gen_order(P, F, E, grp);
    1044        6735 :   } while (!equalii(s, d1));
    1045        2723 :   av = avma;
    1046             :   do
    1047             :   {
    1048        5086 :     set_avma(av);
    1049        5086 :     Q = grp->rand(E);
    1050        5086 :     d = pairorder(E, grp->pow(E, P, dm), grp->pow(E, Q, dm), m, F);
    1051        5086 :   } while (!equalii(d, d2));
    1052        2723 :   return gerepilecopy(ltop, mkvec2(P,Q));
    1053             : }

Generated by: LCOV version 1.13