Potęgowanie modularne

Na koniec przyjrzyjmy się właściwości potęgowania:

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.

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.

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ź":

2^90 = 2^50 * 2^40

2^50 mod 13 = 1125899906842624 mod 13 = 4
  2^40 mod 13 = 1099511627776 mod 13 = 3

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 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....