1-ma’ruza Mavzu: rsa ochiq kalitli shifrlash algoritmi Reja

12.2-misol.10 gacha bo‘lgan tub sonlarni sanab bering.
Yechim. 10 tagacha to‘rtta tub son bor: 2, 3 5 va 7. Qizig‘i shundaki, 1-10 oralig‘idagi tub sonlar 40 foizni tashkil qiladi. Oraliq oshgan sari, foiz kamayadi.
O’zaro tub sonlar
Ikkita natural va butun son nart bajarilsa, o‘zaro tub son deyiladi, chunki 1 ixtiyoriy butun son bilan o‘zaro tub sondir. Agar soni tub bo‘lsa, 1 dan to gacha bo‘lgan barcha sonlar ,soniga o‘zaro tub sonlar hisoblanadi.
Tub sonlar miqdori
Tub sonlar miqdori cheksizdir. Biz zaif dalil keltiramiz. Faraz qilaylik, tub sonlar to‘plami cheklidir va eng katta songa teng bo‘lsin. Ushbu to‘plamga kiritilgan barcha tub sonlarni ko‘paytiramiz va natijani olamiz  . Butun son katta bo‘luvchiga ega bo‘lolmaydi.  (p – ‘eng katta tub son). U holda bu omil .ning omillaridan biri bo‘lishi kerak. Bu ni ga bo‘linishini anglatadi. Agar bo‘linsa, u holda bo‘linadi . 1 ga bo‘linadigan yagona son., 1 - bu asosiy son emas. Demak, soni dan katta bo‘lishi kerak va tub sonlar soni cheklangan son bilan cheklanmaydi.
Butun sonlar to‘plami cheksizdir.
Phi-funksiya Eylera
Eylerning unktsiyasi, FI, ba’zan Elerning totemi deb ataladi, kriptografiyada juda muhim rol o‘ynaydi. Eyler funksiyasi  da gacha bo‘lgan   bilan o‘zaro tub sonlarni aks ettiradi. Modul arifmetikasidan Z_n to‘plam bu dan katta bo‘lmagan va n bilan o‘zaro tub bo‘lgan sonlar ekanligini yeslab o‘tamiz.
funktsiyasi ushbu to‘plamdagi elementlar sonini hisoblab chiqadi. Quyida ushbu qiymatni qanday topish mumkinligi ko‘rsatilgan.

1. 
   .
   
2. 
   , agar  — tub son bo‘lsa.
   
3. 
   , agar m va n — o‘zaro tub bo‘lsa.
   
4. 
   , agar p — tub bo‘lsa.
   

Ushbu to‘rtta qoidani, ifoda topish uchun birlashtirishimiz mumkin. .

E’tibor qilish juda muhimki, agar sonini topish mumkin bo‘lsa va -ni tub sonlarning ajralishi sifatida ifodalash mumkin bo‘lsa, katta raqamlar uchun qiymatini topish mumkin. Boshqacha qilib aytganda, ni topish qiyinligi -ning kengayishini topish qiyinligiga bog‘liq. Bu keyingi bo‘limda muhokama qilinadi.
ni topish qiyinligi sonining faktorlash qiyinligiga bog‘liq.