Næste: D.2 Eksempel Op: D. Hurtig division Foregående: D. Hurtig division

D.1 Algoritmen

Trinnene i algoritmen er:

1. En potentiel faktor til $2^p-1$ vælges, kald den $q$.

2. Eksponenten, $p$, skrives så som et binært tal, kaldet $p_2$

3. Vi starter med at se på den mest betydende bit i $p_2$ (den længst mod venstre), og sætter resten lig 1.

4. Resten kvadreres.

5. Hvis den aktuelle bit er lig 1, ganges resten med 2, ellers forbliver den uændret. Vi ser så på næste bit i $p_2$.

6. Resultatet reduceres modulus $2^p-1$ hvorved der fremkommer en rest.

7. Trinnene 4 til 6 gentages indtil man har været igennem alle bits i $p_2$.