Campo finito

In matematica, in particolare in algebra, un campo finito (detto a volte anche campo di Galois) è 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^{n}$ elementi, per qualche numero primo $p$ e qualche numero naturale $n\geq 1$.
• Per ogni numero primo $p$ e naturale $n\geq 1$, esiste un solo campo finito con $p^{n}$ elementi, a meno di isomorfismo.

Quindi, a meno di isomorfismi, esiste un solo campo con $p^{n}$ elementi; questo viene solitamente indicato con $\mathbb {F} _{p^{n}}$ o con $\mathrm {GF} (p^{n})$, da campo di Galois (Galois Field).

Ad esempio, esiste un campo finito $\mathbb {F} _{8}=\mathbb {F} _{2^{3}}$ 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 $\mathbb {F} _{p}$ è il campo delle classi di resto modulo $p$, ed è anche indicato con $\mathbb {Z} /p\mathbb {Z}$.

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é $\mathbb {F} _{p^{n}}$ non è isomorfo all'anello delle classi di resto $\mathbb {Z} /p^{n}\mathbb {Z}$: quest'ultimo infatti è solo un anello, e non un campo.

Il gruppo additivo soggiacente $\mathbb {F} _{p^{n}}$ 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 $\mathbb {Z} /p\mathbb {Z}$ 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 $\mathbb {F} _{q}$, con $q=p^{n}$, è costruito come il campo di spezzamento del polinomio

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

definito sul campo $\mathbb {Z} /p\mathbb {Z}$.

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(x)$ 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 $\mathbb {Z} /p\mathbb {Z}$. Quindi $K$ è uno spazio vettoriale su questo sottocampo $\mathbb {F} _{p}$.
3. Poiché $K$ è finito, è uno spazio vettoriale su $\mathbb {F} _{p}$ di dimensione finita $n$. Quindi contiene $p^{n}$ elementi.
4. L'unicità del campo a meno di isomorfismi segue dall'unicità del campo di spezzamento.

Proprietà

Caratteristica

Il campo $\mathbb {F} _{p^{n}}$, essendo un anello, possiede una caratteristica che vale $p$.

Automorfismi

Se $F$ è un campo con $q=p^{n}$ elementi, allora

$x^{q}=x,$

per ogni $x$ in $F$. Inoltre la mappa

$f\colon 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 $\mathbb {F} _{p^{n}}$ contiene una copia di $\mathbb {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$.

$\mathbb {F} _{2}$:

+ 0 1 0 0 1 1 1 0

× 0 1 0 0 0 1 0 1

$\mathbb {F} _{3}$:

+ 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1

× 0 1 2 0 0 0 0 1 0 1 2 2 0 2 1

$\mathbb {F} _{4}$:

+ 0 1 A B 0 0 1 A B 1 1 0 B A A A B 0 1 B B A 1 0

× 0 1 A B 0 0 0 0 0 1 0 1 A B A 0 A B 1 B 0 B 1 A

Numero di polinomi irriducibili di un dato grado su un campo finito

Il numero $N(q,n)$ di polinomi monici irriducibili di grado $n$ su $\mathbb {F} _{q}$ è dato da

$N(q,n)={\frac {1}{n}}\sum _{d|n}\mu (d)q^{\frac {n}{d}},$

dove $\mu$ è la funzione di Möbius.

Dalla precedente formula segue che il numero di polinomi irriducibili (non necessariamente monici) di grado $n$ su $\mathbb {F} _{q}$ è $(q-1)N(q,n)$.

I campi finiti nella crittografia

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 $\mathbb {F} _{2^{n}}$ 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, ed. italiana a cura di Luca Salgarelli, 2ª edizione, Milano, McGraw-Hill, ottobre 2006, pp. 101-136., ISBN 88-386-6377-7.

Voci correlate

• Campo con un elemento
• Gruppo finito

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sul campo finito

Collegamenti esterni

• (EN) finite field, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Campo finito, su MathWorld, Wolfram Research.