2

I have a seemingly trivial problem with description:

Find all discrete logarithms of base 2 of all non-zero elements in $Z_{11}$ field.

I'm basing my learning on the notes I managed to grab from other groups and for that problem, there's a solution with only 5 $dlog$'s calculated, namely $dlog_2 1, dlog_2 2, dlog_2 10, dlog_2 7, dlog_2 3$. What I don't get is why are all the other elements of $Z_{11}$ ignored? 2 is a generator of the field so for different values of $i$ you could derive such $2^i$ that it yields numbers from $1$ to $10$. Why don't we calculate the $dlog$'s of all such numbers but only half of them? Or is there mistake in the answer?

quid
  • 42,135
Straightfw
  • 1,558
  • Without seeing whatever it is you are looking at, it is impossible to tell why someone asked for all the logs and only calculated half of them. – Gerry Myerson Apr 23 '14 at 13:08

1 Answers1

4

If $x\cdot y \equiv 1 \mod p$, then $$ \underbrace{\textrm{dlog}_2 x}_{=u} + \underbrace{\textrm{dlog}_2 y}_{=v} \equiv 0 \mod (p-1) $$ because if $2^u \equiv x, 2^v \equiv y$ then $x\cdot y \equiv 2^{u+v} \equiv 1$ if $u + v \mid 10$ (this follows from fermat's little theorem). Over $\mathbb{Z}_{11}$ you have $$\begin{eqnarray} 1 &\cdot& 1 &\equiv& 1 \\ 2 &\cdot& 6 &\equiv& 1 \\ 3 &\cdot& 4 &\equiv& 1 \\ 5 &\cdot& 9 &\equiv& 1 \\ 7 &\cdot& 8 &\equiv& 1 \\ 10 &\cdot& 10 &\equiv& 1 \end{eqnarray}$$ meaning that the discrete $2$-logarithmns of $1,2,3,5,7,10$ suffice to easily express the others. Why your list is missing $\textrm{dlog}_2 5$, I don't know.

fgp
  • 21,050
  • After talking with the notes owner, it turns out they were just given a few examples instead of writing out all the possibilities. Still, I'm accepting this answer because it gives a really interesting insight on how this (or very similar) writing can actually make sense. Thank you :) – Straightfw Apr 23 '14 at 17:36