মিলার-রাবিন পারমালিটি পরীক্ষা একটি শক্তিশালী সিউডোপ্রাইম খুঁজে পেতে ক্লাসিক পদ্ধতিতে ফার্মাট পরীক্ষা এবং ফার্মাট রুট পরীক্ষাকে একত্রিত করে। এই পরীক্ষায়, এটি একটি বিজোড় সংখ্যা m এবং 2 এর শক্তির গুণফল হিসাবে n – 1 লিখতে পারে:
$$\mathrm{n-1=m\, x\, 2^{k}}$$
বেস এ ফার্ম্যাট পরীক্ষাটি এভাবে তৈরি করা যেতে পারে:
$$\mathrm{a^{n-1}\, =\, a^{m\, x\, 2k}=\left [ a^{m} \right ]^{2k}=\left [ a^ {m} \right ]\frac{2^{2}\cdot \cdot \cdot 2}{K\, times}}$$
অন্য কথায়, a n−1 গণনা করার পরিবর্তে (mod n) এক ধাপে, এটা k+1 ধাপে করতে পারে। k + 1 ব্যবহার করার সুবিধা হল বর্গমূল ধাপের প্রতিটি ধাপ প্রয়োগ করা যেতে পারে। বর্গমূল পরীক্ষা ব্যর্থ হলে, এটি থামাতে পারে এবং n কে যৌগিক সংখ্যা হিসাবে ঘোষণা করতে পারে।
প্রতিটি ধাপে, এটি প্রদান করতে পারে যে ফার্ম্যাট পরীক্ষা পাস করা হয়েছে এবং বর্গমূল পরীক্ষাটি সন্নিহিত ধাপগুলির সমস্ত গ্রুপের মধ্যে সন্তুষ্ট, যদি অ্যাক্সেসযোগ্য হয় (যদি ফলাফল 1 হয়)।
শুরু করা
-
এটি একটি বেস a নির্বাচন করতে পারে এবং $\mathrm{T\, =\, a^{m}}$ গণনা করতে পারে, যার মধ্যে $\mathrm{m\, =\, \frac{n-1}{2^{k }}$
-
T + 1 বা -1 হলে ঘোষণা করুন যে n একটি শক্তিশালী সিউডোপ্রাইম এবং থামুন। কারণ যদি T+-1 হয়, T পরবর্তী ধাপে 1 হয়ে যাবে এবং যতক্ষণ না এটি ফার্মাটেস্টে উত্তীর্ণ হয় ততক্ষণ 1 থাকবে। তাছাড়া, T বর্গমূল পরীক্ষায় উত্তীর্ণ হয়েছে কারণ T পরবর্তী ধাপে 1 হতে পারে এবং 1 এর বর্গমূল (পরবর্তী ধাপে) +-1।
-
যদি T অন্য কিছু হয় তবে n একটি মৌলিক বা যৌগিক কিনা তা নিশ্চিত নয়, তাই এটি পরবর্তী ধাপে যেতে পারে।
পদক্ষেপ1 :আমরা T
বর্গক্ষেত্র-
ফলাফল +1 হলে, এটা নিশ্চিতভাবে জানা যায় যে ফার্ম্যাট পরীক্ষা পাস করা হবে কারণ পরবর্তী পরীক্ষাগুলোর জন্য T রয়ে গেছে 1। বর্গমূল পরীক্ষা পাস করা হয়নি. কারণ এই ধাপে T হল 1 এবং আগের ধাপে +-1 ছাড়া অন্য কিছু ছিল এটি n কে কম্পোজিট এবং স্টপ হিসাবে ঘোষণা করতে পারে।
-
ফলাফল -1 হলে, এটি বুঝতে পারে যে n অবশেষে ফার্ম্যাট পরীক্ষায় উত্তীর্ণ হবে৷ এটি এটিও বুঝতে পারে যে এটি বর্গমূল পরীক্ষায় উত্তীর্ণ হবে কারণ T এই ধাপে -1 এবং পরবর্তী ধাপে 1 হয়ে যায়৷ এটি n কে শক্তিশালী সিউডোপ্রাইম এবং স্টপ হিসাবে ঘোষণা করতে পারে।
-
যদি T অন্য কিছু হয়, তবে এটি একটি প্রাইম করতে পারে কি না তা নিশ্চিত নয়। এটি পরবর্তী ধাপে চালিয়ে যান।
ধাপ 2 থেকে ধাপ K – 1:
এই ধাপটি এবং নিম্নলিখিত সমস্ত পদক্ষেপগুলি ধাপ 2 পর্যন্ত চলতে থাকে এবং ধাপ K -1 পর্যন্ত ধাপ 1 এর সমান।
ধাপ K:
এই পদক্ষেপ প্রয়োজন হয় না. যদি এটি এই ধাপে পৌঁছাতে পারে এবং এটি সিদ্ধান্ত না তৈরি করে তবে এই পদক্ষেপটি আমাদের প্রদান করবে না। এই ধাপের ফলাফল 1 হলে, Fermat পরীক্ষাটি গৃহীত হয়, কিন্তু পূর্ববর্তী ধাপের ফলাফল +-1 না হওয়ায় বর্গমূল পরীক্ষা গ্রহণ করা হয় না। ধাপ k -1 এর পরে, যদি এটি ইতিমধ্যে বন্ধ না হয়ে থাকে তবে এটি ঘোষণা করতে পারে যে n কম্পোজিট। ধাপ 0 থেকে ধাপ K-1 পর্যন্ত মিলার-রাবিন পরীক্ষা প্রয়োজন।
