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. formula_1 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:
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
missä
formula_9 kaikilla formula_10.
Alkiot formula_11 voidaan laskea peräkkäisillä neliöönkorotuksilla:
Näin olemme saaneet tehokkaan menetelmän potenssiinkorotuksen laskemiseen.
Potenssiinkorotusalgoritmi voidaan kirjoittaa myös rekursiiviseen muotoon. Helposti todetaan nimittäin, ettäOperaatio formula_19 tarkoittaa luvun k kokonaislukujakoa luvulla 2. Tämä operaatio on tietokoneella helposti suoritettavissa. Operaation suorittamiseksi lukua formula_16 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:
Esimerkki potenssiinkorotusalgoritmin käytöstä: