Station - Modulare Multiplikation

Multiplikation modulo einer vorgegebenen Zahl

Die Multiplikation modulo einer vorgegebenen Zahl wird analog zur Addition durchgeführt.

Vorgegeben sei eine natürliche Zahl n. Zwei natürliche Zahlen a und b werden modulo n multipliziert, indem man sie multipliziert und anschließend vom Produkt den Rest bei der Division durch n berechnet. Das Ergebnis ist also [a*b]%n. Beachte, dass das Ergebnis bei der Multiplikation modulo n immer eine Zahl kleiner als n ist.

Auch die Multiplikation modulo n lässt sich gut mit einer Verknüpfungstafel verdeutlichen. Im folgenden Beispiel ist n = 5 gewählt.

Aufgabe 1

Rechengesetze für die Multiplikation modulo n

Für die Multiplikation modulo n gelten eine Reihe von Rechengesetze wie z.B. das Kommutativ- und das Assoziativgesetz. Wir benötigen zusätzlich die beiden folgenden Rechengesetze:

Modulare Gleichheit bei der Multiplikation

Aus [a1]%n = [a2]%n und [b1]%n = [b2]%n folgt [a1*b1]%n = [a2*b2]%n.

Das erste Rechengesetz besagt, dass Zahlen, die modulo n gleich sind, auch zu gleichen Multiplikationsergebnissen modulo n führen.

Multiplikation und iterierte Modulberechnung

[a*b]%n = [[a]%n * [b]%n]%n

Das zweite Rechengesetz erlaubt es, bei der Multiplikation modulo n zuerst die Faktoren zu verkleinern und dann erst die Multiplikation durchzuführen.

Aufgabe 2

>>> n = 14
>>> a1 = 16
>>> b1 = 19
>>> a2 = 44
>>> b2 = 75
>>> a1%n
2
>>> a2%n
2
>>> b1%n
5
>>> b2%n
5
>>> (a1*b1)%n
...

        ⨉
        
Projekt veröffentlichen
        

        
      
      
Quelltext in die Zwischenablage kopieren Historie einblenden
n = 14
a1 = 16
a2 = 19
b1 = 44
b2 = 75
    
print(a1%n)
xxxxxxxxxx
 
1
n = 14
2
a1 = 16
3
a2 = 19
4
b1 = 44
5
b2 = 75
6
    
7
print(a1%n)
Ausgabe

Das modulare Inverse

Beim Umkehren von Rechenoperationen spielen sogenannte Inverse eine zentrale Rolle. So ist -4 das Inverse von +4 bzgl. der üblichen Addition bei ganzen Zahlen. Ebenso ist 1/2 das Inverse von 2 bzgl. der üblichen Multiplikation bei rationalen Zahlen.

Beim RSA-Verfahren spielt das Inverse bei der modularen Multiplikation eine wichtige Rolle. Dieses Inverse wird auch modulares Inverse genannt.

Zwei natürliche Zahlen a und b heißen modular invers zueinander bezüglich n genau dann, wenn gilt: [a*b]%n = 1.

Beispiel: Es gilt [2*3]%5 = 1. Die beiden Zahlen 2 und 3 sind also modular invers zueinander bzgl. 5. Die Zahl 2 ist das modulare Inverse von 3 bzgl. des Moduls 5. Ebenso ist 3 das modulare Inverse von 2 bzgl. des Moduls 5.

Aufgabe 3

Satz (über die Existenz des modularen Inversen)

Gegeben sei eine natürliche Zahl n. Das modulare Inverse bezüglich n zu einer Zahl a ungleich Null existiert genau dann, wenn a und n keinen gemeinsamen Teiler größer als 1 haben - d.h., wenn ggT(a, n) = 1 gilt.

Den allgemeinen Beweis dieser Aussage findest du im späteren Abschnitt Station - Berechnung der modularen Inversen. Dort wird erklärt, wie die modulare Inverse mithilfe des erweiterten euklidischen Algorithmus berechnet werden kann.

Aufgabe 4