Eindig lichaam (Ned) / Eindig veld (Be)

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Een eindig lichaam (Nederlandse term) of eindig veld (Belgische term), Galoislichaam, Galoisruimte, of Galoisveld (vernoemd naar Évariste Galois) is een lichaam (Nederlandse term) met een eindig aantal elementen. Eindige velden worden gebruikt in de cryptografie, coderingstheorie, Galoistheorie, getaltheorie en algebraïsche meetkunde. Een eindig lichaam wordt genoteerd als \mathbb F_q of \mathrm{GF}(q) waarbij de laatste vorm refereert aan de Engelse term Galois Field.

Galois heeft eindige lichamen in 1830 ingevoerd, maar pas door toedoen van de Amerikaanse wiskundige Eliakim Moore (1862-1932) zijn eindige lichamen geclassificeerd. Eindige lichamen zijn belangrijker geworden met de komst van digitale elektronica en computers en de ontwikkeling van de informatietheorie en discrete wiskunde.

Lichaam[bewerken]

Net als elk lichaam, is een eindig lichaam een verzameling die is uitgerust met de bewerkingen optelling, aftrekking, vermenigvuldiging en deling (delen door nul is niet gedefinieerd), waarbij de verzameling voor deze bewerkingen gesloten is (dat wil zeggen dat het resultaat van de bewerking een element moet zijn in de eindige verzameling van elementen). Bovendien zijn optelling en de vermenigvuldiging beiden associatief en commutatief en is de vermenigvuldiging distributief ten opzichte van de optelling.

Wanneer optellen of vermenigvuldigen wordt toegepast op de normale manier, dan is het lichaam ofwel niet gesloten (en is dus geen lichaam) of oneindig groot: als 1 een element in het lichaam is, dan moet 1 + 1 = 2 ook een element zijn, 2 + 1 = 3, 3 + 1 = 4 etc. Om deze reden worden de normale operaties niet gebruikt, maar worden, voor priemlichamen, alle operaties modulo q uitgevoerd waarbij q het aantal elementen in het lichaam is.

Voorbeeld voor q = 3:

  • 1 + 1 = 2 (modulo 3) = 2
  • 1 + 2 = 3 (modulo 3) = 0
  • 2 × 2 = 4 (modulo 3) = 1
  • 1 ÷ 2 = 2, want als a ÷ b = c, dan geldt a = b × c, dus 1 = 2 × 2 = 4 (modulo 3) = 1

Orde[bewerken]

De orde of kardinaliteit van een eindig lichaam is het aantal elementen van het lichaam. Omdat elk niet-nul element uit een lichaam een invers element voor de vermenigvuldiging moet hebben, bestaat er niet voor elke orde een eindig lichaam. De verzameling van niet-nul elementen van een lichaam \mathbb F_q wordt genoteerd als \mathbb F_q^* en wordt vaak de multiplicatieve groep van het lichaam genoemd.

Voorbeeld :
Voor \Z_4 \quad, ('q = 4'), zoeken we het inverse van het element 2.

  • 2 * 0 = 0 (modulo 4) = 0
  • 2 * 1 = 2 (modulo 4) = 2
  • 2 * 2 = 4 (modulo 4) = 0
  • 2 * 3 = 6 (modulo 4) = 2

We zien dat er voor \Z_4 geen element x is waarvoor geldt dat 2 * x = 1; derhalve is \Z_4 geen lichaam, en dus ook geen eindig lichaam. (\Z_4 is overigens wel een groep voor de optelling.)

Het blijkt dat er alleen eindige lichamen bestaan met een orde die ofwel gelijk is aan een priemgetal, een zogenaamd priemlichaam, ofwel gelijk is aan een priemgetal (p) tot de macht m (q = pm), een zogenaamd uitbreidingslichaam. Het priemgetal p wordt wel de karakteristiek genoemd en m de uitbreidingsgraad van \mathbb F_q.

Er bestaat dus bijvoorbeeld wel degelijk een eindig lichaam met vier elementen; dit is het lichaam \mathbb F_{2^2}. Hierin hebben de drie niet-nul elementen een multiplicatieve inverse.

Uitbreidingslichaam[bewerken]

Een uitbreidingslichaam of extensielichaam is een eindig lichaam waarvoor m ≠ 1. Het voorbeeld hierboven laat zien dat \Z_4 niet een lichaam is, maar 4 voldoet wel aan de vorm q = pm (q = 22). Een lichaam met 4 elementen moet kennelijk op een andere manier worden geconstrueerd. De oplossing is dat lichamen met q = pm elementen (en m > 1) worden geconstrueerd als uitbreidingslichaam van \Z_p. Uitbreidingslichamen kunnen gezien worden als een m-dimensionale vectorruimte over het lichaam \mathbb F_p = \Z_p. Een element \beta\in\mathbb F_{p^m} van een uitbreidingslichaam kan uniek worden geschreven als \beta = b_{m-1}\alpha^{m-1} ...+ b_{1}\alpha^{1} + b_{0}\alpha^{0}. Hierbij is \alpha de wortel van een irreducibel m-de graads polynoom a(x) over het lichaam \mathbb F_q; de b_{i} zijn elementen van \mathbb F_q.

Optellen en aftrekken in een uitbreidingslichaam is gewoonweg modulo rekenen in meerdere dimensies, maar vermenigvuldigen en delen is niet op deze manier te definiëren; hiervoor wordt het irreducibele polynoom a(x) gebruikt dat analoog wordt toegepast als de p bij het modulorekenen in het eendimensionale geval: de twee te vermenigvuldigen polynomen (elementen van \mathbb F_q) worden op de normale manier met elkaar vermenigvuldigd maar het resultaat wordt modulo het polynoom a(\alpha) genomen.

Voor delen geldt dat het overeenkomt met vermenigvuldigen met de multiplicatieve inverse. En alle multiplicatieve inversen kunnen worden gevonden door eenmalig een complete vermenigvuldigingstabel op te stellen voor het eindige lichaam.

Het polynoom a(\alpha) heet ook wel het reductiepolynoom.

Primitief element[bewerken]

Elk eindig lichaam heeft ten minste een element α waarvoor geldt \alpha^{q-1} = 1 en \alpha^{n}\not=1 voor 1<n<q-1; deze α wordt het primitieve element genoemd.

Voorbeeld \mathbb F_{16}[bewerken]

Een voorbeeld van een eindig lichaam is \mathbb F_{2^4} dat 16 elementen bevat. Om dit lichaam te construeren moet als eerste worden gezocht naar een irreducibel polynoom p(x) over \mathbb F_2 met graad 4. Een van de wortels van dit polynoom krijgt per definitie de naam \alpha. Ieder element van \mathbb F_{2^4} kan nu worden voorgesteld als een derdegraads polynoom in \alpha over \mathbb F_2; het is duidelijk dat er inderdaad 16 dergelijke polynomen bestaan. De optelling in L is nu identiek aan de optelling in een 4-dimensionale lineaire vectorruimte over \mathbb F_2. De vermenigvuldiging wordt gedefinieerd met behulp van p(x).

Voor het vinden van een vierdegraads irreducibel polynoom over \mathbb F_2 is het handig om te weten welke de irreducibele polynomen van lagere graad zijn. De situatie is vergelijkbaar met het zoeken naar priemgetallen. De irreducibele polynomen van lagere graad zijn:

  • graad 1: x en x + 1
  • graad 2: x^2 + x + 1 (de overige tweedegraadspolynomen zijn deelbaar door x, door x + 1, of beide; bv. x^2 + 1 = (x + 1)^2 over \mathbb F_2)
  • graad 3: x^3 + x + 1 en x^3 + x^2 + 1

Nu kan een irreducibel polynoom van de graad 4 worden gezocht. Een polynoom dat niet deelbaar is door bovengenoemde polynomen (en dus irreducibel is) is: p(x) = x^4 + x + 1. De vermenigvuldiging van twee elementen uit \mathbb F_{16}, voor te stellen door a_3 \alpha^3 + a_2 \alpha^2 + a_1 \alpha + a_0 en b_3 \alpha^3 + b_2 \alpha^2 + b_1 \alpha + b_0, is dus nu gedefinieerd door deze twee polynomen in \alpha met elkaar te vermenigvuldigen (over \mathbb F_2), en het resultaat te reduceren tot een derdegraads (of lager) polynoom in \alpha, gebruik makend van de identiteit p(\alpha) = \alpha^4 + \alpha + 1 = 0.

Externe link[bewerken]