# What is a primitive polynomial?

What is a primitive polynomial? I was looking into some random number generation algorithms and 'primitive polynomial' came up a sufficient number of times that I decided to look into it in more detail.

I'm unsure of what a primitive polynomial is, and why it is useful for these random number generators.

I'd find it particularly helpful if an example of a primitive polynomial could be provided.

• To determine which sense of primitive polynomial is meant you should probably give some more context. Ideally an excerpt from whatever you're looking at. – Qiaochu Yuan Aug 1 '10 at 1:37
• @Qiaochu Yuan: I'm looking at the version of 'primitive polynomials' that is described by BBishcof's answer. – Cam Aug 1 '10 at 6:16
• in that case, is my answer clear, or are you still confused on something? – BBischof Aug 1 '10 at 16:11
• @BBischof: Your answer is good, but on an explanation question like this (vs. a one-right-answer question) I usually like to give a bit of time for others to answer. At this point though 24 hours have gone by, so I'll accept it. – Cam Aug 1 '10 at 20:31

Consider a finite field $F_p$, then we know that it is cyclic. We call an element primitive if it generates this field. Further, given a field and some polynomial over that field(all the coefficients are in the field), we can form a field extension by any of its roots. This is adjoining on that root and making a field of it.

It is a simple result of Galois Theory that if we take a field and extend by some root of some polynomial and get a finite extension(one who's degree as a vector space over the original field is finite), that we can find a polynomial $m$ over our ground field such that $m$ vanishes at this root and is minimal(smallest degree, i.e. it divides all other polys which vanish at this root).

If we consider a primitive element and its minimal polynomial, that poly is call primitive.

more details on wiki

• Great - thanks. <strike>Can you explain what a field extension is though?</strike> (looked it up on wikipedia) – Cam Aug 1 '10 at 20:32
• What "vanishing at this root" mean? All the definitions of primitive polynomials (in terms of finite fields) I could find are rather confusing. And I just cannot understand it and don't know in general case, how to find one. So what it is exactly? – TStancek Mar 15 '18 at 14:14

BBischof's answer is correct, but unfortunately there's another, quite different possible meaning of the same term: that is a polynomial whose coefficients have no common prime factor (this makes sense over the integers, or other UFDs as well).

• Based on the fact that Cam is looking at RNG, it seems that something related to finite fields (in particular F_2) is more likely. But yes, this is what I thought at first. – Qiaochu Yuan Aug 1 '10 at 1:15
• Completely agree, but down the line people may find the title of this question interesting so this answer at least ought to be here. – Alon Amit Aug 1 '10 at 2:09
• Hehe, I didn't know this usage :) learn something new every day ;) – BBischof Aug 1 '10 at 3:13
• Atiyah and Macdonald Introduction to Commutative Algebra, Exercise 1.2(iv), defines $f=a_0+a_1x+\dots+a_nx^n\in A[x]$ to be primitive if $(a_0,a_1,\dots,a_n)=(1)$, i.e., the ideal generated by the coefficients is equal to the whole ring $A$. In this way, the definition makes sense for any commutative ring with unit. – Per Manne Jan 8 '13 at 9:02

See this: and related references there, there is an algorithm for checking any polynomial to be primitive or not. COMPUTING PRIMITIVE POLYNOMIALS - THEORY AND ALGORITHM

• It's probably a good idea to expand the answer, rather than inserting an external link. – xxx--- Mar 24 '19 at 17:03