Talk:Primitive polynomial
From Wikipedia, the free encyclopedia
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 xn - 1 is n = pm − 1.
This is again mixing together two different notions. Look at the polynomial F(x)=x4+x3+x2+x+1 over GF(2). Then F(x) is irreducible, but not primitive in the quoted sense (F(x) divides x5-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)
``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)
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)
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)
