www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Gruppe, Ring, Körper" - Basic primitive Polynomials
Basic primitive Polynomials < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Gruppe, Ring, Körper"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Basic primitive Polynomials: Frage zu GR(4,n)
Status: (Frage) beantwortet Status 
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.



        
Bezug
Basic primitive Polynomials: Antwort
Status: (Antwort) fertig Status 
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




Bezug
                
Bezug
Basic primitive Polynomials: Rückfrage
Status: (Frage) beantwortet Status 
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 ^^

Bezug
                        
Bezug
Basic primitive Polynomials: Antwort
Status: (Antwort) fertig Status 
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 []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


Bezug
        
Bezug
Basic primitive Polynomials: Problem
Status: (Frage) überfällig Status 
Datum: 13:03 Mi 10.09.2014
Autor: Cebalrai

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?

Bezug
                
Bezug
Basic primitive Polynomials: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 13:20 Fr 12.09.2014
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Gruppe, Ring, Körper"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]