Na koniec przyjrzyjmy się właściwości potęgowania:
A^B mod C = ( (A mod C)^B ) mod C
Często chcemy policzyć A^B mod C for dużych wartości B.
  Niestety, A^B staje się bardzo duże nawet dla stosunkowo małych wartości B.

Na przykład:

2^90 = 1 237 940 039 290 000 000 000 000 000
7^256 = 2 213 595 400 050 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 83 794 038 078 300 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 721 264 246 243 000 000 000 000 000
Te wielkie wartości powodują, że nasze kalkulatory i komputery przestają wykonywać poprawnie zlecone im operacje, ponieważ ich pamięć ulega przepełnieniu.
  Nawet, jeśli nie popełniałyby one tych błędów, wykonanie tych obliczeń zajęłoby im bardzo długi czas.

Jak można zmniejszyć rozmiar wyrażeń i zwiększyć szybkość wykonywania obliczeń?

Załóżmy, że chcemy obliczyć 2^90 mod 13, ale nie posiadamy kalkulatora, który może operować na liczbach większych niż 2^50.
Oto prosta strategia "dziel i rządź":
mniejsze częsci
reguły, dotyczące wykładników
2^90 = 2^50 * 2^40
mod C
każdej części
2^50 mod 13 = 1125899906842624 mod 13 = 4
  2^40 mod 13 = 1099511627776 mod 13 = 3
aby
oba wyniki
2^90 mod 13 = (2^50 * 2^40) mod 13
  2^90 mod 13 = (2^50 mod 13 * 2^40 mod 13) mod 13
  2^90 mod 13 = ( 4 * 3 ) mod 13
  2^90 mod 13 = 12 mod 13
  2^90 mod 13 = 12

Jak możemy szybko obliczyć A^B mod C, jeśli B jest potęgą 2 ?

Jak możemy obliczyć 7^256 mod 13 używając kalkulatora, który nie operuje na liczbach większych niż 7^10 ?
Moglibyśmy rozłożyć 7^256 na 25 części będących 7^10 oraz 1 część równą 7^6. Nie byłoby to jednak zbyt efektywne.
Jest na to lepszy sposób....
Ładowanie