Վերջավոր դաշտ

Վերջավոր դաշտ, կամ ընդհանուր հանրահաշվում Գալուայի դաշտ, դաշտ, որը բաղկացած է վերջավոր թվով տարրերից, այս թիվը կոչվում է դաշտի կարգ։

Վերջավոր դաշտը սովորաբար նշանակվում է  կամ  (հապավումը՝ Galois field-ից) և կոչվում է  կարգի Գալուայի դաշտ, որտեղ -ն՝ դաշտի տարրերի թիվն է։ Վերջնական ճշտությամբ մինչև իզոմորֆիզմը վերջավոր դաշտը լիովին որոշվում է իր կարգով, որը միշտ հանդիսանում է ինչ-որ պարզ թվի աստիճան, այսինքն՝ , որտեղ -ն պարզ թիվ է, -ը՝ ցանկացած բնական թիվ։ Ընդ որում  լինելու է այդ դաշտի բնութագիրը։

Վերջավոր դաշտի հասկացությունը օգտագործվում է թվերի տեսության, խմբերի տեսության ,  հանրահաշվական երկրաչափության և ծածկագիտություն մեջ։

Սահմանում և հատկություններ 
Վերջավոր դաշտ կոչվում է վերջավոր բազմությունը, որի վրա սահմանված են գումարման, բազմապատկման, հանման և բաժանման (բացի 0-ի բաժանումից) կամայական գործողություններ, ըստ աքսիոմների դաշտի։

Վերջավոր դաշտի մուլտիպլիկատիվ խումբը ցիկլային է։ Այսինքն,  դաշտի ոչ բոլոր զրոյական տարրերն են ձևավորում խումբ բազմապատկման գործողության նկատմամբ (այս խումբը կոչվում է դաշտի մուլտիպլիկատիվ խումբ և նշանակում է )։ Այս խումբը համարվում է ցիկլային, այսինքն այն ունի ծնիչ տարր, իսկ մնացած բոլոր տարրերը ստացվում են ծնիչի աստիճանններով։ Այսինքն, գոյություն ունի  գեներացնող տարր, այնպես, որ ցանկացած  -ի համար կարելի է գրել.

։

Գեներացնող տարրը՝ ,  կոչվում է նաև  դաշտի պարզունակ տարր։  դաշտը  պարունակում է  պարզունակ տարրեր, որտեղ ՝ Էյլերի ֆունկցիան է։

Դաշտը ունի նաև մի շարք այլ հատկություններ.

 Ըստ Ֆերմայի թեորեմի,   դաշտի յուրաքանչյուր տարր բավարարում է  հավասարմանը։
  դաշտն իր մեջ պարունակում է  ենթադաշտ այն և միայն այն ժամանակ, երբ  հանդիսանում է -ի բաժանարար։
 Եթե  -ը   աստիճանի չբերվող բազմապատկման է, ապա  դաշտը պարունակում է նրա ցանկացած  արմատ, ընդ որում նրա բոլոր արմատների բազմությունն ունի  տեսքը։ Այսպիսով,  դաշտը հանդիսանում է  բազմանդամի վերլուծման դաշտը  դաշտի վար։
 Յուրաքանչյուր  վերջավոր դաշտի և  բնական թվերի համար բոլոր նորմավորված,  բազմանդամների արտադրյալը հավասար է  Մասնավորապես, այդպիսի բազմանդամների աստիճանների գումարը հավասար է ։
  դաշտի վրա բերվող n աստիճանի նորմավորված բազմանդամների  թիվը որոշվում է  բանաձևով, որտեղ  Մյոբիուսի ֆունկցիան է։ Այս պնդումը հետևում է  բանաձևից։

Պարզ թվով տարրերով դաշտ 

Պարզ կարգի ցանկացած դաշտ կարող է ներկայացվել տարրերի հանման օղակով (այսինքն,  տարրերով ցանկացած դաշտ իզոմորֆ է հանման  օղակին)։ Վերջնական դաշտի առավել հայտնի օրինակներից է՝ ըստ  պարզ թվի մոդուլի հանման դասերի դաշտը, որը նշանակվում է -ով։ Այդ դաշտը կարելի է ներկայացնել հետևյալ կերպ.
 պարզ թվի համար դաշտի տարրերը կլինեն  թվերը։ Գումարումը և բազմապատկումը սահմանվում են որպես թվերի ավելացում և բազմապատկվում արդյունքի բերվում  մոդուլի միջոցով։ Ստորև տրված են նման դաշտեր երկրու և երեք տարերով։

Նվազեցվող օղակների հետ կապը 

Չպետք է շփոթել վերջնական դաշտերը  և նվազեցումների օղակները ։ Միայն այն ժամանակ, երբ թիվը պարզ է, օղակը համարվում է նվազեցվող ։

Երբ n > 1 նվազեցված օղակը  դաշտ չի համարվում։ Օրինակ՝

 ցանկացած տարրի համար ճիշտ է ։

Օղակը , Հաշվելով    
 մենք կստանանք 0 միայն երկու դեպքում, երբ ։ Այս օղակը ունի զրոյական բաժանարար։

Վերջավոր դաշտերի բնութագրիչ 
Յուրաքանչյուր վերջավոր դաշտի բնութագրիչը հանդիսանում է պարզ թիվ։ Թող՝ -ն լինի վերջավոր դաշտ։ Այդ դեպքում այն բաղկացած է  տարրերից, որտեղ  դաշտի բնութագրիչը  է, իսկ  բնական թիվը՝  դաշտի կարգն է իր պարզ ենթադաշտի վրա.

Վերջավոր դաշտի գոյության և միակության թեորեմի համաձայն, յուրաքանչյուր  պարզ և  բնական թվերի համար գոյություն ունի վերջավոր դաշտ՝  տարրերով և  տարրերով ցանկացած վերջավոր դաշտ իզոմորֆ է բազմանդամի վերլուծման  դաշտի նկատմամբ՝  դաշտի վրա։ Տվյալ թեորեմը մեզ թույլ է տալիս խոսել տրված  կարգի, բավականին սահմանված դաշտի մասին (այսինքն, Գաուլայի դաշտի մասին, որը բաղկացած է՝  տարրից)։

Կառուցում
 դաշտը n > 1 -ի դեպքում կարելի է կառուցվել որպես  ֆակտոր օղակ, որտեղ  -ը   դաշտի նկատմամբ nաստիճանի չբերվող բազմանդամ է։ Այսպիսով,  տարրից դաշտ կառուցելու համար բավական է գտնել  աստիճանի,  դաշտի վրա չբերվող բազմանդամ (նման բազմությունները միշտ գոյություն ունի)։  դաշտի տարրերը հանդիսանում են -ից փոքր աստիճաններով,  -ից գործակիցներով,  բազմանդանով ծնված բազմանդամների տարբերության դաս։

 տարրը համարվում է  բազմանդամի արմատը և  դաշտը ծնվում է այդ տարրով՝  դաշտում, հետևաբար անցումը  դաշտից  դաշտ անվանում են  չբերվող բազմանդամի արմատի միավորումը  դաշտին։

Օրինակներ

Երկու տարրերից կազմված դաշտ 
 դաշտը բաղկացած է երկու տարրերից, սակայն այն կարող է տրված լինել տարբեր եղանակներով՝ կախված տարրերի ընտրությունից և նրա վրա  գումարման և բազմապատկամ գործողությունների սահմանելուց։

 Որպես երկու՝ «0» և «1», թվերից բաղկացած բազմություն, որտեղ գումարման և բազմապատկման գործողությունը սահմանվում են ինչպես բերված արդյունքների 2 մոդուլով թվերի գումարում և բազմապատկում.

 Որպես «ՍԽԱԼ» (F) և «ՃԻՇՏ» (T) երկու տրամաբանական օբեկտների բազմություն, որի վրա գումարման և բազմապատկման գործողությունները սահմանվում են որպես բուլյան գործողություններ համապատասխանաբար «բացառող կամ» և «և».

Ակնհայտ է, որ տրված դաշտերը միմիանց իզոմորֆ են, այսինքն, դրանք իրականում առաջադրանքի տրման երկու տարբեր եղանակներ են։

Երեք տարրերից կազմված դաշտ 
Դաշտը  -ն է։ Գումարումը և բազմապատկումը սահմանված են ինչպես 3 մոդուլով թվերի գումարում և բազմապատկում։  գործողությունների աղյուսակը ունի հետևյալ տեսքը.

Չորս տարրերից կազմված դաշտ 
 դաշտը կարելի է ներկայացնել որպես  բազմություն (որտեղ  -ը  բազմանդամի արմատն է  դաշտի վրա, այսինքն՝ ):  գործողությունների աղյուսակներն ունեն հետևյալ տեսքը.

Ինը տարրերից կազմված դաշտ
 դաշտի կառուցման համար բավարար է գտնել 2-րդ կարգի,  -ի վրա չբերվող նորմավորված բազմանդամ։ Այդպիսի բզմանդամներ են հանդիսանում.

 -ի համար որոնվող դաշտը  -ն է (եթե -ի փոխարեն վերձնենք այլ բազմություն, ապա կստացվի նոր դաշտ, հնին իզոմորֆ)։ Ստորև բերված աղյուսակում  սիմվոլը նշանակում է  բազմության համաժեքության դաս՝  ֆակտոր իղակում,  հավասարմանը բավարարող։

 գումարման աղյուսակը սահմանվում է  հարաբերությունից ելնելով։

 -ում բազմապատկման աղյուսակը սահմանվում է  հարաբերությունից։

16 տարրերից կազմված դաշտի մուլտիպլիկատիվ խումբ 
Երբ  դաշտը կազմվում է  չբերվող բազմանդամի օգնությամբ, ընդլայման տարրերը տրվում են բազմանդամի գործակցների հավաքածուներով, որը ստացվում է  բազմանդամի վրա բաժանման մնացորդում՝ գրված աստիճանների աճման կարգով։ Մուլտիպլիկատիվ խումբը ծնվում է  տարրով, որը գրի առնվում որպես (0, 1, 0, 0)

Ուսումնասիրության պատմություն 
Վերջավոր դաշտերի տեսության սկիզբը սկսվում է 17-րդ և 18-րդ դարերից։ Այս թեմայի շուրջ աշխատել են գիտնականներ ինչպիսիք են Պիեռ դը Ֆերման, Լեոնարդ Էյլերը, Ժոզեֆ Լուի Լագրանժը և Ադրիեն-Մարի Լեժանդրը, որոնց կարելի է համարել պարզ կարգի վերջավոր դաշտերի տեսությունների հիմնադիրներ։ Այնուամենայնիվ, վերջավոր դաշտերի ընդհանուր տեսությունը մեծ հետաքրքրություն է ներկայացնում, սկսած Կառլ Գաուսի և Էվարիստ Գալուայի աշխատանքներից։ Որոշ ժամանակ այս տեսությունը կիրառություն գտավ միայն հանրահաշվի և թվերի տեսության մեջ, սակայն հետագայում շփման նոր եզրեր են ի հայտ եկել հանրահաշվական երկրաչափության, կոմբինատորիկայի և կոդավորման տեսության հետ։

Գալուայի ներդրումը 

1830 թվականին տասնութամյա Էվարիստ Գալուան աշխատանք հրատարակեց, որը հիմք դրեց վերջավոր դաշտերի ընդհանուր տեսությանը։ Այդ աշխատանքում Գալուան (կապված փոփոխականների և հանրահաշվական հավասարումների տեսության հետազոտության հետ) ներ է մուծում համեմատության երևակայական  արմատը, որտեղ -ն p մոդուլով չբերվող,  աստիճանի կամայական բազմանդամ է։ Դրանից հետո դիտարկվում է   ընդհանուր արտահայտությունը, որտեղ ՝ p մոդուլով որոշ ամբողջական թվեր։ Եթե այդ թվերին տանք բոլոր հնարավոր արժեքները, ապա  արտահայտությունը կընդունի  արժեքը։ Այնուհետև Գալուան ցույց է տալիս, որ այդ արժեքները դաշտ են ձևավորում և այդ դաշտի մուլտիպլիկատիվ խումբը համարվում է ցիկլիկ։ Այսպիսով, այս աշխատանքը համարվում է վերջավոր դաշտերի ընդհանուր տեսության հիմքը։ Ի տարբերություն նախորդների՝ միայն  դաշտը դիտարկող, Գալուան հետազոտում է արդեն  դաշտերը, որոնք իր պատվին սկսեցին անվանել Գալուայի դաշտ։

Իրականում, այս ուղղությամբ առաջին աշխատանքը գրել է Գաուսը մոտավորապես 1797 թվականին, սակայն նրա կյանքի ընթացքում այս ուսումնասիրությունը երբեք չի հրատարակվել։ Այս ուսումնասիրությունը հավանաբար անտեսվել է նրա գրությունների խմբագրի կողմից և այդ իսկ պատճառով այս աշխատանքը լույս է տեսել միայն նրա մահից հետո՝ 1893 թվականին։

Հետագա զարգացում 
1893 թվականին մաթեմաթիկոս Էլիակիմ Գաստինգս Մուրը ապացուցեց վերջավոր դաշտերի դասակարգման թեորեմ, որը հաստատում էր, որ յուրաքանչյուր վերջավոր դաշտ հանդիսանում է Գալուայի դաշտ, այսինքն՝  անդամներով յուրաքանչյուր դաշտ իզոմորֆ է  -ից գործակիցներով բազմանդամների և  աստիճանի չբերվող բազմանդամի հանման մոդուլի դասի դաշտին։ Այդ տարի էլ կատարվում է վերջավոր դաշտերին աքսոմատիկ մոտեցում ցուցաբերելու առաջին փորձը, որը իրականացրել է Հենրիխ Մարտինը, ով իր աշխատանքում փորձել է համատեղել մաթեմատիկայի տարբեր ճյուղերում առաջացած հասկացությունները, այդ թվում նաև վերջավոր դաշտերի հասկացությունը։ Այնուհետև, 1905 թվականին, Ժոզեֆ Վեդդերբյորնը ապացուցում է Վեդդերբյորնի թեորեմն այն մասին, որ յուրաքանչյուր վերջավոր մարմին կոմուտատիվ է, այսինքն՝ դաշտ է համարվում։ Աքսիոմատիկ դաշտի ժամանակակից սահմանումը (վերջավոր դաշտերով որպես մասնավոր դեպք) պատկանում է Էրնեստ Շտայնիցին և շարադրվել է նրա 1910 թվականի աշխատությունում։

Կիրառում

Դիոֆանտյան հավասարում 

Դիոֆանտովի հավասարումը հանդիսանում է ամբողջ գործակիցներով հավասարում, որտեղ փոփոխականները նաև ընդունում են ամբողջ թվի արժեքներ։ Նման հավասարումների քննարկման մեծ ալիք է առաջացրել Ֆերման՝ ձևավորելով իր թեորեմները։ Ֆերմայի թեորեմը պնդում է, որ եթե  պարզ թիվ է, որը չի հանդիսանում մեկ այլ  բաժանարար, ապա ։ Վերջավոր դաշտերի տեսության մեջ այս տեսությունը հանդիսանում է Լագրանժի թեորեմի ակնհայտ հետևանք, որը կիրառվում է  տարրով ծնված մուլտիպլիկատիվ ենթախմբի նկատմամբ, քանի որ  դաշտի ամբողջ մուլտիպլիկատիվ խումբը բաղկացած է  տարրերից։

Ֆերման նկատել է, որ միակ պարզ թվերը, որոնք կարող են ներկայացնել երկու քառակուսիների գումարով, դրանք այն պարզ թվերն են, որոնք տալիս են 1 մնացորդ 4-ի վրա բաժանելիս։ Մասնավորապես, նա նշում է, որ

1640 թվականի դեկտեմբերի 25-ին թվագրված իր նամակում Մարենա Մերսեննուին Ֆերման առաջարկում է լուծել  հավասարումը։

Հուլիոս Դեդեկինդը ուսումնասիրել է այս հավասարումը  վերջավոր դաշտում, որտեղ այն ընդունում է այս տեսքը ։ Եթե , ապա հավասարումը տրիվյալ է։ Հակառակ դեպքում, երկու մասերը կարելի է բաժանել  -ի և փոփոխելով ստանալ  տեսքի հավասարում։ Բազմապատկելով  -ով ստացվում է  հավասարումը։ -ը համարելով 4 կարգի մուլտիպլիկատիվ ենթախմբի գեներատոր, p-ի վրա կարելի է ստանալ անհրաժեշտ և բավարար պայմաններ, որոնց դեպքում հավասարումը ունի լուծում։ Ֆերմա — Էյլեր թեորեմի հետագա ապացույցը, որը տարել է Դեդեկինդը, չի օգտագործում վերջավոր դաշտերի հասկացություններ և այն կարելի է գտնել համապատասխան հոդվածում։

Ուղղիչ կոդերի տեսություն 

Ուղղիչ կոդերի տեսության ստեղծման տարի է համարվում 1948 թվականը, երբ հրապարակվել Է Կլոդ Շենոնի հոդվածը, որում նա ցույց է տալիս, որ որևէ ալիքով ինֆորմացիայի փոխանցման ժամանակ սխալների առկայությունը այդ թվում կախված է ալիքի փոխանցման արագության և անցանելիության կարողության հարաբերակցությունից։ Փոխանցման արագությունը պետք է լինի ավելի անցանելիության կարողությունից բարձր։ Շենոնը ապացույցներ է ներկայացրել, սակայն դրանք ճանաչվել են ոչ անկախ։

Ռիչարդ Հեմինգն առաջարկել է կառուցողական մոտեցում, դրանով իսկ տվյալ թեմատիկային վերաբերվող հոդվածներին զարգացման վեկտոր հաղորդելով։ Իր աշխատանքում Հեմինգը ստեղծել է պարզ կոդ, որը որոշակի ձևով ուղղում է սխալները։ Հեմինգն ուղղիչ կոդերը դիտարկում է միայն  դաշտի վրա։ Շուտով նմանատիպ կոդեր ստեղծվեցին կամայական վերջնական դաշտերի վրա 1949 թվականին Գոլեյում ։ Սակայն այդ տեսության մեջ ամենամեծ ներդրումը այնուամենայնիվ Հեմինգին է պատկանում։

Ծածկագրություն 

Վերջնավոր դաշտերը լայն կիրառություն են ստացել ծածկագիտության մեջ։ Հիմնարար աշխատանք է համարվում ծածկագրության մասին բաց բանալիով Դիֆֆի և Հելմանի հոդվածը, որի մեջ ներկայացված է բանալիների փոխանակման արձանագրություն։ Այս աշխատանքում օգտագործվել են որոշակի տեսքի վերջավոր դաշտեր։ Ավելի ուշ ի հայտ եկան վերջավոր դաշտերի վրա հիմնված բազմաթիվ կրիպտոգրաֆական արձանագրություններ և կրիպտոգրաֆական համակարգեր։ Դրանց թվին են պատկանում Էլ-Գամալի սխեման, Advanced Encryption Standard, Շնորրի սխեման, Չաումայի (կույր ստորագրություն) ալգորիթմը, XTR կրիպտոգրաֆական համակարգը և շատ ուրիշներ։ Ժամանակակից կրիպտոգրաֆիայի մեջ հիմնական օբյեկ հանդիսացող Էլիպտական կորերի վրա հիմնված ալգորիթմները նույնպես օգտագործում են վերջավոր դաշտեր։

Բացի այդ, հաճախ կոդավորման որակը կախված է մեծ պարզ թվերի արագ գեներացնելու կարողությունից։ Համապատասխանաբար, խնդիր է ծագում թվի՝ պարզ արտադրիչների վերլուծման ալգորիթմի կառուցման (այս կամ այն թվի պարզության որոշում)։ Միխայել Ռաբինը հրապարակել է ուսումնասիրություն, որում նա առաջարկում է պարզության թեստ՝ հիմնված դաշտի մուլտիպլիկատիվ խմբի հատկությունների վրա։

Այլ 

1960 թվականին Ռեյ Բոուզը և Ռոյ-Չոուդխուռին հրապարակեցին աշխատանք, որում հետազոտել են բազմանդամների ընտանիքը վերջավոր դաշտում։ Ալեքսիս Հոկվինգն ընդհանրացրեց նրանց տեսությունը, ինչը հանգեցրեց ԲՉՀ կոդի ստեղծմանը, որի մասնավոր դեպքը Ռիդ - Սոլոմոնի հայտնի կոդն է, որը ունի շատ լայն կիրառություն։ Այն օգտագործվում է ձայնագրման և ընթերցման ժամանակ՝ օպերատիվ հիշողության կարգավորիչներում, տվյալների արխիվացման, ինֆորմացիայի կոշտ սկավառակների (ECC) և CD/DVD վրա ձայնագրման համար։ Հատկանշական է, որ տեղեկատվության զգալի ծավալի վնասման կամ սկավառակային կրիչի մի քանի հատվածների վնասման դեպքում Ռիդա - Սոլոմոնի կոդը թույլ է տալիս վերականգնել կորցրած տեղեկատվության մեծ մասը։ ԲՉՀ կոդը օգտագործվում է ՆԱՍԱ -ի որոշ զոնդերի (ինչպիսին է Վոյաջերը) կապի համակարգում։

Ծանոթագրություններ

Գրականություն 
 
 
 
 
 
  
 

Աբստրակտ հանրահաշիվ