Punkt auf elliptischer Kurve verdoppeln [Fehler finden]

01.06.2018, 22:05

Klingone

Punkt auf elliptischer Kurve verdoppeln [Fehler finden]

Hallo,
ich möchte einen Punkt auf einer elliptischen Kurve verdoppeln. Ich weiß eigentlich was ich machen muss, finde allerdings meinen Fehler nicht.

Es handelt sich um diese el. Kurve:
$\begin{eqnarray*} y^{3} = x^{3} + 7x + 1 \end{eqnarray*}$ F101

der Punkt (0,1) soll verdoppelt werden.

diese hat die Form
$\begin{eqnarray*} y^{2} = x^{3} + ax + b \end{eqnarray*}$

Also nehme ich folgende Formel

$\begin{eqnarray*} m\equiv (3x1 - a)(2y1)^{-1}mod p <br /> \end{eqnarray*}$

$\begin{eqnarray*} m\equiv (3\cdot 0 - 7)(2\cdot 1)^{-1}mod 101 \equiv -7 \cdot 2^{-1} mod 101 \end{eqnarray*}$

Euklid
$\begin{eqnarray*} 101 = 50\cdot2 +1<br /> 2 = 2\cdot1 +0 <br /> \end{eqnarray*}$

Erweiterter Euklid
ergibt 1 (a) und -2 (b)

Also -> $\begin{eqnarray*} 1\cdot101 + (-2)\cdot50 =1 \end{eqnarray*}$

Nun würde das heißen:
$\begin{eqnarray*} 2^{-1} \equiv -2 mod 101 \end{eqnarray*}$

Und das stimmt nicht...Ich weiß dass ich noch nicht fertig bin, aber ich habe hier abgebrochen wegen dem Fehler.

Wo liegt mein Fehler, was mache ich falsch? Ich finde es einfach nicht...

01.06.2018, 23:25

tatmas

Auf diesen Beitrag antworten »

Hallo,

Zitat:

Nun würde das heißen: 2−1≡−2mod101

Nein würde es ist nicht.
Es ist $\begin{eqnarray*} 2 \cdot -2 =-4 \neq 1 \mod 101 \end{eqnarray*}$ .
Wie kommst du darauf dass das gelten soll?

P.S. Das ist keine Analysis

01.06.2018, 23:39

Klingone

Auf diesen Beitrag antworten »

Zitat:

Original von tatmas
Wie kommst du darauf dass das gelten soll?

Bei einer ähnlichen Aufgabe hat man bei $\begin{eqnarray*} 94\cdot 88^{-1} mod 101 \end{eqnarray*}$ auch einfach den erweiterten Euklid angewandt und die Linearkombination bestimmt. Da erhielt man zum Schluß $\begin{eqnarray*} -27\cdot 101 + 31\cdot 88 \end{eqnarray*}$ darauf folgte $\begin{eqnarray*} 88^{-1}\equiv 31 mod 101 \end{eqnarray*}$

Ich hab also den Linearfaktor der beim erweiterten Euklid für die $\begin{eqnarray*} 2^{-1} \end{eqnarray*}$ rauskommt genommen und dass dann mod 101 gesetzt. Das scheint aber nicht zu klappen, siehe oben.

Wie muss man hier vorgehen? Wo ist mein Fehler?

01.06.2018, 23:47

tatmas

Auf diesen Beitrag antworten »

Du liest die falsche Zahl aus dem euklidischen Algorithmus raus.
Schau bei deinem Beispiel nochmal genau hin welche Zahl das Inverse ist.

02.06.2018, 00:01

Klingone

Auf diesen Beitrag antworten »

Den erweiterten Euklid habe ich nicht mit Latex nachgebaut, da es zu kompliziert ist. Daher habe ich hier mal meine Rechnung eingescannt. Das Inverse ist in meinen Augen, laut meiner Rechnung -2. Was aber nicht sein kann. Kann aber auch sein, dass ich einfach schon Matsch in der Birne bin weil es in meinem Zimmer 30°C hat und ich schon den ganzen Tag lerne...

https://www1.xup.in/exec/ximg.php?fid=40093631

02.06.2018, 00:09

tatmas

Auf diesen Beitrag antworten »

Das richtige Inverse ist -50.
Deine Rechnung ist richtig. Du liest nur die falsche Zahl ab.

Schreib mal die Ergebnisse der zwei euklidischen Algorithmen übereinander, markier die Zahlen farbig.
Vielleicht siehst du dann welche Zahl du nehmen sollst.

02.06.2018, 00:23

Klingone

Auf diesen Beitrag antworten »

Ich verstehe ehrlich gesagt nicht, wie du da auf -50 kommst. Ich habe seither immer nur den passenden Linear(vor)faktor genommen.

So wie hier in dieser Rechnung, dort sollte man 2 Punkte addiert, aber das ist ja Wurst. Hier passt es ja auch, wenn ich es so mache.

https://www1.xup.in/exec/ximg.php?fid=59125965

Was soll hier anders sein? Wieso funktioniert das hier in dieser Rechnung, in meiner vorherigen aber nicht? (Ist übrigens die gleiche el. Kurve).
Ich schnapp mir doch auch nur die Ergebnisse des erw. Euklid für x und y und hänge diese vor a und b.

02.06.2018, 00:30

tatmas

Auf diesen Beitrag antworten »

Zitat:

Ich habe seither immer nur den passenden Linear(vor)faktor genommen.

Das machst du hier halt genau nicht.
Das Problem ist nicht die Rechnung, sondern dass du den falschen Wert abliest.

Du hast im Schluss die Form:
irgendwas * p + zu unvertierende Zahl * gesuchte Zahl =1.

Und da musst du halt gesuchte Zahl nehmen, nicht zu invertierende Zahl.

P.S: Dein Problem hier hat nichts mit elliptischen Kurven zu tun. Dein Problem liegt in der modulo Rechnung.
Und die ist absolute Grundlage für jedwedes Rechnen über endlichen Körpern.

02.06.2018, 00:39

Klingone

Auf diesen Beitrag antworten »

Ich bekomme beim erw. Euklid für x=1 und y=-2 raus

Setze ich das ein, kommt ja auch 1 raus :
1*101 - 2*50 = 1

Genau so wie in beiden Rechnungen auch, scheint also zu stimmen. Ich habe beide Blätter neben mir liegen, ich sehe absolut keinen Unterschied in der Vorgehensweise, nur dass es andere Zahlen sind.

Mir ist es ein Rästel wie ich da auf -50 kommen soll. Dann müsste ich ja die 50 z.B mit -1 multiplizieren. Nur bei mir kommt nirgendwo -1 raus.

Kannst du bitte die Zeile mit der Rechnung schreiben, wie du auf die -50 mit meinen Werten aus der Rechnung kommst?

Fehler gefunden!!!

Ich hab den Fehler gefunden Hammer

. In meiner Rechnung ist doch ein Fehler drin, und zwar beim erweiterten Euklid in der Tabelle. Ich habe die Werte b und q vertauscht, weil ich es zuvor im Euklid "falsch rum" aufgeschrieben habe. Normalerweise schreibe ich immer erst den Divisor und dann den Multiplikator hin, hier hatte ich es verdreht. Passt man hier nicht auf, überträgt man es falsch in die Tabelle und man kommt auf andere Werte.

Nun komme ich auf -50 weil 0-1*50 = -50

Somit komme ich auf
1*101+ (-50)*2 = 1

Ich fühle mich gerade richtig dumm, ich saß 4 Stunden an dem Mist.

Vielen Dank für deine Hilfe

02.06.2018, 00:52

tatmas

Auf diesen Beitrag antworten »

Zitat:

Genau so wie in beiden Rechnungen auch

Ja, das hab ich doch schon mehrfach gesagt: Die Rechnung stimmt. Das ist nicht das Thema.

Zitat:

Kannst du bitte die Zeile mit der Rechnung schreiben, wie du auf die -50 mit meinen Werten aus der Rechnung kommst?

Das habe ich doch bereits getan.

Du brauchst die Form

Zitat:

irgendwas * p + zu unvertierende Zahl * gesuchte Zahl =1.

Du hast

Zitat:

1*101 - 2*50 = 1

bring das auf die Form, fertig.
Dazu musst du die -1 mit der 50 multiplizieren.
also:
1*101 + 2*(-50) = 1

02.06.2018, 00:53

Klingone

Auf diesen Beitrag antworten »

Ich habs zur selben Sekunde wie dein Post gerade editiert Freude

. Wäre ich ein Vulkanier, wäre mir ein solcher Fehler natürlich nicht passiert.

02.06.2018, 02:11

Klingone

Auf diesen Beitrag antworten »

Ich habe jetzt mit der Inversen -50 weiter gerechnet. Also mein m berechnet und dann x3 und y3. Ich erhalte dann auch einen Punkt raus. Allerdings liegt dieser wenn ich einen Check mache und die Werte für ihn einsetze, nicht auf der elliptischen Kurve. Also muss da noch irgendwo ein Fehler sein. Aber eigentlich hab ich alles richtig eingesetzt. Das schwierigste ist normal ja immer nur das m zu berechnen.

Ich habe hier alles aufgeschrieben:

https://www1.xup.in/exec/ximg.php?fid=86440864

02.06.2018, 16:49

tatmas

Auf diesen Beitrag antworten »

Deine Formel für m ist falsch.
Es ist +a nicht -a.

02.06.2018, 17:03

Klingone

Auf diesen Beitrag antworten »

Da kann ich ja lange suchen, im Skript vom Professor steht die Formel mit einem Minus drin. Das erklärt auch warum mein x3 immer richtig war, weil das Minus durch das quadrieren von m keine Rolle spielt. Bei y3 kams dann aber zum Fehler. Mit +a kommt ein plausibles Ergebnis raus und der Punkt liegt auch auf der el. Kurve.

Ich habe hier sogar einen Aufschrieb, bei dem wir es in der Vorlesung auch mit Minus gerechnet haben Hammer

.

Vielen Dank, du hast mir sehr geholfen!

Neue Frage »

Antworten »

Punkt auf elliptischer Kurve verdoppeln [Fehler finden]

Verwandte Themen