Campi di Galois - INTRANET di Galois F2: elementi f0;1g, somma modulo 2 Campo di Galois Vm(F2) = F2m...

Campi di GaloisF2: elementi {0, 1}, somma modulo 2

Campo di Galois Vm(F2) = F2m

Elementi: vettori binari di lunghezza m,

Addizione: vettoriale su F2

Moltiplicazione:Vediamo vettori come polinomi binari di grado ≤ m acoefficienti su F2

(am−1, . . . , a0) ≡ a(x) = am−1xm−1 + . . . + a1x+ a0

Dati a,b ∈ Vm(F2)

a · b = c sse c(x) = a(x)b(x) mod p(x)

dove p(x) = pmxm + . . . + p0 = polinomio primitivo

. – p.1/39

(am−1, . . . , a0) ≡ a(x) = am−1xm−1 + . . . + a1x+ a0

Dati a,b ∈ Vm(F2)

. – p.1/39

(am−1, . . . , a0) ≡ a(x) = am−1xm−1 + . . . + a1x+ a0

Dati a,b ∈ Vm(F2)

. – p.1/39

Polinomi primitiviPolinomio irriducibile ≡ non divisibile per altro polinomioa coefficienti in F2

Polinomio irriducibile divide x2m−1 + 1

Polinomio primitivo= polinomio irriducibile che dividex2m−1 + 1, non xn + 1 per n < 2m − 1

Polinomi primitivi esistono e sono noti per ogni mm = 3 x3 + x+ 1m = 4 x4 + x+ 1m = 5 x5 + x2 + 1

. – p.2/39

Radice primitivap(x) = pmx

m + . . . + p1x+ p0 = polinomio primitivo

α= radice di p(x)

x2m−1+1 = q(x)p(x)⇒ α2m−1+1 = q(α)p(α) = 0⇒ α2m−1 = 1

Possibile provare che α0, . . . , α2m−2 sono tutti elementidi Vm(F2) tranne 0

. – p.3/39

α= radice di p(x)

x2m−1+1 = q(x)p(x)⇒ α2m−1+1 = q(α)p(α) = 0⇒ α2m−1 = 1

. – p.3/39

α= radice di p(x)

x2m−1+1 = q(x)p(x)⇒ α2m−1+1 = q(α)p(α) = 0⇒ α2m−1 = 1

. – p.3/39

Esempiom = 3, polinomio primitivo=x3 + x+ 1

α= radice primitiva, α3 + α + 1 = 0 ≡ α3 = α+ 1

αi polinomio (grado ≤ 2) vettore (a2, a1, a0)

α0 = 1 α0 001α1 α 010α2 α2 100α3 α + 1 011α4 α(α+ 1) = α2 + α 110α5 α(α2 + α) = α2 + α + 1 111α6 α(α2 + α + 1) = α2 + 1 101α7 α(α2 + 1) = 1

INVERSO: α−i = αn−i, n = 2m − 1

. – p.4/39

INVERSO: α−i = αn−i, n = 2m − 1

. – p.4/39

INVERSO: α−i = αn−i, n = 2m − 1. – p.4/39

Codici Reed-SolomonCodici di Hamming: H = [α0, . . . , αn−1]

Codice Reed–Solomon(n,t), n = 2m − 1

α0 . . . αn−1

α20 . . . α2

n−1...

......

α2t0 . . . α2t

con αi = αi, α = radice primitiva di Vm(F2)

Parole codice: C = (c0, . . . , cn−1), ci ∈ Vm(F2) t.c.

HCT = 0 ≡n−1∑

αijci = 0, j = 1, . . . , 2t

. – p.5/39

α0 . . . αn−1

α20 . . . α2

n−1...

......

α2t0 . . . α2t

HCT = 0 ≡n−1∑

αijci = 0, j = 1, . . . , 2t

. – p.5/39

α0 . . . αn−1

α20 . . . α2

n−1...

......

α2t0 . . . α2t

HCT = 0 ≡n−1∑

αijci = 0, j = 1, . . . , 2t

. – p.5/39

Codici Reed-SolomonCodificaC = (c0, . . . , cn−1) ≡ C(x) = cn−1x

n−1 + . . .+ c1x+ c0

Parole codice hanno radici α, . . . , α2t

C ∈ RS(n, t) ≡ HCT = 0

≡ ∑n−1i=0 α

ijci = 0, j = 1, . . . , 2t

≡ C(αj) = 0 j = 1, . . . , 2t

Parola codice sono i multipli di (x− α) . . . (x− α2t)C(x) = q(x)g(x)

g(x) = (x− α) . . . (x− α2t) =polinomio generatore delcodice

RS(n,t): tutti polinomi su Vm(F2) multipli di g(x)

. – p.6/39

n−1 + . . .+ c1x+ c0

C ∈ RS(n, t) ≡ HCT = 0

≡ ∑n−1i=0 α

ijci = 0, j = 1, . . . , 2t

≡ C(αj) = 0 j = 1, . . . , 2t

. – p.6/39

n−1 + . . .+ c1x+ c0

C ∈ RS(n, t) ≡ HCT = 0

≡ ∑n−1i=0 α

ijci = 0, j = 1, . . . , 2t

≡ C(αj) = 0 j = 1, . . . , 2t

. – p.6/39

n−1 + . . .+ c1x+ c0

C ∈ RS(n, t) ≡ HCT = 0

≡ ∑n−1i=0 α

ijci = 0, j = 1, . . . , 2t

≡ C(αj) = 0 j = 1, . . . , 2t

. – p.6/39

Distanza Minima RS(n,t): 2t + 1

d ≤ 2t+ 1g(x) ≡ parola codice grado 2t, g = (g0, . . . , g2t, 0, . . . , 0)⇒ wmin ≤ w(g) ≤ 2t+ 1

Quindi d = wmin ≤ 2t + 1

. – p.7/39

d ≥ 2t+ 1Ogni r ≤ 2t colonne di H sono linearmente indipendenti:

Consideriamo αi1 = γ1, . . . , αir = γr e sottomatrice di H

H ′ =

γ1 . . . γr

γ21 . . . γ2

γr1 . . . γrr

. – p.8/39

Risulta

Det(H ′) = (γ1 · · · γr)Det

1 . . . 1

γ1 . . . γr...

......

γr−11 . . . γr−1

= γ1 · · · γr∏

(γj − γi) 6= 0

Quindir ≤ 2t colonne di H sono linearmente indipendenti

⇒ ogni parola ha peso ≥ 2t+ 1 ⇒ d = wmin ≥ 2t+ 1

. – p.9/39

Codifica Sistematica RS(n,t)Simboli di informazione (a0, . . . , ak−1), ai ∈ F2m, k = n− 2t

CODIFICA

C(x) = x2ta(x) + b(x)

b(x) = resto⌊x2ta(x)g(x)

⌋, deg(b(x)) ≤ 2t− 1

C = (c0, . . . , cn−1) = (b0, . . . , b2t−1, a0, . . . , ak−1)

Nota Divisione polinomi VELOCE mediante circuiti

. – p.10/39

Codifica Sistematica RS(n,t)

Proprietá C(x) multiplo di g(x)

DIM. C(x) = x2ta(x) + b(x), con b(x) = resto⌊x2ta(x)g(x)

Divisione x2ta(x) per g(x): quoziente q(x), resto b(x)

C(x) = x2ta(x) + b(x)

= (q(x)g(x) + b(x)) + b(x)

= q(x)g(x)

. – p.11/39

Decodifica RS(n,t)Parola trasmessa C ≡ C(x) = c0 + . . . + cn−1x

Sequenza ricevuta R ≡ R(x) = r0 + . . . + rn−1xn−1

Errore in posizione i sse ri 6= ciSia ei = ri − ciQuindi

R = C + E

Vettore errore E ≡ E(x) = e0 + . . . + en−1xn−1

VOGLIAMO DETERMINARE E(x)

. – p.12/39

R = C + E

. – p.12/39

R = C + E

. – p.12/39

Decodifica RS(n,t)Assumiamo

γ errori in posizioni j1, . . . , jγ⇒ ej1 , . . . , ejγ 6= 0, altri ei = 0

⇒ E(x) = ej1xj1 + . . . + ejγx

Definiamoβ1 = αj1 , . . . , βγ = αjγ e E1 = ej1 , . . . , Eγ = ejγ

⇒ E(x) = E1xj1 + . . . + Eγx

. – p.13/39

Calcoliamo la sindrome S = (s1, . . . , s2t) = HRT

Risulta

si = (riga ima di H)R = (αi, . . . , αij , . . . , αi(n−1))(r0, . . . , rn−1)

= r0 + r1αi + . . . + rjα

ij + . . . + rn−1αi(n−1)

= R(αi)

. – p.14/39

Sindrome S = (s1, . . . , s2t) = HRT , si = R(αi), i = 1, . . . 2t

Essendo S = HRT = H(C + E)T = HCT + HET = HET

si = E(αi) = e0 + e1αi + . . . + en−1α

i(n−1)

= E1αij1 + . . . + Eγα

= E1βi1 + . . . + Eγβ

Ejβij

. – p.15/39

Calcolo della sindromesi = resto

⌊R(x)x+αi

⌋, i = 1, . . . 2t

DIM. Dividendo R(x) per x+ αi: quoziente qi(x) e resto biR(x) = qi(x)(x+ αi) + bi⇒ R(αi) = bi⇒ si = bi

. – p.16/39

Decodifica RS(n,t)Decodificare ≡

Trova posizioni degli errori (j1, . . . , jγ)

Trova valore degli errori (E1, . . . , Eγ)

. – p.17/39

Polinomio locatore degli erroriPolinomio locatore degli errori:σ(x) con radici β−1

1 , . . . , β−1γ

σ(x) = (1 + β1x) . . . (1 + βγx) = 1 + σ1x+ . . . + σγx

Vogliamo determinare σ1, . . . , σγ

Possiamo farlo a partire da s1, . . . , s2t

. – p.18/39

1 , . . . , β−1γ

σ(x) = (1 + β1x) . . . (1 + βγx) = 1 + σ1x+ . . . + σγx

. – p.18/39

1 , . . . , β−1γ

σ(x) = (1 + β1x) . . . (1 + βγx) = 1 + σ1x+ . . . + σγx

. – p.18/39

Poiché σ(β−1` ) = 0, ∀` = 1, . . . , γ

per ogni j ≤ 2t abbiamo

E`βj+γ` σ(β−1

E`βj+γ` (1 + σ1β

−1` + . . . + σγβ

−γ` )

E`βj+γ` + σ1

E`βj+γ−1` + . . . + σγ

E`βj`

= sj+γ + σ1sj+γ−1 + . . . + σγsj

. – p.19/39

Poiché σ(β−1` ) = 0, ∀` = 1, . . . , γ

per ogni j ≤ 2t abbiamo

E`βj+γ` σ(β−1

E`βj+γ` (1 + σ1β

−1` + . . . + σγβ

−γ` )

E`βj+γ` + σ1

E`βj+γ−1` + . . . + σγ

E`βj`

= sj+γ + σ1sj+γ−1 + . . . + σγsj

. – p.19/39

Cioé sγ+j = σ1sj+γ−1 + . . . + σγsj , per ogni j

sγ+1 = σ1sγ + . . . + σγs1

sγ+2 = σ1sγ+1 + . . . + σγs2

. . . . . .

s2γ = σ1s2γ−1 + . . . + σγsγ

. – p.20/39

sγ+1 = σ1sγ + . . . + σγs1

sγ+2 = σ1sγ+1 + . . . + σγs2

. . . . . .

s2γ = σ1s2γ−1 + . . . + σγsγ

. – p.20/39

sγ+1 = σ1sγ + . . . + σγs1

sγ+2 = σ1sγ+1 + . . . + σγs2

. . . . . .

s2γ = σ1s2γ−1 + . . . + σγsγ

. – p.20/39

In forma matriciale

σ1 . . . σγ

σ2 . . . σγ+1

. . . . . . . . .

σγ . . . σ2γ−1

σγ−1

σγ+1

TeoremaSe vi sono γ errori la matrice é invertibile;se vi sono < γ errori la matrice ha determinante nullo.

. – p.21/39

In forma matriciale

σ1 . . . σγ

σ2 . . . σγ+1

. . . . . . . . .

σγ . . . σ2γ−1

σγ−1

σγ+1

TeoremaSe vi sono γ errori la matrice é invertibile;se vi sono < γ errori la matrice ha determinante nullo.

. – p.21/39

Metodo (Peterson-Gorenstein–Ziegler)(1) Input: R(x)(2) Calcola s1, . . . , s2t

(3) Poni γ = t

(4) WHILE Det

σ1 . . . σγ

. . . . . . . . .

σγ . . . σ2γ−1

= 0 poni γ = γ − 1

σγ−1

σ1 . . . σγ

. . . . . . . . .

σγ . . . σ2γ−1

σγ+1

NOTA: Esistono metodi successivi piú efficienti

. – p.22/39

Metodo (Peterson-Gorenstein–Ziegler)(1) Input: R(x)(2) Calcola s1, . . . , s2t

(3) Poni γ = t

(4) WHILE Det

σ1 . . . σγ

. . . . . . . . .

σγ . . . σ2γ−1

= 0 poni γ = γ − 1

σγ−1

σ1 . . . σγ

. . . . . . . . .

σγ . . . σ2γ−1

σγ+1

NOTA: Esistono metodi successivi piú efficienti

. – p.22/39

DecodificaCalcola Sindrome relativa a R(x)

Calcola polinomio locatore errori σ(x)Esistono algoritmi efficienti per trovare polinomio(di grado minimo⇒ parola codice piú vicina ad R(x))σ(x) = (1 + β1x) . . . (1 + βγx) = 1 + σ1x+ . . . + σγx

Determina le posizioni degli erroriValuta σ(x) in 1, α, α2, . . . per trovare radici β−1

β−1i = αji ⇒ errore in posizione βi = αn−ji

Determina il valore degli errori

. – p.23/39

Polinomio valutatore degli erroriPolinomio valutatore degli errori

ω(x) = S(x)σ(x) mod x2t

Lemma Per ogni ` = 1, . . . , γ

E` =ω(β−1

β`∏i6=`(1 + βiβ

−1` )

. – p.24/39

Polinomio valutatore degli erroriPolinomio valutatore degli errori

ω(x) = S(x)σ(x) mod x2t

Lemma Per ogni ` = 1, . . . , γ

E` =ω(β−1

β`∏i6=`(1 + βiβ

−1` )

. – p.24/39

Polinomio valutatore degli erroriDIM.

S(x) =2t∑

sixi−1 =

xi−1n−1∑

ejαij

=n−1∑

α(i−1)jxi−1

=n−1∑

ejαj 1− (αjx)2t

1− αjx

S(x) mod x2t =∑n−1

j=0ejα

1−αjx =∑γ

j=1Ejβj

1−βjx

. – p.25/39

Polinomio valutatore degli erroriDIM.

S(x) =2t∑

sixi−1 =

xi−1n−1∑

ejαij

=n−1∑

α(i−1)jxi−1

=n−1∑

ejαj 1− (αjx)2t

1− αjx

S(x) mod x2t =∑n−1

j=0ejα

1−αjx =∑γ

j=1Ejβj

1−βjx

. – p.25/39

Polinomio valutatore degli errori

ω(x) = S(x)σ(x) mod x2t =

Ejβj1− βjx

(1 + βix)

Ejβj∏

i6=j(1 + βix)

ω(β−1l ) = E`β`

∏i6=`(1 + βiβ

−1` )

E` =ω(β−1

β`Qi6=`(1+βiβ

−1` )

. – p.26/39

Ejβj1− βjx

(1 + βix)

Ejβj∏

i6=j(1 + βix)

ω(β−1l ) = E`β`

∏i6=`(1 + βiβ

−1` )

E` =ω(β−1

β`Qi6=`(1+βiβ

−1` )

. – p.26/39

Ejβj1− βjx

(1 + βix)

Ejβj∏

i6=j(1 + βix)

ω(β−1l ) = E`β`

∏i6=`(1 + βiβ

−1` )

E` =ω(β−1

β`Qi6=`(1+βiβ

−1` )

. – p.26/39

Algoritmo di EuclideServirá per calcolare i polinomi σ(x) ed ω(x)

Siano a(x) e b(x) polinomi su campo F , con deg(a) ≥ deg(b)Algoritmo di Euclide trove massimo comun divisore (mcd)d(x) di a(x) e b(x) e produce equazione

s(x)a(x) + t(x)b(x) = d(x)

. – p.27/39

Algoritmo di EuclideAlgoritmo iterativo che produce sequenza polinomi:si, ti, ri, qi con

s−1(x) = 1 t−1(x) = 0 r−1(x) = a(x)

s0(x) = 0 t0(x) = 1 r0(x) = b(x)

Per i ≥ 1, qi(x) e ri(x) rappresentano quoziente e restodella divisione di ri−2(x) per ri−1(x):ri−2(x) = qi(x)ri−1(x) + ri(x) deg(ri) < deg(ri−1)Inoltresi(x) = si−2(x)− qi(x)si−1(x)ti(x) = ti−2(x)− qi(x)ti−1(x)

. – p.28/39

Algoritmo di EuclideAlgoritmo iterativo che produce sequenza polinomi:si, ti, ri, qi con

s−1(x) = 1 t−1(x) = 0 r−1(x) = a(x)

s0(x) = 0 t0(x) = 1 r0(x) = b(x)

Per i ≥ 1, qi(x) e ri(x) rappresentano quoziente e restodella divisione di ri−2(x) per ri−1(x):ri−2(x) = qi(x)ri−1(x) + ri(x) deg(ri) < deg(ri−1)Inoltresi(x) = si−2(x)− qi(x)si−1(x)ti(x) = ti−2(x)− qi(x)ti−1(x)

. – p.28/39

Algoritmo di EuclideResti grado decrescente⇒ esiste ultimo resto di grado > 0,sia rn(x).Si dimostra chern(x) = d(x) = mcd(a, b)sn(x)a(x) + tn(x)b(x) = rn(x)

. – p.29/39

Proprietá Alg. EuclideA. tiri−1 − ti−1ri = (−1)ia i = 0, . . . , n+ 1

B. siri−1 − si−1ri = (−1)ib i = 0, . . . , n+ 1

C. siti−1 − si−1ti = (−1)i+1 i = 0, . . . , n + 1

D. sia− tib = ri i = −1, . . . , n+ 1

E. deg(si) + deg(ri−1) = deg(b) i = 1, . . . , n+ 1

F. deg(ti) + deg(ri−1) = deg(a) i = 0, . . . , n+ 1

. – p.30/39

Algoritmo di EuclideLemma. Dati interi non negativi µ e ν conν > deg(mcd(a, b)) e µ+ ν = deg(a)− 1, esiste unico j t.c.

deg(tj) ≤ µ deg(rj) ≤ ν

DIM. Sia j t.c.

deg(rj−1) ≥ ν + 1, deg(rj) ≤ ν

Dalla proprietá F (deg(ti) + deg(ri−1) = deg(a)) si ha

deg(tj) ≤ µ deg(tj+1) ≥ µ+ 1

Quindi l’indice j esiste ed é unico.

. – p.31/39

Algoritmo di EuclideLemma. Dati interi non negativi µ e ν conν > deg(mcd(a, b)) e µ+ ν = deg(a)− 1, esiste unico j t.c.

deg(tj) ≤ µ deg(rj) ≤ ν

DIM. Sia j t.c.

deg(rj−1) ≥ ν + 1, deg(rj) ≤ ν

Dalla proprietá F (deg(ti) + deg(ri−1) = deg(a)) si ha

deg(tj) ≤ µ deg(tj+1) ≥ µ+ 1

Quindi l’indice j esiste ed é unico.

. – p.31/39

Algoritmo di EuclideTeorema. Siano t(x) e r(x) due polinomi t.c.

t(x)b(x) ≡ r(x) mod a(x) (1)

deg(t) + deg(r) < deg(a) (2)

Esistono unico indice j, 0 ≤ j ≤ n, e polinomio λ(x) t.c.

t(x) = λ(x)tj(x), r(x) = λ(x)rj(x) (3)

. – p.32/39

Algoritmo di EuclideDIM. (1)⇒ t(x)b(x)− q(x)a(x) = r(x) ⇒r(x) multiplo di mcd(a, b)⇒ deg(r) ≥ deg(mcd(a, b))Sia j l’indice del Lemma precedente con

ν = deg(r), mu = deg(a)− deg(r)− 1

deg(tj+1) ≥ µ+1 ≥ deg(t)+1 deg(rj−1) ≥ ν+1 = deg(r)+1

Quindi se esiste indice che soddisfa (3) esso é unico.

. – p.33/39

Algoritmo di EuclideDimostriamo che indice esiste.Riscriviamo D (sia− tib = ri) e (1) come

sja+ tjb = rj , sa + tb = r (4)

per qualche polinomio s(x). Moltiplicando per t e tj , risp.

sjta+ tjtb = rjt, stja+ ttjb = rtj (5)

Quindi rjt ≡ rtj(moda)

. – p.34/39

Algoritmo di EuclideDimostriamo che indice esiste.Riscriviamo D (sia− tib = ri) e (1) come

sja+ tjb = rj , sa + tb = r (4)

per qualche polinomio s(x). Moltiplicando per t e tj , risp.

sjta+ tjtb = rjt, stja+ ttjb = rtj (5)

Quindi rjt ≡ rtj(moda)

. – p.34/39

Algoritmo di EuclideSapendo rjt ≡ rtj(moda) e deg(t) + deg(r) < deg(a):

deg(rj) ≤ ν ⇒ deg(rjt) = deg(rj)+deg(t) ≤ ν+µ < deg(a)

deg(tj) ≤ µ ⇒ deg(rtj) = deg(r)+deg(tj) ≤ µ+ν < deg(a)

Quindi rjt = rtj. Usando anche (5), sjt = stj .

Essendo da C, sj e tj primi tra loro: esiste λ(x) t.c.

s(x) = λ(x)sj(x) t(x) = λ(x)tj(x)

Sostituendo in (4) (cioé sa + tb = r): λsja+ λtjb = r

Usando sja+ tjb = rj : r = λ(sja+ tjb) = λrjquindi λ(x)rj(x) = r(x)

. – p.35/39

Computo di σ(x) e ω(x)

TEOREMA. Sia il numero di errori ≤ t. Si applichil’algoritmo di Euclide a a(x) = x2t e b(x) = S(x) e sia j ilprimo indice t.c. deg(rj) < t, allora

σ(x) = tj(x), ω(x) = rj(x)

DIM. Se numero di errori é ≤ t, allora

deg(σ) ≤ t deg(ω) < t, σ(x)S(x) ≡ ω(x) mod x2t

Teorema su A.E: Siano t(x) e r(x) due polinomi t.c.t(x)b(x) ≡ r(x) mod a(x)deg(t) + deg(r) < deg(a)Esistono unico indice j, 0 ≤ j ≤ n, e polinomio λ(x) t.c.t(x) = λ(x)tj(x), r(x) = λ(x)rj(x)

. – p.36/39

σ(x) = tj(x), ω(x) = rj(x)

DIM. Se numero di errori é ≤ t, allora

Teorema su A.E: Siano t(x) e r(x) due polinomi t.c.t(x)b(x) ≡ r(x) mod a(x)deg(t) + deg(r) < deg(a)Esistono unico indice j, 0 ≤ j ≤ n, e polinomio λ(x) t.c.t(x) = λ(x)tj(x), r(x) = λ(x)rj(x)

. – p.36/39

σ(x) = tj(x), ω(x) = rj(x)

Se numero di errori é ≤ t, allora

Teorema su A.E:⇒ σ(x) = λ(x)tj(x) e ω(x) = λ(x)rj(x)

Notando che σ(x) e ω(x) non hanno fattori comuni, siottiene σ(x) = tj(x), ω(x) = rj(x)

. – p.37/39

σ(x) = tj(x), ω(x) = rj(x)

Se numero di errori é ≤ t, allora

Teorema su A.E:⇒ σ(x) = λ(x)tj(x) e ω(x) = λ(x)rj(x)

Notando che σ(x) e ω(x) non hanno fattori comuni, siottiene σ(x) = tj(x), ω(x) = rj(x)

. – p.37/39

ALGORITMO DI DECODIFICA

Input: vettore ricevuto R

1. Calcola le sindromi

2. Applica A.E. a x2t e S(x), stop quando deg(rj) < tPoni σ(x) = tj(x) e ω(x) = rj(x) = x+ 1

3. Trova le radici di σβ−1i radice⇒ errore in posizione βi

4. Determina il vettore errore E= (E0, . . . , En−1):

E` =ω(β−1

β`Qi6=`(1+βiβ

−1` )

se c’e’ errore

E` = 0 altrimenti.

5. Output R+E

. – p.38/39

EsempioConsideriamo il codice RS(7, 2) su F8.Sia il vettore ricevuto R = (α3, α, 1, α2, 0, α3, 1).Le sindromi sono S1 = α3, S2 = α4, S3 = α4, S4 = 0.Eseguiamo l’algoritmo di Euclide su x2t = x4 eS(x) = α4x2 + α4x+ α3 fermandoci quando deg(rj) < t = 2.

i ti ri qi

−1 0 x4

0 1 α4x2 + α4x+ α3

1 α3x2 + α3x+ α5 x+ 1 α3x2 + α3x+ α5

Quindi σ(x) = t1(x) = α3x2 + α3x+ α5 ω(x) = r1(x) = x+ 1Si ricordari−2(x) = qi(x)ri−1(x) + ri(x) deg(ri) < deg(ri−1)ti(x) = ti−2(x)− qi(x)ti−1(x)

. – p.39/39

Campi di Galois - INTRANET di Galois F2: elementi f0;1g, somma modulo 2 Campo di Galois Vm(F2) = F2m...

Documents

Transcript of Campi di Galois - INTRANET di Galois F2: elementi f0;1g, somma modulo 2 Campo di Galois Vm(F2) = F2m...