1

Is there any technique to prove that x+1 is a generator of multiplicative group of finite field $ \mathbb F = \mathbb Z _{3}[x] / _ {x ^3 - x + 1} $ ?

What I know is that F consists of 27 elements like $ 1,2,x, x+1, x+2, 2x, ... , 2x^2 + 2x + 2$. I tried to calculate it "brute-force" way but it's way too much time consuming. Is there a fast way to do this?

I tried following way:

$(x+1)^1 mod (x^3 - x + 1 )= x +1 $

$(x+1)^2 mod (x^3 - x + 1 ) = x^2 + 2x + 1$

$ (x+1)^3 mod (x^3 - x + 1 ) = x^3 + 3x^2 + 3x + 1 = x^3 + 1 = (x^3 -x + 1) +x = x $

Thanks for all answers.

Alon Amit
  • 15,591
apricot
  • 13
  • 1
    Here’s the technique to decide whether $g$ is a generator: first factor $27-1=26=2\cdot13$. Then check that neither $g^2$ nor $g^{13}$ is identity. If both fail, $g$ is a generator. In general, if $q=1$ is divisible by primes $p_1,\cdots,p_m$, then try $g^{(q-1)/p_j}$ for each of these primes. If never the identity, then $g$ is a generator. – Lubin May 17 '18 at 23:59

1 Answers1

2

One useful shortcut is this: if you already know that $\mathbb{F}$ is a field of $27$ elements, then you know that $\mathbb{F} \setminus\{0\}$ is a group under multiplication. This group has $26$ elements, so any element in this group has order $1,2,13$ or $26$. In other words, the only elements that are not generators are the identity element, elements of order $2$, and elements of order $13$.

You've already verified that $x+1$ is not of order $2$, since its square isn't $1$. The only thing left to do is show that $(x+1)^{13} \neq 1$. Expanding the binomial $(x+1)^{13}$ over a field of characteristic $3$ isn't so bad, since many of the coefficients $\binom{13}{k}$ vanish, including the most scary ones in the middle. Remembering that $x^3=x+1$ in our field, the computation can be done fairly quickly.

Alon Amit
  • 15,591