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

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

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

সংজ্ঞা অনুসারে একটি মৌলিক সংখ্যার $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;
}

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

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