Removing 1 modular exponentiation

[Mike Perry]

Thus spake Mike Perry (mikepery at fscked.org):

> Thus spake James Muir (jamuir at scs.carleton.ca):
> 
> > >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