মিলার রবিন প্রাইমালিটি টেস্ট
মৌলিক সংখ্যা বের করার অনেকগুলো উপায় আমরা জানি। খুব বেশি একটা উপায় না জানলেও ইরাটোস্থ্যানেস এর সিভ (Sieve of Eratosthenes) – এই অ্যালগোরিদমটি প্রায় সবাই জানি। কিন্তু বড় যেকোনো সংখ্যার ক্ষেত্রে সিভ মেথডটা অনেক বেশি সময় নেয়। তাই সিভ এর পাশাপাশি যদি আরো কয়েকটি অ্যালগোরিদম আমাদের জানা থাকে তাহলে প্রাইম নাম্বার বের করা নিয়ে আর সমস্যা হবে না। আমরা এখন মৌলিক সংখ্যা বের করার যে অ্যালগোরিদমটি দেখব সেটি হল- “মিলার-রবিন প্রাইমালিটি টেস্ট (Miller-Rabin Primality Test)”। মিলার-রবিন অ্যালগোরিদম ভালোভাবে বুঝতে গেলে আমাদের ফার্মাটের লিটল থিওরেম ভালোভাবে বুঝতে হবে। ফার্মাটের লিটল থিওরেম এপ্লাই করেও আমরা মৌলিক সংখ্যা বের করতে পারি। কিন্তু ফার্মাটের থিওরেমের কিছু সীমাবদ্ধতা আছে যার ফলে সব সংখ্যার জন্য নির্ভুল মান পাওয়া যায় না। আমরা প্রথমে ফার্মাটের লিটল থিওরেম দেখব, তারপর এর সীমাবদ্ধতা দেখব এবং সবশেষে ফার্মাটের লিটল থিওরেম ব্যবহার করে কিভাবে মিলার-রবিন প্রাইমালিটি টেস্ট কাজ করে তা দেখব। ফার্মাটের লিটল থিওরেমঃ ফার্মাটের লিটল থিওরেম অনুযায়ী, যদি n একটি মৌলিক সংখ্যা হয় এবং a যদি n এর চেয়ে ছোট যেকোন ধ