$\begingroup$

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.

$\endgroup$ 4

3 Answers

$\begingroup$

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.

$\endgroup$ 2 $\begingroup$

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).

$\endgroup$ 4 $\begingroup$

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

$\endgroup$ 1

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy