\\Pohlig-Hellman algorithm for discrete logs assuming that
\\p-1 factors as a product of *distinct* primes. We leave as
\\exercise to extend to the general case. Call as dlog(p,g,h).
\\Input is assumed to be a prime p, a primitive root g and
\\an h. The output is x satisfying h=g^x mod p
\\by Felipe Voloch



{
fo(p,q,g,h,s)=s=-1;until(Mod(g,p)^(s*(p-1)/q)==Mod(h,p)^((p-1)/q),s=s+1);s
}
{
dlog(p,g,h,a,v)=a=Mod(fo(p,2,g,h),2);v=factor(p-1)[,1]~;
for(j=2,length(v),a=chinese(a,Mod(fo(p,v[j],g,h),v[j])));lift(a)
}