Texnologiyalari universiteti kriptografiyaning matematik asoslari

3.8. Sonlar nazariyasi elementlari
Sonlar nazariyasi kriptografik masalalarning tadqiq qilinishi hamda ularning yechimlarida muhim rol o‘ynaydi.
Natural sonlar to‘plamini N ={1, 2,3, … } va butun sonlar to‘plamini Z={0, _ 1,_ 2,  3, … } ko‘rinishda belgilaymiz.
Noldan farqli bo‘lgan a soni va b sonlar Z –to‘plamga tegishli, ya’ni a, b_ Z bo‘lib, a_ 0 bo‘lsin, agarda shunday s soni mavjud bo‘lib, b =as tenglik bajarilsa, u holda a soni b sonini bo‘ladi, deyiladi.
3.8.1. Eng katta umumiy bo‘luvchi
Berilgan a va v sonlarni bo‘luvchi butun son, ularning umumiy bo‘luvchisi deyiladi. Umumiy bo‘luvchilar ichida eng kattasi eng katta umumiy bo‘luvchi (EKUB) deyiladi va EKUB(a, b) ko‘rinishda belgilanadi. Agarda a va b sonlarning eng katta umumiy bo‘luvchisi 1, EKUB (a, b)=1 bo‘lsa, a va b sonlar o‘zaro tub deyiladi. Eng katta umumiy bo‘luvchilarni topishga oid tasdiqlarni keltiramiz.
1-lemma. Agar b soni a sonini bo‘lsa, u holda bu sonlarning eng katta umumiy bo‘luvchisi EKUB (a, b)= b, ya’ni a sonining umumiy bo‘luvchilari to‘plami b sonining umumiy bo‘luvchilari to‘plami bilan ustma-ust tushadi.
2-lemma. Agar a=bq+c bo‘lsa, u holda a va b sonlarining eng katta umumiy bo‘luvchisi b va s sonlarining eng katta umumiy bo‘luvchisi bilan ustmaust tushadi, ya’ni EKUB (a, b)= EKUB (b, c): a va b sonlarining umumiy bo‘luvchilari to‘plami b va s sonlarining umumiy bo‘luvchilari to‘plami bilan ustma-ust tushadi.
Yuqorida keltirilgan lemmalardan EKUBni topish – Yevklid algoritmi kelib chiqadi.
Haqiqatan ham quyidagi bo‘lish amallarini bajaramiz: a=bq₁+r₁, 0_ r₁₁q₂+r₂, 0_ r₂₁,
…………, …………,
rn-2=rn-1 qn+rn, 0 rn
U holda EKUB (a, b)= EKUB (b, r₁)=…=(r_n-2, r_n-1)= r_n .
Berilgan natural son p>1 tub deyiladi, agarda bu son o‘zi p va 1 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 n soniga bo‘lganda qoladigan qoldiqlar bilan bog‘liq holda qaraymiz. Bunda cheksiz quvvatli (elementlari soni cheksiz) bo‘lgan barcha butun sonlar to‘plamiga, 0 dan n-1 gacha bo‘lgan butun sonlarni o‘z ichiga oladigan chekli, quvvati n ga teng bo‘lgan {0; 1; 2; 3;…;n-1} – to‘plam mos qo‘yiladi. Bu quyidagicha amalga oshiriladi: a va n – natural sonlar bo‘lsa, “a sonini n soniga qoldiq bilan bo‘lish”, deganda ushbu a=qn+r, bu yerda 0_ r <n,
shartni qanoatlantiruvchi natural q va r sonlarini topish tushuniladi. Bu oxirgi tenglikda qoldiq deb ataluvchi r soni nolga teng bo‘lsa r=0, natural a soni n soniga bo‘linadi yoki n soni a sonining bo‘luvchisi deyiladi.