THE ORDER OF A ROOT OF X^{p} – X – 1 OVER 𝔽_{p}

Jian-yi Shi, Zhen-hua Wang Institute of Network Information Security, East China Normal University, Shanghai, 200062, P. R. China

Abstract. The present paper is concerned with the order o(α_{p}) of a root α_{p} of the polynomial x^{p} − x − 1 over a prime field 𝔽_{p}. We propose a conjecture that o(α_{p}) = m_{p} := (p^{p} − 1)/(p − 1) for any prime p. Then we introduce two methods to verify the conjecture in certain cases.

Let f(x) be an irreducible polynomial over a prime field 𝔽_{p} of p > 0 elements, let α be a root of f(x) in the splitting field GF(p, f(x)) and let GF(p, f(x))^{∗} be the multiplication group consisting of all the non-zero elements of GF(p, f(x)). It is well known that the field GF(p, f(x)) is generated by α over 𝔽_{p}. However, the cyclic group GF(p, f(x))^{∗} is not necessarily generated by α in general. Thus it is natural to ask what is the order for α in GF(p, f(x))^{∗}. The solution to this problem has some important applications, e.g., in the cryptography and secure communications (see [1, 4]).

In the present paper, we consider a special polynomial f_{p}(x) = x^{p} −x−1 over 𝔽_{p}, which is irreducible by [3]. Let α_{p} be a root of f_{p}(x) in the field K = GF(p, f_{p}(x)). It is easily seen that \{α_{p} + k | k ∈ 𝔽_{p}\} is the set of all the roots of f_{p}(x) in K. Let m_{p} = \frac{p^{p}−1}{p−1}.

Typeset by AMS-TEX

Supported by the 973 Project of MST of China, the National Science Foundation of China, the Science Foundation of the University Doctorial Program of ED of China, the Shanghai Priority Academic Discipline and the Foundation for the Science and Technology Development of Shanghai.

2 J. Y. Shi, Z. H. Wang We denote the elements of 𝔽_{p} by 0, 1, 2, ..., p − 1 respectively for the simplification of the notation. Then we have Lemma 1. (a) α_{p}^{p^{k}} = α_{p} + k for any k ∈ 𝔽_{p}.

(b) α_{p}^{m_{p}} = 1. Proof. (a) follows by repeatedly applying the relations α_{p}^{p} = α_{p} +1 and (α_{p} +h)^{p} = α_{p}^{p} +h for h ∈ 𝔽_{p}. For (b), write

(1)  m_{p} = 1 + p + p^{2} + ... + p^{p−1}.

Then by (a), we have

α_{p}^{m_{p}} = α_{p} · α_{p}^{p} · α_{p}^{p^{2}} · ... · α_{p}^{p−1} = α_{p}(α_{p} + 1)(α_{p} + 2)...(α_{p} + p − 1) = 1

by the relation between roots and coefficients for a polynomial. □

We know that all the roots of f_{p}(x) have the same order. The above lemma shows that the order o(α_{p}) of α_{p} divides m_{p}. The following criterion on the order of α_{p} is an immediate consequence of Lemma 1, (b). Corollary 2. o(α_{p}) = m_{p} if and only if αp^{\frac{mp}{k}} ≠ 1 for any prime divisor k of m_{p}.

By a case-by-case argument, we can show that if p is a prime less than 40 then o(α_{p}) = m_{p}. The methods of showing this will be introduced later. Here we propose the following Conjecture 3. o(α_{p}) = m_{p} for any prime p.

In the subsequent part of the paper, we shall introduce two methods to deal with the conjecture in some cases by Corollary 2. Here we would like to thank K. F. Lai and A. Nelson for their helpful communications during our writing the paper.

The order of a root of x^{p} − x − 1 over 𝔽_{p} 3

4. For any prime number k with k|m_{p}, the number q = \frac{m_{p}}{k} has a p-adic expansion: q = a_{0} + a_{1}p + a_{2}p^{2} + ... + a_{p−2}p^{p−2} by the facts that q < m_{p} = 1 + p + p^{2} + ... + p^{p−1} and m_{p} = qk, where 0 ⩽ a_{i} < p for 0 ⩽ i ⩽ p − 2. Let I = {i | a_{i} ≠ 0}. Suppose that α_{p}^{q} = 1. Then α_{p}^{q} = ∏_{i∈I}(α_{p} + i)^{a_{i}} = 1. This implies that f_{p}(x) divides the polynomial ∏_{i∈I}(x + i)^{a_{i}} − 1. Since o(α_{p}) = o(α_{p} + j) for any 1 ⩽ j < p, f_{p}(x) divides ∏_{i∈I}(x + j + i)^{a_{i}} − 1 for any 0 ⩽ j < p. This implies that f_{p}(x) divides the polynomial g(x)_{j} = ∏_{i∈I}(x + i)^{a_{i}} − ∏_{i∈I}(x + j + i)^{a_{i}} for any 1 ⩽ j < p. Write g(x)_{j} = h(x)_{j}r(x)_{j} with h(x)_{j} the greatest common divisor of ∏_{i∈I}(x + i)^{a_{i}} and ∏_{i∈I}(x + j + i)^{a_{i}}. Then r(x)_{j} should also be divisible by f_{p}(x) since h(x)_{j} is not divisible by f_{p}(x) and since f_{p}(x) is irreducible over 𝔽_{p}. So if one can show that r(x)_{j} is not divisible by f_{p}(x) (e.g., in the case of deg r(x)_{j} < p) for some j, then one can conclude that α_{p}^{q} ≠ 1. Example 5. Let p = 11. Let z be a root of f_{p}(x) = x^{11}−x−1. Then m_{p} = 28531167061 = 1806113 · 15797 with a = 1806113 and b = 15797 primes. We want to show o(z) = m_{p}. For otherwise, we would have either z^{a} = 1 or z^{b} = 1. Write a = 1 + 6 · 11 + 10 · 11^{2} + 3 · 11^{3} + 2 · 11^{4} + 11^{6} and b = 1 + 6 · 11 + 9 · 11^{2} + 11^{4}. Assume z^{a} = 1. Then

g_{1}(x):=x(x+1)^{6}(x+2)^{10}(x+3)^{3}(x+4)^{2}(x+6)−(x+1)(x+2)^{6}(x+3)^{10}(x+4)^{3}(x+5)^{2}(x+7)

=(x+1)(x+2)^{6}(x+3)^{3}(x+4)^{2}[x(x+1)^{5}(x+2)^{4}(x+6)−(x+3)^{7}(x+4)(x+5)^{2}(x+7)]

is a multiple of f_{p}(x). Now Since the factor [...] is non-zero and has degree < 11, it is impossible for g_{1}(x) to be a multiple of f_{p}(x), a contradiction.

Next assume z^{b} = 1. Then

g′_{1}(x) : = x(x + 1)^{6}(x + 2)^{9}(x + 4) − (x + 1)(x + 2)^{6}(x + 3)^{9}(x + 5)
= (x + 1)(x + 2)^{6}[x(x + 1)^{5}(x + 2)^{3}(x + 4) − (x + 3)^{9}(x + 5)]

4 J. Y. Shi, Z. H. Wang is a multiple of f_{p}(x), and so is the factor [...]. But the latter has degree < 11. It again gives rise to a contradiction. So o(z) = m_{p} by Lemma 1, (b).

6. In a private communication (see [2]), K. F. Lai and A. Nelson suggested another way to show that o(α_{p}) = m_{p} as follows. Let k and q be as before. Write

(2)  q = b_{0} + b_{1}p + b_{2}p^{2} + ... + b_{p−1}p^{p−1},

where −p < b_{i} < p for 0 ⩽ i ⩽ p − 1. Such an expression (2) of q is not unique in general. Let I = {i | b_{i} > 0}, J = {j | b_{j} < 0}, q_{I} = ∑_{i∈I} b_{i} and q_{J} = − ∑_{j∈J} b_{j}. Then we may take (2) such that u = max{q_{I}, q_{J}} is as small as possible. If α_{p}^{q} = 1 then ∏_{i∈I}(α_{p} + i)^{b_{i}} = ∏_{j∈J}(α_{p} + j)^{−b_{j}}. This implies that f_{p}(x) should divide the polynomial h(x) := ∏_{i∈I}(x + i)^{b_{i}} − ∏_{j∈J}(x + j)^{−b_{j}}. Clearly, h(x) ≠ 0. If one can show that h(x) is not divisible by f_{p}(x) (e.g., in the case of deg h(x) < p), then we can conclude that α_{p}^{q} ≠ 1. Example 7. Let p, z, a, b be as in Example 5. Rewrite a = 1−5·11+4·11^{3}+2·11^{4}+11^{6}. If z^{a} = 1 then z(z+1)^{−5}(z+3)^{4}(z+4)^{2}(z+6) = 1 and hence z(z+3)^{4}(z+4)^{2}(z+6) = (z+1)^{5}. Then the polynomial g′(x) := x(x + 3)^{4}(x + 4)^{2}(x + 6) − (x + 1)^{5} should be a multiple of f_{p}(x), which is impossible since g′(x) ≠ 0 and deg g′(x) < 11. On the other hand, rewrite b = 1 − 5 · 11 − 11^{2} + 11^{3} + 11^{4}. If z^{b} = 1 then z(z + 1)^{−5}(z + 2)^{−1}(z + 3)(z + 4) = 1 and hence z(z + 3)(z + 4) = (z + 1)^{5}(z + 2). Then h′(x) := x(x + 3)(x + 4) − (x + 1)^{5}(x + 2) is a multiple of f_{p}(x), which is impossible since h′(x) ≠ 0 and deg h′(x) < 11. This implies that o(z) = m_{p} by Lemma 1, (b).

8. It is natural to ask whether or not either of these two methods will always apply. It would be interesting to find examples where one method works and not the other.

In applying either of the above methods, it also works if one replaces the number q = \frac{m_{p}}{k} by any multiple n of q with 1 ⩽ n ⩽ p^{p} − 1 and m_{p} ∤ n (reading “ m_{p} does

The order of a root of x^{p} − x − 1 over 𝔽_{p} 5

not divide n ”). Thus the method in 4. can be extended and reformulated as follows. Let V_{p} = {(b_{0}, b_{1}, ..., b_{p−1}) ∈ ℤ^{p} | 0 ⩽ b_{i} < p, ∑_{i} b_{i} ≠ 0}. Let V_{p}^{0} be the set of all (b_{0}, b_{1}, ..., b_{p−1}) in V_{p} that there exists some 1 ⩽ j < p with g_{j} ≠ 0 and deg \frac{g_{j}(x)}{h_{j}(x)} < p, where g_{j}(x) := ∏_{0⩽i<p}(x + i)^{b_{i}} − ∏_{0⩽i<p}(x + j + i)^{b_{i}} and, h_{j}(x) is the greatest common divisor of ∏_{0⩽i<p}(x + i)^{b_{i}} and ∏_{0⩽i<p}(x + j + i)^{b_{i}}. We see that no element of V_{p}^{0} has the form (b, ..., b) for any 1 ⩽ b < p.

For a prime divisor k of m_{p}, let C_{(k)} be a cyclic group of order k(p − 1) generated by λ. Then we can define an action of C_{(k)} on V_{p} by setting

λ · (b_{0}, b_{1}, ..., b_{p−1}) = (c_{0}, c_{1}, ..., c_{p−1}),

where c_{0} + c_{1}p + ... + c_{p−1}p^{p−1} ≡ b_{0} + b_{1}p + ... + b_{p−1}p^{p−1} + \frac{m_{p}}{k} (mod p^{p} − 1). Clearly, each C_{(k)}-orbit in V_{p} contains k(p − 1) elements. We have the following criterion for α_{p} to be of the order m_{p}.

Lemma 9. Let v_{h} = (a_{0}, a_{1}, ..., a_{p−1}) ∈ V_{p} be with \frac{m_{p}}{h} = a_{0} + a_{1}p + ... + a_{p−1}p^{p−1} for any h ∈ ℕ, h|m_{p}. If (C_{(k)} · v_{k}) ∩ V_{p}^{0} ≠ ∅ for any prime divisor k of m_{p}, then o(α_{p}) = m_{p}.

The method in 6. can also be extended and reformulated. Let W_{p} be the set of p-tuples (b_{0}, b_{1}, ..., b_{p−1}) ∈ ℤ^{p} with −p < b_{i} < p and 1 ⩽ b_{0} + b_{1}p + ... + b_{p−1}p^{p−1} ⩽ p^{p} − 1 modulo the relation (b_{0}, b_{1}, ..., b_{p−1}) ∼ (b′_{0}, b′_{1}, ..., b′_{p−1}) if b_{0} + b_{1}p + ... + b_{p−1}p^{p−1} = b′_{0} + b′_{1}p + ... + b′_{p−1}p^{p−1}. Define W_{p}^{0} to be a subset of W_{p} consisting of all such (b_{0}, b_{1}, ..., b_{p−1}) that the polynomial

g′(x) := ∏_{\begin{matrix}i \\ b_{i}>0 \end{matrix}}(x + i)^{b_{i}} − ∏_{\begin{matrix}i \\ b_{i}<0 \end{matrix}}(x + i)^{−b_{i}}

has degree < p. It is easily seen that no element w of W_{p}^{0} satisfies w ∼ (b, ..., b) for any 6 J. Y. Shi, Z. H. Wang 1 ⩽ b < p. For any prime divisor k of m_{p}, define an action of C_{(k)} on W_{p} in the same way as that on V_{p}. Then we have another criterion for α_{p} to be of order m_{p}.

Lemma 10. Let w_{h} = (a_{0}, a_{1}, ..., a_{p−1}) ∈ W_{p} be with q_{h} := \frac{m_{p}}{h} = a_{0} +a_{1}p+...+a_{p−1}p^{p−1} for any h ∈ ℕ, h|m_{p}. If (C_{q_{k}} · v_{k}) ∩ W_{p}^{0} ≠ ∅ for any prime divisor k of m_{p}, then o(α_{p}) = m_{p}.

The following result is concerned with a property of a prime factor of m_{p}. As a byproduct, the infinity for the number of prime numbers is an easy consequence of the result.

Lemma 11. Let k be a prime divisor of m_{p}. Then k ≡ 1 (mod p). This, in particular, implies that k > p.

Proof. We have

m_{p} = (p − 1)(p^{p−2} + 2p^{p−3} + 3p^{p−4} + ... + (p − 3)p^{2} + (p − 1)p) + 1.

So the integers m_{p} and p − 1 are coprime. Let k be a prime divisor of m_{p}. Then k|(p^{p} − 1) and hence p^{p} ≡ 1 (mod k). By Fermat’s Least Theorem, we have either p|(k − 1) or p ≡ 1 ( mod k). That is, either k ≡ 1 (mod p) or k|(p − 1). Since m_{p} and p − 1 are coprime, the latter case is impossible. This shows our result. □

12. To use Lemma 9, one need study the subsets V_{p}^{0} and C_{(k)} · v_{k} of V_{p} for any prime divisor k of m_{p}. By Lemma 11, we have v_{k} = (1, a_{1}, ..., a_{p−1}) for any prime divisor k of m_{p}. For any v = (b_{0}, b_{1}, ..., b_{p−1}) in V_{p}, let l(v) := ∑_{i=0}^{p−1} b_{i}, m(v) = min{b_{i} | 0 ⩽ i < p}, m′(v) = max{b_{i} | 0 ⩽ i < p}, d(v) = l(v) − p · m(v) and d′(v) = p · m′(v) − l(v). Then we claim that V_{p}^{0} contains all v = (b_{0}, b_{1}, ..., b_{p−1}) in V_{p} with 0 < d(v) ⩽ p + 1. For, it is obvious that v ∈ V_{p}^{0} for 0 < d(v) ⩽ p. If d(v) = p + 1 then there exist at least two i, j

The order of a root of x^{p} − x − 1 over 𝔽_{p} 7

with 0 ⩽ i < j < p and b_{i}, b_{j} > m(v). Hence deg \frac{g_{j−i}(x)}{h_{j−i}(x)} < p and so v is in V_{p}^{0} also. If v = (b_{0}, b_{1}, ..., b_{p−1}) ∈ C_{(k)} · v_{k} for some prime divisor k of m_{p} with 0 < d′(v) ⩽ p + 1, then we have V_{p}^{0} ∩ C_{(k)} · v_{k} ≠ ∅. This is because (m′(v) − b_{0}, ..., m′(v) − b_{p−1}) is in V_{p}^{0} ∩ C_{(k)} · v_{k}.

Also, one need study the subsets W_{p}^{0} and C_{(k)} · w_{k} of W_{p} for any prime divisor k of m_{p} in order to use Lemma 10.

It is interesting to study some combinatorial properties for the sets V_{p}^{0} and C_{(k)} · v_{k}, e.g., the cardinality of the set V_{p}^{0}, the distribution of these two subsets in V_{p}, etc. The same for the sets W_{p}^{0} and C_{(k)} · w_{k}.

References

1. Zhi-jie Chen and Zhen-hua Wang, preprint (2001).

2. K. F. Lai and A. Nelson, A private communication (2001).

3. R. Lidl and H. Niederreoter, Finite Fields, Addison-Wesley, 1983.

4. Man Young Rhce, Cryptography and Secure Communications, McGraw-Hill Book Co., 1994.