Anwendung des Frobenius Endomorphismus

Neue Frage »

Shalec Auf diesen Beitrag antworten »
Anwendung des Frobenius Endomorphismus
Hallo allerseits,

ich habe seit langem ein kleines Verständnisproblem oder habe den Umfang nicht ganz erfasst. Es geht um den Frobenius Endo. auf endlichen Körper mit Primcharacteristic p. (Am Ende geht es um Pairings, ist aber hier nicht so wichtig)

Sagen wir, wir operieren auf , dann soll gelten:

Ich verstehe/sehe aber nicht, warum. Kann mich hier bitte jemand erleuchten?

Viele Grüße und vielen Dank

Edit: Quelle der Rechnung ist übrigens ein Buch von Mrabet "Guide To Pairing-Based Cryptography" aus 2017. CRC-Press.
Shalec Auf diesen Beitrag antworten »

Dieser Post nur, damit es deutlich wird, dass ich was hinzufüge:

Also wenn ich mir mal angucke, dann kann ich das ja wie einen Tower aufbauen:

Als Basisbetrachtung dient für ein quadratfreies . Dann lässt sich jedes Element als Polynom 1. Grades darstellen: . Nun zur Anwendung des Frob:

(Koeffizienten mod p)
(Frob = Identität auf
da
da kein Quadrat ist.

Damit haben wir schonmal eine sehr schnelle Potenzierung, nahezu gratis. Auf diesem Körper bauen wir auf. Ich poste das jetzt, damit potentielle Antwortgeber wissen, dass hier grad was passiert und sie evtl. Zeit sparen können.

Edit:
Darauf aufbauend betrachten wir nun Also hat jedes Element die Darstellung: mit Koeffizienten . Ziel ist es nach wie vor den p-Frobenius anzuwenden. Also gucken wir uns auch mal hier an, was passiert, wenn ich mit p potenziere:



Soweit korrekt?
Nun ist
Also:


Weiter gedacht, könnte ich dann auch
nutzen und entsprechend rekursiv darstellen.
Shalec Auf diesen Beitrag antworten »

Die Frage spielt offenbar am Ende darauf ab, wie ich auf und entsprechend auf aufbaue.

Würde ich das mit Sage versuchen, müsste ich gemäß [1] verschiedene X verwenden. Was ja auch irgendwie Sinn machen würde.


[1] https://groups.google.com/forum/#!msg/sa...mQ/qLicLWV2alIJ
Shalec Auf diesen Beitrag antworten »

Bei "meinem" Tower muss das Polynom f irreduzibel über sein:
Elvis Auf diesen Beitrag antworten »

Die Antwort steht hier : https://de.wikiversity.org/wiki/Endliche...n/Textabschnitt
Das hoffe ich jedenfalls ... zumindest ein Teil der Antwort ... vielleicht habe ich auch die Frage noch nicht verstanden ...
Jedenfalls ist der Teilkörperverband von antiisomorph zum Gruppenverband der zyklischen Gruppe der Ordnung , und diese zyklische Galoisgruppe wird vom Frobenius-Automorphismus erzeugt.
Shalec Auf diesen Beitrag antworten »

Hallo Elvis Wink

eigentlich wollte ich gerne eine praktische Anwendung vom Frobenius erzeugen, zum Beispiel auf KSS-16 Kurven und dem optimal Ate-Pairing. Beim Ate-Pairing wird durch eine bilineare Abbildung auf die Untergruppe der r-ten Einheitswurzeln im , für eine Primzahlpotenz q und dem Einbettungsgrad k, abgebildet. In F_{q^k} lässt sich der q-Frobenius nutzen, welcher aber Analog zum Primzahl p-Frobenius funktioniert, da beide die gleiche Charakteristik haben und somit (a+b)^p = a^p + b^p mod p bzw. analog für mod q gilt. (insofern ich mich gerade korrekt erinnere.. freshmens dreams für endliche Körper smile )

Die KSS-16 Kurven haben einen Einbettungsgrad k=16. Für diesen möchte ich den Frobenius klar hinschreiben. Dabei baut man sich ja einen Tower von Körpererweiterungen:
code:
1:
2:
3:
4:
F_{p^2}    = F_p[X]/(X^2 - 1)
F_{p^4}    = F_{p^2}[Y]/(Y^2 - X)
F_{p^8}    = F_{p^4}[Z]/(Z^2 - Y)
F_{p^{16}} = F_{p^8}[V]/(V^2 - Z)


In Sage sieht das ganze dann so aus
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
p=11
R = GF(p) 
_.<X> = PolynomialRing(R)
R2.<X> = R.extension(X^2 - 1, 'X')
_.<Y> = PolynomialRing(R2)
R4.<Y> = R2.extension(Y^2 - X, 'Y')
_.<Z> = PolynomialRing(R4)
R8.<Z> = R4.extension(Z^2-Y, 'Z')
_.<V> = PolynomialRing(R8)
R16.<V> = R8.extension(V^2-Z, 'V')

mit der Ausgabe
code:
1:
2:
3:
4:
5:
Finite Field of size 11
Univariate Quotient Polynomial Ring in X over Finite Field of size 11 with modulus X^2 + 10
Univariate Quotient Polynomial Ring in Y over Univariate Quotient Polynomial Ring in X over Finite Field of size 11 with modulus X^2 + 10 with modulus Y^2 + 10*X
Univariate Quotient Polynomial Ring in Z over Univariate Quotient Polynomial Ring in Y over Univariate Quotient Polynomial Ring in X over Finite Field of size 11 with modulus X^2 + 10 with modulus Y^2 + 10*X with modulus Z^2 + 10*Y
Univariate Quotient Polynomial Ring in V over Univariate Quotient Polynomial Ring in Z over Univariate Quotient Polynomial Ring in Y over Univariate Quotient Polynomial Ring in X over Finite Field of size 11 with modulus X^2 + 10 with modulus Y^2 + 10*X with modulus Z^2 + 10*Y with modulus V^2 + 10*Z


Nun kann man sich auch mit
code:
1:
A=R16.random_element(); A

ein zufälliges Element geben lassen und mittels A^p entsprechend die Berechnung durchführen. Diese Berechnungen möchte ich allerdings genauer angucken smile

Daher möchte ich eine explizite Formel/einen expliziten Algorithmus zur Berechnung herleiten.
 
 
Elvis Auf diesen Beitrag antworten »

Igitt, igitt. Augenzwinkern das läuft ja alles auf konkrete Quotientenringe von Polynomringen hinaus, so genau würde ich das gar nicht wissen wollen. Ich ziehe es vor, dass diese endlichen Körper bis auf Isomorphie als Körper eindeutig bestimmt sind. Wir wissen doch, dass man in Körpern recht bequem rechnen kann, bei den reellen oder komplexen Zahlen oder p-adischen Zahlen oder bei Funktionenkörpern macht man sich doch auch keine Gedanken mehr über ihre x-beliebige konstruktive Entstehung.
Positiv formuliert: mach weiter so, lass dich von einem trägen alten ... nicht aufhalten, vielleicht entdeckst du ja noch bahnbrechende Neuigkeiten. Ich warte gespannt auf deine Veröffentlichungen, und ich werde deine Bücher mit absoluter Sicherheit käuflich erwerben und mit Interesse studieren. Freude
Shalec Auf diesen Beitrag antworten »

Die ganze Überlegung dient meiner Masterarbeit Big Laugh Bei der ich aktuell ein zeitliches Problem habe, da ich einem Tipp von meinem Prof in die falsche Richtung gefolgt bin. (Kostete mich ca. 2 Monate)

Am Ende steht eine Implementierung auf einem Mikrocontroller an. Dafür bräuchte ich dann schon die tatsächliche Berechnung und ggfs. eine ASM Implementierung. Ich bin leider weit weg, mit meinem Thema, von der Mathematik unglücklich
Elvis Auf diesen Beitrag antworten »

Interessant. Man kann es ja nicht wissen, aber vielleicht hilft dir mein Ansatz doch weiter. Vielleicht ist es gar nicht nötig, komplizierte konkrete Strukturen zu betrachten. Vielleicht ist der direkte Zugang über die (bis auf Isomorphie) eindeutig definierten Körper, ihre (bis auf Isomorphie) bekannten zyklischen Galoisgruppen und deren erzeugenden Elemente (Frobenius-Automorphismus) und den dadurch bekannten Teilkörperverbänden der richtige Weg.
Bei reellen Zahlen z.B. arbeitet man schon lange nicht mehr mit Dedekindschen Schnitten oder Intervallschachtelungen, obwohl das die historisch ersten Ansätze waren. Man nimmt stattdessen für Rechnungen in der Schule die Dezimalzahlen, in der Analysis je nach Bedarf konvergente Folgen oder Cauchyfolgen oder konvergente Reihen oder sonst etwas. Die Theorie der reellen Zahlen baut man schon gar nicht mehr auf konkrete Objekte auf sondern benutzt stattdessen eine axiomatische Definition (vollständiger angeordneter Zahlkörper). Das funktioniert alles so einfach, weil man weiß, dass es bis auf Isomorphie nur einen Körper der reellen Zahlen gibt.
Genau so weiß man, dass es bis auf Isomorphie zu jeder Primzahl p und jeder natürlichen Zahl n genau einen endlichen Körper mit Primkörper gibt. Die Teilkörper muss man nicht konkret aus irreduziblen Polynomen konstruieren, es genügt zu wissen, dass es sie gibt und wie man mit ihren Elementen rechnet. Das sollte meiner Meinung nach für alle theoretischen und praktischen Zwecke genügen. Frag mal deinen Professor, ob der direkte algebraische Zugang aus der Theorie endlicher Körper sinnvoll möglich und richtig ist.
Shalec Auf diesen Beitrag antworten »

Möglicher Weise hast du da recht. Normaler Weise sind konkrete Strukturen nicht nötig, um zu wissen, das und wie es funktioniert. Aber wenn man das in C oder Assambler realisieren muss sind konkrete Formeln oft einfacher smile

Ich werde wohl demnächst wieder dazu kommen, mich damit weiter zu beschäftigen. Im Moment sieht es für mich nach unnötigen Rechnungen aus, da man ja den entsprechend auf aufbaut:

Edit:{Änderung im ersten "Nenner" "U^2-1" ->" U^2+1", da ich einen Widerspruch gefunden habe.}




Aber bei einer Sache bin ich mir unsicher, ich denke aber, dass das funktioniert. Betrachte ich anstelle von p und baue das ganze auf auf, bleiben obigen Überlegungen, insbesondere die erste, erhalten. (Also einfach in obigen Ausdrücken konsistent p gegen q tauschen).

Zur Berechnung: Fange ich nun mit einem Element aus dem letzten Körper an, habe ich Koeffizienten im darunter () liegenden Körper. (Wenn man es genau nimmt, ist die Relation hier ja nicht ganz korrekt, da diese Äquivalenzklassen unterschiedliche Mengen sind, aber ich denke, man weiß es konventionell, wie es gemeint ist smile )

Es sieht für mich zunächst nach einer großen Indexschlacht aus.


Edit:
Aus obigen Betrachtungen sehe ich ja auch, dass
Einsen sind ja immer recht Toll, was die Multiplikation angeht Big Laugh Mein intuitiver Weg beim Vorgehen mit der Indexschlacht bei 16 Koeffizienten aus wäre zunächst alles zu Potenzen von X umzuformen, damit ich möglichst wenig Variablen habe. Also entsprechend
usw. Möglicherweise ist es manchmal ganz praktisch einsetzen zu dürfen.

Frage: Nun ließe sich noch bzgl. p analysieren, ob 1 ein Quadrat ist. Betrachte ich das quadratische Reziprozitätsgesetz und das Legendresymbol spielt es keine Rolle, ob p kongruent 1 oder 3 mod 4 ist, 1 bleibt 1. Dann habe ich aber das Problem, dass ich Wurzeln berechnen könnte und somit X^8 = 1 und X^4=1 und X^2 = 1 und X = 1. Ich vermute aber stark, dass das nicht möglich sein sollte und ich entsprechend ein Ansatzproblem habe?

Edit: Wenn ich mir nochmal genau angucke, was ich schon wieder vergessen hatte: mit als nicht-Quadrat, sonst wäre das Polynom nicht irreduzibel. Sehe ich hier aber dennoch irgend ein Problem nicht? Ist überhaupt irreduzibel? ( ...) Offenbar nein.

Wieso meckert Sage dann nicht? sind beide nicht irreduzibel. Aber hingegen schon. Demnach sollte doch die Ringerweiterung blödsinn sein? Ohne Irreduzibilität kein Primideal, ohne Prim nicht maximal (in diesem speziellen Fall) und damit wäre das kein Körper.

Betrachte ich nun , dann habe ich mit

Also, nochmal zusammengefasst: -1 ist genau dann kein Quadrat, wenn die Primzahl kongruent 3 mod 4 ist. Anderenfalls ist -1 ein Quadrat und entsprechend U^2+1 nicht irreduzibel. Im Falle, dass wir aber eine Primzahl nutzen, die kongruent 1 mod 4 ist, müssen wir diesbezüglich ein passendes Nichtquadrat wählen und erhalten trotzdem nach dem quadratischen Reziprozitätsgesetz. (Hoffe, dass letzteres die richtige Quelle dafür ist..)
Shalec Auf diesen Beitrag antworten »

Nach dem ganzen hin und her habe ich nun die Lösung:


für ein
wobei eben das irreduzible Element ist.

Aber wie wende ich das nun an? Angenommen wir betrachten einfach Mal q=p=3 und entnehmen dem ein beliebiges Element. Mache ich dies mit Sage erhalte ich
code:
1:
2:
3:
4:
5:
GT=GF(p^16)
GT.gen() #zeige den Generator
GT.random_element() #wähle ein zufälliges Element
Sage: z16
Sage: z16^15 + z16^14 + 2*z16^13 + z16^9 + z16^8 + 2*z16^7 + z16^5 + 2*z16^4 + 2*z16^3 + z16^2


Also ein Polynom aus , wobei
Wie kann ich auf dieses Element nun meine Betrachtungen zum Frobenius anwenden?



Annahme
Meine Annahme ist, dass ich nun die Identitäten einsetze und so entsprechend den gefunden Ausdruck in vier Variablen auf ein Polynom in einer Variablen vom Grad 15 reduziere.
Diese Annahme führt tatsächlich zu einem Polynom vom Grad kleiner als 16.

Nun eine letzte Frage: Wie sieht das überhaupt aus, wenn ich hier quasi im Monolog mein Ergebnis herleite und dieses in der Masterarbeit (inklusive Herleitung) übernehmen will? Muss ich auf diesen Thread in irgend einer Form verweisen?
Neue Frage »
Antworten »



Verwandte Themen

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