পরিচয়পর্ব
মৌলিক সংখ্যা কী সেটা আমরা কমবেশি সবাই জানি। মৌলিক সংখ্যা হচ্ছে এমন সব ধনাত্মক পূর্ণসংখ্যা যাদের ঠিক দুটি উৎপাদক আছে। এই আর্টিকেলটিতে একটি সংখ্যা মৌলিক কিনা তা যাচাই করার বিভিন্ন পদ্ধতি নিয়ে আলোচনা করব।
ট্রায়াল ডিভিশন পদ্ধতি
মৌলিক সংখ্যার সংজ্ঞানুসারে এর 1 এবং সংখ্যাটি নিজে বাদে আর কোন উৎপাদক নেই। একটি যৌগিক সংখ্যার কমপক্ষে একটি অতিরিক্ত উৎপাদক থাকবেই। ধরি এটি \(d\)। যদি \(n\) এর উৎপাদক \(d\) হয় তাহলে \(\frac{n}{d}\) ও এর উৎপাদক হবে। এ উৎপাদকদ্বয় এর উভয়ই সমান হবে যদি \(n\) পূর্ণবর্গ হয়। তখন উৎপাদক দুটি হবে \(\sqrt n\)। কিন্তু যদি এরা সমান না হয় তাহলে এদের মধ্যে একটি \(\sqrt n\) এর চেয়ে ছোট হবে এবং অন্যটি \(\sqrt n\) এর চেয়ে বড় হবে। তাই সকল মৌলিক সংখ্যার একটি হলেও উৎপাদক \(1 < d \leq \sqrt n\) হবে। তাই আমরা \(2\) থেকে শুরু করে \(\sqrt n\) পর্যন্ত সবগুলো সংখ্যা দিয়ে \(n\) এর বিভাজ্যতা পরীক্ষা করব। যদি এর মধ্যে কোন একটি সংখ্যা দিয়ে \(n\) নিঃশেষে বিভাজ্য হয় তাহলে \(n\) যৌগিক, এবং কোন সংখ্যা দিয়েই ভাগ না গেলে \(n\) মৌলিক।
bool isPrime(int x) {
for (int d = 2; d * d <= x; d++) {
if (x % d == 0)
return false;
}
return true;
}
উপরের ইম্প্লিমেন্টেশনটি মৌলিক সংখ্যা যাচাই করার সবচেয়ে সরল উপায়। এটিকে কিছু ছোটখাটো পরিবর্তন করার মাধ্যমে কিছুটা অপটিমাইজ করা যায়। এর একটি উদাহরণ হতে পারে 2 কে আলাদা ভাবে চেক করে শুধু বেজোড় সংখ্যা গুলো দিয়ে বিভাজ্যতা পরীক্ষা করা।
ফার্মার প্রাইমালিটি টেস্ট
এটি একটি প্রবাবিলিস্টিক টেস্ট।
ফার্মার লিটল উপপাদ্য থেকে আমরা পাই যে, একটি মৌলিক সংখ্যা \(p\) এবং এর একটি সহমৌলিক সংখ্যা \(a\) এর জন্য নিম্নোক্ত সমীকরণটি সর্বদা সত্য হবে।
\(a^{p-1} \equiv 1\) \((mod\) \(p)\) \(--------- (1)\)
এই সমীকরণটি সাধারণত যৌগিক সংখ্যার জন্য মিথ্যা হয়।
এই সমীকরণটিকে একটি প্রাইমালিটি টেস্ট হিসেবে ব্যবহার করা যায়। ধরি, আমাদের যাচাই করতে হবে \(p\) মৌলিক নাকি যৌগিক। আমরা যে কোন একটি পূর্ণসংখ্যা \(2 \leq a \leq p-2\) নিব এবং যাচাই করব যে \((1)\) সমীকরণটি এই \(a\) এবং \(p\) জন্য সত্য হয় কিনা। যদি এটা সত্য না হয়, অর্থাৎ \(a^{p-1} \not\equiv 1\) \((mod\) \(p)\), আমরা জানি যে \(p\) মৌলিক নয়। এক্ষেত্রে বেস \(a\) কে \(p\) এর যোগিক সংখ্যা হওয়ার ফার্মার উইটনেস বলা হয়।
কিন্তু এখানে একটি ছোট সমস্যা আছে। এই সমীকরণটি একটি মৌলিক সংখ্যার জন্য সর্বদা সত্য হলেও, কোনো একটি যৌগিক সংখ্যার জন্য সর্বদা মিথ্যা হবেই এমন কোনো কথা নেই। তাই যদিও সমীকরণটি মিথ্যা হলেই আমরা বলতে পারি যে \(p\) অবশ্যই যৌগিক কিন্তু যদি এই সমীকরণটি সত্য হয় তাহলে আমরা নিশ্চিত ভাবে বলতে পারি না যে \(p\) মৌলিক। আমরা বলতে পারি যে এটি সম্ভবত মৌলিক। যদি বেস \(a\) এর জন্য \(1\) সমীকরণটি সত্য হওয়ার পরেও এটি যৌগিক সংখ্যা হয় তাহলে আমরা বেসটিকে ফার্মার লায়ার বলি।
সকল বেস \(2 \leq a \leq p-2\) এর জন্য চেক করে আমরা এটা প্রমাণ করতে পারি যে সংখ্যাটি আসলেই মৌলিক। কিন্তু ব্যবহারিক ক্ষেত্রে এটি করা হয় না কারণ এতে অনেক সময় ব্যয় হয়। বরং দৈব চয়ন এর মাধ্যমে কয়েকটি বেস এর জন্য যাচাই করেই আমরা মোটামুটি নিশ্চিত হতে পারি। যদি কোনো ফার্মার উইটনেস না পাওয়া যায় তাহলে বলা যায় যে এটি মৌলিক হওয়া সম্ভাবনাই বেশি।
bool probablyPrimeFermat(int n, int iter=5) {
if (n < 4)
return n == 2 || n == 3;
for (int i = 0; i < iter; i++) {
int a = 2 + rand() % (n - 3);
if (binpower(a, n - 1, n) != 1)
return false;
}
return true;
}
আমরা বাইনারি এক্সপোনেনশিয়াল ব্যবহার করে খুব এফিশিয়েন্টলি \(a^{p-1}\) গণনা করতে পারি।
তবে একটি খারাপ খবর আছে: এমন কিছু যৌগিক সংখ্যা আছে যাদের সব সহমৌলিক বেস \(a\) এর জন্যই \(a^{n-1} \equiv 1\) \((mod\) \(n)\) সত্য হয়। এসব সংখ্যা কে কারমাইকেল নাম্বার বলা হয়। ফার্মার প্রাইমালিটি টেস্টে এ নাম্বার গুলোকে তখনই যাচাই করতে পারে যদি আমাদের ভাগ্য খুব ভালো হয় এবং আমরা এমন একটি বেস খুঁজে পাই যেটি \(n\) এর সাথে সহমৌলিক নয়।
তাও ফার্মার উপপাদ্য টি ব্যবহারিক ক্ষেত্রে প্রয়োগ করা হয় কারণ এটি খুবই এফিশিয়েন্ট এবং কারমাইকেল নাম্বার খুবই দুষ্প্রাপ্য। \(10^9\) এর নিচে মাত্র \(646\) টি কারমাইকেল নাম্বার রয়েছে।
মিলার ব়্যাবিন প্রাইমালিটি টেস্ট
মিলার ব়্যাবিন প্রাইমালিটি টেস্ট ফার্মার প্রাইমালিটি টেস্ট এর উপর ভিত্তি করেই দাঁড়ানো।
কোনো বেজোড় সংখ্যা \(n\) এর জন্য \(n-1\) সর্বদা জোড় হবে। আমরা \(n-1\) এর সবগুলো \(2\) এর পাওয়ার কে আলাদা করে নিন্মোক্ত ভাবে লিখতে পারি।
\(n - 1 = 2^s \cdot d, ~d~~\text{odd}.\)
এভাবে লিখলে আমরা ফার্মার লিটল উপপাদ্যকে উৎপাদকে বিভাজিত করতে পারি।
\[\begin{array}{rl} a^{n-1} \equiv 1 \bmod n &\Longleftrightarrow a^{2^s d} - 1 \equiv 0 \bmod n \\ &\Longleftrightarrow (a^{2^{s-1} d} + 1) (a^{2^{s-1} d} - 1) \equiv 0 \bmod n \\ &\Longleftrightarrow (a^{2^{s-1} d} + 1) (a^{2^{s-2} d} + 1) (a^{2^{s-2} d} - 1) \equiv 0 \bmod n \\ &\quad\vdots \\ &\Longleftrightarrow (a^{2^{s-1} d} + 1) (a^{2^{s-2} d} + 1) \cdots (a^{d} + 1) (a^{d} - 1) \equiv 0 \bmod n \\ \end{array}\]যদি \(n\) মৌলিক হয় তাহলে \(n\) কে এ উৎপাদকগুলোর যেকোনো একটিকে নিঃশেষে ভাগ করতেই হবে। এবং মিলার ব়্যাবিন প্রাইমালিটি টেস্ট এ আমরা ঠিক এটাই চেক করি। এটা ফার্মার টেস্ট এর চেয়েও শক্তিশালী টেস্ট। বেস \(2 \leq a \leq n-2\) এর জন্য আমরা যাচাই করি যে,
হয় $a^d \equiv 1 \bmod n$ নাহয় $a^{2^r d} \equiv -1 \bmod n$ সত্য কিনা যেখানে $0 \le r \le s - 1$ । অর্থাৎ, সমীকরনদ্বয়ের দুটোর মধ্যে যেকোনো একটি সত্য হয় কিনা।
যদি আমরা এমন কোন বেস পাই যেটা উপরের কোন সমীকরণকেই সিদ্ধ করে না তাহলে আমরা \(n\) এর যৌগিক হওয়ার উইথনেস পেয়ে গেলাম। এক্ষেত্রে এটা প্রমাণিত হয় যে \(n\) মৌলিক নয়।
ফার্মার টেস্টের মতোই, এক্ষেত্রেও এমন হতে পারে যে সবগুলো সমীকরণ কোন একটা যৌগিক সংখ্যার জন্য সত্য হয়ে গেল। এক্ষেত্রে বেস \(a\) কে স্ট্রং লায়ার বলা হয়। যদি একটি বেস যেকোনো একটি সমীকরণ কে সিদ্ধ করে তাহলে আমরা বলতে পারি যে \(n\) প্রাইম হওয়ার তীব্র সম্ভাবনা রয়েছে। তবে এক্ষেত্রে কারমাইকেল নাম্বারের মত এমন কোন নাম্বার নেই যার ক্ষেত্রে বেশিরভাগ সংখ্যাই স্ট্রং লায়ার। এটা দেখানো সম্ভব যে সর্বোচ্চ \(\frac{1}{4}\) বেস স্ট্রং লায়ার হতে পারে। যদি \(n\) যৌগিক হয় তাহলে আমাদের সম্ভাবনা আছে যে দৈবভাবে একটি বেস নিলে সেটি আমাদের \(n\) কে যৌগিক বলবে। দৈবভাবে বেস নিয়ে কয়েকবার আমরা টেস্ট টি চালিয়ে দেখতে পারি। যদি সর্বদাই আমরা দেখি যে যৌগিক আসছে না তাহলে এটা বলা যায় যে সংখ্যাটি মৌলিক হওয়ার সম্ভাবনা খুবই তীব্র।
\(64\) বিট সংখ্যার জন্য ইম্প্লিমেন্টেশন দেয়া হলো।
using u64 = uint64_t;
using u128 = __uint128_t;
u64 binpower(u64 base, u64 e, u64 mod) {
u64 result = 1;
base %= mod;
while (e) {
if (e & 1)
result = (u128)result * base % mod;
base = (u128)base * base % mod;
e >>= 1;
}
return result;
}
bool check_composite(u64 n, u64 a, u64 d, int s) {
u64 x = binpower(a, d, n);
if (x == 1 || x == n - 1)
return false;
for (int r = 1; r < s; r++) {
x = (u128)x * x % n;
if (x == n - 1)
return false;
}
return true;
};
bool MillerRabin(u64 n, int iter=5) { // returns true if n is probably prime, else returns false.
if (n < 4)
return n == 2 || n == 3;
int s = 0;
u64 d = n - 1;
while ((d & 1) == 0) {
d >>= 1;
s++;
}
for (int i = 0; i < iter; i++) {
int a = 2 + rand() % (n - 3);
if (check_composite(n, a, d, s))
return false;
}
return true;
}
মিলার ব়্যাবিন টেস্ট এর আগে আমরা প্রথম কয়েকটি মৌলিক সংখ্যা দিয়ে চেক করে নিতে পারি যে এগুলোর মধ্যে কোনটি \(n\) এর উৎপাদক হয় কিনা। এটা পুরো প্রক্রিয়াটির গতি অনেক বৃদ্ধি করতে পারে। কারণ বেশিরভাগ যৌগিক সংখ্যারই কমপক্ষে একটি মৌলিক উৎপাদক থাকে যা খুবই ছোট। \(88\%\) সংখ্যার ই সবচেয়ে ক্ষুদ্র মৌলিক উৎপাদক \(100\) এর চেয়ে ছোট।
ডিটার্মিনিস্টিক অ্যালগোরিদম
কেমনে সম্ভব?!?
অবিশ্বাস্য হলেও এটা সত্য (আসলেই কি সত্য?) যে মিলার ব়্যাবিন প্রাইমালিটি টেস্টকে ডিটারমিনিস্টিক বানানো সম্ভব (বলে মনে হয়, কিন্তু আসলে?)। আসলে মিলার ব়্যাবিন প্রাইমালিটি টেস্টকে ডিটারমিনিস্টিক বানাতে হলে GRH ব্যবহার করা লাগে। তাই এটা নিশ্চিৎভাবে বলা যাবে না যে মিলার ব়্যাবিন প্রাইমালিটি টেস্টকে ডিটারমিনিস্টিক বানানো যায় নিন্মোক্ত বর্ণিত পদ্ধতিতে। তবে আমরা যদি GRH এর উপর বিশ্বাস (xD) রাখতে পারি তাহলে এটাকে ডিটারমিনিস্টিক বলে চালিয়ে দিতে পারি। আসলে নিন্মোক্ত বর্ণিত পদ্ধতিটি প্রমাণ করতে GRH এর ফুল পাওয়ার লাগে না। Quadratic Dirichlet Characters এর জন্য GRH কে সত্য বলে ধরে নিলেই প্রমাণ হয়ে যায়।
মিলার এটা দেখায় যে যদি GRH সত্য হয় তাহলে সকল বেস a $\le O((\ln n)^2)$ এর জন্য চেক করলেই টেস্ট টি ডিটারমিনিস্টিক হয়ে যায়। বাচ্ পরে কনস্ট্যান্টটি \(2\) এ নামিয়ে আনে। বা্চ দেখায় যে $a \le 2 \ln(n)^2$ এর জন্য চেক করলেই টেস্ট টি ডিটারমিনিস্টিক হয়।
কিন্তু এক্ষেত্রেও বেস এর পরিমাণ ভালো পরিমাণেই বেশি. তাই বিভিন্ন গবেষকরা লোয়ার বাউন্ড খুঁজে বের করার জন্য বিভিন্নভাবে চেষ্টা চালিয়ে গেছে. এটা বের করা হয়েছে যে, \(32\) বিট পূর্ণসংখ্যার জন্য প্রথম \(4\) টা প্রাইমকে \((2, 3, 5\) এবং \(7)\) বেস হিসাবে নিয়ে চেক করলেই হয়। প্রথম যেই যোগিক সংখ্যাকে খুঁজে বের করতে এই \(4\) টি সংখ্যার টেস্টটি ব্যর্থ হয় সেটি হচ্ছ $3,215,031,751 = 151 \cdot 751 \cdot 28351$. আর \(64\) বিট পূর্ণসংখ্যাকে যাচাই করতে প্রথম \(12\) টি মৌলিক সংখ্যাকে \((2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,\) এবং \(37)\) বেস হিসেবে ব্যবহার করলেই যথেষ্ট হয়।
নিচে \(64\) বিট পূর্ণসংখ্যার জন্য ডিটারমিনিস্টিক টেস্টটি দেওয়া হলো:
bool MillerRabin(u64 n) { // returns true if n is prime, else returns false.
if (n < 2)
return false;
int r = 0;
u64 d = n - 1;
while ((d & 1) == 0) {
d >>= 1;
r++;
}
for (int a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
if (n == a)
return true;
if (check_composite(n, a, d, r))
return false;
}
return true;
}
একচুয়ালি শুধু 7 টি বেস ব্যবহার করেই \((2, 325, 9375, 28178, 450775, 9780504\) এবং \(1795265022)\) টেস্টটি করা যায় । কিন্তু যেহেতু এই সংখ্যাগুলো যৌগিক (2 ছাড়া), তাই তোমাকে আলাদাভাবে এটা চেক করে নিতে হবে যে উক্ত ৭ টি সংখ্যাগুলোর মধ্যে কোনোটির উৎপাদক আমাদের যাচাই করার সংখ্যাটি হয় কিনা।