Potenssiinkorotusalgoritmi

Potenssiinkorotusalgoritmi on yksi tärkeimmistä julkisen avaimen salakirjoitusjärjestelmien (PKI) käyttämistä algoritmeista. Sen avulla voidaan tehokkaasti laskea potenssiinkorotus muun muassa RSA:n, Diffie-Hellman-avaimenvaihtoprotokollan ja ElGamal-kryptosysteemin sovelluksissa. Potenssiinkorotusalgoritmia käytetään yleisesti myös erilaisten valesatunnaislukugeneraattoreiden toteutuksissa. 

Yleensä potenssiinkorotusalgoritmia käytetään jonkin äärellisen algebrallisen rakenteen, merk.  alkioiden potenssiinkorotukseen. Rakenteessa tulee olla määriteltynä ainakin yksi laskutoimitus, jolle käytämme seuraavassa kertolaskumerkintää. 
Potenssiinkorotuksen määrittelemiseksi oletetaan, että rakenne sisältää neutraalialkion (merk. 1) ja on ainakin potenssiassosiatiivinen ts. noudattaa normaaleja potenssiinkorotuksen laskusääntöjä.

Potenssiinkorotus määritellään nyt seuraavasti:
 , kaikilla  ja
  kaikilla  ja kaikilla 

Potenssiinkorotus tulee näin määritellyksi kaikilla luonnollisilla luvuilla.

Potenssiinkorotuksen laskeminen suoraan määritelmään nojautuen tulee kuitenkin mahdottomaksi suurilla eksponentin arvoilla. Esimerkiksi RSA-menetelmässä eksponenttien arvot voivat olla useiden satojen numeroiden mittaisia kokonaislukuja. 

Tehokkaampi menetelmä saadaan esittämällä eksponentti binäärilukuna.

Olkoon 
.

Nyt 

missä
 kaikilla .

Alkiot  voidaan laskea peräkkäisillä neliöönkorotuksilla:
 ja
, kun .

Näin olemme saaneet tehokkaan menetelmän potenssiinkorotuksen laskemiseen.

Rekursiivinen muoto

Potenssiinkorotusalgoritmi voidaan kirjoittaa myös rekursiiviseen muotoon. Helposti todetaan nimittäin, että

, kun  on parillinen ja
, kun  on pariton.

Operaatio  tarkoittaa luvun k kokonaislukujakoa luvulla 2. Tämä operaatio on tietokoneella helposti suoritettavissa. Operaation suorittamiseksi lukua  yksinkertaisesti siirretään yhden askeleen verran vähemmän merkitsevien bittien suuntaan. Parittomalla luvulla ylivuotava ykkösbitti yksinkertaisesti unohdetaan.

Rekursiivinen algoritmi potenssiinkorotuksen laskemiseksi olisi siis seuraava:

 Funktio Potensiinkorotus(x,k)
  Jos k = 0
   Palauta x
  Muuten jos k on parillinen
   Aseta h = Potenssiinkorotus(x,k/2)
   Palauta Operaatio(h,h)
  Muuten
   Aseta h = Potenssiinkorotus(x,k/2)
   Palauta Operaatio(Operaatio(h,h),x)

Aiheesta muualla 

Esimerkki potenssiinkorotusalgoritmin käytöstä:
M. K. Sinisalo: Solutions of the congruence  (mod ) up to  (PDF)

Algoritmit
Salakirjoitustekniikka