bridge/class-master/depend/pari/src/basemath/bb_group.c
/* grp->easylog() is an optional trapdoor function that catch easy logarithms*/
/* Generic Pohlig-Hellman discrete logarithm*/
/* smallest integer n such that g^n=a. Assume g has order ord */
grp->easylog() is an optional trapdoor function that catch easy logarithms
Generic Pohlig-Hellman discrete logarithm
smallest integer n such that g^n=a. Assume g has order ord
grp - > easylog () is an optional trapdoor function that catch easy logarithms Generic Pohlig - Hellman discrete logarithm smallest integer n such that g^n = a . Assume g has order ord
GEN
gen_PH_log(GEN a, GEN g, GEN ord, void *E, const struct bb_group *grp)
{
  pari_sp av = avma;
  GEN v,t0,a0,b,q,g_q,n_q,ginv0,qj,ginv;
  GEN fa, ex;
  long e,i,j,l;
  if (grp->equal(g, a)) 
    return grp->equal1(g)? gen_0: gen_1;
  if (grp->easylog)
  {
    GEN e = grp->easylog(E, a, g, ord);
    if (e) return e;
  }
  v = get_arith_ZZM(ord);
  ord= gel(v,1);
  fa = gel(v,2);
  ex = gel(fa,2);
  fa = gel(fa,1); l = lg(fa);
  ginv = grp->pow(E,g,gen_m1);
  v = cgetg(l, t_VEC);
  for (i=1; i<l; i++)
  {
    q = gel(fa,i);
    e = itos(gel(ex,i));
    if (DEBUGLEVEL>5)
      err_printf("Pohlig-Hellman: DL mod %Ps^%ld\n",q,e);
    qj = new_chunk(e+1);
    gel(qj,0) = gen_1;
    gel(qj,1) = q;
    for (j=2; j<=e; j++) gel(qj,j) = mulii(gel(qj,j-1), q);
    t0 = diviiexact(ord, gel(qj,e));
    a0 = grp->pow(E, a, t0);
    ginv0 = grp->pow(E, ginv, t0); 
    if (grp->equal1(ginv0))
    {
      gel(v,i) = mkintmod(gen_0, gen_1);
      continue;
    }
    do { g_q = grp->pow(E,g, mulii(t0, gel(qj,--e))); 
    } while (grp->equal1(g_q));
    n_q = gen_0;
    for (j=0;; j++)
    { 
      b = grp->pow(E,a0, gel(qj,e-j));
      if (j == 0 && !grp->equal1(grp->pow(E,b,q))) {
        avma = av; return cgetg(1, t_VEC);
      }
      b = gen_plog(b, g_q, q, E, grp);
      if (typ(b) != t_INT) { avma = av; return cgetg(1, t_VEC); }
      n_q = addii(n_q, mulii(b, gel(qj,j)));
      if (j == e) break;
      a0 = grp->mul(E,a0, grp->pow(E,ginv0, b));
      ginv0 = grp->pow(E,ginv0, q);
    }
    gel(v,i) = mkintmod(n_q, gel(qj,e+1));
  }
  return gerepileuptoint(av, lift(chinese1_coprime_Z(v)));
}
GEN gen_PH_log ( GEN a , GEN g , GEN ord , void * E , const struct bb_group * grp ) { pari_sp av = avma ; GEN v , t0 , a0 , b , q , g_q , n_q , ginv0 , qj , ginv ; GEN fa , ex ; long e , i , j , l ; if ( grp -> equal ( g , a ) ) return grp -> equal1 ( g ) ? gen_0 : gen_1 ; if ( grp -> easylog ) { GEN e = grp -> easylog ( E , a , g , ord ) ; if ( e ) return e ; } v = get_arith_ZZM ( ord ) ; ord = gel ( v , 1 ) ; fa = gel ( v , 2 ) ; ex = gel ( fa , 2 ) ; fa = gel ( fa , 1 ) ; l = lg ( fa ) ; ginv = grp -> pow ( E , g , gen_m1 ) ; v = cgetg ( l , t_VEC ) ; for ( i = 1 ; i < l ; i ++ ) { q = gel ( fa , i ) ; e = itos ( gel ( ex , i ) ) ; if ( DEBUGLEVEL > 5 ) err_printf ( " \n " , q , e ) ; qj = new_chunk ( e + 1 ) ; gel ( qj , 0 ) = gen_1 ; gel ( qj , 1 ) = q ; for ( j = 2 ; j <= e ; j ++ ) gel ( qj , j ) = mulii ( gel ( qj , j - 1 ) , q ) ; t0 = diviiexact ( ord , gel ( qj , e ) ) ; a0 = grp -> pow ( E , a , t0 ) ; ginv0 = grp -> pow ( E , ginv , t0 ) ; if ( grp -> equal1 ( ginv0 ) ) { gel ( v , i ) = mkintmod ( gen_0 , gen_1 ) ; continue ; } do { g_q = grp -> pow ( E , g , mulii ( t0 , gel ( qj , -- e ) ) ) ; } while ( grp -> equal1 ( g_q ) ) ; n_q = gen_0 ; for ( j = 0 ; ; j ++ ) { b = grp -> pow ( E , a0 , gel ( qj , e - j ) ) ; if ( j == 0 && ! grp -> equal1 ( grp -> pow ( E , b , q ) ) ) { avma = av ; return cgetg ( 1 , t_VEC ) ; } b = gen_plog ( b , g_q , q , E , grp ) ; if ( typ ( b ) != t_INT ) { avma = av ; return cgetg ( 1 , t_VEC ) ; } n_q = addii ( n_q , mulii ( b , gel ( qj , j ) ) ) ; if ( j == e ) break ; a0 = grp -> mul ( E , a0 , grp -> pow ( E , ginv0 , b ) ) ; ginv0 = grp -> pow ( E , ginv0 , q ) ; } gel ( v , i ) = mkintmod ( n_q , gel ( qj , e + 1 ) ) ; } return gerepileuptoint ( av , lift ( chinese1_coprime_Z ( v ) ) ) ; }
grp->easylog() is an optional trapdoor function that catch easy logarithms
Generic Pohlig-Hellman discrete logarithm
smallest integer n such that g^n=a.
grp - > easylog () is an optional trapdoor function that catch easy logarithms Generic Pohlig - Hellman discrete logarithm smallest integer n such that g^n = a .
/* frequent special case */ /* order q^e */ /* order q */ /* n_q = sum_{i<j} b_i q^i */ /* early abort: cheap and very effective */