Primitivní polynom (teorie pole) - Primitive polynomial (field theory)

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: Teorie pole „primitivní polynom“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Květen 2010) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v teorie pole, pobočka matematika, a primitivní polynom je minimální polynom a primitivní prvek z konečný pole rozšíření GF (str^m). Jinými slovy, polynom F(X) s koeficienty v GF (str) = Z/strZ je primitivní polynom, pokud je jeho stupeň m a má kořen α v GF (str^m) takové, že {0, 1, α, α², α³, ..., α^strm−2} je celé pole GF (str^m). To také znamená α je primitivní (str^m − 1) kořen jednoty v GF (str^m).

Vlastnosti

Protože všechny minimální polynomy jsou neredukovatelné, všechny primitivní polynomy jsou také neredukovatelné.

Primitivní polynom musí mít nenulový konstantní člen, protože jinak bude dělitelnýX. Přes GF (2), X + 1 je primitivní polynom a všechny ostatní primitivní polynomy mají lichý počet členů, protože jakýkoli polynomický mod 2 se sudým počtem členů je dělitelný X + 1 (má 1 jako root).

An neredukovatelný polynom F(X) stupně m nad GF (str), kde str je prvočíslo, je primitivní polynom, pokud je nejmenší kladné celé číslo n takhle F(X) rozděluje Xⁿ − 1 je n = str^m − 1.

Nad GF (str^m) existují přesně φ(str^m − 1)/m primitivní polynomy stupně m, kde φ je Eulerova totientová funkce.

Primitivní polynom stupně m má m různé kořeny v GF (str^m), které všichni mají objednat str^m − 1. To znamená, že pokud α je tedy takový kořen α^strm−1 = 1 a αⁱ ≠ 1 pro 0 < i < str^m − 1.

Primitivní polynom F(X) stupně m primitivního prvku α v GF (str^m) má explicitní formu F(X) = (X − α)(X − α^str)(X − α^str2)⋅⋅⋅(X − α^strm−1).

Používání

Reprezentace polního prvku

Primitivní polynomy se používají při reprezentaci prvků a konečné pole. Li α v GF (str^m) je kořen primitivního polynomu F(X) poté od objednávky α je str^m − 1 to znamená, že všechny nenulové prvky GF (str^m) lze reprezentovat jako postupné pravomoci α:

${ displaystyle mathrm {GF} (p ^ {m}) = {0,1, alpha, alpha ^ {2}, ldots, alpha ^ {p ^ {m} -2} }. }$

Když jsou tyto prvky redukovány modulo F(X), poskytují polynomiální základ reprezentace všech prvků pole.

Protože multiplikativní skupina konečného pole je vždy a cyklická skupina, primitivní polynom F je polynom takový, že X je generátor multiplikativní skupiny v GF (str)[X]/F(X)

Generování pseudonáhodných bitů

Lze použít primitivní polynomy nad GF (2), pole se dvěma prvky pseudonáhodné generování bitů. Ve skutečnosti každý posuvný registr lineární zpětné vazby s maximální délkou cyklu (což je 2ⁿ − 1, kde n je délka posuvného registru lineární zpětné vazby) může být vytvořena z primitivního polynomu.^[1]

Například vzhledem k primitivnímu polynomu p (x) = X¹⁰ + X³ + 1začneme uživatelem zadaným nenulovým 10bitovým semínkem, které zabírá bitové pozice 1 až 10, což představuje koeficienty polynomu nad GF (2), počínaje nejméně významným bitem. (Semeno nemusí být vybráno náhodně, ale může být). Semeno je poté posunuto doleva o jednu pozici, takže se 0. bit přesune do polohy 1, čímž se vynásobí x, primitivní prvek GF (2 ^ 10) [x] / p (x). Poté vezmeme 10. a 3. bit a vytvoříme nový 0. bit, takže xor ze tří bitů je 0, čímž je dosaženo dělení modulo p (x). Tento proces lze generovat opakováním 2¹⁰ − 1 = 1023 pseudonáhodné bity.

Obecně platí, že pro primitivní polynom stupně m přes GF (2), tento proces vygeneruje 2^m − 1 pseudonáhodné bity před opakováním stejné sekvence.

Kódy CRC

The kontrola cyklické redundance (CRC) je kód detekce chyb, který funguje tak, že interpretuje bitstring zprávy jako koeficienty polynomu nad GF (2) a vydělí jej pevným polynomem generátoru také nad GF (2); vidět Matematika CRC. Primitivní polynomy nebo jejich násobky jsou někdy dobrou volbou pro generátorové polynomy, protože mohou spolehlivě detekovat dvě bitové chyby, které se v bitstringu zprávy vyskytnou daleko od sebe, a to až do vzdálenosti 2ⁿ − 1 na titul n primitivní polynom.

Primitivní trinomials

Užitečnou třídou primitivních polynomů jsou primitivní trinomie, které mají pouze tři nenulové termíny: X^r + X^k + 1. Jejich jednoduchost je obzvláště malá a rychlá posuvné registry lineární zpětné vazby. Řada výsledků poskytuje techniky pro lokalizaci a testování primitivnosti trinomiálů.

Pro polynomy nad GF (2), kde 2^r − 1 je Mersenne prime, polynom stupně r je primitivní právě tehdy, je-li neredukovatelný. (Vzhledem k neredukovatelnému polynomu je ne primitivní pouze v případě, že období X je netriviální faktor 2^r − 1. Prvočísla nemají žádné netriviální faktory.) Ačkoli Mersenne Twister generátor pseudonáhodných čísel nepoužívá trinomiál, využívá toho.

Richard Brent tabeluje primitivní trinomály této formy, jako např X^74207281 + X^30684570 + 1.^[2][3] To lze použít k vytvoření generátoru pseudonáhodných čísel obrovské periody 2^74207281 − 1 ≈ 3×10^22338617.

Reference

externí odkazy

• Weisstein, Eric W. „Primitivní polynom“. MathWorld.