Агуулгыг алгасах

Анхны тооны шалгуур

Энэ өгүүлэлд тоо анхны эсэхийг тодорхойлох хэд хэдэн алгоритмыг тайлбарлана.

Туршилтын хуваалт

Тодорхойлолтоор анхны тоо нь $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;
}

This is the simplest form of a prime check. You can optimize this function quite a bit, for instance by only checking all odd numbers in the loop, since the only even prime number is 2. Multiple such optimizations are described in the article about integer factorization.

Фермагийн анхны тооны шалгуур

Энэ бол магадлалын шалгуур юм.

Фермагийн бага теорем (Эйлерийн функц-ийг мөн үзнэ үү) нь анхны тоо $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$ тоо. Ийм тоонуудыг Кармайклын тоо гэж нэрлэдэг. Фермагийн анхны тооны шалгуур эдгээр тоог зөвхөн бид маш их азтай байж $\gcd(a, n) \ne 1$ байх $a$ суурь сонгосон тохиолдолд л илрүүлж чадна.

Фермагийн шалгуур маш хурдан бөгөөд Кармайклын тоо маш ховор тул практикт одоо ч ашиглагдсаар байна. Жишээ нь $10^9$-ээс доош ийм тоо ердөө 646 л байдаг.

Миллер-Рабины анхны тооны шалгуур

Миллер-Рабины шалгуур нь Фермагийн шалгуурын санааг өргөтгөдөг.

Сондгой тоо $n$-ийн хувьд $n-1$ нь тэгш бөгөөд бид 2-ын бүх зэргийг ялган авч болно. Бид дараах байдлаар бичиж болно:

$$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$$

эсвэл ямар нэг $0 \le r \le s - 1$-ийн хувьд

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

биелэх эсэхийг шалгана.

Хэрэв бид дээрх тэнцлүүдийн аль нэгийг ч хангахгүй $a$ суурь олсон бол $n$-ийн нийлмэл байдлын гэрч олсон болно. Энэ тохиолдолд бид $n$ анхны тоо биш болохыг баталсан.

Фермагийн шалгуурын нэгэн адил тэгшитгэлийн олонлог нийлмэл тооны хувьд хангагдах боломжтой. Тэр тохиолдолд $a$ суурийг хүчтэй худалч гэж нэрлэдэг. Хэрэв $a$ суурь тэгшитгэлүүдийн (аль нэгийг) хангавал $n$ нь зөвхөн хүчтэй магадлалтай анхны болно. Гэвч бүх тривиал бус суурь худал хэлдэг Кармайклын тоо шиг тоо байдаггүй. Үнэндээ хамгийн ихдээ суурийн $\frac{1}{4}$ нь хүчтэй худалч байж болохыг харуулах боломжтой. Хэрэв $n$ нийлмэл бол санамсаргүй суурь түүнийг нийлмэл гэж хэлэх магадлал $\ge 75\%$ байна. Өөр өөр санамсаргүй суурь сонгож олон давталт хийснээр бид тоо үнэхээр анхны эсвэл нийлмэл эсэхийг маш өндөр магадлалаар хэлж чадна.

Here is an implementation for 64 bit integer.

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;
}

Миллер-Рабины шалгуурын өмнө эхний хэдэн анхны тооны аль нэг нь хуваагч эсэхийг нэмж шалгаж болно. Ихэнх нийлмэл тоо маш бага анхны хуваагчтай байдаг тул энэ нь шалгуурыг ихээхэн хурдасгана. Жишээ нь бүх тооны $88\%$ нь $100$-аас бага анхны үржигдэхүүнтэй байдаг.

Детерминистик хувилбар

Миллер зөвхөн $\le O((\ln n)^2)$ бүх суурийг шалгах замаар алгоритмыг детерминистик болгох боломжтойг харуулсан. Дараа нь Бах тодорхой хязгаар өгсөн, зөвхөн $a \le 2 \ln(n)^2$ бүх суурийг шалгахад хангалттай.

Энэ нь одоо ч нэлээд их тооны суурь юм. Тиймээс хүмүүс доод хязгаарыг олоход нэлээд их тооцооллын хүчин чармайлт зарцуулсан. 32 битийн бүхэл тоог шалгахад зөвхөн эхний 4 анхны суурийг шалгахад хангалттай болох нь тогтоогдсон: 2, 3, 5 ба 7. Энэ шалгуурт унадаг хамгийн бага нийлмэл тоо нь $3,215,031,751 = 151 \cdot 751 \cdot 28351$. Харин 64 битийн бүхэл тоог шалгахад эхний 12 анхны суурийг шалгахад хангалттай: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 ба 37.

This results in the following deterministic implementation:

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-оос бусад) анхны биш тул шалгаж буй тоо нь эдгээр суурийн анхны хуваагчдын аль нэгтэй тэнцүү эсэхийг нэмж шалгах хэрэгтэй: 2, 3, 5, 13, 19, 73, 193, 407521, 299210837.

Дасгал бодлогууд