پرش به محتویات

آزمون‌های اول بودن

این مقاله چندین الگوریتم را برای تشخیص اول بودن یا نبودن یک عدد شرح می‌دهد.

تقسیم آزمایشی

طبق تعریف، یک عدد اول هیچ مقسوم‌علیهی به جز ۱ و خودش ندارد. یک عدد مرکب حداقل یک مقسوم‌علیه اضافی دارد، بیایید آن را $d$ بنامیم. طبیعتاً $\frac{n}{d}$ نیز مقسوم‌علیه $n$ است. به راحتی می‌توان دید که یا $d \le \sqrt{n}$ یا $\frac{n}{d} \le \sqrt{n}$ است، بنابراین یکی از مقسوم‌علیه‌های $d$ و $\frac{n}{d}$ کوچکتر یا مساوی $\sqrt{n}$ است. ما می‌توانیم از این اطلاعات برای بررسی اول بودن استفاده کنیم.

ما با بررسی اینکه آیا هیچ‌کدام از اعداد بین ۲ و $\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$ و یک عدد صحیح $a$ که نسبت به $p$ اول است، رابطه زیر برقرار است:

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

به طور کلی این قضیه برای اعداد مرکب برقرار نیست.

از این موضوع می‌توان برای ایجاد یک آزمون اول بودن استفاده کرد. ما یک عدد صحیح $2 \le a \le p - 2$ انتخاب می‌کنیم و بررسی می‌کنیم که آیا این رابطه برقرار است یا نه. اگر برقرار نباشد، یعنی $a^{p-1} \not\equiv 1 \bmod p$، می‌دانیم که $p$ نمی‌تواند یک عدد اول باشد. در این حالت، پایه $a$ را یک شاهد فرما (Fermat witness) برای مرکب بودن $p$ می‌نامیم.

با این حال، این امکان نیز وجود دارد که این رابطه برای یک عدد مرکب برقرار باشد. بنابراین اگر رابطه برقرار باشد، ما اثباتی برای اول بودن نداریم. ما فقط می‌توانیم بگوییم که $p$ احتمالاً اول است. اگر معلوم شود که عدد در واقع مرکب است، ما پایه $a$ را یک دروغگوی فرما (Fermat liar) می‌نامیم.

با اجرای آزمون برای تمام پایه‌های ممکن $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}$ استفاده می‌کنیم.

اما یک خبر بد وجود دارد: برخی اعداد مرکب وجود دارند که در آن‌ها رابطه $a^{n-1} \equiv 1 \bmod n$ برای تمام $a$ های متباین با $n$ برقرار است، به عنوان مثال برای عدد $561 = 3 \cdot 11 \cdot 17$. چنین اعدادی اعداد کارمایکل (Carmichael numbers) نامیده می‌شوند. آزمون اول بودن فرما تنها در صورتی می‌تواند این اعداد را شناسایی کند که شانس بسیار زیادی داشته باشیم و پایه‌ای مانند $a$ را با $\gcd(a, n) \ne 1$ انتخاب کنیم.

آزمون فرما هنوز در عمل استفاده می‌شود، زیرا بسیار سریع است و اعداد کارمایکل بسیار نادر هستند. به عنوان مثال، تنها ۶۴۶ عدد از این نوع زیر $10^9$ وجود دارد.

آزمون اول بودن میلر-رابین

آزمون میلر-رابین ایده‌های آزمون فرما را گسترش می‌دهد.

برای یک عدد فرد $n$، عدد $n-1$ زوج است و می‌توانیم تمام توان‌های ۲ را از آن فاکتور بگیریم. می‌توانیم بنویسیم:

$$n - 1 = 2^s \cdot d,~\text{که در آن}~d~\text{فرد است}.$$

این به ما اجازه می‌دهد تا معادله قضیه کوچک فرما را تجزیه کنیم:

$$\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$ یک دروغگوی قوی (strong liar) نامیده می‌شود. اگر یک پایه $a$ معادلات را برآورده کند (یکی از آنها را)، $n$ فقط قویاً محتمل به اول بودن (strong probable prime) است. با این حال، اعدادی مانند اعداد کارمایکل وجود ندارند که تمام پایه‌های غیربدیهی برای آنها دروغگو باشند. در واقع، می‌توان نشان داد که حداکثر $\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;
}

قبل از آزمون میلر-رابین، می‌توانید علاوه بر آن بررسی کنید که آیا یکی از چند عدد اول کوچک، مقسوم‌علیه عدد مورد نظر است یا خیر. این کار می‌تواند سرعت آزمون را به شدت افزایش دهد، زیرا اکثر اعداد مرکب مقسوم‌علیه‌های اول بسیار کوچکی دارند. به عنوان مثال، ۸۸٪ از کل اعداد یک عامل اول کوچکتر از ۱۰۰ دارند.

نسخه قطعی

میلر نشان داد که با بررسی تنها تمام پایه‌های $\le O((\ln n)^2)$ می‌توان این الگوریتم را قطعی کرد. بعدها باخ یک کران مشخص ارائه داد، که طبق آن تنها لازم است تمام پایه‌های $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;
}

همچنین امکان انجام بررسی تنها با ۷ پایه وجود دارد: ۲، ۳۲۵، ۹۳۷۵، ۲۸۱۷۸، ۴۵۰۷۷۵، ۹۷۸۰۵۰۴ و ۱۷۹۵۲۶۵۰۲۲. با این حال، از آنجا که این اعداد (به جز ۲) اول نیستند، باید علاوه بر آن بررسی کنید که آیا عددی که در حال آزمایش آن هستید با هر یک از مقسوم‌علیه‌های اول آن پایه‌ها برابر است یا خیر: ۲، ۳، ۵، ۱۳، ۱۹، ۷۳، ۱۹۳، ۴۰۷۵۲۱، ۲۹۹۲۱۰۸۳۷.

مسائل تمرینی