Reszta z dzielenia algorytm

[krzych07]

Jak mozna stopniowo zmiejszac liczbe aby jej reszta z dzielenia przez pewna liczbe pozostawala stała.
Mamy \(\displaystyle{ x^{a}}\) mod b ale \(\displaystyle{ x^{a}}\) jest za duza liczba jak mozna ja stopniowo zmniejszac zeby mod wyszlo poprawnie.

[paladin]

Pomnóż \(\displaystyle{ x}\) przez siebie odpowiednią ilość razy i po każdym mnożeniu zostawiaj tylko resztę z dzielenia.

[mcbob]

Znajdź sobie a mod b, \(\displaystyle{ a ^{2}}\) mod b, \(\displaystyle{ a^{4}}\) mod b itd. A potem je wymnażaj stronami aż będzie \(\displaystyle{ a ^{p}}\)