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\ge 1$.
• Per ogni numero primo $p$ e naturale $n\ge 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 ${𝔽}_{p^n}$ o con $\mathrm{G}\mathrm{F}(p^n)$, da campo di Galois (Galois Field).

Ad esempio, esiste un campo finito ${𝔽}_8={𝔽}_{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 ${𝔽}_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é ${𝔽}_{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 ${𝔽}_{p^n}$ infatti non è ciclico, bensì isomorfo a

$\begin{array}{c}\underbrace{\mathbb{Z}/p\mathbb{Z}\times \cdots \times \mathbb{Z}/p\mathbb{Z}}\\ n\end{array}$

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 ${𝔽}_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,\dots ,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

$q{x}^{q-1}-1\equiv -1modp,$

non è mai nulla. Infine, le radici $r_1,\dots ,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 ${𝔽}_p$.
3. Poiché $K$ è finito, è uno spazio vettoriale su ${𝔽}_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 ${𝔽}_{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: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 ${𝔽}_{p^n}$ contiene una copia di ${𝔽}_{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$.

${𝔽}_2$:

+ 0 1 0 0 1 1 1 0

× 0 1 0 0 0 1 0 1

${𝔽}_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

${𝔽}_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 ${𝔽}_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 ${𝔽}_q$ è $(q-1)N(q,n)$.

I campi finiti nella crittografia

Template:Vedi anche 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 ${𝔽}_{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

• Template:Cita libro

Voci correlate

• Campo con un elemento
• Gruppo finito

Collegamenti esterni

• Template:Collegamenti esterni