Thus spake Mike Perry ([EMAIL PROTECTED]): > Thus spake James Muir ([EMAIL PROTECTED]): > > > >Problem is: (g^X)^k = g for some given k. Find X equivalent to 1/k. > > > > > >Rewrite as (g^k)^X = g > > > > > >Seems like you need to take the Discrete Log of both sides to get your > > >X=1/k value. This is hard. > > > > Since we are working modulo p and we know that g is a generator of ZZ_p > > its order is p-1. So, to find X above you just need to solve: > > > > k*X == 1 (mod p-1) > > > > This can be done efficiently using the extended Euclidean Algorithm > > (provided that gcd(k,p-1)=1). > > Doh! You're right. The kittens are saved! (For now)
Oh wait, heh, this is an extra modular exponentiation hidden in the f^(b/k) step then. The kittens have been put in jeopardy for nothing! ;) -- Mike Perry Mad Computer Scientist fscked.org evil labs
