0
$\begingroup$

Problem: How do we find smallest $x$ such that $a^x \equiv b \bmod p$, where $p$ is a prime and $1 \le b,a \le p$ and $a$, $b$, and $p$ are given and fixed. If there is no such $x$, how do we check it ?

Brute force approach is to iterate over all $x$ starting from $1$ up till when $a^x\equiv 1 \bmod p$ and return the smallest such $x$ if exists.

Is there some closed formula to solve these kinds of equations ?

$\endgroup$
6
  • 4
    $\begingroup$ If there were a closed formula, a lot of cryptographers would be very upset. $\endgroup$
    – Sal
    Dec 14 '14 at 7:38
  • $\begingroup$ Are a, b, and p all given, or are we free to choose one or more of them? If they are given, I think a^x = 1 mod p should be a^x = b mod p? $\endgroup$ Dec 14 '14 at 7:47
  • 2
    $\begingroup$ As already commented by Sal any closed formula would cause the collapse of lot of encryption scheme that rests on the computational difficulty of the "Discrete Logarithm Problem" $\endgroup$ Dec 14 '14 at 8:06
  • $\begingroup$ @2012rcampion no it's correct. They are suggesting an algorithm for finding the smallest positive integer $x$ such that $a^x \equiv b\mod p$. To do this, they check all values of $x$ from 1 onwards, until they they find such an $x$. However the values of $a^x$ modulo $p$ repeat after $a^x$ is congruent to 1 modulo $p$, so if no solution is found before then, there are none. $\endgroup$ Dec 14 '14 at 8:07
  • $\begingroup$ @PVa, not if the closed formula was computationally infeasible. $\endgroup$ Dec 14 '14 at 12:03
1
$\begingroup$

There is an explicit formula for the discrete logarithm:

$$x=\log_a b=\sum\limits_{i=1}^{p-2} \frac{b^i}{1-a^{i}} \mod{p}.$$

See, the thesis , Theorem 3.2

$\endgroup$
3
  • $\begingroup$ Proof? Citation? $\endgroup$ Dec 14 '14 at 9:35
  • $\begingroup$ I added a link, but it is a well known result. $\endgroup$
    – Leox
    Dec 14 '14 at 9:57
  • $\begingroup$ $7^3 \text{ mod } 11 = 2<> \sum_{i=1}^{11-2} \frac{2^i}{1-7^{i}} \text{ mod } 11 = 10,55$ ??? $\endgroup$ Aug 4 '17 at 7:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.