exponentiering

För att göra denna modulära exponentiering bör man alltid börja med att använda binär exponentiering.

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.

Den högra summan konvergerar snabbt, och den vänstra kan beräknas effektivt med hjälp av modulär binär exponentiering för potenserna.