মিলার রবিন বড় সংখ্যার প্রাথমিকতা পরীক্ষা করার জন্য একটি দ্রুত পদ্ধতি। এই অ্যালগরিদমটিকে রবিন-মিলার প্রাইমালিটি টেস্ট বলা হয় এবং এই অ্যালগরিদমটি নির্ধারণ করে যে সংখ্যাটি প্রাইম কিনা যা ফার্ম্যাট প্রাইমালিটি টেস্ট এবং সলোভে-স্ট্রাসেন প্রাইমালিটি টেস্ট সহ অন্যান্য পরীক্ষার জন্য একই।
এই পরীক্ষাটি সমতা বা সমতার গোষ্ঠীর উপর ভিত্তি করে যা মৌলিক মানগুলির জন্য সত্য ধারণ করে, এইভাবে পরীক্ষা করে যে তারা সংখ্যা ধরে রাখে কিনা, প্রাথমিকতার জন্য পরীক্ষা করা প্রয়োজন।
এই অ্যালগরিদমটি সবচেয়ে দরকারী পরিচিত প্রাথমিক পরীক্ষা অ্যালগরিদম এবং RSA এনক্রিপশনের উপর ভিত্তি করে বিভিন্ন সফ্টওয়্যার লাইব্রেরিতে ব্যবহার করা যেতে পারে এবং সেরা উদাহরণ হল OpenSSL৷
মিলার রাবিন যাচাই করেন যে সংখ্যাটি যৌগিক। তাই এটাকে প্রাইমালিটি টেস্ট না বলে কম্পোজিটনেস টেস্ট বলা হয়। মিলার রবিন পরীক্ষা সমস্ত কম্পোজিট সনাক্ত করে। প্রতিটি যৌগিক সংখ্যা n এর জন্য, সংখ্যার কমপক্ষে 3/4 (মিলার রবিন) হতে পারে a n-এর যৌগিকতার সাক্ষী।
মিলার রবিন হল ফার্মাটস লিটল থিওরেমের সহযোগীভাবে সহজ এক্সটেনশন যা আমাদেরকে ফার্মাটস লিটল থিওরেমের চেয়ে অনেক বড় সম্ভাবনার সাথে আদিমতার জন্য পরীক্ষা করতে সক্ষম করে।
অ্যালগরিদম :মিলার-রাবিন পরীক্ষার জন্য সিউডোকোড −
Miller-Rabin-Test (n, a) // n is the number; a is the base
{
Find m and k such that n − 1 = m x 2k
T ← am mod n
If (T = ±1)return "a prime"
for (i ← 1 to k − 1) // k – 1 is the maximum number of steps
{
T ← T2 mod n
if (T = ±1) return "a composite"
if (T = −1) return "a prime"
}
return "a composite"
} সেখানে exi একটি প্রমাণ যে প্রতিবার একটি সংখ্যা একটি মিলার-রাবিন পরীক্ষা পাস করে, সম্ভাব্যতা যে এটি একটি মৌলিক নয় ¼। যদি সংখ্যাটি m পরীক্ষায় উত্তীর্ণ হয় (m ভিন্ন পাস সহ), সম্ভাব্যতা যেটি প্রাইম নয় তা হল (1/4) m .
উদাহরণ :341 সংখ্যাটি যৌগিক কিনা তা পরীক্ষা করতে বেস 2 ব্যবহার করে মিলার-রাবিন অ্যালগরিদম প্রয়োগ করুন৷
সমাধান :মিলার-রাবিন অ্যালগরিদম ব্যবহার করে, আমরা 341 নম্বরটি নিম্নরূপ পরীক্ষা করতে পারি:
ধাপ 1:341 − 1 =2 2 x 85. এইভাবে p =341, k =2 এবং q =85
ধাপ 2:x =2 (প্রদত্ত)
ধাপ3:S =x q মোড p
=2 85 mod 341 =(2 10 ) x 2 5 মোড 341 8
=2 10 মোড 341 x 2 13 মোড 341
=1 x 8192 মোড 341 =8192 মোড 341
=8
ধাপ 4:8 ≠ 1 হিসাবে, আমরা পরবর্তী ধাপে চলে যাই।
ধাপ5:j =1, S =x 2q এর জন্য মোড p
=2 170 mod 341 =(2 20 ) 8 x 2 10 মোড 341
=2 20 মোড 341 x 2 8 মোড 341 x 2 10 মোড 341
=1 x 256 x 1 =256
এখন, =256 ≠ 1
এবং ফলাফল অনিশ্চিত
সুতরাং, 341 একটি যৌগিক সংখ্যা নয়।
সুবিধা
-
এই অ্যালগরিদমটি প্রাথমিকতার জন্য উচ্চ সংখ্যা পরীক্ষা করতে ব্যবহার করা যেতে পারে।
-
অন্যান্য প্রাথমিক পরীক্ষার তুলনায় গতির সুবিধার কারণে, মিলার রবিন পরীক্ষাটি বেশ কয়েকটি ক্রিপ্টোগ্রাফিক অ্যাপ্লিকেশনের জন্য পছন্দের পরীক্ষা হবে।
-
অয়লার এবং সলোভে-স্ট্রাসেন পরীক্ষার সাথে তুলনা করলে, মিলার রবিন আরও গতিশীল এবং অপরিহার্য দিক হল ব্যর্থতার সম্ভাবনা কমে যায়।
-
ফারম্যাট পরীক্ষা অনুসারে সমস্ত কারমাইকেল নম্বর n-এর জন্য অনেক বেশি মিথ্যাবাদী রয়েছে, ত্রুটির সম্ভাবনা 1 এর কাছাকাছি, এই অসুবিধাটি মিলার রাবিনে প্রতিরোধ করা হয়েছে।
