Normal high order elements in finite field extensions based on the cyclotomic polynomials
We consider elements which are both of high multiplicative order and normal in extensions Fqm of the field Fq. If the extension is defined by a cyclotomic polynomial, we construct such elements explicitly and give explicit lower bounds on their orders.
Gespeichert in:
| Datum: | 2020 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2020
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/188518 |
| 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: | Normal high order elements in finite field extensions based on the cyclotomic polynomials / R. Popovych, R. Skuratovskii // Algebra and Discrete Mathematics. — 2020. — Vol. 29, № 2. — С. 241–248. — Бібліогр.: 9 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-188518 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1885182025-02-09T16:03:01Z Normal high order elements in finite field extensions based on the cyclotomic polynomials Popovych, R. Skuratovskii, R. We consider elements which are both of high multiplicative order and normal in extensions Fqm of the field Fq. If the extension is defined by a cyclotomic polynomial, we construct such elements explicitly and give explicit lower bounds on their orders. The authors are grateful to the referee for comments and suggestions which improved the quality of this paper. 2020 Article Normal high order elements in finite field extensions based on the cyclotomic polynomials / R. Popovych, R. Skuratovskii // Algebra and Discrete Mathematics. — 2020. — Vol. 29, № 2. — С. 241–248. — Бібліогр.: 9 назв. — англ. 1726-3255 DOI:10.12958/adm1117 2010 MSC: 11T30. https://nasplib.isofts.kiev.ua/handle/123456789/188518 en Algebra and Discrete Mathematics application/pdf Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
We consider elements which are both of high multiplicative order and normal in extensions Fqm of the field Fq. If the extension is defined by a cyclotomic polynomial, we construct such elements explicitly and give explicit lower bounds on their orders. |
| format |
Article |
| author |
Popovych, R. Skuratovskii, R. |
| spellingShingle |
Popovych, R. Skuratovskii, R. Normal high order elements in finite field extensions based on the cyclotomic polynomials Algebra and Discrete Mathematics |
| author_facet |
Popovych, R. Skuratovskii, R. |
| author_sort |
Popovych, R. |
| title |
Normal high order elements in finite field extensions based on the cyclotomic polynomials |
| title_short |
Normal high order elements in finite field extensions based on the cyclotomic polynomials |
| title_full |
Normal high order elements in finite field extensions based on the cyclotomic polynomials |
| title_fullStr |
Normal high order elements in finite field extensions based on the cyclotomic polynomials |
| title_full_unstemmed |
Normal high order elements in finite field extensions based on the cyclotomic polynomials |
| title_sort |
normal high order elements in finite field extensions based on the cyclotomic polynomials |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2020 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/188518 |
| citation_txt |
Normal high order elements in finite field extensions based on the cyclotomic polynomials / R. Popovych, R. Skuratovskii // Algebra and Discrete Mathematics. — 2020. — Vol. 29, № 2. — С. 241–248. — Бібліогр.: 9 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT popovychr normalhighorderelementsinfinitefieldextensionsbasedonthecyclotomicpolynomials AT skuratovskiir normalhighorderelementsinfinitefieldextensionsbasedonthecyclotomicpolynomials |
| first_indexed |
2025-11-27T19:08:27Z |
| last_indexed |
2025-11-27T19:08:27Z |
| _version_ |
1849971718752305152 |
| fulltext |
“adm-n2” — 2020/7/8 — 8:15 — page 241 — #101
© Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 29 (2020). Number 2, pp. 241–248
DOI:10.12958/adm1117
Normal high order elements in finite field
extensions based on the cyclotomic polynomials
R. Popovych and R. Skuratovskii
Communicated by A. P. Petravchuk
Abstract. We consider elements which are both of high
multiplicative order and normal in extensions Fqm of the field Fq. If
the extension is defined by a cyclotomic polynomial, we construct
such elements explicitly and give explicit lower bounds on their
orders.
Introduction
Throughout this paper Fq is a field of q elements, where q is a power
of prime number p.
High multiplicative order element is a very important notion in the
theory of finite fields. A review of the obtained in this area results is
provided in [6, section 4.4]. The problem of construction of such element is
considered both for general and for special finite fields (extensions based on
cyclotomic, Kummer or Artin-Schreier polynomials, recursive extensions)
[1, 2, 7, 8]. For special finite fields, it is possible to construct elements
which can be proved to have much higher orders.
Normal basis is also an important notion in the theory of finite fields,
see [1, 5, 6, 9] for the definition, basic properties and references. One of the
most interesting constructions of normal bases come from Gauss periods,
see [2] and references therein. In particular, Gauss periods of type (n,2)
are of special interest [2].
2010 MSC: 11T30.
Key words and phrases: finite field, cyclotomic polynomial, normal basis, high
multiplicative order element.
https://doi.org/10.12958/adm1117
“adm-n2” — 2020/7/8 — 8:15 — page 242 — #102
242 Normal high order elements
It would be very useful to bring two mentioned notions together and
consider elements which are both of high order and normal. The first step
in this direction was made in [1, 2]. A lower bound on the order of Gauss
periods of type (n,2) was given by Gathen and Shparlinski [2], and later
improved by Ahmadi, Shparlinski and Voloch [1]. Popovych [7, 8] obtained
better lower bound on the order and for elements in a more general form.
Then the question aroused: what high order elements considered in [7,8]
remain normal.
It should be also noticed that, as a generalization of normal elements,
Huczynska, Mullen, Panario and Thomson [3] introduce and character-
ize k-normal elements, proposing many problems based on theoretical
considerations and computational tests. Particularly, they posed the fol-
lowing problem [3, problem 6.4]: to determine the existence of high-order
k-normal elements.
The current paper enriches the list of normal high order elements in
finite field extensions based on cyclotomic polynomials. More precisely,
we show that a series of high order elements from [7, 8], which have more
general form than Gauss periods of type (n,2), are at the same time normal.
One can also treat that the paper concerns with the mentioned above
problem in the case k = 0 and finite field extensions based on cyclotomic
polynomials. Our main result is Theorem 4.
1. Preliminaries
It is well known that the multiplicative group of a finite field is cyclic.
A generator of the group is called primitive element. The problem of
constructing efficiently a primitive element for a given finite field is notori-
ously difficult. That is why one considers less restrictive question: to find
an element with high multiplicative order. We are not required to compute
the exact order of the element. It is sufficient in this case to obtain a lower
bound on the order. High order elements are needed in several applications.
Such applications include but are not limited to cryptography, coding
theory, pseudo random number generation and combinatorics. The use of
high multiplicative order elements in cryptography is based on the discrete
logarithm problem in a finite cyclic group [5, 6].
The multiplicative order ord(α) of element α ∈ F ∗
qm is the smallest
positive integer u such that αu = 1. “High order” means ord(α) = N with
N a large positive divisor of qm − 1.
For any integer m, we can consider Fqm as an m-dimensional vector
space over Fq. Then any basis of Fqm over Fq can be used to represent
“adm-n2” — 2020/7/8 — 8:15 — page 243 — #103
R. Popovych, R. Skuratovski i 243
the elements in Fqm . A normal basis of Fqm over Fq is a basis of the form
{α, αq, . . . , αqm−1} for some α ∈ Fqm . In this case the element α ∈ Fqm is
called normal over Fq [5, 6].
It is known [6, Theorem 2.39] that α ∈ Fqm is normal over Fq if and
only if the polynomials gα(x) =
∑m−1
i=0 αqixm−1−i and xm− 1 are coprime
over Fqm . Motivated by this fact, in [3], the authors introduce k-normal
elements: for 0 6 k 6 m− 1, an element α ∈ Fqm is said to be k-normal
over Fq if the greatest common divisor of gα(x) and xm − 1 over Fqm
has degree k. In this context, k-normal elements for k = 0 correspond to
normal elements in the usual sense.
Let {α0, α1, . . . , αm−1} be a normal basis of Fqm over Fq with αi = αqi
and A ∈ Fqm have the form
A = (a0, a1, . . . , am−1) =
m−1
∑
i=0
aiαi.
Then, since αq
i = αi+1 for i = 0, . . . ,m− 2 and αq
m−1 = α, we have
Aq =
m−1
∑
i=0
aiα
q
i =
m−1
∑
i=0
aiαi+1 = (an−1, a0, . . . , an−2).
That is, q-th power is the cyclic shift of coordinates. It means taking
q-th powers has negligible cost.
Hence, useful properties of finite field elements from the point of view
of the operation of raising to a power are as follows: high multiplicative
order (provides resistance against breaking by unauthorized person) and
normality (ensures less amount of calculations). This operation is particu-
larly needed for the Diffie Hellman and El Gamal cryptographic protocols
that are based on the discrete logarithm problem.
2. Field extensions based on cyclotomic polynomials
Extensions based on cyclotomic polynomials and connected with a
notion of Gauss period are considered in [1, 2, 7, 8]. More precisely, the
following extensions are constructed. Let r = 2n+ 1 be a prime number
coprime with q. Let q be a primitive root modulo r, that is the multiplica-
tive order of q modulo r equals to r− 1. Set Fq(θ) = Fqr−1 = Fq[x]/Φr(x),
where Φr(x) = xr−1+xr−2+ · · ·+x+1 is the r-th cyclotomic polynomial
and θ = x (mod Φr(x)) is the coset of element x modulo Φr(x). The
polynomial is irreducible over the field Fq. It is clear that the equality
“adm-n2” — 2020/7/8 — 8:15 — page 244 — #104
244 Normal high order elements
θr = 1 holds. We have the following tower of fields Fq ⊂ Fqn ⊂ Fq2n . The
element β = θ + θ−1 is called a Gauss period of type (n,2) [1]. It belongs
to Fqn and is normal over Fq [2].
A lower bound on the order of Gauss periods was given by Gathen and
Shparlinski [2], and later improved by Ahmadi, Shparlinski and Voloch [1].
Popovych [7, 8] derived better than in [2] lower bound, and the bound is
on the order of elements in a more general form. We show in this section
that a series of elements from [7, 8] are normal.
Denote by L(c, d) the number of solutions (u1, . . ., uc) of the linear
Diophantine inequality
∑c
j=1 juj 6 c with the condition 0 6 u1, . . . , uc 6
d. The Lemma below gives a lower bound on this number.
Lemma 1. [8, Lemma 4] The number L(c, d) is at least (δ + 1)
√
2c/δ−2,
where δ = d if d = 1, 2 and δ = 4 if d > 4.
All lower bounds on elements order in Theorem 1 below involve a
number of solutions of the linear Diophantine inequality.
Theorem 1. [8, Theorem 1] Let e be any integer, f any integer coprime
with r and a any non-zero element in the finite field Fq. Then
(a) θe(θf + a) has the multiplicative order at least L(r − 2, p− 1);
(b) (θ−f + a)(θf + a) for a2 6= −1 has the multiplicative order at least
L((r − 3)/2, p− 1) and this order divides q(r−1)/2 − 1;
(c) θe(θf + a) for a2 6= ±1 has the multiplicative order at least (L((r −
3)/2, p− 1))2/2.
Using Lemma 1 and Theorem 1, we obtain the following Theorem 2.
It is a modification of theorem 2 from [8] and gives a lower bound on the
order of elements in a more general form than Gauss periods.
Theorem 2. Let e be any integer, f any integer coprime with rand a ∈ F ∗
q .
Then
(a) θe(θf + a) has the multiplicative order at least
2
√
2(r−2)−2 if p = 2,
3
√
r−2−2 if p = 3,
5
√
(r−2)/2−2 if p > 5;
(b) θe(θf + a) for a2 6= ±1 has the multiplicative order at least
22
√
r−3−5 if p = 2,
3
√
2(r−3)−4/2 if p = 3,
5
√
r−3−4/2 if p > 5;
“adm-n2” — 2020/7/8 — 8:15 — page 245 — #105
R. Popovych, R. Skuratovski i 245
(c) (θ−f + a)(θf + a) for a2 6= −1 has the multiplicative order at least
2
√
r−3−2 if p = 2,
3
√
(r−3)/2−2 if p = 3,
5
√
r−3/2−2 if p > 5.
Proof. (a) By Theorem 1 (a) and Lemma 1.
(b) By Theorem 1 (c) and Lemma 1.
(c) By Theorem 1 (b) the element (θ−f + a)(θf + a) for a2 6= −1 has
the multiplicative order at least L((r− 3)/2, p− 1). Now the result follows
from Lemma 1.
If we take in Theorem 2 e = −1, f = 2, a = 1, then we obtain the
Gauss period of the type (n,2). Note that, since θr = 1 holds, one can
take e between 0 and r − 1, and f between 1 and r − 1. Then f will be
automatically coprime with r.
Element θ ∈ Fq2n , which generates the extension, is normal over Fq.
We show in Theorem 3 that elements in a more general form θ+ b ∈ Fq2n ,
where b ∈ Fq and b satisfies a certain condition, are also normal over Fq.
Theorem 3. Let b be element of the field Fq such that 2nb 6= 1. Then
element θ + b ∈ Fq2n is normal over Fq.
Proof. Since q is primitive modulo 2n + 1, then the set θq
k
+ b (k =
0, . . . , 2n− 1) coincides with θi + b (i = 1, . . . , 2n).
Show that the set θi + b (i = 1, . . . , 2n) is a basis, i. e. its elements are
linear independent over Fq. Really, if these elements are linear dependent,
there exists the set of coefficients ci ∈ Fq (i = 1, . . . , 2n) with at least one
non-zero coefficient (say cj 6= 0, 1 6 j 6 2n) and
∑2n
i=1 ci(θ
i+ b) = 0. As θ
is a root of the polynomial Φ2n+1(x), we have θ2n = −
∑2n−1
i=0 θi. Therefore,
we obtain the relation
∑2n−1
i=1 (ci− c2n)θ
i+(b
∑2n
i=1 ci− c2n) = 0. Hence, θ
is a root of the polynomial of degree 2n−1. At the same time, θ is a root of
the irreducible polynomial Φ2n+1(x) of degree 2n. Therefore, all coefficients
of the polynomial must be equal to zero. So, elements ci (i = 1, . . . , 2n)
are equal and b
∑2n
i=1 ci − c2n = 0. This implies (2nb − 1)cj = 0. Since
cj 6= 0, we have 2nb− 1 = 0, so this is a contradiction.
Remark that the inequality 2nb 6= 1 in the statement of Theorem 3
is modulo p. If n = 0, then, clearly, the condition 2nb 6= 1 holds for any
b ∈ Fq. If n 6= 0, then this condition is true for all elements b of the field
Fq, but b = (2n)−1.
“adm-n2” — 2020/7/8 — 8:15 — page 246 — #106
246 Normal high order elements
Corollary 1. Let b be element of the field Fq such that 2nb 6= 1. Then
element θ + θ−1 + 2b ∈ Fqn is normal over Fq.
Proof. Consider the trace of θ + b over Fqn . Taking into account, that
the trace of a sum equals a sum of traces and Trqmn/qn(b) = mb for
b ∈ Fq ⊂ Fqn [5, Theorem 2.23 (i), (iv)], we obtain:
Trq2n/qn(θ + b) = Trq2n/qn(θ) + Trq2n/qn(b) = (θ + θ−1) + 2b.
Hence, the element (θ + θ−1) + 2b is normal over Fq as the trace
Trq2n/qn(θ + b) of the element θ + b, which is normal over Fq [6, Proposi-
tion 5.2.3, 1].
Corollary 1 is a generalization of the known fact, that the Gauss period
θ + θ−1is normal over Fq.
Recall that for b = 0 we have 2nb 6= 1, and by Theorem 3 element
θ ∈ Fq2n is normal over Fq. However, the order of this element equals r
and is small comparatively with the order of the group F ∗
q2n . By Theorem
3, for b 6= 0 and 2nb 6= 1, the element θ + b ∈ Fq2n is normal over Fq. It
has high order according to the following Theorem 4.
Theorem 4. Let b 6= 0 be element of the field Fq such that 2nb 6= 1. Then,
for f = 1, . . . , r − 1,
(a) θf + b ∈ Fq2n is normal over Fq and has the multiplicative order at
least
2
√
2(r−2)−2 if p = 2,
3
√
r−2−2 if p = 3,
5
√
(r−2)/2−2 if p > 5;
(b) θf+b ∈ Fq2n for b2 6= ±1 is normal over Fq and has the multiplicative
order at least
22
√
r−3−5 if p = 2,
3
√
2(r−3)−4/2 if p = 3,
5
√
r−3−4/2 if p > 5;
(c) θf + θ−f +2b ∈ Fqn for a ∈ F ∗
q and 2b = (a2+1)a−1 is normal over
Fq and has the multiplicative order at least
2
√
r−3−2 ord(a)
(q−1)2
if p = 2,
3
√
(r−3)/2−2 ord(a)
(q−1)2
if p = 3,
5
√
r−3/2−2 ord(a)
(q−1)2
if p > 5.
“adm-n2” — 2020/7/8 — 8:15 — page 247 — #107
R. Popovych, R. Skuratovski i 247
Proof. (a) Since elements θf + b (f = 1, . . . , r− 1) are conjugates over Fq,
it is enough to prove (a) only for the case f = 1. The result follows by
Theorem 3 and Theorem 2 (a).
(b) Analogously to (a), it is enough to prove (b) only for f = 1. The
result follows by Theorem 3 and Theorem 2 (b).
(c) Since elements θf + θ−f +2b (f = 1, . . . , r− 1) are conjugates over
Fq, it is enough to prove (c) only for f = 1. We can write
(θ + a)(θ−1 + a) = a(θ + θ−1) + (a2 + 1) = a[θ + θ−1 + (a2 + 1)a−1].
Set 2b = (a2 + 1)a−1. The condition a2 6= −1 is equivalent to b 6= 0.
If 2nb 6= 1, then the element θ + θ−1 + (a2 + 1)a−1 is normal over Fq by
Corollary 1. Then a[θ + θ−1 + (a2 + 1)a−1] is also normal over Fq by the
following clear fact: if γ is normal over Fq and a ∈ Fq (a 6= 0), then aγ is
normal over Fq (because aq = a).
According to [4], if α and β are elements of a finite abelian group, then
ord(αβ) >
ord(α) ord(β)
[gcd(ord(α), ord(β))]2
. (1)
Set α = a[θ + θ−1 + (a2 + 1)a−1], β = a−1. Taking into account that
by Theorem 2(c) the element α for a2 6= −1 has the multiplicative order
ord(α) = U >
2
√
r−3−2 if p = 2,
3
√
(r−3)/2−2 if p = 3,
5
√
r−3/2−2 if p > 5,
ord(β) 6 q−1 and the inequality (1), we obtain ord(θ+θ−1+(a2+1)a−1) >
U ·ord(a)
(q−1)2
and the result follows.
Note that if the number q is not too large, then ord(a) can be obtained
by direct computer calculations in the field Fq.
Acknowledgements
The authors are grateful to the referee for comments and suggestions
which improved the quality of this paper.
References
[1] Ahmadi O., Shparlinski I. E., Voloch J. F. Multiplicative order of Gauss periods,
Int. J. Number Theory, 2010, 6(4), P. 877-882.
“adm-n2” — 2020/7/8 — 8:15 — page 248 — #108
248 Normal high order elements
[2] Gathen J., Shparlinski I. E. Orders of Gauss periods in finite fields, Appl. Algebra
Engrg. Comm. Comput., 1998, 9 (1), P. 15-24.
[3] Huczynska S., Mullen G.L., Panario D., Thomson D. Existence and properties of
k-normal elements over finite fields, Finite Fields Appl., 2013, 24, P. 170-183.
[4] Jungnickel D. On the order of a product in a finite abelian group, Math. Magazine,
1996, 69 (1), P. 53-57.
[5] Lidl R., Niederreiter H. Finite Fields. – Cambridge: Cambridge University Press,
1997, 755 p.
[6] Mullen G.L., Panario D. Handbook of finite fields. – Boca Raton: CRC Press, 2013,
1068 p.
[7] Popovych R. Elements of high order in finite fields of the form, Finite Fields Appl.,
2012, 18 (4), P. 700-710.
[8] Popovych R. Sharpening of explicit lower bounds on elements order for finite field
extensions based on cyclotomic polynomials, Ukr. Math. J., 2014, 66 (6), P. 815-825.
[9] Skuratovskii R. V. Constructing of finite field normal basis in deterministic polyno-
mial time, Bulletin of Taras Shevchenko National University of Kyiv. Series: Physics
and Mathematics, 2011 (1), P. 49-54 (in Ukrainian).
Contact information
Roman Popovych Lviv Polytechnic National University, Institute
of Computer Technologies, Bandery Str., 12,
Lviv, 79013, Ukraine
E-Mail(s): rombp07@gmail.com
Ruslan Skuratovskii Igor Sikorsky Kiev Polytechnic Institute,
av. Pobedy, 03056, Kiev, Ukraine
E-Mail(s): ruslcomp@mail.ru,
r.skuratovskii@kpi.ua
Received by the editors: 02.04.2018
and in final form 10.02.2019.
R. Popovych, R. Skuratovskii
|