তথ্য নিরাপত্তাতে প্রাইম্যালিটি টেস্টিং (Primality Testing) কী?

প্রাইম্যালিটি টেস্টিং (Primality Testing) — তথ্য নিরাপত্তা

প্রাইম্যালিটি টেস্ট হলো একটি অ্যালগরিদম যা ইনপুট নম্বর প্রাইম কিনা তা নির্ধারণ করে। কিছু টেস্ট ডিটারমিনিস্টিক (Deterministic)—সর্বদা সঠিকভাবে প্রাইম বা কম্পোজিট বলে।

ডিটারমিনিস্টিক টেস্টের গতি

• সবচেয়ে দ্রুত ডিটারমিনিস্টিক প্রাইম্যালিটি টেস্ট ২০০৪ সালে আবিষ্কৃত (Agrawal, Kayal, Saxena — AKS প্রাইম্যালিটি টেস্ট)।
• টাইম কমপ্লেক্সিটি: Õ(log⁶ n) = O(log⁶ n × log(log n)ᵏ)।
• ব্রেকথ্রু হলেও ইনফো সিকিউরিটির দরকারের চেয়ে ধীর।

প্রাইম নম্বরের ক্রিপ্টোগ্রাফিক গুরুত্ব

• প্রাইম নম্বর ক্রিপ্টোগ্রাফিতে ব্যবহৃত হয়। RSA অ্যালগরিদম-এ ১০২৪+ বিট প্রাইম কী দরকার হায় সিকিউরিটির জন্য।
• এত বড় নম্বরের সাথে কাজ করা কঠিন, বিশেষ করে / এবং % অপারেশন প্রাইম্যালিটি টেস্টে।
• তাই সেরা প্রাইম্যালিটি টেস্টিং অ্যালগরিদমগুলো শুধু "প্রবাবলিস্টিক প্রাইম" (Probable Prime) বা কম্পোজিট বলে—নিশ্চিত প্রাইম বলে না।

প্রাইম্যালিটি টেস্টিং-এর প্রকারভেদ

১. ডিটারমিনিস্টিক অ্যালগরিদম (Deterministic Algorithm)

• ইনপুট ইন্টিজার নেয়, আউটপুট সবসময় "প্রাইম" বা "কম্পোজিট"। সর্বদা সঠিক উত্তর দেয়।

২. ডিভিজিবিলিটি অ্যালগরিদম (Divisibility Algorithm)

• সিম্পলেস্ট টেস্ট: ইনপুট n দিয়ে ২ থেকে n-1 পর্যন্ত যেকোনো ইন্টিজার n-কে ভাগ করে কিনা চেক। ভাগ করলে কম্পোজিট, নাইলে প্রাইম।
• অপ্টিমাইজেশন: √n পর্যন্ত চেক করলেই হবে। কম্পোজিট হলে দুটি ফ্যাক্টরের কমপক্ষে একটি ≤ √n।

৩. প্রবাবলিস্টিক অ্যালগরিদম (Probabilistic Algorithm)

• উত্তর অধিকাংশ সময় সঠিক, সবসময় নয়।
• চেক করে যে n প্রাইমদের স্যাটিসফাই করার শর্তগুলো পূরণ করে কিনা।
• আউটপুট নিয়ম:
  • ইনপুট আসলে প্রাইম হলে → নিশ্চিত "প্রাইম"।
  • ইনপুট আসলে কম্পোজিট হলে → প্রোবাবিলিটি 1-ε দিয়ে "কম্পোজিট", প্রোবাবিলিটি ε দিয়ে "প্রাইম" (ভুল)।
  • m বার রান করলে এরর প্রোবাবিলিটি ε^m।

ফারমেট প্রাইম্যালিটি টেস্ট (Fermat Primality Test)

• ফারমেটস লিটল থিওরেম থেকে: n প্রাইম হলে a^n-1 ≡ 1 (mod n)।
• ইনপুট n এবং a < n দিয়ে চেক: a^n-1 ≡ 1 (mod n)? না হলে কম্পোজিট, হলে "প্রবাবলি প্রাইম"।
• দুর্বলতা: হাই এরর রেট—অনেক কম্পোজিট "প্রবাবলি প্রাইম" হিসেবে ফেলস পজিটিভ দেয় (কারমাইকেল নম্বর)।