Appendix H

Appendix H: Order Reversal Theorems for Irreducible Polynomials An order-reversed polynomial is one in which the order of the coefficients is reversed. For example, here H(x) is the order-reversed version of h(x), h(x) = c0 + c1x + c2x2 + c3x3 + ... ck-1xk-1 + ckxk = {c0,c1,c2......ck-1,ck} (H.1) H(x) = ck + ck-1x + ck-2x2 + ck-2x3 + ... + c1xk-1 + c0xk = {ck, ck-1.....c2,c1, c0} Peterson and Weldon refer to such polynomials as being reciprocal. If h(x) and H(x) are the same polynomial, we call it a symmetric polynomial (self-reciprocal). We shall now develop four Facts relating to order-reversed polynomials. Fact 1: If h(x) is irreducible in R, then so is its order-reversed partner H(x). (H.2) Corollary: Irreducible polynomials thus come in pairs as long as h(x) is not symmetric. Often tables of irreducible polynomials only state one of the pair in order to save space. Proof of Fact 1: Let h(x) of degree k be irreducible for GF(pm). We can write (c0 ≠ 0 and ck ≠ 0) h(x) = c0 + c1x + c2x2 + c3x3 + ... + ckxk degree k ≤ m GF(pm) . If c0 were 0, we could factor out x and h(x) would be reducible. If ck were 0, we would not have degree k which we want for this proof. Now consider the order-reversed polynomial, H(x) = ck + ck-1x + ck-2x2 + ck-2x3 + ... + c1xk-1+ c0xk degree k . Notice that H(1/x) = ck + ck-1x-1 + ck-2x-2 + ck-2x-3 + ... + c1x-k+1 c0x-k = x-k [c0 + c1x + c2x2 + c3x3 + ... + ckxk] = x-k h(x) . (H.3) Assume h(x) is irreducible and H(x) is reducible. We will find a contradiction and conclude that if h(x) is irreducible, then the order-reversed H(x) must also be irreducible. If H(x) is reducible then it can be written as the product of two polynomials in R whose degrees add up to the degree of H(x) which is k. So write, H(x) = [gn(x)][fk-n(x)] (H.4) where the gn is of degree n and fk-n is of degree k-n. Values of n range from 1 to k-1, so each factor is at least linear in x, not just a constant. We then find that h(x) = xk H(1/x) = xnxk-n [gn(1/x)][fk-n(1/x)] = { xn gn(1/x) } { xk-n fk-n(1/x) } = { Gn(x) } { Fk-n(x)} (H.5) where Gn(x) and Fk-n(x) are both polynomials in R with 1 ≤ n ≤ k-1 so neither factor is a constant. Then h(x) is reducible, and this is our contradiction, QED. Fact 2: If h(x) is a minimum polynomial in R, then so its order-reversed partner H(x). (H.6) Corollary: Minimum polynomials thus come in pairs as long as h(x) is not symmetric. Often tables of minimum polynomials only state one of the pair in order to save space. Proof of Fact 2: If h(x) is a a minimum polynomial in R, we know it is irreducible and it can be factored as h(x) = (x-a1)(x-a2)...... (x-ak) (H.7) where the ai are all elements of GF(pm) and are elements of a conjugate set as defined in Section 5 (c). We already know that H(x) is irreducible from Fact 1, but we need to show that H(x) is a minimum polynomial. From (H.3) , H(1/x) = x-k h(x) . (H.3) so that H(x) = xk h(1/x) = xk(1/x-a1)(1/x-a2)...... (1/x-ak) = (1-a1x) (1-a2x)...... (1-akx) = [(-a1)(x-a1-1)] [(-a2)(x-a2-1)] ... [(-ak)(x-ak-1)] = {(-a1) (-a2) ... (-ak) } {(x-a1-1) (x-a2-1) ... (x-ak-1) . Since any product of field elements is a field element, we can call the first factor γ in GF(q). Then H(x) = γ (x-a1-1) (x-a2-1) ... (x-ak-1) . (H.8) According to following Lemma, we know that the inverses of the elements of a conjugate set form a conjugate set, and therefore H(x) is a minimum polynomial, QED. Lemma 1: The set formed by inverting the elements of a conjugate set is a conjugate set. (H.9) Proof: If α is a primitive element of GF(q), then we can enumerate GF(q) this way from (4.31), { 0, 1, α, α2, α3 , ...... αq-2 } αq-1 = 1 αq = α . (4.31) The general form of a conjugate set from (5.40) is { αs, αsp, αsp, αsp , .... αsp } , (5.40) where α is a primitive element of GF(q) and αs is some other element of GF(q) where s is an integer which we normally think of as lying in the range 1 to q-1. If we set s = q-2, we get this conjugate set { α(q-2), α(q-2)p, α(q-2)p, α(q-2)p , .... α(q-2)p } . (H.10) If α-1 is the inverse of α, then α α-1 =1. On the other hand, we know α αq-2 = αq-1 = 1. Therefore we can identify α-1 = α(q-2) (H.11) and we can write the above conjugate set as { α-1, (α-1)p, (α-1)p, (α-1)p , .... (α-1)p } . (H.12) We know that in general (αn)-1 = (α α α...)-1 = α-1 α-1 α-1 ... = (α-1)n (H.13) so we can write the above conjugate set as { α-1, (αp)-1, (αp)-1, (αp)-1 , .... (αp )-1} (H.14) Since this is a conjugate set, we have shown that the inverses of the elements of a conjugate set form a conjugate set (in general a different one with the same number of elements). QED. Fact 3: If h(x) is a primitive polynomial in R, then so is its order-reversed partner H(x). (H.15) Corollary: Primitive polynomials thus come in pairs as long as h(x) is not symmetric (see Fact 4 below). Often tables of primitive polynomials only state one of the pair in order to save space. Proof of Fact 3: If h(x) is a primitive polynomial of GF(pm) then it is of degree m and from (5.35) all members of its conjugate set ai are primitive elements of GF(q). From (H.10) α-1 = α(q-2). According to (4.32), if α is primitive, α-1 = α(q-2) is also primitive since GCD(q-2,q-1) = 1 (see following Lemma). Now recall from Fact 1 the forms for h(x) and its order-reversed H(x), h(x) = (x-a1)(x-a2)...... (x-ak) (H.7) H(x) = γ (x-a1-1) (x-a2-1) ... (x-am-1) . (H.8) Letting α = a1, a primitive element of h(x), we have just shown that α-1 = a1-1 is also a primitive element and therefore H(x) is a primitive polynomial (and all the ai-1 are primitive elements of GF(q) ). Lemma 1: The GCD of two sequential integers is 1. (H.16) Proof: Assume GCD(n,n+1) = N > 1. Then there exist integers I and J such that n/N = I => n = IN (n+1)/N = J => n+1 = JN => IN + 1 = JN => N(J-I) = 1 . We end up then with (J-I) = 1/N which is impossible unless N = 1, QED. Fact 4: A primitive polynomial h(x) for GF(pm) cannot be symmetric if p and m are in these ranges: p = 2 with m ≥ 3 p = 3 with m ≥ 2 p > 3 (H.17) Corollary: Thus, the only fields for which h(x) can be symmetric are GF(2), GF(22) and GF(3). This means there are no symmetric primitive polynomials of degree greater than 2 for any GF(q). As was shown in Chapter 5 (c), for GF(2) and GF(3) the only primitive polynomial is 1+x, and for GF(22) the only one is 1 + x + x2 as we found in (5.29). Thus, in the only cases in which h(x) can be symmetric, it is symmetric (Murphy's Law). (H.18) Proof of Fact 4: The conjugate set of h(x) with respect to GF(pm) looks like this, where α is a primitive element of GF(pm) : { α, αp, αp, αp , .... αp } αp = α m conjugates (5.16) The conjugate set of H(x) we found from (H.10) is, with k = m now since h(x) is primitive, { α(q-2), α(q-2)p, α(q-2)p, α(q-2)p , .... α(q-2)p } . (H.10) In order to have h(x) = H(x), these two conjugate sets have to be the same. One must be at worst a rearrangement of the other. But we shall now show that the element α is missing from the second set under the conditions stated above, and therefore the two sets cannot be the same, and therefore we cannot have H(x) = h(x) and therefore h(x) cannot be symmetric. In order to have α be present in the second set we would have to have α = α(q-2)p for some i in range 0 to m-1 Multiply both sides by αp to get αp+1 = α(q-1)p = [ αq-1]p = [1]p = 1 . Since α is a primitive element of GF(pm), we know that αq-1 = 1. In order for the above equation to be true, we must have pi+1 be a multiple of q-1 = pm - 1 for some i in (0,m-1): pi+1 = K (pm - 1) K = integer (H.19) Obviously K = 0 does not work. We try K = 1 next. But for (p,m) in the ranges stated below, we will show that in fact pi+1 < (pm - 1), so K = 1 does not work nor does any K > 1 work. In order to show that pi+1 < (pm - 1) for all i in our range 0 to m-1, if suffices to show this for the largest exponent i = m-1, for then it will be true as well for all smaller i. So we want to show that, for a certain range of p and m, we have pm-1+1 < (pm - 1) or pm - pm-1 > 2 or pm-1(p-1) > 2 Lemma 2 below shows that this inequality is true for p and m in these ranges p = 2 m ≥ 3 p = 3 m ≥ 2 p > 3 m ≥ 1 or just p > 3 These then are the ranges for which no K exists in (H.18) and therefore α which is in the conjugate set of h(x) is NOT in the conjugate set of H(x). These sets are then different, so h(x) ≠ H(x) which means h(x) cannot have symmetric coefficients for p and m as shown above. Lemma 2: The inequality pm-1(p-1) > 2 is true for the following values of p and m: p = 2 true for m ≥ 3 p = 3 true for m ≥ 2 p > 3 true for m ≥ 1 (H.20) Proof: Start with p = 2 2m-1 * 1 > 2 ? For m ≥3 this is clearly true, but it is not true for m = 1 or m = 2. Now consider p = 3. 3m-1(2) > 2 ? This is true for m ≥ 2. Finally, consider p > 3. pm-1(p-1) > 2 ? In this case (p-1) > 2 all by itself and so this is valid for m ≥ 1. QED.