[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: Removing 1 modular exponentiation



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

-James