Multiplicative orders of elements in Conway's towers of finite fields
We give a lower bound on multiplicative orders of certain elements in defined by Conway towers of finite fields of characteristic 2 and also formulate a condition under that these elements are primitive.
Gespeichert in:
| Datum: | 2018 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2018
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/188353 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Multiplicative orders of elements in Conway's towers of finite fields / R. Popovych // Algebra and Discrete Mathematics. — 2018. — Vol. 25, № 1. — С. 137-146. — Бібліогр.: 14 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-188353 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1883532023-02-24T01:27:16Z Multiplicative orders of elements in Conway's towers of finite fields Popovych, R. We give a lower bound on multiplicative orders of certain elements in defined by Conway towers of finite fields of characteristic 2 and also formulate a condition under that these elements are primitive. 2018 Article Multiplicative orders of elements in Conway's towers of finite fields / R. Popovych // Algebra and Discrete Mathematics. — 2018. — Vol. 25, № 1. — С. 137-146. — Бібліогр.: 14 назв. — англ. 1726-3255 2010 MSC: 11T30. http://dspace.nbuv.gov.ua/handle/123456789/188353 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
We give a lower bound on multiplicative orders of certain elements in defined by Conway towers of finite fields of characteristic 2 and also formulate a condition under that these elements are primitive. |
| format |
Article |
| author |
Popovych, R. |
| spellingShingle |
Popovych, R. Multiplicative orders of elements in Conway's towers of finite fields Algebra and Discrete Mathematics |
| author_facet |
Popovych, R. |
| author_sort |
Popovych, R. |
| title |
Multiplicative orders of elements in Conway's towers of finite fields |
| title_short |
Multiplicative orders of elements in Conway's towers of finite fields |
| title_full |
Multiplicative orders of elements in Conway's towers of finite fields |
| title_fullStr |
Multiplicative orders of elements in Conway's towers of finite fields |
| title_full_unstemmed |
Multiplicative orders of elements in Conway's towers of finite fields |
| title_sort |
multiplicative orders of elements in conway's towers of finite fields |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2018 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/188353 |
| citation_txt |
Multiplicative orders of elements in Conway's towers of finite fields / R. Popovych // Algebra and Discrete Mathematics. — 2018. — Vol. 25, № 1. — С. 137-146. — Бібліогр.: 14 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT popovychr multiplicativeordersofelementsinconwaystowersoffinitefields |
| first_indexed |
2025-07-16T10:22:38Z |
| last_indexed |
2025-07-16T10:22:38Z |
| _version_ |
1837798637233504256 |
| fulltext |
“adm-n1” — 2018/4/2 — 12:46 — page 137 — #139
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 25 (2018). Number 1, pp. 137–146
c© Journal “Algebra and Discrete Mathematics”
Multiplicative orders of elements
in Conway’s towers of finite fields
Roman Popovych
Communicated by A. P. Petravchuk
Abstract. We give a lower bound on multiplicative orders
of certain elements in defined by Conway towers of finite fields of
characteristic 2 and also formulate a condition under that these
elements are primitive.
Introduction
Elements with high multiplicative order are often needed in several
applications that use finite fields [11]. Ideally we want to have a possibility
to obtain a primitive element for any finite field. However, if we have not
any factorization of the order of finite field multiplicative group, it is not
known how to rich the goal. That is why one considers less ambitious
question: to find an element with provable high order. It is sufficient in
this case to obtain a lower bound on the order. The problem is considered
both for general and special finite fields [1, 3, 7, 12, 13].
Another less ambitious, but supposedly more important question is
to find primitive elements for a class of special finite fields. A polynomial
algorithm that find a primitive element in a finite field of small character-
istic is described in [8]. However, the algorithm relies on two unproved
assumptions and is not supported by any computational example. Our
paper can be considered as a step towards this direction. We give a lower
bound on multiplicative orders of certain elements in binary recursive
2010 MSC: 11T30.
Key words and phrases: finite field, multiplicative order, Conway’s tower.
“adm-n1” — 2018/4/2 — 12:46 — page 138 — #140
138 Multiplicative orders of elements
extensions of finite fields defined by Conway [4,5,14] and also formulate a
condition under that these elements are primitive. Fq denotes finite field
with q elements.
The following finite fields of characteristic 2 are considered:
c−1 = 1, L−1 = F2(c−1) = F2,
for i > −1, Li+1 = Li(ci+1), where ci+1 satisfies the equation
c2i+1 + ci+1 +
i
∏
j=−1
cj = 0.
So, the following tower of finite fields arises:
L−1 = F2(c−1) = F2 ⊂ L0 = F2(c0) ⊂ L1 = L0(c1) ⊂ L2 = L1(c2) ⊂ . . .
Such a construction is very attractive from the point of view of applications,
since one can perform operations with finite field elements recursively,
and therefore effectively [9].
It is easy to verify directly the following facts: element c0 is primitive
in L0, and element c1 is primitive in L1. On the other hand, H. Lenstra
[10, Exercise 2] showed: if i > 2, then element ci is not primitive in Li.
Some primitive elements for the fields L2, L3, L4 are found in [2] using
SageMath. Therefore, for i > 2, the following questions arise: 1) what is
a lower bound on the multiplicative order O(ci) of element ci; 2) what
elements are primitive in the fields Li. We partially answer the questions
in Theorems 3, 4 and Corollaries 2, 3, 4, 5.
1. Preliminaries
Observe that, for i > 0, the number of elements of the multiplicative
group L∗
i = Li\{0} equals 22
i+1
− 1. If to denote the Fermat numbers by
Nj = 22
j
+ 1 (j > 0), then the cardinality of L∗
i is
∏i
j=0Nj . We will use
for k > 0 the denotation ak =
∏k
j=0 cj .
Lemma 1 ([6, Section 1.3.2]). For i > 1, Ni =
∏i−1
j=0Nj + 2.
Lemma 2 ([6, Section 1.3.2]). Any two Fermat numbers are coprime.
Lemma 3. For j > 2, a divisor α > 1 of the number Nj is of the form
α = l · 2j+2 + 1, where l is a positive integer.
“adm-n1” — 2018/4/2 — 12:46 — page 139 — #141
R. Popovych 139
Proof. The result obtained by Euler and Lucas (see [6, theorem 1.3.5])
states: for j > 2, a prime divisor of Nj is of the form l · 2j+2 + 1, where l
is a positive integer. Clearly, a product of two numbers of the specified
form is a number of the same form. Hence, the result follows.
Lemma 4. For i > 2 and 1 6 j 6 i− 1, gcd(Ni + 1, Nj) = 1.
Proof. By lemma 1, Ni +1 =
∏i−1
j=0Nj +3. A common divisor of numbers
Ni + 1 and
∏i−1
j=0Nj divides their difference that equals 3. As N0 = 3,
gcd(Ni + 1,
∏i−1
j=0Nj) = 3. Since, by lemma 2, numbers Nj are coprime,
gcd(Ni + 1, Nj) = 1 for i > 2 and 1 6 j 6 i− 1.
Lemma 5. For i > 1, the equations
(ci)
Ni = ai−1 (1)
and
(ai)
Ni = (ai−1)
Ni+1. (2)
are true.
Proof. First show that (1) holds. Indeed, note that ci is a root of equation
x2 + x+ ai−1 = 0 over the field Li−1. One can verify directly, that ci + 1
is also a root of this equation. Then ci and ci + 1 are conjugates [11] over
Li−1 = F
22i
, that is (ci)
22
i
= ci+1. Therefore, (ci)
22
i
+1 = (ci+1)ci = ai−1,
and (1) is true. Applying (1) shows that (ai)
Ni = (ciai−1)
Ni = (ai−1)
Ni+1.
Hence, (2) is true as well.
If uj is a sequence of integers and s > t, then we will consider below
the empty product
∏t
j=s uj = 1.
Lemma 6. For k > 0 and i > k, the following equations are true:
(ci)
∏k
j=0
Ni−j = (ai−k−1)
∏k
j=1
(Ni−j+1) (3)
and
(ai)
∏k
j=0
Ni−j = (ai−k−1)
∏k
j=0
(Ni−j+1) (4)
Proof. We will proceed by induction on k. For k = 0 (and for i > 1), (3)
and (4) coincide with (1) and (2) respectively.
Now, suppose that (3) and (4) hold for k − 1, namely
(ci)
∏k−1
j=0
Ni−j = (ai−(k−1)−1)
∏k−1
j=1
(Ni−j+1) (5)
“adm-n1” — 2018/4/2 — 12:46 — page 140 — #142
140 Multiplicative orders of elements
and
(ai)
∏k−1
j=0
Ni−j = (ai−(k−1)−1)
∏k−1
j=0
(Ni−j+1). (6)
Then, applying (5) and (2), we obtain
(ci)
∏k
j=0
Ni−j =
(
(ci)
∏k−1
j=0
Ni−j
)Ni−k
=
(
(ai−k)
Ni−k
)
∏k−1
j=1
(Ni−j+1)
= (ai−k−1)
∏k
j=1
(Ni−j+1).
Hence, (3) is true for k. Analogously, exploiting (6) and (2) shows that
(ai)
∏k
j=0
Ni−k =
(
(ai)
∏k−1
j=0
Ni−k
)Ni−k
=
(
(ai−k)
Ni−k
)
∏k−1
j=0
(Ni−j+1)
= (ai−k−1)
∏k
j=0
(Ni−j+1),
and (4) is true for k as well. This completes the induction and the proof.
Lemma 7. Let K ⊂ L be a tower of fields. Let x ∈ L\K and m be the
smallest positive integer, satisfying the condition xm ∈ K. If xn ∈ K for
a positive integer n, then m|n.
Proof. One may write n = um+v, where 0 6 v < m. Then xn = (xm)u·xv,
and, therefore, xv ∈ K. As m is the smallest positive integer with the
condition xm ∈ K and v < m, we have v = 0, and the result follows.
Lemma 8. Let u > 1 and l be a positive integer. If (cu)
l ∈ Lu−1, then
(l, Nu) > 1.
Proof. (1) implies that (cu)
Nu = au−1 ∈ Lu−1. By Lemma 7, if d is the
smallest positive integer with (cu)
d ∈ Lu−1, then d|Nu and d|l. Clearly,
d > 1, and hence, (l, Nu) > d > 1.
Lemma 9. Let L1 ⊂ L2 be a tower of fields and b ∈ L∗
2. Let br = a ∈ L∗
1
and r be the smallest positive integer with br ∈ L∗
1. Then O(b) = r ·O(a).
Proof. Since bO(b) = 1 ∈ L∗
1, the inequality O(b) > r holds. Write O(b) =
sr + t, where s is a positive integer and 0 6 t < r. Then
1 = bO(b) = bsr+t = asbt.
Hence, bt = a−s ∈ L∗
1. By definition of r, it is possible only for t = 0.
Therefore, as = 1, s > O(a) and O(b) = sr > r · O(a). From the other
side, br·O(a) = aO(a) = 1, and thus O(b) = r ·O(a).
“adm-n1” — 2018/4/2 — 12:46 — page 141 — #143
R. Popovych 141
Theorem 1. The relation (ci)
∏k
j=0
Ni−j ∈ Li−k−1\Li−k−2 holds for i > 2
and 0 6 k 6 i− 1.
Proof. Applying (3), we see that
(ci)
∏k
j=0
Ni−j = (ci−k−1)
∏k
j=1
(Ni−j+1)(ai−k−2)
∏k
j=1
(Ni−j+1). (7)
Obviously, (ci−k−1)
∏k
j=1
(Ni−j+1) ∈ Li−k−1 and (ai−k−2)
∏k
j=1
(Ni−j+1) ∈
Li−k−2. Hence, the product on the right hand of (7) belongs to Li−k−1.
For 1 6 j 6 k, by Lemma 4, gcd(Ni−j + 1, Ni−k−1) = 1, and thus
gcd(
∏k
j=1(Ni−j + 1), Ni−k−1) = 1. Then, by Lemma 8, the relation
(ci−k−1)
∏k
j=1
(Ni−j+1) /∈ Li−k−2 is true. Therefore, the element
(ci−k−1)
∏k
j=1
(Ni−j+1)(ai−k−2)
∏k
j=1
(Ni−j+1)
does not belong to Li−k−2.
Theorem 2. The relation (ai)
∏k
j=0
Ni−j ∈ Li−k−1\Li−k−2 holds for i > 2
and 0 6 k 6 i− 1.
Proof. Using (4), we have
(ai)
∏k
j=0
Ni−j = (ci−k−1)
∏k
j=0
(Ni−j+1)(ai−k−2)
∏k
j=0
(Ni−j+1). (8)
Observe that (ci−k−1)
∏k
j=0
(Ni−j+1) ∈ Li−k−1 and (ai−k−2)
∏k
j=0
(Ni−j+1) ∈
Li−k−2. Thus, the product on the right hand of (8) belongs to Li−k−1.
For 0 6 j 6 k, by Lemma 4, gcd(Ni−j + 1, Ni−k−1) = 1, and therefore
gcd(
∏k
j=0(Ni−j +1), Ni−k−1) = 1. So, the relation (ci−k−1)
∏k
j=0
(Ni−j+1) /∈
Li−k−2 holds by Lemma 8. Hence, the element
(ci−k−1)
∏k
j=0
(Ni−j+1)(ai−k−2)
∏k
j=0
(Ni−j+1)
does not belong to Li−k−2.
2. Lower bound on multiplicative orders of elements
We give in this section in Corollary 2 a lower bound on multiplicative
orders of elements ci, ai and also formulate in Corollary 3 a condition
under that these elements are primitive.
Theorem 3. For i > 2, the following statements hold:
“adm-n1” — 2018/4/2 — 12:46 — page 142 — #144
142 Multiplicative orders of elements
(a) O(ci) =
∏i
j=1 αj, where αj |Nj, αj > 1;
(b) O(ai) =
∏i
j=1 βj, where βj |Nj, βj > 1.
Proof. (a) Define recursively the sequence αi, . . . , α1 of positive integers
as follows. αi is the smallest integer satisfying the relation (ci)
αi ∈ Li−1.
If αi,. . . ,αi−j , where 0 6 j 6 i− 2, are already known, then αi−j−1 is the
smallest positive integer such that the relation
{(ci)
∏i
k=i−j αk}αi−j−1 ∈ Li−j−2
holds.
Since the cardinality of the group L∗
i is
∏i
j=0Nj and the cardinality
of the group L∗
i−1 is
∏i−1
j=0Nj , we have that the number of elements of
the factor-group L∗
i /L
∗
i−1 equals Ni. If d is the coset of ci in the factor-
group, then αi = O(d) and, as a consequence of Lagrange’s theorem for
finite groups, αi|Ni. Clearly, αi > 1. By Theorem 2 (ci)
Ni ∈ Li−1\Li−2,
and thus (ci)
αi ∈ Li−1\Li−2. Indeed, if to suppose that (ci)
αi ∈ Li−2,
then [(ci)
αi ]Ni/αi = (ci)
Ni ∈ Li−2, a contradiction. Hence, by Lemma 9,
O(ci) = αiO((ci)
αi).
Analogously, one can show that αi−j−1|Ni−j−1 (αi−j−1 > 1) and
{(ci)
∏i
k=i−j αi−k}αi−j−1 ∈ Li−j−2\Li−j−3. By Lemma 9,
O((ci)
αi...αi−j ) = αi−j−1O((ci)
αi...αi−jαi−j−1).
From (3), we deduce that
(ci)
∏i−1
j=0
Ni−j = ((a0)
N1+1)
∏i−2
j=1
(Ni−j+1) = 1.
Thus, O(ci)|
∏i−1
j=0Ni−j and O(ci) = αi . . . α1.
(b) The proof is analogues to the previous one, using Theorem 2
instead of Theorem 1.
Corollary 1. For i > 2, O(cic0) = N0O(ci) and O(aia0) = N0O(ai).
Proof. Note that O(c0) = N0. Since, by Theorem 3, O(ci) divides
∏i
j=1Nj , and lemma 2 implies that gcd(
∏i
j=1Nj , N0) = 1, we have
gcd(O(ci), O(c0)) = 1. Therefore, O(cic0) = O(ci)O(c0), and the result
for cic0 follows. The proof for aia0 = aic0 is analogous.
Corollary 2. The multiplicative order of the elements ci and ai equals
∏i
j=1Nj for 2 6 i 6 4 and is at least
∏4
j=1Nj ·
∏i
j=5(2
j+2 + 1) for i > 5.
“adm-n1” — 2018/4/2 — 12:46 — page 143 — #145
R. Popovych 143
Proof. Consider the formulas for the multiplicative order of ci and ai given
in Theorem 3. For 1 6 j 6 4 the Fermat numbers N1 = 5, N2 = 17,
N3 = 257, N4 = 65537 are prime [6, table 1.3]. Therefore, αj = βj = Nj
for 1 6 j 6 4. By Lemma 3, αj , βj > 2j+2 + 1 for j > 5.
Theorem 4. Let i > 5. If, for 5 6 j 6 i, the αj = Nj is the smallest
positive integer satisfying the condition (cj)
αj ∈ Lj−1, then O(ai) =
O(ci) =
∏i
j=1Nj.
Proof. First prove the theorem for element ai. Note that αj is the smallest
positive integer with (cj)
αj ∈ Lj−1 iff αj is the smallest positive integer
with (aj)
αj ∈ Lj−1. We will proceed by induction on i > 5.
For i = 5, we have from (2) that (a5)
N5 = (a4)
N5+1. Thus, by Lemma 9,
O(a5) = N5O((a4)
N5+1). We have O(a4) =
∏4
j=1Nj by Corollary 2 and
gcd(N5 + 1,
∏4
j=1Nj) = 1 by Lemma 4. Use the well known fact that
raising an element of a group to a power relatively prime to its order
does not change the order. One deduces that O((a4)
N5+1) = O(a4) and
O(a5) =
∏5
j=1Nj .
Now, assume that the statement of the theorem is true for i−1. For i, we
have from (2) that (ai)
Ni = (ai−1)
Ni+1. Therefore, by Lemma 9, O(ai) =
NiO((ai−1)
Ni+1). As O(ai−1) =
∏i−1
j=1Nj by the induction assumption
and gcd(Ni + 1,
∏i−1
j=1Nj) = 1 by Lemma 4, one obtains, analogously to
the previous, that O((ai−1)
Ni+1) = O(ai−1) and O(ai) =
∏i
j=1Nj . This
completes the induction
To complete the proof, observe that, by equality (1) and Lemma 9,
O(ci) = NiO(ai−1) = O(ai).
Remark that, if the condition of Theorem 4 is true, then the following
chain of cyclic subgroups arises:
〈ci〉 = 〈ai〉 ⊃ 〈ci−1〉 = 〈ai−1〉 ⊃ · · · ⊃ 〈c2〉 = 〈a2〉 ⊃ 〈a1〉 .
At the same time, 〈a1〉 6= 〈c1〉, because O(c1) = 15, O(a1) = O(c1c0) = 5.
Theorem 4 and Corollary 1 imply the following corollary.
Corollary 3. Let i > 5. If, for 5 6 j 6 i, the αj = Nj is the smallest
positive integer with (cj)
αj ∈ Lj−1, then cic0 and aia0 are primitive.
Proof. Since O(cic0) = O(aia0) =
∏i
j=0Nj , the result follows.
Theorem 5. For 5 6 j 6 11, the number αj = Nj is the smallest positive
integer with (cj)
αj ∈ Lj−1.
“adm-n1” — 2018/4/2 — 12:46 — page 144 — #146
144 Multiplicative orders of elements
Proof. Note that to prove the fact: Nj is the smallest positive integer with
(cj)
αj ∈ Lj−1, it is enough to verify c
Nj/p
j /∈ Lj−1 for any prime divisor p
of Nj . Really, if element cj in the power Nj/p does not belong to Lj−1,
then element cj in the power of any divisor Nj/(pq) of Nj/p does not
belong to Lj−1 as well.
For 5 6 j 6 11, the Fermat numbers Nj are completely factored into
primes [6]. These factorizations are provided in Appendix. By equation
(1), (ci)
Ni = ai−1 ∈ Li−1. We have verified for 5 6 j 6 11, using the
factorizations and computer calculations, that αj = Nj is the smallest
positive integer with (cj)
αj ∈ Lj−1.
Corollary 4. For 2 6 i 6 11, the multiplicative order of elements ci and
ai equals
∏i
j=1Nj.
Proof. The result in the case 2 6 i 6 4 follows from Corollary 2. The
result in the case 5 6 i 6 11 follows from Theorem 4 and Theorem 5.
As a consequence of Corollary 1 and Corollary 4, one obtains the
following corollary.
Corollary 5. For 2 6 i 6 11, the elements cic0 and aia0 are primitive.
Let us consider, for example, the multiplicative group of the field L2.
The multiplicative order of element c2 is O(c2) = 5 ·17 = 85. Element c2c0
is primitive, namely O(c2c0) = 3 · 5 · 17 = 255. Since c2 + c1 + 1 = (c2)
5,
the order of element c2 + c1 + 1 is O(c2 + c1 + 1) = 17.
Appendix
N5 = 641 · 6700417,
N6 = 274177 · 67280421310721,
N7 = 59649589127497217 · 5704689200685129054721,
N8 = 1238926361552897 · P62,
where P62 is prime with 62 decimal digits
P62 = 93461639715357977769163558199606896584051237541638188580
280321,
N9 = 7455602825647884208337395736200454918783366342657
· 2424833 · P99,
“adm-n1” — 2018/4/2 — 12:46 — page 145 — #147
R. Popovych 145
where P99 is prime with 99 decimal digits
P99 = 74164006262753080152478714190193747405994078109751902390
5821316144415759504705008092818711693940737,
N10 = 45592577 · 6487031809
· 4659775785220018543264560743076778192897 · P252,
where P252 is prime with 252 decimal digits
P252 = 1304398744054881897274847687965099039466085308416118921
8689529577683241625147186357414022797757310489589878392
8842923844831149032913798729088601617946094119449010595
9067101305319061710183544916096191939124885381160807122
99672322806217820753127014424577,
N11 = 319489 · 974849 · 167988556341760475137
· 3560841906445833920513 · P564,
where P564 is prime with 564 decimal digits
P564 = 1734624471791475554302589708643097783774218447236640846
4934701906136357919287910885759103833040883717798381086
8451546421940712978306134189864280826014542758708589243
8736855639731189488693991585455066111474202161325570172
6056413939436694579322096866510895968548270538807264582
8554151936401912464931182546092879815733057795573358504
9822792800909428725675915189121186227517143192297881009
7925103603549691727991266352735878323664719315477709142
7745377038294584918917590325110939381322486044298573971
6507110592444621775425407069130470346646436034913824417
23306598834177.
References
[1] O. Ahmadi, I. E. Shparlinski, J. F. Voloch, Multiplicative order of Gauss periods,
Intern. J. Number Theory, N.4, 2010, pp.877-882.
[2] L. le Bruyn, 2010,
http://www.neverendingbooks.org/the-odd-knights-of-the-round-table
http://www.neverendingbooks.org/seating-the-first-few-thousand-knights
http://www.neverendingbooks.org/seating-the-first-few-billion-knights
[3] Q. Cheng, On the construction of finite field elements of large order, Finite Fields
Appl., N.3, 2005, pp.58-366.
“adm-n1” — 2018/4/2 — 12:46 — page 146 — #148
146 Multiplicative orders of elements
[4] J. H. Conway, On Numbers and Games, Academic Press, New York, 1976.
[5] J. H. Conway, N. J. A. Sloane, Lexicographic codes: error-correcting codes from
game theory, IEEE Trans. Inform. theory, N.3, 1986, pp.337-348.
[6] R. Crandall, C. Pomerance, Prime Numbers: A Computational Perspective,
Springer-Verlag, New York, 2005.
[7] S. Gao, Elements of provable high orders in finite fields, Proc. Amer. Math. Soc.,
N.6, 1999, pp.1615-1623.
[8] M.-D. Huang, A. K. Narayanan, Finding primitive elements in finite fields of small
characteristic, 2013, http://arxiv.org/abs/1304.1206.
[9] H. Ito, T. Kajiwara, H. Song, A Tower of Artin-Schreier extensions of finite fields
and its applications, JP J. Algebra, Number Theory Appl., N.2, 2011, pp.111-125.
[10] H.W.Lenstra, Nim multiplication, 1978,
https://openaccess.leidenuniv.nl/handle/1887/2125.
[11] R. Lidl, H. Niederreiter, Finite Fields, Cambridge University Press, 1997.
[12] R. Popovych, Elements of high order in finite fields of the form Fq[x]/Φr(x), Finite
Fields Appl., N.4, 2012, pp.700-710.
[13] R. Popovych, Elements of high order in finite fields of the form Fq[x]/(x
m − a),
Finite Fields Appl., N.1, 2013, pp.86-92.
[14] D. Wiedemann, An iterated quadratic extension of GF(2), Fibonacci Quart., N.4,
1988, pp.290-295.
Contact information
R. Popovych Lviv Polytechnic National University, Institute
of Computer Technologies, Bandery Str., 12,
Lviv, 79013, Ukraine
E-Mail(s): rombp07@gmail.com
Received by the editors: 26.02.2016
and in final form 12.03.2018.
|