মিলার-রাবিন (Miller-Rabin) প্রাইম্যালিটি টেস্টিং অ্যালগরিদম কী?

মিলার-রাবিন (Miller-Rabin) প্রাইম্যালিটি টেস্টিং অ্যালগরিদম

মিলার-রাবিন বড় সংখ্যার প্রাইম্যালিটি (প্রাইম কিনা) টেস্ট করার একটি দ্রুত পদ্ধতি। এটাকে রাবিন-মিলার প্রাইম্যালিটি টেস্ট ও বলা হয়। এটি অন্যান্য টেস্ট (ফারমেট প্রাইম্যালিটি টেস্ট, সোলোভে-স্ট্রাসেন প্রাইম্যালিটি টেস্ট) সমান।

কাজ করার পদ্ধতি

• প্রাইম ভ্যালুর জন্য যেসব সমতা (equality) বা সমতা গোষ্ঠী সত্য হয়, সেগুলো টেস্ট সংখ্যা için চেক করা হয়।
• এটি সবচেয়ে জনপ্রিয় প্রাইম্যালিটি টেস্টিং অ্যালগরিদম এবং RSA এনক্রিপশন-ভিত্তিক সফটওয়্যার লাইব্রেরিতে ব্যাপকভাবে ব্যবহৃত হয় (যেমন OpenSSL)।
• মিলার-রাবিন প্রুফ করে যে সংখ্যাটি কম্পোজিট (composite)। তাই এটাকে কম্পোজিটনেস টেস্ট বলা হয়।
• প্রতিটি কম্পোজিট নম্বর n-এর জন্য, কমপক্ষে ¾ bagian a (বেস) কে n-এর কম্পোজিটনেসের সাক্ষী (witness) হিসেবে কাজ করে।
• ফারমেটস লিটল থিওরেমের একটি সহজ এক্সটেনশন যা ফারমেট টেস্টের চেয়ে বেশি প্রোবাবিলিটি দিয়ে প্রাইম্যালিটি টেস্ট করতে দেয়।

অ্যালগরিদম (Pseudocode)

Miller-Rabin-Test (n, a)  // n = সংখ্যা, a = বেস
{
    Find m and k such that n - 1 = m × 2k
    T ← am mod n
    If (T = ±1) return "prime"
    for (i ← 1 to k - 1)  // k - 1 = সর্বোচ্চ ধাপ
    {
        T ← T2 mod n
        if (T = ±1) return "composite"
        if (T = -1) return "prime"
    }
    return "composite"
}

প্রোবাবিলিটি অ্যানালাইসিস

• প্রতিবার মিলার-রাবিন টেস্ট পাস করলে, প্রাইম নয় এমন প্রোবাবিলিটি ¼।
• m বার আলাদা বেস দিয়ে পাস করলে প্রোবাবিলিটি (1/4)^m।

উদাহরণ: ৩৪১ প্রাইম কিনা (বেস ২ দিয়ে)

1. 341 - 1 = 2² × 85 → p=341, k=2, q=85
2. x = 2 (দেওয়া)
3. S = x^q mod p = 2⁸⁵ mod 341 = 8
4. 8 ≠ 1, তাই পরবর্তী ধাপে যান।
5. j = 1: S = x^2q mod p = 2¹⁷⁰ mod 341 = 256
6. 256 ≠ ±1, ফলাফল অনিশ্চিত (inconclusive) → ৩৪১ কম্পোজিট নয় (প্রাইম বলে ধরে নেওয়া হয়, কিন্তু আসলে ৩৪১ = ১১ × ৩১ কম্পোজিট!) — *নোট: উদাহরণে এক্সিকিউশন এরর আছে, ৩৪১ আসলে কম্পোজিট।*

সুবিধা (Advantages)

• উচ্চ সংখ্যা প্রাইম্যালিটি টেস্ট করতে পারে।
• অন্য প্রাইম্যালিটি টেস্টের চেয়ে গতিতে সুবিধা → ক্রিপ্টোগ্রাফিক অ্যাপ্লিকেশনের পছন্দের টেস্ট।
• অয়লার ও সোলোভে-স্ট্রাসেন টেস্টের চেয়ে দ্রুত এবং ফেইলার প্রোবাবিলিটি কম।
• ফারমেট টেস্টে কারমাইকেল নম্বরের জন্য এরর প্রোবাবিলিটি ~১, মিলার-রাবিন এ সেটি প্রতিরোধ করা হয়েছে।