Miller-Rabin Test — Toq sonning tub yoki murakkabligini modular darajalar orqali tekshiradigan tez ehtimolli primality testi. Uning to‘g‘ri qo‘llanishi ishlash mexanizmi, kirish shartlari va natija kafolatini birgalikda tushunishni talab qiladi.
Matematik model
n−1=d·2^s, d toq ko‘rinishga ajratiladi. Tasodifiy a baza uchun x=a^d mod n hisoblanadi; x 1 yoki n−1 bo‘lmasa, s−1 marta kvadratlanib n−1 izlanadi. Shart bajarilmasa a compositeness witnessidir.
Miller-Rabin Testni dasturda qo‘llashdan oldin kirish modeli aniq belgilanadi: ma’lumot turi, indekslash, graf yo‘nalishi, ehtimollik taqsimoti yoki arifmetik aniqlik haqidagi farazlar algoritm kafolatining bir qismidir. Nazariy shart bajarilmasa, tez va xatosiz ishlagan kod ham mazmunan noto‘g‘ri javob berishi mumkin. Shu sabab API kirishni tekshiradi yoki cheklovni hujjatida ochiq bildiradi.
Samaradorlik
Murakkab son uchun tasodifiy bazaning xato ehtimoli raundiga ko‘pi bilan 1/4. Bir nechta mustaqil baza xatoni kamaytiradi. Ma’lum bit diapazonlarida belgilangan bazalar testi deterministik qiladi. n<4 va juft sonlar alohida.
Miller-Rabin Test samaradorligi faqat Big O bilan baholanmaydi. Real natijaga graf zichligi, alphabet hajmi, cache lokaliteti, priority queue amallari, katta son arifmetikasi va tasodifiy generator xarajati ta’sir qilishi mumkin. Benchmark odatiy kirish bilan birga noqulay taqsimot, maksimal o‘lcham va ko‘p dublikatli holatlarni ham qamrab oladi. Natijaning to‘g‘riligi esa alohida etalon yoki invariant bilan tasdiqlanadi.
Foydalanish holatlari
Katta tub nomzodlar, RSA kalit generatsiyasi va faktorizatsiyadan oldingi filtrda qo‘llanadi.
Miller-Rabin Test tanlanganda preprocessing narxi, bitta operatsiya yoki so‘rov vaqti, xotira sarfi va natijaning aniqligi birga baholanadi. Bir martalik kichik kirishda sodda usul afzal bo‘lishi mumkin; ko‘p takrorlanadigan yoki katta ma’lumotda esa tayyorlov xarajati keyingi amallar hisobiga qoplanadi. Nazariy ustunlik real ish yukida profil orqali tasdiqlanadi.
Sinov usuli
Kichik diapazon sieve bilan, Carmichael sonlari va ma’lum pseudoprimelar bilan tekshiriladi; modular multiplication overflow bermasligi zarur.
Miller-Rabin Test implementatsiyasida xato holati ham interfeysning bir qismidir. Bo‘sh kirish, mavjud bo‘lmagan yechim, overflow, yetarli bo‘lmagan aniqlik yoki noto‘g‘ri parametr uchun qaytariladigan qiymat oldindan belgilanadi. Diagnostika foydali bo‘lishi uchun versiya va asosiy parametrlar qayd etiladi, lekin katta yoki maxfiy kirish to‘liq jurnalga chiqarilmaydi. Property-based test tasodifiy kichik misollarda matematik xususiyatlarni muntazam tekshiradi.
+## Ichki invariant
Miller–Rabin composite witness topsa natija qat’iy murakkabdir; “probably prime” javobi esa tanlangan bazalarga nisbatan testdan o‘tganini bildiradi. Kriptografik kalit generatsiyasida trial division va bir necha raund birga ishlatiladi.
Miller-Rabin Test ishlab chiqarish muhitida qo‘llanganda natija bilan birga algoritm versiyasi, asosiy parametrlar va kirishning muhim xususiyatlari qayd etiladi. Kuzatuv ko‘rsatkichlari mavzuga mos tanlanadi: DFS chuqurligi, kengaytirilgan tugunlar, hash collisionlari, qabul qilish ulushi, sample variance, interval aniqligi yoki kodlangan baytlar soni shular jumlasidandir. Chegara qiymati oshsa, avval correctness invariantlari tekshiriladi, keyin profiling orqali qimmat bosqich aniqlanadi. Bu yondashuv nazariy kafolat bilan amaldagi xatti-harakat orasidagi farqni ko‘rsatadi.
Miller-Rabin Test bo‘yicha test ma’lumotlari faqat tasodifiy kirishdan iborat bo‘lmaydi. Nazariy eng yomon holat, ko‘p teng qiymat, minimal o‘lcham va chegaraga yaqin arifmetik qiymatlar alohida sinov to‘plamida saqlanadi.
Bog‘liq tushunchalar
Miller–Rabin test, primality test, modular exponentiation, witness, pseudoprime, RSA