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

Korzystając z reguł mnożenia modularnego:
tj. A^2 mod C = (A * A) mod C = ((A mod C) * (A mod C)) mod C
Możemy użyć tego wyniku, aby szybko obliczyć 7 ^ 256 mod 13
7^1 mod 13 = 7
  7^2 mod 13 = (7^1 *7^1) mod 13 = (7^1 mod 13 * 7^1 mod 13) mod 13
Możemy teraz podstawić wynik na 7^1 mod 13 do powyższego równania.
7^2 mod 13 = (7 *7) mod 13 = 49 mod 13 = 10
  7^2 mod 13 = 10
7^4 mod 13 = (7^2 *7^2) mod 13 = (7^2 mod 13 * 7^2 mod 13) mod 13
Możemy teraz podstawić wynik na 7^2 mod 13 do tego równania.
7^4 mod 13 = (10 * 10) mod 13 = 100 mod 13 = 9
  7^4 mod 13 = 9
7^8 mod 13 = (7^4 * 7^4) mod 13 = (7^4 mod 13 * 7^4 mod 13) mod 13
Podstawiamy teraz nasz wynik na 7^4 mod 13 do powyższego równania.
7^8 mod 13 = (9 * 9) mod 13 = 81 mod 13 = 3
  7^8 mod 13 = 3
w kolejnych krokach postępujemy w analogiczny sposób.
po 5 iteracjach dostajemy:
7^256 mod 13 = (7^128 * 7^128) mod 13 = (7^128 mod 13 * 7^128 mod 13) mod 13
  7^256 mod 13 = (3 * 3) mod 13 = 9 mod 13 = 9
  7^256 mod 13 = 9
Przedstawiliśmy metode na szybkie obliczanie A^B mod C pod warunkiem, że B jest potęgą 2.
Jednakże, potrzebujemy jeszcze metody na szybkie obliczanie potęg modulo, kiedy B nie jest potęgą 2.

Jak możemy szybko obliczyć A^B mod C dla każdego B ?

Krok 1: Podziel liczbę B na potęgi 2 zapisując ją w postaci binarnej

Zacznij od liczby najbardziej na prawo. Niech k=0 i dla każdej cyfry:
  • Jeśli k-ta cyfra jest jedynką, potrzebujemy mnożenia przez 2^k.
  • dodaj 1 do liczby k i przesuń się o jedno miejsce w lewo do następnej cyfry w zapisie binarnym

Krok 2: Policz mod C dla potęg 2 ≤ B

5^1 mod 19 = 5
5^2 mod 19 = (5^1 * 5^1) mod 19 = (5^1 mod 19 * 5^1 mod 19) mod 19
  5^2 mod 19 = (5 * 5) mod 19 = 25 mod 19
  5^2 mod 19 = 6
5^4 mod 19 = (5^2 * 5^2) mod 19 = (5^2 mod 19 * 5^2 mod 19) mod 19
  5^4 mod 19 = (6 * 6) mod 19 = 36 mod 19
  5^4 mod 19 = 17
5^8 mod 19 = (5^4 * 5^4) mod 19 = (5^4 mod 19 * 5^4 mod 19) mod 19
  5^8 mod 19 = (17 * 17) mod 19 = 289 mod 19
  5^8 mod 19 = 4
5^16 mod 19 = (5^8 * 5^8) mod 19 = (5^8 mod 19 * 5^8 mod 19) mod 19
  5^16 mod 19 = (4 * 4) mod 19 = 16 mod 19
  5^16 mod 19 = 16
5^32 mod 19 = (5^16 * 5^16) mod 19 = (5^16 mod 19 * 5^16 mod 19) mod 19
  5^32 mod 19 = (16 * 16) mod 19 = 256 mod 19
  5^32 mod 19 = 9
5^64 mod 19 = (5^32 * 5^32) mod 19 = (5^32 mod 19 * 5^32 mod 19) mod 19
  5^64 mod 19 = (9 * 9) mod 19 = 81 mod 19
  5^64 mod 19 = 5

Krok 3: Użyj własności mnożenia modularnego aby wykorzystać policzone wcześniej wielkości

5^117 mod 19 = ( 5^1 * 5^4 * 5^16 * 5^32 * 5^64) mod 19
  5^117 mod 19 = ( 5^1 mod 19 * 5^4 mod 19 * 5^16 mod 19 * 5^32 mod 19 * 5^64 mod 19) mod 19
  5^117 mod 19 = ( 5 * 17 * 16 * 9 * 5 ) mod 19
  5^117 mod 19 = 61200 mod 19 = 1
  5^117 mod 19 = 1

Uwagi:

Istnieje więcej technik optymalizacji, ale są poza zakres tego artykułu. Często w kontekście kryptografii wykonuje się modularne potęgowanie z użyciem wykładników B dla których reprezentacja binarna ma długość większą niż 1000.
Ładowanie