মিলার-রাবিন প্রাইম্যালিটি টেস্টিং প্রসিডিউর (Procedure)
মিলার-রাবিন প্রাইম্যালিটি টেস্ট ফারমেট টেস্ট এবং ফারমেট রুট টেস্ট-কে ক্লাসিক্যালি কম্বাইন করে একটি স্ট্রং সিউডোপ্রাইম (strong pseudoprime) খুঁজে বের করে।
গাণিতিক ভিত্তি
n - 1 কে একটি বিজোড় সংখ্যা m এবং ২-এর পাওয়ারের গুণফলে লিখা হয়:
n - 1 = m × 2k
বেস a-এ ফারমেট টেস্ট:
an-1 = am × 2k = [am]2k = [am]2×2×...×2 (k বার)
অর্থাৎ an-1 (mod n) এক ধাপে না করেই k+1 ধাপে করা হয়। সুবিধা: প্রতিটি ধাপে স্কয়ার রুট টেস্ট করা যায়। যদি স্কয়ার রুট টেস্ট ফেইল করে, তাহলে রুকিয়ে n-কে কম্পোজিট ঘোষণা করা যায়।
প্রতিটি ধাপে নিশ্চিত করা হয়: ফারমেট টেস্ট পাস হয়েছে এবং সব এডজাসেন্ট ধাপের মাঝে স্কয়ার রুট টেস্ট স্যাটিসফাইড (যদি রেজাল্ট ১ হয়)।
ইনিশিয়ালাইজেশন (Initialization)
- বেস a সিলেক্ট করুন এবং T = am ক্যালকুলেট করুন, যেখানে m = (n-1)/2k।
- যদি T = +1 বা -1 হয়: n-কে স্ট্রং সিউডোপ্রাইম ঘোষণা করুন এবং থামুন। কারণ T = ±1 হলে পরবর্তী ধাপে ১ হয়ে যাবে এবং ফারমেট টেস্ট পাস করবে। 더불어 স্কয়ার রুট টেস্টও পাস (১-র স্কয়ার রুট ±1)।
- যদি T অন্য কিছু হয়: নিশ্চিত নয় যে প্রাইম নাকি কম্পোজিট, পরবর্তী ধাপে যান।
স্টেপ ১ (Step 1)
- T কে স্কয়ার করুন (T ← T² mod n)।
- ফলাফল +1: ফারমেট টেস্ট অবশ্যই পাস হবে (T থাকবে ১)। কিন্তু স্কয়ার রুট টেস্ট ফেইল—কারণ এই ধাপে T=১ কিন্তু পূর্ব ধাপে T ≠ ±1। → n কম্পোজিট, থামুন।
- ফলাফল -1: n ফারমেট টেস্ট পাস করবে। স্কয়ার রুট টেস্টও পাস (এই ধাপে -1, পরবর্তীতে ১)। → n স্ট্রং সিউডোপ্রাইম, থামুন।
- অন্য ফলাফল: নিশ্চিত নয়, পরবর্তী ধাপে যান।
স্টেপ ২ থেকে স্টেপ K-1
এই ধাপগুলো স্টেপ ১-এর সমান। চেইন চলতে থাকে।
স্টেপ K (ফাইনাল স্টেপ)
- এই ধাপ প্রয়োজন নেই। যদি এখানെയেও ডিসিশন না হয়, এই ধাপ কিছুই দেবে না।
- ফলাফল ১ হলে ফারমেট টেস্ট পাস, কিন্তু পূর্ব ধাপ ±1 নয় বলে স্কয়ার রুট টেস্ট ফেইল।
- স্টেপ k-1 পরেও যদি থামতে না পারা হয়, n কম্পোজিট ঘোষণা করুন।
- মিলার-রাবিন টেস্ট স্টেপ ০ থেকে স্টেপ K-1 পর্যন্ত চালানো হয়।
