主題
Search

本原多項式

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本

本原多項式是從基域生成擴張域所有元素的多項式。本原多項式也是不可約多項式。對於任何素數或素數冪 q 和任何正整數 n，都存在次數為 n 的 GF(q) 上的本原多項式。共有

a_q(n)=(phi(q^n-1))/n
(1)

GF(q) 上的本原多項式，其中 phi(n) 是尤拉總計函式。

在有限域 GF(2) (即係數為 0 或 1) 上的次數為 n 的多項式是本原的，如果它具有多項式階 2^n-1。例如，x^2+x+1 的階數為 3，因為

(x+1)/(x^2+x+1)=(x+1)/(x^2+x+1) (mod 2)
(2)
(x^2+1)/(x^2+x+1)=1+x/(x^2+x+1) (mod 2)
(3)
(x^3+1)/(x^2+x+1)=x+1 (mod 2).
(4)

將 q=2 代入等式 (◇)，GF(2) 上的本原多項式的數量為

a_2(n)=(phi(2^n-1))/n,
(5)

對於 n=1, 2, ... 給出 1, 1, 2, 2, 6, 6, 18, 16, 48, ... (OEIS A011260)。下表列出了階數為 1 到 5 的本原多項式 (mod 2)。

n本原多項式
11+x
21+x+x^2
31+x+x^3, 1+x^2+x^3
41+x+x^4, 1+x^3+x^4
51+x^2+x^5, 1+x+x^2+x^3+x^5, 1+x^3+x^5, 1+x+x^3+x^4+x^5, 1+x^2+x^3+x^4+x^5, 1+x+x^2+x^4+x^5

令人驚訝的是，GF(2) 上的本原多項式定義了一個遞推關係，它可以用來從前面的 n 位中獲得一個新的偽隨機位。

另請參閱

有限域, 不可約多項式, 多項式, 多項式階, 本原元, 本原根

使用 探索

參考文獻

Berlekamp, E. R. Algebraic Coding Theory. New York: McGraw-Hill, p. 84, 1968.Booth, T. L. "An Analytical Representation of Signals in Sequential Networks." In Proceedings of the Symposium on Mathematical Theory of Automata. New York, N.Y., April 24, 25, 26, 1962. Brooklyn, NY: Polytechnic Press of Polytechnic Inst. of Brooklyn, pp. 301-324, 1963.Church, R. "Tables of Irreducible Polynomials for the First Four Prime Moduli." Ann. Math. 36, 198-209, 1935.Fan, P. and Darnell, M. Table 5.1 in Sequence Design for Communications Applications. New York: Wiley, p. 118, 1996.O'Connor, S. E. "Computing Primitive Polynomials." http://seanerikoconnor.freeservers.com/Mathematics/AbstractAlgebra/PrimitivePolynomials/overview.html.Peterson, W. W. and Weldon, E. J. Jr. Error-Correcting Codes, 2nd ed. Cambridge, MA: MIT Press, p. 476, 1972.Ristenblatt, M. P. "Pseudo-Random Binary Coded Waveforms." In Modern Radar (Ed. R. S. Berkowitz). New York: Wiley, pp. 274-314, 1965.Ruskey, F. "Information on Primitive and Irreducible Polynomials." http://www.theory.csc.uvic.ca/~cos/inf/neck/PolyInfo.html.Sloane, N. J. A. Sequence A011260/M0107 in "The On-Line Encyclopedia of Integer Sequences."Zierler, N. and Brillhart, J. "On Primitive Trinomials." Inform. Control 13, 541-544, 1968.Zierler, N. and Brillhart, J. "On Primitive Trinomials (II)." Inform. Control 14, 566-569, 1969.

在 中被引用

本原多項式

請引用為

Weisstein, Eric W. "本原多項式。" 來自 Web Resource. https://mathworld.tw/PrimitivePolynomial.html

主題分類