Modulare Exponentiation - rekursive Implementierung

 aufwärts

Die modulare Exponentiation spielt allgemein in der Kryptografie eine große Rolle. Im RSA-Verfahren beispiels­weise besteht die Chiffrierung in der Berechnung von me mod n. Hierbei sind m, e und n sehr große Zahlen (typischerweise 512 oder 1024 Bit lang).

Um me mod n zu berechnen, sind zum Glück nicht e Multi­plikationen von m mit sich selbst erforderlich. Schon bei einer Länge von e von nur 50 Bit wären dies eine Billiarde Multi­plikationen. Tatsächlich genügen weniger als 2 log(e) Multi­plikationen, also weniger als 100 bei einem 50-Bit-Exponenten.

Für die schnelle modulare Exponentiation (square and multiply) gibt es eine iterative Implementierung unter Benutzung der Binär­darstellung des Exponenten,

Am einfachsten ist die im Folgenden dargestellte rekursive Implementierung; in diesem Fall wird die Binär­darstellung des Exponenten nicht explizit benötigt.

Idee

Ausgehend von der Beobachtung, dass z.B. m13 dargestellt werden kann als

m13  =  m12 · m

und m12 als

m12  =  (m6)2

lassen sich folgende Rekursions­formeln für die Berechnung von me mit e Element natürliche Zahlen0 aufstellen:

me  =   geschweifte Klammer
1    falls e = 0
me-1 · m      falls e ungerade
(me/2)2    falls e gerade

Programm

 

Das folgende Python-Programm stellt eine mögliche Implementierung dieser Rekursions­formeln für die modulare Exponentiation dar.

 

def modexp(m, e, n):
    if e==0:
        return 1
    if e%2==1:
        return modexp(m, e-1, n)*m % n
    return modexp(m, e//2, n)**2 % n

 

Eine ent­sprechende Implementierung in der funktionalen Programmier­sprache Haskell ist die folgende:

 

-- schnelle modulare Exponentiation
modexp :: Integer -> Integer -> Integer -> Integer
modexp m e n | e==0      = 1
             | odd e     = modexp m (e-1) n * m `mod` n
             | otherwise = modexp m (e `div` 2) n ^ 2 `mod` n

 

 

Weiter mit:   [Modulare Exponentiation iterativ]   [Primzahltest]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 12.06.2001   Updated: 11.06.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik