0
$\begingroup$

On a previous Cryptography exam I'm working through, there is the following problem:

Given $$f(x) = x^{134}+x^{127}+x^{7}+1$$ and the field $\mathbb{F}_{2^{n}}$ where $n=1463$, how many roots does the polynomial have? The polynomial has the form $f(x) = (x^{7}+1)(x^{127}+1)$, this is clear. It's also clear that the order of the field is $2^{1463}-1$. At this point I was unsure how to continue, so I peaked in the solution from that year's exam, and I was very confused by their arguments. This is how they solved it:

The order of the multiplicative group is $2^{1463}-1$, and $2^{1463}-1 \equiv 3 \bmod{7}$, and hence $x^{7}+1$ has only the one root, $1$. I've tried working out why this must be the case, but can't do it. Would be glad if someone could explain. Furthermore, $2^{1463} \equiv 1 \bmod{127}$, so $127$ divides the order of the group, so there are $127$ solutions in the field to the full polynomial when the zeros are counted without multiplicity, and $128$ when counted with multiplicity.

I would be very glad if someone could try to explain the reasoning presented in the solution.

$\endgroup$
3
  • $\begingroup$ "I'm assuming they meant field": the order of the multiplicative group $\mathbb{F}_q^{\times}$ is $2^{1463}-1$. $\endgroup$ Dec 3, 2015 at 9:45
  • $\begingroup$ @DietrichBurde Yes of course. I'm so used to my crypto professor using the name field for this, and in the solution they used both name group and field, which through me off. $\endgroup$
    – Auclair
    Dec 3, 2015 at 9:53
  • $\begingroup$ Every field $F$ involves two groups naturally. First, there is the additive group $(F,+,0)$ and then there is the multiplicative group ($F^\times, \cdot, 1)$. If the field $F$ is finite of order $n$, then the order of the group $(F^\times, \cdot, 1)$ is $n-1$. But $F^\times$ is usually not a field. $\endgroup$
    – user44400
    Dec 3, 2015 at 9:56

1 Answer 1

1
$\begingroup$

Cauchy's theorem states that if a prime $p$ divides the order of a group, then that group has an element of order $p$. In fact, this goes both ways, since an element of order $p$ generates a subgroup of order $p$, and the order of the subgroup must divide the order of the group it is in.

$\mathbb{F}_{2^n}$ is a group under multiplication. $2^{1463}-1 \equiv 3 \bmod{7}$ implies that $7$ does not divide the order of the group, and therefore there is no element $g \in \mathbb{F}_{2^n}$ such that $g^7 = 1$ except for $g=1$.

If there were nontrivial elements satisfying this, then taking the additive inverse $-g$, we find that this is a root of $x^7+1$, since $(-g)^7 + 1 = (-1)^7g^7+1 = (-1)(1) + 1 = 0$.

Because $2^{1463} \equiv 1 \bmod{127}$, $127$ divides the order of $\mathbb{F}_{2^n}$, and therefore since $127$ is also prime, there exists an element of order $127$. If we look at the subgroup generated by this element, we will find that actually every element of this subgroup has order $127$, so any of these satisfies the equation $g^{127} = 1$. Therefore, if we take $-g$, $(-g)^{127}+1 = 0$ as above, and we have at least $127$ solutions to the polynomial $x^{127}+1$.

I say "at least", because this doesn't actually prove that there are exactly $127$ elements of order $127$. It is not clear to me why there could not be more.

$\endgroup$
2
  • $\begingroup$ Thanks a lot! I'll more thoroughly look through your answer in a bit, I've moved on to different problem sets. But skimming through your answer, it seems to explain exactly what I didn't quite get. $\endgroup$
    – Auclair
    Dec 3, 2015 at 13:26
  • $\begingroup$ No problem, glad it helped. $\endgroup$
    – mathochist
    Dec 3, 2015 at 13:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .