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. $S$ 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:

• $x^0=1$, kaikilla $x\in S$ ja
• $x^{k+1}=x^kx$ kaikilla $k\in\mathbb{N}$ ja kaikilla $x\in S$

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

$k=\sum_{i=0}^m b_i2^i$.

Nyt

$x^k=x^{\sum_{i=0}^m b_i2^i}=\prod_{i=0}^m (x^{2^i})^{b_i} =\prod_{i=0,b_i=1}^m x^{2^i}=\prod_{i=0,b_i=1}^m x_i,$

missä $x_i=x^{2^i}$ kaikilla $i=0,1,2,...,m$.

Alkiot $x_i$ voidaan laskea peräkkäisillä neliöönkorotuksilla:

• $x_0=x$ ja
• $x_{i+1}=x_ix_i$, kun $i=0,1,2,...,m-1$.

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

Rekursiivinen muoto

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

• $x^k=(x^{k/2})^2$, kun $k$ on parillinen ja
• $x^k=(x^{\lfloor k/2\rfloor})^2x$, kun $k$ on pariton.

Operaatio $\lfloor k/2\rfloor$ tarkoittaa luvun k kokonaislukujakoa luvulla 2. Tämä operaatio on tietokoneella helposti suoritettavissa. Operaation suorittamiseksi lukua $k$ 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 $2^{n-2}\equiv 1$ (mod $n$) up to $10^{11}$ (PDF)