Шешікті өрістер және Галуа өрістері

Кіріспе

Алгебралық құрылым

Математикада, шекті өріс немесе Галуа өрісі (Эварист Галуаның құрметіне аталған) – шекті сандағы элементтерді қамтитын өріс. Кез келген өріс сияқты, шекті өріс – көбейту, қосу, алу және бөлу амалдары анықталған және белгілі бір негізгі қағидаларды қанағаттандыратын жиын. Шекті өрістердің ең көп таралған мысалдары, p жай сан болғанда, p-модуль бойынша бүтін сандармен беріледі. Шекті өрістің реті – оның элементтерінің саны, ол жай сан немесе жай санның дәрежесі болуы мүмкін. Кез келген жай сан p және кез келген оң бүтін сан k үшін p^k реті бар өрістер бар, олардың барлығы изоморфты. Шекті өрістер математика мен компьютерлік ғылымның көптеген салаларында, оның ішінде сандар теориясы, алгебралық геометрия, Галуа теориясы, шекті геометрия, криптография және кодтау теориясында маңызды рөл атқарады.

Негізгі емес өрістер

1=q = p^(n) жай санның дәрежесі p және n > 1 болғанда, GF(q) өрісі келесідей жасалуы мүмкін. Біріншіден, GF(p)[X] ішінде n дәрежелі қайталанбайтын P көпмүшесі таңдалады (мұндай қайталанбайтын көпмүше әрқашан болады). Содан кейін, GF(p)[X] көпмүшелік сақинасының P-ден туындаған идеалға қатысты бөлу сақинасы q реттік өріс болады. Нақтырақ айтқанда, GF(q) элементтері – GF(p) үстінен n-ден кіші дәрежелі көпмүшелер. Қосу және алу GF(p) үстінен көпмүшелер үшін орындалады. Екі элементтің көбейтіндісі – GF(p)[X] көбейтіндісін P-ге бөлгендегі қалдық. Нөлдік емес элементтің кері шамасы кеңейтілген Евклид алгоритмімен есептелуі мүмкін; қараңыз. Дегенмен, осы бейнелеуде GF(q) элементтерін сәйкес келетін көпмүшелерден ажырату қиын болуы мүмкін. Сондықтан, GF(q) өрісіндегі X көпмүшесіне сәйкес келетін α атауын беру қалыпты жағдай. Осылайша, GF(q) элементтері α арқылы берілетін көпмүшелерге айналады, мұнда 1=P(α) = 0 және α-дағы n-ден жоғары немесе тең дәрежелі көпмүшеге кездескенде (мысалы, көбейтуден кейін), оның дәрежесін төмендету үшін 1=P(α) = 0 қатынасын қолдану қажеттігін білеміз (бұл Евклидтік бөлудің мәні). GF(4) өрісін құрудан басқа, P үшін бірнеше мүмкін таңдаулар бар, олар изоморфты нәтижелер береді. Евклидтік бөлуді жеңілдету үшін, P үшін қажетті Евклидтік бөлуді тиімді етуге мүмкіндік беретін формадағы көпмүше таңдалады. Алайда, кейбір өрістер үшін, әсіресе екілік өрісте, X^(n) + aX + b түріндегі қайталанбайтын көпмүшелер болмауы мүмкін. Екілік өрісте, егер X^(n) + X + 1 көпмүшесі қайталанатын болса, X^(n) + X^(k) + 1 көпмүшесін таңдау ұсынылады, мұнда k мүмкіндігінше төмен болуы керек, сонда көпмүше қайталанбайды. Егер осы үшмүшелердің барлығы қайталанатын болса, онда "бесмүшелерді" таңдайды: X^(n) + X^(a) + X^(b) + X^(c) + 1, өйткені екілік өрісте 1-ден жоғары дәрежелі және жұп санды мүшелері бар көпмүшелер 1 түбірі болғандықтан қайталанбайды. Мұндай көпмүшелердің мысалы Конвей көпмүшелері болып табылады. Олар өріс пен оның ішкі өрістерінің бейнелеуі арасындағы үйлесімділікті қамтамасыз етеді. Келесі бөлімдерде жоғарыда сипатталған жалпы құрылыс әдісінің кішкентай шекті өрістер үшін қалай жұмыс істейтінін көрсетеміз.

Given a prime power 1=q = p^(n) with p prime and n > 1, the field GF(q) may be explicitly constructed in the following way. One first chooses an irreducible polynomial P in GF(p)[X] of degree n (such an irreducible polynomial always exists). Then the quotient ring

of the polynomial ring GF(p)[X] by the ideal generated by P is a field of order q. More explicitly, the elements of GF(q) are the polynomials over GF(p) whose degree is strictly less than n. The addition and the subtraction are those of polynomials over GF(p). The product of two elements is the remainder of the Euclidean division by P of the product in GF(p)[X]. The multiplicative inverse of a non zero element may be computed with the extended Euclidean algorithm; see
However, with this representation, elements of GF(q) may be difficult to distinguish from the corresponding polynomials. Therefore, it is common to give a name, commonly α to the element of GF(q) that corresponds to the polynomial X. So, the elements of GF(q) become polynomials in α, where 1=P(α) = 0, and, when one encounters a polynomial in α of degree greater or equal to n (for example after a multiplication), one knows that one has to use the relation 1=P(α) = 0 to reduce its degree (it is what Euclidean division is doing). Except in the construction of GF(4), there are several possible choices for P, which produce isomorphic results. To simplify the Euclidean division, one commonly chooses for P a polynomial of the form

which make the needed Euclidean divisions very efficient. However, for some fields, typically in characteristic 2, irreducible polynomials of the form X^(n) + aX + b may not exist. In characteristic 2, if the polynomial X^(n) + X + 1 is reducible, it is recommended to choose X^(n) + X^(k) + 1 with the lowest possible k that makes the polynomial irreducible. If all these trinomials are reducible, one chooses "pentanomials" X^(n) + X^(a) + X^(b) + X^(c) + 1, as polynomials of degree greater than 1, with an even number of terms, are never irreducible in characteristic 2, having 1 as a root. A possible choice for such a polynomial is given by Conway polynomials. They ensure a certain compatibility between the representation of a field and the representations of its subfields. In the next sections, we will show how the general construction method outlined above works for small finite fields.

GF(p2) тақ жай p үшін

GF(p^(2)) жағдайында шекті өрістердің жоғарыда аталған жалпы құрылымын қолдану үшін 2-дәрежелі қайталанбайтын көптік табу керек. p = 2 үшін бұл алдыңғы бөлімде орындалды. Егер p - тақ сан болса, онда әрқашан X^(2) − r түріндегі қайталанбайтын көптіктер болады, мұнда r GF(p) өрісінде. Нақтырақ айтқанда, X^(2) − r көптігі GF(p) бойынша қайталанбайды, егер және тек егер r, p модулі бойынша квадраттық қалдықсыз болса (бұл квадраттық қалдықсыздың дерлік анықтамасы). p модулі бойынша квадраттық қалдықсыз сандар бар. Мысалы, 2, p = 3, 5, 11, 13 үшін квадраттық қалдықсыз, ал 3, p = 5, 7, 17 үшін квадраттық қалдықсыз. Егер p ≡ 3 (mod 4), яғни p = 3, 7, 11, 19, болса, онда квадраттық қалдықсыз ретінде −1 ≡ p − 1 таңдауға болады, бұл X^(2) + 1 өте қарапайым қайталанбайтын көптік болуына мүмкіндік береді. Квадраттық қалдықсыз r таңдалғаннан кейін, α r-дың символды квадрат түбірі болсын, яғни α^(2) = r қасиетіне ие символ, дәл i кешенді санының −1 символды квадрат түбірі сияқты. Онда GF(p^(2)) элементтері GF(p) өрісіндегі a және b элементтері бар барлық сызықтық өрнектер болады. GF(p^(2)) өрісіндегі амалдар келесідей анықталады (GF(p) өрісіндегі элементтер арасындағы амалдар GF(p) өрісіндегі амалдар болып табылады):

Көбейту құрылымы

GF(q) -дегі нөлдік емес элементтер жиыны көбейту бойынша q-1 реттік абель тобы болып табылады. Лагранж теоремасы бойынша, q-1 санының k бөлгіші бар, сондықтан GF(q) -дағы әрбір нөлдік емес x үшін 1=x^k=1 теңдігі орындалады. Кез келген өрісте 1=x^k=1 теңдеуінің шешімі ең көп дегенде k болуы мүмкін, сондықтан q-1 саны k үшін ең төменгі мүмкін мән болып табылады. Шектеулі абельдік топтардың құрылым теоремасы осы көбейтуші топтың циклдік екенін көрсетеді, яғни барлық нөлдік емес элементтер бір элементтің дәрежелері болып табылады. Қорыта айтқанда:

Мұндай элемент a, GF(q) -ның түпнұсқалық элементі деп аталады. Егер q=2, 3 болмаса, түпнұсқалық элемент бірегей емес. Түпнұсқалық элементтердің саны φ(q-1) тең, мұнда φ – Эйлердің тотиент функциясы. Жоғарыдағы нәтиже GF(q) -дағы әрбір x үшін 1=x^q=x екенін білдіреді. q саны жай сан болғандағы ерекше жағдай Ферманың кішкентай теоремасы болып табылады.

Бірліктің негізі

Шекті өрістің нөлден өзге әрбір елемі біртүбір болып табылады, себебі 1=x^(q−1) = 1 GF(q)-ның нөлден өзге әрбір елемі үшін. Егер n – оң бүтін сан болса, n-ші примитивті біртүбір – 1=x^(n) = 1 теңдеуінің шешімі, бірақ ол 1=x^(m) = 1 теңдеуінің шешімі емес, мұндағы m – кез келген оң бүтін сан және m < n. Егер a – F өрісіндегі n-ші примитивті біртүбір болса, онда F өрісі біртүбірдің барлық n түбірін қамтиды, яғни 1, a, a^(2), ..., a^(n−1). GF(q) өрісінде n-ші примитивті біртүбірлердің саны φ(n) (Эйлердің тотиент функциясы) құрайды, егер ғана n, q – 1-дің бөлгіші болса; ал егер n, q – 1-дің бөлгіші болса, онда GF(q)-дағы біртүбірдің n-ші дәрежесінің саны gcd(n, q − 1)-ге тең. p сипаттамасы бар өрісте, біртүбірдің әрбір (np)-ші дәрежесі де біртүбірдің n-ші дәрежесі болып табылады. Осыдан, p сипаттамасы бар өрісте примитивті (np)-ші біртүбірлер болмайды.

Екінші жағынан, егер n, p-ге өзіндік болса, n-ші циклотомиялық полиномның түбірлері p сипаттамасы бар кез келген өрісте ерекшеленеді, себебі бұл полином X^(n) − 1-дің бөлгіші болып табылады, ал оның дискриминанты n^(n) p модулі бойынша нөлге тең емес. Осыдан, n-ші циклотомиялық полином GF(p) бойынша әртүрлі иррационалды полиномдарға жіктеледі, олардың барлығы бірдей дәрежеге ие, мысалы, d, және GF(p^(d)) – n-ші примитивті біртүбірді қамтитын ең кіші p сипаттамасы бар өріс.

Көптамалық факторлау

Егер F – шекті өріс болса, онда F коэффициенттерімен берілген тұрақты емес монополином, егер ол F коэффициенттерімен берілген екі тұрақты емес монополиномның көбейтіндісі болмаса, F өрісінде бөлгіш емес болады.

Өріс үстіндегі әрбір полиномдық сақина бірегей факторлау домені болғандықтан, шекті өріс үстіндегі әрбір монополиномды бөлгіш емес монополиномдардың көбейтіндісіне дейін бірегей түрде (факторлардың ретіне қарамастан) жіктеуге болады. Шекті өрісте полиномның бөлгіш еместігін тексеру және полиномдарды жіктеу үшін тиімді алгоритмдер бар. Олар бүтін сандар немесе рационал сандар бойынша полиномдарды жіктеудің маңызды қадамы болып табылады. Осы себепті, кез келген компьютерлік алгебра жүйесінде шекті өрістердегі полиномдарды жіктеуге арналған функциялар бар, немесе кемінде шекті жай өрістердегі полиномдарды жіктеуге арналған функциялар бар.

Қолданбалар

Криптографияда шекті өрістердегі немесе эллиптік қисықтардағы дискретті логарифм мәселесінің қиындығы Диффи–Хеллман протоколы сияқты кеңінен қолданылатын бірнеше протоколдардың негізі болып табылады. Мысалы, 2014 жылы Уикипедияға қауіпсіз интернет-қосылымы үлкен шекті өріс үстінде эллиптік қисық Диффи–Хеллман протоколын (ECDHE) пайдаланды. Кодтау теориясында көптеген кодтар шекті өрістердегі векторлық кеңістіктердің кіші кеңістіктері ретінде құрастырылады. Шекті өрістер көптеген қателерді түзету кодтарында қолданылады, мысалы, Рид–Соломон қателерді түзету коды немесе BCH коды. Шекті өріс көбінесе 2 сипаттамасына ие, себебі компьютерлік деректер екілік түрде сақталады. Мысалы, бір байт дерек GF(2⁸) элементі ретінде қарастырылуы мүмкін. Бір ерекшелік – PDF417 штрих-коды, ол GF(929) өрісінде жұмыс істейді. Кейбір процессорларда 2 сипаттамалы шекті өрістер үшін пайдалы арнайы командалар бар, әдетте көтерілмейтін көбейтудің түрлері. Шекті өрістер сандар теориясында кеңінен қолданылады, өйткені бүтін сандармен байланысты көптеген мәселелерді бір немесе бірнеше жай сандар бойынша қалдықтарды есептеу арқылы шешуге болады. Мысалы, рационал сандар өрісінде полиномдарды жіктеуге және сызықтық алгебраға арналған ең жылдам белгілі алгоритмдер, бір немесе бірнеше жай сандар бойынша қалдықтарды есептеу арқылы жүзеге асырылады, содан кейін шешімді қытайлық қалдық теоремасы, Хенсел көтеруі немесе LLL алгоритмін қолдану арқылы қалпына келтіруге болады. Сол сияқты, сандар теориясының көптеген теориялық мәселелерін жай сандардың біріне немесе барлығына қатысты қалдықтарды қарастыру арқылы шешуге болады. Мысалы, Хассе принципін қараңыз. Алгебралық геометрияның соңғы жылдардағы дамуының көп бөлігі осы модульдік әдістердің қуатын арттыру қажеттілігімен шақырылды. Уайлстың Ферманың соңғы теоремасын дәлелдеуі, шекті өрістерді қоса алғанда, көптеген математикалық құралдарды қолданатын терең нәтижеге мысал болып табылады. Вейльдің болжамдары шекті өрістердегі алгебралық сорттардағы нүктелер санына қатысты және экспоненциалдық және белгі сомаларын бағалауды қоса алғанда, көптеген қолданыстарға ие. Шекті өрістер комбинаторикада кеңінен қолданылады, екі белгілі мысал – Пейли графтарының анықтамасы және Хадамард матрицаларын құрумен байланысы. Арифметикалық комбинаторикада шекті өрістер мен шекті өріс модельдері, мысалы, Сземередидің арифметикалық прогрессиялар туралы теоремасында кеңінен қолданылады.

In cryptography, the difficulty of the discrete logarithm problem in finite fields or in elliptic curves is the basis of several widely used protocols, such as the Diffie–Hellman protocol. For example, in 2014, a secure internet connection to Wikipedia involved the elliptic curve Diffie–Hellman protocol (ECDHE) over a large finite field. In coding theory, many codes are constructed as subspaces of vector spaces over finite fields. Finite fields are used by many error correction codes, such as Reed–Solomon error correction code or BCH code. The finite field almost always has characteristic of 2, since computer data is stored in binary. For example, a byte of data can be interpreted as an element of GF(2^(8)). One exception is PDF417 bar code, which is GF(929). Some CPUs have special instructions that can be useful for finite fields of characteristic 2, generally variations of carry less product. Finite fields are widely used in number theory, as many problems over the integers may be solved by reducing them modulo one or several prime numbers. For example, the fastest known algorithms for polynomial factorization and linear algebra over the field of rational numbers proceed by reduction modulo one or several primes, and then reconstruction of the solution by using Chinese remainder theorem, Hensel lifting or the LLL algorithm. Similarly many theoretical problems in number theory can be solved by considering their reductions modulo some or all prime numbers. See, for example, Hasse principle. Many recent developments of algebraic geometry were motivated by the need to enlarge the power of these modular methods. Wiles' proof of Fermat's Last Theorem is an example of a deep result involving many mathematical tools, including finite fields. The Weil conjectures concern the number of points on algebraic varieties over finite fields and the theory has many applications including exponential and character sum estimates. Finite fields have widespread application in combinatorics, two well known examples being the definition of Paley Graphs and the related construction for Hadamard Matrices. In arithmetic combinatorics finite fields and finite field models are used extensively, such as in Szemerédi's theorem on arithmetic progressions.

Веддерберннің кішкентай теоремасы

Бөлу сақинасы – өрістің жалпылама түрі. Бөлу сақиналары коммутативті болуы міндетті емес. Коммутативті емес шекті бөлу сақиналары жоқ: Веддерберннің кіші теоремасы бойынша, барлық шекті бөлу сақиналары коммутативті, демек, шекті өрістер. Бұл нәтиже, егер ассоциативтілік аксиомасын альтернативтілікке дейін жеңілдетсек, яғни, барлық шекті альтернативті бөлу сақиналары Артин-Зорн теоремасы бойынша шекті өрістер болып табылады.

Квазиалгебралық жабу

Шекті өрістер алгебралық жабық болмаса да, квазиалгебралық жабық болып табылады, яғни егер гомогенді полиномның айнымалыларының саны оның дәрежесінен артық болса, онда ол полином шекті өрістегі тривиальды емес нөлге ие болады, оның компоненттері сол өрісте жатады. Бұл Артин мен Диксон болжаған теореманы Chevalley дәлелдеген (Chevalley–Warning теоремасын қараңыз).