Removing 1 modular exponentiation

Mike Perry mikepery at
Mon Feb 19 23:30:17 UTC 2007

Thus spake James Muir (jamuir at

> >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)

Mike Perry
Mad Computer Scientist evil labs

More information about the tor-talk mailing list