Cryptography Reference
In-Depth Information
ggT(n, a)
1
für
n
a
0,
n, a
¢
(2.1-13)
Der ggT lässt sich, wie bald zu sehen, durch eine Linearkombination von n und a darstellen.
ggT
!
1
n
a
mit
a, n,
!
,
¢
(2.1-14)
Wenn wir modulo n auf (2.1-14) anwenden, dann wird der Term ·n zu Null und wir erhalten
als das multiplikativ inverse Element.
1
1
!
a (mod n)
und damit
a
!
( ) mod n
(2.1-15)
Mit Hilfe des Euklidischen Algorithmus können wir nicht nur den größten gemeinsamen Teiler
ggT ermitteln, sondern auch die Werte von und in (2.1-14).
Der Euklidische Algorithmus gibt eine Ersetzung von ggT(n, a) an.
ggT(n, a)
wobei
n
a
0,
n, a
¢
(2.1-16)
ggT(a, (n) mod a)
für
a
0
n
für
a
0
Für ein Beispiel mit n=72 und a=5 wollen wir zunächst prüfen, ob ggT=1 ist, und anschließend
das multiplikativ inverse Element a 1 zu a=5 modulo n ermitteln. Es ergeben sich folgende
Ersetzungsschritte:
ggT(72, 5)
72
"#
ggT(5, 2)
wobei
2
72 mod 5
72
5
"#
5
5
$%
(2.1-17)
"#
ggT(2, 1)
wobei
1
5 mod 2
5
2
"#
2
$%
ggT(1, 0)
1
Links in (2.1-17) stehen die Ersetzungen entsprechend dem Euklidischen Algorithmus. Beim
ersten Ersetzungsschritt wandert die 5 nach links, und nach rechts kommt 72mod5=2. Nach
drei Schritten ist der Algorithmus mit ggT(1, 0) = 1 beendet. Rechts in (2.1-17) ist als Erweite-
rung des Algorithmus angegeben, wie der Rest (z.B. 2) sich aus den Operanden (z.B. 72, 5)
der vorherigen Zeile ergibt. Dabei bedeuten die „nach unten eckigen Klammern“ „das Ganze
von“ (das Ganze z.B. von (72/5) ist 14).
Die 1 (rechts unten in (2.1-17)) wird dargestellt als Linearkombination LK(5, 2) von 5 und 2.
Die 2 kann mittels der Zeile darüber ersetzt werden als LK(72, 5). Damit ist auch ggT=1 dar-
stellbar als LK(72, 5). Wir erhalten für das Beispiel:
152252(72145) 5272285
272 295
(2.1-18)
Wir erhalten aus (2.1-18) das in modulo 72 multiplikativ inverse Element zu a=5 als a 1 ==29.
Falls der Wert für negativ gewesen wäre, dann müsste entsprechend (2.1-15) noch eine Rest-
bildung a 1 =()mod n durchgeführt werden.
Search WWH ::




Custom Search