Basic primitive Polynomials < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:55 Fr 15.08.2014 | | Autor: | Cebalrai |
Ich hoffe, dass ich an die richtige Stelle poste, bin neu hier. Zu meinem Problem:
Ich möchte analog zum folgenden Paper die MUBs konstuieren, wobei das einzige verbliebene Problem darin besteht, dass ich für beliebige Dimensionen das "basic primitive polynomial" zu meinem Galoisring GR(4,n) herankommen muss.
URL: http://arxiv.org/pdf/quant-ph/0409081.pdf
Der für mein Problem relevante Teil ist auf Seite 7 unten.
Das Paper hier gibt dabei einen Ansatz für die Polynome h(x), bei dem ich auf nichts gescheites komme. Insbesondere weiß ich nicht, wie ich die Information mit dem gegebenen Kreisteilungspolynom einfließen lassen soll.
Falls mir jemand den Ansatz dort ausführlicher anhand eines nicht trivialen Beispiels erklären könnte oder einen ganz anderen Ansatz zu bieten hat, wär ich sehr dankbar.
Mfg
PS:
Habe eigentlich absolut keine Ahnung von Algebra und Galoistheorie. Komme aber leider gerade schlecht drumherum.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:27 Sa 16.08.2014 | | Autor: | felixf |
Moin!
> Ich hoffe, dass ich an die richtige Stelle poste, bin neu
> hier. Zu meinem Problem:
> Ich möchte analog zum folgenden Paper die MUBs
> konstuieren, wobei das einzige verbliebene Problem darin
> besteht, dass ich für beliebige Dimensionen das "basic
> primitive polynomial" zu meinem Galoisring GR(4,n)
> herankommen muss.
> URL: http://arxiv.org/pdf/quant-ph/0409081.pdf
>
> Der für mein Problem relevante Teil ist auf Seite 7
> unten.
> Das Paper hier gibt dabei einen Ansatz für die Polynome
> h(x), bei dem ich auf nichts gescheites komme. Insbesondere
> weiß ich nicht, wie ich die Information mit dem gegebenen
> Kreisteilungspolynom einfließen lassen soll.
> Falls mir jemand den Ansatz dort ausführlicher anhand
> eines nicht trivialen Beispiels erklären könnte oder
> einen ganz anderen Ansatz zu bieten hat, wär ich sehr
> dankbar.
Also. Du faengst ja an mit einem Polynom [mm] $h_2 \in (\IZ/2\IZ)[x]$ [/mm] von Grad $m$, welches irreduzibel und primitiv (d.h. die Restklasse von $x$ in [mm] $(\IZ/2\IZ)[x]/(h_2)$ [/mm] hat die maximal moegliche Ordnung, naemlich [mm] $2^m [/mm] - 1$) ist. Die Bednigung, dass $h$ primitiv ist, ist aequivalent zu $h [mm] \mid (x^r [/mm] - 1)$ und $h [mm] \nmid (x^\ell [/mm] - 1)$ fuer $0 < [mm] \ell [/mm] < r$ (hier ist $r = [mm] 2^m [/mm] - 1$ wie im Preprint).
Du suchst jetzt ein $h [mm] \in (\IZ/4\IZ)[x]$, [/mm] welches ebenfalls Grad $m$ hat, kongruent zu [mm] $h_2$ [/mm] ist modulo $2$, und welches $h [mm] \mid (x^r [/mm] - 1)$ erfuellt (in [mm] $(\IZ/4\IZ)[x]$).
[/mm]
Da es (bis auf Vielfache mit Einheiten) [mm] $2^m$ [/mm] Kandidaten $h$ gibt, die Grad $m$ haben und $h [mm] \equiv h_2 \pmod{2}$ [/mm] erfuellen, kannst du bei "kleinen" Werten von $m$ (sagen wir $< 20$) alle Moeglichkeiten einfach durchprobieren. Ist nicht schoen, aber schnell und einfach zu implementieren 
Ansonsten kannst du auch einfach das Paper weiterlesen: da steht naemlich, wie man sehr einfach (!) von [mm] $h_2$ [/mm] auf $h$ kommen kann. Und zwar schreibt man [mm] $h_2 [/mm] = e(x) - d(x)$, so dass $e$ nur gerade Potenzen von $x$ und $d$ nur ungerade Potenzen von $x$ hat. Dann gilt (laut dem Preprint) [mm] $h(x^2) \equiv \pm (e(x)^2 [/mm] - [mm] d(x)^2) \pmod{4}$. [/mm] Und aus [mm] $h(x^2)$ [/mm] kannst du $h(x)$ direkt ablesen. Das kannst du also in [mm] $O(m^2)$ [/mm] Operationen ausrechnen -- was wesentlich weniger als [mm] $O(2^m)$ [/mm] von der Methode oben.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:34 Sa 16.08.2014 | | Autor: | Cebalrai |
Das [mm] $h_2$ [/mm] fehlt mir ja aber auch.
Mit der Annahme allgemeinen Koeffizienten kam ich mit den Forderungen aus dem Absatz rund um $h(x)$ und [mm] $h_2(x)$ [/mm] eben nur auf wahre Aussagen bezüglich einiger unbestimmter Koeffizienten.
Ich hab dabei auch den Ansatz mit [mm] $h(x^2)=\pm (e^2(x)-d^2(x))$ [/mm] angewandt und bin einfach mit einem allgemeinen [mm] $h_2(x)$ [/mm] reingegangen und habe versucht über die Bedingungen die Koeffizienten für h(x) rauszubekommen.
Zum Ansatz mit dem Durchprobieren:
Beim Überprüfen, ob $h(x)$ hier [mm] §x^r-1§ [/mm] im [mm] $\frac{\IZ}{4\IZ}\[x\]$ [/mm] teilt, da ist doch egal, wann ich modulo 4 anwende, oder? Ob schon unterwegs beim Ausrechnen oder erst auf das Endergebnis, richtig? Die Polynomdivision kann ich also durchführen wie über dem [mm] $\IR$ [/mm] und [mm] $\IC$ [/mm] oder ist da irgendeine Kleinigkeit noch zu beachten?
Dann weiß ich auch überhaupt nicht, wie ich mit so Begriffen wie die Restklasse von $x$ in $ [mm] (\IZ/2\IZ)[x]/(h_2) [/mm] $ in der Rechnung dann umgehen soll.
In den Denkweisen hier in Algebra steck ich einfach überhaupt (noch) nicht drin .... Die Vorlesung(en) hören werd ich aber wohl irgendwann mal noch.
Vielen Dank schonmal ^^
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:46 Sa 16.08.2014 | | Autor: | felixf |
Moin!
> Das [mm]h_2[/mm] fehlt mir ja aber auch.
Nimm zufaellig ein normiertes Polynom [mm] $h_2$ [/mm] von Grad $m$. Teste ob es irreduzibel ist (das geht ueber endlichen Koerpern recht einfach: dazu muss [mm] $ggT(h_2, X^k [/mm] - X) = 1$ sein fuer jedes $k [mm] \le [/mm] m/2$); dies ist mit Wahrscheinlichkeit ca. $1/m$ der Fall. (Vom Erwartungswert her musst du also im Durchschnitt $m$ Kandidaten testen.)
Dann schaust du zusaetzlich, ob es primitiv ist. Wenn nicht, geht der Spass von vorne los. Um zu testen ob [mm] $h_2$ [/mm] primitiv ist, musst du [mm] $X^k$ [/mm] modulo [mm] $h_2$ [/mm] ausrechnen fuer jedes $k = [mm] \frac{2^m - 1}{p}$, [/mm] wobei du fuer $p$ jede Primzahl einsetzen musst, die ein Teiler von [mm] $2^m [/mm] - 1$ ist. (Dazu musst du [mm] $2^m [/mm] - 1$ faktorisieren.) Wenn fuer jedes solche $k$ das Ergebnis [mm] $X^k \bmod h_2$ [/mm] nicht gleich $1$ ist, ist dein [mm] $h_2$ [/mm] primitiv. (Effizient kannst du [mm] $X^k \bmod h_2$ [/mm] mit ![[]](/images/popup.gif) binaerer Exponentiation ausrechnen.)
Damit solltest du relativ effizient ein passendes Polynom [mm] $h_2$ [/mm] finden, wenn $m$ nicht zu gross ist. (Wenn $m$ gross ist, konsultiere ein gutes Buch zur Computeralgebra.)
> Mit der Annahme allgemeinen Koeffizienten kam ich mit den
> Forderungen aus dem Absatz rund um [mm]h(x)[/mm] und [mm]h_2(x)[/mm] eben nur
> auf wahre Aussagen bezüglich einiger unbestimmter
> Koeffizienten.
Nun, die Koeffizienten von [mm] $h_2$ [/mm] kennst du ja konkret (nachdem du es gefunden hast). Damit kannst du konkrete Koeffizienten von $e$ und $d$ hinschreiben, und somit auch konkret [mm] $h(x^2)$.
[/mm]
> Ich hab dabei auch den Ansatz mit [mm]h(x^2)=\pm (e^2(x)-d^2(x))[/mm]
> angewandt und bin einfach mit einem allgemeinen [mm]h_2(x)[/mm]
> reingegangen und habe versucht über die Bedingungen die
> Koeffizienten für h(x) rauszubekommen.
Warum so kompliziert?
> Zum Ansatz mit dem Durchprobieren:
> Beim Überprüfen, ob [mm]h(x)[/mm] hier [mm]§x^r-1§[/mm] im
> [mm]\frac{\IZ}{4\IZ}\[x\][/mm] teilt, da ist doch egal, wann ich
> modulo 4 anwende, oder? Ob schon unterwegs beim Ausrechnen
> oder erst auf das Endergebnis, richtig?
Ja, solange du es am Schluss nocheinmal machst. Es hat allerdings einen grossen Vorteil, das nach (fast) jedem Schritt zu machen: damit bleiben die Koeffizienten klein!
> Die Polynomdivision
> kann ich also durchführen wie über dem [mm]\IR[/mm] und [mm]\IC[/mm] oder
> ist da irgendeine Kleinigkeit noch zu beachten?
Wenn dein Polynom, modulo dem du rechnest, nicht normiert ist, musst du mit Inversen modulo $4$ arbeiten. Also sorg dafuer, dass [mm] $h_2$ [/mm] und $h$ normiert sind 
> Dann weiß ich auch überhaupt nicht, wie ich mit so
> Begriffen wie die Restklasse von [mm]x[/mm] in [mm](\IZ/2\IZ)[x]/(h_2)[/mm]
> in der Rechnung dann umgehen soll.
> In den Denkweisen hier in Algebra steck ich einfach
> überhaupt (noch) nicht drin .... Die Vorlesung(en) hören
> werd ich aber wohl irgendwann mal noch.
Wenn du [mm] $\IZ/\ell\IZ$ [/mm] hast fuer irgendeine Zahl [mm] $\ell$, [/mm] dann mach alle Zahlen die auftreten nach jeder Rechnung modulo [mm] $\ell$, [/mm] damit sie in $0, 1, [mm] \dots, \ell-1$ [/mm] liegen. Das reicht im Prinzip schon aus
LG Felix
|
|
|
| |
|
Eingabefehler: "\left" und "\right" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "\left" und "\right" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Hallo.
Ich habe mittlerweile alles so, wie es wohl sein soll, implementiert und hab mich damit mittlerweile auf die absolute brute-force-Methodik hinabbegeben, aber es kommen einfach zu viele $h(x)$ am Ende dabei raus.
Was mein Programm der Reihe nach tut:
1. Irreduzible Polynome in $\frac{\IZ}{2\IZ}\right[ x\left]$ bestimmen, indem ich iterativ in den Dimensionen bis zu $m$ hochgehe. Start ist dabei mit Dimension 2 und den kleineren irreduziblen Polynomen $x$ und $x+1$. Dann vergleiche ich eine Liste aller Möglicher Polynome mit einer, die alle Polynome enthält, die ich aus den kleineren irreduziblen zusammenmultiplizieren kann.
2. Diese Kandidaten für $h_2$ auf Teilbarkeit bzgl. $x^r-1$ mit $r=2^m-1$ überprüfen, jeweils modulo 2.
3. Für alle $h_2$ mttels des Ansatzes aus dem Paper das zugehörige $h(x)$ mittels des Ansatzes $h(x^2)=\pm(e^2(x) - d^2(x))$ berechnen, wobei $e(x)$ der gerade Anteil von $h_2(x)$ und $d(x)$ der ungerade.
4. Die erhaltenen $h(x)$ werden dann auf Teilbarkeit bzgl. $x^r-1$ und Unteilbarkeit auf $x^\ell-1$ mit $grad(H)<\ell<r$ überprüft, alles modulo 4.
Die Bedingung, dass $h(x)=h_2(x) mod 2$ erfüllt die Berechnungsvorschrift unter (3) automatisch. Scheinbar auch die Kreisteilung für $x^r-1$. Durch die Überprüfung der $\ell$s scheiden aber nur sehr wenige Kandidaten aus.
Somit habe ich kein "unique" basic primitive Polynomial sondern mehrere. Beispielsweise für $m=4$ sind es 2 (bei 3 $h_2$-Kandidaten) und für $m=9$ sind es 48 (bei 56 $h_2$-Kandidaten).
Hab ich irgendwo eine relevante Bedingung unterschlagen oder muss da irgendwo ein Fehler im Algorithmus sein?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:20 Fr 12.09.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
