În acest articol enumerăm mai mulți algoritmi de factorizare a numerelor întregi, fiecare dintre ei putând fi atât rapid, cât și lent (unii mai lenți decât alții), în funcție de datele de intrare.

Observați că, dacă numărul pe care doriți să îl factorizați este de fapt un număr prim, majoritatea algoritmilor, în special algoritmul de factorizare al lui Fermat, algoritmul p-1 al lui Pollard, algoritmul rho al lui Pollard vor funcționa foarte lent. Prin urmare, este logic să efectuați un test de primalitate probabilistic (sau determinist rapid) înainte de a încerca să factorizați numărul.

Folosind definitia

Acesta este cel mai simplu algoritm de bază pentru a găsi o descompunere in factori primi.

Împărțim cu fiecare divizor posibil d. Putem observa că este imposibil ca toți factorii primi ai unui număr compus să fie mai mari decât \( \sqrt{n} \) . Prin urmare, trebuie doar să testăm divizorii \( 2 \le d \le \sqrt{n}\), ceea ce ne oferă factorizarea primilor în \( O(\sqrt{n})\).

Cel mai mic divizor trebuie să fie un număr prim. Îndepărtăm factorul din număr și repetăm procesul. Dacă nu putem găsi niciun divizor în intervalul \( [2; \sqrt{n}]\), atunci numărul în sine trebuie să fie prim.

vector<long long> trial_division1(long long n) {
    vector<long long> factorization;
    for (long long d = 2; d * d <= n; d++) {
        while (n % d == 0) {
            factorization.push_back(d);
            n /= d;
        }
    }
    if (n > 1)
        factorization.push_back(n);
    return factorization;
}

Factorizarea roată

Aceasta este o optimizare a variantei in care folosim definitia. Ideea este următoarea. Odată ce știm că un număr nu este divizibil cu 2, nu mai este nevoie să verificăm fiecare alt număr par. Acest lucru ne lasă doar 50% din numere de verificat. După ce verificăm 2, putem pur și simplu să începem cu 3 și să sărim peste toate celelalte numere.

Această metodă poate fi extinsă. Dacă numărul nu este divizibil cu 3, putem ignora toți ceilalți multipli de 3 în calculele viitoare. Astfel, trebuie să verificăm doar numerele \( \5, 7, 11, 13, 17, 19, 23, \dots\) . Putem observa un model al acestor numere rămase. Trebuie să verificăm toate numerele cu \( \d \bmod 6 = 1\) și \( \d \bmod 6 = 5\). Astfel, ne rămân doar 33,3% din numere de verificat. Putem pune în aplicare acest lucru verificând mai întâi numerele prime 2 și 3, apoi putem începe verificarea cu 5 și alternativ să sărim 1 sau 3 numere.

Putem extinde acest lucru și mai mult. Iată o implementare pentru numerele prime 2, 3 și 5. Este convenabil să folosim o matrice pentru a stoca cât de mult trebuie să sărim.

vector<long long> trial_division3(long long n) {
    vector<long long> factorization;
    for (int d : {2, 3, 5}) {
        while (n % d == 0) {
            factorization.push_back(d);
            n /= d;
        }
    }
    static array<int, 8> increments = {4, 2, 4, 2, 4, 6, 2, 6};
    int i = 0;
    for (long long d = 7; d * d <= n; d += increments[i++]) {
        while (n % d == 0) {
            factorization.push_back(d);
            n /= d;
        }
        if (i == 8)
            i = 0;
    }
    if (n > 1)
        factorization.push_back(n);
    return factorization;
}

Dacă extindem acest lucru mai departe cu mai multe numere prime, putem ajunge chiar la procente mai bune. Cu toate acestea, și listele de sărituri vor deveni mult mai mari.

Prime precalculate

Extinderea factorizării roții cu din ce în ce mai multe numere prime va lăsa exact numerele prime de verificat. Așadar, o modalitate bună de verificare este de a calcula în prealabil toate numerele prime cu ciurul lui Eratosthenes până la \( \sqrt{n} \) și de a le testa individual.

vector<long long> primes;
vector<long long> trial_division4(long long n) {
    vector<long long> factorization;
    for (long long d : primes) {
        if (d * d > n)
            break;
        while (n % d == 0) {
            factorization.push_back(d);
            n /= d;
        }
    }
    if (n > 1)
        factorization.push_back(n);
    return factorization;
}

Metoda de descompunere in factori primi a lui Fermat

Putem scrie un număr compus impar \( n = p \cdot q\) ca diferență a două pătrate \( n = a^2 – b^2\):

\(n = \left(\frac{p + q}{2}\right)^2 – \left(\frac{p – q}{2}\right)^2\)

Metoda de descompunere in factori primi a lui Fermat încearcă să exploateze acest fapt, ghicind primul pătrat \( a^2\) și verificând dacă partea rămasă \( b^2 = a^2 – n\) este, de asemenea, un număr pătrat. Dacă este, atunci am găsit factorii \( a – b\) și \( a + b\) ai lui n.

int fermat(int n) {
    int a = ceil(sqrt(n));
    int b2 = a*a - n;
    int b = round(sqrt(b2));
    while (b * b != b2) {
        a = a + 1;
        b2 = a*a - n;
        b = round(sqrt(b2));
    }
    return a - b;
}

Observați că această metodă de factorizare poate fi foarte rapidă, dacă diferența dintre cei doi factori p și q este mică. Algoritmul se execută în timp \( O(|p – q|)\). Cu toate acestea, deoarece este foarte lent, odată ce factorii sunt foarte depărtați, este rar utilizat în practică.

Cu toate acestea, există încă un număr mare de optimizări pentru această abordare. De exemplu, prin examinarea pătratelor \( a^2\) modulo un număr mic fix, puteți observa că nu trebuie să vă uitați la anumite valori a, deoarece acestea nu pot produce un număr pătrat \( a^2 – n\)