Talk:Primitive polynomial (field theory)

Various comments

There is still a serious error in this article, beside the confusion with two completely different notions of primitivity. Namely, the article says that

An irreducible polynomial of degree m, F(x) over GF(p) for prime p, is a primitive polynomial if the smallest positive integer n such that F(x) divides xⁿ - 1 is n = p^m − 1.

This is again mixing together two different notions. Look at the polynomial F(x)=x⁴+x³+x²+x+1 over GF(2). Then F(x) is irreducible, but not primitive in the quoted sense (F(x) divides x⁵-1). But the definition of a primitive polynomial as the minimal polynomial of a primitive element refers to a simple extension. But the residue of x in the representation of GF(16) as the factor (GF(2))[x]/(f(x)) is a primitive element over GF(2) and F(x) really is its minimal polynomial!

Doesn't Gauss's lemma [1] state that the product of primitive polynomials is primitive? Then how can all primitive polynomials be irreducible? -3mta3 08:37, 20 July 2005 (UTC)[reply]

``Because all minimal polynomials are irreducible, all primitive polynomials are also irreducible. Its not correct that all primitive polynomials are irreducible. Consider x^4+4. One can see that (1,4) = 1, so its a primitive polynomial. But, its not irreducible, since: x^4 + 4 = (x^2 - 2x + 2) *(x^2 + 2 x + 2)

This article is utterly confusing, as it defines two (completely different) notions of primitivity, and then deals only with the second. 21:29, 27 May 2006 (UTC)

I hopefully fixed that. Oleg Alexandrov (talk) 03:16, 18 July 2007 (UTC)[reply]

Also the first definition is wrong, the gcd could be a unit (eg -x - 5 is primitive over Z[X]).

In section "Random bit generation" it says that "Primitive polynomials define a recurrence relation that can be used to generate pseudorandom bits, like a linear feedback shift register does." which is kind of true but a strange thing to say. Maybe it's better to say a linear feedback shift register is a way to implement the recurrence relation defined by a primitive polynomial. (Or in fact by any polynomial, but it's the ones corresponding to primitive polynomials that are mostly used in practice due to maximal period and other nice properties.) 198.142.44.123 00:27, 26 June 2007 (UTC)[reply]

It would be kind of neat to have a list of interesting primitive polynomials, or perhaps multiple lists by category (eg. primitive trinomials over GF2). Or if that isn't encyclopedic enough, a link to where such lists can be found. 198.142.44.123 00:27, 26 June 2007 (UTC)[reply]

In the part about LFSRs, it says "We then take the 10th, 3rd, and 0th bits of it, starting from the least significant bit, and xor them together, obtaining a new bit." which is confusing at best, and says there are 3 bits that are XORed together, which is not the case for the polynomial given.129.42.161.36 (talk) 21:15, 21 June 2013 (UTC)[reply]

That whole paragraph is confusing and goes into excessive details about LFSR that can anyways be found in the main LFSR article, so I am deleting it. Burritok (talk) 04:32, 22 November 2022 (UTC)[reply]

Roots?

The article says:

The roots of a primitive polynomial all have order p^m − 1.

I thought primitive polynomials are irreducible. How can they have roots?

Very confusing article... This one is a bit better: http://www.theory.csc.uvic.ca/~cos/inf/neck/PolyInfo.html

Woz2 (talk) 20:13, 6 November 2013 (UTC)[reply]

Primitive polynomials are irreducible over GF(p) and have all their roots in GF(p^m). Thus they factors in linear factors over GF(p^m). I have rewritten this sentence to be less confusing. D.Lazard (talk) 21:26, 6 November 2013 (UTC)[reply]

Thanks! Woz2 (talk) 13:27, 7 November 2013 (UTC)[reply]

Indeed, if you read the definition with which the article begins, you will see that a primitive polynomial must have roots: the concept "primitive polynomial" is defined in terms of a root of the polynomial (referred to in the article as α). As for the page that you link to, if you find it "better", then that's fine, but it seems to me unhelpful to anyone who wants to use it to learn about primitive polynomials, as it does not give context to the concepts it defines. For example, it defines it in terms of the order of the polynomial, but gives no indication why happening to have order 2ⁿ-1 is significant or interesting, rather than defining it in terms of fundamental properties which are more relevant to why the concept is used. That page is part of the documentation of a software tool, and if all you want is to know how to use the tool, then the information given is probably adequate. However, for anyone wanting an understanding of the mathematical theory of fields, it seems to me to be of rather limited use. Also, parts of its explanations apply only to GF(2), not to other fields. JamesBWatson (talk) 21:43, 6 November 2013 (UTC)[reply]

Thanks! I suppose my frustration with the article is that I came to it as a non-mathematician expecting answers to two engineering questions (that I think other readers might also have) namely "1) How does one generate a complete set of primitive polynomials? 2) Why is it that GF(2) primitive polynomials are a necessary and sufficient condition to generate maximal length sequences in linear feedback shift registers?" If I find the answers, I'll add them here or in the MLS and/or LFSR articles. Any pointers appreciated. Woz2 (talk) 13:27, 7 November 2013 (UTC)[reply]

I had to laugh when I read this at http://mathworld.wolfram.com/PrimitivePolynomial.html "Amazingly, primitive polynomials over GF(2) define a recurrence relation which can be used to obtain a new pseudorandom bit from the n preceding ones." Yes, it is amazing. Citation needed. :-) Woz2 (talk) 22:35, 7 November 2013 (UTC)[reply]

Noting that hardware implementations benefit from choosing primitive polynomials for GF(2^m) where the primitive element is 2

It should be mentioned somewhere in the article that hardware implementations involving binary finite fields $GF(2^{m})$ benefit when reducing polynomial is primitive, where the primitive element is x == 2. This reduces gate count and speeds up calculations. Rcgldr (talk) 07:38, 20 May 2021 (UTC)[reply]

2 is not an element of

GF(2^{m}),

and cannot therefore be a primitive element. In any case, for mentioning anything, we must provide WP:reliable sources that discuss it. It is to you to provide them. Also, the choice of a "good" representation is already discussed with a source in Finite field#Non-prime fields. If other representations are better for some computations, the applications that require these representations must be mentioned. "Hardware implementations" is not an application, but a method of implementation of other applications. D.Lazard (talk) 09:47, 20 May 2021 (UTC)[reply]

2 is a common shorthand form of stating that

\alpha =x+0

, in binary shown as 1 0, or in hex as 2. For example Reed-SolomonProjectReport.pdf. It's also common to show elements of GF(2^n) or polynomials as hex values, for example CRC Zoo. Linear Feedback Shift Register like operations are similar to multiplying by 2 modulo a primitive polynomial, which is why hardware implementations of GF(2^n) usually choose a primitive polynomial. AES inversion step is an exception, it uses 0x11B which is irreducible, but not primitive, one of the primitive elements is 3, but the primitive element hex 1f is often used when mapping to a composite field such as GF((2^4)^2) or GF(((2^2)^2)^2). In the case of a composite field, such as GF((2^4)^2), again a primitive polynomial is desired, but in this case

\alpha =x+0

= hex 10 (not 2). Rcgldr (talk) 02:24, 21 May 2021 (UTC)[reply]

Is there a primitive polynomial x^n + ... + 1 where x is not a primitive element or vice versa?

Is there a primitive polynomial x^n + ... + 1 where x is not a primitive element or vice versa? If all primitive polynomials have x as a primitive element or if all polynomials that have x as a primitive element are primitive polynomials, then why not include this as a alternative and simpler definition for primitive polynomial? Rcgldr (talk) 16:38, 5 August 2021 (UTC)[reply]

Is x a root?

From the article, the roots of a primitive polynomial are generators of the field GF(p^m). Each root $\alpha$ will generate all the nonzero elements of the field. Later in the article, it says that x is also a generator of the multiplicative group of the field (which I believe is the same as all the nonzero elements). Does that mean x is a root of p(x)? — Preceding unsigned comment added by 108.60.43.48 (talk) 11:11, 12 March 2022 (UTC)[reply]

Good point: the two last paragraphs of § Field element representation were almost nonsensical. I have replaced them by a clarification of the meaning of "representation". D.Lazard (talk) 11:48, 12 March 2022 (UTC)[reply]

But x is still a generator of the field, a point which should remain in the article, and was briefly mentioned but not really proven. This explains how LFSR's work, where each shift of the register corresponds to multiplication by x, followed by division by p(x). If p(x) isn't primitive, then multiplication by x does not generate the entire field, an important point for this article as well. My confusion comes from the fact that the shift is multiplication by x (the indeterminate of p(x), not multiplication by a root

\alpha

of p(x). Unless somehow there is a proof that it's the same thing? — Preceding unsigned comment added by 108.60.43.48 (talk) 20:38, 12 March 2022 (UTC)[reply]

There are two ways for generating a finite field: a primitive element generates the elements of the field as the powers of the primitive element; a generator generates the elements of the field as polynomials in the generator, whose degree is less than the degree of the field (

m

in

\operatorname {GF} (p^{m})

). Primitive elements are generators for this second way of generating, but not all generators are primitive. All these things are discussed in Finite field, and it is better to go to there than trying to find here information that is out of the scope of this article. D.Lazard (talk) 09:22, 13 March 2022 (UTC)[reply]

"a generator generates the elements of the field as polynomials in the generator, whose degree is less than the degree of the field" Could you clarify this a bit more?

I think I worked out the answer to my question, using https://glassnotes.github.io/OliviaDiMatteo_FiniteFieldsPrimer.pdf as a resource. Ultimately x is not a root of P(x). As they do in that article, as you write out the finite field elements using the root

\sigma

of P(x), which is also a generator of the finite field, then just change the variable to x, you'll get x is a generator of the field as well.

This article defines a primitive polynomial P(x) as the minimal polynomial of a primitive element of a field. Other places on the web define the primitive polynomial P(x) as a polynomial where x is a generator of the finite field constructed from GF(p)[x]/P(x). I think I'll add to this article to show that they are equivalent. 108.60.43.48 (talk) 03:53, 14 March 2022 (UTC)[reply]

You are confusing primitive element (finite field) and primitive element (field theory). Also, you use "generator" without distinguishing the two completely diffent meanings of generator of the multiplicative group (called "primitive element" in the context of finite fields) and generator of a field extension (called "primitive element" in the context of infinite fields). This ambiguous terminology is traditional, and, therefore, must be kept in Wikipedia. So, Wikipedia articles must be carefully written for not confusing readers. By the way, your source is not a reliable source (see WP:Reliable sources). Also, it confusing, since it does not says that the construction of the section "Extending a prime field" works with irreducible polynomials that are not primitive. The article Finite field is much clearer, and is a much more accurate source of information. D.Lazard (talk) 13:44, 14 March 2022 (UTC)[reply]

Fair enough 108.60.43.48 (talk) 08:14, 15 March 2022 (UTC)[reply]

LFSRs and Primitive Polynomials

The section on pseudo-random bit generation and LFSRs should at least discuss why x is a generator (not $\alpha$ ), and why you need to pick a primitive polynomial (vs. an irreducible one) in order to get x to be a generator, to get maximal length. That is what brought me to this article in the first place, trying to understand how pseudo-random generators used for communications (such as PN11) work. — Preceding unsigned comment added by 108.60.43.48 (talk • contribs) 12:54, 14 March 2022 (UTC)[reply]