Ferienübung F2 Euklid
Moderator: Einführung in die Kryptographie
-
- Mausschubser
- Beiträge: 99
- Registriert: 4. Okt 2010 16:25
Ferienübung F2 Euklid
Moin,
ich bekomme einen negativen Vorfaktor x für mein M, dabei heißt es in der Aufgabenstellung, dass \(0 \leq x \lt 2027\) sein soll. Das Ergebnis habe ich per Computer bestätigt, ist also kein Rechenfehler.
Bin verwirrt. Geht das noch anderen so?
ich bekomme einen negativen Vorfaktor x für mein M, dabei heißt es in der Aufgabenstellung, dass \(0 \leq x \lt 2027\) sein soll. Das Ergebnis habe ich per Computer bestätigt, ist also kein Rechenfehler.
Bin verwirrt. Geht das noch anderen so?
Re: Ferienübung F2 Euklid
Euklid ist symmetrisch, also kannst du die Werte für x und y einfach vertauschen.
Tutor:
Mathe II Inf (SS12)
Mathe I Inf (WS11/12)
Mathe II Inf (SS12)
Mathe I Inf (WS11/12)
-
- Mausschubser
- Beiträge: 99
- Registriert: 4. Okt 2010 16:25
Re: Ferienübung F2 Euklid
Ähm… nein. Beispiel: ggt(2027,560) = 1 mit 163*2027-590*560=1. Soweit gut. Wenn ich jetzt x und y vertausche, steht da: -590*2027+163*560=-1104650. Wenn ich nur die Vorzeichen vertausche, kommt hinten -1 raus.
Die einzige Symmetrie beim Euklid, die ich kenne, ist dass man die Parameter in beliebiger Reihenfolge angeben kann und immer das gleiche Ergebnis kriegt.
Die einzige Symmetrie beim Euklid, die ich kenne, ist dass man die Parameter in beliebiger Reihenfolge angeben kann und immer das gleiche Ergebnis kriegt.
Re: Ferienübung F2 Euklid
Das ist die Symmetrie, die ich meine. Du sollst also nur die Bezeichner x,y vertauschen.arne.lottmann hat geschrieben:Ähm… nein. Beispiel: ggt(2027,560) = 1 mit 163*2027-590*560=1. Soweit gut. Wenn ich jetzt x und y vertausche, steht da: -590*2027+163*560=-1104650. Wenn ich nur die Vorzeichen vertausche, kommt hinten -1 raus.
Die einzige Symmetrie beim Euklid, die ich kenne, ist dass man die Parameter in beliebiger Reihenfolge angeben kann und immer das gleiche Ergebnis kriegt.
Tutor:
Mathe II Inf (SS12)
Mathe I Inf (WS11/12)
Mathe II Inf (SS12)
Mathe I Inf (WS11/12)
Re: Ferienübung F2 Euklid
[...nervöser Zeigefinger
]...

Tutor:
Mathe II Inf (SS12)
Mathe I Inf (WS11/12)
Mathe II Inf (SS12)
Mathe I Inf (WS11/12)
-
- Mausschubser
- Beiträge: 99
- Registriert: 4. Okt 2010 16:25
Re: Ferienübung F2 Euklid
Das ändert nichts an der Tatsache, dass der Vorfaktor von M negativ ist, egal wie ich ihn nenne.
Re: Ferienübung F2 Euklid
Ich sehe das genauso wie Arne. In der Aufgabenstellung ist fest das x der Vorfaktor von M ist und das x nicht kleiner 0 sein darf. Wenn man nun als Lösung 163*2027-590*560 angibt ist das x meiner Meinung nach immer noch die Variable vor dem M also die -590 ...
Andererseits kenne ich keine andere Umstellungsart im Euklid also vielleicht ist das wirklich die Lösung die sich die Veranstalter gedacht haben.
Andererseits kenne ich keine andere Umstellungsart im Euklid also vielleicht ist das wirklich die Lösung die sich die Veranstalter gedacht haben.
Re: Ferienübung F2 Euklid
Ich hatte das gleiche Problem, hab ein bisschen rumprobiert und bin auf folgendes gestoßen:
((-590)+2027)*560 + (163-560)*2027 = 1
somit ist x = -590 + 2027 = 1437
und y = 163 - 560 = -397
((-590)+2027)*560 + (163-560)*2027 = 1
somit ist x = -590 + 2027 = 1437
und y = 163 - 560 = -397
-
- Mausschubser
- Beiträge: 99
- Registriert: 4. Okt 2010 16:25
Re: Ferienübung F2 Euklid
Genial
. Kann man auch mathematisch fundieren, für alle die es interessiert:
Man hat: \(M \cdot x + N \cdot y = 1\)
Vorgeschlagen ist: \((x + N) \cdot M + (y - M) \cdot N = 1\)
Umformen gibt: \((x + N) \cdot M + (y - M) \cdot N = x \cdot M + N \cdot M + y \cdot N - M \cdot N = x \cdot M + y \cdot N = 1\).
Danke, mir
.

Man hat: \(M \cdot x + N \cdot y = 1\)
Vorgeschlagen ist: \((x + N) \cdot M + (y - M) \cdot N = 1\)
Umformen gibt: \((x + N) \cdot M + (y - M) \cdot N = x \cdot M + N \cdot M + y \cdot N - M \cdot N = x \cdot M + y \cdot N = 1\).
Danke, mir

Re: Ferienübung F2 Euklid
Hallo,
bei meinen Berechnugen ist ein positiver Faktor vor dem M und was ich gerne wissen würde, ist, wie ich jetzt das Lösungswort bestimmen kann. Binärdarstellung ist klar, aber soll ich x und y verknüpfen oder sollen es zwei Lösungswörter sein?
Da mein y negativ ist, muss ich y mit M addieren und dann in Binärdarstellung bringen?
Greetz
McLovin
bei meinen Berechnugen ist ein positiver Faktor vor dem M und was ich gerne wissen würde, ist, wie ich jetzt das Lösungswort bestimmen kann. Binärdarstellung ist klar, aber soll ich x und y verknüpfen oder sollen es zwei Lösungswörter sein?
Da mein y negativ ist, muss ich y mit M addieren und dann in Binärdarstellung bringen?
Greetz
McLovin
Re: Ferienübung F2 Euklid
Du nimmst einfach dein x, machst ein Komma, und setzt dein y hintendran. Mit allen Vorzeichen und nicht binär