মৌলিকতা পরীক্ষা#

এই আর্টিকেলে একটি সংখ্যা মৌলিক কিনা তা নির্ণয়ের জন্য একাধিক অ্যালগরিদম বর্ণনা করা হয়েছে।

ট্রায়াল ডিভিশন#

সংজ্ঞা অনুসারে একটি মৌলিক সংখ্যার $1$ এবং নিজে ছাড়া অন্য কোনো ডিভাইজর নেই। একটি যৌগিক সংখ্যার অন্তত একটি অতিরিক্ত ডিভাইজর আছে, একে $d$ বলি। স্বাভাবিকভাবেই $\frac{n}{d}$-ও $n$ এর একটি ডিভাইজর। সহজেই দেখা যায় যে, হয় $d \le \sqrt{n}$ অথবা $\frac{n}{d} \le \sqrt{n}$, সুতরাং $d$ এবং $\frac{n}{d}$ ডিভাইজরদ্বয়ের একটি $\le \sqrt{n}$। আমরা মৌলিকতা পরীক্ষায় এই তথ্য ব্যবহার করতে পারি।

আমরা $2$ থেকে $\sqrt{n}$ পর্যন্ত কোনো সংখ্যা $n$ এর ডিভাইজর কিনা পরীক্ষা করে একটি অ-তুচ্ছ ডিভাইজর খুঁজে বের করার চেষ্টা করি। যদি এটা ডিভাইজর হয়, তাহলে $n$ অবশ্যই মৌলিক নয়, অন্যথায় এটা মৌলিক।

bool isPrime(int x) {
    for (int d = 2; d * d <= x; d++) {
        if (x % d == 0)
            return false;
    }
    return x >= 2;
}

এটা মৌলিকতা পরীক্ষার সবচেয়ে সরল রূপ। লুপে শুধুমাত্র বিজোড় সংখ্যাগুলো পরীক্ষা করে এই ফাংশনটিকে যথেষ্ট অপটিমাইজ করা যায়, কারণ একমাত্র জোড় মৌলিক সংখ্যা হলো ২। এরকম একাধিক অপটিমাইজেশন পূর্ণ সংখ্যার উৎপাদক বিভাজন সংক্রান্ত আর্টিকেলে বর্ণনা করা হয়েছে।

ফার্মার মৌলিকতা পরীক্ষা#

এটা একটি প্রোবাবিলিস্টিক পরীক্ষা।

ফার্মার ক্ষুদ্র থিওরেম (দেখো অয়লারের টোশেন্ট ফাংশন) বলে যে, একটি মৌলিক সংখ্যা $p$ এবং $p$ এর সাথে সহমৌলিক একটি পূর্ণ সংখ্যা $a$ এর জন্য নিচের ইকুয়েশনটি সত্য:

$$a^{p-1} \equiv 1 \bmod p$$

সাধারণত এই থিওরেমটি যৌগিক সংখ্যাদের জন্য সত্য হয় না।

এটা মৌলিকতা পরীক্ষা তৈরিতে ব্যবহার করা যায়। আমরা একটি পূর্ণ সংখ্যা $2 \le a \le p - 2$ বেছে নিই, এবং ইকুয়েশনটি সত্য হয় কিনা পরীক্ষা করি। যদি সত্য না হয়, যেমন $a^{p-1} \not\equiv 1 \bmod p$, তাহলে আমরা জানি $p$ মৌলিক সংখ্যা হতে পারে না। এই ক্ষেত্রে আমরা ভিত্তি $a$ কে $p$ এর যৌগিকতার ফার্মা উইটনেস বলি।

তবে এটাও সম্ভব যে যৌগিক সংখ্যার জন্যও ইকুয়েশনটি সত্য হয়। তাই ইকুয়েশনটি সত্য হলে, আমাদের কাছে মৌলিকতার প্রুফ নেই। আমরা শুধু বলতে পারি যে $p$ সম্ভবত মৌলিক। যদি দেখা যায় যে সংখ্যাটি আসলে যৌগিক, তাহলে আমরা ভিত্তি $a$ কে ফার্মা লায়ার বলি।

সব সম্ভাব্য ভিত্তি $a$ এর জন্য পরীক্ষা চালিয়ে, আমরা আসলে একটি সংখ্যা মৌলিক কিনা তা প্রুফ করতে পারি। তবে বাস্তবে এটা করা হয় না, কারণ এটা শুধু ট্রায়াল ডিভিশন করার চেয়ে অনেক বেশি প্রচেষ্টা। এর পরিবর্তে $a$ এর র‍্যান্ডম মান বেছে পরীক্ষাটি একাধিকবার পুনরাবৃত্তি করা হয়। যদি আমরা যৌগিকতার কোনো উইটনেস না পাই, তাহলে এটা অত্যন্ত সম্ভাব্য যে সংখ্যাটি আসলে মৌলিক।

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}$ ঘাত দক্ষতার সাথে হিসাব করতে বাইনারি এক্সপোনেনশিয়েশন ব্যবহার করি।

তবে একটি খারাপ খবর আছে: কিছু যৌগিক সংখ্যা আছে যেখানে $n$ এর সাথে সহমৌলিক সব $a$ এর জন্য $a^{n-1} \equiv 1 \bmod n$ সত্য হয়, যেমন $561 = 3 \cdot 11 \cdot 17$ সংখ্যাটি। এই ধরনের সংখ্যাকে কারমাইকেল সংখ্যা বলে। ফার্মার মৌলিকতা পরীক্ষা এই সংখ্যাগুলো শুধুমাত্র তখনই শনাক্ত করতে পারে, যদি আমরা অত্যন্ত ভাগ্যবান হয়ে এমন ভিত্তি $a$ বেছে নিই যেখানে $\gcd(a, n) \ne 1$।

ফার্মা পরীক্ষা এখনো বাস্তবে ব্যবহৃত হয়, কারণ এটা অত্যন্ত দ্রুত এবং কারমাইকেল সংখ্যা অত্যন্ত বিরল। যেমন $10^9$ এর নিচে মাত্র ৬৪৬টি এরকম সংখ্যা আছে।

মিলার-রাবিন মৌলিকতা পরীক্ষা#

মিলার-রাবিন পরীক্ষা ফার্মা পরীক্ষার ধারণাকে সম্প্রসারিত করে।

একটি বিজোড় সংখ্যা $n$ এর জন্য, $n-1$ জোড় এবং আমরা ২ এর সব ঘাত বের করে আনতে পারি। আমরা লিখতে পারি:

$$n - 1 = 2^s \cdot d,~\text{where}~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 \le a \le n-2$ এর জন্য আমরা পরীক্ষা করি হয়

$$a^d \equiv 1 \bmod n$$

সত্য হয় অথবা

$$a^{2^r d} \equiv -1 \bmod n$$

কোনো $0 \le r \le s - 1$ এর জন্য সত্য হয়।

যদি আমরা এমন ভিত্তি $a$ পাই যেটা উপরের কোনো সমতাই পূরণ করে না, তাহলে আমরা $n$ এর যৌগিকতার একটি উইটনেস পেয়েছি। এই ক্ষেত্রে আমরা প্রুফ করেছি যে $n$ মৌলিক সংখ্যা নয়।

ফার্মা পরীক্ষার মতো, এখানেও সম্ভব যে যৌগিক সংখ্যার জন্য ইকুয়েশনগুলোর সেট পূরণ হয়। সেক্ষেত্রে ভিত্তি $a$ কে স্ট্রং লায়ার বলা হয়। যদি একটি ভিত্তি $a$ ইকুয়েশনগুলো পূরণ করে (যেকোনো একটি), $n$ শুধু স্ট্রং প্রোবেবল প্রাইম। তবে, কারমাইকেল সংখ্যার মতো কোনো সংখ্যা নেই যেখানে সব অ-তুচ্ছ ভিত্তি মিথ্যা বলে। আসলে দেখানো সম্ভব যে সর্বোচ্চ $\frac{1}{4}$ ভিত্তি স্ট্রং লায়ার হতে পারে। যদি $n$ যৌগিক হয়, তাহলে একটি র‍্যান্ডম ভিত্তি যে আমাদের বলবে এটা যৌগিক তার সম্ভাবনা $\ge 75\%$। বিভিন্ন র‍্যান্ডম ভিত্তি বেছে একাধিক ইটারেশন করলে, আমরা অত্যন্ত উচ্চ সম্ভাবনায় বলতে পারি সংখ্যাটি সত্যিই মৌলিক না যৌগিক।

এখানে ৬৪ বিট ইন্টিজারের জন্য একটি ইমপ্লিমেন্টেশন দেওয়া হলো।

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) { // n সম্ভবত মৌলিক হলে true রিটার্ন করে, অন্যথায় 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;
}

মিলার-রাবিন পরীক্ষার আগে অতিরিক্তভাবে পরীক্ষা করা যায় যে প্রথম কয়েকটি মৌলিক সংখ্যার কোনোটি ডিভাইজর কিনা। এটা পরীক্ষাকে অনেক দ্রুত করতে পারে, কারণ বেশিরভাগ যৌগিক সংখ্যার অত্যন্ত ছোট মৌলিক ফ্যাক্টর আছে। যেমন $100$ এর চেয়ে ছোট মৌলিক ফ্যাক্টর আছে সব সংখ্যার $88\%$ এর।

ডিটারমিনিস্টিক সংস্করণ#

মিলার দেখিয়েছেন যে শুধুমাত্র $\le O((\ln n)^2)$ সব ভিত্তি পরীক্ষা করে অ্যালগরিদমটিকে ডিটারমিনিস্টিক করা সম্ভব। Bach পরে একটি সুনির্দিষ্ট সীমা দিয়েছেন, শুধুমাত্র $a \le 2 \ln(n)^2$ সব ভিত্তি পরীক্ষা করাই যথেষ্ট।

এটা এখনো বেশ বড় সংখ্যক ভিত্তি। তাই মানুষ নিম্ন সীমা খুঁজে বের করতে প্রচুর কম্পিউটেশন শক্তি বিনিয়োগ করেছে। দেখা যায় যে, ৩২ বিট ইন্টিজার পরীক্ষার জন্য শুধুমাত্র প্রথম ৪টি মৌলিক ভিত্তি পরীক্ষা করা প্রয়োজন: ২, ৩, ৫ এবং ৭। এই পরীক্ষায় ব্যর্থ হওয়া ক্ষুদ্রতম যৌগিক সংখ্যা হলো $3,215,031,751 = 151 \cdot 751 \cdot 28351$। এবং ৬৪ বিট ইন্টিজার পরীক্ষার জন্য প্রথম ১২টি মৌলিক ভিত্তি পরীক্ষা করাই যথেষ্ট: ২, ৩, ৫, ৭, ১১, ১৩, ১৭, ১৯, ২৩, ২৯, ৩১, এবং ৩৭।

এটা নিচের ডিটারমিনিস্টিক ইমপ্লিমেন্টেশনে পরিণত হয়:

bool MillerRabin(u64 n) { // n মৌলিক হলে true রিটার্ন করে, অন্যথায় 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;
}

শুধুমাত্র ৭টি ভিত্তি দিয়েও পরীক্ষা করা সম্ভব: ২, ৩২৫, ৯৩৭৫, ২৮১৭৮, ৪৫০৭৭৫, ৯৭৮০৫০৪ এবং ১৭৯৫২৬৫০২২। তবে, যেহেতু এই সংখ্যাগুলো (২ ব্যতীত) মৌলিক নয়, তাই তোমাকে অতিরিক্তভাবে পরীক্ষা করতে হবে যে তুমি যে সংখ্যাটি পরীক্ষা করছেন সেটা ওই ভিত্তিগুলোর কোনো মৌলিক ডিভাইজরের সমান কিনা: ২, ৩, ৫, ১৩, ১৯, ৭৩, ১৯৩, ৪০৭৫২১, ২৯৯২১০৮৩৭।

অনুশীলন সমস্যা#