Campo finito

In algebra un campo finito è un campo che contiene un numero finito di elementi. I campi finiti sono importanti in teoria dei numeri, geometria algebrica, teoria di Galois, in crittografia e in teoria dei codici.

I campi finiti sono completamente classificati.

Classificazione

I campi finiti sono classificati nel modo seguente:

• Ogni campo finito ha pⁿ elementi, per qualche numero primo p e qualche numero naturale n ≥ 1.
• Per ogni numero primo p e naturale n ≥ 1, esiste un solo campo finito con pⁿ elementi, a meno di isomorfismo.

Quindi, a meno di isomorfismi, esiste un solo campo con pⁿ elementi; questo viene solitamente indicato con F_pⁿ o con GF(pⁿ), da campo di Galois (Galois Field).

Ad esempio, esiste un campo finito F₈ = F_2³ con 8 elementi, mentre non ne esiste nessuno con 6 elementi, perché 6 non è la potenza di un numero primo.

Il campo finito presenta una struttura differente a seconda che n sia 1, e quindi il campo abbia precisamente p elementi, o che n sia maggiore di 1.

F_pⁿ, per n=1

Quando il campo finito ha esattamente p elementi (n=1) le sue operazioni vengono definite tramite l'aritmetica modulare modulo p.

Quindi F_p è il campo delle classi di resto modulo p, indicato normalmente con Z/_pZ.

Il gruppo soggiacente in questo caso è un gruppo ciclico di ordine p.

F_pⁿ, per n>1

Quando n>1, invece, l'aritmetica modulare modulo p non produce un campo poiché F_pⁿ non è isomorfo all'anello delle classi di resto Z/_pⁿZ: quest'ultimo infatti è solo un anello, e non un campo.

Il gruppo additivo soggiacente F_pⁿ infatti non è ciclico, bensì isomorfo a

$\begin{matrix} \underbrace{\mathbb{Z}/_{p\mathbb{Z}}\times\cdots\times \mathbb{Z}/_{p\mathbb{Z}}} \\ n \end{matrix}$

Le operazioni del campo sono quindi definite tramite aritmetica polinomiale e ogni elemento del campo viene visto come un polinomio i cui coefficienti appartengono a Z_p e il cui grado massimo è pari a n-1. Le operazioni sono svolte seguendo due accorgimenti: l'aritmetica sui coefficienti è un'aritmetica modulare modulo p e al termine di ogni operazione il polinomio risultante viene diviso per un polinomio irriducibile di grado n e ne viene preso il resto (assicurando così che questo abbia ancora grado al più n-1).

Costruzione di F_pⁿ

Il campo F_pⁿ è costruito come il campo di spezzamento del polinomio

$p(x) = x^{p^n} - x$

definito sul campo Z/_pZ.

Infatti il campo di spezzamento è generato da alcuni elementi $r_1,\ldots,r_q$ che spezzano il polinomio in

$p(x) = (x-r_1)\dots (x-r_q).$

Le radici $r_i$ sono distinte perché il polinomio p non ha radici multiple, in virtù del fatto che la sua derivata formale

$qx^{q-1} - 1 \equiv -1 \mod p$

non è mai nulla. Infine, le radici $r_1, \ldots, r_q$ formano esse stesse un campo, della cardinalità desiderata, che quindi coincide con il campo di spezzamento.

Dimostrazione della classificazione

La dimostrazione procede nel modo seguente. Sia K un campo finito.

1. Poiché finito, ha caratteristica non nulla. Poiché è un dominio d'integrità, la caratteristica è un numero primo p.
2. L'elemento 1 genera (additivamente) un sottocampo con p elementi, isomorfo quindi a Z/_pZ. Quindi K è uno spazio vettoriale su questo sottocampo.
3. Poiché K è finito, è uno spazio vettoriale di dimensione finita n. Quindi contiene pⁿ elementi.
4. L'unicità del campo a meno di isomorfismi segue dall'unicità del campo di spezzamento.

Proprietà

Caratteristica

Il campo F_pⁿ, essendo un anello, possiede una caratteristica che vale p.

Automorfismi

Se F è un campo con q = pⁿ elementi, allora

$x^q = x$

per ogni $x$ in F. Inoltre la mappa

$f: F \to F$

$f(x) = x^p$

è un isomorfismo (e quindi un automorfismo), chiamato automorfismo di Frobenius, in nome del matematico Ferdinand Georg Frobenius. L'automorfismo ha ordine n.

Sottocampi

Il campo F_pⁿ contiene una copia di F_p^m se e solo se m divide n.

I campi finiti più piccoli

Descriviamo le operazioni di somma e prodotto nei campi finiti di ordine 2, 3 e 4.

F₂:

 + | 0 1        · | 0 1
 --+----        --+----
 0 | 0 1        0 | 0 0
 1 | 1 0        1 | 0 1

F₃:

 + | 0 1 2       · | 0 1 2
 --+------       --+------
 0 | 0 1 2       0 | 0 0 0
 1 | 1 2 0       1 | 0 1 2
 2 | 2 0 1       2 | 0 2 1

F₄:

 + | 0 1 A B       · | 0 1 A B
 --+--------       --+--------
 0 | 0 1 A B       0 | 0 0 0 0
 1 | 1 0 B A       1 | 0 1 A B
 A | A B 0 1       A | 0 A B 1
 B | B A 1 0       B | 0 B 1 A

I campi finiti nella crittografia

Per approfondire, vedi Advanced Encryption Standard e Crittografia ellittica.

Per le loro proprietà i campi finiti svolgono un importante ruolo in diversi algoritmi crittografici tra cui l'AES e la crittografia ellittica.

Particolarmente utilizzati sono i campi della forma F_2ⁿ poiché presentano diversi vantaggi:

• permettono di rappresentare univocamente ogni polinomio del campo in n bit: infatti ogni coefficiente del polinomio assumerà proprio i valori binari 0 o 1;
• la somma tra i polinomi può essere eseguita efficientemente come semplice XOR bit-a-bit;
• la moltiplicazione per piccoli coefficienti (1, 2 o 3) richiede al massimo uno shift a sinistra e uno XOR.

Bibliografia

• William Stallings, Capitolo 4 - I campi finiti in Crittografia e sicurezza delle reti, 2ª edizione, ed. italiana a cura di Luca Salgarelli, Milano, McGraw-Hill, ottobre 2006, Pagg. 101-136.. ISBN 88-386-6377-7

Voci correlate

• Campo con un elemento
• Gruppo finito

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica