Folosind definitia

Prin definiție, un număr prim nu are alți divizori decât 1 și el însăși. Un număr compus are cel puțin un divizor suplimentar, să îl numim d. Natural \(\frac{n}{d} \) va fi un divizor a lui n. Este ușor de văzut, că fied \(d \le \sqrt{n}\) sau \(\frac{n}{d} \le \sqrt{n}\), prin urmare, unul dintre divizorii d si \(\frac{n}{d} \) este \(d \le \sqrt{n}\). Putem folosi aceste informații pentru a verifica primalitatea.

Încercăm să găsim un divizor nenul, verificând dacă oricare dintre numerele cuprinse între 2 si \(\sqrt{n}\) sunt divizori ai lui n. Daca exista un divizor in acest interval, atunci este clar ca n nu este prim.

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

Aceasta este cea mai simplă formă de verificare a unei prime. Puteți optimiza destul de mult această funcție, de exemplu, verificând doar toate numerele impare în buclă, deoarece singurul număr prim par este 2.

Testul de primalitate Fermat

Acesta este un test probabilistic.

Mica teoremă a lui Fermat afirmă că, pentru un număr prim și un număr întreg coprim, este valabilă următoarea ecuație:

\(a^{p-1} \equiv 1 \bmod p\)

În general, această teoremă nu este valabilă pentru numerele compuse.

Aceasta poate fi utilizată pentru a crea un test de primalitate. Alegem un număr întreg \(2 \le a \le p – 2\) , și verificam dacă ecuația se confirmă sau nu. Dacă nu se menține, de ex. \(a^{p-1} \not\equiv 1 \bmod p\) , știm că nu poate fi un număr prim. În acest caz, numim baza un martor Fermat pentru compunerea lui p.

Cu toate acestea, este posibil ca ecuația să fie valabilă și pentru un număr compus. Deci, dacă ecuația este valabilă, nu avem o dovadă a primalității. Putem spune doar că p este probabil prim. Dacă se dovedește că numărul este de fapt compus, numim baza a un mincinos al lui Fermat.

Efectuând testul pentru toate bazele posibile a, putem demonstra că un număr este prim. Cu toate acestea, acest lucru nu se face în practică, deoarece acest lucru presupune un efort mult mai mare decât simpla efectuare a unei diviziuni de probă. În schimb, testul va fi repetat de mai multe ori cu alegeri aleatorii pentru a. Dacă nu găsim niciun martor al compunerii, este foarte probabil ca numărul să fie de fapt prim.

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

Folosim Exponențierea binară pentru a calcula eficient puterea \(a^{p-1}\).

Există totuși o veste proastă: există unele numere compuse în care \(a^{n-1} \equiv 1 \bmod n\) este valabil pentru orice a coprim cu n, de exemplu pentru numărul \(561 = 3 \cdot 11 \cdot 17\). Astfel de numere se numesc numere Carmichael. Testul de primalitate Fermat poate identifica aceste numere doar dacă avem un noroc imens și alegem o bază a cu \(\gcd(a, n) \ne 1\).

Testul Fermat este încă utilizat în practică, deoarece este foarte rapid, iar numerele Carmichael sunt foarte rare. De exemplu, există doar 646 de astfel de numere sub \(10^9\).

Test de primalitate Miller-Rabin

Testul Miller-Rabin extinde ideile din testul Fermat.

Pentru un număr impar n, n-1 este par și putem elimina toate puterile lui 2. Putem scrie: \(n – 1 = 2^s \cdot d,~\text{with}~d~\text{odd}.\)

Acest lucru ne permite să factorizăm ecuația micii teoreme a lui Fermat:

\(\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}\)

Dacă n este prim, atunci n trebuie să împartă unul dintre acești factori. Iar în testul de primalitate Miller-Rabin verificăm exact această afirmație, care este o versiune mai strictă a afirmației din testul Fermat.Pentru o bază \(2 \le a \le n-2\) se verifică dacă fie: \(a^d \equiv 1 \bmod n2\) deține sau \(a^{2^r d} \equiv -1 \bmod n\) este valabil pentru un anumit \(0 \le r \le s – 1\)

Dacă am găsit o bază a care nu satisface niciuna dintre egalitățile de mai sus, atunci am găsit un martor al compunerii lui n.În acest caz am dovedit că n nu este un număr prim.

La fel ca în cazul testului lui Fermat, este posibil ca setul de ecuații să fie satisfăcut pentru un număr compus. În acest caz, baza a se numește un mincinos puternic. Dacă o bază a satisface ecuațiile (una dintre ele), este doar un prim puternic probabil. Cu toate acestea, nu există numere precum numerele Carmichael, unde se află toate bazele nenule. De fapt, este posibil să se arate că cel mult \(\frac{1}{4}\) din baze pot fi niște mincinoși puternici. Dacă n este compus, avem o probabilitate de \(\ge 75\%\) că o baza aleatorie ne va spune că este compusă. Făcând mai multe iterații, alegând diferite baze aleatoare, putem spune cu o probabilitate foarte mare dacă numărul este cu adevărat prim sau dacă este compus.

Iată o implementare pentru numere întregi pe 64 de biți.

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

Înainte de testul Miller-Rabin, puteți testa suplimentar dacă unul dintre primele câteva numere prime este un divizor. Acest lucru poate accelera foarte mult testul, deoarece majoritatea numerelor compuse au divizori primi foarte mici. De exemplu, 88% din toate numerele au un factor prim mai mic decât 100.

Versiunea deterministă

Miller a arătat că este posibil să se facă algoritmul determinist prin verificarea doar a tuturor bazelor \(\le O((\ln n)^2)\). Bach a dat mai târziu o limită concretă, este necesar doar să se testeze toate bazele \(a \le 2 \ln(n)^2\).

Acesta este încă un număr destul de mare de baze. Așadar, oamenii au investit destul de multă putere de calcul pentru a găsi limite inferioare. Se pare că, pentru testarea unui număr întreg de 32 de biți, este necesar să se verifice doar primele 4 baze prime: 2, 3, 5 și 7. Cel mai mic număr compus care nu trece acest test este \(3,215,031,751 = 151 \cdot 751 \cdot 28351\). Iar pentru testarea numerelor întregi de 64 de biți este suficient să se verifice primele 12 baze prime: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 și 37.

Aceasta duce la următoarea implementare deterministă:

bool MillerRabin(u64 n) {
    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;
}

De asemenea, este posibil să se facă verificarea cu numai 7 baze: 2, 325, 9375, 28178, 450775, 9780504 și 1795265022. Cu toate acestea, deoarece aceste numere (cu excepția lui 2) nu sunt prime, trebuie să verificați în plus dacă numărul pe care îl verificați este egal cu orice divizor prim al acestor baze: 2, 3, 5, 13, 19, 73, 193, 407521, 299210837.