Arbeiten mit cyclotomic polynomials

05.11.2017, 16:57	Shalec	Auf diesen Beitrag antworten »
Arbeiten mit cyclotomic polynomials Hallo allerseits. $\begin{align} \newcommand\F[1]{\mathbb F_{p^{#1}}} \end{align}$ Wir befinden uns im Körper $\begin{align} \mathbb F_{p^{16}} \end{align}$ und wollen ein Element A daraus mit $\begin{align} p^8-1 \end{align}$ 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: $\begin{align} p^8-1 = \prod\limits_{d\mid 8} \phi_d(p) \end{align}$ wobei $\begin{align} \phi_d(p) = \prod\limits_{ \overset{1\leq k \leq d}{ ggT(k,d)=1} } \left( p - e^{2\pi i k/d} \right) \end{align}$ Angewandt auf diesen speziellen Fall d=8 liefert dann die Teiler von 8: 1, 2, 4 und 8. Also: $\begin{align} \phi_1(p)=p-e^{2\pi i} = p-1 \end{align}$ (k=1) $\begin{align} \phi_2(p)= p-e^{2\pi i/2} \end{align}$ (k=1) $\begin{align} \phi_4(p) =(p-e^{2\pi i/4})(p-e^{6\pi i /4}) \end{align}$ (k=1,3) $\begin{align} \phi_8(p) =(p-e^{2\pi i/8})(p-e^{6\pi i /8})(p-e^{15\pi i /8})(p-e^{21\pi i /8}) \end{align}$ (k=1,3,5,7) Insgesamt liefert mir das eine Faktorisierung: $\begin{align} (p - 1) (p + 1) (p^2 + 1) (p^4 + 1) \end{align}$ Ich sehe nur nicht unbedingt wie diese Faktorisierung schneller gehen soll.. Ich meine, ich könnte den $\begin{align} p^8 \end{align}$ -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: $\begin{align} \F{16} = \F{}[x]/(x^{16}-2) \end{align}$ und dann $\begin{align} (x^k)^{p^8-1} \end{align}$ ausrechnen lasse, erhalte ich für alle geraden k: 1 und für alle ungeraden k: p-1. Weiter ist $\begin{align} x^{-1}=(p-1)/2 +1 \end{align}$ Das hieße, dass ich alle x-Potenzen der Darstellung durch eine multiplikation entsprechend ersetzen darf. Nehmen wir das Element $\begin{align} A\in\F{16} \end{align}$ mit der Darstellung: $\begin{align} A=\sum\limits_{k=0}^{15} a_kx^k \end{align}$ eine Berechnung würde dann auf $\begin{align} A^{p^8-1} \end{align}$ 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: $\begin{align} A^{p^8-1}=A^{p^8} \cdot A^{-1} \end{align}$ 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 $\begin{align} (p^{16}-1)/r \end{align}$ berechnen musste, könnte damit auch die Aufspaltung gemeint sein. Wobei, meiner Meinung nach, genau diese Faktorisierung nicht sonderlich Nennenswert ist.
12.11.2017, 16:17	Shalec	Auf diesen Beitrag antworten »
Nun nochmal eine Antwort zu diesem Problem, was jedoch noch nicht gelöst ist. Wir betrachten ein $\begin{align} \newcommand{\F}[1]{\mathbb F_{p^{#1}}} A\in\F{16} \end{align}$ für ein $\begin{align} p\sim2^{340} \end{align}$ prim. Wir möchten nun "einfach" $\begin{align} A^{p^8-1} \end{align}$ berechnen. Folgende zwei mögliche Wege existieren dafür (mod $\begin{align} p^{16} \end{align}$ ) 1. Methode Naive Berechnung mit Trick: $\begin{align} A^{p^8-1}=A^{p^8}A^{-1} \end{align}$ Dabei ist die $\begin{align} p^8 \end{align}$ Potenz der entsprechende Frobenius, welcher "einfach" berechnet werden kann. Folgendes Mapping wird dazu verwendet, falls man $\begin{align} \F{16}=\F{}[x]/[x^{16}-\alpha) \end{align}$ als Körpererweiterung betrachtet, wobei $\begin{align} x^{16}-\alpha \end{align}$ 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 Nun das Vorgehen: Man nutzt Kreisteilungspolynome (Cyclotomic Polynomials) um $\begin{align} p^{16}-1=(p^8-1)(p^8+1) \end{align}$ zu faktorisieren und erkennt, dass $\begin{align} A^{p^{16}-1} \equiv A\bmod p^{16} \end{align}$ ist. Diese Tatsache und die Faktorisierung macht man sich dann zu Nutze: Sei $\begin{align} g=A^{p^8-1} \end{align}$ , dann ist $\begin{align} g^{p^8}= g^{-1} \end{align}$ . Nun betrachten wir eine quadratische Körpererweiterung: $\begin{align} \F{16}=\F{8}(i) \end{align}$ (Analog zu $\begin{align} \F{2}=\F{}(i) \end{align}$ , darf man das hier überhaupt? Ich denke schon, infosofern man $\begin{align} \F8 \end{align}$ nicht als Tower auf $\begin{align} \F2 \end{align}$ und dann auf $\begin{align} \F{}(i) \end{align}$ aufbaut.) Dann ist $\begin{align} g^{p^8} = (g_0 + ig_1)^{p^8} = q_0 +i^{p^8} g_1 = g_0 -ig_1 = g^{-1} \end{align}$ für $\begin{align} g_0,g_1\in\F8 \end{align}$ . (Damit endet Bemerkung 7.1) Nun lässt sich Bemerkung 7.3 hinzuziehen, welche aussagt, dass $\begin{align} \|g\|=1 \end{align}$ . 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 $\begin{align} \phi_k(p)=p^8-1 \end{align}$ betrachte, so sehe ich, dass diese Bemerkung offenbar nicht das Ziel verfolgte $\begin{align} A^{p^8-1} \end{align}$ 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. (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.

1

Verwandte Themen