এ পর্যন্ত
নাম্বার থিওরি সিরিজে
প্রাইম নাম্বার নিয়ে বেশ কিছু টিউটোরিয়াল দেখেছি এবং অ্যালগরিদম শিখেছি। কিন্তু ইনপুট লিমিট যদি
১০^১৬ এর বেশি হয়ে যায় তাহলে,
আগে শিখে আসা কোন অ্যালগরিদমই কাজে আসবে না। তাই আজকে শিখব "
ফারমার লিটল থিওরেম"।
ইনপুট অনেক বড় হলেও, সেটি প্রাইম কিনা তা ফারমার লিটল থিওরেম দিয়ে নির্ণয় করা সম্ভব। এই থিওরেমে বলা হয়েছে, যদি a এবং p কো-প্রাইম বা সহ-মৌলিক হয় এবং a যদি p এর থেকে ছোট হয় তাহলে, a^p কে p দ্বারা ভাগ করলে ভাগশেষ a হবে,
ap≡amodpআবার, a^p-1 কে p দিয়ে ভাগ করলে ভাগশেষ সবসময় 1 হবে। এই কথাটুকু আমাদের জন্য খুবই গুরুত্বপূর্ণ। কেন গুরুত্বপূর্ণ? সেটি সরাসরি না বলে প্রাইম নাম্বারের বেসিক কিছু বিষয় নিয়ে আবার ঘাটাঘাটি করতে পারি। তবে যদি
অয়লারের ফাই ফাংশন জানেন তবে হয়ত এতক্ষণে বিষয় টি ধরে ফেলতে পেরেছেন।
প্রাইম নাম্বারের ডেফিনিশন হচ্ছে, n যদি প্রাইম হয় তাহলে, n কে শুধুমাত্র 1 এবং n দিয়েই ভাগ করা যাবে। তারমানে, m যদি n এর মাল্টিপল না হয় তাহলে n এবং m এর gcd সবসময় 1 হবে। মানে n এবং m সবসময় পরস্পর কো-প্রাইম। আর আমরা জানি, n এর মাল্টিপল কখনো n এর থেকে ছোট নয় :D মানে 2 থেকে n-1 পর্যন্ত সংখ্যা গুলো নিয়ে কাজ করতে পারি। তাহলে, সাধারণত বলতে পারি p প্রাইম হলে a^p-1 কে p দিয়ে ভাগ করলে ভাগশেষ সবসময় ১ হবে। যেখানে a হচ্ছে ১ এর থেকে বড় এবং p এর থেকে ছোট যেকোন একটি সংখ্যা।
তবে, p প্রাইম নয় কিন্তু তাও p এর থেকে ছোট এমন কিছু সংখ্যা পাওয়া যাবে, যাদের সাথে p কো-প্রাইম এবং a^p-1 mod p = 1 হতে পারে। এমন কিছু ক্ষেত্রে ভুল উত্তর আসতে পারে। তাই আমরা ১ এর থেকে বড় এবং n এর থেকে ছোট এমন কমপক্ষে ৫টি random সংখ্যাকে a হিসেবে নিয়ে a^p-1 mod p বের করে দেখব তাহলে, উত্তর ভুল আসার সম্ভাবনা অনেক কমে যাবে। আর এই কারনেই এই থিওরেম কে বলে প্রবাবিলিস্টিক থিওরেম। p এর লিমিট হয়ত ১০^১৮ হতে পারে। তাই পাওয়ার ক্যালকুলেট করার জন্য
Binary Exponentiation পদ্ধতি ব্যবহার করব।
|
// calculate a^n-1 % n
int power(int b, int p, int mod) {
int id = 1;
while (p > 0) {
if (p%2==1) {
id = ((id % mod) * (b % mod)) % mod;
p--;
} else {
b = ((b % mod) * (b % mod)) % mod;
p /= 2;
}
}
return id;
}
bool fermat_test(int n) {
if (n < 4)return n==2 || n==3;
for (int it = 0;it < 5;it++) {
int a = (rand() % (n-3)) + 2;
if (power(a, n-1, n) != 1) return false;
}
return true;
}
|
n যদি 4 এর থেকে ছোট হয় তাহলে fermat_test() ফাংশনে শুরুতেই n কে আলাদা করে হ্যান্ডেল করে নিয়েছি। এরপর 2 থেকে n-2 পর্যন্ত 5 টি random সংখ্যাকে a হিসেবে ধরে নিয়ে দেখেছি a^p-1 mod p অসমান 1 হয় কিনা। যদি একটি সংখ্যার জন্যেও 1 না হয় তাহলে শতভাগ নিশ্চিত p প্রাইম নয় অন্যথায় ধরে নিব এটি প্রাইম। আর এর কমপ্লেক্সিটি হচ্ছে O(5 x log(p))।
এখন একটি বিষয় হচ্ছে, p এর লিমিট ১০^১৮ তাই mod করে করে হিসেব করা সত্বেও ইন্টিজার ওভারফ্লো হবেই। তবে গুণের কাজটি যদি আলাদা ফাংশনে
Binary Exponentiation করে করতে পারি তাহলে ওভারফ্লো হবে। এতে যদিও কমপ্লেক্সিটি প্রায় O(log(p)^2) হয়ে যাবে, তবে সেটি খুব বেশি নয়।
|
// calculate b times a in log(b) complexity
int mulmod(int a, int b, int mod) {
int id = 0;
while (b > 0) {
if (b%2==1) {
id = (id + a) % mod;
b--;
} else {
a = (a + a) % mod;
b /= 2;
}
}
return id;
}
int power(int b, int p, int mod) {
int id = 1;
while (p > 0) {
if (p%2==1) {
id = mulmod(id, b, mod);
p--;
} else {
b = mulmod(b, b, mod);
p /= 2;
}
}
return id;
}
bool fermat_test(int n) {
if (n < 4)return n==2 || n==3;
for (int it = 0;it < 5;it++) {
int a = (rand() % (n-3)) + 2;
if (power(a, n-1, n) != 1) {
return false;
}
}
return true;
}
|
mulmod() ফাংশন আর power() ফাংশন কিন্তু একই। একটি তে গুণ করে করে পাওয়ার বের করতে হয়েছে এবং অপরটিতে যোগ করে করে গুণফল বের করা হয়েছে। এরপরেও বুঝার সুবিধার্থে একটি উদাহরণ দেখতে পারি, যদি 8 এবং 10 কে গুণ করি তাহলে, আসলে কি করতে হচ্ছে? 8 কে 10 বার যোগ করতে হচ্ছে। এখন ত তাহলে 10 টি 8 কে যোগ না করে 5 টি 8 কে যোগ করে যোগফল কে যোগফল দিয়ে যোগ করে দিলেই অর্ধেক কাজ কমে যাচ্ছে। এভাবেই চলতে থাকবে।
id = 0; // identity veriable
a = 8, b = 10;
এখন,
// b is even now
a = a + a = 8 + 8 = 16
b = b / 2 = 10 / 2 = 5
// b is odd now
id = id + a = 0 + 16
b = b - 1 = 5 - 1 = 4
// b is even now
a = a + a = 16 + 16 = 32
b = b / 2 = 4 / 2 = 2
// b is even now
a = a + a = 32 + 32 = 64
b = b / 2 = 2 / 2 = 1
// b is odd now
id = id + a = 16 + 64 = 80
b = b - 1 = 1 - 1 = 0
এই অ্যালগরিদম টির সীমাবদ্ধতা উপরে একটু বললেও এর আসলে ভালোরকম সীমাবদ্ধতা আছে। এমন কিছু কম্পোজিট সংখ্যা আছে যাদের প্রাইম বলে রায় দেয় এই অ্যালগরিদম 5 বার বা, তার বেশি বার পরীক্ষা করার পরেও। এই সীমাবদ্ধতা ছাড়া এটি অনেক ফাস্ট অ্যালগরিদম। তাছাড়া Miller Rabin Primality Test এই থিওরেমের উপর ভিত্তি করেই এসেছে। যেটি কিনা অনেক নির্ভুল উত্তর দিতে পারে। Miller Rabin Primality Test শিখব পরের টিউটোরিয়ালে।
এই বিষয়ে আরো টিউটোরিয়াল।
টিউটোরিয়াল ১টিউটোরিয়াল ২টিউটোরিয়াল ৩
No comments