Wat is Machtsverheffing door kwadrateren?

Als deel van de berekening, bereken je een grote macht van een getal.
Dat kan, door de macht als een binair getal te schrijven.
Elke nulbit betekent kwadrateren elke eenbit betekent kwadrateren plus vermenigvuldigen.
Een eenvoudig voorbeeld: 3^8
8 is dan 1000 binair.
Dus 3^8 wordt (((3^2)^2)^2) ofwel driemaal kwadrateren.

Iets moeilijker voorbeeld: 3^12
12 is 1100 binair
Dus 3^12 is (((3^2 )*3)^2)^2. Voor elk volgende cijfer kwadrateren alsmede voor een 1 vermenigvuldigen.

Om de rest bij deling door een priem te berekenen, moet na elke stap de rest worden berekend.
Met deze twee elementen kun je de rest berekenen bij machtsverheffing tot een heel groot getal en deling daarvan door een priem.
Het algoritme kun je nu zelf bouwen.