2
$\begingroup$

I am trying to find a primitive elements of $\mathbb{F}_5[X]/(X^2-2)$, so I was thinking about checking all the powers of an element in this field and see if they yield all the non-zero elements in this set, but since there are $5^2$ elements in this field, this seems a little tedious. Are there more efficient ways to do this?

$\endgroup$
3
$\begingroup$

Basically you are staring at $\Bbb{F}_5[\sqrt2]$. You hopefully know that $2$ is of (multiplicative) order $4$, so $\sqrt2$ is of order eight. How to find an element of order three? Well, let's recall from complex roots of unity that $$ \omega=\frac{-1+\sqrt{-3}}2 $$ is such a beast. But, we have the counterpart lying around here! Recall that in $\Bbb{F}_5$ we have $-3=2$, so $\sqrt2$ can serve in the role of $\sqrt{-3}$ well.

So in your field $$ \omega=\frac{-1+\sqrt2}2=2+3\sqrt2 $$ is of order three. Because $\gcd(3,8)=1$ the product $$ g=\omega\cdot\sqrt2=2\sqrt2+1 $$ will be of order $3\cdot8=24$.

$\endgroup$
  • $\begingroup$ Nice, I like this. Similiar to mine, but a little bit more smooth I think. $\endgroup$ – MooS Jun 10 '17 at 11:22
  • $\begingroup$ Thanks @MooS. Hopefully not unexpectedly the early upvote to your post was mine. $\endgroup$ – Jyrki Lahtonen Jun 10 '17 at 12:22
2
$\begingroup$

First, be careful: You are looking for a primitive element in $[\mathbb{F}_5[X]/(X^2−2)]^*$ (which has 24 elements). There is no general "easy" way to find primitive elements in finite fields, otherwise many kryptography applications would not work. But think about this: what are the possible values for $ ord(a) $ in $ \mathbb{F}_{25}^*$? After Lagranges theorem $ord(a)$ must be a divisor of 24, that means $ ord(a) \in \{2,3,4,6,8,12\} :=M$, if $a$ is not a primitive element. So you have to check $a^k =1$ for $k \in M $. If non of these cases are true, $a$ is primitive and $k=24=|\mathbb{F}_{25}^*|$ is the lowest exponent so that $a^k =1$ holds.

$\endgroup$
1
$\begingroup$

Since ${\Bbb F}_{25}^* \cong {\Bbb Z}_{24}$, it has $\phi(24) = 8$ primitive elements. The ones in ${\mathbb F}_5$ can't be it, which leaves $20$ candidates, so randomly picking candidates is not too bad.

To check if $\beta$ is a primitive element, you only have to check $\beta^k$ for $k \mid 24$, so you only need to do a computation for $k = 2, 3, 4, 6, 8, 12$ and if one of those is $1$, it's not a primitive element. Of course, you use, e.g., $\beta^3$ to compute $\beta^6$ to limit the number of computations you have to do, so that's not too bad either.

$\endgroup$
1
$\begingroup$

There is no need to follow the other suggestions and compute all these powers of randomly chosen candidates, which might end up in doing many computations if you are out of luck.

Let $\alpha$ be the residue class of $X$ in your field $K=\mathbb F_5[X]/(X^2-2)$. Note that $\alpha^2=2$ and $2$ has order $4$ in $K^*$, thus $\alpha$ has order $8$. So all you gotta do is finding a third root of $\alpha$, this will automatically be an element of the desired order $24$. This is not too hard, just solve the equation $$\alpha = (u+v\alpha)^3=u^3+3u^2v\alpha+3uv^2\alpha^2+\alpha^3=(u^3+uv^2) + (3u^2v+2)\alpha,$$ i.e. find $u,v \in \mathbb F_5$, such that $u^3+uv^2=0$ and $3u^2v+2=1 \Longleftrightarrow u^2v=-2$. There are three solutions of course and you only have to find one, so you better do it with trial and error, namely you see that $u=1,v=-2$ works.

Hence $1-2\alpha$ generates the group $K^*$.

$\endgroup$

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.