Primitivt polynom (TMA4160 Krypto)

[Gommle]

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

Gitt et primitivt polynom [tex]f(x)[/tex] over [tex]\mathbb F_2[/tex] av grad 248.

a) Er [tex]g(x) = x^{17}[/tex] et primitivt element? Hvorfor?

b) Er [tex]h(x) = x^{23}[/tex] et primitivt element? Hvorfor?

---

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

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

Men gir det i det hele tatt mening å finne [tex]\gcd(2^{248}-1, x^{17})[/tex]?

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