9
$\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
  • $\begingroup$ 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. $\endgroup$
    – Qiaochu Yuan
    Commented Aug 1, 2010 at 1:37
  • $\begingroup$ @Qiaochu Yuan: I'm looking at the version of 'primitive polynomials' that is described by BBishcof's answer. $\endgroup$
    – Cam
    Commented Aug 1, 2010 at 6:16
  • $\begingroup$ in that case, is my answer clear, or are you still confused on something? $\endgroup$
    – BBischof
    Commented Aug 1, 2010 at 16:11
  • $\begingroup$ @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. $\endgroup$
    – Cam
    Commented Aug 1, 2010 at 20:31

3 Answers 3

Reset to default
16
$\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$ Great - thanks. <strike>Can you explain what a field extension is though?</strike> (looked it up on wikipedia) $\endgroup$
    – Cam
    Commented Aug 1, 2010 at 20:32
  • $\begingroup$ 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? $\endgroup$
    – TStancek
    Commented Mar 15, 2018 at 14:14
14
$\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
  • 1
    $\begingroup$ 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. $\endgroup$
    – Qiaochu Yuan
    Commented Aug 1, 2010 at 1:15
  • 7
    $\begingroup$ Completely agree, but down the line people may find the title of this question interesting so this answer at least ought to be here. $\endgroup$
    – Alon Amit
    Commented Aug 1, 2010 at 2:09
  • $\begingroup$ Hehe, I didn't know this usage :) learn something new every day ;) $\endgroup$
    – BBischof
    Commented Aug 1, 2010 at 3:13
  • 2
    $\begingroup$ 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. $\endgroup$
    – Per Erik Manne
    Commented Jan 8, 2013 at 9:02
1
$\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
  • 1
    $\begingroup$ It's probably a good idea to expand the answer, rather than inserting an external link. $\endgroup$
    – hola
    Commented Mar 24, 2019 at 17:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .