3.3 Multiplikativne funkcije

Jedna od važnih primena faktorizacije broja je efikasno izračunavanje nekih funkcija nad prirodnim brojevima. Za funkciju \(f: \mathbb{N} \rightarrow \mathbb{N}_0\) kažemo da je multiplikativna ako i samo ako za svaka dva uzajamno prosta broja \(a\) i \(b\) (dva broja za koje je \(\mathrm{nzd}(a, b)=1\)) važi da je \(f(a \cdot b) = f(a) \cdot f(b)\). Kada se broj \(n\) faktoriše u proizvod \(p_1^{k_1}p_2^{k_2}\ldots p_m^{k_m}\), činioci \(p_1^{k_1}, p_2^{k_2}, \ldots, p_m^{k_m}\) su uzajamno prosti pa, ako je \(f\) multiplikativna funkcija, onda važi:

\[f(n) = f(p_1^{k_1}) \cdot f(p_2^{k_2}) \cdot \ldots \cdot f(p_m^{k_m}).\]

Dakle, da bi se mogla odrediti vrednost multiplikativne funkcije za proizvoljni broj \(n\) potrebno je odrediti vrednost funkcije za proizvoljni stepen prostog broja tj. za brojeve obilka \(p^k\). To je često mnogo jednostavnije nego u opštem slučaju i može se rešiti analitički, pronalaženjem izraza kojim se ta vrednost izračunava. Naglasimo da je u opštem slučaju \(f(p^k) \neq f(p)^k\), jer stepeni prostog broja \(p\) nisu međusobno uzajamno prosti (imaju zajednički delilac \(p\)).

Ako je vremenska složenost izračunavanja vrednosti \(f(p^k)\) jednaka \(O(1)\), što je često slučaj, onda vremenska složenost izračunavanja vrednosti \(f(n)\) odgovara vremenu potrebnom za faktorizaciju broja \(n\) što je \(O(\sqrt{n})\).

Ako je potrebno izračunati vrednosti nekih multiplikativnih funkcija za više ulaznih parametara (na primer za sve vrednosti od \(1\) do \(n\)), tada je moguće upotrebiti faktorizaciju pomoću Eratostenovog sita, koja je efikasnija od faktorizacije svakog broja pojedinačno.

U nastavku će biti prikazano izračunavanje nekoliko važnih multiplikativnih funkcija.

3.3.1 Ojlerova funkcija

Razmotrimo naredni problem: potrebno je odrediti broj nesvodljivih razlomaka u intervalu [0,1] čiji je imenilac jednak datom broju \(n\). To su svi oni razlomci \(\frac{m}{n},\ \ m\leq n\) za koje važi da su \(m\) i \(n\) uzajamno prosti. Zadatak se dakle svodi na prebrojavanje koliko ima prirodnih brojeva manjih ili jednakih \(n\) koji su uzajamno prosti sa \(n\).

Ojlerova funkcija (engl. Euler’s totient function) \(\varphi\) broja \(n\) označava broj prirodnih brojeva manjih ili jednakih od \(n\) koji su uzajamno prosti sa \(n\). Na primer, \(\varphi(9)=6\), jer postoji šest brojeva \(1,2,4,5,7,8\) manjih od 9 koji su uzajamno prosti sa 9, a \(\varphi(17)=16\), jer je broj \(17\) prost i uzajamno je prost sa svim brojevima strogo manjim od njega. Po definiciji je \(\varphi(1)=1\). Označimo sa \(\Phi_n\) skup svih brojeva koji su manji od \(n\) i uzajamno su prosti sa \(n\). Na primer, \(\Phi_9 = \{1, 2, 4, 5, 7, 8\}\). Važi da je \(\varphi(n) = |\Phi_n|\).

Ojlerova funkcija ima primenu u teoriji brojeva, u algebri, ali, kao što ćemo videti, igra i ključnu ulogu u sistemu za šifrovanje RSA.

Direktan algoritam

Direktan način da se reši problem bio bi da se redom prođe kroz sve brojeve od \(1\) do \(n-1\) i da se izbroji koliko je od njih uzajamno prosto sa \(n\).

// funkcija koja racuna vrednost Ojlerove funkcije
int ojlerovaFunkcija(int n) { 
  // 1 je uvek uzajamno prosto sa n
  int phi = 1; 
  for (int i = 2; i < n; i++) 
    if (nzd(i, n) == 1) 
      phi++; 
  return phi; 
} 

Prilikom računanja vrednosti Ojlerove funkcije, funkcija za određivanje najvećeg zajedničkog delioca dva broja se poziva \(O(n)\) puta. Kako znamo da je složenost algoritma za izračunavanje najvećeg zajedničkog delioca brojeva \(i\) i \(n\) jednaka \(O(\log (i+n))\) i kako je ovde uvek \(i < n\), važi da je složenost računanja vrednosti \(\mathrm{nzd}(i, n)\) jednaka \(O(\log n)\), te je ukupna složenost prikazanog algoritma za izračunavanje vrednosti Ojlerove funkcije broja \(n\) jednaka \(O(n\log n)\).

Računanje Ojlerove funkcije broja svođenjem na faktorizaciju

Dokazaćemo da je Ojlerova funkcija multiplikativna, što omogućava njeno izračunavanje svođenjem na faktorizaciju.

Pošto je Ojlerova funkcija multiplikativna, dovoljno je odrediti samo njene vrednosti za stepene prostih brojeva tj. za brojeve oblika \(p^k\).

Na osnovu ovoga, moguće je izračunati vrednost Ojlerove funkcije za proizvoljno \(n\).

Često je u primenama (na primer u algoritmu RSA) potrebno izračunati \(\varphi(n)\), gde je \(n\) proizvod dva velika prosta broja \(p\) i \(q\); tada je \(\varphi(n) = \varphi(p\cdot q) = \varphi(p) \cdot \varphi(q) = (p - 1)\cdot(q-1)\).

Implementacija algoritma za računanje Ojlerove funkcije broja svodi se na prilagođavanje algoritma faktorizacije. Množenje promenjlive phi faktorom (1 - 1/p) u implementaciji ne bi bilo korektno, jer taj faktor nije celobrojan. Ako phi inicijalizujemo na n, možemo ga ažurirati naredbama oblika phi = (phi / p) * (p - 1), jer je broj phi uvek deljiv brojem p (phi se inicijalizuje na vrednost n, a p je uvek delilac broja n). S obzirom na to da je (phi / p) * (p - 1) = phi - phi / p, možemo izbeći množenje tj. možemo ažurirati phi naredbama oblika phi -= phi / p.

// funkcija koja racuna vrednost Ojlerove funkcije
// svodjenjem na problem faktorizacije
int ojlerovaFunkcija(int n) {
  // rezultat inicijalizujemo na n
  int phi = n; 
  // za svaki prost cinilac p broja n
  // rezultat mnozimo sa 1-1/p = (p-1)/p
  // usput azuriramo vrednost broja n
  for (int p = 2; p * p <= n; p++) {
    if (n % p == 0) { 
      while (n % p == 0) 
        n /= p; 
      phi -= phi / p; 
    } 
  } 
  // ako je n prost broj
  if (n > 1) 
    phi -= phi / n; 
  return fi; 
}

Složenost ovog algoritma odgovara složenosti odgovarajućeg algoritma za faktorizaciju, odnosno jednaka je \(O(\sqrt{n})\). Iako je ovaj algoritam neuporedivo efikasniji nego direktan algoritam, izračunavanje vrednosti Ojlerove funkcije kada nije poznata faktorizacija broja \(n\) se smatra računski izuzetno teškim problemom i nije ga moguće izvršiti za velike brojeve \(n\) (sa nekoliko stotina cifara). Na ovome se zasniva sigurnost nekih kriptografskih algoritama (na primer, RSA opisanog u poglavlju 3.5).

Kao što je to slučaj kada se radi faktorizacija, umesto da se u petlji prolazi redom kroz sve prirodne brojeve od \(2\) do \(\sqrt{n}\), posebno se može razmotriti vrednost \(p=2\), a zatim se u petlji može prolaziti samo kroz skup neparnih brojeva od \(3\) do \(\sqrt{n}\), čime bi se dobilo ubrzanje za faktor \(2\).

Računanje Ojlerove funkcije svih brojeva do n

Ukoliko bi zadatak bio da se izračuna vrednost Ojlerove funkcije za sve brojeve manje ili jednake \(n\), prethodna implementacija bila bi složenosti \(O(n\sqrt{n})\).

Kao i ranije, razmotrimo varijantu algoritma zasnovanu na Eratostenovom situ, kojom se angažuje dodatni memorijski prostor veličine \(O(n)\). Na osnovu jednakosti (1) možemo zaključiti da se za sve brojeve deljive nekim prostim brojem \(p\) u izrazu za vrednost Ojlerove funkcije javlja činilac \(1-\frac{1}{p}\). Dakle, možemo redom prolaziti kroz sve proste brojeve i vrednosti Ojlerove funkcije svih umnožaka tekućeg prostog broja \(p\) pomnožiti izrazom \(1-\frac{1}{p}\).

Pošto u izrazu (1) za \(\varphi(n)\) kao činilac figuriše \(n\), vrednosti elemenata pomoćnog niza \(\bar{\varphi}(i),\ 1\leq i \leq n,\) inicijalizovaćemo na vrednost \(i\). Razmatraćemo redom sve vrednosti za \(p\) počev od 2 do \(n\): naime, za razliku od osnovne varijante Eratostenovog sita gde je vrednost za \(p\) išla do \(\sqrt n\), ovde je neophodno da \(p\) prođe skupom svih vrednosti do \(n\), jer je potrebno obraditi vrednosti svih prostih činilaca (a ne samo najmanjih) svih brojeva. Ukoliko prilikom obrade broja \(p\) i dalje važi \(\bar{\varphi}(p)=p\), to znači da je broj \(p\) prost, pa vrednost \(\bar{\varphi}\) svih umnožaka broja \(p\) množimo sa \(\frac{p-1}{p}\). Pritom ne možemo kao u originalnoj verziji Eratostenovog sita krenuti od vrednosti \(p^2\), jer moramo sve umnoške broja \(p\) (i brojeve \(p, 2p, 3p,\ldots,(p-1)p\)) pomnožiti sa \(\frac{p-1}{p}\). Ako prilikom obrade broja \(p\) važi \(\bar{\varphi}(p) \neq p\), broj \(p\) je složen i preskače se. Na kraju algoritma u pomoćnom nizu \(\bar{\varphi}(i)\) nalaze se vrednosti Ojlerove funkcije za sve vrednosti \(i\) od 1 do \(n\).

Opisani algoritam se jednostavno implementira.

vector<int> OjlerovaFunkcijaDoN(int n) {
  // niz u kome na poziciji i formiramo vrednost phi(i)
  vector<int> phi(n + 1);
  // inicijalizujemo sve vrednosti
  for (int i = 1; i <= n; i++) 
    phi[i] = i;
  // za sve vrednosti od 2 do n
  for (int p = 2; p <= n; p++) {
    // ako vrednost nije menjana, to znaci da je p prosto
    if (phi[p] == p) {
      // azuriramo vrednosti Ojlerove funkcije
      // za sve umnoske broja p
      for (int i = p; i <= n; i += p)
         phi[i] -= phi[i] / p; 
    } 
  } 
  return phi;
} 

Iako se sa prolazom kroz činioce ne ide do \(\sqrt{n}\) već do \(n\) i iako se precrtavaju svi umnošci od \(p\) do \(n\), umesto od \(p^2\) do \(n\), složenost prikazanog algoritma i dalje iznosi \(O(n\log \log n)\), što je i složenost osnovne varijante Eratostenovog sita u koju su uključena sva ova odsecanja.

Zbir Ojlerovih funkcija delilaca

Naredna lema daje jedno interesantno svojstvo Ojlerove funkcije koje nam omogućava da na drugi način odredimo vrednosti Ojlerove funkcije za sve brojeve od 1 do \(n\).

Pre nego što pređemo na dokaz, razmotrimo naredni primer.

Prethodna lema nam daje način da korišćenjem naredne formule izračunamo \(\varphi(n)\).

\[\varphi(n) = n - \sum_{d\vert n, d < n} \varphi(d).\]

Postupak je sličan Eratostenovom situ. Inicijalizuju se sve vrednosti u nizu fi tako da se na poziciji \(i\) nalazi vrednost \(i\). Zatim prolazimo kroz sve vrednosti \(d\) od \(1\) do \(n\). Invarijanta algoritma je da to se u trenutku obrade vrednosti \(d\) u nizu na poziciji \(d\) već nalazi izračunata vrednost \(\varphi(d)\). Tada tu vrednost oduzimamo od svih umnožaka broja \(d\). Invarijanta zaista važi, jer kada se stigne do broja \(d\) od početne vrednosti \(d\) su oduzete sve vrednosti funkcije \(\varphi\) za delioce broja \(d\) (oni su svi manji od \(d\) pa su tada već obrađeni).

Implementacija je jednostavna.

vector<int> OjlerovaFunkcijaDoN(int n) {
  vector<int> phi(n+1);
  for (int i = 1; i <= n; i++)
     phi[i] = i;
  for (int d = 1; d <= n; d++)
     for (i = d+d; i <= n; i += d)
         phi[i] -= phi[d];
  return phi;
}

Pošto se u ovom algoritmu unutrašnja petlja izvršava za sve vrednosti broja \(d\), a ne samo za proste, složenost algoritma je \(O(n\log{n})\).

3.3.2 Funkcije delilaca

Funkcija delilaca (engl. divisor function) je neka funkcija nad skupom delilaca datog celog broja. U funkcije delilaca spadaju broj delilaca i zbir delilaca datog broja koje ćemo u daljem tekstu detaljnije razmatrati. Uopštenje ove dve funkcije je funkcija zbira stepena delilaca broja:

\[\sigma_l(n) = \sum_{d | n} d^l\]

Tada je zbir delilaca \(\sigma_1(n)\), a broj delilaca \(\sigma_0(n)\).

Ponekad se razmatra i zbir pravih delilaca, u koje spadaju svi delioci osim \(n\). U zavisnosti od toga da li je zbir pravih delilaca broja manji, jednak ili veći od njega samog, brojevi se mogu klasifikovati na deficitarne (engl. deficit), savršene (engl. perfect) ili obilne (engl. abundant). Zbir pravih delilaca broja se naziva i alikvotna suma i lako izračunava kada je poznat zbir svih delilaca.

Broj delilaca

Direktan algoritam

Primetimo da je svaki broj deljiv brojem \(1\) i da broj \(n\) uvek deli sam sebe te je broj delilaca broja \(n\) uvek veći ili jednak \(2\) (osim kada je \(n=1\)). Delioci \(1\) i \(n\) su trivijalni delioci broja \(n\). Jednostavni algoritam za određivanje broja delilaca broja \(n\) prolazi skupom svih brojeva od \(1\) do \(n\) i za svaku vrednost koja deli broj \(n\) se ukupan broj delilaca uvećava za \(1\). Pošto nema delilaca između \(n/2\) i \(n\), algoritam se može malo usavršiti tako što se delilac \(n\) obradi zasebno (na primer, pre petlje), dok se u petlji prolazi skupom brojeva od \(1\) do \(n/2\).

// funkcija koja racuna broj delilaca broja n
// razmatrajuci sve potencijalne delioce pojedinacno
int brojDelilaca(int n) { 
  // broj delilaca je bar 1 -- sam taj broj
  int br = 1; 
  for (int i = 1; i <= n/2; i++) 
    if (n % i == 0) 
      br++; 
  return br; 
} 

Složenost ovog algoritma je \(O(n)\).

Traženje parova delilaca

Primetimo da se delioci skoro uvek javljaju u paru: u prethodnom primeru imamo da je \(24=1\cdot 24 = 2\cdot 12 = 3\cdot 8 = 4\cdot 6\). Ovo ne važi samo kada je \(n\) kvadrat nekog broja: na primer delioci broja \(16\) su \(1,2,4,8\) i \(16\), gde središnji delilac \(4\) nema svog para (tj. sam je svoj par). Primetimo da je manji od brojeva koji čine par manji od \(\sqrt{n}\) (a ako je broj potpun kvadrat, tada je broj \(\sqrt{n}\) sam sebi par). Stoga je moguće formulisati efikasniji algoritam koji prolazi skupom svih brojeva manjih ili jednakih \(\sqrt{n}\) i za svaki broj \(d\) koji deli broj \(n\) ako je \(d\neq \frac{n}{d}\) ukupan broj delilaca uvećava za \(2\), a ako je \(d=\frac{n}{d}\) za \(1\).

// funkcija koja racuna broj delilaca broja n
// razmatrajuci parove delilaca
int brojDelilaca(int n) { 
  int br = 0; 
  for (int i = 1; i * i <= n; i++) 
    if (n % i == 0)
      if (i * i != n)
        br += 2;
      else
        br++;
  return br; 
} 

Primetimo da smo ovom malom modifikacijom prethodnog algoritma, smanjili asimptotsku složenost algoritma na \(O(\sqrt{n})\).

Svođenje na problem faktorizacije

Funkcija broja delilaca \(\sigma_0\) je multiplikativna.

Dakle, dovoljno je samo da umemo da izračunamo vrednosti \(\sigma_0(p^k)\).

Ovo je zapravo prilično očigledno, jer je opšti oblik svakog delioca broja \(n\) jednak \(d=p_1^{l_1}\cdot p_2^{l_2}\cdot\ldots\cdot p_m^{l_m}\), gde za svako \(1\leq i \leq m\) važi \(0\leq l_i\leq k_i\). Dakle, za eksponent činioca \(p_i\) u deliocu \(d\) postoji \(k_i+1\) različitih mogućnosti, te je ukupan broj delilaca broja \(n\) jednak \((k_1+1)\cdot(k_2+1)\cdot\ldots\cdot(k_r+1)\). Primetimo da u ovoj formuli figurišu samo eksponenti prostih činilaca, a ne i sami činioci.

Implementacija se dobija jednostavnom modifikacijom algoritma faktorizacije.

int brojDelilaca(int n) {
  // ukupan broj delilaca broja n
  int broj = 1;
  // prolazimo skupom svih brojeva od 2 do sqrt(n)
  for (int i = 2; i * i <= n; i++) {
    // broj puta koliko broj i deli n
    int k = 0;
    while (n % i == 0) {
      n /= i;
      k++;
    }
    // ukupan broj delilaca mnozimo sa k+1
    broj *= (k + 1);
  }
  // ako je preostali broj prost, njegova vrednost za k je 1,
  // te je prethodni rezultat potrebno pomnoziti sa k + 1 = 2
  if (n > 1)
    broj *= 2;
    
  return broj;
}

Složenost prethodnog algoritma za računanje broja delilaca broja \(n\) odgovara složenosti faktorizacije broja \(n\), te iznosi \(O(\sqrt{n})\). Primetimo da ako nam je unapred poznata faktorizacija broja \(n\), broj delilaca možemo lako efektivno odrediti.

Određivanje broja delilaca brojeva od \(1\) do \(n\)

Po uzoru na Eratostenovo sito, lako je odrediti broj delilaca svakog broja do \(1\) do \(n\). Broj \(1\) je delilac svakog broja, pa broj delilaca svakog broja inicijalizujemo na \(1\). Zatim prolazimo redom kroz sve moguće delioce \(d\) i broj delilaca njihovih umnožaka (krenuvši od samog \(d\)) uvećavamo za \(1\).

vector<int> brojDelilaca(n+1, 1);
for (int d = 2; d <= n; d++)
   for (int k = d; k <= n; k++)
      brojDelilaca[k]++;

Složenost ovog algoritma je \(O(n\log{n})\), što je efikasnije od izračunavanja broja delilaca svakog broja pojedinačno, koje bi bilo složenosti \(O(n\sqrt{n})\).

Zbir delilaca

Direktan algoritam

Naivni pristup za rešavanje ovog problema je proći skupom svih brojeva manjih od \(n\) i uvećavati tekuću sumu delilaca za vrednost svakog od brojeva koji deli broj \(n\). Složenost ovog pristupa je \(O(n)\).

// funkcija koja racuna sumu delilaca broja n
// razmatrajuci sve moguce delioce pojedinacno
int zbirDelilaca(int n) { 
  // n je uvek sam sebi delilac
  int zbir = n; 
  for (int i = 1; i < n; i++) 
    if (n % i == 0) 
      zbir += i; 
  return zbir; 
}

Traženje parova delilaca

Efikasniji pristup je da se delioci otkrivaju u paru, tako što se prolazi skupom svih brojeva manjih ili jednakih \(\sqrt{n}\) i za svaki broj \(i\) koji deli broj \(n\) vrednost \(i\) i vrednost njemu odgovarajućeg činioca \(n/i\) se dodaje na tekuću sumu, osim kada je baš \(i=n/i\), odnosno kada je \(i=\sqrt{n}\), kada se na sumu dodaje samo vrednost \(i\).

// funkcija koja racuna sumu delilaca broja n
// razmatrajuci parove delilaca
int zbirDelilaca(int n) { 
  int zbir = 0; 
  for (int i = 1; i * i <= n; i++) 
    if (n % i == 0)
      if (i * i != n)
        zbir += (i + n/i);
      else
        zbir += i;
  return zbir; 
} 

Složenost ovog algoritma je \(O(\sqrt{n})\).

Svođenje na problem faktorizacije

I funkcija zbira delilaca je multiplikativna. Dokažimo još opštije da su sve funkcije \(\sigma_l\) multiplikativne (podsetimo se, \(\sigma_l\) izračunava zbir \(l\)-tih stepena delilaca).

Dakle, dovoljno je da znamo vrednost \(\sigma_1(p^k)\).

Do ovog rezultata smo mogli doći i direktno. Opšti oblik delioca broja \(n\) jednak je \(d=p_1^{l_1}\cdot p_2^{l_2}\cdot\ldots\cdot p_m^{l_m}\), gde je \(0\leq l_i\leq k_i\). Primetimo da se u narednom izrazu posle oslobađanja od zagrada svaki delilac broja \(n\) pojavljuje u sumi tačno jednom:

\[(1+p_1+p_1^2+\ldots+p_1^{k_1})\cdot(1+p_2+p_2^2+\ldots+p_2^{k_2})\cdot\ldots\cdot(1+p_m+p_m^2+\ldots+p_m^{k_m})\]

odnosno izraz je jednak sumi delilaca broja \(n\). Dakle, problem se svodi na identifikovanje prostih činalaca broja \(n\), odnosno na faktorizaciju broja \(n\). Iako je na papiru jednostavnije da umesto sume \(1 + p_i + p_i^2 + \ldots + p_i^{k_i}\) primenimo formulu za zbir geometrijskog niza i dobijemo \(\frac{p_i^{k_i + 1}-1}{p_i - 1}\), u implementaciji stepenovanje možemo izbeći ako traženi zbir računamo inkrementalno, čime dobijamo i brži i jednostavniji kod. Naime, poznati zbir \(S = 1 + p_i + \ldots + p_i^k\) možemo ažurirati dodavanjem sabirka \(p_i^{k+1}\), ali i množenjem sa \(p_i\) i sabiranjem sa \(1\).

int zbirDelilaca(int n) {
  // ukupan zbir delilaca broja n
  int zbir = 1;
  // prolazimo skupom svih brojeva od 2 do sqrt(n)
  for (int p = 2; p * p <= n; p++) {
     // 1 + p + ... + p^k
    int S = 1;
    while (n % p == 0) {
      n /= p;
      S = S * p + 1;
    }
    // azuriramo vrednost zbira delilaca
    zbir *= S;
  }
  // ako je preostali broj n prost, njegovi delioci su 1 i n
  if (n > 1)
    zbir *= (1 + n);
  return zbir;
}

Složenost algoritma za računanje sume svih delilaca zasnovanog na faktorizaciji je \(O(\sqrt{n})\).

Određivanje zbira delilaca brojeva od \(1\) do \(n\)

Veoma slično broju delilaca, po uzoru na Eratostenovo sito, algoritmom složenosti \(O(n\log{n})\) možemo odrediti i zbirove delilaca svih brojeva od \(1\) do \(n\).

vector<int> brojDelilaca(n+1, 1);
for (int d = 2; d <= n; d++)
   for (int k = d; k <= n; k++)
      brojDelilaca[k] += d;

Zadaci:

• Broj delilaca proizvoda
• Zbir NZD svih parova delilaca