Guruh: cry002-1 Toshkent 2023 Mavzu: Sonlarni tublikka tekshirish algoritmlari va ularning dasturiy ta’minotini ishlab chiqish Ishdan maqsad

O`zbekiston Respublikasi
Raqamli texnologiyalar vazirligi



Muhammad al- Xorazmiy nomidagi
Toshkent axborot texnologiyalari universiteti
Kiberxavfsizlik fakulteti
Kriptografiya 1
4-topshiriq


Tayyorladi: Jahongirov J.
Tekshirdi: Jabbarov N.
Guruh: CRY002-1


Toshkent 2023
Mavzu: Sonlarni tublikka tekshirish algoritmlari va ularning dasturiy ta’minotini ishlab chiqish
Ishdan maqsad: Tub sonlarn hosil qilish va va ularni tublikka tekshirish bo‘yicha amaliy ko‘nikmalarga ega bo‘lish.






2-amaliy ish
Mavzu: Eyler funksiyasi, berilgan modul bo‘yicha birlamchi ildizni hisoblovchi dasturiy ta‘minoti ishlab chiqish


Eyler funksiyasining multiplikativligi – Eyler funksiyasining asosiy xossalaridan biri bu uning multiplikativligidadir. Ikki o‘zaro tub sonlar uchun Eyler funksiyasining qiymati

ga teng bo‘ladi.
Natural son uchun Eyler funksiyasi qiymati quyidagicha hisoblanadi:

bu yerda tub son bo‘lib, ning barcha tub bo‘luvchilarini o‘z ichiga oladi.


Umumashtirilgan multiplikativlik
Yuqorida ta’kidlaganimizdek Eyler funksiyasi multiplikativ arifmetik funksiya hisobladi, ya’ni
,
Ushbu formulani umumlashtirish mumkin, agar va ning birdan farqli umumiy bo‘luvchisiga ega bo‘lsa.
Ixtiyoriy natural va uchun

bu yerda va ning eng katta umumiy bo‘luvchisi.
Eyler teoremasi
va o‘zaro tub sonlar uchun quyidagi tasdiq o‘rinli bo‘ladi

Ushbu teoremadan Ferma kichik teoremasi kelib chiqadi va bu sonlarni tublikka tekshirishda foydalaniladi.

modul bo‘yicha butun sonni tartibi
butun musbat son shunday bo‘ladigan mavjud bo‘lsin. ning tartibi ko‘rinishida ifodalanib, uning qiymati

shartni qanoatlantiruvchi ga teng bo‘ladi.
barcha , demak .