# Determine dlog in quotient rings of polynomial rings

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...

• See here how to do it. – Dietrich Burde Aug 29 '20 at 10:15

## 2 Answers

• $$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...

• 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. – Henno Brandsma Aug 29 '20 at 17:04
• I see. I was just having trouble getting started. I understood how I can use shank's algorithm. Thank you! – Ankit Kumar Aug 30 '20 at 6:10
• @AnkitKumar You're welcome. Shank's is about factorisation isn't it? Or do you mean another one? – Henno Brandsma Aug 30 '20 at 6:16
• No, no. I just meant the baby step giant step algo only – Ankit Kumar Aug 30 '20 at 10:17
• @AnkitKumar I see that that is also due to Shanks. – Henno Brandsma Aug 30 '20 at 10:34

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$$.