Avaa päävalikko

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 muotoMuokkaa

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 muuallaMuokkaa

Esimerkki potenssiinkorotusalgoritmin käytöstä:

  • M. K. Sinisalo: Solutions of the congruence   (mod  ) up to   (PDF)