Rastavljanje na proste činioce (faktorizacija)

Na primer, za \(n=315\), dobija se razlaganje \(315 = 3\cdot 3\cdot 5 \cdot 7\).

Kao što ćemo videti nešto kasnije, faktorizacija brojeva igra važnu ulogu u oblasti kriptografije. Međutim, ona može biti od koristi i za rešavanje nekih standardnih matematičkih problema, poput računanja najvećeg zajedničkog delioca (bez Euklidovog algoritma) ili najmanjeg zajedničkog sadržaoca dva broja, za izračunavanje kvadratnog korena potpunih kvadrata itd. U nastavku ćemo opisati osnovni algoritam za faktorizaciju brojeva zasnovan na pokušajima deljenja potencijalnim činiocima (eng. trial division), koji je složenosti \(O(\sqrt{n})\). Postoje i mnogi efikasniji algoritmi (na primer, Polardov \(\rho\), kvadratno sito, Fermaova i Ojlerova faktorizacija itd.), međutim, i sa njima problem faktorizacije ostaje težak problem, čije velike instance (npr. brojeve sa nekoliko stotina cifara) ni najsavremeniji računari ne mogu nikako rešiti.

Problem faktorizacije broja \(n\) možemo rešavati induktivno-rekurzivnim pristupom na sledeći način. Pretpostavimo da sve brojeve manje od \(n\) umemo da rastavimo na proste činioce. Ako nekako ustanovimo da je broj \(n\) prost, onda je jedini prost činilac broja \(n\) on sam i problem je rešen. Ako \(n\) nije prost broj, onda se on može predstaviti kao proizvod \(n=d\cdot n_1\), gde je \(d\) najmanji od svih činilaca broja \(n\) (veći od 1).

Dakle, da bi se pronašao najmanji prost činilac broja \(n\), dovoljno je pronaći najmanji činilac broja \(n\) i on će obavezno biti prost (to se ne mora eksplicitno proveravati). Najmanji činilac se može pronaći prolaskom kroz skup prirodnih brojeva redom od \(2\) do \(\sqrt{n}\). Ako postoji činilac \(d \leq \sqrt{n}\), broj \(n\) je složen i problem se svodi na faktorizaciju broja \(n_1 = n / d\), čije proste činioce prema induktivnoj hipotezi umemo da odredimo. Ako ne postoji činilac \(d\leq \sqrt{n}\) broja \(n\), tada je broj \(n\) prost i on je svoj jedini prost činilac.

Na osnovu ove konstrukcije jednostavno je formulisati rekurzivni algoritam.

Iterativna varijanta ovog rekurzivnog algoritma sastoji se iz narednih koraka: prolazi se skupom brojeva \(d\) od \(2\) do \(\sqrt{n}\) i ako je \(n\) deljivo brojem \(d\), sve dok je \(n\) deljivo sa \(d\) pamtimo ili štampamo vrednost \(d\) (to su prosti činioci) i postavljamo vrednost \(n\) na \(n/d\). Nakon toga, ako je \(n > 1\), \(n\) je prost i on je prost činilac polaznog broja.

S obzirom na to da nijedan prost broj veći od \(2\) nije paran, efikasnije je zasebno razmatrati broj \(2\), a zatim proći skupom neparnih brojeva od \(3\) do \(\sqrt{n}\) (moguće je nakon brojeva \(2\) i \(3\) razmatrati samo brojeve oblika \(6k\pm -1\), čime se dobija ušteda za faktor \(3\)).

// funkcija koja racuna sve proste cinioce broja n
vector<int> prostiCinioci(int n) {
  // vektor u koji upisujemo rezultat
  vector<int> cinioci;
  // ako je n parno, uzimamo cinilac 2 onoliki broj puta koliko puta deli n
  while (n % 2 == 0) {
    cinioci.push_back(2);
    // azuriramo n
    n /= 2;
  }
  // n je neparno
  // prolazimo kroz neparne brojeve 
  for (int d = 3; d*d <= n; d += 2) {
    // sve dok d deli n, uzimamo cinilac d
    while (n % d == 0) {
      cinioci.push_back(d);
      // azuriramo n
      n /= d;
    }
  }
  // ako je n veci od 1, on je prost
  if (n > 1)
    cinioci.push_back(n);
    
  return cinioci;
}

Invarijanta spoljašnje for petlje algoritma čija je implementacija u C++ prikazana je to da je u svakom koraku proizvod do tada određenih činilaca i trenutne vrednosti promenljive \(n\) jednak polaznom broju \(n\), kao i da trenutna vrednost \(n\) nije deljiva ni sa jednim brojem koji je manji ili jednak \(d\). Kada se spoljašnja petlja završi, pošto broj \(n\) nije deljiv ni sa jednim brojem manjim ili jednakim od svog korena, \(n\) mora biti prost, pa ako je veći od \(1\), on je najveći prost činilac polaznog broja.

Istaknimo jednu važnu stvar: nigde u programu se posebno ne ispituje da li su pronađeni činioci prosti brojevi. Na prvi pogled ovo može delovati zbunjujuće, međutim redosled kojim tražimo činioce broja \(n\) nam garantuje da će svaki određeni činilac \(d\) biti prost. Naime, na osnovu invarijante znamo da kada se vrednost \(d\) doda u kolekciju činilaca broja \(n\), trenutna vrednost promenljive \(n\) nije deljiva nijednim brojem manjim od \(d\), a ako bi \(d\) bio složen, tj. ako bi važilo \(d=d_1\cdot d_2\), \(n\) bi bio deljiv sa \(d_1\) i \(d_2\) koji su veći od \(1\), a manji od \(d\), što je na osnovu invarijante nemoguće.

Pošto se petlja for izvršava do korena iz \(n\) (koje je sve vreme manje ili jednako polaznoj vrednosti broja \(n_0\equiv n\)), možemo zaključiti da je složenost algoritma \(O(\sqrt{n_0})\). Primetimo da se za složene brojeve granica \(\sqrt{n}\) petlje for smanjuje sa svakim novim pronađenim činiocem (jer će nova vrednost za \(n\) biti strogo manja od stare), pa u nekim slučajevima algoritam može izvršiti i dosta manje koraka od \(\sqrt{n_0}\). Ako su prosti činioci (ne nužno različiti) broja \(n_0\) redom jednaki \(p_1\leq p_2\leq \ldots \leq p_{k-1}\leq p_k\), može se pokazati da je složenost ovog algoritma za faktorizaciju \(O(\max(p_{k-1},\sqrt{p_k}))\), jer se deli do \(p_{k-1}\), a zatim eventualno do \(\sqrt{p_k}\). Primetimo da je u pitanju izlazno-zavisna složenost, jer složenost zavisi od rezultata. Pri tom pretpostavljamo da radimo sa mašinskim tipovima podataka, pa se unutrašnja petlja kojom se vrši deljenje izvršava uvek mali broj puta (zbir svih stepena u faktorizaciji je ograničen brojem bitova u zapisu broja).

Dakle, važi sledeće: nije jednako teško faktorisati sve brojeve iste dužine. Najteže instance ovog problema, ako se primenjuje opisani algoritam, čine brojevi koji su prosti ili su proizvodi dva približno jednaka prosta broja. Naime, kada su oba ova prosta činioca velika i slične veličine, ovaj problem postaje jako teško rešiti. Kao ilustraciju ovoga, navedimo da se primenom veoma efikasnog algoritma faktorizacije, 2009. godine okončao dvogodišnji napor grupe istraživača da se faktoriše broj od 232 cifre korišćenjem više stotina računara. Pretpostavljena težina ovog problema je osnova za procenu sigurnosti velikog broja kriptografskih algoritama, kao što je RSA algoritam (videti poglavlje 3.5).

Naglasimo i da je to što se petlja zaustavlja kada je \(d > \sqrt{n}\) i što se slučaj prostog broja \(n\) obrađuje van petlje dovelo do algoritma složenosti \(O(\sqrt{n})\). Ako bi se činioci redom proveravali sve dok se broj deljenjem ne svede na vrednost \(1\), umesto da se stane kada se pređe \(\sqrt{n}\) (kako se često radi kada se ručno određuju prosti činioci), dobio bi se algoritam složenosti \(O(n)\). Dakle, to što su za bazu indukcije uzeti svi prosti brojevi a ne broj \(1\), dovelo je do značajno efikasnijeg algoritma.

3.2.1 Fermaov algoritam faktorizacije

Kada broj \(n\) ima činioce blizu vrednosti \(\sqrt{n}\), oni se efikasnije mogu naći Fermaovim algoritmom. On je zasnovan na tome da se svaki neparan prirodan broj \(n\) može napisati kao razlika dva potpuna kvadrata \(n = a^2 - b^2\). Zaista, broj \(n\) se uvek može napisati kao proizvod \(n = n_1 \cdot n_2\) (ako je \(n\) prost, tada je \(n_1=n\) i \(n_2=1\), a ako je \(n\) složen, \(n_1\) i \(n_2\) mogu biti njegovi proizvoljni činioci). Pri tom su \(n_1\) i \(n_2\) neparni, jer je \(n\) neparan. Tada važi

\[n = \left(\frac{n_1 + n_2}{2}\right)^2 - \left(\frac{n_1 - n_2}{2}\right)^2,\]

pri čemu su kvadrati celobrojni, jer su \(n_1\) i \(n_2\) neparni, pa su njihov zbir i razlika parni.

Ako je \(n = a^2 - b^2\), tada se \(n\) može rastaviti na činioce \((a-b)\cdot(a+b)\). Ako je \(a-b\) različito od \(1\), tada smo pronašli dva činioca, koji se dalje mogu faktorisati.

Algoritam se zasniva na isprobavanju raznih vrednosti \(a\), krenuvši od \(\left\lceil{\sqrt{n}}\right\rceil\), naviše i ispitivanju da li je \(b^2 = a^2 - n\) potpun kvadrat (tj. kvadrat celog broja \(b\)). U nekom trenutku \(b^2\) mora biti potpun kvadrat. Zaista, ako je \(n=n_1\cdot n_2\), u nekom trenutku će \(a\) dostići vrednost \((n_1 + n_2) / 2\). Ako je \(n\) prost, to će se desiti tek kada se dostigne \((n+1)/2\), što je prilično neefikasno. Sa druge strane, ako postoji činilac broja \(n\) blizak vrednosti \(\sqrt{n}\), on će se brzo pronaći, jer pretraga kreće baš od vrednosti \(a = \left\lceil{\sqrt{n}}\right\rceil\) koja je bliska broju, a ako postoje vrednosti \(n_1\) i \(n_2\) bliske broju \(\sqrt{n}\), i njihova aritmetička sredina će mu biti bliska i brzo će biti pronađena. Prilikom provere da li je \(b^2\) potpun kvadrat puno brojeva može biti odbačeno na osnovu jednostavnih testova (na primer, poslednja cifra tj. ostatak pri deljenju sa \(10\) potpunog kvadrata mora biti \(0\), \(1\), \(4\), \(5\), \(6\), ili \(9\), a slični kriterijumi se mogu formulisati i za druge brojevne osnove).

3.2.2 Faktorizacija više brojeva pomoću Eratostenovog sita

Nekad je potrebno veliki broj puta izvršiti faktorizaciju broja i to se može uraditi efikasno korišćenjem ideje Eratostenovog sita. Zato naredni postupak nazivamo faktorizacija pomoću Eratostenovog sita.

Moguće je \(O(n)\) puta izvršiti ispočetka osnovni algoritam faktorizacije i ukupna složenost ovog pristupa iznosi \(O(n\sqrt{n})\).

Ključni korak razmotrenog algoritma za faktorizaciju je pronalaženje najmanjeg (prostog) činioca tekućeg broja. Kada faktorišemo više brojeva doći ćemo u situaciju da više puta za isti broj određujemo najmanji prosti činilac. Na primer, prilikom faktorisanja broja \(221\) odredićemo da je njegov najmanji prost činilac \(13\), a prilikom faktorisanja broja \(442\) odredićemo da je njegov najmanji prost činilac \(2\), međutim, tada ćemo broj \(442\) podeliti sa \(2\) i ponovo doći u situaciju da treba da određujemo najmanji prost činilac broja \(221\), što smo već jednom uradili. Dakle, do efikasnijeg rešenja dolazi se ako primenimo tehniku dinamičkog programiranja tj.
memoizacije i konstruišemo pomoćni niz dužine \(n\) koji za svako \(k\le n\) sadrži najmanji prost činilac broja \(k\). Naime, kad bismo znali vrednost najmanjeg prostog činioca svakog broja \(k\) za \(k\leq n\), broj \(m \leq n\) bismo mogli faktorisati na sledeći način: računamo vrednost \(p_1\) najmanjeg prostog činioca broja \(m\), zatim vrednost \(p_2\) najmanjeg prostog činioca broja \(m/p_1\), zatim vrednost najmanjeg prostog činioca broja \(m/(p_1\cdot p_2),\ldots\) Dakle, problem faktorizacije brojeva od \(1\) do \(n\) možemo svesti na problem efikasnog izračunavanja najmanjeg prostog činioca svih brojeva od \(1\) do \(n\) i smeštanje ovih vrednosti u odgovarajući niz.

Niz koji za svaki prirodan broj manji ili jednak \(n\) sadrži vrednost njegovog najmanjeg prostog činioca, može se dobiti malim prilagođavanjem Eratostenovog sita. Podsetimo se, Eratostenovo sito se koristi da se odrede svi prosti brojevi do datog broja \(n\), tako što se precrtaju svi umnošci broja \(2\), zatim broja \(3\), zatim broja \(5\) i tako redom, sve dok se ne precrtaju i svi umnošci broja \(\left\lfloor{\sqrt{n}}\right\rfloor\). Neprecrtani brojevi su svi traženi prosti brojevi.

Ovaj se algoritam lako prilagođava tako da određuje najmanji prost činilac svakog broja do \(n\). Inicijalno za svaki broj \(i\) postavljamo da je njegov najmanji prost činilac baš \(i\). U originalnom Eratostenovom situ se prilikom prolaska kroz umnoške nekog prostog broja \(d\) označava da su ti umnošci složeni (za šta se koristi niz logičkih vrednosti). Umesto toga, u ovom algoritmu ćemo prilikom prolaske kroz umnoške nekog prostog broja \(d\), svim umnošcima kojima nije ranije umanjena vrednost najmanjeg prostog činioca, postaviti tu vrednost na \(d\). Za broj \(d\) zaključujemo da je prost, ako je njegov najmanji prost činilac on sam. Prilikom razmatranja umnožaka prostog broja \(d\), možemo da krenemo od \(d^2\), jer su brojevi \(2d,3d,\ldots,(d-1)d\) deljivi redom sa \(2,3,\ldots,d-1\), te sigurno imaju činilac manji od \(d\).

Kada se prva faza završi i popuni niz najmanjih prostih činilaca, tada se u drugoj fazi popunjeni niz može upotrebiti za brzu faktorizaciju bilo kog broja od \(1\) do \(n\).

U nastavku je data implementacija algoritma faktorizacije svih brojeva od 1 do \(n\) korišćenjem Eratostenovog sita.

vector<int> eratosten(int n) {
  // niz koji cemo popuniti tako da se na poziciji i
  // nalazi najmanji prost cinilac broja i
  vector<int> najmanjiCinilac(n + 1);
 
  // postavljamo da je najmanji prost cinilac svakog broja sam taj broj
  for (int i = 1; i <= n; i++)
    najmanjiCinilac[i] = i;
  for (int d = 2; d * d <= n; d++)
    // ako je broj d prost, tj njegov najmanji prost činilac je on sam
    if (najmanjiCinilac[d] == d)
      // prolazimo kroz skup svih umnozaka tog broja
      for (int i = d * d; i <= n; i += d)
        // ako nije ranije azurirana vrednost, odnosno
        // postavljena neka manja vrednost za cinilac
        if (najmanjiCinilac[i] == i)
          // postavljamo da je najmanji prost cinilac broj d
          najmanjiCinilac[i] = d;
  return najmanjiCinilac;
}

// funkcija koja ispisuje sve proste cinioce broja n
void ispisiProsteCinioce(int n, const vector<int>& najmanjiCinilac) {
  while (n != 1) {
    // stampamo najmanji prost cinilac broja n
    cout << najmanjiCinilac[n] << " ";
    // azuriramo vrednost n
    n /= najmanjiCinilac[n];
  }
  cout << endl;
}

int main() {
  int n;
  cout << "Unesite broj n" << endl;
  cin >> n;
  auto najmanjiCinilac = eratosten(n);
  for (int i = 1; i <= n; i++)
    ispisiProsteCinioce(i, najmanjiCinilac);
  return 0;
}

Složenost prvog koraka algoritma – određivanja najmanjeg prostog činioca svih brojeva do \(n\) jednaka je složenosti algoritma Eratostenovo sito koja je, ako pretpostavimo da je složenost sabiranja \(O(1)\), jednaka sumi \(n/p\) po prostim brojevima \(p\), što je \(O(n\log{\log n})\). Složenost ispisivanja prostih činilaca broja \(k\) iznosi \(O(\log k)\) jer je maksimalni broj prostih činilaca broja \(k\) jednak \(\log_2 k\), a pretpostavljamo da je deljenje činiocima konstantne vremenske složenosti. Pošto treba ispisati proste činioce svih brojeva od \(1\) do \(n\), ukupno vreme potrebno za to jednako je \(\log 1+\log 2+\ldots+\log n\) što je, prisetimo se, jednako \(\Theta(n\log n)\). Dakle, složenost prikazanog algoritma za faktorizaciju brojeva od \(1\) do \(n\) je jednaka \(O(n\log{\log n})+O(n\log n)=O(n\log n)\), što je značajno efikasnije od pristupa zasnovanog na nezavisnoj faktorizaciji svakog broja posebno.

Zadaci:

• Dopuna do punog kvadrata
• Max nzd