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]?
Primitivt polynom (TMA4160 Krypto)
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
http://projecteuler.net/ | fysmat
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$
EDIT: Så det du må sjekke er at $gcd(2^{248}-1,17)> 1$