Campo finito

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca

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

[modifica | modifica wikitesto]

I campi finiti sono classificati nel modo seguente:

  • Ogni campo finito ha elementi, per qualche numero primo e qualche numero naturale .
  • Per ogni numero primo e naturale , esiste un solo campo finito con elementi, a meno di isomorfismo.

Quindi, a meno di isomorfismi, esiste un solo campo con elementi; questo viene solitamente indicato con o con , da campo di Galois (Galois Field).[1]

Ad esempio, esiste un campo finito con elementi, mentre non ne esiste nessuno con elementi, perché non è la potenza di un numero primo.

Il campo finito presenta una struttura differente a seconda che sia , e quindi il campo abbia precisamente elementi, o che sia maggiore di .[1]

Quando il campo finito ha esattamente elementi () le sue operazioni vengono definite tramite l'aritmetica modulare modulo .[2]

Quindi è il campo delle classi di resto modulo , ed è anche indicato con .

Il gruppo soggiacente in questo caso è un gruppo ciclico di ordine .

Quando , invece, l'aritmetica modulare modulo non produce un campo poiché non è isomorfo all'anello delle classi di resto : quest'ultimo infatti è solo un anello, e non un campo.

Il gruppo additivo soggiacente infatti non è ciclico, bensì isomorfo a

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 e il cui grado massimo è pari a . Le operazioni sono svolte seguendo due accorgimenti: l'aritmetica sui coefficienti è un'aritmetica modulare modulo e al termine di ogni operazione il polinomio risultante viene diviso per un polinomio irriducibile di grado e ne viene preso il resto (assicurando così che questo abbia ancora grado al più ).[3]

Costruzione di Fpn

[modifica | modifica wikitesto]

Il campo , con , è costruito come il campo di spezzamento del polinomio

definito sul campo .

Infatti il campo di spezzamento è generato da alcuni elementi che spezzano il polinomio in

Le radici sono distinte perché il polinomio non ha radici multiple, in virtù del fatto che la sua derivata formale

non è mai nulla. Infine, le radici formano esse stesse un campo, della cardinalità desiderata, che quindi coincide con il campo di spezzamento.

Dimostrazione della classificazione

[modifica | modifica wikitesto]

La dimostrazione procede nel modo seguente. Sia un campo finito.

  1. Poiché finito, ha caratteristica non nulla. Poiché è un dominio d'integrità, la caratteristica è un numero primo .
  2. L'elemento genera (additivamente) un sottocampo con elementi, isomorfo quindi a . Quindi è uno spazio vettoriale su questo sottocampo .
  3. Poiché è finito, è uno spazio vettoriale su di dimensione finita . Quindi contiene elementi.
  4. L'unicità del campo a meno di isomorfismi segue dall'unicità del campo di spezzamento.

Caratteristica

[modifica | modifica wikitesto]

Il campo , essendo un anello, possiede una caratteristica che vale .

Se è un campo con elementi, allora

per ogni in . Inoltre la mappa

è un isomorfismo (e quindi un automorfismo), chiamato automorfismo di Frobenius, in nome del matematico Ferdinand Georg Frobenius. L'automorfismo ha ordine .

Il campo contiene una copia di se e solo se divide .

I campi finiti più piccoli

[modifica | modifica wikitesto]

Descriviamo le operazioni di somma e prodotto nei campi finiti di ordine , e .

:

+ 0 1
0 0 1
1 1 0
× 0 1
0 0 0
1 0 1

:

+ 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

:

+ 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

[modifica | modifica wikitesto]

Il numero di polinomi monici irriducibili di grado su è dato da[4]

dove è la funzione di Möbius.

Dalla precedente formula segue che il numero di polinomi irriducibili (non necessariamente monici) di grado su è .

I campi finiti nella crittografia

[modifica | modifica wikitesto]
Lo stesso argomento in dettaglio: Advanced Encryption Standard e Crittografia ellittica.

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 poiché presentano diversi vantaggi:

  • permettono di rappresentare univocamente ogni polinomio del campo in bit: infatti ogni coefficiente del polinomio assumerà proprio i valori binari o ;[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]
  1. ^ a b Stallings 2006, pag.113
  2. ^ a b c 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
  • 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

[modifica | modifica wikitesto]

Altri progetti

[modifica | modifica wikitesto]

Collegamenti esterni

[modifica | modifica wikitesto]
Controllo di autoritàThesaurus BNCF 63749 · LCCN (ENsh85048351 · BNF (FRcb120618782 (data) · J9U (ENHE987007531228605171
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica