1- amaliy ish Mavzu: Modulyar arifmetika. Evklid va kengaytirilgan Evklid algoritmi hamda ularning dasturiy ta‘minotini ishlab chiqish. Ishdan maqsad

¹- amaliy ish
Mavzu: Modulyar arifmetika. Evklid va kengaytirilgan Evklid algoritmi hamda ularning dasturiy ta‘minotini ishlab chiqish.
Ishdan maqsad: O‘zaro tub sonlar va modul amali xossalari, Modul arifmetikasida effiktiv usuldan foydalanish, Evklid va Evklidning kengaytirilgan algoritmi haqida nazariy va amaliy ko‘nikmalarga ega bo‘lish.
Nazariy qism
Natural sonlar to‘plamini va butun sonlar to‘plamini ko‘rinishda belgilaymiz.
Noldan farqli bo‘lgan soni va sonlar –to‘plamga tegishli, ya’ni bo‘lib, bo‘lsin., agarda shunday soni mavjud bo‘lib, tenglik bajarilsa, u holda, soni sonini bo‘ladi deyiladi.
Berilgan va sonlarni bo‘luvchi butun son, ularning umumiy bo‘luvchisi deyiladi. Umumiy bo‘luvchilar ichida eng kattasi eng katta umumiy bo‘luvchi deyiladi va ko‘rinishda belgilanadi. Agarda va sonlarning eng katta umumiy bo‘luchisi bo‘lsa, a va b sonlar o‘zaro tub deyiladi.
Berilgan natural son tub deyiladi, agarda bu son o‘zi va dan boshqa natural songa bo‘linmasa.
Misol uchun: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, tub sonlar, ular sanoqli va cheksiz quvvatli to‘plamni tashkil etadi. Kelgusida, barcha butun sonlarni modul (xarakteristika) deb ataluvchi biror fiksirlangan natural soniga bo‘lganda qoladigan qoldiqlar bilan bog‘liq holda qaraymiz. Bunda cheksiz quvvatli (elementlari soni cheksiz) bo‘lgan barcha butun sonlar to‘plamiga, dan gacha bo‘lgan butun sonlarni o‘z ichiga oladigan chekli, quvvati ga teng bo‘lgan to‘plam mos qo‘yiladi.
Bu quyidagicha amalga oshiriladi: va –natural sonlar bo‘lsa, “ sonini soniga qoldiq bilan bo‘lish”, deganda ushbu , bu yerda shartni qanoatlantiruvchi natural va sonlarini topish tushuniladi. Bu oxirgi tenglikda qoldiq deb ataluvchi soni nolga teng bo‘lsa , natural soni soniga bo‘linadi yoki soni sonining bo‘luvchisi deyiladi.
Butun va sonlari modul bo‘ycha taqqoslanadigan deyiladi, agarda ularni n ga bo‘lganda qoladigan qoldiqlari teng bo‘lsa, hamda, deb yoziladi. Bundan esa va sonlar ayirmasining ga qoldiqsiz bo‘linishi kelib chiqadi.
Qoldiqni ifodalash uchun ushbu tenglikdan foydalaniladi, hamda tenglikni qanoatlantiruvchi sonini topish sonini modul bo‘yicha keltirish deyiladi.
Biror modul bo‘yicha qo‘shish, ayirish va ko‘paytirish amallariga nisbatan quyidagi kommutativlik, assotsiativlik va distributivlik munosabatlari o‘rinli:




Quyida modul amallari bilan bog‘liq bir nechta misollar keltirib o‘tilgan:

1. 
   tenglikda bo‘lgan holda, natijani hisoblash uchun ni ga bo‘lib, qoldig‘i olinadi. Masalan,
   
2. 
   tenglikda va bo‘lgan holda, a ga toki yig‘inda noldan katta bo‘lgunga qadar n qo‘shiladi. Masalan, ; ;
   
3. 
   tenglikda kasr son bo‘lgan holda, tenglik quyidagi tenglikka keltiriladi. ga teng bo‘lsa, butun son bo‘ladi. Olingan tenglikdan ning o‘rniga qiymat berish orqali tenglik bajaralishi tekshiriladi. Tenglik bajarilsa, unda ga o‘zlashtiriladi. Bu usul ko‘p vaqt talab etadi. Shuning uchun amalda Evklidning kengaytirilgan algoritmining xususiy holidan foydalaniladi.
   

qoldiqni hisoblashning effektiv usuli
RSA , EL-GAMAl asimmetrik kriptotizimlarda ma’lumotlarni shifrlash, deshifrlash va bu shifrlash algoritmlari bilan bog‘liq bo‘lgan boshqa parametrlarni hisoblash uchun taqqoslamani hisoblashga to‘g‘ri keladi. Agar berilgan , , sonlar katta razryadli sonlardan iborat bo‘lsa, taqqoslamani hisoblash masalasi hatto eng zamonaviy kopyuterlarda ham ancha mushkul hisoblanadi. Anashu maqsadda bunday taqqoslamalarni hisoblashning effektiv usullarini bilish muhimdir. Shunday algoritmlardan biri haqida to‘xtalib o‘tamiz.
Algoritm quyidagi qadamlardan iborat :