4-amaliy ish

4-amaliy ish

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.

Nazasir qism

Sonni tubligini aniqlovchi ko‘pgina usullar (algoritmlar) mavjud bo‘lib, ular orasida sonlarning ma’lum bir ko‘rinishi yoki strukturasiga bog‘liq bo‘lgan testlar hamda ixtiyoriy sonlar uchun sinov testlari ham mavjud. Ixtiyoriy sonlar uchun ishlab chiqilgan test sinovlari ham nazariy ham amaliy jihatdan katta qiymatga ega. Barcha mavjud tublikka sinash algoritmlarini ikki sinfga bo‘lish mumkin:

• 
  aniqlashtirilgan testlar - bu sinov natijasida tadqiq etilayotgan son tubmi yo yo‘qmiligining kafolatlangan aniq javobi beriladi;
  
• 
  ehtimolli testlar - bu sinovning natijasi yetarlicha katta ehtimollik bilan haqiqiy bo‘ladi. Bitta son uchun turli parametrlar bilan ularning ko‘p martalik takrorlanishi xatolik bo‘lishi ehtimolligini yetarlicha kichik qiymatli qilish imkonini beradi.
  

Tub sonlarni generasiya qilish ochiq kalitli kriptotizimlarni loyihalashda asosiy bosqichlardan biri, chunki ular asosida modul arifmetikasining hal qiluvchi elementi - moduli shakllantiriladi.
Tub sonlarni generasiya qilishda qo‘llaniladigan barcha algoritmlar ma’lum ehtimollik bilan tub sonni hosil qiladi. Bunda tublikka sinash algoritmlaridan foydalaniladi va ular hal qiluvchi ahamiyat kasb etadi. Sinash algoritmlari qanchalik ko‘p “tublik guvohlari”ni ko‘rsatsalar, sinalayotgan n sonining tub bo‘lish ehtimolligi shunchalik katta bo‘ladi.
Odatda, katta tub sonlarni generasiya qilishda quyidagi yondoshuvdan foydalaniladi:

1. 
   Tasodifan berilgan uzunlikdagi (bitlar soni bo‘yicha) toq son n tanlanadi.
   
2. 
   Tublikka sinash (test) o‘tkaziladi.
   
3. 
   Agar 𝑛 murakkab son bo‘lsa, u holda 1-qadamga qaytiladi.