BCH questions

BCH questions PhL 1.21.13 All this material has been incorporated into Galois doc, Chapter 5 (g) Consider the set of roots of g(x) { α, α2 , α3, ....αN }. Each of these powers has a minimum polynomial mi(x). Question #1: Can the same root "a" appear in two different minimum polynomials? For example m1(x) = (x-a)(x-b) m2(x) = (x-a)(x-c)(x-d) Answer: We know exactly the roots in for any min poly from our formula. They are the distinct members of this set of m elements. { α, αp, αp, αp , .... αp } This we know that the number of elements in the conjugate set of α is ≤ m. If α is primitive, then the number of distinct elements is exactly m by (5.15). We do have α = primitive. The general min poly formula is for any α is m(x) = (x - α) (x - αp) (x - αp) (x - αp) ... .... (x - αp) αp= α . (5.17) where k ≤ m. How do you compute k ? I do know that any α has some order n. We can see from the above that αp-1= 1 Therefore I think this is true n = order of α = pk - 1 since then αn = 1 and this is the smallest power that does it. Therefore, for α = primitive, the then we have the full list m(x) = (x - α) (x - αp) (x - αp) (x - αp) ... .... (x - αp) αp= α . (5.17) In this case, there are m distinct roots of m(x), and the order of α is pm - 1 = q, all this fits together. Subquestion. If α is primitive, is αi also primitive? Recall Fact 12: A power αk of a known primitive element α of GF(q) is itself a primitive element if and only if GCD(k,q-1) = 1. (4.32) So I guess in general I don't know whether or not αi is also a primitive element! So I don't now the order of the min poly of αi right now. All I really know is this: The order of αi is some number ni = pki - 1 for some ki ≤ m. Thus, if we write out the product Back to Question 1. Suppose two different min polys have the same root a. m(x) = (x - α) (x - αp) (x - αp) (x - αp) ... .... (x - αp) αp= α . (5.17) n(x) = (x - β) (x - βp) (x - βp) (x - βp) ... .... (x - βp) βp= β . (5.17) Suppose in the first poly we have αp = a and in the second poly we have βp = a Then we have (assume for now that i ≥ j) αp = βp β = α[p/p] = αp Since i-j ≥0, we have β = α or αp or αp etc. Therefore, β must be in m(x). Pause: I suspect you can take any element in (5.17) and write it as the first element. For example m(x) = (x - αp) (x - αp) (x - αp) ... .... (x - αp) (x - α) or m(x) = (x - αp) (x - αp) ... .... (x - αp) (x - α) (x - αp) You get the same polynomial in either case. This last version can be written m(x) = (x - αp) (x - αp) ... .... (x - αp) (x - αp) (x - αp) αp= α m(x) = (x - αp) (x - αp) ... .... (x - αp) (x - αp) (x - αp) αp= α In general we could I think write m(x) = (x - αp) (x - αp) ... .... ..... (x - αp) αp= α The idea is that you can pick any r you want to start the expression for m(x). Resume: Back to m(x) and n(x) having the same root a. We found that β = αp with r = i-j. This I think means that m(x) and n(x) are the same polynomial! That would be a major fact. Can I get verification? google books There it is! Assuming this is true, then here is what I know. If we take gN(x) = LCM[ m1(x)m2(x)m3(x)m4(x) ... mN(x)] = ma(x)mb(x)mc(x) Then since the min polys have no overlapping roots, we know that the order of the resulting product is less than q-1 !! Fact 16: Any root of a minimal polynomial can be written as the first root. Proof: Consider this generic minimum polynomial of α shown in (5.17), where k ≤ m, m(x) = (x - α) (x - αp) (x - αp) (x - αp) ... .... (x - αp) αp= α (*) We can move the leftmost root to the right end and write α as αp to get m(x) = (x - αp) (x - αp) (x - αp) ... .... (x - αp) (x - αp) Now take the left element above and move it to the right end m(x) = (x - αp) (x - αp) ... .... (x - αp) (x - αp) (x - αp) Since we can do this any number of times, we conclude that m(x) can be written as m(x) = (x - αp) (x - αp) ... .... ..... (x - αp) for any integer r such that αp is in the original set of roots. This is what we mean by saying that any element of (*) can be written as the first root. Fact 17: Two distinct minimum polynomials can have no roots in common. In other words, the elements of two distinct conjugate sets have no common elements. Proof: Let m(x) and n(x) be two distinct minimum polynomials m(x) = (x - α) (x - αp) (x - αp) (x - αp) ... .... (x - αp) αp= α . n(x) = (x - β) (x - βp) (x - βp) (x - βp) ... .... (x - βp) βp= β . Our formula above for the minimal polynomial of some GF(q) field element α was, { α, αp, αp, αp , .... αp } αp = α k conjugates k ≤ m (5.16) Question: is the conjugate set a cyclic subgroup of something? This is just not obvious to me. It is not a list of sequential powers as I am used to.