Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

irreduzible Polynome gesucht
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> irreduzible Polynome gesucht
 
Autor Nachricht
xytrath
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 02.07.2005
Beiträge: 45

BeitragVerfasst am: 08 Jul 2005 - 14:56:32    Titel: irreduzible Polynome gesucht

Hallo Leutchens,

Da meine Frage nach Berechnungen im endlichen Körper in diesem Forum recht gut beantwortet wurde, möchte ich heute gern folgendes wissen:

Kennt jemand ne seite, auf der ich ne liste mit irreduziblen polynomen
für endliche körper GF(p^k)

p: primzahl
k: natürliche zahl > 1

sagen wir für alle n <= 3^4 finde?

also für
2^2 2^3 2^4 2^5 2^6
3^2 3^3 3^4
5^2
7^2


beziehungsweise:

kann mir einer sagen, wie ich selber auf jeweils genau ein irreduzibles polynom komme?

und am besten wäre es noch, wenn mir einer erklären könnte, wie ich das dann programmtechnisch realisiere, dass
zb, dass bei dem irred. polyn. x^3+x+1 mein prog weiß, dass es x^3 durch x+1 zu ersetzen hat?

Ich weiß, sind viele fragen auf einmal.

Hoffe ihr könnt mir n bissl helfen.

Will das nämlich noch in meine diplarbeit einbringen, aber weiss nicht so recht weiter.

Hab jetzt mittlerweile die Polynome gefunden, hab nur noch ein Problem: Wie kann ich das programmieren, dass z.B:
x^3=x+1 ist? Ich nehme an, dass das über die binärzahlen geht, aber wie mache ich das zB mit C++? ich finde da keine binäre rechenweise, auch nicht in der MSDN library
und wie rechne ich binär 100*100 aus?

müsste ja theoretisch 100*100=1000*10=0011*10=0110 sein.





Gruß
xytrath
yushoor
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 05.07.2005
Beiträge: 517

BeitragVerfasst am: 08 Jul 2005 - 21:45:46    Titel:

zum programmieren musst du ja nicht mit polynomen arbeiten, da kannst du diese mit zahlen ersetzen und dann einfach modulo rechnen.
zb ist der körper (als faktorring) (Z/2Z)[X]/(x^3+x+1), den du wohl irgendwie mit GF bezeichnest, isomorph zu (Z/2Z)^3. du musst also einfach nur die elemente aus GF mit den entsprechenden vektoren aus (Z/2Z) identifizieren und dann kannst du damit programmieren.

nach dem prinzip:
- polynom eingeben
- in zahlen umwandeln
- irgendwas damit rechnen
- wieder zurück umwandeln in polynom
- ergebnis-polynom ausgeben

zu der frage, wie man mit binärzahlen rechnet: dir sollte bewusst sein, dass intern immer binär gerechnet wird. nur die ausgabe als integer (oder sonstiges format) wird halt dir zuliebe im schönen dezimalsystem ausgegeben. im speicher liegen die zahlen natürlich im binärsystem vor. du mußt also einfach nur direkt auf den speicher zugreifen, um an die einzelnen bits zu kommen.
xytrath
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 02.07.2005
Beiträge: 45

BeitragVerfasst am: 09 Jul 2005 - 10:14:26    Titel:

Hallo yushoor,

danke für die recht präzise antwort. hat mir schon ein wenig weiter geholfen.

Lassen wir aber erst mal das mit dem speicherzugriff weg. Wink

sagen wir ich möchte die elemente des 2^3 ermitteln und möchte doch lieber mit dezimalzahlen rechnen.

diese elemente habe ich mir überlegt müssten zwar genauso aussehen wie die binärzahlen, nur dass sie trotzdem dez sind:

also 0, 1, 10, 11, 100, 101, 110, 111, alle dezimal dargestellt mein problem ist jetzt:

Wie generiere ich mir diese zahlen?

mit denen würde das ganze wunderschön funktionieren

bsp 11 + 11 = 22 würde ich dann die 2en in 0en umwandeln und hätte das richtige ergebnis

bsp 10*11 = 110: auch das is korrekt. bei überlauf würde ich dann einfach die rechenregel nach dem polynom anwenden:

also, vereinfachtes beispiel:
wenn zahl/1000 >0, dann zahl minus 1000 und + 11

bei zahl > 10000 müsste ich halt schauen, dass ich das dann in 1000*10 umwandle und die 1000 umforme.

das ist also alles kein problem, wenn ich doch nur auf die zahlen kommen würde.

hab schon einiges versucht, aber komme nur auf 0, 1, 10, 11, 100, 101, 1000, 1001, aber so will ich das ja nicht. Sad erbitte noch einmal rat Wink.

gruß
xytrath

ein anderes noch viel größeres problem wären dann die trinärzahlen, für 3^3, also 0, 1, 2, 10, 11, 12,100, 101, 102, 110, 111 usw...
da wird mir jetz schon schlecht Sad.
yushoor
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 05.07.2005
Beiträge: 517

BeitragVerfasst am: 09 Jul 2005 - 11:37:21    Titel:

ich würde das nicht mit zahlen sondern mit vektoren machen. ok zugegeben, dann musst du etwas mehr aufwand betreiben und selbst operationen +,-,* schreiben, aber das sollte gehen.
nimmst also statt einer zahl beim körper mit p^n elementen einen vektor mit n elementen (array oder sowas), und dann willst du zb 2 davon addieren:
(a_1,a_2,...,a_n)+(b_1,b_2,...,b_n)=(a_1+b_1 mod p,a_2+b_2 mod p,...,a_n+b_n mod p)
multiplizieren ist etwas komplizierter: als beispiel für n=2 für das polynom x^2+x+1
(a_1,a_2)*(b_1,b_2)=(a_1b_2+a_2b_1+a_1b_1 mod p,a_2b_2+a_1b_1 mod p)
wie kommt man darauf?
einfach wieder in polynome ersetzen und koeffizientenvergleich machen.
(a_1,a_2) => a_1*x+a_2
=> (a_1*x+a_2)*(b_1*x+b_2)=a_1*a_2*x^2+x*(a_1*b_2+a_2*b_1)+a_2*b_2
x^2 durch x+1 ersetzen ergibt dann das ergebnis.
das ganze geht auch allgemeiner für ein gegebenes polynom (gegeben durch einen vektor der koeffizienten).

mit dezimalzahlen zu rechnen finde ich zu umständlich. da kannst du ja nur sehr schwer auf die einzelnen ziffern zugreifen, und sie ändern.
xytrath
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 02.07.2005
Beiträge: 45

BeitragVerfasst am: 09 Jul 2005 - 12:57:28    Titel:

Also ich denke das habe ich soweit verstanden.

das ganze mit vektoren zu machen, hatte ich auch schon mal kurz überlegt, aber dann wieder verworfen. schwer zu realisieren is das allerdings wirklich nicht.

jetzt muss ich nur noch die routinen für allgemeine länge finden, aber das pack ich schon, denk ich.

hab aber nur noch 10 tage zeit, dann will(muss) ich meine diplarbeit abgeben :/

den rest (theorien und so weiter) hab ich aber wenigstens schon komplett fertig^^.

also vielen dank nochma @yushoor
falls noch fragen auftreten, weiss ich ja, an wen ich mich wenden kann Wink.

gruß
xytrath
xytrath
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 02.07.2005
Beiträge: 45

BeitragVerfasst am: 09 Jul 2005 - 19:00:07    Titel:

Wollte nur ma nen kurzen Lagebericht durchgeben:

Hab jetzt folgendes gemacht:

gegeben sei ordnung p^k

für k = 1 gebe ich einfach alle operationstafeln aij = bl*i+j
für bl = 1, ..., p an.

für k > 1 wird ein 2dim feld generiert

mit den maßen [p^k][k]

soll heissen Element[r][s].
das sind erst mal nur die elemente die miteinander operieren

die addition funktioniert immerhin schon, war aber n hartes stück arbeit auf die bildung der elemente zu kommen.
hab ewig probiert, bis ich hier grad nochmal nachfragen wollte und bei der niederschrift gemerkt hab, dass
Element[r][s] = (r/p^s)%p ist. Smile

<= stolz ist Very Happy.

jetzt fehlt nur noch die multiplikation, aber mit deinen vorgaben schaff ich auch das Wink.

gruß
xytrath
xytrath
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 02.07.2005
Beiträge: 45

BeitragVerfasst am: 10 Jul 2005 - 21:15:57    Titel:

ich bins ma wieder Wink.

so hab jetzt für die ordnungen

2^2
2^3
2^4
3^2
3^3
3^4
5^2
7^2

das alles programmiert.

aber nur für ein festes irreduzibles polynom

jetzt würde ich das ganze aber ganz gern variabel gestalten, also mit einem polynom, was der anwender vorgibt.

hier nur mal als beispiel für 2^2 und 3^2 mein code:

Zitat:
if((GROESSEJ==4)||(GROESSEJ==9)){

o_a = (_E[b_r][0]*E[o_i][0]+ //o_a=x^0
_______E[b_r][1]*E[o_i][1])%gfbasis;

o_b = ( E[b_r][1]*E[o_i][0]+ //o_b=x^1
_______E[b_r][0]*E[o_i][1]+
_______E[b_r][1]*E[o_i][1]*(gfbasis-1))%gfbasis;
}
//das ist multiplikation von b_r*o_i

if(gfpotenz==2){
o_r = (o_a + E[o_j][0])%gfbasis + gfbasis*((o_b + E[o_j][1])%gfbasis);
//o_r = umgewandeltes element, von b_r*o_i+o_j
}


aber es müsste ja auch allgemein gehen, vielleicht mit minus?

danke fürs reinschauen.

gruß
xytrath
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> irreduzible Polynome gesucht
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum