3.4 Modularna aritmetika

U osnovi modularne aritmetike leži operacija određivanja celobrojnog količnika i ostatka. Podsetimo se, broj je \(q\) količnik, a broj \(r\) ostatak pri deljenju broja \(x\) brojem \(y\) ako i samo ako postoje brojevi \(q\) i \(r\) takvi da važi \(x = q\cdot y + r\) i \(0 \leq r < y\). Brojevi \(q\) i \(r\) su ovim uslovom jedinstveno određeni. Pisaćemo \(q = a \,\mathrm{div}\,b\) i \(r = a \,\mathrm{mod}\,b\).

Pored toga što sa \(\,\mathrm{mod}\,\) označavamo binarnu operaciju, \(\,\mathrm{mod}\,\) se koristi i kao oznaka relacije u skupu celih brojeva. Naime, pisaćemo \(a \equiv b\ (\mathrm{mod}\ m)\) i reći da su \(a\) i \(b\) kongruentni po modulu \(m\) ako \(m\vert a-b\) tj. ako je \(a \,\mathrm{mod}\,m = b \,\mathrm{mod}\,m\), odnosno ako \(a\) i \(b\) daju isti ostatak pri deljenju sa \(m\). Na primer, \(12 \equiv 2\ (\mathrm{mod}\ 5)\) jer \(5\vert (12-2)\).

Relaciju \(\mathrm{mod}\) koristimo u raznim svakodnevnim situacijama, a da toga često nismo ni svesni. Jedan od takvih primera je rad sa vremenom. Naime, za vreme koje je \(15\) časova nakon \(11\) sati reći ćemo da je \(2\) sata (što odgovara tome da je \(11+15 \equiv 2\ (\mathrm{mod}\ 24)\)). Slično važi i za dane u nedelji koje možemo obeležiti brojevima od 0 do 6 (na primer, od nedelje, do subote). Operacije vršimo po modulu \(7\). Na primer, ako je danas četvrtak (dan obeležen brojem 4), za šest dana biće sreda (dan obeležen brojem 3), jer je \(4+6 \equiv 3\ (\mathrm{mod}\ 7)\). Analogno se računa i mesec ili redni broj nedelje u godini. Modularna aritmetika ima još puno praktičnih primena, pomenimo samo neke zanimljive: koristi se za izračunavanje kontrolnih suma za međunarodne standardne identifikatore knjiga (ISBN brojeve), međunarodne brojeve bankovnih računa (IBAN), kao i jedinstvene identifikatore hemijskih jedinjenja (CAS registarski broj). Modularna aritmetika je i u osnovi nekih savremenih kriptografskih sistema.

Neoznačeni celi brojevi se u računarima predstavljaju sa \(k\) bitova, a operacije nad njima se izvode po modulu \(2^k\). Recimo, u jeziku C++ brojevi tipa unsigned int su širine \(32\) bita, pa se operacije nad njima izvode po modulu \(2^{32}\).

unsigned int x = 123456789;
unsigned int y = x * x;
cout << y << endl;

Ako je \(a_1 \equiv b_1\ (\mathrm{mod}\ m)\) i \(a_2 \equiv b_2\ (\mathrm{mod}\ m)\), onda je \(a_1\pm a_2 \equiv b_1\pm b_2\ (\mathrm{mod}\ m)\) i \(a_1\cdot a_2 \equiv b_1\cdot b_2\ (\mathrm{mod}\ m)\); na primer,

\[\begin{array}{ccc} 12,14 & \stackrel{\,\mathrm{mod}\,5}\longrightarrow & 2,4 \\ +\downarrow & & \downarrow + \\ 26 & \stackrel{\,\mathrm{mod}\,5}\longrightarrow & 1 \end{array} \]

Drugim rečima, relacija \(\mathrm{mod}\) je saglasna (kongruentna) sa operacijama sabiranja, oduzimanja i množenja. Rezimirajmo osnovne osobine kogruencija u narednoj lemi.

Ovo inspiriše sledeće jednakosti koje se koriste za računanje vrednosti zbira ili proizvoda brojeva po modulu \(m\).

Računanje na osnovu prethodnih jednakosti je važno, jer često omogućava da se izbegnu greške nastale usled prekoračenja. Naime, ako su brojevi \(a\) i \(b\) relativno veliki, a \(m\) mali, tada izrazi \(a+b\) i \(a\cdot b\) mogu dovesti do prekoračenja, pa se samim tim mogu dobiti netačni rezultati prilikom izračunavanja vrednosti izraza \((a+b)\,\mathrm{mod}\,m\) i \((a\cdot b)\,\mathrm{mod}\,m\). Sa druge strane, u izrazima \((a\,\mathrm{mod}\,m + b\,\mathrm{mod}\,m)\,\mathrm{mod}\,m\) i \((a\,\mathrm{mod}\,m \cdot b\,\mathrm{mod}\,m)\,\mathrm{mod}\,m\) se računa sa manjim brojevima i oni najčešće ne dovode do prekoračenja.

Ipak, treba biti obazriv, jer je moguće da se desi da su i operandi (\(a\,\mathrm{mod}\,m\) i \(b\,\mathrm{mod}\,m\)) i krajnji rezultat dovoljno mali da se mogu ispravno predstaviti određenim tipom, ali da su međurezultati (\(a\,\mathrm{mod}\,m + b\,\mathrm{mod}\,m\) i naročito \(a\,\mathrm{mod}\,m \cdot b\,\mathrm{mod}\,m\)) preveliki da bi mogli da se ispravno predstave.

Zato je u slučaju velikih vrednosti broja \(m\) poželjno međurezultate izračunati u širem tipu (na primer, ako su \(a \,\mathrm{mod}\,m\) i \(b \,\mathrm{mod}\,m\) predstavljeni sa \(32\) bita, tada je poželjno konvertovati ih i pomnožiti kao \(64\)-bitne brojeve, pre nego što se izračunavanjem ostatka dobije konačan rezultat koji se ponovo ispravno može predstaviti pomoću \(32\) bita).

Prethodna svojstva nam omogućavaju da garantujemo da će se uz sva prekoračenja međurezultata koja dolaze tokom rada sa neoznačenim brojevima, na kraju izračunavanja dobiti rezultat koji je jednak ostatku pri deljenju brojem \(2^{32}\) (tj. \(2\) na broj bitova upotrebljenih za zapis) rezultata koji bi se dobio bez prekoračenja.

Razmotrimo sada problem određivanja razlike nenegativnih brojeva \(b\) i \(a\) po modulu \(m\). Na primer, potrebno je odrediti vrednost \((b-a)\,\mathrm{mod}\,m\) za \(a,b\geq 0\). Pretpostavimo za početak da su brojevi \(a\) i \(b\) manji od \(m\). Ponovimo da ne postoji saglasnost između različitih programskih jezika u računanju vrednosti a % m kada je vrednost broja a negativna. Naime, u jeziku C++ se za vrednost ostatka pri deljenju može dobiti negativan broj: na primer, vrednost izraza (2 - 7) % 3 je \(-2\), dok se u jeziku Python kao rezultat istog ovog izraza dobija pozitivan broj \(1\). Često želimo da kao rezultat računanja vrednosti po modulu dobijemo nenegativnu vrednost. Umesto da vršimo analizu slučajeva, rešenje je moguće dobiti izračunavanjem vrednosti izraza \((b \,\mathrm{mod}\,m - a \,\mathrm{mod}\,m + m)\,\mathrm{mod}\,m\).

Naravno, ako se unapred zna da su argumenti \(a\) i \(b\) već svedeni po modulu \(m\) (tj. važi \(0 \leq a < m\) i \(0 \leq b < m\)), onda je dovoljno samo koristiti izraz \((b - a + m) \,\mathrm{mod}\,m\).

Prethodno tvrđenje nam omogućava da u bilo kom programskom jeziku razliku po modulu možemo izračunati jednim izrazom, tako da se dobije nenegativan rezultat.

Važi sličan rezultat i za stepenovanje po modulu.

Ova lema se jednostavno dokazuje primenom pravila za množenje brojeva po modulu. Pošto i vrednost \((a\,\mathrm{mod}\,m)^n\) veoma brzo raste i može dovesti do prekoračenja, prilikom računanja stepena, svođenje po modulu treba vršiti prilikom svakog množenja. Ovakvo modularno stepenovanje se najbolje izvodi algoritmom brzog stepenovanja (pri čemu je poželjno u prvom pozivu svesti vrednost \(a\) po modulu \(m\) tj. kao prvi parametar proslediti vrednost a % m).

int stepen(int a, int n, int m) {
    if (n == 0)
       return 1;
    if (n % 2 == 0)
        return stepen((a * a) % m, n / 2, m);
    else
        return (a * stepen(a, n-1, m)) % m;
}

Aritmetičke operacije po modulu \(m\) se često koriste, pa ćemo uvesti naredne skraćene oznake: sa \(+_m\) ćemo obeležavati sabiranje po modulu tj. \(a +_m b\) je oznaka za \((a + b)\,\mathrm{mod}\,m\), sa \(\times_m\) množenje po modulu tj. \((a \cdot b)\,\mathrm{mod}\,m\) itd.

U kriptografiji se obično razmatraju jako veliki brojevi (sa po nekoliko hiljada cifara) koji se ne mogu predstaviti mašinskim tipovima podataka i za koje se ni osnovne aritmetičke operacije ne mogu izvršiti u konstantnom vremenu. Podsetimo se da je broj cifara broja \(n\) jednak \(O(\log{n})\), odakle slede naredna tvrđenja.

• Sabiranje i oduzimanje dva velika broja (reda veličine broja \(n\)) može se izvršiti u vremenu \(O(\log{n})\).
• Množenje takva dva broja se osnovnim algoritmom može izvršiti u vremenu \(O(\log^2{n})\) (a može i efikasnije, na primer, primenom brze Furijeove transformacije opisane u poglavlju 3.7).
• I deljenje se može osnovnim algoritmom izvršiti u vremenu \(O(\log^2{n})\) (a postoje i efikasniji algoritmi).

Dakle, sve osnovne aritmetičke operacije su dovoljno efikasne i kada se sprovode nad brojevima sa po nekoliko hiljada cifara.

Stvar se ne menja značajno ni kada se operacije izvršavaju po modulu. Određivanje ostatka zahteva dodatno deljenje, međutim, smanjuje broj cifara rezultata, pa se složeni izrazi ponekad efikasnije izračunavaju kada su operacije po modulu.

• U poglavlju 3.4.1 videćemo da deljenje po modulu (tj. određivanje modularnog inverza) zahteva sprovođenje proširenog Euklidovog algoritma, pa je sporije od množenja brojeva po modulu. Međutim, prošireni Euklidov algoritam primenjen na brojeve \(a\) i \(n\) zahteva \(O(\log(a + n))\) koraka koji uključuju osnovne aritmetičke operacije po modulu. Zato su u rezultujućoj složenosti deljenja po modulu svi izrazi pod logaritmom, pa se i ova operacija može izvršiti relativno efikasno (u veoma razumnom vremenu, čak i za brojeve koji imaju po nekoliko hiljada cifara).
• Modularno stepenovanje \(a^k \,\mathrm{mod}\,n\) zahteva \(O(\log{k})\) operacija deljenja i množenja po modulu, pa se i ono može izvršiti u razumnom vremenu, čak i kada vrednosti brojeva \(a\), \(k\) i \(n\) imaju po nekoliko hiljada cifara.

Sa druge strane, u slučaju jako velikih vrednosti modula \(n\), neke operacije koje se efikasno sprovode nad mašinskim tipovima podataka su jako neefikasne i ne mogu se praktično izvršiti. Kod ovako velikih brojeva postoji ogromna razlika između algoritama složenosti \(O(\sqrt{n})\) i \(O(\log{n})\). Ako je \(n\) reda veličine \(10^{1000}\), onda algoritam koji izvršava \(\sqrt{n}\) operacija izvršava \(10^{500}\) operacija, što je neizvodivo, dok algoritam koji izvršava \(\log{n}\) operacija izvršava samo oko 1000 operacija, što je veoma brzo. Sigurnost mnogih kriptografskih protokola zasnovana je na težini izvođenja operacija složenosti \(O(\sqrt{n})\).

• Operacija faktorizacije broja \(n\) zahteva \(O(\sqrt{n})\) koraka ako se koristi osnovni algoritam opisan u poglavlju 3.2 i ne može se sprovesti za brojeve koji imaju velike proste faktore.

• Izračunavanje Ojlerove funkcije (i sličnih multiplikativnih funkcija) obično se svodi na faktorizaciju, pa je i ono praktično neizvodivo.

• Operacija inverzna modularnom stepenovanju, tj. operacija pronalaženja vrednosti \(k\) takve da je \(a^k \equiv b\ (\mathrm{mod}\ n)\) naziva se diskretni logaritam i do sada nije pronađen ni jedan algoritam koji bi omogućio njeno efikasno izvršavanje (za brojeve od po nekoliko hiljada cifara i najsavremenijim računarima bi trebali bilioni godina za rešavanje ovog problema).

3.4.1 Modularne grupe

Za svaki prirodan broj \(n\) mogući ostaci pri deljenju sa \(n\) čine skup \(Z_{n} = \{0, 1, \ldots, n-1\}\). Kada se ovi ostaci kombinuju operacijom \(+_n\) sabiranja po modulu \(n\) i operacijom \(\times_n\) množenja po modulu \(n\) ponovo se dobijaju vrednosti koje pripadaju tom skupu. Pošto su obe operacije asocijativne i pošto neutral za sabiranje \(0\) i neutral za množenje \(1\) pripadaju skupu ostataka \(Z_{n}\), strukture \((Z_n, +_n)\) i \((Z_n \setminus \{0\}, \times_n)\) su monoidi¹ (za bilo koju vrednost \(n\)).

Svaki element u strukturi \((Z_n, +_n)\) ima inverzni element jer je za svako \(x \in Z_n\) i element \(n-x \in Z_n\) i važi \(x +_n (n - x) = 0\), pa je struktura \((Z_n, +_n)\) grupa² (za bilo koju vrednost \(n\)). Ovu grupu nazivamo aditivna grupa celih brojeva po modulu \(n\) ili modularna aditivna grupa i obeležavamo sa \(\mathbb{Z}_n^+\). Inverzni element u odnosu na \(+_n\) nazivamo modularni aditivni inverz.

U narednoj tablici prikazana je tablica sabiranja modularne aditivne grupe \(\mathbb{Z}_5^+\).

Da li, analogno aditivnim, možemo da razmatramo modularne multiplikativne grupe? Struktura \((Z_n \setminus \{0\}, \times_n)\) ne mora biti grupa, jer ne moraju svi elementi da imaju inverz (koji u ovom slučaju nazivamo modularni multiplikativni inverz). Na primer, razmotrimo tablicu za \(n=6\).

Kada se broj \(2\) pomnoži bilo kojim elementom skupa \(Z_6 \setminus \{0\}\), dobija se paran broj i ostatak tog broja pri deljenju sa \(6\) može biti samo \(0\), \(2\) ili \(4\). Zato \(2\) nema inverzni element. Slično se dešava i sa elementima \(3\) i \(4\). Element \(1\) je sam sebi inverzan, a isto važi i za element \(5\) (jer je \(5 \cdot 5 = 25 \equiv 1\ (\mathrm{mod}\ 6)\)).

Sa druge strane, razmotrimo tablicu za \(n=5\).

Jasno je da svaki element ima sebi inverzni (u svakoj vrsti i svakoj koloni se tačno jednom javlja vrednost \(1\)) i ova struktura je grupa. Inverz broja \(1\) je uvek \(1\) (jer je \(1 \cdot 1 = 1\)), inverz broja \(2\) je \(3\) (jer je \(2\cdot 3 = 6 \equiv 1\ (\mathrm{mod}\ 5)\)), inverz broja \(3\) je \(2\), a broj \(4\) je sam svoj inverz (jer je \(4 \cdot 4 = 16 \equiv 1\ (\mathrm{mod}\ 5)\)). Ova struktura je, dakle, grupa.

Dakle, za neke vrednosti \(n\), struktura \((Z_n \setminus \{0\}, \times_n)\) jeste grupa, a za neke nije.

Primetimo da su u slučaju \(n=6\) inverz imali brojevi \(1\) i \(5\) koji su uzajamno prosti sa \(6\), a u slučaju \(n=5\) svi brojevi \(1\), \(2\), \(3\) i \(4\), jer su svi uzajamno prosti sa \(5\). Razmotrimo sada opšti slučaj i formulišimo potreban i dovoljan uslov da element skupa \(Z_n\setminus \{0\}\) ima inverz u odnosu na operaciju \(\times_n\).

Broj \(x\) je inverz broja \(a\), ali je i \(a\) ujedno inverz broja \(x\), pa je i \(x\) uzajamno prost sa \(n\).

Ako je \(p\) prost broj, svi elementi skupa \(Z_p \setminus \{0\}\) su uzajamno prosti sa \(p\), pa je struktura \(\mathbb{Z}_p^\times = (Z_p \setminus \{0\}, \times_p) = (\{1, 2, \ldots, p-1\}, \times_p)\) grupa i označavamo je sa \(\mathbb{Z}_p^\times\). Još opštije, ako posmatramo samo skup \(\Phi_n\) brojeva između \(1\) i \(n-1\) koji su uzajamno prosti sa \(n\), struktura \((\Phi_n, \times_n)\) je grupa. Primetimo da za prost broj \(p\) važi da je skup \(Z_p \setminus \{0\} = \Phi_p\), pa je grupa \(\mathbb{Z}_p^\times\) samo specijalni slučaj grupe \(\mathbb{\Phi}_n^\times = (\Phi_n, \times_n)\), kada je \(n\) prost broj. Grupa \((\Phi_n, \times_n)\) naziva se multiplikativna grupa celih brojeva po modulu \(n\) ili modularna multiplikativna grupa. Ove grupe ćemo obeležavati sa \(\mathbb{\Phi}_n^\times\).

Operacija deljenja brojem \(a\) po modulu \(n\) se svodi na množenje modularnim multiplikativnim inverzom broja \(a\) po modulu \(n\). Ovo se u nekim situacijama može upotrebiti za optimizaciju deljenja. Pretpostavimo da je potrebno izvršiti deljenje većeg broja neoznačenih brojeva nekim brojem \(k\), da su ti brojevi zapisani sa \(w\) bitova i svi deljivi sa \(k\). Umesto da se svi brojevi dele sa \(k\) moguće je (jednom) izračunati modularni multiplikativni inverz broja \(k\) po modulu \(2^w\), a zatim sve brojeve pomnožiti tim inverzom. Na sistemima na kojima se množenje izvršava brže od deljenja, ovo predstavlja optimizaciju. Naravno, da bi modularni multiplikativni inverz postojao, potrebno je da su brojevi \(k\) i \(2^w\) uzajamno prosti, što je slučaj ako i samo ako je broj \(k\) neparan. Sličan postupak možemo upotrebiti i ako je \(k\) paran, tako što ćemo \(k\) zapisati u obliku \(2^p\cdot k'\) za neparan broj \(k'\), a zatim svaki broj podeliti sa \(2^p\) (pomeranjem bitova za \(p\) mesta udesno, što je veoma brza operacija), pre množenja sa modularnim multiplikativnim inverzom broja \(k'\) po modulu \(2^w\) (on sigurno postoji jer je \(k'\) neparan broj).

3.4.2 Mala Fermaova i Ojlerova teorema

Kardinalnost skupa \(\Phi_n\), tj. broj brojeva između 1 i \(n-1\) koji su uzajamno prosti sa \(n\) izračunava se Ojlerovom funkcijom \(\varphi\), čije je izračunavanje opisano u poglavlju o multiplikativnim funkcijama 3.3. Važi \(|\Phi_n| = \varphi(n)\). Ojlerova teorema nam suštinski govori o određenim stepenima elemenata modularne multiplikativne grupe, ali se uopštava i na brojeve koji su veći od \(n\).

Osnovni slučaj Ojlerove teoreme se odnosi na elemente skupa \(\Phi_n\), odnosno brojeve \(1 \leq a < n\) uzajamno proste sa \(n\). Ako pretpostavimo da teorema važi za njih, lako je dokazati i da važi za sve ostale brojeve koji zadovoljavaju uslove teoreme. Recimo da je \(a > n\) i da je \(a\) uzajamno prosto sa \(n\). Tada se \(a\) može podeliti sa \(n\), tj. postoje brojevi \(q\) i \(1 \leq r < n\) takvi da je \(a = qn + r\). Ako je \(a\) uzajamno prost sa \(n\), takav mora biti i \(r\) (jer ako bi \(r\) imao neki zajednički činilac sa \(n\) desna strana bi bila deljiva njime, pa bi deljiv njime morao da bude i broj \(a\) na levoj strani jednakosti). Tada je \(a^{\varphi(n)} = (qn+r)^{\varphi(n)}\), međutim, \((qn+r)^{\varphi(n)} \equiv r^{\varphi(n)}\ (\mathrm{mod}\ n)\). Pošto je i \(1 \leq r < n\), važi da je \(r \in \Phi_n\), pa na osnovu pretpostavke da teorema važi u osnovnom slučaju, tj. da važi za sve elemente skupa \(\Phi_n\), ona važi i za \(r\). Dakle, važi \(r^{\varphi(n)} \equiv 1\ (\mathrm{mod}\ n)\), pa važi i \(a^{\varphi(n)} \equiv 1\ (\mathrm{mod}\ n)\).

Specijalni slučaj Ojlerove teoreme, kada je \(n\) prost broj, je Mala Fermaova teorema (dok Ojlerova teorema govori o grupama \(\mathbb{\Phi}_n^\times\), Mala Fermaova govori samo o grupama \(\mathbb{Z}_p^\times\)).

Ako \(a\) i \(n\) nisu uzajamno prosti, tada jednakost \(a^{\varphi(n)} \equiv 1\ (\mathrm{mod}\ n)\) ne mora da važi. Na primer, ako je \(a\) deljivo sa \(p\) tada je \(a^0 = 1\), međutim važi \(a^1 \equiv 0\ (\mathrm{mod}\ p)\), \(a^2 \equiv 0\ (\mathrm{mod}\ p)\), pa i \(a^{p-1} \equiv 0\ (\mathrm{mod}\ p)\), jer su svi stepeni broja \(a\) deljivi sa \(p\), pa \(a^{p-1} \not\equiv 1\ (\mathrm{mod}\ n)\) i jednakost \(a^{p-1} \equiv 1\ (\mathrm{mod}\ p)\) ne mora da važi. Ipak, naredna, modifikovana, formulacija Male Fermaove teoreme ispravno obuhvata i ovaj slučaj.

Pokazali smo da je dovoljno da se Ojlerova teorema dokaže za svaki broj \(a \in \Phi_n\). Iz toga sledi i opšti slučaj Ojlerove teoreme i Mala Fermaova teorema. Dokažimo³ da za ovakve brojeve važi \(a^{\varphi(n)} \equiv 1\ (\mathrm{mod}\ n)\). To je neposredna posledica Lagranževe teoreme iz teorije grupa koja tvrdi da red (broj elemenata) podgrupe uvek deli red grupe iz čega rezultat direktno sledi posmatrajući grupu \(\Phi_n\) i njenu cikličku podrgrupu generisanu sa \(a\) (nju čine elementi \(1\), \(a\), \(a^2\), , \(a^{k-1}\), za neko \(k \vert \varphi(n)\) takvo da je \(a^k=1\)), međutim, daćemo direktan dokaz, bez pozivanja na rezultate teorije grupe.

XXX   XXY   XYY  YYY
      XYX   YXY
      YXX   YYX

Malu Fermaovu teoremu je jednostavno dokazati i indukcijom (Ojler je prvi objavio dokaz ove teoreme i taj je dokaz bio indukcijom).

Na osnovu male Fermaove teoreme, za svako \(1 \leq a < p\) važi da je \(a^{p-1} \equiv 1\ (\mathrm{mod}\ p)\). Prirodno se postavlja pitanje šta se dešava sa stepenima broja \(a\) kada je izložilac manji od \(p\) tj. kakav je skup \(\{a^0 \,\mathrm{mod}\,p, a^1 \,\mathrm{mod}\,p, \ldots, a^{p-2} \,\mathrm{mod}\,p\}\). Može se dokazati sledeća lema.

Dakle u grupi \((\mathbb{Z}_{p}, \times_p)\) uvek postoji element \(a\) takav da se svi elementi grupe mogu izraziti kao njegovi stepeni. Takav element se naziva generator grupe ili primitivni koren po modulu p. Pokazuje sa da u grupi \((\mathbb{Z}_{p}, \times_p)\) postoji \(\varphi(p-1)\) generatora. Pronalaženje generatora je netrivijalan problem i razmotrićemo ga u poglavlju 3.7.4.

Grupe \((\mathbb{\Phi}_{n}, \times_n)\) ne moraju biti cikličke.

Primene Ojlerove i Male Fermaove teoreme su razne: ispitivanje da li je broj prost, izračunavanje modularnog multiplikativnog inverza, RSA kriptografija i slično. Prikažimo sada primenu Male Fermaove teoreme na ispitivanje da li je broj prost, a ostale primene ovih teorema će biti prikazane u narednim poglavljima (na primer, u poglavlju 3.5 biće prikazana primena Ojlerove teoreme u oblasti kriptografije).

Fermaov test da li je broj prost

Jedna primena Male Fermaove teoreme je za testiranje da li je dati broj \(n\) prost ili ne (engl. Fermat primality test). Mala Fermaova teorema daje potreban uslov da bi broj bio prost. Naime, za dati broj \(n\) možemo izabrati proizvoljan broj \(a\) koji nije deljiv sa \(n\) i izračunati vrednost \(a^{n-1} \,\mathrm{mod}\,n\). Ukoliko je rezultat različit od \(1\), broj \(n\) je sigurno složen. Ipak, teorema ne daje i dovoljan uslov da bi broj bio prost, jer postoje i složeni brojevi \(n\) takvi da za neke vrednosti \(a\) koje su uzajamno proste sa \(n\) važi da je \(a^{n-1} \,\mathrm{mod}\,n\) jednako \(1\). Ipak, ako je \(a^{n-1} \,\mathrm{mod}\,n = 1\), pokazuje se da je malo verovatno da broj \(n\) nije prost. Posebno, ako se za veliki broj različitih vrednosti za \(a\) koje su uzajamno proste sa \(n\) pokaže da je vrednost izraza \(a^{n-1} \,\mathrm{mod}\,n\) jednaka \(1\), prilično je verovatno da je broj \(n\) prost. Nažalost, ni ispitivanje svih vrednosti \(a\) koje su uzajamno proste sa \(n\) nam ne daje garanciju, jer postoje složeni brojevi \(n\) takvi da za sve brojeve \(a\) koji su uzajamno prosti sa \(n\) važi \(a^{n-1} \equiv 1 (\mathrm{mod}\ n)\). Takvi brojevi se zovu Karmajklovi brojevi (engl. Carmichael numbers) i relativno su retki. Najmanji takav broj je 561.

3.4.3 Izračunavanje modularnog multiplikativnog inverza

U poglavlju 3.4.1 o modularnim grupama smo videli da je multiplikativni inverz broja \(a\) po modulu \(n\) (engl. modular multiplicative inverse) broj \(x\) za koji važi \(a\cdot x \equiv 1\ (\mathrm{mod}\ n).\)

Najčešće se kao multiplikativni inverz broja \(a\) po modulu \(n\) razmatra vrednost iz skupa \(Z_n = \{1,2,\ldots,n-1\}\).

U teoremi 3.4.1 je dokazano da inverz po modulu \(n\) broja \(a\) postoji ako i samo ako su \(a\) i \(n\) uzajamno prosti i da je u tom slučaju jedinstven po modulu \(n\). Razmotrimo sada kako ga je moguće izračunati.

Algoritam grube sile

Pri naivnom pristupu rešavanju ovog problema se za \(x\) razmatraju redom svi brojevi \(x\) od \(1\) do \(n-1\) (elementi skupa \(Z_n\)) i proverava se da li je ostatak pri deljenju broja \(a\cdot x\) sa \(n\) jednak \(1\).

// direktno racunanje multiplikativnog inverza broja a po modulu n
int modInverz(int a, int n) {
  a = a % n;
  // proveravamo redom kandidate od 1 do n-1
  for (int x = 1; x < n; x++) 
     if ((a*x) % n == 1) 
       return x; 
} 

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

Algoritam zasnovan na proširenom Euklidovom algoritmu

Na osnovu teoreme 3.4.1 modularni inverz broja \(a\) po modulu \(n\) postoji ako i samo ako su \(a\) i \(n\) uzajamno prosti. Dokaz naredne teoreme nam govori da se, kada postoji, on može odrediti proširenim Euklidovim algoritmom.

Dakle, pronalaženje modularnog inverza se može svesti na rešavanje jednačine \(ax = yn + 1\) tj. \(ax - ny = 1\), a na osnovu teoreme 3.1.4, znamo da jednačina \(ax+by=c\) ima celobrojna rešenja ako i samo ako \(d=\mathrm{nzd}(a, b)\) deli broj \(c\). Dakle, za \(c=1\) jednačina \(ax - ny = 1\) ima celobrojna rešenja \((x, y)\) ako i samo ako su \(a\) i \(n\) uzajmno prosti.

Za efikasno izračunavanje modularnog inverza možemo iskoristiti prošireni Euklidov algoritam. Potrebno je da pronađemo koeficijente \(x\) i \(y\) takve da je \(x\cdot a - y\cdot n = 1\), što možemo uraditi primenom proširenog Euklidovog algoritma na dva data, uzajamno prosta broja \(a\) i \(n\) (on će nam, doduše, vratiti i vrednost \(-y\), ali taj koeficijent nas ionako ne zanima). S obzirom na to da dobijena vrednost koeficijenta \(x\) može biti i negativna i veća od \(n\), ako želimo da \(x\) pripada \(Z_n\), tj. da zadovoljava uslov \(0\le x<n\), onda umesto \(x\) kao modularni multiplikativni inverz u programu vraćamo vrednost \((x \,\mathrm{mod}\,n + n)\,\mathrm{mod}\,n\).

Dakle, određivanje modularnog multiplikativnog inverza broja možemo svesti na prošireni Euklidov algoritam.

// racunanje multiplikativnog inverza broja a po modulu m
// koriscenjem prosirenog Euklidovog algoritma
int modInverz(int a, int n) {
  int x, y;
  // određujemo x i y tako da vazi a*x + n*y = d
  int d = nzdProsireni(a, n, x, y);

  // ako a i n nisu uzajamno prosti, onda ne postoji inverz
  if (d != 1)
    cout << "Modularni multiplikativni inverz ne postoji" << endl;
  else{
    // obezbedjujemo da je inverz iz skupa [0, n)
    int inverz = (x % n + n) % n;
    return inverz;
   }
}

Primetimo da za računanje modularnog multiplikativnog inverza broja vrednost koeficijenta \(y\) nije od interesa, te se može konstruisati algoritam koji ne poziva eksplicitno prošireni Euklidov algoritam, već na isti način kao kod proširenog Euklidovog algoritma iterativno računa samo vrednost koeficijenta \(x\).

// funkcija racuna x -- multiplikativni inverz broja a po modulu n,
// koriscenjem prosirenog Euklidovog algoritma
// funkcija vraca da li je uspela da izracuna broj x
bool modInverz(int a, int n, int& x) {
  // pocetne vrednosti za r su n i a
  int r_preth = n;
  int r_tek = a;
  // pocetne vrednosti za x su 0 i 1
  int x_preth = 0;
  int x_tek = 1;
  
  while (r_tek > 0) {
    int q = r_preth / r_tek;
    int pom;

    // azuriramo tekucu i prethodnu vrednost niza r
    pom = r_preth;
    r_preth = r_tek;
    r_tek = pom - q * r_tek;

    // azuriramo tekucu i prethodnu vrednost niza x
    pom = x_preth;
    x_preth = x_tek;
    x_tek = pom - q * x_tek;
  }

  // obezbedjujemo da je inverz iz skupa [0,m)
  x = (x_preth % n + n) % n;

  // vracamo true ako je nzd(a, n) = 1, inace false
  return r == 1;
}

Složenost prethodnog algoritma za izračunavanje multiplikativnog inverza broja \(a\) po modulu \(n\) jednaka je složenosti proširenog Euklidovog algoritma za brojeve \(a\) i \(n\) i iznosi \(O(\log(a+n))\), odnosno kada je \(a\) reda \(O(n)\) jednaka je \(O(\log n)\) (što je veoma efikasno).

Algoritam zasnovan na Ojlerovoj i Maloj Fermaovoj teoremi

Još jedan efikasan način za računanje modularnog multiplikativnog inverza broja je korišćenjem Ojlerove teoreme. Podsetimo se njenog tvrđenja: ako su \(a\) i \(n\) uzajamno prosti brojevi onda važi: \(a^{\varphi(n)} \equiv 1\ (\mathrm{mod}\ n)\). Primetimo da je uslov da su brojevi \(a\) i \(n\) uzajamno prosti takođe uslov i da bi postojao multiplikativni inverz broja \(a\) po modulu \(n\). Iz prethodne jednačine sledi:

\[a\cdot a^{\varphi(n)-1} \equiv 1\ (\mathrm{mod}\ n).\](1)

Primetimo da za proizvoljnu vrednost \(n\) važi \(\varphi(n)\geq 1\), odnosno \(\varphi(n)-1\geq 0\), te je \(a^{\varphi(n)-1}\) pozitivna celobrojna vrednost. Dakle, za \(x=a^{\varphi(n)-1} \,\mathrm{mod}\,n\) važi \(a\cdot x \equiv 1\ (\mathrm{mod}\ n)\), pa je \(a^{\varphi(n)-1}\) multiplikativni inverz broja \(a\) po modulu \(n\). Dodatno, \(a^{\varphi(n)-1}\) može biti veće od \(n\) te je kao rezultat potrebno vratiti vrednost \(x \,\mathrm{mod}\,n\) (što je unapred osigurano ako se tokom stepenovanja svođenje vrši nakon svakog množenja).

Na ovaj način smo problem računanja modularnog multiplikativnog inverza broja \(a\) sveli na računanje Ojlerove funkcije broja \(n\) što se dalje svodi na faktorizaciju broja \(n\), koja se osnovnim algoritmom opisanim u poglavlju 3.2 vrši u složenosti \(O(\sqrt{n})\), što je neprihvatljivo za brojeve od recimo \(100\) cifara.

Ukoliko je pak broj \(n\) prost, tvrđenje Ojlerove teoreme se svodi na malu Fermaovu teoremu: \(a^{n-1} \equiv 1\ (\mathrm{mod}\ n)\), odakle sledi:

\[a\cdot a^{n-2} \equiv 1\ (\mathrm{mod}\ n).\](2)

Pošto je broj \(n\) prost, važi \(n\geq 2\), odnosno \(n-2\geq 0\), te je vrednost \(a^{n-2}\) celobrojna i pozitivna. Stoga važi da je \(x=a^{n-2}\,\mathrm{mod}\,n\) multiplikativni inverz broja \(a\) po modulu \(n\). Primetimo da je ovde stvar jednostavnija, jer je vrednost Ojlerove funkcije broja \(n\) unapred poznata (i jednaka \(n-1\)).

Iz kongruencija (1) i (2) možemo jednostavno odrediti multiplikativni inverz broja \(a\) po modulu \(n\). Jedino što preostaje jeste što efikasnije izračunati odgovarajući stepen broja \(a\), što se može izvesti korišćenjem efikasnog algoritma za modularno stepenovanje broja, koji je složenosti \(O(\log k)\), gde je \(k\) vrednost eksponenta.

Napomenimo da je u situaciji kada \(n\) nije prost broj, potrebno izračunati vrednost Ojlerove funkcije broja \(n\) što uključuje faktorizaciju broja \(n\) i može biti težak problem. Međutim, u situaciji kada je broj \(n\) prost, ali takođe i kada broj \(n\) nije prost ali je poznata njegova faktorizacija, složenost ovog algoritma je \(O(\log n)\).

U nastavku je dat algoritam za računanje multiplikativnog inverza broja \(a\) po modulu \(n\) za prost broj \(n\).

// funkcija za mnozenje po modulu n
int puta_mod(int a, int b, int n) {
  return ((a % n) * (b % n)) % n;
}

// funkcija za brzo stepenovanje po modulu n
int stepen_mod(int a, int b, int n) {
    // a^0 = 1
    if (b == 0)
        return 1;
    // racunamo a^(b/2) mod n
    int rez = stepen_mod(a, b / 2, n);
    // racunamo rez*rez mod n
    rez = puta_mod(rez, rez, n);
    if (b % 2)
      // racunamo rez*a mod n
      return puta_mod(rez, a, n);
    else
        return rez;
}

// racunanje multiplikativnog inverza broja a po modulu n
// koriscenjem Male Fermaove teoreme
int modInverz(int a, int n) {
  return stepen_mod(a, n - 2, n);
}