EuklidAlgorithmus

Verwendung dieser Mathematica-Datei:

(Nehmen Sie bei schlechter Darstellung einen anderen Browswer)

Bestimmung des Größten gemeinsamen Teilers ggt(a,b) von a und b
Bestimmung der Vielfachsummendarstellung VSD mit dem erweiterten Euklidischen Algorithmus: mit a=20 und b=7 ergibt sich 1=-1 mal 20 + 3 mal 7.
Das ist im Buch in 2.3.6 vorgerechnet.
Zur Bestimmumg des modularen Inverse von 7 im Modul Z₂₀ kann man die VSD verwenden, indem man die VSD in mem Modul Z₂₀ liest. Dann fallen die 20er Vielfachen weg und es bleibt 1=3 mal 7. Probe: 3 mal 7=21=1 modulo 20. Das ist im Buch von Hand vorgerechnet.
Die Ergebnisse werden von Mathematica erzeugt, funktionieren also auch für sehr große Zahlen in kryptografischer Größenordnung.