bridge/class-master/depend/pari/src/basemath/bb_group.c
/*Generic Pollard rho discrete log algorithm*/
Generic Pollard rho discrete log algorithm
Generic Pollard rho discrete log algorithm
static GEN
gen_Pollard_log(GEN x, GEN g, GEN q, void *E, const struct bb_group *grp)
{
  pari_sp av=avma;
  GEN A, B, l, sqrt4q = sqrti(shifti(q,4));
  ulong i, h = 0, imax = itou_or_0(sqrt4q);
  if (!imax) imax = ULONG_MAX;
  do {
 rho_restart:
    A = B = mkvec3(x,gen_1,gen_0);
    i=0;
    do {
      if (i>imax)
      {
        h++;
        if (DEBUGLEVEL)
          pari_warn(warner,"changing Pollard rho hash seed to %ld",h);
        goto rho_restart;
      }
      A = iter_rho(x, g, q, A, h, E, grp);
      B = iter_rho(x, g, q, B, h, E, grp);
      B = iter_rho(x, g, q, B, h, E, grp);
      if (gc_needed(av,2))
      {
        if(DEBUGMEM>1) pari_warn(warnmem,"gen_Pollard_log");
        gerepileall(av, 2, &A, &B);
      }
      i++;
    } while (!grp->equal(gel(A,1), gel(B,1)));
    gel(A,2) = modii(gel(A,2), q);
    gel(B,2) = modii(gel(B,2), q);
    h++;
  } while (equalii(gel(A,2), gel(B,2)));
  l = Fp_div(Fp_sub(gel(B,3), gel(A,3),q),Fp_sub(gel(A,2), gel(B,2), q), q);
  return gerepileuptoint(av, l);
}
static GEN gen_Pollard_log ( GEN x , GEN g , GEN q , void * E , const struct bb_group * grp ) { pari_sp av = avma ; GEN A , B , l , sqrt4q = sqrti ( shifti ( q , 4 ) ) ; ulong i , h = 0 , imax = itou_or_0 ( sqrt4q ) ; if ( ! imax ) imax = ULONG_MAX ; do { rho_restart : A = B = mkvec3 ( x , gen_1 , gen_0 ) ; i = 0 ; do { if ( i > imax ) { h ++ ; if ( DEBUGLEVEL ) pari_warn ( warner , " " , h ) ; goto rho_restart ; } A = iter_rho ( x , g , q , A , h , E , grp ) ; B = iter_rho ( x , g , q , B , h , E , grp ) ; B = iter_rho ( x , g , q , B , h , E , grp ) ; if ( gc_needed ( av , 2 ) ) { if ( DEBUGMEM > 1 ) pari_warn ( warnmem , " " ) ; gerepileall ( av , 2 , & A , & B ) ; } i ++ ; } while ( ! grp -> equal ( gel ( A , 1 ) , gel ( B , 1 ) ) ) ; gel ( A , 2 ) = modii ( gel ( A , 2 ) , q ) ; gel ( B , 2 ) = modii ( gel ( B , 2 ) , q ) ; h ++ ; } while ( equalii ( gel ( A , 2 ) , gel ( B , 2 ) ) ) ; l = Fp_div ( Fp_sub ( gel ( B , 3 ) , gel ( A , 3 ) , q ) , Fp_sub ( gel ( A , 2 ) , gel ( B , 2 ) , q ) , q ) ; return gerepileuptoint ( av , l ) ; }
Generic Pollard rho discrete log algorithm
Generic Pollard rho discrete log algorithm