Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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...
$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...
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$.
