Bestimmung von Twists elliptischer Kurven |
| 20.08.2017, 10:57 | Shalec | Auf diesen Beitrag antworten » | ||
| Bestimmung von Twists elliptischer Kurven heute wieder ein spannendes Thema aus der Zahlentheorie oder Algebra (je nachdem, wie man es sehen will 
wobei das Eine das Andere nicht ausschließt) elliptischer Kurven. Folgende Situation:Ich beschäftige mich mit einer Paarungs-freundlichen (pairing-friendly) Familie elliptischer Kurven: KSS16. In meinem speziellen Fall habe ich und eine Kurve der Familie, gegeben durch . Der Einbettungsgrad (embedding degree) ist (daher die 16 in KSS16). Wenn ich richtig der Annahme gehe, reichen diese Voraussetzungen für mein Anliegen. Frage In einem Paper habe ich folgenden Twist genannt bekommen und folgende Körpererweiterung . Nun möchte ich diesen Twist selber bestimmen bzw. nachvollziehen können, wie man darauf kommt. Ich hatte die Frage bereits vor einiger Zeit im Stackexchangeboard [1] gestellt, aber noch keine Antwort, vielleicht haben wir hier ja jemanden an Board, der sich damit ein wenig auskennt oder Mutmaßungen anstellen könnte 
(Den Link nenne ich, damit niemand, falls es zwischenzeitlich eine umfassende Antwort auf Stack gab, seine Zeit mit dem Tippen der Antwort verbrauchen muss.) Mein Bisheriger Ansatz ist ebenfalls bei Stack gelistet, leider weiß ich echt nicht, mit welchem Ziel ich diesen Ansatz verfolgen sollte. Mein Ansatz Zu Twists habe ich mal das Buch "Elliptic Curves" von "J.S. Milne" [2] konsultiert. Ich bin mir aber ehrlich gesagt nicht sicher, ob seine Angaben für jeden Fall gelten. Falls ja, sind wir im Fall "b=0". Unsere Kurve von oben sieht nach einer Homogenisierung einfach so aus: und Punkte sind entsprechend (X:Y:Z). Die Abbildung für den Twist würden wir dann nach [2] durch für i=0,1,2,3 und einer vierten Einheitswurzel (fourth root of unity) c. Allerdings ist dies ein Automorphismus, bildet also Punkte von E auf Punkte von E isomorph ab. Das klappt wohl immer bei Twists, allerdings nur über den algebraischen Abschluss. Genau in diesem Punkt ist Milne leider nicht genau genug. Naja, abgesehen von seinen einführenden zwei Zeilen "given an elliptic curve E over K, find all elliptic curves E' over K that become isomorphic to E over Cl(K)" (ich habe die Buchstaben ein wenig verändert) Weiter notiert er, dass jede Kurve Isomorph zu E wird. Nutze ich diese Form, habe ich a=1, b=0 und entsprechend wird was meinem Ansatz von [1] entsprechen würde: zu betrachten (abgeleitet von obigen ). Wobei die Wurzel nur symbolisch gemeint ist. Ergänzung Mein Gedanke bei der genauen Bestimmung war dieser, dass ich einen effizient berechenbaren Homomorphismus erhalte, sodass ich die Skalarmultiplikation mP, für ein P aus E, beschleunigen kann indem ich den Wert m zerlege in wobei m1 und m2 nur die halbe Größe von m haben. Damit hätte ich dann für den gesuchten Homomorphismus . Das ist natürlich nur genau dann ein speedup, wenn psi(P) schnell zu berechnen geht. Mittlerweile weiß ich, dass das wohl unter der GLV/GLS Methode verstanden wird, obwohl ich hiervon die genauen Details nicht kenne und auch noch keine Quelle fand. Nachtrag Ich habe nun herausgefunden, dass mein Ansatz unter der GLV/GLS recomposition verstanden wird. Diese wurde wohl in 2008 [3] bereits vorgestellt. 
Da denkt man, man hat mal was neues, war es schon da
[1] https://math.stackexchange.com/questions...twist-of-y2-x3x [2] http://www.jmilne.org/math/Books/ectext5.pdf S.138 [3] https://eprint.iacr.org/2008/194.pdf |
||||
| 20.08.2017, 18:25 | jester. | Auf diesen Beitrag antworten » | ||
RE: Bestimmung von Twists elliptischer Kurven
Das war ja erst vor 23 Stunden. Ob das viel ist an einem Wochenende kann man sicher diskutieren. Und obwohl es nicht unmöglich ist, dass das hier jemand beantworten kann (ich kann es nicht), ist es meiner Erfahrung nach doch eher unwahrscheinlich, dass du eine Antwort eher auf dem MB als auf Stackexchange bekommst. Der tendenziell erfolgversprechendere Weg führt von Math Stackexchange zu Mathoverflow. Ob deine Frage dorthin passt, mag ich nicht sicher beurteilen. Aber das schlimmste, was passieren kann, ist, dass sie geschlossen wird. Aber warte ruhig noch ein paar Tage. Tipp: Die Details, die du hier notiert hast, auch auf Stackexchange eintragen. |
||||
| 20.08.2017, 19:37 | Shalec | Auf diesen Beitrag antworten » | ||
RE: Bestimmung von Twists elliptischer Kurven
oh, ernsthaft? Ich dachte, dass es wesentlich länger her sei. Aber so ist es mit der Zeit und dem Gefühl für die Zeit 
Danke für den Tipp, dann werde ich es wohl eher dort ausbauen. Ich habe nun auch im Silverman - Arithmetic of Elliptc Curves ein paar Antworten gefunden. Viel interessanter ist aktuell die Frage, die sich daraus ergeben hat: GLV/GLS Methode in der Anwendung. Sie scheint wohl 30% der Berechnungen einzusparen.
|
||||
| 24.08.2017, 17:28 | Shalec | Auf diesen Beitrag antworten » | ||
Es hat sich offenbar ein Typo bei den Verfassen des Artikels [1] in Abschnitt 6.3 eingeschlichen. Es ist wohl ein quartic twist über anstelle eines "octic" twists über . Mit dem Grad vier kann ich besser leben, als vorher 8. Es gibt keine "octic twists" nicht. [1] https://eprint.iacr.org/2017/334 |
||||
|
|
