| Autor |
 Modulo |
|
questionmark
Junior 
Dabei seit: 24.01.2005
Mitteilungen: 10
 |  Themenstart: 2008-01-06
|
Hallo.
Ich habe in einer Prüfungsaufgabe, die sich um die Hill-Chiffrierung dreht, einen Schritt in der Lösung gefunden, den ich nicht nachvollziehen kann. und zwar folgendes:
x = (23)^-1 mod 26
x = 17
wie kommt man von der 23 hoch -1 modulo 26 auf die 17?? bei einer aufgabe mit der selben aufgabenstellung, aber anderen werten das selbe spiel:
x = (19)^-1 mod 26
x = 11
kann mir jemand diesen schritt erklären? wie kommt man auf diese zahl?
vielen dank.
|
 Profil
|
Luke
Senior 
Dabei seit: 19.10.2006
Mitteilungen: 5501
 |  Beitrag No.1, eingetragen 2008-01-06
|
hallo:
\
x = 23^(-1) mod 26
x = 17
das gilt, weil:
17 * 23 mod 26 = 1
[ Nachricht wurde editiert von Luke am 06.01.2008 14:06:31 ]
|
Profil
|
questionmark
Junior
Dabei seit: 24.01.2005
Mitteilungen: 10
| Beitrag No.2, vom Themenstarter, eingetragen 2008-01-06
|
danke für die schnelle antwort. aber wie komme ich dann auf die 17? also wie sie zustande kommt, hab ich jetzt verstanden, aber wie errechne ich sie?
|
Profil
|
acm5
Ehemals Aktiv
Dabei seit: 11.05.2004
Mitteilungen: 461
 | Beitrag No.3, eingetragen 2008-01-06
|
seasund das ist so, weil wir befinden uns ja im
\IZ_26
a * a^(-1) = 1
23 \el\ \IZ_26
=> a^(-1) = 1/23 \el\ \IZ_26
edit:
war wohl falsch... hab falsch gedacht, sry... weiter unten gehts weiter: @gockel...
lg daneli
[ Nachricht wurde editiert von acm5 am 06.01.2008 15:16:41 ]
|
Profil
|
questionmark
Junior
Dabei seit: 24.01.2005
Mitteilungen: 10
| Beitrag No.4, vom Themenstarter, eingetragen 2008-01-06
|
also auf gleichen nenner bringen:
x = 1/23 - k * 26 * 23/23
x = 1/23 - k * 598/23
und dann? hatte mir das einfacher vorgestellt;)
|
Profil
|
Luke
Senior
Dabei seit: 19.10.2006
Mitteilungen: 5501
| Beitrag No.5, eingetragen 2008-01-06
|
hallo, wieso ist Z_26 ein körper?
man kann nachrechnen dass nur die ungeraden zahlen ausser 13 ein inverses haben (genau eins, der rest hat 0 inverse).
Z_26 ist also entgegen acm5s behauptungen KEIN koerper.
[ Nachricht wurde editiert von Luke am 06.01.2008 15:14:49 ]
|
Profil
|
Gockel
Senior 
Dabei seit: 22.12.2003
Mitteilungen: 25548
Wohnort: Jena
 | Beitrag No.6, eingetragen 2008-01-06
|
Um es mal klarzustellen: \IZ_26 ist kein__ Körper und selbst in Körpern hat längst nicht jedes Element ein Inverses!
23 ist deshalb invertierbar, weil ggT(23,26)=1 ist.
Was man sucht, ist eine Zahl s, sodass 23*s==1 (mod 26) ist, d.h. 23*s-1=k*26, d.h. (23*s-1)/26=k.
Man kann jetzt also s=1,2,3,... durchlaufen lassen, bis dieser Bruch ganzzahlig wird und hat dann das Inverse gefunden.
Die deutlich effizientere Methode ist aber der erweiterte euklidische Algorithmus.
mfg Gockel.
|
Profil
|
acm5
Ehemals Aktiv
Dabei seit: 11.05.2004
Mitteilungen: 461
| Beitrag No.7, eingetragen 2008-01-06
|
harr, stimmt, ist kein körper, kopfschüttel, hatte andere aufgabe im kopf...
lg daniel, aber wo liegt trotdem der fehler im inversen-suchen?
[Die Antwort wurde nach Beitrag No.5 begonnen.]
|
Profil
|
questionmark
Junior
Dabei seit: 24.01.2005
Mitteilungen: 10
| Beitrag No.8, vom Themenstarter, eingetragen 2008-01-06
|
und wie funktioniert das über den erweiterten euklidischen Algorithmus?
|
Profil
|
Gockel
Senior 
Dabei seit: 22.12.2003
Mitteilungen: 25548
Wohnort: Jena
| Beitrag No.9, eingetragen 2008-01-06
|
@acm5:
Es fängt schon damit an, dass du mit dem Bruch 1/23 rechnest. Es geht hier nur um ganze Zahlen.
@Fragezeichen:
google ist dein Freund. Und Wikipedia auch. Und die Forensuche auch.
mfg Gockel.
|
Profil
|
Luke
Senior
Dabei seit: 19.10.2006
Mitteilungen: 5501
| Beitrag No.10, eingetragen 2008-01-06
|
\quoteon(2008-01-06 15:13 - acm5)
harr, stimmt, ist kein körper, kopfschüttel, hatte andere aufgabe im kopf...
lg daniel, aber wo liegt trotdem der fehler im inversen-suchen?
\quoteoff
auch in anderen aufgabe ist es kein koerper. ;)
|
Profil
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
