Перайсці да зместу

Канечнае поле

З Вікіпедыі, свабоднай энцыклапедыі

Кане́чнае по́ле ці по́ле Галуа́поле, якое складаецца з канечнай колькасці элементаў. Другую назву канечныя палі атрымалі ў гонар французскага матэматыка Эварыста Галуа.

Канечнае поле звычайна абазначаецца ці GF(q) (скарачэнне ад Galois field), дзе q — колькасць элементаў поля (магутнасць). З дакладнасцю да ізамарфізму канечнае поле поўнасцю вызначаецца яго магутнасцю, якая заўсёды з'яўляецца ступенню нейкага простага ліку (q = pn, дзе p — просты лік, які з'яўляецца характарыстыкаю поля).

Паняцце канечнага поля выкарыстоўваецца, сярод іншага, у тэорыі лікаў, алгебраічнай геаметрыі, тэорыі Галуа, крыптаграфыі, у распрацоўцы сакрэтных ключоў розных шыфраў (напрыклад, AES).

Найпрасцейшым прыкладам канечнага поля з'яўляецца колца вылікаў па модулю простага ліку .

Гісторыя вывучэння

[правіць | правіць зыходнік]

Першыя ўпамінанні пра нешта, блізкае да тэорыі канечных палёў, можна знайсці яшчэ ў XVII стагоддзі. Над гэтаю тэмай працавалі такія навукоўцы, як П’ер Ферма, Леанард Эйлер, Жазеф Луі Лагранж і Адрыен Мары Лежандр, якіх можна лічыць заснавальнікамі тэорыі простых канечных палёў. Аднак большую цікавасць прадстаўляе агульная тэорыя канечных палёў, якая бярэ пачатак з прац Гауса і Галуа. У гонар апошняга канечныя палі і атрымалі сваю другую назву — палі Галуа. Да некаторага часу гэтая тэорыя прымянялася толькі ў алгебры і тэорыі лікаў, аднак у другой палавіне XX стагоддзя выявіліся новыя вобласці дотыку з тэорыяй палёў  (руск.), тэорыяй груп, алгебраічнаю геаметрыяй, камбінаторыкаю і тэорыяй кадзіравання[1].

Эварыст Галуа

У 1830 годзе Эварыст Галуа апублікаваў працу[2], якая стала асноваю агульнай тэорыі канечных палёў. Зыходнаю мэтаю Галуа было вывучэнне параўнання

якое з'яўляецца абагульненнем квадратычных параўнанняў, даследаваных Гаусам (гл. квадратычны закон узаемнасці). Тут — адвольны непрыводны мнагачлен ступені n. У гэтай рабоце Галуа ўводзіць уяўны корань параўнання і абазначае яго . Пасля гэтага разглядаецца агульны выраз

дзе — нейкія цэлыя лікі па модулю p. Калі прысвойваць гэтым лікам усе магчымыя значэнні, выраз будзе прымаць значэнняў. Далей Галуа паказвае, што гэтыя значэнні ўтвараюць поле магутнасці і яго мультыплікатыўная група з'яўляецца цыклічнаю[3]. Такім чынам, гэтая праца стала першым каменем у падмурку агульнай тэорыі канечных палёў. У адрозненне ад яго папярэднікаў, якія разглядалі толькі палі Галуа разглядае ўжо палі якія пачалі называць палямі Галуа ў яго гонар.

На самай справе, Гаус пачаў працаваць у гэтым напрамку прыкладна на 30 гадоў раней, але пры яго жыцці гэтыя даследаванні так і не былі выдадзены. Верагодна, гэтае даследаванне было праігнаравана рэдактарам яго твораў[4], таму ў свет гэтая праца выйшла толькі ў пасмяротным выданні ў 1863.

Далейшае развіццё

[правіць | правіць зыходнік]

У 1893 годзе матэматык Эліякім Мур  (руск.) даказаў тэарэму аб класіфікацыі канечных палёў[5], якая сцвярджае, што любое канечнае поле з'яўляецца полем Галуа.

Да гэтага ж года адносіцца першая спроба аксіяматычнага падыходу да тэорыі канечных палёў, ажыццёўленая Генрыхам Веберам  (руск.), які спрабаваў аб'яднаць у сваёй працы[6] паняцці, якія ўзніклі ў розных раздзелах матэматыкі, у тым ліку і паняцце канечнага поля.

Далей у 1905 годзе Джозэф Ведэрбёрн  (англ.) даказвае тэарэму  (англ.) аб тым, што любое канечнае цела камутатыўнае, г.зн. з'яўляецца полем.

Сучаснае аксіяматычнае азначэнне поля (з канечнымі палямі ў якасці асобнага выпадку) належыць Эрнсту Штайніцу  (руск.) і выкладзена ў яго працы 1910 года[7].

Далейшае развіццё тэорыі адбываецца ў тэарэтычных і прыкладных галінах, якія выкарыстоўваюць канечныя палі ў той ці іншай ролі.

Уласцівасці і факты

[правіць | правіць зыходнік]
  1. Характарыстыка канечнага поля з'яўляецца простым лікам, і лік элементаў канечнага поля ёсць яго характарыстыка ў натуральнай ступені: .
  2. Канечнае поле не можа быць упарадкаваным  (руск.), бо ўпарадкаванае поле ўтрымлівае бесканечна многа элементаў.
  3. Канечнае поле не з'яўляецца алгебраічна замкнутым. Мнагачлен
    не мае каранёў у , прычым
  4. Для кожнага простага ліку і натуральнага існуе канечнае поле з элементаў, адзінае, з дакладнасцю да ізамарфізму. Гэтае поле ізаморфнае полю раскладання мнагачлена .
  5. Мультыплікатыўная група канечнага поля з'яўляецца цыклічнай групай парадку .
    • У прыватнасці, у канечным полі заўсёды існуе прымітыўны элемент  (руск.) , парадак якога роўны , г. зн. і для .
    • Любы ненулявы элемент з'яўляецца некаторай ступенню прымітыўнага элемента:
      .
  6. Поле утрымлівае ў сабе ў якасці падполя тады і толькі тады, калі з'яўляецца дзельнікам .
  7. Лік N непрыводных мнагачленаў ступені n вызначаецца па формуле
    дзе функцыя Мёбіуса.
+ 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
  • , дзе — просты: і гэтак далей.
  • , дзе галоўны ідэал кальца , спароджаны непрыводным мнагачленам ступені .

Пабудова поля , дзе p — просты лік, n — натуральны лік, пачынаецца з пабудовы ягонага простага падполя (якое супадае з усім полем пры n=1).

  • Простае поле будуецца як кальцо вылікаў па модулю , якое дзякуючы прастаце не мае дзельнікаў нуля і таму з'яўляецца полем.
    Элементы — лікі . Аперацыі праводзяцца як са звычайнымі цэлымі лікамі з прывядзеннем выніку па модулю .
  • Поле пры n>1 будуецца як фактарколца , дзе непрыводны мнагачлен ступені n над полем . Такім чынам, каб пабудаваць поле з элементаў, дастаткова адшукаць мнагачлен ступені , непрыводны над полем .
    Элементамі поля з'яўляюцца ўсе мнагачлены ступені, меншай чым з каэфіцыентамі з . Арыфметычныя аперацыі (складанне і множанне) ажыццяўляюцца па модулю мнагачлена , г.зн. вынік адпаведнай аперацыі — гэта астача ад дзялення на з прывядзеннем каэфіцыентаў па модулю .

Прыклад пабудовы поля GF(9)

[правіць | правіць зыходнік]

Каб пабудаваць поле , неабходна знайсци мнагачлен ступені 2, непрыводны над . Такімі мнагачленамі з'яўляюцца:

Возьмем, напрыклад, , тады шуканае поле ёсць . Калі замест узяць іншы мнагачлен, то атрымаецца новае поле, ізаморфнае старому.

Табліца складання ў GF(9)

[правіць | правіць зыходнік]

+ 0 1 2
0 0 1 2
1 1 2 0
2 2 0 1
0 1 2
1 2 0
2 0 1
0 1 2
1 2 0
2 0 1

Табліца множання ў GF(9)

[правіць | правіць зыходнік]

× 0 1 2
0 0 0 0 0 0 0 0 0 0
1 0 1 2
2 0 2 1
0 2 1
0 1 2
0 1 2
0 1 2
0 2 1
0 2 1

Дыяфантавы ўраўненні

[правіць | правіць зыходнік]

Дыяфантава ўраўненне — ураўненне з цэлымі каэфіцыентамі, у якім зменныя таксама прымаюць цэлалікавыя значэнні. Вялікую хвалю абмеркавання такіх ураўненняў выклікаў Ферма, сфармуляваўшы свае тэарэмы. Малая тэарэма Ферма сцвярджае, што калі — просты лік, які не з'яўляецца дзельнікам другога ліку , то . У тэорыі канечных палёў гэтая тэарэма з'яўляецца відавочным вынікам з тэарэмы Лагранжа, прымененай да мультыплікатыўнай падгрупы, спароджанай элементам , бо ўся мультыплікатыўная група поля складаецца з элементаў.

Ферма заўважае, што адзіныя простыя лікі, якія можна раскласці ў суму двух квадратаў — гэта тыя простыя лікі, якія даюць астачу 1 пры дзеленні на 4. Сярод іншага, ён адзначае, што

.

У сваім пісьме Марену Мерсенну, датаваным 25 снежня 1640 года, Ферма прапануе рашыць ураўненне

Юліус Дэдэкінд даследаваў[8] падобныя ўраўненні ў нейкім канечным полі . У гэтым полі ўраўненне прымае від . Калі , то рашэнне будзе трывіяльнае. У процілеглым выпадку можна падзяліць абедзве часткі на і, зрабіўшы замену, атрымліваем ураўненне выгляду . Дамножыўшы на , атрымліваем . Лічачы утваральнікам мультыплікатыўнай падгрупы парадку 4, можна атрымаць неабходныя і дастатковыя ўмовы на p, пры якіх ураўненне мае рашэнне. Далейшы доказ тэарэмы, праведзены Дэдэкіндам, не выкарыстоўвае паняцці канечных палёў, і яго можна знайсці ў адпаведным артыкуле.

Тэорыя карэкціруючых кодаў

[правіць | правіць зыходнік]

Годам стварэння тэорыі карэкціруючых кодаў лічыцца 1948 год, у якім быў апублікаваны артыкул Клода Шэнана[9], у якой ён паказвае, што наяўнасць памылак пры перадачы інфармацыі па якім-небудзь канале залежыць у тым ліку ад суадносін скорасці перадачы і прапускной здольнасці канала. Скорасць перадачы павінна быць вышэйшая за прапускную здольнасць. Шэнан прывёў доказы, але яны былі прызнаны няслушнымі. Канструктыўны падыход прапанаваў Рычард Хэмінг  (руск.)[10], задаўшы тым самым напрамак развіцця многіх пазнейшых артыкулаў па тэме. У сваёй працы Хэмінг пабудаваў просты код  (руск.), які пэўным чынам выпраўляе памылкі. Хэмінг разглядаў карэкціруючыя коды толькі над полем . Неўзабаве падобныя коды былі пабудаваны над адвольнымі канечнымі палямі Голеем  (англ.) у 1949 годзе[11]. Аднак найбольшы ўклад у гэту тэорыю належыць усё ж Хэмінгу.

Канечныя палі шырока прымяняюцца ў крыптаграфіі. Асноватворнаю працай лічыцца артыкул Дыфі  (руск.) і Хелмана  (руск.)[12] па крыптаграфіі з адкрытым ключом, у якім быў прапанаваны пратакол абмену ключамі  (руск.). У гэтай працы выкарыстоўваліся канечныя палі пэўнага віду. Цяпер жа існуе вялікае мноства крыптаграфічных пратаколаў і крыптасістэм, заснаваных на выкарыстанні канечных палёў. Гэта і схема Эль-Гамаля  (руск.), і Advanced Encryption Standard  (руск.), і схема Шнора  (руск.), і алгарытм Чаўма (сляпы подпіс)  (руск.), крыптасістэма XTR  (англ.), і шмат іншага. Алгарытмы на аснове эліптычных крывых, якія з'яўляюцца адным з ключавых аб'ектаў у сучаснай крыптаграфіі, таксама выкарыстоўваюць канечныя палі.

Таксама часта якасць шыфравання залежыць ад здольнасці хутка генераваць вялікія простыя лікі. Адпаведна, паўстае задача пабудовы алгарытму раскладання на простыя множнікі (вызначэнне простасці таго ці іншага ліку). Майкл Рабін  (руск.) апублікаваў даследаванне[13], у якім ён прапануе тэст прастаты на аснове ўласцівасцей мультыплікатыўнай групы поля.

Тэорыя канечных палёў самым цесным чынам звязана з модульнаю арыфметыкай. У прыватнасці, паняцце аб канечных палях (якое існавала на той час) памагло Гаусу сфармуляваць квадратычны закон узаемнасці[14].

Эміль Арцін  (руск.) выкарыстаў інструментарый тэорыі канечных палёў для рашэння знакамітай дзявятай праблемы Гільберта  (руск.) (ён аналізаваў аналаг дзэта-функцыі Рымана над канечнымі палямі). Найбольш актыўнае абагульненне арыфметычнай геаметрыі на канечныя структуры адбывалася ў другой палавіне XX стагоддзя, калі Андрэ Вейль абагульніў падыход да вывучэння алгебраічных крывых  (руск.), а П’ер Дэлінь — алгебраічных мнагастайнасцей  (руск.). Гіпотэзы Вейля  (англ.) аб алгебраічных мнагастайнасцях над канечнымі палямі, канчаткова даказаныя ў 1940 годзе, былі адным з важных пытанняў таго часу.

Касмічны зонд «Вояджэр»

У 1960 годзе Рай Чандра Бозэ  (англ.) і Двіджэндра Кумар Рэй-Чаўдхуры  (англ.) апублікавалі працу[15], у якой даследавалі сямейства мнагачленаў над канечнымі палямі. Алексіс Акенгем  (англ.) абагульніў іх тэорыю і гэта прывяло да стварэння кода БЧХ  (руск.), асобным выпадкам якога з’яўляецца шырока вядомы код Рыда — Соламана  (руск.), які прымяняецца вельмі шырока. Ён выкарыстоўваецца пры запісе і чытанні ў кантролерах аператыўнай памяці, пры архіваванні даных, запісе інфармацыі на жорсткія дыскі (ECC  (руск.)), запісе на CD/DVD дыскі. Цікава тое, што пры пашкоджанні значнага аб’ёму інфармацыі, ці калі сапсавана некалькі сектараў дыскавага накапляльніка, коды Рыда — Соламана дазваляюць аднавіць большую частку згубленай інфармацыі. Код БЧХ  (руск.) выкарыстоўваецца таксама ў сістэме сувязі некаторых зондаў NASA (такіх як Вояджэр)

  1. Лидл Р., Нидеррайтер Г. Конечные поля. — М.: Мир, 1988. — С. 5. — 808 с. — ISBN 5-03-000065-8.
  2. Evariste Galois (1830), Sur la théorie des nombres. Bulletin des sciences mathématiques de M. Férussac 13, pp 428—435 (1830)
  3. Israel Kleiner. A History of Abstract Algebra. — Birkhäuser, 2007. — С. 70. — 168 с. — ISBN 978-0-8176-4684-4.
  4. G. Frei. The Unpublished Section Eight: On the Way to Function Fields over a Finite Field. — Goldstein Schappacher Schwermer, 2007. — С. 159-198.
  5. Moore E. H. A double–infinite systems of simple groups. — Mathematical Papers Read at the International Mathematical Congress in Chicago, 1893. — С. 208–242.
  6. H. Weber, " Die allgemeinen Grundlagen der Galois'schen Gleichungstheorie ", Mathematische Annalen, vol. 43, 1893, p. 521—549
  7. Ernst Steinitz, " Algebraische Theorie der Körper ", Journal für die reine und angewandte Mathematik, vol. 137, 1910, p. 167—309 (ISSN 0075-4102)
  8. R. Dedekind, Supplément XI des Leçons en théorie des nombres de Dirichlet, 1894
  9. Шеннон, К. Математическая теория связи [Текст] / К. Шеннон // Работы по теории информации и кибернетике. — М. : Издательство иностранной литературы, 1963. — С. 243—332.
  10. Хэмминг, К. Коды с обнаружением и исправлением ошибок [Текст] / К. Хэмминг // Коды с обнаружением и исправлением ошибок. — М. : Издательство иностранной литературы, 1956. — С. 7-23.
  11. Golay M.J.E. Notes on digital coding // Proceedings IRE. 1949. V. 37, P.657.
  12. W. Diffie and M.E. Hellman. New directions in cryptography. IEEE Trans. Info. Theory, IT-22(6):644-654, 1976.
  13. M. Rabin, Probabilistic Algorithm for Testing Primality, J. Number Th. 12 (1980), 128—138
  14. C. F. Gauss, Disquisitiones Arithmeticae, 1801
  15. R. C. Bose et D. K. Ray-Chaudhuri, On a class of error-correcting binary group codes, Inform. Control, vol. 3, mars 1960, p. 68-79
  • Винберг Э. Б. Курс алгебры. — 3-е изд. — М.: Факториал Пресс, 2002. — 544 с. — 3 000 экз. — ISBN 5-88688-060-7.
  • Лидл Р., Нидеррайтер Г. Конечные поля. В 2-х тт. — М.: Мир, 1998.