主题
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 位中获得一个新的伪随机位。

另请参阅

有限域, 不可约多项式, 多项式, 多项式阶, 本原元, 本原根

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 中被引用

本原多项式

请引用为

Weisstein, Eric W. "本原多项式。" 来自 MathWorld--Wolfram Web Resource. https://mathworld.net.cn/PrimitivePolynomial.html

主题分类