Elliptische Kurve brechnung der Gruppen

[aSHtRAY]

Moin Moin,

ich habe ein arges Problem mit den elliptischen Kurven und zwar habe ich keine Ahnung wie ich da die Gruppen berechnen soll.

Es gilt ja

y^2=x^3 + ax + b

nun geben wir ein a und ein b

und irgend wie zauberhaft werden dann Gruppen erzeugt mit zwei zahlenpaaren (x1,y2), wobei dort zu einem x1 aufeinmal mehrere y2 auftauchen können.

Aus einem PDF von einer Abschlussarbeit von jemanden habe ich z.B. dies hier:

_zahl = die zahl danach ist untergestezt, so wie ein Index

E = elliptische Kurve

E(F_zahl) = elliptische Kurve über den Körper F_zahl

Es sei E(F_23)=x^3+3x+22 eine elliptische Kurve über den Primkörper F_23. Sie hat 33 Punkte: (1,16),(1,7), ....

Wieso hat 1 16 und 7 ????

Ich krieg ne Kriese ... es ist einfach viel zu heiß

Please, help me doctor Sayas!!

Danke schon einmal und schüss.

[flashpixx]

ich habe ein arges Problem mit den elliptischen Kurven und zwar habe ich keine Ahnung wie ich da die Gruppen berechnen soll

Um welche Art von Gruppen und Körpern reden wir?

Körper (Algebra) ? Wikipedia

Gruppentheorie ? Wikipedia

Was haben Kurven mit Gruppen zu tun? Im Moment fehlt mir hier der Zusammenhang.

Es gilt ja

y^2=x^3 + ax + b

nun geben wir ein a und ein b

und irgend wie zauberhaft werden dann Gruppen erzeugt mit zwei zahlenpaaren (x1,y2), wobei dort zu einem x1 aufeinmal mehrere y2 auftauchen können.

Poste doch die originale Aufgabenstellung, damit man auch versteht was gemacht werden soll und außerdem solltest Du das Problem eingrenzen, so dass man wenigstens einen Anhaltspunkt hat, in welchen Bereich der Mathematik man nach einer Lösung suchen kann.

[aSHtRAY]

Kurz:

Es gibt verschiedenen Gruppen die verschieden viele Punkte auf der elliptischen Kurve haben. (Hier liegt auch so ziemlich mein Problem.)

Lang und wohl eher das nachdem was du fragst:

http://www.cs.uni-potsdam.de/ti/lehre/09-Kryptographie/slides/Baum_Publickey2.pdf

[aSHtRAY]

Oh hier ist was besseres

http://www.uni-ulm.de/~s_sfackl/ss09/PunkteZaehlenaufElliptischenKurven.pdf

Unter Punkt 2.1 ist die Beschreibung der Gruppe kurz und knapp.

Und weiter unten unter dem Punkt 2.4 ist auch noch der Baby-Step erklärt, mit dem wir die größte Gruppe bestimmen.

Also die größte Anzahl von Punkten auf der elliptischen Kurve.

-------------------------------------------

Ich habe jetzt gut und gerne 3 Tage darüber nachgedacht wieso zu verschiedenen x mehrere y gibt... ich muss das wirklich auf die hitze schieben, die mich fertig macht und durch die ich nicht richtig denken kann ... es ist verdamt nochmal eine elliptische Kurve ... natürlich gibt es da mehrere Zahlenpaare.

Oh man, wie gut das es im Moment kühler ist, da bekomme ich bestimmt noch was in meinen Kopf herein.

Trotzdem, wie erzeuge ich diese Gruppe?

Und flashpixx wenn du mir aber was zum Baby-Step erzählen könntest wieso der so fix ist währe ich dir sehr dankbar

Bearbeitet 4. Juli 2010 von aSHtRAY

[flashpixx]

Und flashpixx wenn du mir aber was zum Baby-Step erzählen könntest wieso der so fix ist währe ich dir sehr dankbar

Also ich finds interessant ;-)

Also ich denke Du solltest bei Satz 2.6 (Lang-Trotter Methode) anfangen, denn das ist die Grundlage. Damit kannst Du erst einmal die Anzahl der Punkte bestimmen. Da das aber ein recht aufwendiger Algo ist, will man das ganze natürlich "besser" machen, das wäre dann Satz 2.3.1 Satz von Hasse, der eine Heuristik ist, d.h. er wird defakto nicht die beste Lösung liefern, sondern nur eine Näherung. Nun will man ja auch genau die Punkte bestimmen und man muss diese interpolieren, was mit dem Baby Step bzw Giant Step über das Lagrange Polynom gemacht wird.

Also letztendlich nimmst Du einen guten Startwert durch den Satz von Hasse und interpolierst via Lagrange (2.17)

Ich hoffe, das hilft weiter, wenn nicht, müsste ich mich auch länger damit beschäftigen

[aSHtRAY]

Ne Ne is super =)

Eine kurze knappe Aussage an der man sich langarbeiten kann.

Danke

[aSHtRAY]

Es wird wieder zu warm, ich komm einfach nicht mehr drauf

http://www.uni-ulm.de/~s_sfackl/ss09/PunkteZaehlenaufElliptischenKurven.pdf

Das Beispiel 2.4

Die Punkte

auf jeweils das erste Punktepaar komme ich aber nicht auf das zweite.