Apri il menu principale

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.

Indice

ClassificazioneModifica

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]

Fpn, per n=1Modifica

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  .

Fpn, per n>1Modifica

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 FpnModifica

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 classificazioneModifica

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.

ProprietàModifica

CaratteristicaModifica

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

AutomorfismiModifica

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  .

SottocampiModifica

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

I campi finiti più piccoliModifica

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 finitoModifica

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 crittografiaModifica

 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]

NoteModifica

  1. ^ a b Stallings 2006, pag.113
  2. ^ a b c Stallings 2006, pag.101
  3. ^ Stallings 2006, pagg.116 e 124
  4. ^ Jacobson,  §4.13
  5. ^ Stallings 2006, pag.127
  6. ^ Stallings 2006, pag.128
  7. ^ Stallings 2006, pagg.128 e 157

BibliografiaModifica

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

Collegamenti esterniModifica

Controllo di autoritàLCCN (ENsh85048351
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica