Bei der Methode nach MONTGOMERY handelt es sich eigentlich um eine Multiplikationsmethode, bei der die Modulo-Reduktion des (Zwischen-) Ergebnisses ohne echte Langzahldivision erfolgen kann [Mon85], [CP05, 9.2.1], [HMV04, 2.2.4]. Da allerdings zuerst eine Transformation beider Faktoren in den MONTGOMERY-“Raum“ vorgenommen werden muß (welche zwei Modulo-Division erfordert) und außerdem einmal der erweiterte GCD-Algorithmus bemüht werden muß, kommen die Geschwindigkeitsvorteile nur bei der Potenzierung wirklich zum tragen.
Um einen leicht verständlichen Zugang zu finden, konzentrieren wir uns auf eine einzelne Multiplikation . Dazu soll eine Zahl vorausgesetzt werden, die keinen gemeinsamen Teiler mit dem Modul hat und für die gewährleistet ist. Die MONTGOMERY-Multiplikation kann man nun, unter der Voraussetzung (bzw. mit dem Satz von BéZOUT ), in folgenden Einzelschritten darstellen:
Die nötige Korrektur69 führt zu einer MONTGOMERY-Darstellung für (als Voraussetzung für den nächsten Teilschritt).70
MONTGOMERY-Reduktion Zur Herleitung von MONTGOMERY’s effizienter Berechnungsmethode für wählen wir als Ausgangspunkt:
Subtraktion beider Gleichungen ergibt
was mit zu
führt.71
Mit dem Wissen, daß es sich bei um das multiplikativ inverse Element von im Restklassensystem modulo handelt (, ), stellen wir noch um:
und gewinnen letztlich MONTGOMERY’s Reduktionsformel.
Praktisch benötigt man und nicht, sondern geht meist nach folgendem Algorithmus vor:
Bei geschickter Wahl von zum Beispiel als sind für alle (Modulo-) Divisionen in Formel 4.40 nur logische oder Schiebeoperationen nötig.72 Um zu garantieren ist die einfachste Bedingung die, als ungerade vorauszusetzen.73