Multiplikativni inverz
Motivacija
Računanje je čas posla, ali što je sa i kada je to uopće definirano?
Slično kao i u aritmetici s realnim brojevima, se definira kao inverzna operacija množenju, odnosno je jednak broju takvom da . Analogno tome, definiramo kao sve brojeve takve da . Može se pokazati da je jednoznačno definiran ako i samo ako su i relativno prosti.
Naoružani novim znanjem, ne treba dugo da pomislite vrijedi li ? E pa vrijedi (pogledati sekciju "Za one koji žele znati više")! Dakle, dovoljno je za svaki broj znati iznos "multilikativnog inverza" da bismo izračunali rezultat. Donja dva odjeljka objašnjavaju kako!
Računanje binarnim potenciranjem (čas posla)
Još od malih nogu (ili barem od predavanja iz teorije brojeva) znamo za svaki prosti broj i cijeli vrijedi da
Drugim riječima, multilikativni inverz broja računamo pomoću brzog potenciranja. Laganica.
Računanje svih inverzova (čas časa posla)
Da skratimo priču:
int M = 10007; // da, prost je int inverzi[M]; inverz[1] = 1; for (int x = 2; x < M; ++x) inverz[x] = (M - M/x) * inverz[M%x] % M;
Čudesno, zar ne?! Ali, pitate zašto?
Recimo da smo izračunali sve inverze . Znamo po "teoremu o ostacima" da postoje i takvi da:
Pomnožimo sve s (kojeg smo već izračunali), te imamo:
Drugim riječima, je modularni inverz broja . Podsjetimo se samo kako izračunati i :
i s time smo gotovi!
Za one koji žele znati više
Andrej Dujella: Uvod u teoriju brojeva - skripta (predavanje s PMF-a): http://web.math.pmf.unizg.hr/~duje/utb/utblink.pdf
Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License