Is there a way to efficiently discover or choose the integers $b$, $d$ for the congruence relationship below where $p$ is a large prime number? Is there a name for this relationship?
$$ a^{b} = c^{d} \pmod p $$
$\begingroup$
$\endgroup$
13
-
1$\begingroup$ I think what you are asking is the discrete logarithm problem, which is one of the foundations of the modern cryptography. $\endgroup$– Alex DegtyarevCommented Apr 20, 2014 at 8:32
-
$\begingroup$ $b=d=p-1$ I suppose. Sometimes $(p-1)/2$. $\endgroup$– joroCommented Apr 20, 2014 at 8:38
-
$\begingroup$ You could start with b and d both p-1, and try divisors of p-1 after that. $\endgroup$– The Masked AvengerCommented Apr 20, 2014 at 8:40
-
$\begingroup$ One further restriction -- a^b (mod p) and c^d (mod p) should be between 2 and (p-1) $\endgroup$– riseupCommented Apr 20, 2014 at 8:45
-
$\begingroup$ @AlexDegtyarev -- I am wondering this myself, is there a way to show that this is the case? I can think of one way it is not, and that is when the ratio of log(c) to log(a) is a rational number -- then this is trivial to solve. What about when log(c) to log(a) is irrational? $\endgroup$– riseupCommented Apr 20, 2014 at 8:47
|
Show 8 more comments
1 Answer
$\begingroup$
$\endgroup$
As was mentioned in the comments, this is essentially the discrete logarithm problem. Since $a^{p-1}=c^{p-1}=1$, $b,d$ are naturally thought of best as modulo $p-1$. Now for any solution, we can factor $d= d'\cdot gcd(d,p-1)$. Then $d'$ is invertible modulo $p-1$, so we can find some $e$ for which $d'e = 1$ modulo $p-1$. Setting $c' = c^{gcd(d,p-1)}$, taking the $e$-th power of the original equation gives you $$ a^{be} = c' $$ mod $p$. Now finding $be$ here is exactly the discrete logarithm problem.
You can get your original equation back by powering with $d'$ again (since $d'e=1$ mod $p-1$), so this describes all solutions. More precisely, let $k$ run through divisors $k | p-1$, let $x$ run through all solutions of the discrete logarithm problem $a^x = c^k$, and $d'$ through all things invertible mod $p-1$, then $(c,d) = (d'x, d'k)$ describes all solutions mod $p-1$.
As was also mentioned in the comments, this discrete logarithm problem is believed to be not efficiently solvable, and a lot of modern cryptography depends on that.
answered Apr 20, 2014 at 18:25