1
$\begingroup$

Question:

Determine $\operatorname{dlog}_x (x^2 + 1)$ in $\Bbb Z_5[x]/\langle\,x^3 + x + 1\,\rangle$

So I know the elements of $F = \Bbb Z_5[x]/\langle\,x^3 + x + 1\,\rangle $ are of the form $ax^2 + bx + c \bmod x^3 + x + 1$ ($a, b, c \in \Bbb Z_5$). I know how to calculate inverse of elements in F and all, but I dont know how to solve the discrete log problem. Any solution, partial or complete, would be great. Thanks...

$\endgroup$
1
  • $\begingroup$ See here how to do it. $\endgroup$ – Dietrich Burde Aug 29 '20 at 10:15
1
$\begingroup$
  • $x^1 = x$.

  • $x^2= x^2$.

  • $x^3 \equiv -x-1 \equiv 4x+4$. Here we use that $x^3 + x +1 \equiv 0$ in this field (assuming it is a field, haven't checked), and coefficients are mod 5.

  • $x^4 \equiv 4x^2 + 4x$.

  • $x^5 \equiv 4x^3 + 4x^2 \equiv 4(-x-1)+ 4x^2 \equiv 4x^2 + x +1$.

  • $x^6 \equiv 4x^3 + x^2 + x \equiv 4(-x-1) + x^2 +x \equiv x^2 + 2x + 1$.

  • $x^7 \equiv x^3 + 2x^2 + x \equiv (-x-1) + 2x^2 + x \equiv 2x^2 + 4$.

  • $x^8 \equiv 2x^3 + 4x \equiv 2(-x-1) + 4x = 2x+3$.

  • $x^9 \equiv 2x^2 + 3x$.

  • $x^{10} \equiv 2x^3 + 3x \equiv 2(-x-1) + 3x \equiv x + 3$.

  • $x^{11} \equiv x^2 + 3x$.

  • $x^{12} \equiv x^3 + 3x^2 \equiv -x-1 + 3x^2 = 3x^2 + 4x + 4$.

  • $x^{13} \equiv 3x^3 + 4x^2 + 4x \equiv 3(-x-1) + 4x^2 + 4x \equiv 4x^2 + x + 2$.

  • $x^{14} \equiv 4x^3 + x^2 + 2x \equiv 4(-x-1) + x^2 + 2x \equiv x^2 + 3x +1$.

etc. Continue until we get $x^n \equiv x^2+1$, and the answer is $n$.

Or use a computer algebra package, or write your own program...

$\endgroup$
6
  • 1
    $\begingroup$ Note that this is doable at all with such a small ($5^3 =125$) elements, but a computer program is better, though this is nice practice. You could use optimisations like baby step, giant-step etc. $\endgroup$ – Henno Brandsma Aug 29 '20 at 17:04
  • $\begingroup$ I see. I was just having trouble getting started. I understood how I can use shank's algorithm. Thank you! $\endgroup$ – Ankit Kumar Aug 30 '20 at 6:10
  • $\begingroup$ @AnkitKumar You're welcome. Shank's is about factorisation isn't it? Or do you mean another one? $\endgroup$ – Henno Brandsma Aug 30 '20 at 6:16
  • $\begingroup$ No, no. I just meant the baby step giant step algo only $\endgroup$ – Ankit Kumar Aug 30 '20 at 10:17
  • 1
    $\begingroup$ @AnkitKumar I see that that is also due to Shanks. $\endgroup$ – Henno Brandsma Aug 30 '20 at 10:34
0
$\begingroup$

One could also observe that we have $x^2+1=-1/x$ in ${\bf Z}_5[x]/(x^3+x+1)$. Therefore the dlog of $x^2+1$ is equal to the dlog of $-1$ minus the dlog of $x$. Since the constant coefficient of $x^3+x+1$ is equal to $1$, we have $x\cdot x^5\cdot x^{25} = -1$. It follows that the dlog of $x^2+1$ is $31-1=30$.

$\endgroup$
1

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.