How to apply inverse modulo on (g^a) mod p?

Question

How can I find 'a' when

A = (g^a) mod p.

A, g( primitive root) and p (prime number) are known? Although practically such a method would be too time consuming, can we find a theoretical explanation to find a?

Answer 1

The short answer to your question is no, and that's the mathematical basis of the Diffie-Hellman key exchange (https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange) encryption algorithm. If the numbers you choose are sufficiently small then you can write a computer program to do this by brute force - not an elegant mathematical solution.