Binär exponentiering

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2020-06) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

Binär exponentiering är en algoritm för att beräkna heltalspotenser, multiplikation av ett tal med sig självt ett antal gånger, på ett effektivt sätt. Idén är att utnyttja exponentens binära representation för att reducera förfarandet till en serie kvadreringar och multiplikationer.

Algoritmen kan beskrivas på rekursiv form av

${\displaystyle {\mbox{potens}}(x,\,n)=\left\{{\begin{matrix}x,&{\mbox{om }}n{\mbox{ = 1}}\\{\mbox{potens}}(x^{2},\,n/2),&{\mbox{om }}n{\mbox{ jamnt}}\\x\times {\mbox{potens}}(x^{2},\,(n-1)/2),&{\mbox{om }}n>{\mbox{2 udda}}.\\\end{matrix}}\right.}$

Antalet multiplikationer som krävs är av storleksordningen O(log n), vilket då exponenten är stor gör metoden oerhört mycket mer effektiv än direkt upprepad multiplikation. Till exempel krävs endast 25 multiplikationer för att med denna metod beräkna 10^1000000, 10 gånger sig självt en miljon gånger.

Algoritmen används med fördel för att beräkna modulära potenser, en tillämpning som har betydelse inom kryptografi.