Câmp terminat

În matematică , în special în algebră , un câmp finit (uneori numit și câmp Galois ) este un câmp care conține un număr finit de elemente. Câmpurile finite sunt importante în teoria numerelor , geometria algebrică , teoria Galois , în criptografie și în teoria codurilor .

Câmpurile finite sunt complet clasificate.

Clasificare

Câmpurile finite sunt clasificate după cum urmează:

Fiecare câmp finit are $p^{n}$ ${\ displaystyle p ^ {n}}$ $p ^ n$ elemente, pentru un număr prim $p$ ${\ displaystyle p}$ $p$ și câteva numere naturale $n\geq 1$ ${\ displaystyle n \ geq 1}$ $n \ ge 1$ .
Pentru orice număr prim $p$ ${\ displaystyle p}$ $p$ este natural $n\geq 1$ ${\ displaystyle n \ geq 1}$ $n \ ge 1$ , există un singur câmp terminat cu $p^{n}$ ${\ displaystyle p ^ {n}}$ $p ^ n$ elemente, cu excepția izomorfismului .

Deci, cu excepția izomorfismelor, există un singur câmp cu $p^{n}$ ${\ displaystyle p ^ {n}}$ $p ^ n$ elemente; acest lucru este indicat de obicei cu $\mathbb {F} _{p^{n}}$ ${\ displaystyle \ mathbb {F} _ {p ^ {n}}}$ ${\ mathbb {F}} _ {{p ^ {n}}}$ sau cu $\mathrm {GF} (p^{n})$ ${\ displaystyle \ mathrm {GF} (p ^ {n})}$ ${\ mathrm {GF}} (p ^ {n})$ , din Galois Field ( Galois Field ). ^[1]

De exemplu, există un câmp finit $\mathbb {F} _{8}=\mathbb {F} _{2^{3}}$ ${\ displaystyle \ mathbb {F} _ {8} = \ mathbb {F} _ {2 ^ {3}}}$ ${\ mathbb {F}} _ {8} = {\ mathbb {F}} _ {{2 ^ {3}}}$ cu $8$ ${\ displaystyle 8}$ $8$ elemente, în timp ce niciunul nu există cu $6$ ${\ displaystyle 6}$ $6$ elemente, de ce $6$ ${\ displaystyle 6}$ $6$ nu este puterea unui număr prim.

Câmpul finit are o structură diferită în funcție de aceasta $n$ ${\ displaystyle n}$ $n$ este $1$ ${\ displaystyle 1}$ $1$ , și astfel câmpul are exact $p$ ${\ displaystyle p}$ $p$ elemente, sau asta $n$ ${\ displaystyle n}$ $n$ este mai mare decât $1$ ${\ displaystyle 1}$ $1$ . ^[1]

F _{p ⁿ} , pentru n = 1

Când câmpul terminat are exact $p$ ${\ displaystyle p}$ $p$ elemente ( $n=1$ ${\ displaystyle n = 1}$ $n = 1$ ) operațiile sale sunt definite folosind modulul modular aritmetic $p$ ${\ displaystyle p}$ $p$ . ^[2]

Prin urmare $\mathbb {F} _{p}$ ${\ displaystyle \ mathbb {F} _ {p}}$ ${\ mathbb {F}} _ {{p}}$ este câmpul clasei de odihnă a modulului $p$ ${\ displaystyle p}$ $p$ , și este, de asemenea, indicat cu $\mathbb {Z} /p\mathbb {Z}$ ${\ displaystyle \ mathbb {Z} / p \ mathbb {Z}}$ $\ mathbb {Z} / p \ mathbb {Z}$ .

Grupul de bază în acest caz este un grup ciclic de ordine $p$ ${\ displaystyle p}$ $p$ .

F _{p ⁿ} , pentru n > 1

Cand $n>1$ ${\ displaystyle n> 1}$ $n> 1$ în schimb, modul modular aritmetic $p$ ${\ displaystyle p}$ $p$ nu produce un câmp din moment ce $\mathbb {F} _{p^{n}}$ ${\ displaystyle \ mathbb {F} _ {p ^ {n}}}$ ${\ mathbb {F}} _ {{p ^ {n}}}$ nu este izomorfă pentru inelul celorlalte clase $\mathbb {Z} /p^{n}\mathbb {Z}$ ${\ displaystyle \ mathbb {Z} / p ^ {n} \ mathbb {Z}}$ $\ mathbb {Z} / p ^ {n} \ mathbb {Z}$ : acesta din urmă este de fapt doar un inel, și nu un câmp.

Grupul aditiv subiacent $\mathbb {F} _{p^{n}}$ ${\ displaystyle \ mathbb {F} _ {p ^ {n}}}$ ${\ mathbb {F}} _ {{p ^ {n}}}$ de fapt nu este ciclic, ci izomorf

{\begin{matrix}\underbrace {\mathbb {Z} /p\mathbb {Z} \times \cdots \times \mathbb {Z} /p\mathbb {Z} } \\n\end{matrix}}

{\ displaystyle {\ begin {matrix} \ underbrace {\ mathbb {Z} / p \ mathbb {Z} \ times \ cdots \ times \ mathbb {Z} / p \ mathbb {Z}} \\ n \ end {matrix }}}

{\ begin {matrix} \ underbrace {\ mathbb {Z} / p \ mathbb {Z} \ times \ cdots \ times \ mathbb {Z} / p \ mathbb {Z}} \\ n \ end {matrix}}

Operațiile câmpului sunt deci definite prin aritmetica polinomială ^[2] și fiecare element al câmpului este văzut ca un polinom al cărui coeficienți aparțin $\mathbb {Z} /p\mathbb {Z}$ ${\ displaystyle \ mathbb {Z} / p \ mathbb {Z}}$ $\ mathbb {Z} / p \ mathbb {Z}$ și al cărui grad maxim este egal cu $n-1$ ${\ displaystyle n-1}$ $n-1$ . Operațiunile sunt efectuate urmând două precauții: aritmetica pe coeficienți este un modul aritmetic modular $p$ ${\ displaystyle p}$ $p$ iar la sfârșitul fiecărei operații polinomul rezultat este împărțit la un polinom ireductibil de grad $n$ ${\ displaystyle n}$ $n$ iar restul este luat (asigurându-se astfel că acesta are încă cel mult rang $n-1$ ${\ displaystyle n-1}$ $n-1$ ). ^[3]

Construcția F _{p ⁿ}

Campul $\mathbb {F} _{q}$ ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ mathbb {F}} _ {{q}}$ , cu $q=p^{n}$ ${\ displaystyle q = p ^ {n}}$ $q = p ^ {n}$ , este construit ca câmpul de divizare al polinomului

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

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

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

câmp definit $\mathbb {Z} /p\mathbb {Z}$ ${\ displaystyle \ mathbb {Z} / p \ mathbb {Z}}$ $\ mathbb {Z} / p \ mathbb {Z}$ .

De fapt, câmpul de divizare este generat de unele elemente $r_{1},\ldots ,r_{q}$ ${\ displaystyle r_ {1}, \ ldots, r_ {q}}$ $r_ {1}, \ ldots, r_ {q}$ care rup polinomul în

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

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

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

Radacinile $r_{i}$ ${\ displaystyle r_ {i}}$ $re$ sunt distincte deoarece polinomul $p(x)$ ${\ displaystyle p (x)}$ $p (x)$ nu are rădăcini multiple, în virtutea faptului că derivatul său formal

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

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

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

nu este niciodată nimic. În cele din urmă, rădăcinile $r_{1},\ldots ,r_{q}$ ${\ displaystyle r_ {1}, \ ldots, r_ {q}}$ $r_ {1}, \ ldots, r_ {q}$ ei înșiși formează un câmp, cu cardinalitatea dorită, care deci coincide cu câmpul despărțitor.

Demonstrarea clasificării

Demonstrația se desfășoară după cum urmează. Este $K.$ ${\ displaystyle K}$ $K.$ un câmp finit.

De când este terminat, are o caracteristică care nu este nulă. Deoarece este un domeniu de integritate , caracteristica este un număr prim $p$ ${\ displaystyle p}$ $p$ .
Elementul $1$ ${\ displaystyle 1}$ $1$ generează (adițional) un subcâmp cu $p$ ${\ displaystyle p}$ $p$ elemente, izomorfe deci a $\mathbb {Z} /p\mathbb {Z}$ ${\ displaystyle \ mathbb {Z} / p \ mathbb {Z}}$ $\ mathbb {Z} / p \ mathbb {Z}$ . Prin urmare $K.$ ${\ displaystyle K}$ $K.$ este un spațiu vectorial pe acest subcâmp $\mathbb {F} _{p}$ ${\ displaystyle \ mathbb {F} _ {p}}$ ${\ mathbb {F}} _ {p}$ .
Atâta timp cât $K.$ ${\ displaystyle K}$ $K.$ este finit, este un spațiu vectorial pe $\mathbb {F} _{p}$ ${\ displaystyle \ mathbb {F} _ {p}}$ ${\ mathbb {F}} _ {p}$ de mărime finită $n$ ${\ displaystyle n}$ $n$ . Deci conține $p^{n}$ ${\ displaystyle p ^ {n}}$ $p ^ n$ elemente.
Unicitatea câmpului până la izomorfisme rezultă din unicitatea câmpului despărțitor .

Proprietate

Caracteristică

Campul $\mathbb {F} _{p^{n}}$ ${\ displaystyle \ mathbb {F} _ {p ^ {n}}}$ ${\ mathbb {F}} _ {{p ^ {n}}}$ , fiind un inel , are o caracteristică valoroasă $p$ ${\ displaystyle p}$ $p$ .

Automorfisme

De sine $F.$ ${\ displaystyle F}$ $F.$ este un câmp cu $q=p^{n}$ ${\ displaystyle q = p ^ {n}}$ $q = p ^ {n}$ elemente, atunci

x^{q}=x,

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

x ^ {q} = x,

pentru fiecare $X$ ${\ displaystyle x}$ $X$ în $F.$ ${\ displaystyle F}$ $F.$ . Plus harta

f\colon F\to F

{\ displaystyle f \ colon F \ to F}

f \ colon F \ to F

f(x)=x^{p},

{\ displaystyle f (x) = x ^ {p},}

f (x) = x ^ {p},

este un izomorfism (și deci un automorfism ), numit automorfism Frobenius , în numele matematicianului Ferdinand Georg Frobenius . Automorfismul are ordine $n$ ${\ displaystyle n}$ $n$ .

Subcampuri

Campul $\mathbb {F} _{p^{n}}$ ${\ displaystyle \ mathbb {F} _ {p ^ {n}}}$ ${\ mathbb {F}} _ {{p ^ {n}}}$ conține o copie a $\mathbb {F} _{p^{m}}$ ${\ displaystyle \ mathbb {F} _ {p ^ {m}}}$ ${\ mathbb {F}} _ {{p ^ {m}}}$ dacă și numai dacă $m$ ${\ displaystyle m}$ $m$ împarte $n$ ${\ displaystyle n}$ $n$ .

Cele mai fine câmpuri mai mici

Descriem operațiunile de sumă și produs în câmpurile de comandă finită $2$ ${\ displaystyle 2}$ $2$ , $3$ ${\ displaystyle 3}$ $3$ Și $4$ ${\ displaystyle 4}$ $4$ .

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

+	0	1
0	0	1
1	1	0

×	0	1
0	0	0
1	0	1

$\mathbb {F} _{3}$ ${\ displaystyle \ mathbb {F} _ {3}}$ ${\ mathbb {F}} _ {{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

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

+	0	1	LA	B.
0	0	1	LA	B.
1	1	0	B.	LA
LA	LA	B.	0	1
B.	B.	LA	1	0

×	1	LA	B.
0	0	0	0
1	1	LA	B.
LA	LA	B.	1
B.	B.	1	LA

Numărul de polinoame ireductibile de un anumit grad pe un câmp finit

Numarul $N(q,n)$ ${\ displaystyle N (q, n)}$ $N (q, n)$ de polinoame monice ireductibile de grad $n$ ${\ displaystyle n}$ $n$ pe $\mathbb {F} _{q}$ ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ mathbb {F}} _ {{q}}$ este dat de ^[4]

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

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

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

unde este $\mu$ ${\ displaystyle \ mu}$ $\ mu$ este funcția Möbius .

Din formula de mai sus rezultă că numărul de polinoame ireductibile (nu neapărat monice) de grad $n$ ${\ displaystyle n}$ $n$ pe $\mathbb {F} _{q}$ ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ mathbb {F}} _ {{q}}$ Și $(q-1)N(q,n)$ ${\ displaystyle (q-1) N (q, n)}$ $(q-1) N (q, n)$ .

Câmpuri finite în criptografie

Același subiect în detaliu: Criptare standard avansată și criptare eliptică .

Datorită proprietăților lor, câmpurile finite joacă un rol important în diferiți algoritmi criptografici, inclusiv AES și criptografie eliptică . ^[2]

Utilizate în mod special sunt câmpurile formularului $\mathbb {F} _{2^{n}}$ ${\ displaystyle \ mathbb {F} _ {2 ^ {n}}}$ ${\ mathbb {F}} _ {{2 ^ {n}}}$ deoarece au mai multe avantaje:

permite să reprezinte în mod unic fiecare polinom al câmpului în $n$ ${\ displaystyle n}$ $n$ bit : de fapt, fiecare coeficient al polinomului va lua valorile binare o $1$ ${\ displaystyle 1}$ $1$ ; ^[5]
suma dintre polinoame poate fi efectuată eficient ca un simplu XOR bit-to-bit; ^[6]
multiplicarea cu coeficienți mici (1, 2 sau 3) necesită cel mult o deplasare la stânga și o XOR. ^[7]

Notă

^ ^a ^b Stallings 2006, ^p . 113
^ ^a ^b ^c Stallings 2006, pagina 101
^ Stallings 2006, pp. 116 și 124
^ Jacobson , §4.13
^ Stallings 2006, p.127
^ Stallings 2006, pagina 128
^ Stallings 2006, paginile 128 și 157

Bibliografie

William Stallings, Capitolul 4 - Câmpuri finite , în Criptografie și securitate rețea , ed. Italiană editat de Luca Salgarelli, ediția a II-a, Milano, McGraw-Hill, octombrie 2006, pp. 101-136., ISBN 88-386-6377-7 .

Elemente conexe

linkuri externe

( EN ) Domeniu terminat , în Enciclopedia Britanică , Enciclopedia Britanică, Inc.

Controlul autorității	Tezaur BNCF 63749 · LCCN (EN) sh85048351 · BNF (FR) cb120618782 (data)

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[stallings113-1] Stallings 2006, ^p . 113

[stallings101-2] Stallings 2006, pagina 101

[3] Stallings 2006, pp. 116 și 124

[4] Jacobson , §4.13

[5] Stallings 2006, p.127

[6] Stallings 2006, pagina 128

[7] Stallings 2006, paginile 128 și 157

[1]

[2]

[3]

[4]

[5]

[6]

[7]