A primitive polynomial is a polynomial that generates all elements of an extension field from a base field. Primitive polynomials are also irreducible polynomials. For any prime or prime power  and any positive integer , there exists a primitive polynomial of degree  over GF(). There are

(1)

primitive polynomials over GF(), where  is the totient function.

A polynomial of degree  over the finite field GF(2) (i.e., with coefficients either 0 or 1) is primitive if it has polynomial order . For example,  has order 3 since

			(2)
			(3)
			(4)

Plugging in  to equation (◇), the numbers of primitive polynomials over GF(2) are

(5)

giving 1, 1, 2, 2, 6, 6, 18, 16, 48, ... (OEIS A011260) for , 2, .... The following table lists the primitive polynomials (mod 2) of orders 1 through 5.

	primitive polynomials
1
2
3	,
4	,
5	, , , , ,

Amazingly, primitive polynomials over GF(2) define a recurrence relation which can be used to obtain a new pseudorandom bit from the  preceding ones.

REFERENCES:

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.

اخر الاخبار

اخبار العتبة العباسية المقدسة

المجمع العلمي للقرآن الكريم يصدر الكتاب الثاني من سلسلة يخشى

قسم الشعائر يكرّم أصحاب المواكب المشاركة في إحياء ذكرى شهادة السيدة الزهراء (عليها السلام)

جامعة العميد تستقبل طلبة المراحل الأولى المقبولين ضمن كلياتها للعام الدراسي الجديد

سماحة السيد الصافي يكرّم طلبة حفظ القرآن الكريم المتفوّقين ويؤكّد دور التدبّر في الهداية والتكامل

المزيد

الآخبار الصحية

طبيب يكشف تأثير برودة الشتاء على النوم

دون أن تعلم.. 10 عادات يومية تسرع شيخوخة جسمك

تقرير: النيكوتين خطر على القلب مهما كانت الطريقة

أيهما أفضل لصحتك.. زبدة الفول السوداني أم النوتيلا؟

المزيد

الآخبار التكنلوجية

السعودية تدشن أكبر نظام لتخزين الكهرباء بالبطاريات في العالم !

بأمر تنفيذي.. ترامب يؤكد هدف عودة الأميركيين إلى القمر في عام 2028

بعيدا عن البشر.. "قتال جوي في الفضاء" بين أميركا والصين

كشف مذهل في قاع "برمودا" !

المزيد