0

I am doing some cryptography programming, and I have to isolate a in the following formula in order to decode some cipher-messages. $${g^a\mod p}=21$$

I am pretty far from implementing the isolation, but I would like to understand how it is done. So if you have a solution, I would appreciate pointers to some material to look into

Edit

It should be noted that p is a prime and g is a primitive root modulo of p

I expect the solution to be done with trial and error, since I am trying to make a brute-force program to find a. p will be a prime between 7 and 23

Jonas Grønbek
  • 103
  • 4
  • 1
    Refer to discrete logarithm. wiki : https://en.wikipedia.org/wiki/Discrete_logarithm algorithm : https://cp-algorithms.com/algebra/discrete-log.html – dust05 May 22 '20 at 11:20
  • Welcome to MSE. Please use MathJax to format your posts on this site. – saulspatz May 22 '20 at 11:34
  • @saulspatz thanks for the tip! – Jonas Grønbek May 22 '20 at 11:38
  • 1
    Since $g$ is a primitive root we know there exists a unique number $a \in {1,2, \dots, p-1 }$ such that $g^a \equiv 21 \pmod p$. the set of all solutions will be $a+ k(p-1)$ where $k \in \mathbb{Z}$ since $g$ is a primitive root and $g^{a+k(p-1)} \equiv g^a(g^{p-1})^k \equiv g^a(1)^k \equiv g^a \pmod p$ (using fermat's little theorem). So one option is to check iteratively among the $p-1$ options – Aladin May 22 '20 at 11:50
  • @Aladin Would you agree to making a chat? I have some questions, you don't have to tag along until everything clicks – Jonas Grønbek May 22 '20 at 12:13
  • Ok. by the way my answer is correct only if $\gcd(p,21) = 1$. otherwise, there is no solution – Aladin May 22 '20 at 13:08

0 Answers0