Campo finito
# 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_{pn},$ 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_{pn},$ 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_{pn}$

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.

* Poiché finito, ha caratteristica non nulla. Poiché è un dominio d'integrità, la caratteristica è un numero primo $p$.
* 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}$.
* Poiché $K$ è finito, è uno spazio vettoriale su $\mathbb {F} _{p}$ di dimensione finita $n$. Quindi contiene $p^{n}$ elementi.
* 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.
