0
$\begingroup$

I need some clarification on the discrete logarithm problem...

When a friend and I were solving for the discrete logarithm problem of 9 = 2 ^ x mod 11, we got two different answers. My initial answer was 6 for x.

But his answer was 12 for x. So we decided to cross check our answers and indeed we were very correct.

So what does this mean? Does it mean that there can be more than one answer for a single discrete logarithm problem?

And does this also relate to the circumstance in a real discrete logarithm problem?

Improve this question
$\endgroup$
11
  • $\begingroup$ Can't you use some computer algebra to verify your solutions? Like Sagemath $\endgroup$
    – kelalaka
    Jan 23, 2021 at 0:08
  • $\begingroup$ $2^{12} \equiv 4 \pmod{11}$, hence (unless you typo'ed something) his answer was wrong $\endgroup$
    – poncho
    Jan 23, 2021 at 4:29
  • $\begingroup$ @poncho But it provided the same answer. Why isn't it correct? $\endgroup$
    – Dave Kent
    Jan 23, 2021 at 13:49
  • $\begingroup$ What do you mean 'it provided the same answer'? $x = 12$ is not a solution for $9 = 2^x \bmod 11$ $\endgroup$
    – poncho
    Jan 23, 2021 at 14:01
  • $\begingroup$ @DaveKent if you look at the answer, it is there $2^{10} = 2^{2} \bmod 11$ $\endgroup$
    – kelalaka
    Jan 23, 2021 at 14:09

1 Answer 1

Reset to default
1
$\begingroup$

The powers of $2$ modulo 11;

\begin{array}{c|rrrrrrrrrrrrrrrr} x& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10\\ \hline 2 ^x \bmod 11& 2& 4& 8& 5& 10& 9& 7& 3& 6& 1 \end{array}

We don't need the above 10 due to the Little Fermat Theorem; for a prime $p$ and $p\not| a$ then

$$a^{p-1} \equiv 1 \pmod p$$ We can use this theorem as

$$a^x \equiv a^{x \bmod{p-1}} \pmod p$$

Therefore your friend's power $12$ is equal to $2$; $12 \equiv 2 \pmod{10}$. In power;

$$ 2^{12} = 2^{12 \bmod{10}} = 2^2 = 4 \bmod 11.$$

A little theory;

The non-zero elements of modulus $11$ form a cyclic multiplicative group. The order of the group is given by $\varphi(p) = p-1$ where $\varphi$ is the Euler's totient function, so it has order $10$.

By the Lagrange theorem, the order of the subgroups must divide the order of the group. The converse, in general, is not true, that is for a divisor of the order of the group, there may not be a subgroup.

$2$ is a multiplicative generator, $\langle 2 \rangle = \mathbb{Z}_{11}^*$ and we can see this in the above table. Besides, $3$ is not a generator, since $\langle 3 \rangle = \{1,3,4,5,9\}$, with $1=3^5,3=3^1,4 = 3^4,5 = 3^3,9 =3^3$. As we can see, the order of $3$ is $ord(3)=5 | 10$.

What about order 2? It is generated by $\langle 10 \rangle = \{1,10\}$. The reason is $10 = -1 \bmod 11$

Note that for a prime $p$ forms a field $\mathbb{F}_{p}$ (also written as $GF(P)$) with integer addition and multiplication.

Improve this answer
$\endgroup$
3
  • $\begingroup$ So this question is slightly unrelated but when finding x using the discrete logarithm problem, which is required or better; using the uncompressed public key or using the compressed public key? $\endgroup$
    – Dave Kent
    Jan 23, 2021 at 1:37
  • $\begingroup$ @DaveKent compression is highly unrelated. In ECC, if $P=(x,y)$ is a point then $-P=(x,-y)$ is also a point. If you remove the knowledge of $y$ or $-y$ and only provide the $x$ then one can solve the curve equation to find these two solutions. To uniquely determine one bit is enough. This is the compression technique. For DLog maybe you should look at this as a tutorial. $\endgroup$
    – kelalaka
    Jan 23, 2021 at 9:10
  • $\begingroup$ So this means when imputing my values to solve a discrete logarithm problem using the uncompressed public key or the compressed public key doesn't matter. is it? $\endgroup$
    – Dave Kent
    Jan 26, 2021 at 20:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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