Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

3 Answers 3

up vote 10 down vote accepted

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

share|improve this answer
    
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

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

share|improve this answer
1  
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
4  
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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.