Primitivt polynom (TMA4160 Krypto)

[Gommle]

Dette er en eksamensoppgave med fasit, som jeg ikke skjønner så mye av.

Gitt et primitivt polynom $f(x)$ over ${\mathbb{F}}_2$ av grad 248.

a) Er $g(x)=x^{17}$ et primitivt element? Hvorfor?

b) Er $h(x)=x^{23}$ et primitivt element? Hvorfor?

---

Jeg tenker at elementet må være coprime til ordenen til gruppen, som i dette tilfellet er $2^{248}-1$.

Altså $gcd(2^{248}-1,x^{17})=1\text{iff}{x}^{17}$ er et primitivt element.

Men gir det i det hele tatt mening å finne $gcd(2^{248}-1,x^{17})$?

[Gustav]

La x være et primitivt element. Da er x en primitiv $(2^{248}-1)$-te enhetsrot. Siden 17 deler $2^{248}-1$ vil $x^{17}$ ikke være en primitiv $(2^{248}-1)$-te enhetsrot. Altså er $x^{17}$ ikke et primitivt element.

EDIT: Så det du må sjekke er at $gcd(2^{248}-1,17)>1$