Inversion und Quadrieren im endlichen Körper mit Erweiterungsnorm 1

11.08.2017, 10:59

Shalec

Inversion und Quadrieren im endlichen Körper mit Erweiterungsnorm 1

$\begin{align*} \newcommand\F{\mathbb F} \end{align*}$

Hallo allerseits,

ich habe folgendes gelesen:
"If $\begin{align*} N_{\F_{q^k}/\F_{q^d}}(m)=1 \end{align*}$ , then the inversion in $\begin{align*} \F_{q^k} \end{align*}$ for a $\begin{align*} m\in\F_{q^k} \end{align*}$ is a simple conjugation and any squaring can be computed efficiently."

Aber warum? Wie hängt das zusammen?

Viele Grüße und vielen Dank für die Hinweise!

Edit: Nach [1] habe ich die Norm in diesem Fall:
$\begin{align*} N_{\F_{q^k}/\F_{q^d}}(m)= m^{1+p+...+p^{k/d-1}}=1 \end{align*}$

Nehmen wir als Beispiel k=16, d=1, dann haben wir
$\begin{align*} N(m)=m^{1+p+...+p^{15}}\equiv1 \end{align*}$ da $\begin{align*} m\in\F_p \end{align*}$ (korrigiert mich bitte, falls ich mich hier täusche) wird das Ergebnis modulo p berechnet. Nehmen wir mal an, dass p obiges erfüllt. D.h. $\begin{align*} p-1=\phi(p)\mid \sum\limits_{k=0}^{15}p^k \end{align*}$ .

Aber wie hilft mir das bei der Invertierung und Quadrierung? Ich übersehe mit Sicherheit irgendwas..

[1] https://de.wikipedia.org/wiki/Norm_(K%C3%B6rpererweiterung)#Beispiele

11.08.2017, 18:26

jester.

Auf diesen Beitrag antworten »

RE: Inversion und Quadrieren im endlichen Körper mit Erweiterungsnorm 1

Zitat:

Original von Shalec $\begin{align*} \newcommand\F{\mathbb F} \end{align*}$
Edit: Nach [1] habe ich die Norm in diesem Fall:
$\begin{align*} N_{\F_{q^k}/\F_{q^d}}(m)= m^{1+p+...+p^{k/d-1}}=1 \end{align*}$

Nein, richtig ist $\begin{align*} N_{\F_{q^k}/\F_{q^d}}(m)= m^{1+q^d+...+{(q^d)}^{k/d-1}}=1 \end{align*}$

Aus der Gleichung bekommt man aber
$\begin{align*} 1 = N_{\F_{q^k}/\F_{q^d}}(m)= m^{1+q^d+...+{(q^d)}^{k/d-1}} = m \cdot \underbrace{m^{q^d+...+{(q^d)}^{k/d-1}} }_{=m^{-1}} = m \cdot \underbrace{m^{q^d} \cdot m^{(q^d)^2} \cdot ... \cdot m^{{(q^d)}^{k/d-1}} }_{=m^{-1}} \end{align*}$
Es ist also $\begin{align*} m^{-1} \end{align*}$ lediglich ein Produkt von Konjugaten von $\begin{align*} m \end{align*}$ (Konjugat heißt hier Bild unter dem Frobenius-Automorphismus).

Somit ist also das Invertieren "leicht", wenn man denn den Frobenius "gut" ausrechnen und "leicht" multiplizieren kann.

Das heißt aber halt auch, dass man multiplizieren können muss. Demnach kann man also auch quadrieren. Die Bemerkung über das Quadrieren kann ich daher gerade nicht so ganz deuten, aber vielleicht hilft dir die Beschreibung für $\begin{align*} m^{-1} \end{align*}$ ja schon etwas weiter...

Edit: Im Fall $\begin{align*} k/d=2 \end{align*}$ ist natürlich tatsächlich $\begin{align*} m^{-1}=m^{q^d} \end{align*}$ , und Invertieren ist da Konjugieren mit dem Frobenius (ohne weitere Multiplikationen)...

12.08.2017, 16:37

Shalec

Auf diesen Beitrag antworten »

Ahh. Du hast den Holzhammer rausgeholt Hammer

Vielen Dank. Ich habe leider k=16 und d=1 smile

Damit wird das Invertieren tatsächlich etwas teurer. Wobei ich hier auch die Tower Fields betrachten könnte und das Inverse immer eine Ebene weiter durchschubse. Also habe ich dann

$\begin{align*} \newcommand\F{\mathbb F} N_{\F_{p^{16}}/\F_p} (m) = m\cdot m^{p+...+p^{15}}=1 \end{align*}$ was ja bereits aussagt: <15 Mal den Frobenius anwenden und ein paar Potenzen davon bestimmen. Dabei ist ja gerade m^p=m, falls m aus F_p kommt.

Gehe ich im Tower durch, hätte ich als ersten Schritt
$\begin{align*} N_{\F_{p^{16}}/\F_{p^8}}= m \cdot m^{p^{8}}=1 \end{align*}$

Wie dem auch sei, ich habe mal spaßenshalber mit einer Primzahl den Test gemacht, ob
$\begin{align*} 1+p+...+p^{15}\equiv 0 (\bmod\ p-1) \end{align*}$ , dies wurde mir dank Sage verneint. (Nach dem kleinen Satz von Fermat) Die gewählte Primzahl ist leider die Basis meiner weiteren Betrachtungen.

Neue Frage »

Antworten »

Inversion und Quadrieren im endlichen Körper mit Erweiterungsnorm 1

Verwandte Themen