Arbeiten mit cyclotomic polynomials

Neue Frage »

Shalec Auf diesen Beitrag antworten »
Arbeiten mit cyclotomic polynomials
Hallo allerseits.

Wir befinden uns im Körper und wollen ein Element A daraus mit potenzieren. In der Literatur lese ich darüber nur "thanks to the cyclotomic polynomials, we can do that fast".

Hat dazu jemand eine Idee, wie das gemeint ist? Der p-Frobenius darin ist praktisch "gratis".


Meine Annahme
Wenn ich auf [1] nachschaue sind solche Polynome daraus gekennzeichnet, dass ich sie faktorisieren kann:

wobei

Angewandt auf diesen speziellen Fall d=8 liefert dann die Teiler von 8: 1, 2, 4 und 8. Also:
(k=1)
(k=1)
(k=1,3)
(k=1,3,5,7)

Insgesamt liefert mir das eine Faktorisierung:

Ich sehe nur nicht unbedingt wie diese Faktorisierung schneller gehen soll.. Ich meine, ich könnte den -Frobenius vorberechnen (ist am Ende nur eine Permutation und Multiplikation mit zweier Potenzen) und die Invertierung nimmt sich am Ende sowieso nichts. Vermutlich ist mein Ansatz auch komplett doof.

Vielen Dank für die Zeit und Hilfe!

[1] https://de.wikipedia.org/wiki/Kreisteilungspolynom


Nachtrag
Wenn ich mal in Sage folgendes aufbaue: und dann ausrechnen lasse, erhalte ich für alle geraden k: 1 und für alle ungeraden k: p-1.
Weiter ist

Das hieße, dass ich alle x-Potenzen der Darstellung durch eine multiplikation entsprechend ersetzen darf.
Nehmen wir das Element mit der Darstellung:
eine Berechnung würde dann auf hinauslaufen. Da hier zwar der "Freshmens Dream" funktioniert, aber nicht für diese Potenz, ist obige Erkenntnis vlt. an einigen wenigen Teilen wirklich gewinnbringend anwendbar.

Nun ist wohl die erste Hürde: Wie löse ich die Potenz auf? Erster naiver Ansatz:

Der erste Ausdruck ist praktisch das 8-Fache Anwenden des p-Frobenius. Also nur der p^8-Frobenius. Die Inverse zu berechnen ist hingegen eine wirklich blöde Arbeit - Also kein guter Ansatz!


EDit2: Mögliche "Interpretation" der Worte: Da ich ursprünglich berechnen musste, könnte damit auch die Aufspaltung gemeint sein. Wobei, meiner Meinung nach, genau diese Faktorisierung nicht sonderlich Nennenswert ist.
Shalec Auf diesen Beitrag antworten »

Nun nochmal eine Antwort zu diesem Problem, was jedoch noch nicht gelöst ist.
Wir betrachten ein für ein prim. Wir möchten nun "einfach"

berechnen. Folgende zwei mögliche Wege existieren dafür (mod )

1. Methode
Naive Berechnung mit Trick:

Dabei ist die Potenz der entsprechende Frobenius, welcher "einfach" berechnet werden kann. Folgendes Mapping wird dazu verwendet, falls man als Körpererweiterung betrachtet, wobei irreduzibel ist. Jeder Koeffizient zur geraden Potenz von x wird abgeschrieben und jedes andere mit (-1) multipliziert.
Die Invertierung ist ein wenig schlimmer, da würde ich zunächst dem Standard "IEEE 1363-1.2008" im Kapitel 6 folgen. Exemplarisch (und gut) beschrieben auf Stack zu finden unter [1].


2. Methode
Diese Methode wird im Buch von Mrabet etal. "Guide to Pairing-Based Cryptography" im Kapitel 7 [2] nebenher beschrieben. Ich habe keine Ahnung, wie diese Methode genau helfen soll ohne Invertierung. Dies ist meine Frage ans Board. Sie sollte mit der Macht der Algebra beantwortet werden können Big Laugh

Nun das Vorgehen:
Man nutzt Kreisteilungspolynome (Cyclotomic Polynomials) um zu faktorisieren und erkennt, dass ist. Diese Tatsache und die Faktorisierung macht man sich dann zu Nutze: Sei , dann ist .

Nun betrachten wir eine quadratische Körpererweiterung: (Analog zu , darf man das hier überhaupt? Ich denke schon, infosofern man nicht als Tower auf und dann auf aufbaut.) Dann ist
für . (Damit endet Bemerkung 7.1)
Nun lässt sich Bemerkung 7.3 hinzuziehen, welche aussagt, dass . Dazu hatte ich vor einiger Zeit bereits einen Thread gepostet, welcher das Potenzieren und Invertieren solcher Elemente mit Norm 1 thematisiert.

Wenn ich mir die Überschrift von Remark 7.1 nochmal genau durchlese, und betrachte, so sehe ich, dass diese Bemerkung offenbar nicht das Ziel verfolgte zu berechnen.
Ich würde halt sehr gerne auf das Invertieren verzichten wollen. Wenn das nicht geht, ist es so und ich muss einen Weg konstruieren, die Inverse zu bestimmen. smile (Weg 1)




Literatur
[1] https://stackoverflow.com/questions/2421...of-a-polynomial (accepted answere)

[2] https://books.google.de/books?id=jmwNDgA...k%207.1&f=false
Die Seite sollte online einsehbar sein. Zur Not nach "Remark 7.1" suchen.
 
 
Neue Frage »
Antworten »



Verwandte Themen