Normalbasen - Multiplikation < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:01 Do 29.11.2012 | | Autor: | Tim87 |
Hallo,
ich habe 3 Fragen zur Arithmetik von Normalbasen. Ich habe ca. 20 Quellen gelesen, darunter:
-[Q1] Normal Bases over Finite Fields von Shuhong Gao
-[Q2] Software Multiplication using Normal Bases von Ricardo Dahab et.al
1)
Quadrieren ist ein zyklischer rechtsschift der Elemente eines Elements des Erweiterungskörpers. [mm] A=(a_{0},a_{1},...a_{m-1}) [/mm] -- > [mm] A^{2}= (a_{m-1},a_{0},a_{1},...a_{m-2}).
[/mm]
Gilt das nur für Erweiterungskörper über den Basiskörper [mm] F_{2}? [/mm] Oder allgemein?
Wie verhält sich das für [mm] A^x [/mm] statt [mm] A^2?
[/mm]
2)
Eine Frage bezüglich der Multiplikation von zwei Elementen des Erweiterungskörpers: A*B=C. wie ergeben sich genau die Koeffizienten [mm] c_{i}? [/mm]
Man verwendet eine Multiplikationsmatrix [mm] \lambda_{ij} [/mm] (s). Wie ergibt sich diese Matrix denn? Die Elemente der Matrix sind ja [mm] \in [/mm] Basiskörper.
Schon die Eingangsformel verwirrt mich etwas (Q2: letzte Zeile auf Seite 3)
[mm] ß^{2^{i}}ß^{2^{j}} [/mm] = [mm] \summe_{s=0}^{m-1} \lamda_{ij} [/mm] (s) [mm] *ß^{2^{}s}.
[/mm]
Warum [mm] ß^{2^{i}}ß^{2^{j}} [/mm] ? Sollte die Basis ß nicht irgendwie immer gleich sein?
3) Der Multiplikationsalgorithmus von Mullin und O., kennt jemand einen gute Quelle, wo dieser beschrieben wird? viele verweisen darauf, aber den konkreten Algorithmus habe ich noch nicht gefunden..
Viele Grüße
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:41 Do 29.11.2012 | | Autor: | Tim87 |
Nachtrag:
ich habe nichts zur Addition von Elementen in Normalbasendarstellugn gefunden - gibt es hierzu ein gutes Paper o.ä.?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:32 So 02.12.2012 | | Autor: | felixf |
Moin!
> Nachtrag:
> ich habe nichts zur Addition von Elementen in
> Normalbasendarstellugn gefunden - gibt es hierzu ein gutes
> Paper o.ä.?
Dazu braucht's kein Paper, da es trivial ist. Du hast eine Basis des Vektorraums - naemlich passende Potenzen eines Elements - und alle Elemente sind Linearkombinationen dieser Basiselemente. Wenn du zwei solche Linearkombinationen addierst, kannst du einfach die Koeffizienten vom gleichen Basiselement zusammenaddieren.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 11:30 Mo 03.12.2012 | | Autor: | Tim87 |
okay, und das addieren ist dann bezüglich mod (Charakteristk des Basiskörpers), oder? :)
lg
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:20 Mi 05.12.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:43 So 02.12.2012 | | Autor: | felixf |
Moin!
> ich habe 3 Fragen zur Arithmetik von Normalbasen. Ich habe
> ca. 20 Quellen gelesen, darunter:
>
> -[Q1] Normal Bases over Finite Fields von Shuhong Gao
> -[Q2] Software Multiplication using Normal Bases von
> Ricardo Dahab et.al
Hast du Links dazu?
> 1)
> Quadrieren ist ein zyklischer rechtsschift der Elemente
> eines Elements des Erweiterungskörpers.
> [mm]A=(a_{0},a_{1},...a_{m-1})[/mm] -- > [mm]A^{2}= (a_{m-1},a_{0},a_{1},...a_{m-2}).[/mm]
>
> Gilt das nur für Erweiterungskörper über den
> Basiskörper [mm]F_{2}?[/mm] Oder allgemein?
Das gilt nur ueber [mm] $\IF_2$, [/mm] wenn man eine Normalbasis ueber [mm] $\IF_2$ [/mm] hat (und nicht eine allgemeinere Erweiterung in Charakteristik 2).
> Wie verhält sich das für [mm]A^x[/mm] statt [mm]A^2?[/mm]
Nun, wenn du die ![[]](/images/popup.gif) square-and-multiply-Methode verwendest, kannst du sehr schnell quadrieren (aber multiplizieren ist nicht ganz so einfach). Wenn $x$ eine Potenz von 2 ist, dann geht es eben sehr schnell.
Wenn du in Charakteristik $p$ bist (also ueber [mm] $\IF_p$, [/mm] mit $p$ Primzahl), dann ist Potenzieren mit $p$ ein solcher Rechtsshift. Das Quadrieren ist also nur dann ein Rechtsshift, wenn $p = 2$ ist.
> 2)
> Eine Frage bezüglich der Multiplikation von zwei
> Elementen des Erweiterungskörpers: A*B=C. wie ergeben sich
> genau die Koeffizienten [mm]c_{i}?[/mm]
(Ich schreib jetzt allgemein $p$, bei dir ist immer $p = 2$.)
Es ist ja $A = [mm] \sum_{i=0}^{k-1} a_i \beta^{p^i}$ [/mm] und $B = [mm] \sum_{j=0}^{k-1} b_i \beta^{p^i}$, [/mm] wobei [mm] $a_0, \dots, a_{k-1}$ [/mm] das Element $A$ beschreibt und [mm] $b_0, \dots, b_{k-1}$ [/mm] das Element $B$ beschreibt.
Nun ist $A B = [mm] \sum_{i=0}^{k-1} \sum_{j=0}^{k-1} a_i b_j \beta^{p^i + p^j}$.
[/mm]
Wenn du jetzt [mm] $\beta^{p^i} \cdot \beta^{p^j}$ [/mm] in der Form [mm] $\sum_{\ell=0}^{k-1} \lambda_{i,j,\ell} \beta^{p^\ell}$ [/mm] darstellen kannst, dann ist $A B = [mm] \sum_{\ell=0}^{k-1} \biggl( \sum_{i=0}^{k-1} \sum_{j=0}^{k-1} a_i b_j \lambda_{i,j,\ell} \biggr) \beta^\ell$. [/mm] Damit siehst du, wie du die Koeffizienten von $C = A [mm] \cdot [/mm] B$ berechnen kannst.
> Man verwendet eine Multiplikationsmatrix [mm]\lambda_{ij}[/mm] (s).
Das was ich oben mit [mm] $\lambda_{i,j,\ell}$ [/mm] bezeichne, ist wohl das was du mit [mm] $\lambda_{ij}(\ell)$ [/mm] meinst.
> Wie ergibt sich diese Matrix denn? Die Elemente der Matrix
> sind ja [mm]\in[/mm] Basiskörper.
Das haengt vom Minimalpolynom von [mm] $\beta$ [/mm] (also dem definierenden Polynom von [mm] $\beta$) [/mm] ab.
> Schon die Eingangsformel verwirrt mich etwas (Q2: letzte
> Zeile auf Seite 3)
> [mm]ß^{2^{i}}ß^{2^{j}}[/mm] = [mm]\summe_{s=0}^{m-1} \lamda_{ij}[/mm] (s)
> [mm]*ß^{2^s}.[/mm]
Das ist genau das, was ich oben auch hatte.
> Warum [mm]ß^{2^{i}}ß^{2^{j}}[/mm] ? Sollte die Basis ß nicht
> irgendwie immer gleich sein?
Die Basis ist ja gleich. Du willst nun das "beliebige" Element [mm] $\beta^{2^i} \cdot \beta^{2^j}$ [/mm] bzgl. der Basis [mm] $\beta^0, \dots, \beta^{m-1}$ [/mm] darstellen.
(Bei mir oben ist $k$ das, was du hier als $m$ bezeichnest.)
> 3) Der Multiplikationsalgorithmus von Mullin und O., kennt
Meinst du den Algorithmus von Mullin et al? Oder was meinst du mit "O."?
> jemand einen gute Quelle, wo dieser beschrieben wird? viele
> verweisen darauf, aber den konkreten Algorithmus habe ich
> noch nicht gefunden..
Ist es vielleicht der Algorithmus, der in "R. Mullin, I. Onyszchuk, S. Vanstone, and R. Wilson. Optimal normal bases in GF(pn ). Discrete Applied Mathematics, 22:149–161, 1988." beschrieben wird? Such doch mal explizit nach diesem Paper, z.B. in der Uni-Bibliothek bei den Zeitschriften.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:28 Mo 03.12.2012 | | Autor: | Tim87 |
Hallo,
danke für deine Antwort. mir wurde einiges klarer -
> Moin!
>
> > ich habe 3 Fragen zur Arithmetik von Normalbasen. Ich habe
> > ca. 20 Quellen gelesen, darunter:
> >
> > -[Q1] Normal Bases over Finite Fields von Shuhong Gao
> > -[Q2] Software Multiplication using Normal Bases von
> > Ricardo Dahab et.al
>
> Hast du Links dazu?
http://www.google.de/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CDcQFjAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.67.2965%26rep%3Drep1%26type%3Dpdf&ei=_ne8UOeSDczb4QTms4CgBw&usg=AFQjCNHXjWyhNivV3e-ez9HZb-cAbshKzQ&sig2=k-rQhNsdmRDuuWzjcY5goQ
und
http://cacr.uwaterloo.ca/techreports/2004/cacr2004-12.pdf
>
> > 1)
> > Quadrieren ist ein zyklischer rechtsschift der Elemente
> > eines Elements des Erweiterungskörpers.
> > [mm]A=(a_{0},a_{1},...a_{m-1})[/mm] -- > [mm]A^{2}= (a_{m-1},a_{0},a_{1},...a_{m-2}).[/mm]
>
> >
> > Gilt das nur für Erweiterungskörper über den
> > Basiskörper [mm]F_{2}?[/mm] Oder allgemein?
>
> Das gilt nur ueber [mm]\IF_2[/mm], wenn man eine Normalbasis ueber
> [mm]\IF_2[/mm] hat (und nicht eine allgemeinere Erweiterung in
> Charakteristik 2).
>
> > Wie verhält sich das für [mm]A^x[/mm] statt [mm]A^2?[/mm]
>
> Nun, wenn du die
> square-and-multiply-Methode
> verwendest, kannst du sehr schnell quadrieren (aber
> multiplizieren ist nicht ganz so einfach). Wenn [mm]x[/mm] eine
> Potenz von 2 ist, dann geht es eben sehr schnell.
>
> Wenn du in Charakteristik [mm]p[/mm] bist (also ueber [mm]\IF_p[/mm], mit [mm]p[/mm]
> Primzahl), dann ist Potenzieren mit [mm]p[/mm] ein solcher
> Rechtsshift. Das Quadrieren ist also nur dann ein
> Rechtsshift, wenn [mm]p = 2[/mm] ist.
>
ok, dass hatte ich in einem Paper falsch verstanden, ich dachte das wäre allgemein für eine Chara. des Basiskörpers - danke ;>
> > 2)
> > Eine Frage bezüglich der Multiplikation von zwei
> > Elementen des Erweiterungskörpers: A*B=C. wie ergeben sich
> > genau die Koeffizienten [mm]c_{i}?[/mm]
>
> (Ich schreib jetzt allgemein [mm]p[/mm], bei dir ist immer [mm]p = 2[/mm].)
>
> Es ist ja [mm]A = \sum_{i=0}^{k-1} a_i \beta^{p^i}[/mm] und [mm]B = \sum_{j=0}^{k-1} b_i \beta^{p^i}[/mm],
> wobei [mm]a_0, \dots, a_{k-1}[/mm] das Element [mm]A[/mm] beschreibt und [mm]b_0, \dots, b_{k-1}[/mm]
> das Element [mm]B[/mm] beschreibt.
>
> Nun ist [mm]A B = \sum_{i=0}^{k-1} \sum_{j=0}^{k-1} a_i b_j \beta^{p^i + p^j}[/mm].
ok, dass habe ich verstanden
>
> Wenn du jetzt [mm]\beta^{p^i} \cdot \beta^{p^j}[/mm] in der Form
> [mm]\sum_{\ell=0}^{k-1} \lambda_{i,j,\ell} \beta^{p^\ell}[/mm]
> darstellen kannst, dann ist [mm]A B = \sum_{\ell=0}^{k-1} \biggl( \sum_{i=0}^{k-1} \sum_{j=0}^{k-1} a_i b_j \lambda_{i,j,\ell} \biggr) \beta^\ell[/mm].
> Damit siehst du, wie du die Koeffizienten von [mm]C = A \cdot B[/mm]
> berechnen kannst.
>
also jedes [mm] c_{i} [/mm] wird quasi in dem äußeren Summenzeichen dargestellt- ok
> > Man verwendet eine Multiplikationsmatrix [mm]\lambda_{ij}[/mm] (s).
>
> Das was ich oben mit [mm]\lambda_{i,j,\ell}[/mm] bezeichne, ist wohl
> das was du mit [mm]\lambda_{ij}(\ell)[/mm] meinst.
>
> > Wie ergibt sich diese Matrix denn? Die Elemente der Matrix
> > sind ja [mm]\in[/mm] Basiskörper.
>
> Das haengt vom Minimalpolynom von [mm]\beta[/mm] (also dem
> definierenden Polynom von [mm]\beta[/mm]) ab.
>
wie ergibt sich genau lamda i,j,l ? würde ich einfach den Koeffizient bzw. das Element [mm] a_{i} [/mm] und das Element [mm] b_{i} [/mm] an der entsprechenden Stelle nehmen und mit einander multiplizieren im Basisvektorraum sozusagen?
> > Schon die Eingangsformel verwirrt mich etwas (Q2: letzte
> > Zeile auf Seite 3)
> > [mm]ß^{2^{i}}ß^{2^{j}}[/mm] = [mm]\summe_{s=0}^{m-1} \lamda_{ij}[/mm]
> (s)
> > [mm]*ß^{2^s}.[/mm]
>
> Das ist genau das, was ich oben auch hatte.
>
> > Warum [mm]ß^{2^{i}}ß^{2^{j}}[/mm] ? Sollte die Basis ß nicht
> > irgendwie immer gleich sein?
>
> Die Basis ist ja gleich. Du willst nun das "beliebige"
> Element [mm]\beta^{2^i} \cdot \beta^{2^j}[/mm] bzgl. der Basis
> [mm]\beta^0, \dots, \beta^{m-1}[/mm] darstellen.
>
> (Bei mir oben ist [mm]k[/mm] das, was du hier als [mm]m[/mm] bezeichnest.)
>
> > 3) Der Multiplikationsalgorithmus von Mullin und O., kennt
>
> Meinst du den Algorithmus von Mullin et al? Oder was meinst
> du mit "O."?
>
> > jemand einen gute Quelle, wo dieser beschrieben wird? viele
> > verweisen darauf, aber den konkreten Algorithmus habe ich
> > noch nicht gefunden..
>
> Ist es vielleicht der Algorithmus, der in "R. Mullin, I.
> Onyszchuk, S. Vanstone, and R. Wilson. Optimal normal bases
> in GF(pn ). Discrete Applied Mathematics, 22:149–161,
> 1988." beschrieben wird? Such doch mal explizit nach diesem
> Paper, z.B. in der Uni-Bibliothek bei den Zeitschriften.
ja genau den meine ich
>
> LG Felix
>
super, danke ;)
lg tim
|
|
|
|
