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.

اخر الاخبار

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

قسم الشؤون الدينية يُطلق دورة فقهية دينية لملاكات مستشفى الكفيل

شعبة فاطمة بنت أسد للدراسات القرآنية تعلن نتائج مسابقة (ميثاق الرسول)

شعبة الخطابة الحسينية النسوية تنظّم مسابقة فرقية لطالبات برنامج ثمار العطاء

قسم العلاقات ينظم ورشة عن فن الإقناع والتواصل الفعّال للطلبة المنسقين

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

تغيير بسيط في نمط التفكير قد يحدث فرقا كبيرا لصحة الدماغ ؟

لماذا ينعشنا المشروب الساخن في الطقس الحار؟

علماء يكتشفون فئة دم فريدة من نوعها في العالم !

لماذا ينصح الأطباء بزيت الزيتون يوميا؟

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

حساس الإطارات.. ما هو وعلامات تلفه وكيفية صيانته؟

ما معنى أودي Quattro؟ سر الأداء والتميز الهندسي ؟!

فصل الشاحن أم الهاتف أولا؟.. عادات بسيطة تطيل عمر البطارية

تعود للقرن الرابع قبل الميلاد.. اكتشاف بقايا "إيمت" المصرية