Bajardi: 414-21 guruh talabasi Choriyev Fazliddin Tekshirdi: Safoyev Nuriddin Toshkent – 2022

Javob: 3^-1 (mod7) = 5
Galua maydoni

Agar p –tub son bo‘lsa, u holda 0 dan p-1 gacha bo‘lgan barcha natural sonlar to‘plami {0, 1, 2, …, p-1} elementlari soni p ta bo‘lgan chekli maydon tashkil etadi va bu maydon Galua maydoni deb yuritiladi, hamda, GF(p) ko‘rinishda belgilanadi. Galua maydonida qo‘shish, ayirish, ko‘paytirish va noldan farqli bo‘lgan elementga bo‘lish amallari aniqlangan. Hamda, bu maydonda: qo‘shish amaliga nisbatan ixtiyoriy a GF(p) uchun a + 0 = a tenglikni qanoatlantiruvchi 0 (nol) element mavjud; ko‘paytirish amaliga nisbatan ihtiyoriy a GF(p) uchun a ·1 = a tenglikni qanoatlantiruvchi 1 (bir) element mavjud; ihtiyoriy noldan farqli a GF(p) uchun (a·b)mod p =1 tenglikni qanoatlantiruvchi b GF(p) element mavjud bo‘lib, bu b element a elementga teskari element deyiladi va deb belgilanadi; aniqlangan amallar kommutativlik, assotsiativlik va distributivlik xossalariga ega.

Galua maydoni bilan bog‘liq bo‘lgan matematik tushuncha va tasdiqlar kriptografida keng qo‘llaniladi.
Kriptografik masalalarni yana ham murakkablashtirish maqsadida keltirilmaydigan (ko‘paytuvchilarga ajramaydigan), koefitsientlari ushbu {0,1,…,q-1} ( bu yerda q –tub son) to‘plamdan bo‘lgan barcha n –tartibgacha ko‘phadlar to‘plamidan foydalaniladi. Bu ko‘phadlar maydoni GF(qⁿ) deb belgilanadi. Hamma amallar xarakteristikasi n –tartibli keltirilmaydigan ko‘phad p(x) GF(qⁿ) bilan aniqlanadigan maydonda bajariladi. Misol uchun, GF(2³) maydon ushbu: 0,1, x, x + 1, x² , x²+1, x²+x, x²+x+1 elementlarni o‘z ichiga oladi.
Berilgan GF(qⁿ) maydondan olingan p(x) ko‘phadning koeffitsientlari o‘zaro tub bo‘lsa, bu ko‘phad yasovchi bo‘ladi, hamda, primitiv (sodda) deyiladi. Primitiv ko‘phadlar chiziqli teskari bog‘liqlikga ega bo‘lgan siljish registrlari bilan uzviy bog‘liqlikga ega, ya’ni q=2 bo‘lganda GF(2ⁿ) maydonda bajariladigan amallarni chiziqli teskari bog‘liqlikka ega bo‘lgan siljitish registlarining apparat-texnik qurilmalari yordamida tez bajarish mumkin. Haqiqatan ham, darajaga ko‘tarish amalini bajarish GF(qⁿ)_q<2 maydondagidan ko‘ra GF(2ⁿ) maydonda samaralidir. Bundan esa GF(2ⁿ) maydonda diskret logarifmlarni hisoblashning ham samarali ekanligi kelib chiqadi.
Koeffitsientlari ikkilik sanoq sistemasi elementlaridan iborat n –tartibgacha bo‘lgan barcha ko‘phadlar to‘plami GF(2ⁿ) –Galua maydonida modul - maydon xarakteristikasi sifatida p(x)=xⁿ+x+1 ko‘rinishdagi uch haddan iborat bo‘lgan n –tartibli primitiv ko‘phad olinadi. Maydon xarakteristikasining bunday tanlab olinishi, ya’ni xⁿ va x hadlar oralig‘idagi: x^n-1 , x^n-2 , …, x² hadlarning yo‘qligi modul bo‘yicha ko‘paytirish amalining samarali bajarilishini ta’minlaydi. Maydon xarakteristikasini ifodalovchi p(x)=xⁿ+x+1 ko‘phad primitiv bo‘lmasa, amallarning bajarilishi murakkablashadi hamda kriptografik samaradorlikka erishilmaydi. Misol uchun, bevosita hisoblash natijasida, n ning 1000 dan kichik bo‘lgan: 1, 3, 4, 6, 9, 15, 22, 28, 30, 46, 60, 63, 127, 153, 172, 303, 471, 532, 865, 900) qiymatlarida p(x)=xⁿ+x+1 ko‘phad primitivlik xossasiga ega bo‘ladi.