Cryptography Reference
In-Depth Information
Das Diagramm zeigt auch, dass das Ergebnis in dem Intervall [0, n]=[0, 20] einzig ist. Das
Schema der Pfeile wiederholt sich mit der Periode n=p·q=3·7=21. Ein nächstes Ergebnis
x'=11+21=32 fällt bereits aus dem Intervall der Restklassen [0, 20] heraus.
Mit dem Chinesischen Restsatz ergibt die Berechnung von x das erwartete Ergebnis:
ggT(p, q)
ggT(3, 7)
!
1
2 3
1 7
,
mit
6,
!
7
x
!
(b
a
) mod n
(4 ( 6)
2 7) mod 21
10 mod 21
11
Wenn der Chinesische Restsatz mit dem gleichen Modul n=p·q immer wieder angewendet
wird, dann braucht und nur einmal berechnet und abgespeichert zu werden.
4.1.7
Übungen
Übung 1
Bestimmen Sie in der Arithmetik modulo p (p=65537=2
16
+1=prim) zu dem Element a=504 das
multiplikativ inverse Element a
1
. Wenden Sie dazu den Kleinen Satz von Fermat an. Keine
Zahlenrechnung.
Lösung
Für eine Primzahl p gilt: 1=(a
p1
)mod p bzw. a
1
=(a
p-2
)mod p.
Somit 504
1
=
(504
65535
)mod65537
.
Übung 2
Berechnen Sie 27
348782
in der Arithmetik modulo n, wobei n=7·11=77 ist. Machen Sie davon
Gebrauch, dass die Potenzen periodisch sind.
Lösung
Die Periode im Exponenten ist (7·11)=6·10=60. Der Exponent mod60 ist
(348782)mod 60=2. Das Ergebnis ist (27
2
)mod 77=
36
.
Übung 3
Berechnen Sie 27
41
in der Arithmetik modulo 77.
Lösung
Der Exponent lautet als Dualzahl 101001. Das ergibt die Rechenfolge: Q (Q M) Q Q (Q M)
und im speziellen Fall: 27-Q36-Q64-M34-Q1-Q1-Q1-M
27
.
Übung 4
Berechnen Sie die Wurzel von 71 in der Arithmetik modulo n, wobei n=7·11=77 ist. Wie viele
Wurzeln gibt es?
Berechnen Sie diese Wurzeln. Verwenden Sie dazu den Chinesischen Restsatz.
Lösung
Aus (71)mod 77 folgt (711)mod 7 und (715)mod 11.
Test auf Quadratzahlen mit Jacobi-Funktion (4.1-20) für die Teilmoduln 1mod7 und 5mod11:
