6- ma'ruza. To'liq va qisman tanlash algoritmlari reja

Miller-Rabin algoritmi.
U ham ikkinchi turdagi algoritmlarga kiradi, ya'ni ehtimollikdir. Uning murakkablik darajasini quyidagi formula bo'yicha aniqlash mumkin: O (k • log2n), bu erda k - o'tishlar soni. Qisqacha usulning mohiyatini quyidagicha ta'riflash mumkin: agar n > 2 natural son bo'lsa, u holda n -1 sonini n -1 ni 2 ga teng bo'lgan s ning t ga ko'paytirilishi bilan ifodalash mumkin. toq va s musbat bo'lishi kerak. U holda a son qiymati kamida bitta shart bajarilgan taqdirda n sonining soddaligiga guvoh bo'lishi mumkin: a ning t quvvati bir modul n ga teng bo'lsa; r butun soni mavjud.
Algoritmning ishonchlilik darajasi raqamning soddaligini tasdiqlovchi guvohlar sonining ko'payishi bilan ortadi.
Bu usul ochiq kalit mavjud bo'lgan kriptotizimlarda amaliy foydalanishni topadi. Bu nisbatan qisqa vaqt ichida etarlicha yuqori ehtimollik darajasi bilan raqamlarning tub sonlar guruhiga tegishliligini tekshirish imkonini beradi.
Ko'rib chiqilayotgan muammoni hal qilish usuli ham mavjud . Agraval - Kayal - Saxena (AKS) Yu, Poklington algoritmi, Fermat algoritmi.