Ferienübung F2 Euklid

Moderator: Einführung in die Kryptographie

arne.lottmann
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Okt 2010 16:25

Ferienübung F2 Euklid

Beitrag von arne.lottmann » 3. Jan 2013 17:51

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?

Benutzeravatar
DB_420
Mausschubser
Mausschubser
Beiträge: 89
Registriert: 24. Nov 2010 15:12

Re: Ferienübung F2 Euklid

Beitrag von DB_420 » 3. Jan 2013 18:28

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)

arne.lottmann
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Okt 2010 16:25

Re: Ferienübung F2 Euklid

Beitrag von arne.lottmann » 3. Jan 2013 18:38

Ä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.

Benutzeravatar
DB_420
Mausschubser
Mausschubser
Beiträge: 89
Registriert: 24. Nov 2010 15:12

Re: Ferienübung F2 Euklid

Beitrag von DB_420 » 3. Jan 2013 20:53

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.
Das ist die Symmetrie, die ich meine. Du sollst also nur die Bezeichner x,y vertauschen.
Tutor:
Mathe II Inf (SS12)
Mathe I Inf (WS11/12)

Benutzeravatar
DB_420
Mausschubser
Mausschubser
Beiträge: 89
Registriert: 24. Nov 2010 15:12

Re: Ferienübung F2 Euklid

Beitrag von DB_420 » 3. Jan 2013 20:53

[...nervöser Zeigefinger ;)]...
Tutor:
Mathe II Inf (SS12)
Mathe I Inf (WS11/12)

arne.lottmann
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Okt 2010 16:25

Re: Ferienübung F2 Euklid

Beitrag von arne.lottmann » 4. Jan 2013 07:35

Das ändert nichts an der Tatsache, dass der Vorfaktor von M negativ ist, egal wie ich ihn nenne.

Benutzeravatar
Natchen
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 11. Okt 2008 23:15

Re: Ferienübung F2 Euklid

Beitrag von Natchen » 4. Jan 2013 15:15

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.

mir
Neuling
Neuling
Beiträge: 5
Registriert: 27. Okt 2012 18:00

Re: Ferienübung F2 Euklid

Beitrag von mir » 4. Jan 2013 16:02

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

arne.lottmann
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Okt 2010 16:25

Re: Ferienübung F2 Euklid

Beitrag von arne.lottmann » 4. Jan 2013 16:10

Genial :P. 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 :).

Benutzeravatar
McLovin
Neuling
Neuling
Beiträge: 10
Registriert: 26. Sep 2010 23:43
Wohnort: Mainz

Re: Ferienübung F2 Euklid

Beitrag von McLovin » 14. Jan 2013 00:59

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

Tobio
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 4. Okt 2010 15:47

Re: Ferienübung F2 Euklid

Beitrag von Tobio » 14. Jan 2013 06:51

Du nimmst einfach dein x, machst ein Komma, und setzt dein y hintendran. Mit allen Vorzeichen und nicht binär

Antworten

Zurück zu „Einführung in die Kryptographie“