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.
3 Answers
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 polynomial is call primitive.
More details on wiki.
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).
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
