Confused about discrete logarithm question

66 Views Asked by At

For purposes of explaining the notation for those unfamiliar, if we fix a prime $q$, as well as $a,b$ nonzero integers $\mod{q}$, $L_a(b) = x$ is the solution to the equation $b = a^x \mod{p}$

We are working with $p = 211$. Suppose we want to find $L_2(5)$. Also, suppose we know that $L_2(25) = 54$.

My thinking was along the lines of "well I know that $5^2 = 2^{54} \mod211$ so I guess $5 = 2^27 \mod211$", so I said that $L_2{5}$ could be any number that is congruent to $27 \mod211$, but the solution that appeared on the quiz was that it is actually congruent to any number that is congruent to $27 \mod105$. I am confused as to why. I see that $105 = \frac{211 - 1}{2}$ but I don't see why my operation of squaring both sides should change the modulus. Thanks for any help in resolving my confusion.

1

There are 1 best solutions below

0
On BEST ANSWER

Recall that $2^{210}\equiv 1\pmod{211}$. Indeed, since $2$ is a primitive root of $211$, the number $210$ is the least positive integer $w$ such that $2^w\equiv 1\pmod{n}$.

Let $L_2(5)=b$. So $2^b\equiv 5\pmod{211}$ and therefore $2^{2b}\equiv 2^{54}\pmod{211}$. This is true if and only if $2b\equiv 54\pmod{210}$. This last congruence is equivalent to $b\equiv 27\pmod{105}$.

So $L_2(5)$ must be congruent to $27$ modulo $105$. But there are two numbers between $0$ and $209$ that are congruent to $27$ modulo $105$, namely $27$ and $132$.

Only one of them can be the index of $5$. It turns out that the index of $5$ is any number that is congruent to $132$ modulo $210$. The number $27$ is "the" index of the other square root of $25$, which we can call $-5$ or $206$.

To reiterate, the answer given on the quiz, as reported, is not correct. The index of $5$ is not any number congruent to $27$ modulo $105$. For example, it is not the case that $2^{27}\equiv 5\pmod{211}$.