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.8.0 lcov report (development 19044-129ab8a) Lines: 502 544 92.3 %
Date: 2016-06-26 Functions: 32 33 97.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 339 428 79.2 %

           Branch data     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                 :     770272 : int_block(GEN n, long i, long l)
      32                 :            : {
      33                 :     770272 :   long q = divsBIL(i), r = remsBIL(i)+1, lr;
      34                 :     770399 :   GEN nw = int_W(n, q);
      35                 :     770399 :   ulong w = (ulong) *nw, w2;
      36         [ +  + ]:     770399 :   if (r>=l) return (w>>(r-l))&((1UL<<l)-1);
      37                 :      49975 :   w &= (1UL<<r)-1; lr = l-r;
      38                 :      49975 :   w2 = (ulong) *int_precW(nw); w2 >>= (BITS_IN_LONG-lr);
      39                 :     770399 :   return (w<<lr)|w2;
      40                 :            : }
      41                 :            : 
      42                 :            : /* assume n != 0, t_INT. Compute x^|n| using sliding window powering */
      43                 :            : static GEN
      44                 :    2826851 : 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                 :    2826851 :   long i, l = expu(n), u = (1UL<<(e-1));
      49                 :            :   long w, v;
      50                 :    2826870 :   GEN tab = cgetg(1+u, t_VEC);
      51                 :    2826893 :   GEN x2 = sqr(E, x), z = NULL, tw;
      52                 :    2793318 :   gel(tab, 1) = x;
      53         [ +  + ]:    7596885 :   for (i=2; i<=u; i++) gel(tab,i) = mul(E, gel(tab,i-1), x2);
      54                 :    2792883 :   av = avma;
      55         [ +  + ]:   21696483 :   while (l>=0)
      56                 :            :   {
      57         [ +  + ]:   18869852 :     if (e > l+1) e = l+1;
      58                 :   18869852 :     w = (n>>(l+1-e)) & ((1UL<<e)-1); v = vals(w); l-=e;
      59                 :   18896818 :     tw = gel(tab, 1+(w>>(v+1)));
      60         [ +  + ]:   18896818 :     if (z)
      61                 :            :     {
      62         [ +  + ]:   45313303 :       for (i=1; i<=e-v; i++) z = sqr(E, z);
      63                 :   16045979 :       z = mul(E, z, tw);
      64                 :    2826763 :     } else z = tw;
      65         [ +  + ]:   29860894 :     for (i=1; i<=v; i++) z = sqr(E, z);
      66         [ +  + ]:   34334502 :     while (l>=0)
      67                 :            :     {
      68         [ -  + ]:   31479676 :       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         [ +  + ]:   31516289 :       if (n&(1UL<<l)) break;
      74                 :   15467515 :       z = sqr(E, z); l--;
      75                 :            :     }
      76                 :            :   }
      77                 :    2826631 :   return z;
      78                 :            : }
      79                 :            : 
      80                 :            : 
      81                 :            : /* assume n != 0, t_INT. Compute x^|n| using sliding window powering */
      82                 :            : static GEN
      83                 :      57906 : 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                 :      57906 :   long i, l = expi(n), u = (1UL<<(e-1));
      88                 :            :   long w, v;
      89                 :      57906 :   GEN tab = cgetg(1+u, t_VEC);
      90                 :      57907 :   GEN x2 = sqr(E, x), z = NULL, tw;
      91                 :      57418 :   gel(tab, 1) = x;
      92         [ +  + ]:     455795 :   for (i=2; i<=u; i++) gel(tab,i) = mul(E, gel(tab,i-1), x2);
      93                 :      57415 :   av = avma;
      94         [ +  + ]:     828203 :   while (l>=0)
      95                 :            :   {
      96         [ +  + ]:     770344 :     if (e > l+1) e = l+1;
      97                 :     770344 :     w = int_block(n,l,e); v = vals(w); l-=e;
      98                 :     772668 :     tw = gel(tab, 1+(w>>(v+1)));
      99         [ +  + ]:     772668 :     if (z)
     100                 :            :     {
     101         [ +  + ]:    3322265 :       for (i=1; i<=e-v; i++) z = sqr(E, z);
     102                 :     712354 :       z = mul(E, z, tw);
     103                 :      57907 :     } else z = tw;
     104         [ +  + ]:    1501549 :     for (i=1; i<=v; i++) z = sqr(E, z);
     105         [ +  + ]:    5043103 :     while (l>=0)
     106                 :            :     {
     107         [ +  + ]:    4984753 :       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         [ +  + ]:    4984753 :       if (int_bit(n,l)) break;
     113                 :    4273207 :       z = sqr(E, z); l--;
     114                 :            :     }
     115                 :            :   }
     116                 :      57859 :   return z;
     117                 :            : }
     118                 :            : 
     119                 :            : /* assume n != 0, t_INT. Compute x^|n| using leftright binary powering */
     120                 :            : static GEN
     121                 :   41135755 : leftright_binary_powu(GEN x, ulong n, void *E, GEN (*sqr)(void*,GEN),
     122                 :            :                                               GEN (*mul)(void*,GEN,GEN))
     123                 :            : {
     124                 :   41135755 :   pari_sp av = avma;
     125                 :            :   GEN  y;
     126                 :            :   int j;
     127                 :            : 
     128         [ -  + ]:   41135755 :   if (n == 1) return x;
     129 [ -  + ][ -  + ]:   41135755 :   y = x; j = 1+bfffo(n);
         [ +  + ][ +  + ]
     130                 :            :   /* normalize, i.e set highest bit to 1 (we know n != 0) */
     131                 :   41135755 :   n<<=j; j = BITS_IN_LONG-j;
     132                 :            :   /* first bit is now implicit */
     133 [ +  + ][ +  + ]:   98994460 :   for (; j; n<<=1,j--)
     134                 :            :   {
     135                 :   57858710 :     y = sqr(E,y);
     136         [ +  + ]:   57858702 :     if (n & HIGHBIT) y = mul(E,y,x); /* first bit set: multiply by base */
     137         [ -  + ]:   57858705 :     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                 :   41135750 :   return y;
     144                 :            : }
     145                 :            : 
     146                 :            : GEN
     147                 :   44043866 : gen_powu_i(GEN x, ulong n, void *E, GEN (*sqr)(void*,GEN),
     148                 :            :                                     GEN (*mul)(void*,GEN,GEN))
     149                 :            : {
     150                 :            :   long l;
     151         [ +  + ]:   44043866 :   if (n == 1) return x;
     152                 :   43962527 :   l = expu(n);
     153         [ +  + ]:   43962643 :   if (l<=8)
     154                 :   41135755 :     return leftright_binary_powu(x, n, E, sqr, mul);
     155                 :            :   else
     156         [ +  + ]:   44043977 :     return sliding_window_powu(x, n, l<=24? 2: 3, E, sqr, mul);
     157                 :            : }
     158                 :            : 
     159                 :            : GEN
     160                 :    1138336 : gen_powu(GEN x, ulong n, void *E, GEN (*sqr)(void*,GEN),
     161                 :            :                                   GEN (*mul)(void*,GEN,GEN))
     162                 :            : {
     163                 :    1138336 :   pari_sp av = avma;
     164         [ +  + ]:    1138336 :   if (n == 1) return gcopy(x);
     165                 :    1138336 :   return gerepilecopy(av, gen_powu_i(x,n,E,sqr,mul));
     166                 :            : }
     167                 :            : 
     168                 :            : GEN
     169                 :   22005068 : 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         [ +  + ]:   22005068 :   if (lgefint(n)==3) return gen_powu_i(x, uel(n,2), E, sqr, mul);
     174                 :      57906 :   l = expi(n);
     175         [ +  + ]:      57906 :   if      (l<=64)  e = 3;
     176         [ +  + ]:      34174 :   else if (l<=160) e = 4;
     177         [ +  + ]:       6085 :   else if (l<=384) e = 5;
     178         [ +  + ]:       1164 :   else if (l<=896) e = 6;
     179                 :        646 :   else             e = 7;
     180                 :   22005062 :   return sliding_window_pow(x, n, e, E, sqr, mul);
     181                 :            : }
     182                 :            : 
     183                 :            : GEN
     184                 :    1297835 : gen_pow(GEN x, GEN n, void *E, GEN (*sqr)(void*,GEN),
     185                 :            :                                GEN (*mul)(void*,GEN,GEN))
     186                 :            : {
     187                 :    1297835 :   pari_sp av = avma;
     188                 :    1297835 :   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                 :     279420 : gen_powu_fold_i(GEN x, ulong n, void *E, GEN  (*sqr)(void*,GEN),
     194                 :            :                                          GEN (*msqr)(void*,GEN))
     195                 :            : {
     196                 :     279420 :   pari_sp av = avma;
     197                 :            :   GEN y;
     198                 :            :   int j;
     199                 :            : 
     200         [ -  + ]:     279420 :   if (n == 1) return x;
     201 [ +  + ][ +  + ]:     279420 :   y = x; j = 1+bfffo(n);
         [ +  + ][ +  + ]
     202                 :            :   /* normalize, i.e set highest bit to 1 (we know n != 0) */
     203                 :     279420 :   n<<=j; j = BITS_IN_LONG-j;
     204                 :            :   /* first bit is now implicit */
     205 [ +  + ][ +  + ]:    2796509 :   for (; j; n<<=1,j--)
     206                 :            :   {
     207         [ +  + ]:    2517089 :     if (n & HIGHBIT) y = msqr(E,y); /* first bit set: multiply by base */
     208                 :    2007286 :     else y = sqr(E,y);
     209         [ -  + ]:    2517089 :     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                 :     279420 :   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                 :     144211 : gen_pow_fold_i(GEN x, GEN N, void *E, GEN (*sqr)(void*,GEN),
     229                 :            :                                       GEN (*msqr)(void*,GEN))
     230                 :            : {
     231                 :     144211 :   long ln = lgefint(N);
     232         [ +  + ]:     144211 :   if (ln == 3) return gen_powu_fold_i(x, N[2], E, sqr, msqr);
     233                 :            :   else
     234                 :            :   {
     235                 :      65219 :     GEN nd = int_MSW(N), y = x;
     236                 :      65219 :     ulong n = *nd;
     237                 :            :     long i;
     238                 :            :     int j;
     239                 :      65219 :     pari_sp av = avma;
     240                 :            : 
     241         [ +  + ]:      65219 :     if (n == 1)
     242                 :       6298 :       j = 0;
     243                 :            :     else
     244                 :            :     {
     245 [ +  + ][ +  + ]:      58921 :       j = 1+bfffo(n); /* < BIL */
         [ +  + ][ +  + ]
     246                 :            :       /* normalize, i.e set highest bit to 1 (we know n != 0) */
     247                 :      58921 :       n <<= j; j = BITS_IN_LONG - j;
     248                 :            :     }
     249                 :            :     /* first bit is now implicit */
     250                 :      65219 :     for (i=ln-2;;)
     251                 :            :     {
     252         [ +  + ]:    7390302 :       for (; j; n<<=1,j--)
     253                 :            :       {
     254         [ +  + ]:    7217810 :         if (n & HIGHBIT) y = msqr(E,y); /* first bit set: multiply by base */
     255                 :    6360476 :         else y = sqr(E,y);
     256         [ -  + ]:    7217264 :         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         [ +  + ]:     172492 :       if (--i == 0) return y;
     263                 :     107819 :       nd = int_precW(nd);
     264                 :     107819 :       n = *nd; j = BITS_IN_LONG;
     265                 :     251484 :     }
     266                 :            :   }
     267                 :            : }
     268                 :            : GEN
     269                 :      78993 : gen_pow_fold(GEN x, GEN n, void *E, GEN (*sqr)(void*,GEN),
     270                 :            :                                     GEN (*msqr)(void*,GEN))
     271                 :            : {
     272                 :      78993 :   pari_sp av = avma;
     273                 :      78993 :   return gerepilecopy(av, gen_pow_fold_i(x,n,E,sqr,msqr));
     274                 :            : }
     275                 :            : 
     276                 :            : GEN
     277                 :    3385959 : 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                 :    3385959 :   GEN V = cgetg(l+2,t_VEC);
     282         [ +  + ]:    3385959 :   gel(V,1) = one(E); if (l==0) return V;
     283         [ +  + ]:    3374745 :   gel(V,2) = gcopy(x); if (l==1) return V;
     284                 :    2115552 :   gel(V,3) = sqr(E,x);
     285         [ +  + ]:    2115557 :   if (use_sqr)
     286         [ +  + ]:    5065806 :     for(i = 4; i < l+2; i++)
     287                 :    8849670 :       gel(V,i) = (i&1)? sqr(E,gel(V, (i+1)>>1))
     288         [ +  + ]:    3629511 :                       : mul(E,gel(V, i-1),x);
     289                 :            :   else
     290         [ +  + ]:    1500218 :     for(i = 4; i < l+2; i++)
     291                 :     820960 :       gel(V,i) = mul(E,gel(V,i-1),x);
     292                 :    3385960 :   return V;
     293                 :            : }
     294                 :            : 
     295                 :            : GEN
     296                 :    1502167 : gen_product(GEN x, void *data, GEN (*mul)(void *,GEN,GEN))
     297                 :            : {
     298                 :            :   pari_sp ltop;
     299                 :    1502167 :   long i,k,lx = lg(x);
     300                 :            :   pari_timer ti;
     301         [ -  + ]:    1502167 :   if (DEBUGLEVEL>7) timer_start(&ti);
     302                 :            : 
     303         [ +  + ]:    1502170 :   if (lx == 1) return gen_1;
     304         [ +  + ]:    1501491 :   if (lx == 2) return gcopy(gel(x,1));
     305                 :    1400104 :   x = leafcopy(x); k = lx;
     306                 :    1400145 :   ltop = avma;
     307         [ +  + ]:    4231137 :   while (k > 2)
     308                 :            :   {
     309         [ -  + ]:    2831051 :     if (DEBUGLEVEL>7)
     310                 :          0 :       timer_printf(&ti,"gen_product: remaining objects %ld",k-1);
     311                 :    2831515 :     lx = k; k = 1;
     312         [ +  + ]:   10417206 :     for (i=1; i<lx-1; i+=2)
     313                 :    7586433 :       gel(x,k++) = mul(data,gel(x,i),gel(x,i+1));
     314         [ +  + ]:    2830773 :     if (i < lx) gel(x,k++) = gel(x,i);
     315         [ +  + ]:    2830773 :     if (gc_needed(ltop,1))
     316                 :          8 :       gerepilecoeffs(ltop,x+1,k-1);
     317                 :            :   }
     318                 :    1502154 :   return gel(x,1);
     319                 :            : }
     320                 :            : 
     321                 :            : /***********************************************************************/
     322                 :            : /**                                                                   **/
     323                 :            : /**                    DISCRETE LOGARITHM                             **/
     324                 :            : /**                                                                   **/
     325                 :            : /***********************************************************************/
     326                 :            : 
     327                 :            : static GEN
     328                 :   55393914 : iter_rho(GEN x, GEN g, GEN q, GEN A, ulong h, void *E, const struct bb_group *grp)
     329                 :            : {
     330                 :   55393914 :   GEN a = gel(A,1);
     331   [ +  +  +  - ]:   55393914 :   switch((h|grp->hash(a))%3UL)
     332                 :            :   {
     333                 :            :     case 0:
     334                 :   18471028 :       return mkvec3(grp->pow(E,a,gen_2),Fp_mulu(gel(A,2),2,q),
     335                 :   18471028 :                                         Fp_mulu(gel(A,3),2,q));
     336                 :            :     case 1:
     337                 :   18458341 :       return mkvec3(grp->mul(E,a,x),addis(gel(A,2),1),gel(A,3));
     338                 :            :     case 2:
     339                 :   18464545 :       return mkvec3(grp->mul(E,a,g),gel(A,2),addis(gel(A,3),1));
     340                 :            :   }
     341                 :   55393914 :   return NULL;
     342                 :            : }
     343                 :            : 
     344                 :            : /*Generic Pollard rho discrete log algorithm*/
     345                 :            : static GEN
     346                 :         49 : gen_Pollard_log(GEN x, GEN g, GEN q, void *E, const struct bb_group *grp)
     347                 :            : {
     348                 :         49 :   pari_sp av=avma;
     349                 :         49 :   GEN A, B, l, sqrt4q = sqrti(shifti(q,4));
     350                 :         49 :   ulong i, h = 0, imax = itou_or_0(sqrt4q);
     351         [ -  + ]:         49 :   if (!imax) imax = ULONG_MAX;
     352                 :            :   do {
     353                 :            :  rho_restart:
     354                 :         49 :     A = B = mkvec3(x,gen_1,gen_0);
     355                 :         49 :     i=0;
     356                 :            :     do {
     357         [ -  + ]:   18464638 :       if (i>imax)
     358                 :            :       {
     359                 :          0 :         h++;
     360         [ #  # ]:          0 :         if (DEBUGLEVEL)
     361                 :          0 :           pari_warn(warner,"changing Pollard rho hash seed to %ld",h);
     362                 :          0 :         goto rho_restart;
     363                 :            :       }
     364                 :   18464638 :       A = iter_rho(x, g, q, A, h, E, grp);
     365                 :   18464638 :       B = iter_rho(x, g, q, B, h, E, grp);
     366                 :   18464638 :       B = iter_rho(x, g, q, B, h, E, grp);
     367         [ +  + ]:   18464638 :       if (gc_needed(av,2))
     368                 :            :       {
     369         [ -  + ]:       1756 :         if(DEBUGMEM>1) pari_warn(warnmem,"gen_Pollard_log");
     370                 :       1756 :         gerepileall(av, 2, &A, &B);
     371                 :            :       }
     372                 :   18464638 :       i++;
     373         [ +  + ]:   18464638 :     } while (!grp->equal(gel(A,1), gel(B,1)));
     374                 :         49 :     gel(A,2) = modii(gel(A,2), q);
     375                 :         49 :     gel(B,2) = modii(gel(B,2), q);
     376                 :         49 :     h++;
     377         [ -  + ]:         49 :   } while (equalii(gel(A,2), gel(B,2)));
     378                 :         49 :   l = Fp_div(Fp_sub(gel(B,3), gel(A,3),q),Fp_sub(gel(A,2), gel(B,2), q), q);
     379                 :         49 :   return gerepileuptoint(av, l);
     380                 :            : }
     381                 :            : 
     382                 :            : /* compute a hash of g^(i-1), 1<=i<=n. Return [sorted hash, perm, g^-n] */
     383                 :            : GEN
     384                 :     506031 : gen_Shanks_init(GEN g, long n, void *E, const struct bb_group *grp)
     385                 :            : {
     386                 :     506031 :   GEN p1 = g, G, perm, table = cgetg(n+1,t_VECSMALL);
     387                 :     506031 :   pari_sp av=avma;
     388                 :            :   long i;
     389                 :     506031 :   table[1] = grp->hash(grp->pow(E,g,gen_0));
     390         [ +  + ]:    2748737 :   for (i=2; i<=n; i++)
     391                 :            :   {
     392                 :    2242706 :     table[i] = grp->hash(p1);
     393                 :    2242706 :     p1 = grp->mul(E,p1,g);
     394         [ -  + ]:    2242706 :     if (gc_needed(av,2))
     395                 :            :     {
     396         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_log, baby = %ld", i);
     397                 :          0 :       p1 = gerepileupto(av, p1);
     398                 :            :     }
     399                 :            :   }
     400                 :     506031 :   G = gerepileupto(av, grp->pow(E,p1,gen_m1)); /* g^-n */
     401                 :     506031 :   perm = vecsmall_indexsort(table);
     402                 :     506031 :   table = vecsmallpermute(table,perm);
     403                 :     506031 :   return mkvec4(table,perm,g,G);
     404                 :            : }
     405                 :            : /* T from gen_Shanks_init(g,n). Return v < n*N such that x = g^v or NULL */
     406                 :            : GEN
     407                 :     506479 : gen_Shanks(GEN T, GEN x, ulong N, void *E, const struct bb_group *grp)
     408                 :            : {
     409                 :     506479 :   pari_sp av=avma;
     410                 :     506479 :   GEN table = gel(T,1), perm = gel(T,2), g = gel(T,3), G = gel(T,4);
     411                 :     506479 :   GEN p1 = x;
     412                 :     506479 :   long n = lg(table)-1;
     413                 :            :   ulong k;
     414         [ +  + ]:    3095795 :   for (k=0; k<N; k++)
     415                 :            :   { /* p1 = x G^k, G = g^-n */
     416                 :    3053276 :     long h = grp->hash(p1), i = zv_search(table, h);
     417         [ +  + ]:    3053276 :     if (i)
     418                 :            :     {
     419 [ +  + ][ +  + ]:     464705 :       do i--; while (i && table[i] == h);
     420 [ +  - ][ +  - ]:     463960 :       for (i++; i <= n && table[i] == h; i++)
     421                 :            :       {
     422                 :     463960 :         GEN v = addiu(muluu(n,k), perm[i]-1);
     423         [ +  - ]:     463960 :         if (grp->equal(grp->pow(E,g,v),x)) return gerepileuptoint(av,v);
     424         [ #  # ]:          0 :         if (DEBUGLEVEL)
     425                 :          0 :           err_printf("gen_Shanks_log: false positive %lu, %lu\n", k,h);
     426                 :            :       }
     427                 :            :     }
     428                 :    2589316 :     p1 = grp->mul(E,p1,G);
     429         [ -  + ]:    2589316 :     if (gc_needed(av,2))
     430                 :            :     {
     431         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_log, k = %lu", k);
     432                 :          0 :       p1 = gerepileupto(av, p1);
     433                 :            :     }
     434                 :            :   }
     435                 :     506479 :   return NULL;
     436                 :            : }
     437                 :            : /* Generic Shanks baby-step/giant-step algorithm. Return log_g(x), ord g = q.
     438                 :            :  * One-shot: use gen_Shanks_init/log if many logs are desired; early abort
     439                 :            :  * if log < sqrt(q) */
     440                 :            : static GEN
     441                 :      79436 : gen_Shanks_log(GEN x, GEN g, GEN q, void *E, const struct bb_group *grp)
     442                 :            : {
     443                 :      79436 :   pari_sp av=avma, av1;
     444                 :            :   long lbaby, i, k;
     445                 :            :   GEN p1, table, giant, perm, ginv;
     446                 :      79436 :   p1 = sqrti(q);
     447         [ -  + ]:      79436 :   if (cmpiu(p1,LGBITS) >= 0)
     448                 :          0 :     pari_err_OVERFLOW("gen_Shanks_log [order too large]");
     449                 :      79436 :   lbaby = itos(p1)+1; table = cgetg(lbaby+1,t_VECSMALL);
     450                 :      79436 :   ginv = grp->pow(E,g,gen_m1);
     451                 :      79436 :   av1 = avma;
     452                 :      79436 :   for (p1=x, i=1;;i++)
     453                 :            :   {
     454         [ +  + ]:     853888 :     if (grp->equal1(p1)) { avma = av; return stoi(i-1); }
     455         [ +  + ]:     843325 :     table[i] = grp->hash(p1); if (i==lbaby) break;
     456                 :     774452 :     p1 = grp->mul(E,p1,ginv);
     457         [ +  + ]:     774452 :     if (gc_needed(av1,2))
     458                 :            :     {
     459         [ -  + ]:          7 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_log, baby = %ld", i);
     460                 :          7 :       p1 = gerepileupto(av1, p1);
     461                 :            :     }
     462                 :     774452 :   }
     463                 :      68873 :   p1 = giant = gerepileupto(av1, grp->mul(E,x,grp->pow(E, p1, gen_m1)));
     464                 :      68873 :   perm = vecsmall_indexsort(table);
     465                 :      68873 :   table = vecsmallpermute(table,perm);
     466                 :      68873 :   av1 = avma;
     467         [ +  - ]:     439677 :   for (k=1; k<= lbaby; k++)
     468                 :            :   {
     469                 :     439677 :     long h = grp->hash(p1), i = zv_search(table, h);
     470         [ +  + ]:     439677 :     if (i)
     471                 :            :     {
     472 [ +  + ][ +  - ]:     137746 :       while (table[i] == h && i) i--;
     473 [ +  - ][ +  - ]:      68873 :       for (i++; i <= lbaby && table[i] == h; i++)
     474                 :            :       {
     475                 :      68873 :         GEN v = addiu(mulss(lbaby-1,k),perm[i]-1);
     476         [ +  - ]:      68873 :         if (grp->equal(grp->pow(E,g,v),x)) return gerepileuptoint(av,v);
     477         [ #  # ]:          0 :         if (DEBUGLEVEL)
     478                 :          0 :           err_printf("gen_Shanks_log: false positive %ld, %lu\n", k,h);
     479                 :            :       }
     480                 :            :     }
     481                 :     370804 :     p1 = grp->mul(E,p1,giant);
     482         [ -  + ]:     370804 :     if (gc_needed(av1,2))
     483                 :            :     {
     484         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_log, k = %ld", k);
     485                 :          0 :       p1 = gerepileupto(av1, p1);
     486                 :            :     }
     487                 :            :   }
     488                 :      79436 :   avma = av; return cgetg(1, t_VEC); /* no solution */
     489                 :            : }
     490                 :            : 
     491                 :            : /*Generic discrete logarithme in a group of prime order p*/
     492                 :            : GEN
     493                 :     425698 : gen_plog(GEN x, GEN g, GEN p, void *E, const struct bb_group *grp)
     494                 :            : {
     495         [ +  + ]:     425698 :   if (grp->easylog)
     496                 :            :   {
     497                 :     417958 :     GEN e = grp->easylog(E, x, g, p);
     498         [ +  + ]:     417958 :     if (e) return e;
     499                 :            :   }
     500         [ +  + ]:      92532 :   if (grp->equal1(x)) return gen_0;
     501         [ +  + ]:      92490 :   if (grp->equal(x,g)) return gen_1;
     502         [ +  + ]:      79485 :   if (expi(p)<32) return gen_Shanks_log(x,g,p,E,grp);
     503                 :     425698 :   return gen_Pollard_log(x, g, p, E, grp);
     504                 :            : }
     505                 :            : 
     506                 :            : GEN
     507                 :    1697094 : dlog_get_ordfa(GEN o)
     508                 :            : {
     509         [ -  + ]:    1697094 :   if (!o) return NULL;
     510   [ +  +  +  + ]:    1697094 :   switch(typ(o))
     511                 :            :   {
     512                 :            :     case t_INT:
     513         [ +  + ]:    1306246 :       if (signe(o) > 0) return mkvec2(o, Z_factor(o));
     514                 :          7 :       break;
     515                 :            :     case t_MAT:
     516         [ +  + ]:     196106 :       if (is_Z_factorpos(o)) return mkvec2(factorback(o), o);
     517                 :         14 :       break;
     518                 :            :     case t_VEC:
     519 [ +  - ][ +  - ]:     194735 :       if (lg(o) == 3 && signe(gel(o,1)) > 0 && is_Z_factorpos(gel(o,2))) return o;
                 [ +  - ]
     520                 :          0 :       break;
     521                 :            :   }
     522                 :         28 :   pari_err_TYPE("generic discrete logarithm (order factorization)",o);
     523                 :    1697066 :   return NULL; /* not reached */
     524                 :            : }
     525                 :            : GEN
     526                 :      75781 : dlog_get_ord(GEN o)
     527                 :            : {
     528         [ -  + ]:      75781 :   if (!o) return NULL;
     529   [ +  +  +  + ]:      75781 :   switch(typ(o))
     530                 :            :   {
     531                 :            :     case t_INT:
     532         [ +  + ]:      56493 :       if (signe(o) > 0) return o;
     533                 :          7 :       break;
     534                 :            :     case t_MAT:
     535                 :         14 :       o = factorback(o);
     536 [ #  # ][ #  # ]:          0 :       if (typ(o) == t_INT && signe(o) > 0) return o;
     537                 :          0 :       break;
     538                 :            :     case t_VEC:
     539         [ -  + ]:      19267 :       if (lg(o) != 3) break;
     540                 :      19267 :       o = gel(o,1);
     541 [ +  - ][ +  - ]:      19267 :       if (typ(o) == t_INT && signe(o) > 0) return o;
     542                 :          0 :       break;
     543                 :            :   }
     544                 :         14 :   pari_err_TYPE("generic discrete logarithm (order factorization)",o);
     545                 :      75753 :   return NULL; /* not reached */
     546                 :            : }
     547                 :            : 
     548                 :            : /* grp->easylog() is an optional trapdoor function that catch easy logarithms*/
     549                 :            : /* Generic Pohlig-Hellman discrete logarithm*/
     550                 :            : /* smallest integer n such that g^n=a. Assume g has order ord */
     551                 :            : GEN
     552                 :     238914 : gen_PH_log(GEN a, GEN g, GEN ord, void *E, const struct bb_group *grp)
     553                 :            : {
     554                 :     238914 :   pari_sp av = avma;
     555                 :            :   GEN v,t0,a0,b,q,g_q,n_q,ginv0,qj,ginv;
     556                 :            :   GEN fa, ex;
     557                 :            :   long e,i,j,l;
     558                 :            : 
     559         [ +  + ]:     238914 :   if (grp->equal(g, a)) /* frequent special case */
     560         [ +  + ]:      49078 :     return grp->equal1(g)? gen_0: gen_1;
     561         [ +  + ]:     189836 :   if (grp->easylog)
     562                 :            :   {
     563                 :     189738 :     GEN e = grp->easylog(E, a, g, ord);
     564         [ +  + ]:     189710 :     if (e) return e;
     565                 :            :   }
     566                 :     101365 :   v = dlog_get_ordfa(ord);
     567                 :     101365 :   ord= gel(v,1);
     568                 :     101365 :   fa = gel(v,2);
     569                 :     101365 :   ex = gel(fa,2);
     570                 :     101365 :   fa = gel(fa,1); l = lg(fa);
     571                 :     101365 :   ginv = grp->pow(E,g,gen_m1);
     572                 :     101365 :   v = cgetg(l, t_VEC);
     573         [ +  + ]:     275801 :   for (i=1; i<l; i++)
     574                 :            :   {
     575                 :     174443 :     q = gel(fa,i);
     576                 :     174443 :     e = itos(gel(ex,i));
     577         [ -  + ]:     174443 :     if (DEBUGLEVEL>5)
     578                 :          0 :       err_printf("Pohlig-Hellman: DL mod %Ps^%ld\n",q,e);
     579                 :     174443 :     qj = new_chunk(e+1);
     580                 :     174443 :     gel(qj,0) = gen_1;
     581                 :     174443 :     gel(qj,1) = q;
     582         [ +  + ]:     266626 :     for (j=2; j<=e; j++) gel(qj,j) = mulii(gel(qj,j-1), q);
     583                 :     174443 :     t0 = diviiexact(ord, gel(qj,e));
     584                 :     174443 :     a0 = grp->pow(E, a, t0);
     585                 :     174443 :     ginv0 = grp->pow(E, ginv, t0); /* order q^e */
     586         [ +  + ]:     174443 :     if (grp->equal1(ginv0))
     587                 :            :     {
     588                 :         14 :       gel(v,i) = mkintmod(gen_0, gen_1);
     589                 :         14 :       continue;
     590                 :            :     }
     591                 :     174436 :     do { g_q = grp->pow(E,g, mulii(t0, gel(qj,--e))); /* order q */
     592         [ +  + ]:     174436 :     } while (grp->equal1(g_q));
     593                 :     174429 :     n_q = gen_0;
     594                 :     174429 :     for (j=0;; j++)
     595                 :            :     { /* n_q = sum_{i<j} b_i q^i */
     596                 :     266577 :       b = grp->pow(E,a0, gel(qj,e-j));
     597                 :            :       /* early abort: cheap and very effective */
     598 [ +  + ][ +  + ]:     266577 :       if (j == 0 && !grp->equal1(grp->pow(E,b,q))) {
     599                 :          7 :         avma = av; return cgetg(1, t_VEC);
     600                 :            :       }
     601                 :     266570 :       b = gen_plog(b, g_q, q, E, grp);
     602         [ -  + ]:     266570 :       if (typ(b) != t_INT) { avma = av; return cgetg(1, t_VEC); }
     603                 :     266570 :       n_q = addii(n_q, mulii(b, gel(qj,j)));
     604         [ +  + ]:     266570 :       if (j == e) break;
     605                 :            : 
     606                 :      92148 :       a0 = grp->mul(E,a0, grp->pow(E,ginv0, b));
     607                 :      92148 :       ginv0 = grp->pow(E,ginv0, q);
     608                 :      92148 :     }
     609                 :     174422 :     gel(v,i) = mkintmod(n_q, gel(qj,e+1));
     610                 :            :   }
     611                 :     238886 :   return gerepileuptoint(av, lift(chinese1_coprime_Z(v)));
     612                 :            : }
     613                 :            : 
     614                 :            : /***********************************************************************/
     615                 :            : /**                                                                   **/
     616                 :            : /**                    ORDER OF AN ELEMENT                            **/
     617                 :            : /**                                                                   **/
     618                 :            : /***********************************************************************/
     619                 :            : /*Find the exact order of a assuming a^o==1*/
     620                 :            : GEN
     621                 :     707873 : gen_order(GEN a, GEN o, void *E, const struct bb_group *grp)
     622                 :            : {
     623                 :     707873 :   pari_sp av = avma;
     624                 :            :   long i, l;
     625                 :            :   GEN m;
     626                 :            : 
     627                 :     707873 :   m = dlog_get_ordfa(o);
     628         [ -  + ]:     707873 :   if (!m) pari_err_TYPE("gen_order [missing order]",a);
     629                 :     707873 :   o = gel(m,1);
     630                 :     707873 :   m = gel(m,2); l = lgcols(m);
     631         [ +  + ]:    2485491 :   for (i = l-1; i; i--)
     632                 :            :   {
     633                 :    1777618 :     GEN t, y, p = gcoeff(m,i,1);
     634                 :    1777618 :     long j, e = itos(gcoeff(m,i,2));
     635         [ +  + ]:    1777618 :     if (l == 2) {
     636                 :     129876 :       t = gen_1;
     637                 :     129876 :       y = a;
     638                 :            :     } else {
     639                 :    1647742 :       t = diviiexact(o, powiu(p,e));
     640                 :    1647742 :       y = grp->pow(E, a, t);
     641                 :            :     }
     642         [ +  + ]:    1777618 :     if (grp->equal1(y)) o = t;
     643                 :            :     else {
     644         [ +  + ]:    1870233 :       for (j = 1; j < e; j++)
     645                 :            :       {
     646                 :     683888 :         y = grp->pow(E, y, p);
     647         [ +  + ]:     683888 :         if (grp->equal1(y)) break;
     648                 :            :       }
     649         [ +  + ]:    1402905 :       if (j < e) {
     650         [ +  + ]:     216560 :         if (j > 1) p = powiu(p, j);
     651                 :     216560 :         o = mulii(t, p);
     652                 :            :       }
     653                 :            :     }
     654                 :            :   }
     655                 :     707873 :   return gerepilecopy(av, o);
     656                 :            : }
     657                 :            : 
     658                 :            : /*Find the exact order of a assuming a^o==1, return [order,factor(order)] */
     659                 :            : GEN
     660                 :     580057 : gen_factored_order(GEN a, GEN o, void *E, const struct bb_group *grp)
     661                 :            : {
     662                 :     580057 :   pari_sp av = avma;
     663                 :            :   long i, l, ind;
     664                 :            :   GEN m, F, P;
     665                 :            : 
     666                 :     580057 :   m = dlog_get_ordfa(o);
     667         [ -  + ]:     580057 :   if (!m) pari_err_TYPE("gen_factored_order [missing order]",a);
     668                 :     580057 :   o = gel(m,1);
     669                 :     580057 :   m = gel(m,2); l = lgcols(m);
     670                 :     580057 :   P = cgetg(l, t_COL); ind = 1;
     671                 :     580057 :   F = cgetg(l, t_COL);
     672         [ +  + ]:    1400354 :   for (i = l-1; i; i--)
     673                 :            :   {
     674                 :     820297 :     GEN t, y, p = gcoeff(m,i,1);
     675                 :     820297 :     long j, e = itos(gcoeff(m,i,2));
     676         [ +  + ]:     820297 :     if (l == 2) {
     677                 :     350339 :       t = gen_1;
     678                 :     350339 :       y = a;
     679                 :            :     } else {
     680                 :     469958 :       t = diviiexact(o, powiu(p,e));
     681                 :     469958 :       y = grp->pow(E, a, t);
     682                 :            :     }
     683         [ +  + ]:     820297 :     if (grp->equal1(y)) o = t;
     684                 :            :     else {
     685         [ +  + ]:    1034655 :       for (j = 1; j < e; j++)
     686                 :            :       {
     687                 :     224326 :         y = grp->pow(E, y, p);
     688         [ +  + ]:     224326 :         if (grp->equal1(y)) break;
     689                 :            :       }
     690                 :     813143 :       gel(P,ind) = p;
     691                 :     813143 :       gel(F,ind) = utoipos(j);
     692         [ +  + ]:     813143 :       if (j < e) {
     693         [ +  + ]:       2814 :         if (j > 1) p = powiu(p, j);
     694                 :       2814 :         o = mulii(t, p);
     695                 :            :       }
     696                 :     813143 :       ind++;
     697                 :            :     }
     698                 :            :   }
     699                 :     580057 :   setlg(P, ind); P = vecreverse(P);
     700                 :     580057 :   setlg(F, ind); F = vecreverse(F);
     701                 :     580057 :   return gerepilecopy(av, mkvec2(o, mkmat2(P,F)));
     702                 :            : }
     703                 :            : 
     704                 :            : /* E has order o[1], ..., or o[#o], draw random points until all solutions
     705                 :            :  * but one are eliminated */
     706                 :            : GEN
     707                 :        917 : gen_select_order(GEN o, void *E, const struct bb_group *grp)
     708                 :            : {
     709                 :        917 :   pari_sp ltop = avma, btop;
     710                 :            :   GEN lastgood, so, vo;
     711                 :        917 :   long lo = lg(o), nbo=lo-1;
     712         [ +  + ]:        917 :   if (nbo == 1) return icopy(gel(o,1));
     713                 :        448 :   so = ZV_indexsort(o); /* minimize max( o[i+1] - o[i] ) */
     714                 :        448 :   vo = zero_zv(lo);
     715                 :        448 :   lastgood = gel(o, so[nbo]);
     716                 :        448 :   btop = avma;
     717                 :            :   for(;;)
     718                 :            :   {
     719                 :        448 :     GEN lasto = gen_0;
     720                 :        448 :     GEN P = grp->rand(E), t = mkvec(gen_0);
     721                 :            :     long i;
     722         [ +  - ]:        623 :     for (i = 1; i < lo; i++)
     723                 :            :     {
     724                 :        623 :       GEN newo = gel(o, so[i]);
     725         [ -  + ]:        623 :       if (vo[i]) continue;
     726                 :        623 :       t = grp->mul(E,t, grp->pow(E, P, subii(newo,lasto)));/*P^o[i]*/
     727                 :        623 :       lasto = newo;
     728         [ +  + ]:        623 :       if (!grp->equal1(t))
     729                 :            :       {
     730         [ +  + ]:        539 :         if (--nbo == 1) { avma=ltop; return icopy(lastgood); }
     731                 :         91 :         vo[i] = 1;
     732                 :            :       }
     733                 :            :       else
     734                 :         84 :         lastgood = lasto;
     735                 :            :     }
     736                 :          0 :     avma = btop;
     737                 :        917 :   }
     738                 :            : }
     739                 :            : 
     740                 :            : /*******************************************************************/
     741                 :            : /*                                                                 */
     742                 :            : /*                          n-th ROOT                              */
     743                 :            : /*                                                                 */
     744                 :            : /*******************************************************************/
     745                 :            : /* Assume l is prime. Return a generator of the l-th Sylow and set *zeta to an element
     746                 :            :  * of order l.
     747                 :            :  *
     748                 :            :  * q = l^e*r, e>=1, (r,l)=1
     749                 :            :  * UNCLEAN */
     750                 :            : static GEN
     751                 :     214393 : gen_lgener(GEN l, long e, GEN r,GEN *zeta, void *E, const struct bb_group *grp)
     752                 :            : {
     753                 :     214393 :   const pari_sp av1 = avma;
     754                 :            :   GEN m, m1;
     755                 :            :   long i;
     756                 :     182575 :   for (;; avma = av1)
     757                 :            :   {
     758                 :     396968 :     m1 = m = grp->pow(E, grp->rand(E), r);
     759         [ +  + ]:     396969 :     if (grp->equal1(m)) continue;
     760         [ +  + ]:     768943 :     for (i=1; i<e; i++)
     761                 :            :     {
     762                 :     554549 :       m = grp->pow(E,m,l);
     763         [ +  + ]:     554549 :       if (grp->equal1(m)) break;
     764                 :            :     }
     765         [ +  + ]:     326006 :     if (i==e) break;
     766                 :     182575 :   }
     767                 :     214394 :   *zeta = m; return m1;
     768                 :            : }
     769                 :            : 
     770                 :            : /* Let G be a cyclic group of order o>1. Returns a (random) generator */
     771                 :            : 
     772                 :            : GEN
     773                 :      14665 : gen_gener(GEN o, void *E, const struct bb_group *grp)
     774                 :            : {
     775                 :      14665 :   pari_sp ltop = avma, av;
     776                 :            :   long i, lpr;
     777                 :      14665 :   GEN F, N, pr, z=NULL;
     778                 :      14665 :   F = dlog_get_ordfa(o);
     779                 :      14665 :   N = gel(F,1); pr = gel(F,2); lpr = lgcols(pr);
     780                 :      14665 :   av = avma;
     781                 :            : 
     782         [ +  + ]:      48811 :   for (i = 1; i < lpr; i++)
     783                 :            :   {
     784                 :      34146 :     GEN l = gcoeff(pr,i,1);
     785                 :      34146 :     long e = itos(gcoeff(pr,i,2));
     786                 :      34146 :     GEN r = diviiexact(N,powis(l,e));
     787                 :      34146 :     GEN zetan, zl = gen_lgener(l,e,r,&zetan,E,grp);
     788         [ +  + ]:      34146 :     z = i==1 ? zl: grp->mul(E,z,zl);
     789         [ -  + ]:      34146 :     if (gc_needed(av,2))
     790                 :            :     { /* n can have lots of prime factors*/
     791         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_gener");
     792                 :          0 :       z = gerepileupto(av, z);
     793                 :            :     }
     794                 :            :   }
     795                 :      14665 :   return gerepileupto(ltop, z);
     796                 :            : }
     797                 :            : 
     798                 :            : /* solve x^l = a , l prime in G of order q.
     799                 :            :  *
     800                 :            :  * q =  (l^e)*r, e >= 1, (r,l) = 1
     801                 :            :  * y is not an l-th power, hence generates the l-Sylow of G
     802                 :            :  * m = y^(q/l) != 1 */
     803                 :            : static GEN
     804                 :     180318 : gen_Shanks_sqrtl(GEN a, GEN l, long e, GEN r, GEN y, GEN m,void *E,
     805                 :            :                  const struct bb_group *grp)
     806                 :            : {
     807                 :     180318 :   pari_sp av = avma;
     808                 :            :   long k;
     809                 :            :   GEN p1, u1, u2, v, w, z, dl;
     810                 :            : 
     811                 :     180318 :   (void)bezout(r,l,&u1,&u2);
     812                 :     180318 :   v = grp->pow(E,a,u2);
     813                 :     180318 :   w = grp->pow(E,v,l);
     814                 :     180318 :   w = grp->mul(E,w,grp->pow(E,a,gen_m1));
     815         [ +  + ]:     339432 :   while (!grp->equal1(w))
     816                 :            :   {
     817                 :     162868 :     k = 0;
     818                 :     162868 :     p1 = w;
     819                 :            :     do
     820                 :            :     {
     821                 :     282705 :       z = p1; p1 = grp->pow(E,p1,l);
     822                 :     282705 :       k++;
     823         [ +  + ]:     282705 :     } while(!grp->equal1(p1));
     824         [ +  + ]:     162868 :     if (k==e) { avma = av; return NULL; }
     825                 :     159128 :     dl = gen_plog(z,m,l,E,grp);
     826         [ -  + ]:     159128 :     if (typ(dl) != t_INT) { avma = av; return NULL; }
     827                 :     159128 :     dl = negi(dl);
     828                 :     159128 :     p1 = grp->pow(E, grp->pow(E,y, dl), powiu(l,e-k-1));
     829                 :     159128 :     m = grp->pow(E,m,dl);
     830                 :     159128 :     e = k;
     831                 :     159128 :     v = grp->mul(E,p1,v);
     832                 :     159128 :     y = grp->pow(E,p1,l);
     833                 :     159128 :     w = grp->mul(E,y,w);
     834         [ -  + ]:     159128 :     if (gc_needed(av,1))
     835                 :            :     {
     836         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_sqrtl");
     837                 :          0 :       gerepileall(av,4, &y,&v,&w,&m);
     838                 :            :     }
     839                 :            :   }
     840                 :     180304 :   return gerepilecopy(av, v);
     841                 :            : }
     842                 :            : /* Return one solution of x^n = a in a cyclic group of order q
     843                 :            :  *
     844                 :            :  * 1) If there is no solution, return NULL.
     845                 :            :  *
     846                 :            :  * 2) If there is a solution, there are exactly m of them [m = gcd(q-1,n)].
     847                 :            :  * If zetan!=NULL, *zetan is set to a primitive m-th root of unity so that
     848                 :            :  * the set of solutions is { x*zetan^k; k=0..m-1 }
     849                 :            :  */
     850                 :            : GEN
     851                 :     185526 : gen_Shanks_sqrtn(GEN a, GEN n, GEN q, GEN *zetan, void *E, const struct bb_group *grp)
     852                 :            : {
     853                 :     185526 :   pari_sp ltop = avma;
     854                 :            :   GEN m, u1, u2, z;
     855                 :            :   int is_1;
     856                 :            : 
     857         [ -  + ]:     185526 :   if (is_pm1(n))
     858                 :            :   {
     859         [ #  # ]:          0 :     if (zetan) *zetan = grp->pow(E,a,gen_0);
     860         [ #  # ]:          0 :     return signe(n) < 0? grp->pow(E,a,gen_m1): gcopy(a);
     861                 :            :   }
     862                 :     185526 :   is_1 = grp->equal1(a);
     863 [ +  + ][ +  + ]:     185526 :   if (is_1 && !zetan) return gcopy(a);
     864                 :            : 
     865                 :     180521 :   m = bezout(n,q,&u1,&u2);
     866                 :     180521 :   z = grp->pow(E,a,gen_0);
     867         [ +  + ]:     180521 :   if (!is_pm1(m))
     868                 :            :   {
     869                 :     180206 :     GEN F = Z_factor(m);
     870                 :            :     long i, j, e;
     871                 :            :     GEN r, zeta, y, l;
     872                 :     180205 :     pari_sp av1 = avma;
     873         [ +  + ]:     356699 :     for (i = nbrows(F); i; i--)
     874                 :            :     {
     875                 :     180247 :       l = gcoeff(F,i,1);
     876                 :     180247 :       j = itos(gcoeff(F,i,2));
     877                 :     180247 :       e = Z_pvalrem(q,l,&r);
     878                 :     180247 :       y = gen_lgener(l,e,r,&zeta,E,grp);
     879         [ +  + ]:     180248 :       if (zetan) z = grp->mul(E,z, grp->pow(E,y,powiu(l,e-j)));
     880         [ +  + ]:     180248 :       if (!is_1) {
     881                 :            :         do
     882                 :            :         {
     883                 :     180318 :           a = gen_Shanks_sqrtl(a,l,e,r,y,zeta,E,grp);
     884         [ +  + ]:     180304 :           if (!a) { avma = ltop; return NULL;}
     885         [ +  + ]:     176564 :         } while (--j);
     886                 :            :       }
     887         [ -  + ]:     176494 :       if (gc_needed(ltop,1))
     888                 :            :       { /* n can have lots of prime factors*/
     889         [ #  # ]:          0 :         if(DEBUGMEM>1) pari_warn(warnmem,"gen_Shanks_sqrtn");
     890         [ #  # ]:          0 :         gerepileall(av1, zetan? 2: 1, &a, &z);
     891                 :            :       }
     892                 :            :     }
     893                 :            :   }
     894         [ +  + ]:     176767 :   if (!equalii(m, n))
     895                 :        336 :     a = grp->pow(E,a,modii(u1,q));
     896         [ +  + ]:     176767 :   if (zetan)
     897                 :            :   {
     898                 :        119 :     *zetan = z;
     899                 :        119 :     gerepileall(ltop,2,&a,zetan);
     900                 :            :   }
     901                 :            :   else /* is_1 is 0: a was modified above -> gerepileupto valid */
     902                 :     176648 :     a = gerepileupto(ltop, a);
     903                 :     185512 :   return a;
     904                 :            : }
     905                 :            : 
     906                 :            : /*******************************************************************/
     907                 :            : /*                                                                 */
     908                 :            : /*               structure of groups with pairing                  */
     909                 :            : /*                                                                 */
     910                 :            : /*******************************************************************/
     911                 :            : 
     912                 :            : static GEN
     913                 :      39515 : ellgroup_d2(GEN N, GEN d)
     914                 :            : {
     915                 :      39515 :   GEN r = gcdii(N, d);
     916                 :      39515 :   GEN F1 = gel(Z_factor(r), 1);
     917                 :      39515 :   long i, j, l1 = lg(F1);
     918                 :      39515 :   GEN F = cgetg(3, t_MAT);
     919                 :      39515 :   gel(F,1) = cgetg(l1, t_COL);
     920                 :      39515 :   gel(F,2) = cgetg(l1, t_COL);
     921         [ +  + ]:      69517 :   for (i = 1, j = 1; i < l1; ++i)
     922                 :            :   {
     923                 :      30002 :     long v = Z_pval(N, gel(F1, i));
     924         [ +  + ]:      30002 :     if (v<=1) continue;
     925                 :      15554 :     gcoeff(F, j  , 1) = gel(F1, i);
     926                 :      15554 :     gcoeff(F, j++, 2) = stoi(v);
     927                 :            :   }
     928                 :      39515 :   setlg(F[1],j); setlg(F[2],j);
     929         [ +  + ]:      39515 :   return j==1 ? NULL : mkvec2(factorback(F), F);
     930                 :            : }
     931                 :            : 
     932                 :            : GEN
     933                 :      39592 : gen_ellgroup(GEN N, GEN d, GEN *pt_m, void *E, const struct bb_group *grp,
     934                 :            :              GEN pairorder(void *E, GEN P, GEN Q, GEN m, GEN F))
     935                 :            : {
     936                 :      39592 :   pari_sp av = avma;
     937                 :            :   GEN N0, N1, F;
     938         [ +  - ]:      39592 :   if (pt_m) *pt_m = gen_1;
     939         [ +  + ]:      39592 :   if (is_pm1(N)) return cgetg(1,t_VEC);
     940                 :      39515 :   F = ellgroup_d2(N, d);
     941         [ +  + ]:      39515 :   if (!F) {avma = av; return mkveccopy(N);}
     942                 :      14861 :   N0 = gel(F,1); N1 = diviiexact(N, N0);
     943                 :            :   while(1)
     944                 :            :   {
     945                 :      26776 :     pari_sp av2 = avma;
     946                 :            :     GEN P, Q, d, s, t, m;
     947                 :            : 
     948                 :      26776 :     P = grp->pow(E,grp->rand(E), N1);
     949         [ +  + ]:      26776 :     s = gen_order(P, F, E, grp); if (equalii(s, N0)) {avma = av; return mkveccopy(N);}
     950                 :            : 
     951                 :      21107 :     Q = grp->pow(E,grp->rand(E), N1);
     952         [ +  + ]:      21107 :     t = gen_order(Q, F, E, grp); if (equalii(t, N0)) {avma = av; return mkveccopy(N);}
     953                 :            : 
     954                 :      18509 :     m = lcmii(s, t);
     955                 :      18509 :     d = pairorder(E, P, Q, m, F);
     956                 :            :     /* structure is [N/d, d] iff m d == N0. Note that N/d = N1 m */
     957 [ +  + ][ +  + ]:      18509 :     if (is_pm1(d) && equalii(m, N0)) {avma = av; return mkveccopy(N);}
     958         [ +  + ]:      18481 :     if (equalii(mulii(m, d), N0))
     959                 :            :     {
     960                 :       6566 :       GEN g = mkvec2(mulii(N1,m), d);
     961         [ +  - ]:       6566 :       if (pt_m) *pt_m = m;
     962         [ +  - ]:       6566 :       gerepileall(av,pt_m?2:1,&g,pt_m);
     963                 :       6566 :       return g;
     964                 :            :     }
     965                 :      11915 :     avma = av2;
     966                 :      51507 :   }
     967                 :            : }
     968                 :            : 
     969                 :            : GEN
     970                 :       2646 : gen_ellgens(GEN D1, GEN d2, GEN m, void *E, const struct bb_group *grp,
     971                 :            :              GEN pairorder(void *E, GEN P, GEN Q, GEN m, GEN F))
     972                 :            : {
     973                 :       2646 :   pari_sp ltop = avma, av;
     974                 :            :   GEN F, d1, dm;
     975                 :            :   GEN P, Q, d, s;
     976                 :       2646 :   F = dlog_get_ordfa(D1);
     977                 :       2646 :   d1 = gel(F, 1), dm =  diviiexact(d1,m);
     978                 :       2646 :   av = avma;
     979                 :            :   do
     980                 :            :   {
     981                 :       7004 :     avma = av;
     982                 :       7004 :     P = grp->rand(E);
     983                 :       7004 :     s = gen_order(P, F, E, grp);
     984         [ +  + ]:       7004 :   } while (!equalii(s, d1));
     985                 :       2646 :   av = avma;
     986                 :            :   do
     987                 :            :   {
     988                 :       5199 :     avma = av;
     989                 :       5199 :     Q = grp->rand(E);
     990                 :       5199 :     d = pairorder(E, grp->pow(E, P, dm), grp->pow(E, Q, dm), m, F);
     991         [ +  + ]:       5199 :   } while (!equalii(d, d2));
     992                 :       2646 :   return gerepilecopy(ltop, mkvec2(P,Q));
     993                 :            : }

Generated by: LCOV version 1.9