একটি ইনপুট নম্বর প্রাইম কিনা তা নির্ধারণ করার জন্য একটি প্রাথমিক পরীক্ষা হল একটি অ্যালগরিদম। কিছু প্রাথমিক পরীক্ষা নির্ধারক। তারা সর্বদা সঠিকভাবে সিদ্ধান্ত নেয় যে একটি সংখ্যা মৌলিক নাকি যৌগিক।
সবচেয়ে দ্রুত পরিচিত ডিটারমিনিস্টিক প্রাইমালিটি টেস্টটি 2004 সালে আবিষ্কৃত হয়েছিল। তিনজন কম্পিউটার বিজ্ঞানী আছেন, যেমন আগ্রাওয়াল, কায়াল এবং সাক্সেনা, AKS প্রাইমালিটি টেস্টের উদ্ভাবন করেছিলেন যা O˜ (log(n) 6 তে পরিচালিত হয়েছিল। ) সময়, যেখানে O˜ (f(n)) কে O(f(n) হিসেবে উপস্থাপন করা হয়।log(f(n)) k ) কিছু পূর্ণসংখ্যা k [1] জন্য। যদিও একটি উল্লেখযোগ্য অগ্রগতি, তথ্য সুরক্ষা প্রয়োজনীয়তার তুলনায় এই গতিটি বরং ধীর৷
মৌলিক সংখ্যার সুবিধা হল সেগুলিকে ক্রিপ্টোগ্রাফিতে ব্যবহার করা হয়। স্ট্যান্ডার্ড ক্রিপ্টোসিস্টেমগুলির মধ্যে একটি -আরএসএ অ্যালগরিদমের কী হিসাবে একটি মৌলিক সংখ্যা প্রয়োজন যা সাধারণত 1024 বিটের বেশি হয় উচ্চতর নিরাপত্তা প্রদানের জন্য৷
এত বড় সংখ্যার সাথে পরিচালনা করার সময়, নিম্নলিখিত পদ্ধতিটি অবশ্যই কোন ভাল তৈরি করে না। এত বড় সংখ্যার সাথে কাজ করা কেবলমাত্র নয়, বিশেষ করে যখন সঞ্চালিত অপারেশনগুলি প্রাথমিক পরীক্ষার সময় / এবং % হয়৷
তাই, উৎপাদিত সেরা প্রাইমালিটি টেস্টিং অ্যালগরিদমগুলি শুধুমাত্র প্রদত্ত সংখ্যাটি "সম্ভাব্য প্রাইম" বা যৌগিক কিনা তা নির্ধারণ করতে পারে৷
নিম্নলিখিত ধরণের প্রাথমিক পরীক্ষা রয়েছে যা নিম্নরূপ -
-
ডিটারমিনিস্টিক অ্যালগরিদম − একটি নির্ধারক প্রাইমালিটি টেস্টিং অ্যালগরিদম একটি পূর্ণসংখ্যা গ্রহণ করে এবং ক্রমাগত একটি মৌলিক বা যৌগিক আউটপুট করে। এই অ্যালগরিদম সবসময় একটি সঠিক উত্তর প্রদান করে।
-
বিভাজ্যতা অ্যালগরিদম − সহজতম প্রাথমিক পরীক্ষা নিম্নরূপ -
একটি ইনপুট সংখ্যা n দেওয়া হয়েছে, 2 থেকে n -1 পর্যন্ত কোনো পূর্ণসংখ্যা n কে ভাগ করে কিনা তা পরীক্ষা করে। যদি n কোনো m দ্বারা বিভাজ্য হয়, তাহলে n যৌগিক অন্যথায় এটি একটি মৌলিক। যাইহোক, n – 1 পর্যন্ত সমস্ত m পরীক্ষা করার পরিবর্তে, শুধুমাত্র m √n পর্যন্ত পরীক্ষা করা গুরুত্বপূর্ণ। যদি n যৌগিক হয় তাহলে থিনিট দুটি মানের মধ্যে ফ্যাক্টর করা যেতে পারে, যার মধ্যে অন্তত একটি √n-এর থেকে কম বা একই হওয়া উচিত।
-
সম্ভাব্য অ্যালগরিদম - একটি সম্ভাব্য অ্যালগরিদম এমন একটি উত্তর প্রদান করে যা বেশিরভাগ সময় সঠিক হয়, কিন্তু সব সময় নয়। এই পরীক্ষাগুলি সিদ্ধান্ত নিয়েছে যে n এক বা একাধিক শর্ত পূরণ করে যা সমস্ত প্রাইমকে সন্তুষ্ট করা উচিত। একটি সম্ভাব্য অ্যালগরিদম একটি প্রাইম বা একটি যৌগিক পুনরুদ্ধার নিম্নলিখিত নিয়মগুলির উপর নির্ভর করে -
-
যদি পরীক্ষিত পূর্ণসংখ্যা প্রকৃতপক্ষে একটি মৌলিক হয়, তাহলে অ্যালগরিদম অবশ্যই প্রাইম প্রদান করবে।
-
যদি পরীক্ষিত পূর্ণসংখ্যাটি প্রকৃতপক্ষে একটি যৌগিক হয়, তবে এটি সম্ভাব্যতা 1 − ε সহ একটি যৌগিক প্রদান করে, তবে এটি সম্ভাব্যতা ε সহ একটি মৌলিক প্রদান করতে পারে। ভুলের সম্ভাবনা বাড়ানো যেতে পারে যদি এটি অ্যালগরিদম 'm' বার চালাতে পারে এবং ত্রুটির সম্ভাবনা Σ m এ হ্রাস পায় .
-
ফার্ম্যাট প্রাইমালিটি টেস্ট − ফার্মাট প্রাইমালিটি টেস্ট ফার্ম্যাটের লিটল থিওরেম থেকে উদ্ভূত হয়, যা বলে যে n যদি প্রাইম হয়, a
n−1
≡ 1 (mod n)। একটি ইনপুট n এবং a
