1 Introduction
Finding elements of high multiplicative order in a finite field is an interesting problem in computational number theory and has applications in cryptography (for instance: Discrete Logarithm Problem). A general method to find high order elements was given in [
11], later improved in [
8,
18]. Another general result in this area is an algorithmic technique for finding primitive elements which is devised in [
12]. Such technique is efficient in finite fields of small characteristic. Other strategies which allow to construct elements of high order usually address specific sequences of finite fields. In this regard, methods involving Gauss periods were first proposed in the results summarized in [
26]. After that, an extensive literature followed with works such as [
1,
5,
16,
17,
19]. Recently, Artin-Schreier extensions were also effectively used in [
13,
21]. Another interesting approach is to look for high order elements which arise as coordinates of points on an algebraic curve defined over a finite field (see for example [
4,
24,
25]). One way which has been explored for generating elements of this type is through the iterative use of polynomial equations of type
\(f(x_{n - 1},x_n) = 0\), defining suitable towers of fields, which we address as
recursive towers in this work. Examples of this can be found in [
3,
20,
22,
25].
In [
3], a recursive tower defined by
\(f(x_{n - 1},x_n)\) is used to produce elements
\(\delta _n\) with high multiplicative order in
\(\mathbb {F}_{q^{2^n}}\), for an odd
q, and in
\(\mathbb {F}_{q^{3^n}}\), for
\(q \ne 3\). The choice of the polynomial
f for the recursive process to generate high order elements in finite field extensions, was limited to the equations of the modular curve towers in [
10].
In this work, we attempt to generalize the choice of the polynomials. We illustrate in detail several interesting towers of fields defined by
\(x_n^2 + x_n = v(x_{n - 1})\), where
\(v(x) \in \mathbb {F}_{q}[x]\), for an odd
q, or
\(x_n^3 + x_n = v(x_{n - 1})\), for
\(v(x) \in \mathbb {F}_{2}[x]\). These towers generate elements of high orders in
\(\mathbb {F}_{q^{2^n}}\) and in
\(\mathbb {F}_{2^{2 \cdot 3^n}}\), for
\(n \ge 1\). We also give a recipe for finding other towers of the same form which have similar properties. The simple algebraic conditions given in Sections
3 and
4, which differ partially from the conditions required in [
3] (Remark
3.1 below), seem to play an important role toward this. In fact, in many of the cases we studied, these conditions are useful to prove the existence of high order elements
\(x_n\), in the field extension.
Throughout this paper,
\(\delta _n\) in
\(\mathbb {F}_{q^{2^n}}\) is the discriminant of the polynomial
\(f(x_{n},y)\) in
\(\mathbb {F}_{q^{2^n}}[y]\). In Corollary
3.5, we prove that the multiplicative orders of
\(x_n\) and
\(\delta _n\) grow very fast if
\(x_{n - j}^2\) and
\(\delta _{n-j}^2\) do not belong to
\(\mathbb {F}_{q^{2^{n - j - 1}}}\), for all
\(j < n-1\). Similar results hold also in even characteristic, see Corollary
4.3. Notably, despite the bounds obtained are similar and have no advantage with respect to the ones in [
3], the even characteristic case turns out to be completely new. In particular, no additional conditions on the discriminant are required, and the details of the proof are worked out in a different manner. Furthermore the numerical performance of some of our examples improves slightly on [
3], in the iterations we were able to compute. As already mentioned above, the polynomials used in [
3] are the models of certain modular curves given in [
10]. Despite this fact, a possible relation of the construction of high order elements with the arithmetic properties of such curves does not seem to play a role in the proof of the lower bounds. Instead, in one case, we do make use of some arithmetic properties of the algebraic curve considered by us (Lemma
5.4).
A comparative study with other relevant literature has also been carried-out. For example, a specific construction of high order elements in the same type of fields of odd characteristic
q can be found in [
7], and some variations on it are in [
6,
15]. Comparing the numerical performance of their construction with our variety of examples, we observe that the results are similar for
\(q \equiv 1 \pmod 4\), while for
\(q \equiv 3 \pmod 4\) our construction performs better (see Sect.
7 for examples with
\(q=3,11\)).
In Sect.
2, we introduce the notation that we use in the paper. In Sects.
3 and
4, we give the main results which allow us to obtain the lower bounds on the order of
\(x_n\) and
\(\delta _n\). Section
3 deals with odd characteristic and Sect.
4 deals with even characteristic. The lists of towers satisfying the properties given in Sects.
3 and
4 are provided in Sects.
5 and
6, respectively. Finally, in Sect.
7, we list numerical results obtained using MAGMA [
2], about the seven towers listed in Sects.
5 and
6.
2 Background and notation
Let q be a prime and let \(\mathbb {F}_q\) and \(\mathbb {F}_q^*\) denote the finite field with q elements and its multiplicative group, respectively. We recall that every extension \(\mathbb {F}_{q^r}/\mathbb {F}_q\) of finite fields, for a positive integer r, is cyclic and the Galois group is generated by the Frobenius automorphism \(a\mapsto a^q\), for each \(a\in \mathbb {F}_{q^r}\).
By
tower of fields, or simply a
tower, we mean a sequence of field extensions
$$\begin{aligned} K_1\subset K_2\subset \ldots \subset K_n\subset \ldots . \end{aligned}$$
We are interested in infinite towers, namely towers such that the degree
\([K_n : K_1]\) grows to infinity. All the towers considered in this paper are actually finite, normal and separable, i.e., each extension
\(K_n/K_{n - 1}\) is finite, normal and separable, for every
\(n > 1\). When
q is odd, for each positive integer
n, let
\(K_n = \mathbb {F}_{q}(x_n)\), where the element
\(x_n \in \mathbb {F}_{q^{2^n}}\) is given by a recursive formula
\(f(x_{n - 1},x_n) = 0\), for a polynomial
\(f(x,y) \in \mathbb {F}_{q}[x,y]\). In this case, we say that the tower
\(K_1 \subset K_2 \subset \ldots \subset K_n \subset \ldots \) is defined by
\(f(x_{n - 1},x_n)\) and we address this kind of towers as
recursive towers. We focus on towers defined by
\(f(x_{n - 1},x_n) = x_n^2 + x_n - v(x_{n - 1})\), for
\(n \ge 2\), with
\(x_1 \in \mathbb {F}_{q^2}\), and where
v(
x) is a polynomial in
\(\mathbb {F}_{q}[x]\). We denote by
\(\delta _n\) the discriminant
\(\delta _n = 1 + 4v(x_n)\), for
\(n \ge 1\). We point out that both elements
\(x_n\) and
\(\delta _n\) belong to
\(\mathbb {F}_{q^{2^n}}\), but they could also lie in a smaller extension
\(\mathbb {F}_{q^{2^k}}\) for some
\(k < n\). Given the tower defined by
\(f(x_{n-1},x_n)\), we denote by
\(g(x,y) \in \mathbb {F}_{q}[x,y]\) a polynomial giving the relation between two consecutive discriminants
\(\delta _{n-1}\) and
\(\delta _{n}\), namely
\(g(\delta _{n-1},\delta _{n})=0\). In the case of even characteristic (Sects.
4 and
6), we deal with towers defined by
\(f(x_{n-1},x_n) = x_n^3 + x_n + v(x_{n - 1})\), with
\(x_n \in \mathbb {F}_{2^{2 \cdot 3^n}}\), for
\(n \ge 1\), and
v(
x) being a polynomial in
\(\mathbb {F}_{2}[x]\).
Given two positive integers j and n, such that \(j < n\), we denote the norm of the field extension \(\mathbb {F}_{q^{2^n}}/ \mathbb {F}_{q^{2^{n - j}}}\) by, \(\mathrm {N}_{n,j} :\mathbb {F}_{q^{2^n}} \rightarrow \mathbb {F}_{q^{2^{n - j}}}\). The norm in the odd case is \(\mathrm {N}_{n,j}(x) = x^{\prod _{i = 1}^j (q^{2^{n - i}}+1)}\). In order to apply the same techniques to even characteristic, we also denote by \(\mathrm {N}_{n,j}:\mathbb {F}_{2^{2\cdot 3^n}}\rightarrow \mathbb {F}_{2^{2 \cdot 3^{n-j}}}\) the norm of the extension \(\mathbb {F}_{2^{2 \cdot 3^n}}/ \mathbb {F}_{2^{2 \cdot 3^{n - j}}}\), namely \(\mathrm {N}_{n,j}(x) = x^{\prod _{i = 1}^j (4^{2 \cdot 3^{n-i}} + 4^{3^{n - i}} + 1)}\). For every characteristic, we use the conventions \(\mathrm {N}(x):=\mathrm {N}_{n,1}(x)\) and \(\mathrm {N}_{n,0}(x)=x\).
We use the following lemma for estimating the order of the elements in finite fields.
In order to prove that a cubic polynomial is irreducible, we need the following results.
3 Towers in odd characteristic
In order to find good towers we restrict our search to polynomials
\(f(x,y)=y^2+y-v(x)\), with
\(v(x)\in \mathbb {F}_{q}[x]\) being a non-zero polynomial, which satisfy Condition
(1) below and at least one of the last two conditions:
(1)
\(\frac{f(x_{n - 1},0)}{x_{n - 1}}\) is a square in \(\mathbb {F}_{q^{2^{n-1}}}\) for \(n \ge 2\);
(2)
\(\frac{g(\delta _{n - 1},0)}{x_{n - 1}}\) is a square in \(\mathbb {F}_{q^{2^{n-1}}}\) for \(n \ge 2\);
(2’)
\(\frac{g(\delta _{n - 1},0)}{\delta _{n - 1}}\) is a square in \(\mathbb {F}_{q^{2^{n-1}}}\) for \(n \ge 2\).
The following key proposition ensures that all the polynomials
\(f(x_{n - 1}, x_{n})\) listed in Sect.
5 define infinite towers of fields. In particular it shows that
\([K_n : K_{n - 1}] = 2\), for all
\(n > 1\). The argument of the proof is the corresponding analogue of [
3, Proposition 1] but it could be applied to many different towers.
The importance of this proposition is evident if we consider Corollary
3.5 below, which is an analogue of [
3, Proposition 2]. We first state the following property of the norm that is used in the proof of the corollary.
4 Towers in even characteristic
The even analogue of Conditions
(1) and
(2) in the odd case for polynomials
\(f(x,y)=y^3+y+v(x)\), with
\(v(x)\in \mathbb {F}_{2}[x]\), is:
(3)
There exists an integer \(e\ge 0\) such that \(f(x_{n-1},0)=x_{n-1}^{2^e}\) for all \(n\ge 2\).
This means that we can restrict our study to polynomials in the form
\(f(x,y)=y^3+y+x^{2^e}\), with
\(e\ge 0\), and deduce similar results as in the previous section. In Sect.
6, we find some cases where the towers defined by polynomials
\(f(x_{n - 1},x_n)\) are infinite and Galois. This is achieved by finding a suitable initial element
\(x_1\in \mathbb {F}_{2^6}\). Under these hypotheses we have an analogue of Proposition
3.3.
The analogue of Lemma
3.4 in even characteristic is the following:
5 Examples of good towers in odd characteristic
In this section we find high order elements in
\(\mathbb {F}_{q^{2^n}}\), for odd
q, using five good towers. In this section, we denote by
\(\varepsilon \) the element
\(4^{-1}\) inside
\(\mathbb {F}_{q}\). We consider the polynomials
\(f_i(x_{n - 1}, x_n) := x_n^2 + x_n - v_i(x_{n - 1})\), for
\(i \in \{1, 2,\ldots , 5\}\), where
\(v_i(x)\) is a polynomial chosen as follows:
(1)
\(v_1(x) := \varepsilon x;\)
(2)
\(v_2(x) := 4x{(x + 3\varepsilon )}^2;\)
(3)
\(v_3(x) := 2\varepsilon x;\)
(4)
\(v_4(x) := 8x{(2x + 3\varepsilon )}^2;\)
(5)
\(v_5(x) := 8x{(x + 3\varepsilon )}^2.\)
The next two lemmas ensures the existence of a non-square
\(x_1\) such that
\(\delta _1\) is a non-square in
\(\mathbb {F}_{q^2}\) as well. This would be the corresponding analogue of [
3, Lemma 3], but here we also need that
both \(x_1\) and
\(\delta _1\) must be non-squares. This requires more effort, especially for the last tower
\(f_5(x_{n-1},x_n)\) below, but, as a balance, this gives a lower bound for the order of
\(x_n\), also.
The present proof relies mainly on elementary combinatorial arguments.
In order to show the existence of a suitable initial element \(x_1\) for the tower defined by \(f_5(x_{n-1},x_n)\) we prove the following lemma.
The following corollary ensures the existence of towers defined by \(f_i(x_{n - 1},x_n)\) generating high order elements for \(i \in \{ 1,2,\ldots ,5\}\).
As in [
3], the bound of the previous corollary does not seem to be sharp, in fact in many cases we were able to construct generators of the multiplicative group
\(\mathbb {F}_{q^{2^n}}^*\), whose order is
\(q^{2^n} - 1\), which is much higher than
\(2^{\frac{n^2}{2}}\). The interested reader can compare the tables in Sect.
7 with the experimental results of [
3].
Of course could exist other towers satisfying analogues of Conditions (1) and (2) or Conditions (1) and (2’) above. An extensive computer search could show the non-existence of similar examples of the form \(f(x_{n - 1},x_n) = x_n^2 + x_n + v(x_{n - 1})\), with \(\deg (v(x)) \le 3\), at least for small prime fields.
6 Examples of good towers in even characteristic
In this section we list polynomials generating high order elements, as in Sect.
5. We have to adapt some proofs in even characteristic, since we have to prove that our cubic polynomials
\(f(x_{n-1},y)\) are irreducible in
\(\mathbb {F}_{2^{2\cdot 3^{n-1}}}[y]\). Let
e be a non-negative integer. In the following results, we prove that
\(f(x_{n - 1},x_n):= x_n^3+x_n+x_{n-1}^{2^e}\) actually defines an infinite normal separable tower.
Part (iii) in the previous lemma shows by induction that if \(f(x_1,y)=y^3+y+x_{1}^{2^e}\) is irreducible in \(\mathbb {F}_{2^6}[y]\), then \(f(x_n,y)=y^3+y+x_{n}^{2^e}\) is also irreducible in \(\mathbb {F}_{2^{2\cdot 3^{n}}}[y]\) for all \(n>1\). It follows that the Galois group of the splitting field of \(f(x_n,y)\) is the cyclic group \(\mathbb {Z}/3 \mathbb {Z}\).
We summarize the results above in the following corollary, which provides a good initial choice for \(x_1\), resulting in \(f(x_{n-1},x_n)\) to be a normal separable recursive tower.
In Sect.
7 we collated the numerical results for
\(f_6(x_{n - 1},x_n) := x_n^3 + x_n + x_{n - 1}\) and
\(f_7(x_{n - 1},x_n) := x_n^3 + x_n + x_{n - 1}^2\) corresponding to
\(e=0\) and
\(e=1\), respectively. The initial element
\(x_1\) is one of the roots of
\(h(x) := x^6 + x^5 + x^3 + x^2 + 1\) as explained in the proof of Corollary
6.2.
Table 1
Results for \(f_1(x_{n - 1},x_n)\) for odd \(q\le 11\)
n | \(\log _2\)(o(\(x_n\))) | \(\log _2\)(o(\(\delta _n\))) | \(\log _2\)(o(\(x_n\))) | \(\log _2\)(o(\(\delta _n\))) | \(\log _2\)(o(\(x_n\))) | \(\log _2\)(o(\(\delta _n\))) | \(\log _2\)(o(\(x_n\))) | \(\log _2\)(o(\(\delta _n\))) |
1 | 3.0 | 3.0 | 4.6 | 3.0 | 5.6 | 5.6 | 6.9 | 5.3 |
2 | 6.3 | 6.3 | 9.3 | 9.3 | 11.2 | 11.2 | 13.8 | 13.8 |
3 | 12.7 | 12.7 | 18.6 | 18.6 | 22.5 | 22.5 | 27.7 | 27.7 |
4 | 25.4 | 25.4 | 37.2 | 37.2 | 44.9 | 44.9 | 55.4 | 55.4 |
5 | 50.7 | 50.7 | 74.3 | 74.3 | 89.8 | 89.8 | 110.7 | 110.7 |
6 | 101.4 | 101.4 | 148.6 | 148.6 | 179.7 | 179.7 | 221.4 | 221.4 |
7 | 202.9 | 202.9 | 297.2 | 297.2 | 359.3 | 359.3 | 442.8 | 442.8 |
8 | 405.8 | 405.8 | 594.4 | 594.4 | 718.7 | 718.7 | 883.3 | 885.6 |
9 | 811.5 | 811.5 | 1188.8 | 1188.8 | 1437.4 | 1437.4 | 1771.2 | 1771.2 |
Table 2
Results for \(f_2(x_{n - 1},x_n)\) for odd \(q\le 11\)
n | \(\log _2\)(o(\(x_n\))) | \(\log _2\)(o(\(\delta _n\))) | \(\log _2\)(o(\(x_n\))) | \(\log _2\)(o(\(\delta _n\))) | \(\log _2\)(o(\(x_n\))) | \(\log _2\)(o(\(\delta _n\))) | \(\log _2\)(o(\(x_n\))) | \(\log _2\)(o(\(\delta _n\))) |
1 | 3.0 | 3.0 | 4.6 | 4.6 | 5.6 | 5.6 | 6.9 | 4.6 |
2 | 6.3 | 6.3 | 9.3 | 9.3 | 11.2 | 11.2 | 13.8 | 12.3 |
3 | 12.7 | 12.7 | 18.6 | 18.6 | 20.9 | 22.5 | 26.1 | 27.7 |
4 | 25.4 | 25.4 | 37.2 | 37.2 | 44.9 | 44.9 | 55.4 | 48.9 |
5 | 50.7 | 50.7 | 74.3 | 74.3 | 88.3 | 89.8 | 106.6 | 110.7 |
6 | 101.4 | 101.4 | 148.6 | 148.6 | 179.7 | 179.7 | 221.4 | 219.8 |
7 | 202.9 | 202.9 | 297.2 | 297.2 | 357.8 | 359.3 | 441.2 | 442.8 |
8 | 405.8 | 405.8 | 594.4 | 594.4 | 718.7 | 718.7 | 885.6 | 879.2 |
9 | 811.5 | 811.5 | 1188.8 | 1188.8 | 1435.8 | 1437.4 | 1767.1 | 1771.2 |
Table 3
Results for \(f_3(x_{n - 1},x_n)\) for odd \(q \le 11\)
n | \(\log _2\)(o(\(x_n\))) | \(\log _2\)(o(\(\delta _n\))) | \(\log _2\)(o(\(x_n\))) | \(\log _2\)(o(\(\delta _n\))) | \(\log _2\)(o(\(x_n\))) | \(\log _2\)(o(\(\delta _n\))) | \(\log _2\)(o(\(x_n\))) | \(\log _2\)(o(\(\delta _n\))) |
1 | 3.0 | 3.0 | 4.6 | 4.6 | 5.6 | 4.0 | 6.9 | 5.3 |
2 | 6.3 | 4.0 | 9.3 | 5.6 | 11.2 | 5.0 | 13.8 | 6.3 |
3 | 12.7 | 5.0 | 18.6 | 6.6 | 22.5 | 6.0 | 25.4 | 7.3 |
4 | 25.4 | 6.0 | 37.2 | 7.6 | 44.9 | 7.0 | 51.3 | 8.3 |
5 | 50.7 | 7.0 | 74.3 | 8.6 | 89.8 | 8.0 | 106.6 | 9.3 |
6 | 101.4 | 8.0 | 148.6 | 9.6 | 179.7 | 9.0 | 217.3 | 10.3 |
7 | 202.9 | 9.0 | 297.2 | 10.6 | 359.3 | 10.0 | 436.4 | 11.3 |
8 | 405.8 | 10.0 | 594.4 | 11.6 | 718.7 | 11.0 | 881.5 | 12.3 |
9 | 811.5 | 11.0 | 1188.8 | 12.6 | 1437.4 | 12.0 | 1767.1 | 13.3 |
Table 4
Results for \(f_4(x_{n - 1},x_n)\) for odd \(q \le 11\)
n | \(\log _2\)(o(\(x_n\))) | \(\log _2\)(o(\(\delta _n\))) | \(\log _2\)(o(\(x_n\))) | \(\log _2\)(o(\(\delta _n\))) | \(\log _2\)(o(\(x_n\))) | \(\log _2\)(o(\(\delta _n\))) | \(\log _2\)(o(\(x_n\))) | \(\log _2\)(o(\(\delta _n\))) |
1 | 3.0 | 3.0 | 4.6 | 4.6 | 5.6 | 5.6 | 6.9 | 4.6 |
2 | 6.3 | 4.0 | 9.3 | 7.7 | 11.2 | 11.2 | 13.8 | 13.8 |
3 | 12.7 | 5.0 | 17.0 | 17.0 | 22.5 | 20.9 | 27.7 | 27.7 |
4 | 25.4 | 6.0 | 35.6 | 37.2 | 41.0 | 43.3 | 55.4 | 55.4 |
5 | 50.7 | 7.0 | 72.7 | 72.7 | 89.8 | 89.8 | 110.7 | 109.1 |
6 | 101.4 | 8.0 | 147.0 | 148.6 | 177.3 | 179.7 | 221.4 | 219.8 |
7 | 202.9 | 9.0 | 295.6 | 295.6 | 359.3 | 357.8 | 442.8 | 441.2 |
8 | 405.8 | 10.0 | 592.8 | 594.4 | 717.1 | 717.1 | 885.6 | 884.0 |
9 | 811.5 | 11.0 | 1187.2 | 1188.8 | 1435.8 | 1435.8 | 1769.6 | 1771.2 |
Table 5
Results for \(f_5(x_{n - 1},x_n)\) for odd \(q\le 11\)
n | \(\log _2\)(o(\(x_n\))) | \(\log _2\)(o(\(\delta _n\))) | \(\log _2\)(o(\(x_n\))) | \(\log _2\)(o(\(\delta _n\))) | \(\log _2\)(o(\(x_n\))) | \(\log _2\)(o(\(\delta _n\))) | \(\log _2\)(o(\(x_n\))) | \(\log _2\)(o(\(\delta _n\))) |
1 | 3.0 | 3.0 | 4.6 | 4.6 | 5.6 | 5.6 | 6.9 | 3.0 |
2 | 6.3 | 4.0 | 9.3 | 5.6 | 8.9 | 5.0 | 13.8 | 5.6 |
3 | 12.7 | 5.0 | 18.6 | 8.7 | 22.5 | 12.2 | 27.7 | 14.8 |
4 | 25.4 | 6.0 | 35.6 | 18.0 | 42.6 | 23.5 | 55.4 | 28.7 |
5 | 50.7 | 7.0 | 72.7 | 38.2 | 89.8 | 45.9 | 110.7 | 56.4 |
6 | 101.4 | 8.0 | 147.0 | 73.7 | 179.7 | 89.3 | 221.4 | 110.1 |
7 | 202.9 | 9.0 | 295.6 | 149.6 | 359.3 | 179.1 | 442.8 | 220.8 |
8 | 405.8 | 10.0 | 592.8 | 296.6 | 718.7 | 358.8 | 883.3 | 442.8 |
9 | 811.5 | 11.0 | 1187.2 | 595.4 | 1437.4 | 718.1 | 1771.2 | 885.0 |
Table 6
Upper bounds for odd \(q\le 11\) and lower bound
n | \(\log _2(q^{2^n}-1)\) | \(\log _2(q^{2^n}-1)\) | \(\log _2(q^{2^n}-1)\) | \(\log _2(q^{2^n}-1)\) | \(\log _2(2^{(n^2+3n)/2})\) |
1 | 3.0 | 4.6 | 5.6 | 6.9 | 2.0 |
2 | 6.3 | 9.3 | 11.2 | 13.8 | 5.0 |
3 | 12.7 | 18.6 | 22.5 | 27.7 | 9.0 |
4 | 25.4 | 37.2 | 44.9 | 55.4 | 14.0 |
5 | 50.7 | 74.3 | 89.8 | 110.7 | 20.0 |
6 | 101.4 | 148.6 | 179.7 | 221.4 | 27.0 |
7 | 202.9 | 297.2 | 359.3 | 442.8 | 35.0 |
8 | 405.8 | 594.4 | 718.7 | 885.6 | 44.0 |
9 | 811.5 | 1188.8 | 1437.4 | 1771.2 | 54.0 |
7 Numerical results
In this section, we have collated the multiplicative orders
\(o(x_n)\) (and
\(o(\delta _n )\) for
q odd) for small
n in the towers defined by
\(f_i (x_{n - 1}, x_n)\), for
\(i = 1, 2,\ldots ,7\). In most of the cases we obtained generators of the multiplicative groups
\(\mathbb {F}_{q^{2^n}}^*\) and
\(\mathbb {F}_{2^{2 \cdot 3^n}}^*\). We tabulated base 2 logarithm of the orders as they grow exponentially. In particular, in Tables
1,
2,
3,
4,
5 we list the numerical results in odd characteristic for
\(f_1,\ldots ,f_5\). The interested reader can also find the lower and upper bounds for
\(o(x_n)\) and
\(o(\delta _n)\) listed in Tables
6 and
7, for odd and even characteristic respectively. Finally, in Table
8, we compare one of our examples in characteristic 3, with the constructions of [
3] and [
7].
MAGMA [
2] computational algebra system was used for the experiments and a sample MAGMA code and output, for
\(q = 11\) can be found in [
9]. The performance of the code depends on the efficiency of the
root finding algorithm that one uses. We have used the standard function of MAGMA [
2] for finding roots.
Table 7
Results for \(f_6(x_{n - 1},x_n)\) and \(f_7(x_{n - 1},x_n)\) for \(q=2\) and related lower and upper bounds
n | \(\log _2\)(o(\(x_n\))) | \(\log _2\)(o(\(x_n\))) | \(\log _2(3^{n(n+3)/2})\) | \(\log _2(4^{3^n}-1) \) |
1 | 6.0 | 6.0 | 3.2 | 6.0 |
2 | 18.0 | 18.0 | 7.9 | 18.0 |
3 | 54.0 | 54.0 | 14.3 | 54.0 |
4 | 162.0 | 162.0 | 22.2 | 162.0 |
5 | 486.0 | 486.0 | 31.7 | 486.0 |
6 | 1458.0 | 1458.0 | 42.8 | 1458.0 |
Table 8
Comparative analysis
1 | 3.0 | 3.0 | 3.0 | 3.0 | 3.0 |
2 | 6.3 | 6.3 | 5.3 | 4.0 | 4.3 |
3 | 12.7 | 12.7 | 10.7 | 5.0 | 7.4 |
4 | 25.4 | 25.4 | 22.4 | 6.0 | 13.7 |
5 | 50.7 | 50.7 | 46.8 | 7.0 | 26.4 |
6 | 101.4 | 101.4 | 96.5 | 8.0 | 51.7 |
7 | 202.9 | 202.9 | 197.0 | 9.0 | 102.4 |
8 | 405.8 | 405.8 | 399.0 | 10.0 | 203.9 |
9 | 811.5 | 811.5 | 804.0 | 11.0 | 406.8 |
8 Conclusion and future work
In [
3], the choice of polynomials for the recursive process to generate high order elements in finite field extensions, was limited to the equations of the modular curve towers in [
10]. In this work, we attempted to generalize the choice of the polynomials. This provides us with more examples with similar properties. A central theme of this research work is to find a recipe to choose polynomials to use the recursive process. There might be other equations which could help to attain similar bounds. It would be interesting to understand in general which equations are good and which ones are not. We also point out that there could be other explicit towers satisfying similar properties. We were in fact attracted previously by other interesting examples with
v(
x) being a polynomial of higher degree over
\(\mathbb {F}_{q}\), which turned out to give high order elements, although the proof seems to be much harder. A possible relation linking together these equations could allow to obtain other families of towers with good parameters. We also expect to improve our results by extending the construction of Sect.
3 to higher degree polynomials and extending the construction of Sect.
4 to odd characteristic
\(q > 3\).
Another question that would be interesting to explore is the possible relation with some geometric construction. In fact, since the tower in [
3] is obtained from the equation of a modular curve, it is a natural question to ask whether our results have a geometric interpretation or not. We hope that a finer understanding of the subject might also possibly provide a recipe for finding high order elements from towers obtained from different forms.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.