Elliptische Kurve: Punkte der Ordnung 2 und zyklische Elliptische Kurven

Neue Frage »

Highlander1989 Auf diesen Beitrag antworten »
Elliptische Kurve: Punkte der Ordnung 2 und zyklische Elliptische Kurven
Hallo,

ich tue mit Kryptographie noch etwas schwer, da ich durch Krankheit drei Wochen Vorlesung verpasset habe.

Ich habe folgende Aufgabe zu lösen (siehe Anhang).

1. Hier müsste man ja dann irgendwie zeigen, dass wenn der Punkt eine Nullstelle ist er Ordnung 2 besitzt. Zunächst ist mir nicht wirklich klar wie ich die Ordnung des Punktes von einer Elliptischen Kurve bestimme. Hier wäre ein Hinweise hilfreich.

2. kleiner gleich 1 heißt ja entweder gibt es keine Nullstellen oder eine.

3. Das Kapitel über Elliptische Kurven im Skript ist sehr knapp gehalten. Ich habe im Internet verschiedene Verfahren zur Bestimmung der Anzahl von Punkte auf der Kurve gefunden, glaube aber nicht dass ich damit arbeiten soll, da sie nicht behandelt wurden (bis jetzt).
Captain Kirk Auf diesen Beitrag antworten »

Hallo,

1. Schau dir die Addition auf elliptischen Kurven an. Die Ordnung ist so definiert wie in jeder anderen Gruppe auch, die Bestimmung der Ordnung eines konkreten Punktes unterscheidet sich auch nicht wirklich von anderen gruppen.
2.Was passiert denn wenn das Polynom drei Nullstellen hat= Die 1) ist nützlich.
3.Elementare Gruppentheorie und 1).

Die 2) und 3) folgen aus der 1) ohne irgendwelche weiteren Kenntnisse über elliptischen Kurven, außer dass man darauf eine abelsche Gruppenstruktur bilden kann.
 
 
Highlander1989 Auf diesen Beitrag antworten »

Hallo, vielen Dank für deine Antwort:

Erstmal zur 1.

Die Addition habe ich mir angeschaut. Wenn die Ordnung so definiert ist wie in jeder Gruppe heißt das ich nehme den Punkt P und suche die kleinste Zahl x für die gilt :

.

Das neutrale Element einer Ell. Kurve ist ja der "Punkt im Unendlichen".

Wenn ich nun sage die Ordnung des Punktes ist 2, dann rechne ich ja P*P, was bei der Addition über Elliptischen Kurven ja genau zu dem Ergebnis "Punkt im Unendlichen" führt, da man bei gleicher x-Koordinate durch 0 teilt.

Doch was genau hat das nun mit den Nullstellen des Polynoms zu tun?
Captain Kirk Auf diesen Beitrag antworten »

Die Verknüpfung auf einer elliptischen Kurve ist die Addition. Dementsprechend, wie für abelsche Gruppen üblich, ist die Notation generell additiv nicht multiplikativ.
Also P+P und nP.


Zitat:
Wenn ich nun sage die Ordnung des Punktes ist 2, dann rechne ich ja P*P, was bei der Addition über Elliptischen Kurven ja genau zu dem Ergebnis "Punkt im Unendlichen" führt, da man bei gleicher x-Koordinate durch 0 teilt.

Ich verstehe nicht was das sagen soll. Dass ist alles andere als überraschend, das ist Teil der Definition der Ordnung.


Zitat:
Doch was genau hat das nun mit den Nullstellen des Polynoms zu tun?

Wenn du P+P berechnest kann man das kaum übersehen.
Highlander1989 Auf diesen Beitrag antworten »

Okay, dass macht Sinn,

also eine Nullstelle liegt ja dann vor, wenn die y-Koordinate von (x,y) gleich 0 ist. Ist das der Fall rechnet man xP = (die ausführliche Rechnung für dieses Addition kann ich aufschreiben, spare ich mir jetzt hier), wobei dies ja der Fall ist für x = 2. Damit ist die Ordnung des Punktes 2 und das gilt für jeden Punkt der eine Nullstelle ist.


Reicht das so?
Sorry wenn ich mich etwas blöd anstelle, ich habe mir in zwei Tagen 150 Seiten Skript reingezogen, die Algebra ist schon ein paar Jährchen her, da bedarf es auch nochmal einiger Auffrischung!

Danke!!!!
Captain Kirk Auf diesen Beitrag antworten »

Der Gedanke ist richtig, der Aufschrieb verbesserungswürdig.
Highlander1989 Auf diesen Beitrag antworten »

Okay gut, das ist mir klar, ich werde es für die Übung ausführlich aufschreiben! Darum geht es ja hier: den richtigen Gedanken zu bekommen!


zur 2.

Eine Gruppe ist dann zyklisch, wenn sie ein Element besitzt, dass die komplette Gruppe erzeugt.

Eine Nullstelle ist in in diesem Fall zu sich selbst das inverse Element (das hat etwas mit der Aufgabe zu tun, ich bin aber noch nicht sicher was!)
Highlander1989 Auf diesen Beitrag antworten »

Ich würde sagen, dass wenn ich mehr als eine Nullstelle habe, dann müsste ich eine Nullstelle mithilfe einer anderen erzeugen, das geht aber nicht, was man in der 1. sieht.
Captain Kirk Auf diesen Beitrag antworten »

Wie erzeugt denn eine Nullstelle eine andere?

Hat das Polynom mehr als eine Nullstelle (diese sind dann notwendig verschieden(!)) so hat die Gruppe mind. 2 Punkte von Ordnung 2.
Wie viele Punkte der Ordnung zwei kann eine zyklische Gruppe nur haben?
Highlander1989 Auf diesen Beitrag antworten »

Okay, das war Quatsch, sehe ich selbst traurig .

Eine zyklische Gruppe kann maximal ein Element der Ordnung zwei haben. Den Beweis dafür habe ich sogar schon einmal gemacht Augenzwinkern . damit kann die Gruppe nicht mehr zyklisch sein, wenn es mehr als eine Nullstelle gibt.


Zu 3.

kann man dort so argumentieren, dass die Punkte immer paarweise auftreten, oder habe ich das falsch verstanden? Die punkte sind doch immer an der x-Achse gespiegelt. man hat also eine gerade Anzahl an Punkten + den Punkt im Unendlichen, damit ist die Ordnung der ell. Kurve ungerade.
Captain Kirk Auf diesen Beitrag antworten »

Zitat:
kann man dort so argumentieren, dass die Punkte immer paarweise auftreten, oder habe ich das falsch verstanden? Die punkte sind doch immer an der x-Achse gespiegelt. man hat also eine gerade Anzahl an Punkten + den Punkt im Unendlichen, damit ist die Ordnung der ell. Kurve ungerade.

Das hast du komplett falsch verstanden. Es muss kein Punkt der Ordnung 2 existieren (hängt davon ab wie IK konkret aussieht ) und es kann Punkte höherer Ordnung geben.
Berechne mal als Bsp. und
Highlander1989 Auf diesen Beitrag antworten »

Okay, dann weiß ich aber nicht wie ich aus der 1. auf die 3. schließen soll (das hattest du oben vorgeschlagen).

Hättest du da noch einen Hinweis?
Captain Kirk Auf diesen Beitrag antworten »

Da der Beweis ein Einzeiler ist wäre jeder weitere Tipp von mir bereits die Lösung.
Wie gesagt das ist elementare Gruppentheorie.
Highlander1989 Auf diesen Beitrag antworten »

Okay, wenn es keine Nullstellen gibt heißt das es gibt keine Punkte der Ordnung 2, dann müsste man nur noch zeigen, dass es keine Punkte mit gerader Ordnung gibt (bzw. nur Punkte mit ungerader Ordnung). Daraus würde dann folgen dass die Gruppenordnung ungerade sein muss.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »