Euklidischer Algorithmus, Asymmetrische Verschlüsselung: 1=(47*d) mod 60 nach d auflösen.

Question

Meine Frage:
Hallo,
ich bin erst in der 10ten Klasse brauch für mein Referat aber die Asymetrische Verschlüsselung. Meine Kenntnisse hören nun
bei dem Euklidischer Algorithmus auf. Kann mir jemand sagen wie ich nun mit dem Euklidischer Algorithmus und modulo meiner Info nach der Rest anteil einer Rechnung folgende Rechnung löse:

1=(47*d)mod60

Comments

Nützt dir die Rechnung hier schon etwas?

https://www.mathelounge.de/99231/euklidischen-algorithmus-inverse

Answer 1

Inverser Euklidischer Algorithmus

60 : 47 = 1 R 13	1 = 5*47 - 18*(60 - 1*47) = 23*47 - 18*60
47 : 13 = 3 R 8	1 = 5*(47 - 3*13) - 3*13 = 5*47 - 18*13
13 : 8 = 1 R 5	1 = 2*8 - 3*(13 - 1*8) = 5*8 - 3*13
8 : 5 = 1 R 3	1 = 2*(8 - 1*5) - 1*5 = 2*8 - 3*5
5 : 3 = 1 R 2	1 = 3 - 1*(5 - 1*3) = 2*3 - 1*5
3 : 2 = 1 R 1	1 = 3 - 1*2
2 : 1 = 2 R 0

47 * 23 MOD 60 = 1