sonlu alan - Finite field

In matematik , bir sonlu alan veya Galois alan (onuruna diye adlandırılan Évariste Galois ) bir olduğu saha sınırlı sayıda içerir elemanlar . Herhangi bir alanda olduğu gibi, bir sonlu alan a, dizi çarpma, toplama, çıkarma ve bölünme işlemleri tanımlanmış ve bazı temel kuralları yerine edildiği. Sonlu alanların en yaygın örnekleri, p bir asal sayı olduğunda mod p tam sayıları tarafından verilir .

Sonlu alanlar, sayı teorisi , cebirsel geometri , Galois teorisi , sonlu geometri , kriptografi ve kodlama teorisi dahil olmak üzere matematik ve bilgisayar biliminin birçok alanında temeldir .

Özellikler

Bir sonlu alan, bir alan olan sonlu bir kümedir ; bu, çarpma, toplama, çıkarma ve bölmenin (sıfıra bölme hariç) tanımlandığı ve alan aksiyomları olarak bilinen aritmetik kurallarına uyduğu anlamına gelir .

Sonlu bir alanın öğelerinin sayısına, düzeni veya bazen boyutu denir . q düzeyinde sonlu bir alan, ancak ve ancak q bir asal güç p ^{k ise mevcuttur} (burada p bir asal sayıdır ve k pozitif bir tamsayıdır). p ^k düzeyindeki bir alanda, herhangi bir öğenin p kopyalarının eklenmesi her zaman sıfırla sonuçlanır; olduğu, karakteristik alanı olan s .

Eğer q = p ^k , sipariş tüm alanları q olan izomorf (bkz § Varlık ve teklik altında). Ayrıca, bir alan aynı sırada iki farklı sonlu alt alan içeremez . Bir nedenle aynı sırada tüm sonlu alanlar tespit edebilir ve bunlar açık bir şekilde belirtilir , F _q ya GF ( q ) harfleri "Galois alanına" için ayakta GF. ${\displaystyle \mathbb {F} _{q}}$

Sipariş sınırlı bir alanda q , polinom X ^q - X, tüm sahip q, sonlu alan elemanları kökleri . Sonlu bir alanın sıfır olmayan öğeleri, çarpımsal bir grup oluşturur . Bu grup döngüseldir , bu nedenle sıfır olmayan tüm öğeler , alanın ilkel öğesi olarak adlandırılan tek bir öğenin güçleri olarak ifade edilebilir . (Genel olarak, belirli bir alan için birkaç ilkel öğe olacaktır.)

Sonlu alanların en basit örnekleri, asal mertebeden alanlardır: her p asal sayısı için , p , , mertebesindeki asal alan modulo p , Z / p Z tamsayıları olarak oluşturulabilir . ${\displaystyle \mathbb {F} _{p}}$

p dereceli asal alanın öğeleri 0, ..., p − 1 aralığında tam sayılarla temsil edilebilir . Toplanması, çıkarılması ve ürün olan dizgisinde ile p gelen tamsayıdır işleminin sonucu. Bir elemanın çarpımsal tersi, genişletilmiş Öklid algoritması kullanılarak hesaplanabilir (bkz. Genişletilmiş Öklid algoritması § Modüler tamsayılar ).

Let F sonlu alan olabilir. Her eleman için x in F ve herhangi bir tam sayı , n ile denote n ⋅ x toplamı n kopyaları x . En küçük pozitif N , öyle ki , n ⋅ 1 = 0 özelliğidir s alanının. Bu çarpma tanımlama, bir eleman , k ve GF ( p ) bir eleman ile x ve F için bir tamsayı temsil eden seçerek k . Bu çarpma yapan F bir içine GF ( p ) - vektör uzayı . Bazı n tam sayıları için F'nin eleman sayısının p ⁿ olduğu sonucu çıkar . ${\displaystyle (k,x)\mapsto k\cdot x}$

kimlik

${\görüntüleme stili (x+y)^{p}=x^{p}+y^{p}}$

(bazen birinci sınıf rüyası olarak adlandırılır ) karakteristik p alanında doğrudur . Bu, binom teoreminden kaynaklanmaktadır , çünkü ( x + y ) ^p'nin genişlemesinin her binom katsayısı , birinci ve son hariç, p'nin bir katıdır .

By Fermat'ın küçük teoremi ise, p bir asal sayı ve olduğu x saha içindedir GF ( p ) daha sonra x ^p = x . Bu eşitlik anlamına gelir

${\displaystyle X^{p}-X=\prod _{a\in {\rm {GF}}(p)}(Xa)}$

GF( p ) üzerindeki polinomlar için . Daha genel olarak, GF( p ⁿ ) içindeki her eleman x ^{p n} − x = 0 polinom denklemini sağlar .

Sonlu bir alanın herhangi bir sonlu alan uzantısı ayrılabilir ve basittir. Yani, E sonlu bir alan ve F , E'nin bir alt alanı ise , o zaman F'den , minimal polinomu ayrılabilir olan tek bir eleman birleştirilerek E elde edilir . Bir jargon kullanmak için, sonlu alanlar mükemmeldir .

Bir alanın diğer tüm aksiyomlarını karşılayan, ancak çarpımının değişmeli olması gerekmeyen daha genel bir cebirsel yapıya bölme halkası (veya bazen çarpık alan ) denir . Tarafından Wedderburn küçük teoremi , sonlu bölme halka değişmeli ve dolayısıyla sınırlı bir alandır.

Varlık ve benzersizlik

Let q = p ^{, n} bir olmak asal güç ve F olarak bölme alan polinom

${\görüntüleme stili P=X^{q}-X}$

asal alan üzerinde GF( p ) . Bu araçlar F olan en düşük düzeyde bir sonlu alan, bir P sahip q farklı kökleri ( resmi türevi bir P olan P ' = -1 , ima gcd ( P , P ' ) 1 = , genel olarak bu ima bölme alanı, orijinalin ayrılabilir bir uzantısıdır ). Yukarıdaki kimlik Şekil toplamı ve iki kök ürünü olup, bu P kökleri olan P , hem de bir kök çarpımsal ters P . Başka bir deyişle, P'nin kökleri , bölme alanının minimalliği ile F'ye eşit olan q düzeyinde bir alan oluşturur .

Bölme alanlarının eşbiçimliliğine kadar olan benzersizliği, böylece, q düzeyindeki tüm alanların eşbiçimli olduğunu ima eder . Ayrıca, bir F alanı alt alan olarak q = p ^k düzeyinde bir alana sahipse , öğeleri X ^q − X'in q kökleridir ve F , q düzeyinde başka bir alt alan içeremez .

Özetle, ilk olarak 1893'te EH Moore tarafından kanıtlanan aşağıdaki sınıflandırma teoremine sahibiz :

Sonlu bir alanın mertebesi asal bir güçtür. Her asal güç için q orada düzen alanları olan q , ve hepsi izomorfik. Bu alanlarda, her öğe tatmin edicidir

${\görüntüleme stili x^{q}=x,}$

ve polinom X ^q − X faktörleri olarak

${\displaystyle X^{q}-X=\prod _{a\in F}(Xa).}$

Bu izler , GF ( s ^{, n} ) izomorf bir alt alanı içeren GF ( s ^m ) ancak ve ancak m bir bölen bir n ; bu durumda, bu alt alan benzersizdir. Aslında, polinom x ^{p m} - X- bölme x ^{p , n} - X, ancak ve ancak m bir bölen bir n .

açık inşaat

Asal olmayan alanlar

p üssü ve n > 1 olan bir q = p ⁿ asal kuvveti verildiğinde , GF( q ) alanı aşağıdaki şekilde açıkça oluşturulabilir. Bir birinci tercih eden bir indirgenemez polinom P içinde GF ( s ) [ X ] derece , n (bir indirgenemez polinom her zaman var). Daha sonra bölüm halkası

${\displaystyle {\rm {GF}}(q)={\rm {GF}}(p)[X]/(P)}$

GF( p )[ X ] polinom halkasının P tarafından üretilen ideale göre q mertebesinde bir alandır .

Daha açık olarak, GF( q )' nin elemanları , derecesi kesinlikle n'den küçük olan GF( p ) üzerindeki polinomlardır . Toplama ve çıkarma, GF( p ) üzerindeki polinomlarınkilerdir . İki elemanın ürünün geri kalan kısmı olan Öklid bölünmesi ile P ürünün GF ( s [) X ] . Sıfır olmayan bir elemanın çarpımsal tersi genişletilmiş Öklid algoritması ile hesaplanabilir; bkz. Genişletilmiş Öklid algoritması § Basit cebirsel alan uzantıları .

GF(4)' ün oluşturulması dışında, P için izomorfik sonuçlar üreten birkaç olası seçenek vardır . Öklid bölünmesini basitleştirmek için, P için genel olarak formun polinomlarını seçer

${\displaystyle X^{n}+aX+b,}$

bu da gerekli Öklid bölümlerini çok verimli hale getirir. Bununla birlikte, tipik olarak karakteristik 2'deki bazı alanlar için, X ⁿ + aX + b biçimindeki indirgenemez polinomlar mevcut olmayabilir. Karakteristik 2'de , eğer X ⁿ + X + 1 polinomu indirgenebilir ise, polinomu indirgenemez yapan mümkün olan en düşük k ile X ⁿ + X ^k + 1'in seçilmesi tavsiye edilir . Tüm bu ise trinomials bir seçer "pentanomials" indirgenebilir olan X ^{, n} + X ^bir + x ^b + X ^C + 1 , daha derecesi arttıkça polinomlarla olarak 1 terimlerin çift sayısına sahip, karakteristik asla indirgenemeyen 2 sahip olan, 1 kök olarak.

Böyle bir polinom için olası bir seçim Conway polinomları tarafından verilmektedir . Bir alanın temsili ile alt alanlarının temsilleri arasında belirli bir uyumluluk sağlarlar.

Sonraki bölümlerde, yukarıda özetlenen genel yapım yönteminin küçük sonlu alanlar için nasıl çalıştığını göstereceğiz.

Dört elementli alan

Küçük olmayan birinci alan genel olarak gösterilen dört elemanları ile alandır GF (4) ya da dört öğeden oluşmaktadır şekilde ve her için başka bir işlem sonucu kolayca çıkarılabilir edilen dağıtım hakları . Tam çalışma tabloları için aşağıya bakın. ${\displaystyle \mathbb {F} _{4}.}$${\displaystyle 0,1,\alpha ,1+\alpha }$${\displaystyle \alpha ^{2}=1+\alpha ,}$ ${\displaystyle 1\cdot \alpha =\alpha \cdot 1=\alpha ,}$ ${\görüntüleme stili x+x=0,}$${\displaystyle x\cdot 0=0\cdot x=0,}$${\displaystyle x\in \operatöradı {GF} (4),}$

Bu, önceki bölümün sonuçlarından aşağıdaki gibi çıkarılabilir.

Üzeri GF (2) , sadece bir tane indirgenemez polinom derecesi2 :

${\displaystyle X^{2}+X+1}$

Bu nedenle, GF(4) için önceki bölümün yapısı bu polinomu içermelidir ve

${\displaystyle {\rm {GF}}(4)={\rm {GF}}(2)[X]/(X^{2}+X+1).}$

Let α bu polinomun anlamında olabildikleri, bir kök GF (4) . Bu, şu anlama gelir:

α ² = 1 + α ,

ve α ve 1 + α , GF(2)' de olmayan GF(4)' ün elemanlarıdır . GF(4)'teki işlemlerin tabloları bundan kaynaklanmaktadır ve aşağıdaki gibidir:

Toplama x + y	çarpma x ⋅ y	Bölüm x / y
x ╲ y 0 1 α 1 + α 0 0 1 α 1 + α 1 1 0 1 + α α α α 1 + α 0 1 1 + α 1 + α α 1 0	x ╲ y 0 1 α 1 + α 0 0 0 0 0 1 0 1 α 1 + α α 0 α 1 + α 1 1 + α 0 1 + α 1 α	x ╲ y 1 α 1 + α 0 0 0 0 1 1 1 + α α α α 1 1 + α 1 + α 1 + α α 1

Çıkarma eklenmesinden aynıdır, çünkü üçüncü bir tablo karakteristik 2'nin her alan için olduğu gibi çıkarma için bir tablo ayırma için, verilen değildir x ile y , değerleri , x , sol sütunda okunmalıdır , ve üst satırdaki y değerleri . (Çünkü 0 ⋅ z = 0 , her için z her halka , 0 ile bölme tanımlanmamıştır zorundadır.)

Harita

${\displaystyle \varphi :x\mapsto x^{2}}$

adı önemsiz olmayan alan otomorfizm olduğu Frobemino otomorfizm gönderir, α ikinci köküne 1 + α Yukarıda belirtilen indirgenemez polinom${\displaystyle X^{2}+X+1.}$

Tek bir asal p için GF( p ² )

GF( p ² ) durumunda sonlu alanların yukarıdaki genel yapısını uygulamak için , 2. dereceden indirgenemez bir polinom bulunmalıdır. p = 2 için , bu önceki bölümde yapılmıştır. Eğer p bir tek asal olan, her zaman bir şekilde indirgenemez polinomlar vardır x ² - r olan, r içinde GF ( s ) .

Daha kesin olarak, X ² − r polinomu GF( p ) üzerinden indirgenemez, ancak ve ancak r ikinci dereceden bir kalıntı olmayan modulo p ise (bu neredeyse ikinci dereceden kalıntı olmayanın tanımıdır). Var p - 1/2ikinci dereceden kalıntı olmayan modulo p . Örneğin, 2 , p = 3, 5, 11, 13, ... için ikinci dereceden bir kalıntı değildir ve 3 , p = 5, 7, 17, ... için ikinci dereceden bir kalıntı değildir . Eğer p ≡ 3 mod 4 olduğu, p = 3, 7, 11, 19, ... , tek bir seçim olabilir -1 ≡ p 1 - bizi çok basit indirgenemez polinom olması için izin veren bir ikinci derece olmayan artık halinde X ² +1 .

İkinci dereceden bir olmayan kalıntı seçilmiş, r , izin α sembolik karekökü r özelliğine sahip bir semboldür, α ² = r karmaşık sayısı ile aynı şekilde, I sembolik bir kare köküdür -1 . O halde, GF( p ² )' nin tüm elemanları lineer ifadelerdir.

${\ Displaystyle a+b\alpha ,}$

GF( p )' de a ve b ile . Üzerinde işlemler GF ( s ² ) (unsurları arasındaki işlemleri aşağıdaki gibi tanımlanmıştır GF ( s ) Latin harfleri temsil edilir işlemleri GF ( s ) ):

${\displaystyle {\begin{hizalı}-(a+b\alpha )&=-a+(-b)\alpha \\(a+b\alpha )+(c+d\alpha )&=(a+c )+(b+d)\alpha \\(a+b\alpha )(c+d\alpha )&=(ac+rbd)+(ad+bc)\alpha \\(a+b\alpha )^ {-1}&=a(a^{2}-rb^{2})^{-1}+(-b)(a^{2}-rb^{2})^{-1}\alpha \end{hizalanmış}}}$

GF(8) ve GF(27)

polinom

${\görüntüleme stili X^{3}-X-1}$

GF(2) ve GF(3) üzerinden indirgenemez , yani indirgenemez modulo 2 ve 3'tür (bunu göstermek için GF(2) veya GF(3)'te kökü olmadığını göstermek yeterlidir ). GF(8) ve GF(27) öğelerinin ifadelerle temsil edilebileceği sonucu çıkar.

${\displaystyle a+b\alpha +c\alpha ^{2},}$

burada a , b , c GF(2) veya GF(3)'ün (sırasıyla) öğeleridir ve öyle bir semboldür ki ${\görüntüleme stili \alfa }$

${\displaystyle \alpha ^{3}=\alpha +1.}$

GF(8) ve GF(27) üzerindeki toplama, toplamalı ters ve çarpma böylece aşağıdaki gibi tanımlanabilir; Aşağıdaki formüllerde, Latin harfleriyle temsil edilen GF(2) veya GF(3) öğeleri arasındaki işlemler , sırasıyla GF(2) veya GF(3) içindeki işlemlerdir :

${\displaystyle {\begin{hizalı}-(a+b\alpha +c\alpha ^{2})&=-a+(-b)\alpha +(-c)\alpha ^{2}\qquad {\ metin{(}}\mathrm {GF} (8 için),{\text{bu işlem kimliktir)}}\\(a+b\alpha +c\alpha ^{2})+(d+e\ alpha +f\alpha ^{2})&=(a+d)+(b+e)\alpha +(c+f)\alpha ^{2}\\(a+b\alpha +c\alpha ^ {2})(d+e\alpha +f\alpha ^{2})&=(ad+bf+ce)+(ae+bd+bf+ce+cf)\alpha +(af+be+cd+ cf)\alpha ^{2}\end{hizalı}}}$

GF(16)

polinom

${\displaystyle X^{4}+X+1}$

GF(2) üzerinden indirgenemez , yani indirgenemez modulo 2'dir . GF(16) öğelerinin ifadelerle temsil edilebileceği sonucu çıkar.

${\displaystyle a+b\alpha +c\alpha ^{2}+d\alpha ^{3},}$

burada bir , b , c , d her olan 0 veya 1 (unsurları GF (2) ) ve α böyle bir semboldür

${\displaystyle \alpha ^{4}=\alpha +1}$

(yani, α , verilen indirgenemez polinomun bir kökü olarak tanımlanır). Karakteristik olarak GF (2) olan 2 , her bir öğe olarak katık tersidir GF (16) . GF(16) üzerindeki toplama ve çarpma işlemi aşağıdaki gibi tanımlanabilir; aşağıdaki formüllerde, elemanları arasındaki işlemleri GF (2) Latin harfleri ile temsil edilen, içinde işlemlerdir GF (2) .

${\displaystyle {\begin{hizalanmış}(a+b\alpha +c\alpha ^{2}+d\alpha ^{3})+(e+f\alpha +g\alpha ^{2}+h\ alpha ^{3})&=(a+e)+(b+f)\alpha +(c+g)\alpha ^{2}+(d+h)\alpha ^{3}\\(a+ b\alpha +c\alpha ^{2}+d\alpha ^{3})(e+f\alpha +g\alpha ^{2}+h\alpha ^{3})&=(ae+bh+ cg+df)+(af+be+bh+cg+df+ch+dg)\alpha \;+\\&\quad \;(ag+bf+ce+ch+dg+dh)\alpha ^{2 }+(ah+bg+cf+de+dh)\alpha ^{3}\end{hizalı}}}$

çarpımsal yapı

GF( q )' deki sıfır olmayan elemanlar kümesi, q – 1 sıralı çarpma altında bir değişmeli gruptur . Tarafından Lagrange teoremi , bölen vardır k ve q 1 - bu şekilde X ^k = 1 , her sıfır olmayan için x de GF ( q ) . x ^k = 1 denkleminin herhangi bir alanda en fazla k çözümü olduğundan, q – 1 , k için mümkün olan en düşük değerdir . Sonlu değişmeli grupların yapı teoremi bu çarpımsal grubu olduğu anlamına gelir siklik olduğu, sıfır olmayan tüm elemanlar tek bir elemanın güçler. Özetle:

Sıfır olmayan elemanları çarpımsal grubu GF ( q ) , siklik, ve bir element vardır a , öyle ki q - 1 sıfır olmayan elemanları, GF ( q ) olan bir , bir ² , ..., bir ^{q −2} , bir ^{q −1} = 1 .

Böyle bir eleman , bir denen ilkel eleman . q = 2, 3 olmadıkça , ilkel eleman benzersiz değildir. İlkel öğelerin sayısı φ ( q − 1)'dir, burada φ , Euler'in totient işlevidir .

Yukarıdaki sonuç , GF( q ) içindeki her x için x ^q = x olduğunu gösterir . q'nun asal olduğu özel durum Fermat'ın küçük teoremidir .

ayrık logaritma

Eğer bir ilkel elemandır GF ( q ) , daha sonra herhangi bir sıfır olmayan eleman için , x in F , benzersiz bir tam sayı olduğu N ile 0 ≤ n ≤ q - 2 olacak şekilde

x = bir ⁿ .

Bu tam sayı , n olarak adlandırılır ayrık logaritma ait x baza a .

Birlikte bir ⁿ kullanılarak, örneğin, çok hızlı bir şekilde hesaplanabilir karesi alınarak üs , herhangi bir ters işlemini, ayrık logaritmasını hesaplanması için etkili bir yöntem bilinmekte olup. Bu çeşitli kullanılmıştır kriptografik protokoller , bkz Ayrık logaritma detayları için.

GF( q ) ' nin sıfır olmayan elemanları ayrık logaritmalarıyla temsil edildiğinde, toplama ve çıkarma modulo q - 1'e düştükleri için çarpma ve bölme kolaydır . Bununla birlikte, toplama, a ^m + a ^n'nin ayrık logaritmasının hesaplanması anlamına gelir . Kimlik

bir ^m + bir ⁿ = bir ⁿ ( bir ^{m - n} + 1)

n = 0, ..., q − 2 için bir ⁿ + 1'in ayrık logaritmalarının tablosunu oluşturarak bu problemi çözmeye izin verir , Zech'in logaritmaları denir (sıfırın ayrık logaritmasını şu şekilde tanımlamak uygundur : ∞ ).

Zech'in logaritmaları, orta büyüklükteki alanlar üzerindeki doğrusal cebir , yani doğal algoritmaları verimsiz hale getirmek için yeterince büyük, ancak aynı boyutta bir tabloyu önceden hesaplamak zorunda olduğu için çok büyük olmayan alanlar gibi büyük hesaplamalar için kullanışlıdır. alanın sırası olarak.

birliğin kökleri

GF( q ) ' nin sıfır olmayan her elemanı için x ^{q −1} = 1 gibi, sonlu bir alanın sıfır olmayan her elemanı birliğin köküdür .

Eğer , n pozitif bir tamsayıdır, bir bir n- inci birlik ilkel kök denkleminin bir çözüm x ^{, n} = 1 denklemi bir çözüm değildir x ^m = 1 , herhangi bir pozitif tam sayı için m < n . Eğer bir a, n, bir alan birlik ilkel kök inci F , daha sonra F tümünü içeren N olan birlik kökleri, 1, bir , bir ² , ..., bir ^{N -1} .

Alan GF ( q ) bir içermektedir n birlik ilkel kök inci ancak ve ancak n, bir bölen bir q - 1 ; Eğer n, bir bölen bir q - 1 , daha sonra ilk sayısı n birlik inci kökleri GF ( q ) olan φ ( n ) ( totient ). Sayısı , n birlik inci kökleri GF ( q ) olan gcd ( n , q - 1) .

Bir p karakteristiği alanında, birliğin her ( np ) inci kökü aynı zamanda birliğin n inci köküdür. Birliğin ilkel ( np ) köklerinin p özelliğinin bir alanında asla var olmadığı sonucu çıkar .

Diğer yandan, eğer , n olan göreceli asal için p , kökleri n inci devirli polinom karakteristik her alanında farklı olan p Bu polinom bir bölen olarak, X ^{, n} 1 - , olan ayırt edici sıfır olmayan bir modül olup s . Bu izler , n inci devirli polinom fazla faktörler GF ( p ) aynı derecede, söz sahibi tat indirgenemez polinom içine d ve bu GF ( s ^d ) karakteristik en küçük alanı olan p içeren N inci ilkel kök birlik. ${\görüntüleme stili n^{n}}$

Örnek: GF(64)

GF(64) alanı , daha küçük alanların paylaşmadığı birkaç ilginç özelliğe sahiptir: iki alt alanı vardır, öyle ki hiçbiri diğerinde yer almaz; tüm üreteçler ( en az polinom derecesi 6'ya göre GF(2 ) olan öğeler) ilkel öğeler değildir; ve ilkel öğelerin tümü Galois grubu altında eşlenik değildir .

Olmak bu alanda sırası 2 ⁶ , ve bölenler 6 olan 1, 2, 3, 6 bölgesinin alt alanlar GF (64) olan GF (2) , GF (2 ² ) = GF (4) , GF (2 ³ ) = GF(8) ve GF(64)'ün kendisi. Olarak 2 ve 3 olan göreceli asal , kesişme GF (4) ve GF (8) içinde GF (64) ana bir alandır GF (2) .

GF(4) ve GF(8) ' in birleşimi bu nedenle 10 elemana sahiptir. Geri kalan 54 elemanları GF (64) oluşturmak (64) GF başka bir alt alan bunlardan herhangi birini içeren anlamında. Onlar derece indirgenemez polinomların kökleri olduğu aşağıdaki 6 üzerinde GF (2) . Bu, GF(2) üzerinde tam olarak 9 = olduğu anlamına gelir.54/66. dereceden indirgenemez monik polinomlar . Bu, X ⁶⁴ − X'i GF(2) üzerinden çarpanlara ayırarak doğrulanabilir .

Elemanları GF (64) ilkel n bazıları için birlik kökleri inci n bölünmesi 63 . 3 ve aittir birlik 7. kökleri olarak GF (4) ve GF (8) , sırasıyla, 54 jeneratör ilkel n bazıları için birlik inci kökleri n olarak {9, 21, 63} . Totient olduğu Şekil 6 ilk 9 birlik inci kökleri, 12 ilkel 21 birlik st kökler ve 36 ilk 63 birlik üçüncü kökleri. Bu sayıları toplarsak yine 54 element bulunur.

Siklotomik polinomları GF(2) üzerinden çarpanlarına ayırarak şunları buluruz :

• Birliğin altı ilkel 9. kökü, birliğin kökleridir.

${\displaystyle X^{6}+X^{3}+1,}$

ve hepsi Galois grubunun etkisi altında konjugedir.

• Birliğin on iki ilkel 21. kökü, birliğin kökleridir.

${\displaystyle (X^{6}+X^{4}+X^{2}+X+1)(X^{6}+X^{5}+X^{4}+X^{2} +1).}$

Galois grubunun etkisi altında iki yörünge oluştururlar. İki faktör birbirine karşılıklı olduğundan, bir kök ve onun (çarpımsal) tersi aynı yörüngeye ait değildir.

• 36 ilkel elemanları GF (64) kökleri olan

${\displaystyle (X^{6}+X^{4}+X^{3}+X+1)(X^{6}+X+1)(X^{6}+X^{5}+ 1)(X^{6}+X^{5}+X^{3}+X^{2}+1)(X^{6}+X^{5}+X^{2}+X+ 1)(X^{6}+X^{5}+X^{4}+X+1),}$

Galois grubunun etkisi altında 6 elementten oluşan 6 yörüngeye ayrıldılar.

Bu, GF(64) oluşturmak için en iyi seçimin onu GF(2)[ X ] / ( X ⁶ + X + 1) olarak tanımlamak olduğunu gösterir . Aslında bu üreteç ilkel bir elemandır ve bu polinom en kolay Öklid bölünmesini üreten indirgenemez polinomdur.

Frobenius otomorfizmi ve Galois teorisi

Bu bölümde, p bir asal sayıdır ve q = p ⁿ , p'nin bir kuvvetidir .

Gelen GF ( q ) , kimlik ( x + y ) ^p = X ^P + y ^p harita ima

${\displaystyle \varphi :x\mapsto x^{p}}$

a, GF ( p ) - doğrusal Endomorfizma ve alan otomorfizm arasında GF ( q ) alt alan her eleman giderir, GF ( s ) . Buna Ferdinand Georg Frobenius'tan sonra Frobenius otomorfizmi denir .

Tarafından belirten cp ^k kompozisyon ve cp kendisiyle k Elimizdeki, süreleri

${\displaystyle \varphi ^{k}:x\mapsto x^{p^{k}}.}$

Önceki bölümde φ ^n'nin özdeşlik olduğu gösterilmiştir. İçin 0 < k < N , otomorfizm φ ^k , kimlik değildir, aksine, polinom

${\displaystyle X^{p^{k}}-X}$

p ^k'den fazla köke sahip olacaktır .

GF( q ) ' nin başka GF( p ) -otomorfizmi yoktur . Başka bir deyişle, GF( p ⁿ ) tam olarak n tane GF( p ) -otomorfizmine sahiptir.

${\displaystyle \mathrm {Id} =\varphi ^{0},\varphi ,\varphi ^{2},\ldots ,\varphi ^{n-1}.}$

Galois teorisi açısından bu, GF( p ⁿ )' nin siklik bir Galois grubuna sahip olan GF( p )' nin bir Galois uzantısı olduğu anlamına gelir .

Frobenius haritasının örtük olması, her sonlu alanın mükemmel olduğunu ima eder .

polinom çarpanlara ayırma

Eğer F sonlu bir alandır, sabit olmayan bir mghorta polinom katsayılı F olduğu indirgenemez üzerinde F içeri katsayıları ile iki sabit olmayan mghorta polinomların ürünü değilse, F .

Bir alan üzerindeki her polinom halkası benzersiz bir çarpanlara ayırma alanı olduğundan , sonlu bir alan üzerindeki her monik polinom, benzersiz bir şekilde (faktörlerin sırasına göre) indirgenemez monik polinomların bir ürününe çarpanlarına ayrılabilir.

Polinomların indirgenemezliğini test etmek ve polinomları sonlu alan üzerinde çarpanlarına ayırmak için etkili algoritmalar vardır. Polinomları tamsayılar veya rasyonel sayılar üzerinde çarpanlara ayırmada önemli bir adımdır . En azından bu nedenle, her bilgisayar cebir sistemi , polinomları sonlu alanlar veya en azından sonlu asal alanlar üzerinde çarpanlarına ayırma işlevlerine sahiptir.

Belirli bir derecede indirgenemez polinomlar

polinom

${\görüntüleme stili X^{q}-X}$

faktörleri, q dereceli bir alan üzerinde doğrusal faktörlere dönüştürür . Daha kesin olarak, bu polinom, q dereceli bir alan üzerinde birinci dereceden tüm monik polinomların ürünüdür .

Bu da, anlaşılacağı eğer q = p ^{, n} , sonra X ^q - X, yerinden mghorta indirgenemez polinomların ürünü olan GF ( p ) derecesi bölme, n . Aslında, eğer P üzerinde indirgenemez faktördür GF ( p ) ve X- ^q - X , derecesi bölme n onun kadar, bölme alanı içerdiği GF ( s ^{, n} ) . Tersine, eğer P üzerinde indirgenemez mghorta polinom GF ( p ) derecesi d bölünmesi , n , o derece bir alan uzantısına tanımlayan d içerdiği, GF ( s ^{, n} ) ve her kökleri P aittir GF ( s ⁿ ) ve X ^q - X'in kökleridir ; böylece P , X ^q − X'i böler . Olarak X- ^q - X, herhangi çoklu faktörü yoktur, bu nedenle bu bölen indirgenemez mghorta polinomların ürünüdür.

Bu özellik, her bir polinom derecesinin indirgenemez faktörlerinin çarpımını GF( p ) üzerinden hesaplamak için kullanılır ; bkz. Farklı derece çarpanlarına ayırma .

Sonlu bir alan üzerinde belirli bir derecede monik indirgenemez polinomların sayısı

Sayısı , N ( q , n ) derecesi mghorta indirgenemez polinomların n üzerindeki GF ( q ) ile verilir

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

burada μ olan Möbiüs işlevi . Bu formül, X ^q - X'in yukarıdaki özelliğinin neredeyse doğrudan bir sonucudur .

Yukarıdaki formüle göre, n derecesi bölü GF( q ) olan indirgenemez (mutlaka monik olmayan) polinomların sayısı ( q − 1) N ( q , n ) 'dir .

Bir (biraz daha basit) için alt sınır , N ( q , n ) bir

${\displaystyle N(q,n)\geq {\frac {1}{n}}\left(q^{n}-\sum _{p\mid n,\ p{\text{ asal}}}q ^{n/p}\sağ).}$

Her q ve her n için , en az bir indirgenemez dereceli n bölü GF( q ) polinomu olduğu kolayca çıkarılabilir . Bu alt sınır q = n = 2 için keskindir .

Uygulamalar

Gelen kriptografi , zorluğu diskre logaritma problemi sonlu alanlarda veya eliptik eğri gibi çeşitli yaygın olarak kullanılan protokoller, temelidir Diffie-Hellman protokolü. Örneğin, 2014'te Wikipedia'ya güvenli bir internet bağlantısı, geniş bir sonlu alan üzerinde Diffie-Hellman protokolü ( ECDHE ) eliptik eğrisini içeriyordu . Olarak kodlama teorisi , bir çok kod olarak teşkil edilmiştir bölme odasının bir vektör uzayı sonlu cisimler üzerinde.

Sonlu alanlar, Reed–Solomon hata düzeltme kodu veya BCH kodu gibi birçok hata düzeltme kodu tarafından kullanılır . Bilgisayar verileri ikili dosyada depolandığından, sonlu alan hemen hemen her zaman 2 özelliğine sahiptir. Örneğin, bir bayt veri, öğesinin bir öğesi olarak yorumlanabilir . Bir istisna PDF417 barkod vardır . Bazı CPU'larda, karakteristik 2'nin sonlu alanları, genellikle taşımasız ürün çeşitleri için faydalı olabilecek özel talimatlar bulunur . ${\ Displaystyle GF(2^{8})}$${\ Displaystyle GF(929)}$

Sonlu alanlar sayı teorisinde yaygın olarak kullanılmaktadır , çünkü tamsayılar üzerindeki birçok problem, onları bir veya birkaç asal sayının modulo azaltılarak çözülebilir . Örneğin, polinom çarpanlara ayırma ve rasyonel sayılar alanı üzerindeki lineer cebir için bilinen en hızlı algoritmalar, bir veya birkaç asal sayı indirgeme modulo ile ilerler ve daha sonra Çin kalan teoremi , Hensel kaldırma veya LLL algoritması kullanılarak çözümün yeniden yapılandırılmasıyla ilerler .

Benzer şekilde, sayılar teorisindeki birçok teorik problem, asal sayıların bazılarının veya tümünün modülo indirgemeleri dikkate alınarak çözülebilir. Örneğin, Hasse ilkesine bakın . Cebirsel geometrideki birçok yeni gelişme , bu modüler yöntemlerin gücünü artırma ihtiyacıyla motive edildi. Wiles'ın Fermat'ın Son Teoreminin kanıtı, sonlu alanlar da dahil olmak üzere birçok matematiksel aracı içeren derin bir sonucun bir örneğidir.

Weil varsayımlar üzerine noktalarının sayısını ilgilendiren cebirsel çeşitlerinin Sonlu cisimler üzerinde ve teori gibi birçok uygulamaları vardır üstel ve karakter toplamı tahminleri.

Sonlu alanlar kombinatorikte yaygın bir uygulamaya sahiptir , iki iyi bilinen örnek Paley Grafiklerinin tanımı ve Hadamard Matrisleri için ilgili yapıdır . Gelen aritmetik kombinatorik alanları ve sonlu alan modeller böyle olduğu gibi, yaygın olarak kullanılmaktadır sonlu Szemeredi'nin teoremi aritmetik olarak geliştirmeye.

Uzantılar

cebirsel kapatma

Sonlu bir F alanı cebirsel olarak kapalı değildir: polinom

${\displaystyle f(T)=1+\prod _{\alpha \in F}(T-\alpha ),}$

kökleri yoktur F , çünkü f  ( α ) 1 = tüm a olarak F .

Bir Fix cebirsel kapatılması arasında . Haritası her gönderme x etmek x ^q denir q güç inci Frobemino otomorfizm . Bir alt alanı ile sabit n ve yineleme inci polinom sıfırlarının dizi x ^{q , n} - X , onun türevi yana farklı kökleri olan bir -1 , hiç bir zaman sıfır olan. Bu nedenle alt alanı vardır q ⁿ elemanları, bu nedenle eşsiz kopyasıdır içinde . Her sonlu uzatma in bu bazıları için n böylece, ${\displaystyle {\overline {\mathbb {F} }}_{q}}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle \varphi _{q}\kolon {\overline {\mathbb {F} }}_{q}\to {\overline {\mathbb {F} }}_{q}}$${\displaystyle {\overline {\mathbb {F} }}_{q}}$${\displaystyle \varphi _{q}}$${\displaystyle \mathbb {F} _{q}[x]}$${\displaystyle \mathbb {F} _{q^{n}}}$${\displaystyle {\overline {\mathbb {F} }}_{q}}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle {\overline {\mathbb {F} }}_{q}}$${\displaystyle \mathbb {F} _{q^{n}}}$

${\displaystyle {\overline {\mathbb {F}}}_{q}=\bigcup _{n\geq 1}\mathbb {F} _{q^{n}}.}$

Mutlak Galois'in grubu arasında olduğu profinite grubu${\displaystyle \mathbb {F} _{q}}$

${\displaystyle \operatorname {Gal} ({\overline {\mathbb {F}}}_{q}/\mathbb {F} _{q})\simeq \varprojlim _{n}\operatorname {Gal} ({ \overline {\mathbb {F} }}_{q^{n}}/\mathbb {F} _{q})\simeq \varprojlim _{n}(\mathbf {Z} /n\mathbf {Z} )={\widehat {\mathbf {Z} }}.}$

Herhangi bir sonsuz Galois grubu gibi, Krull topolojisi ile donatılabilir ve o zaman az önce verilen izomorfizmler, topolojik grupların izomorfizmleridir . Görüntü grubunda jeneratör 1 , yani karşılık gelen . O şöyle sonsuz düzeni vardır ve yoğun bir alt grubunu oluşturur eleman, çünkü değil bütün grup, sonsuz düzeni vardır ve yoğun alt grup üretir biri diyor bir topolojik jeneratör . ${\displaystyle \operatöradı {Gal} ({\overline {\mathbb {F} }}_{q}/\mathbb {F} _{q})}$${\displaystyle \varphi _{q}}$${\displaystyle \operatorname {Gal} ({\overline {\mathbb {F} }}_{q^{n}}/\mathbb {F} _{q})\simeq \mathbf {Z} /n\mathbf {Z} }$${\displaystyle \varphi _{q}}$${\displaystyle 1\in {\widehat {\mathbf {Z}}}}$${\displaystyle \varphi _{q}}$${\displaystyle \operatöradı {Gal} ({\overline {\mathbb {F} }}_{q}/\mathbb {F} _{q})}$${\displaystyle 1\in {\widehat {\mathbf {Z}}}}$${\displaystyle \mathbf {Z} \subsetneqq {\widehat {\mathbf {Z} }}.}$${\displaystyle \varphi _{q}}$${\displaystyle \operatöradı {Gal} ({\overline {\mathbb {F} }}_{q}/\mathbb {F} _{q})}$

Yarı cebirsel kapatma

Sonlu alanlar cebirsel olarak kapalı olmasa da, yarı cebirsel olarak kapalıdır , yani sonlu bir alan üzerindeki her homojen polinom , değişkenlerinin sayısı derecesinden fazlaysa bileşenleri alanda olan önemsiz bir sıfıra sahiptir. Bu, Chevalley tarafından kanıtlanan Artin ve Dickson'ın bir varsayımıydı (bkz. Chevalley-Uyarı teoremi ).

Wedderburn'ün küçük teoremi

Bir bölme halka alanı bir genellemedir. Bölme halkalarının değişmeli olduğu varsayılmaz. Değişmeli olmayan sonlu bölme halkaları yoktur: Wedderburn'ün küçük teoremi , tüm sonlu bölme halkalarının değişmeli, dolayısıyla sonlu alanlar olduğunu belirtir . Biz birleşim dinlenmek ve dikkate sonuçlar çok tutan alternatif halkaları tarafından, Artin-Zorn teoremi .

Ayrıca bakınız

• yarı-sonlu alan
• Tek elemanlı alan
• sonlu alan aritmetiği
• sonlu halka
• sonlu grup
• Temel değişmeli grup
• Hamming alanı

Notlar

Referanslar

Dış bağlantılar

• Wolfram araştırmasında Sonlu Alanlar .