Guruh talabasi Yigitaliyev Fazliddin

Multiplikativ identifikatsiya Multiplikativ identifikatsiya har doim 1 ga teng. Masalan, GF(28), multiplikativ teskari bit 00000001

Misol uchun 4.20
GF(24) da (x2 + 1) modulning (x4 + x + 1) teskarisini toping.
Yechish
Biz kengaytirilgan Evklid algoritmidan 4.5-jadvaldagidek foydalanamiz:
Jadval 4.5

Bu (x2 + 1)−1 modul (x4 + x + 1) (x3 + x + 1) ekanligini bildiradi. Javob oson bo'lishi mumkin
ikki ko'phadni ko'paytirish va natija bo'linganda qoldiqni topish bilan isbotlangan moduli bo'yicha.


Misol uchun 4.21
GF(28) da (x5) modulning teskarisini toping (x8 + x4 + x3 + x + 1)

Yechim
4.6-jadvalda ko'rsatilganidek, kengaytirilgan Evklid algoritmidan foydalaning:

Jadval 4.6

Bu (x5)−1 modul (x8 + x4 + x3 + x + 1) (x5 + x4 + x3 + x) ekanligini bildiradi. Javob bo'lishi mumkin ikki ko'phadni ko'paytirish va natija bo'lganda qoldiqni topish orqali osonlik bilan isbotlanadi
modulga bo'linadi.

Kompyuter yordamida ko'paytirish
Bo'linish operatsiyasi tufayli yozishda samaradorlik muammosi mavjud ikkita polinomni ko'paytirish dasturi. Kompyuterni amalga oshirish yaxshiroq foydalanadi kichraytirilgan ko'phadni x ga qayta-qayta ko'paytirish algoritmi. Masalan, o'rniga (x2 ⊗ P2) ning natijasini topsa, dastur (x ⊗ (x ⊗ P2)) natijasini topadi. The Ushbu strategiyaning foydasi yaqinda muhokama qilinadi, lekin avvaliga misol keltiramiz jarayonini ko'rsatish.
Misol uchun 4.22
GF(28) da P1 = (x5 + x2 + x) ni P2 = (x7 + x4 + x3 + x2 + x) ga ko‘paytirish natijasini toping. Kamaytirilmaydigan ko'phad (x8 + x4 + x3 + x + 1) yuqorida tavsiflangan algoritm.

Yechish
Jarayon 4.7-jadvalda ko'rsatilgan. Biz birinchi navbatda x0, x1, x2, x3, x4 ko'paytirishning qisman natijasini topamiz va x5 - P2. E'tibor bering, faqat uchta atama kerak bo'lsa-da, xm ⊗ P2 ko'paytmasi m uchun 0 dan 5 gacha hisoblab chiqiladi, chunki har bir hisob avvalgi natijaga bog'liq.

Jadval 4.7

Yuqoridagi algoritm ikkita afzalliklarga ega. Birinchidan, ko'phadni x ga ko'paytirish
n-bitli so'zning bir bitli siljishi orqali osonlik bilan erishish mumkin; tomonidan taqdim etilgan operatsiya
umumiy dasturlash tillari. Ikkinchidan, natijani faqat agar kamaytirish kerak bo'lsa
polinomning maksimal quvvati n - 1. Bunday holda, kamaytirish osonlik bilan an orqali amalga oshirilishi mumkin
XOR moduli bilan ishlash, chunki natijada eng yuqori quvvat faqat 8. Biz
keyin har bir qisman natijani topish uchun oddiy algoritmni loyihalashi mumkin:
1. Agar oldingi natijaning eng muhim biti 0 bo'lsa, avvalgi natijani o'zgartiring
bir oz chapga.
2. Agar oldingi natijaning eng muhim biti 1 bo'lsa,
a. uni bir oz chapga siljiting va
b. eksklyuziv yoki eng muhim bitsiz modul bilan