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 $𝔽_{p^{n}}$ o con $G 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 $ℤ / p ℤ$ .

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 $ℤ / p^{n} ℤ$ : quest'ultimo infatti è solo un anello, e non un campo.

Il gruppo additivo soggiacente $𝔽_{p^{n}}$ infatti non è ciclico, bensì isomorfo a

\begin{matrix} \underset{⏟}{ℤ / p ℤ \times \dots \times ℤ / p ℤ} \\ 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 $ℤ / 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 $𝔽_{q}$ , con $q = p^{n}$ , è costruito come il campo di spezzamento del polinomio

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

definito sul campo $ℤ / p ℤ$ .

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 - 1 mod p,

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.

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 $ℤ / p ℤ$ . Quindi $K$ è uno spazio vettoriale su questo sottocampo $𝔽_{p}$ .
Poiché $K$ è finito, è uno spazio vettoriale su $𝔽_{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 $𝔽_{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

×	1	2
0	0	0
1	1	2
2	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

×	1	A	B
0	0	0	0
1	1	A	B
A	A	B	1
B	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} μ (d) q^{\frac{n}{d}},

dove $μ$ è 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

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.

Note

1 2 Stallings 2006, pag.113
1 2 3 Stallings 2006, pag.101
↑ Stallings 2006, pagg.116 e 124
↑ Jacobson, 2009
↑ Stallings 2006, pag.127
↑ Stallings 2006, pag.128
↑ Stallings 2006, pagg.128 e 157

Bibliografia

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

Voci correlate

Altri progetti

Wikimedia Commons contiene immagini o altri file sul campo finito

Collegamenti esterni

Campo finito, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.

Galois, campo di, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.

(EN) finite field, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.

(EN) Opere riguardanti Finite fields (Algebra), su Open Library, Internet Archive.

(EN) Eric W. Weisstein, Finite Field, su MathWorld, Wolfram Research.

(EN) Galois field, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.

Controllo di autorità	Thesaurus BNCF 63749 · LCCN (EN) sh85048351 · BNF (FR) cb120618782 (data) · J9U (EN, HE) 987007531228605171

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

[stallings113-1] 1 2 Stallings 2006, pag.113

[stallings101-2] 1 2 3 Stallings 2006, pag.101

[3] Stallings 2006, pagg.116 e 124

[4] Jacobson, 2009

[5] Stallings 2006, pag.127

[6] Stallings 2006, pag.128

[7] Stallings 2006, pagg.128 e 157

V · D · M Algebra
Numeri
Naturali · Interi · Razionali · Irrazionali · Algebrici · Trascendenti · Reali · Complessi · Numero ipercomplesso · Numero p-adico · Duali · Complessi iperbolici
Principî fondamentali
Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza · Relazione d'ordine · Associatività della potenza
Algebra elementare
Equazione · Disequazione · Polinomio · Triangolo di Tartaglia · Teorema binomiale · Teorema del resto · Lemma di Gauss · Teorema delle radici razionali · Regola di Ruffini · Criterio di Eisenstein · Criterio di Cartesio · Disequazione con il valore assoluto · Segno · Metodo di Gauss-Seidel · Polinomio simmetrico · Funzione simmetrica
Calcolo combinatorio base
Fattoriale · Permutazione · Disposizione · Combinazione · Dismutazione · Principio di inclusione-esclusione
Basi di teoria dei numeri
Numeri primi	Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Crivello di Atkin · Test di primalità · Teorema fondamentale dell'aritmetica
Divisori	Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Criteri di divisibilità · Divisore
Aritmetica modulare	Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Funzione φ di Eulero · Teorema di Wilson · Reciprocità quadratica
Teoria dei gruppi
Omomorfismo · Isomorfismo · Automorfismo interno · Automorfismo esterno · Permutazione · Presentazione di un gruppo · Azione di gruppo
Gruppi	Gruppo finito · Gruppo ciclico · Gruppo abeliano · Gruppo primario · Gruppo quoziente · Gruppo nilpotente · Gruppo risolubile · Gruppo simmetrico · Gruppo diedrale · Gruppo semplice · Gruppo sporadico · Gruppo mostro · Gruppo di Klein · Gruppo dei quaternioni · Gruppo generale lineare · Gruppo ortogonale · Gruppo unitario · Gruppo unitario speciale · Gruppo residualmente finito · Gruppo spaziale · Gruppo profinito · Out(F_n) · Parola · Prodotto diretto · Prodotto semidiretto · Prodotto intrecciato
Teoremi	Alternativa di Tits · Teorema di isomorfismo · Teorema di Lagrange · Teorema di Cauchy · Teoremi di Sylow · Teorema di Cayley · Teorema di struttura dei gruppi abeliani finiti · Lemma di Burnside · Lemma della farfalla · Lemma del ping-pong · Classificazione dei gruppi semplici finiti
Sottoinsiemi	Sottogruppo · Sottogruppo normale · Sottogruppo caratteristico · Sottogruppo di Frattini · Sottogruppo di torsione · Classe laterale · Classe di coniugio · Serie di composizione
Teoria degli anelli
Anello (artiniano · noetheriano · locale) · Caratteristica · Ideale (primo · massimale) · Dominio (a fattorizzazione unica · a ideali principali · euclideo) · Matrice · Anello semplice · Anello degli endomorfismi · Teorema di Artin-Wedderburn · Modulo · Dominio di Dedekind · Estensione di anelli · Teorema della base di Hilbert · Anello di Gorenstein · Base di Gröbner · Prodotto tensoriale · Primo associato
Teoria dei campi
Campo · Polinomio irriducibile · Polinomio ciclotomico · Teorema fondamentale dell'algebra · Campo finito · Automorfismo · Endomorfismo di Frobenius
Estensioni	Campo di spezzamento · Estensione di campi · Estensione algebrica · Estensione separabile · Chiusura algebrica · Campo di numeri · Estensione normale · Estensione di Galois · Estensione abeliana · Estensione ciclotomica · Teoria di Kummer
Teoria di Galois	Gruppo di Galois · Teorema fondamentale della teoria di Galois · Teorema di Abel-Ruffini · Costruzioni con riga e compasso
Altre strutture algebriche
Magma · Semigruppo · Corpo · Spazio vettoriale · Algebra su campo · Algebra di Lie · Algebra differenziale · Algebra di Clifford · Gruppo topologico · Gruppo ordinato · Quasi-anello · Algebra di Boole
Argomenti
Teoria delle categorie · Algebra lineare · Algebra commutativa · Algebra omologica · Algebra astratta · Algebra computazionale · Algebra differenziale · Algebra universale