অয়লারের থিওরেম (Euler's Theorem) — তথ্য নিরাপত্তা
অয়লারের থিওরেম হলো ফারমেটস লিটল থিওরেমের জেনারেলাইজেশন (Generalization) যা পজিটিভ ইন্টিজার মডুলো ইন্টিজারের পাওয়ার নিয়ে কাজ করে। এটি মৌলিক সংখ্যা তত্ত্বের প্রয়োগে (যেমন RSA ক্রিপ্টোসিস্টেমের থিওরেটিক্যাল ফাউন্ডেশন) কাম্য।
থিওরেমের স্টেটমেন্ট
প্রতিটি a এবং n যেগুলো রিলেটিভলি প্রাইম (Relatively Prime / Coprime) জন্য:
aφ(n) ≡ 1 (mod n)
যেখানে φ(n) = অয়লারের টোটিয়েন্ট ফাংশন (Euler's Totient Function), যা n-এর চেয়ে ছোট পজিটিভ ইন্টিজারের সংখ্যা যা n-এর সাথে রিলেটিভলি প্রাইম।
প্রুফ (Proof) — সংক্ষিপ্ত
R = {x₁, x₂, ..., xφ(n)} = n-এর চেয়ে ছোট এবং n-এর সাথে কো-প্রাইম সব ইন্টিজার। প্রতিটি xᵢ-কে a দিয়ে গুণ করে মডুলো n নিলে সেট S পাওয়া যায়। a ও xᵢ উভয়ই n-এর সাথে কো-প্রাইম → axᵢ ও n-এর সাথে কো-প্রাইম। S-এ ডুপ্লিকেট নেই। দুটি সেটের প্রোডাক্ট মডুলো n সমান → aφ(n) ≡ 1 (mod n)।
অয়লার টোটিয়েন্ট ফাংশন (Euler Totient Function — φ(n))
- গাণিতিক মাল্টিপ্লিকেটিভ ফাংশন যা n-এর চেয়ে ছোট বা সমান পজিটিভ ইন্টিজারের মধ্যে কতগুলো n-এর সাথে কো-প্রাইম সেটা গণনা করে।
- φ(n) বা phi function ও বলা হয়।
- ক্রিপ্টোগ্রাফিতে (বিশেষত RSA-এ) অত্যন্ত গুরুত্বপূর্ণ।
- সেট Zn* = {n-এর চেয়ে ছোট এবং n-এর সাথে রিলেটিভলি প্রাইম নম্বরগুলো}।
φ(n) গণনার নিয়মাবলী (Rules)
- φ(1) = 0
- φ(P) = P - 1 যদি P প্রাইম হয়
- φ(m × n) = φ(m) × φ(n) যদি m, n রিলেটিভলি প্রাইম হয়
- φ(Pe) = Pe - Pe-1 যদি P প্রাইম হয়
এই চারটি নিয়ম কম্বাইন করে n-কে প্রাইম ফ্যাক্টরাইজ করে φ(n) বের করা যায়:
n = P₁e1 × P₂e2 × ... × Pₖek
φ(n) = (P₁e1 - P₁e1-1) × (P₂e2 - P₂e2-1) × ... × (Pₖek - Pₖek-1)
দুর্বলতা: φ(n) বের করার কঠিনতা n-এর ফ্যাক্টরাইজেশনের কঠিনতার ওপর নির্ভর করে। বড় n-এর ফ্যাক্টরাইজেশন কঠিন → RSA নিরাপদ।
ব্যবহারিক উদাহরণ
- φ(7) = 6 (৭ প্রাইম)
- φ(10) = φ(2×5) = φ(2)×φ(5) = 1×4 = 4
- φ(12) = φ(2²×3) = (4-2)×(3-1) = 2×2 = 4
