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:

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

Ad esempio, esiste un campo finito ${\displaystyle \mathbb {F} _{8}=\mathbb {F} _{2^{3}}}$ con ${\displaystyle 8}$ elementi, mentre non ne esiste nessuno con ${\displaystyle 6}$ elementi, perché ${\displaystyle 6}$ non è la potenza di un numero primo.

Il campo finito presenta una struttura differente a seconda che ${\displaystyle n}$ sia ${\displaystyle 1}$, e quindi il campo abbia precisamente ${\displaystyle p}$ elementi, o che ${\displaystyle n}$ sia maggiore di ${\displaystyle 1}$.^[1]

F_pⁿ, per n=1

Quando il campo finito ha esattamente ${\displaystyle p}$ elementi (${\displaystyle n=1}$) le sue operazioni vengono definite tramite l'aritmetica modulare modulo ${\displaystyle p}$.^[2]

Quindi ${\displaystyle \mathbb {F} _{p}}$ è il campo delle classi di resto modulo ${\displaystyle p}$, ed è anche indicato con ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$.

Il gruppo soggiacente in questo caso è un gruppo ciclico di ordine ${\displaystyle p}$.

F_pⁿ, per n>1

Quando ${\displaystyle n>1}$, invece, l'aritmetica modulare modulo ${\displaystyle p}$ non produce un campo poiché ${\displaystyle \mathbb {F} _{p^{n}}}$ non è isomorfo all'anello delle classi di resto ${\displaystyle \mathbb {Z} /p^{n}\mathbb {Z} }$: quest'ultimo infatti è solo un anello, e non un campo.

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

${\displaystyle {\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^[2] e ogni elemento del campo viene visto come un polinomio i cui coefficienti appartengono a ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ e il cui grado massimo è pari a ${\displaystyle n-1}$. Le operazioni sono svolte seguendo due accorgimenti: l'aritmetica sui coefficienti è un'aritmetica modulare modulo ${\displaystyle p}$ e al termine di ogni operazione il polinomio risultante viene diviso per un polinomio irriducibile di grado ${\displaystyle n}$ e ne viene preso il resto (assicurando così che questo abbia ancora grado al più ${\displaystyle n-1}$).^[3]

Costruzione di F_pⁿ

Il campo ${\displaystyle \mathbb {F} _{q}}$, con ${\displaystyle q=p^{n}}$, è costruito come il campo di spezzamento del polinomio

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

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

Infatti il campo di spezzamento è generato da alcuni elementi ${\displaystyle r_{1},\ldots ,r_{q}}$ che spezzano il polinomio in

${\displaystyle p(x)=(x-r_{1})\dots (x-r_{q}).}$

Le radici ${\displaystyle r_{i}}$ sono distinte perché il polinomio ${\displaystyle p(x)}$ non ha radici multiple, in virtù del fatto che la sua derivata formale

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

non è mai nulla. Infine, le radici ${\displaystyle 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 ${\displaystyle K}$ un campo finito.

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

Proprietà

Caratteristica

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

Automorfismi

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

${\displaystyle x^{q}=x,}$

per ogni ${\displaystyle x}$ in ${\displaystyle F}$. Inoltre la mappa

${\displaystyle f\colon F\to F}$

${\displaystyle 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 ${\displaystyle n}$.

Sottocampi

Il campo ${\displaystyle \mathbb {F} _{p^{n}}}$ contiene una copia di ${\displaystyle \mathbb {F} _{p^{m}}}$ se e solo se ${\displaystyle m}$ divide ${\displaystyle n}$.

I campi finiti più piccoli

Descriviamo le operazioni di somma e prodotto nei campi finiti di ordine ${\displaystyle 2}$, ${\displaystyle 3}$ e ${\displaystyle 4}$.

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

+ 0 1 0 0 1 1 1 0

× 0 1 0 0 0 1 0 1

${\displaystyle \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

${\displaystyle \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 ${\displaystyle N(q,n)}$ di polinomi monici irriducibili di grado ${\displaystyle n}$ su ${\displaystyle \mathbb {F} _{q}}$ è dato da^[4]

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

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

Dalla precedente formula segue che il numero di polinomi irriducibili (non necessariamente monici) di grado ${\displaystyle n}$ su ${\displaystyle \mathbb {F} _{q}}$ è ${\displaystyle (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.^[2]

Particolarmente utilizzati sono i campi della forma ${\displaystyle \mathbb {F} _{2^{n}}}$ poiché presentano diversi vantaggi:

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

Note

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

• 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.

V · D · M Algebra
Numeri	Naturali · Interi · Razionali · Irrazionali · Algebrici · Trascendenti · Reali · Complessi · Numero ipercomplesso · Numero p-adico · Duali · Complessi iperbolici
Principi 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
Elementi di Calcolo combinatorio	Fattoriale · Permutazione · Disposizione · Combinazione · Dismutazione · Principio di inclusione-esclusione
Concetti fondamentali di Teoria dei numeri	Primi Numero primo · 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	Gruppi Gruppo (finito · ciclico · 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(Fn) · 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 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 Omomorfismo · Isomorfismo · Automorfismo interno · Automorfismo esterno · Permutazione · Presentazione di un gruppo · Azione di gruppo
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 · Teoria 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

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