Diskussion:Primitives Polynom

aus Wikipedia, der freien Enzyklopädie
Letzter Kommentar: vor 11 Jahren von Aragorn321 in Abschnitt .Wiederholung nach 2^m -1
Zur Navigation springen Zur Suche springen

Übersetzung

[Quelltext bearbeiten]

Bitte Übersetzung aus en noch einmal prüfen. So ist z.B. Potenzreihe ein Übersetzungsfehler, auch Saatzahl ist ungewöhnlich.--FerdiBf 20:59, 22. Apr. 2010 (CEST)Beantworten

Der Begriff Saatzahl wird auch in der Literatur verwendet. z.B. [1]. Wikipedia kennt den Begriff Saat im Artikel Zufallszahlengenerator --N. Büchen 22:40, 22. Apr. 2010 (CEST)Beantworten

Beispiele für primitive Polynome geben

[Quelltext bearbeiten]

Leider erschlisst sich mir aus dem Artikel nicht, was ein primitives Polynom sein soll. Vielleicht könnte man einfach ein paar Beispiele geben, oder eine Bildungsvorschrift ala "ax**i + bx**j + bx**k + mit a, b, c, ... und i, j, k ... so, dass ..."? (nicht signierter Beitrag von 87.185.76.112 (Diskussion) 17:27, 4. Feb. 2011 (CET)) Beantworten

Zum Beispiel im Erweiterungskörper F24, der durch das irreduzible Polynom f(x) = x4+x1+x0 (oder mit seiner Binärdarstellung (10011)) erzeugt wird, ist das Polynom g(x) = x1 also kurz g(x) = x ein Generator, welches alle anderen Polynome dieses Erweiterungskörpers durch fortgesetze Multiplikation erzeugen kann. Weil x ein Generator für alle Elemente der maximalen multiplikativen Gruppe maxG* in F24 ist, heißt das Polynom f(x) dann primitives Polynom. Die Ordnung des Erweiterungskörpers ord(F24) = 24 = 16, die Ordnung der zugehörigen maximalen multiplikativen Gruppe ist dann ord(maxG*) = (24 - 1) = 15 und enthält alle Nicht-Null-Polynome p(x) mit einem Grad (n < 4), also mit anderen Worten alle 15 möglichen Bitketten der Länge 4 außer dem Null-Polynom (0000), nämlich {(0001),(0010),(0011),(0100), ... ,(1111)} .

Weitere, vor allen Dingen auch "große" Beispiele für primitive Polynome mit einem Grad (n >= 1024), sollte man in jedem besseren Kryptographielehrbuch finden (und nicht nur dort), welches auch einen Abschnitt über linear rückgekoppelte Schieberegister enthält. Dort sollten dann auch verschiedene (insbesondere auch laufzeiteffiziente) Algorithmen zur Generierung sowohl von irreduziblen Polynomen als auch von primitiven Polynomen mit dem jeweils gewünschten Grad aufgeführt werden.--Aragorn321 (Diskussion) 14:01, 8. Dez. 2012 (CET)Beantworten

.Wiederholung nach 2^m -1

[Quelltext bearbeiten]

„Allgemein gilt für ein primitives Polynom des Grades m, dass dieser Vorgang 2m−1 Pseudo-Zufallszahlen erzeugt, bevor die Sequenz sich wiederholt“

Warum nach 2^m -1? --repat 18:01, 6. Jul. 2011 (CEST)Beantworten

Weil jeder Erweiterungskörper der Form Fpm mit p ist eine Primzahl und (m > 1), also auch alle mit (p = 2), die Ordnung pm hat, und somit auch das Null-Polynom enthält. Die zugehörige maximale multiplikative Gruppe maxG* enthält alle Polynome des Erweiterungskörpers außer dem Null-Polynom und hat somit nur noch die Ordnung (pm - 1). Von jedem multiplikativen Generator g können aber durch fortgesetzte Multiplikation mit g stets nur alle Elemente der multiplikativen Gruppe aber niemals das Null-Polynom erzeugt werden. Also ist bei jedem primitiven Polynom des Grades m zwangsweise nach (pm - 1) erzeugten Pseudo-Zufallszahlen das Ende der Sequenz erreicht, siehe auch linear rückgekoppelte Schieberegister.--Aragorn321 (Diskussion) 14:24, 8. Dez. 2012 (CET)Beantworten

Kleiner aber feiner Unterschied zwischen additiven und multiplikativen Gruppen

[Quelltext bearbeiten]

Eine Gruppe G ist genau dann zyklisch, wenn es wenigstens ein Element a dieser Gruppe G gibt, mit dem man durch wiederholte Anwendung der Gruppenoperation (also Addition bei additiven Gruppen, Multiplikation bei multiplikativen Gruppen) alle Elemente dieser Gruppe erzeugen kann. So weit so gut.

Da sich die beiden Operationen Addition und Multiplikation bezüglich ihrer Eigenschaften aber unterscheiden, unterscheiden sich auch die beiden verschiedenen Gruppenarten (also additive und multiplikative Gruppen) voneinander. Das neutrale Element der Addition ist das Null-Element kurz 0, wohingegen das neutrale Element der Multiplikation das Eins-Element kurz 1 ist, denn für das neutrale Element e muss für alle Elemente a der Gruppe G folgendes gelten: gruppen_operation(a,e) = a. Mit anderen Worten das Null-Element muß in jeder zyklischen additiven Gruppe G+ und das Eins-Element muß in jeder zyklischen multiplikativen Gruppe G* enthalten sein. Das bezüglich der Gruppenoperation neutrale Element ist also immer in einer zyklischen Gruppe enthalten.

Etwas anders ist die Situation bei dem sogenannten zu a inversen Element b, für welches gelten muss: gruppen_operation(a,b) = e, wobei e wieder das neutrale Element der Gruppe G und a und b beliebige Elemente einer additiven Gruppe G+ oder einer multiplikativen Gruppe G* sein können. Bei einer additiven Gruppe G+ wäre b = neg(a) oder kurz b = -a, denn a + (-a) = 0 = e, es gibt hier also zu jedem Element aus G+ ein bzgl. der Addition inverses Element. Bei einer multiplikativen Gruppe G* wäre das inverse Element b ja eigentlich b = 1/a, denn nur a * 1/a = 1 = e, aber zum einen existiert die Division als Operation in einer multiplikativen Gruppe G* überhaupt nicht und zum anderen hat nicht jedes Element a in einer muliplikativen Gruppe G* ein inverses Element b.

Als anschauliches Beispiel diene hier der Modulo-Zahlenring mit N=10, also Z10 = {0,1,2,3,4,5,6,7,8,9}, wo z.B. die 9 das inverse Element bezüglich der Addition zu 1 ist (und umgekehrt), also 1 + 9 = 10 mod 10 = 0. Da ggT(1,10) = 1 ist, was übrigens auch für die Zahlen 3,7 und 9 gilt, können auch alle diese Zahlen als additive Generatoren benutzt werden, um durch wiederholte Addition alle Elemente aus Z10 zu erzeugen. Also z.B. G(7,+) in Z10 = {7,4,1,8,5,2,9,6,3,0}. Die Ordnung von 7 bezüglich der Addition in Z10 wäre also gleich 10. Dagegen hat zwar auch die 2 in Z10 ein bezüglich der Addition inverses Element, nämlich die 8, denn 2 + 8 = 10 = 0 mod 10, aber der ggT(2,10) = 2 # 1. Folgerichtig kann die 2 als additiver Generator nicht alle Elemente in Z10 erzeugen, G(2,+) in Z10 = {2,4,6,8,0}. Die Ordnung von 2 bezüglich der Addition in Z10 wäre also nur 5 und nicht 10. Mit anderen Worten die maximale additive Gruppe maxG+ besitzt genauso viele Elemente wie der Zahlenring ZN selbst, also ord(maxG+) = ord(ZN) = N.

Betrachten wir noch einmal den Modulo-Zahlenring mit N=10, also Z10 = {0,1,2,3,4,5,6,7,8,9}, wo das inverse Element von 3 bezüglich der Multiplikation die 7 ist (und umgekehrt), denn 3*7 = 21 mod 10 = 1. Das klappt für alle Elemente a aus ZN mit ggT(a,N) = 1. Die von 3 erzeugte multiplikative Gruppe G* in Z10 wäre übrigens G(3,*) in Z10 = {3,9,7,1}. Für die 4 zum Beispiel ist aber ggT(4,10) = 2 # 1 und folgerichtig gibt es auch kein multiplikativ inverses Element b zu 4 in Z10 so dass 4 * b = k*10+1 = 1 mod 10 wäre. Die von 4 durch wiederholte Multiplikation in Z10 erzeugte Zahlenmenge wäre übrigens nur {4,6}, enthält also auch nicht das Eins-Element, also das bezüglich der Multiplikation benötigte neutrale Element, weshalb die Zahlenmenge {4,6} zwar zyklisch aber noch keine multiplikative Gruppe ist.

Erst in einem Körper K gibt es laut Definition wieder für jedes Element a aus K mit a # 0 (also außer dem Null-Element) ein bezüglich der Multiplikation inverses Element b, so dass a * b = 1 gilt. Aber auch in jedem Körper K ist das Null-Element 0 explizit aus jeder zyklischen multiplikativen Gruppe G* ausgeschlossen, denn 0 * a = 0, für alle Elemente a aus K. Also einmal Null, dann immer Null und nix mehr mit Zyklus. Wenn also ein Körper K insgeamt m Elemente hat, so hat die größte zyklische multiplikative Gruppe maxG* dieses Körpers K nur noch m-1 Elemente und kein einziges mehr. Die maximale multiplikative Gruppe maxG* hat also nur noch die Ordnung ord(maxG*) = m-1. Für jeden Generator g dieser maximalen multiplikativen Gruppe maxG* muss dann auch gelten, ord(g) = m-1, also gm-1 = 1 in K, sonst könnte der multiplikative Generator g nicht alle m-1 Elemente der maximalen multiplikativen Gruppe maxG* erzeugen. Mit anderen Worten ein Generator g einer multiplikativen Gruppe G* kann durch wiederholtes Multiplizieren immer nur Elemente der mulktiplikativen Gruppe G* und nicht alle Elemente des Körpers K erzeugen, denn dieser enthält ja auch noch das per Multiplikation mit einem von 0 verschiedenen Element nicht erzeugbare Null-Element und falls die multiplikative Gruppe G* keine maximale multiplikative Gruppe maxG* war auch noch weitere vom Null-Element verschiedene Elemente.

Z11 = {0,1,2,3,4,5,6,7,8,9,10} wäre zum Beispiel ein Modulo-Zahlenkörper, da 11 eine Primzahl ist. Die maximale multiplikative Gruppe maxG* in Z11 wäre also nur {1,2,3,4,5,6,7,8,9,10} und läßt sich z.B. durch die 2 als multiplikativen Generatoren erzeugen: G(2,*) = {2,4,8,5,10,9,7,3,6,1}, ord(G(2,*)) in Z11 = 10 = N-1. Dagegen hat das Element 3 in Z11 nur ord(G(3,*)) = 5 und erzeugt daher per Multiplikation auch nur die multiplikative Gruppe G* = G(3,*) in Z11 = {3,9,5,4,1}, also keineswegs die maximale multiplikative Gruppe.--Aragorn321 (Diskussion) 13:12, 8. Dez. 2012 (CET)Beantworten