Diskussion:Primitives Polynom

Übersetzung

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)

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)

Beispiele für primitive Polynome geben

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))

Zum Beispiel im Erweiterungskörper F_2⁴, der durch das irreduzible Polynom f(x) = x⁴+x¹+x⁰ (oder mit seiner Binärdarstellung (10011)) erzeugt wird, ist das Polynom g(x) = x¹ 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 F_2⁴ ist, heißt das Polynom f(x) dann primitives Polynom. Die Ordnung des Erweiterungskörpers ord(F_2⁴) = 2⁴ = 16, die Ordnung der zugehörigen maximalen multiplikativen Gruppe ist dann ord(maxG*) = (2⁴ - 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)

.Wiederholung nach 2^m -1

„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? --re^pat 18:01, 6. Jul. 2011 (CEST)

Weil jeder Erweiterungskörper der Form F_p^m mit p ist eine Primzahl und (m > 1), also auch alle mit (p = 2), die Ordnung p^m 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 (p^m - 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 (p^m - 1) erzeugten Pseudo-Zufallszahlen das Ende der Sequenz erreicht, siehe auch linear rückgekoppelte Schieberegister.--Aragorn321 (Diskussion) 14:24, 8. Dez. 2012 (CET)

Kleiner aber feiner Unterschied zwischen additiven und multiplikativen Gruppen

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 Z₁₀ = {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 Z₁₀ zu erzeugen. Also z.B. G(7,+) in Z₁₀ = {7,4,1,8,5,2,9,6,3,0}. Die Ordnung von 7 bezüglich der Addition in Z₁₀ wäre also gleich 10. Dagegen hat zwar auch die 2 in Z₁₀ 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 Z₁₀ erzeugen, G(2,+) in Z₁₀ = {2,4,6,8,0}. Die Ordnung von 2 bezüglich der Addition in Z₁₀ wäre also nur 5 und nicht 10. Mit anderen Worten die maximale additive Gruppe maxG+ besitzt genauso viele Elemente wie der Zahlenring Z_N selbst, also ord(maxG+) = ord(Z_N) = N.

Betrachten wir noch einmal den Modulo-Zahlenring mit N=10, also Z₁₀ = {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 Z_N mit ggT(a,N) = 1. Die von 3 erzeugte multiplikative Gruppe G* in Z₁₀ wäre übrigens G(3,*) in Z₁₀ = {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 Z₁₀ so dass 4 * b = k*10+1 = 1 mod 10 wäre. Die von 4 durch wiederholte Multiplikation in Z₁₀ 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 g^m-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.

Z₁₁ = {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 Z₁₁ 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 Z₁₁ = 10 = N-1. Dagegen hat das Element 3 in Z₁₁ nur ord(G(3,*)) = 5 und erzeugt daher per Multiplikation auch nur die multiplikative Gruppe G* = G(3,*) in Z₁₁ = {3,9,5,4,1}, also keineswegs die maximale multiplikative Gruppe.--Aragorn321 (Diskussion) 13:12, 8. Dez. 2012 (CET)