On elements of high order in general finite fields
Збережено в:
| Дата: | 2014 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2014
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/153355 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | On elements of high order in general finite fields / R. Popovych // Algebra and Discrete Mathematics. — 2014. — Vol. 18, № 2. — С. 295–300. — Бібліогр.: 13 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-153355 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1533552019-06-15T01:27:00Z On elements of high order in general finite fields Popovych, R. 2014 Article On elements of high order in general finite fields / R. Popovych // Algebra and Discrete Mathematics. — 2014. — Vol. 18, № 2. — С. 295–300. — Бібліогр.: 13 назв. — англ. 1726-3255 2010 MSC:11T30. http://dspace.nbuv.gov.ua/handle/123456789/153355 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| format |
Article |
| author |
Popovych, R. |
| spellingShingle |
Popovych, R. On elements of high order in general finite fields Algebra and Discrete Mathematics |
| author_facet |
Popovych, R. |
| author_sort |
Popovych, R. |
| title |
On elements of high order in general finite fields |
| title_short |
On elements of high order in general finite fields |
| title_full |
On elements of high order in general finite fields |
| title_fullStr |
On elements of high order in general finite fields |
| title_full_unstemmed |
On elements of high order in general finite fields |
| title_sort |
on elements of high order in general finite fields |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2014 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/153355 |
| citation_txt |
On elements of high order in general finite fields / R. Popovych // Algebra and Discrete Mathematics. — 2014. — Vol. 18, № 2. — С. 295–300. — Бібліогр.: 13 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT popovychr onelementsofhighorderingeneralfinitefields |
| first_indexed |
2025-07-14T04:34:51Z |
| last_indexed |
2025-07-14T04:34:51Z |
| _version_ |
1837595562716692480 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 18 (2014). Number 2, pp. 295–300
© Journal “Algebra and Discrete Mathematics”
On elements of high order in general finite fields
Roman Popovych
Communicated by I. P. Shestakov
Abstract. We show that the Gao’s construction gives for
any finite field Fqn elements with the multiplicative order at least
(
n+t−1
t
)
∏t−1
i=0
1
di , where d =
⌈
2 logq n
⌉
, t = ⌊logd n⌋.
Introduction
It is well known that the multiplicative group of a finite field is cyclic.
A generator of the group is called a primitive element. The problem
of constructing efficiently a primitive element for a given finite field is
notoriously difficult in the computational theory of finite fields. 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.
Throughout this paper Fq is a field of q elements, where q is a power
of prime number p. We use F ∗
q to denote the multiplicative group of Fq.
Previous work. If no constraint is put on the extension degree n,
very few results are known. Gao gives in [5] an algorithm for constructing
high order elements for general extensions Fqn of finite field Fq with
lower bound on the order n
logq n
4 logq(2 logq n)
− 1
2 . His algorithm assumes some
2010 MSC: 11T30.
Key words and phrases: finite field, multiplicative order, Diophantine inequality.
296 On elements of high order in general finite fields
reasonable but unproved conjecture. Conflitti [4] provided a more careful
analysis of results from [5].
A polynomial algorithm that find a primitive element in finite field of
small characteristic is described in [8]. However, the algorithm relies on
two unproved assumptions, and the second assumption is not supported
by any computational example.
For special finite fields, it is possible to construct elements which
can be proved to have much higher orders. Extensions connected with a
notion of Gauss period are considered in [1, 6, 7, 10]. The lower bound on
the order equals to
exp(2.5
√
n−2)
13(n−2) . Extensions based on the Kummer and
Artin-Schreier polynomials are considered in [2, 11]. Some generalization
of the extensions is given in [3].
Field extension based on the Kummer polynomial is of the form
Fq[x]/(xn − a). It is shown in [2] how to construct high order element in
the extension Fq[x]/(xn −a) with the condition q ≡ 1 (mod n). The lower
bound 5, 8n is obtained in this case. High order elements are constructed
in [11] for Kummer extensions without the condition q ≡ 1 (mod n) with
lower bound 2⌊ 3√2n⌋.
Voloch [12, 13] proposed a method which constructs an element of
order at least exp((log n)2) in finite fields from elliptic curves.
Our results. Set Fq(θ) = Fqn = Fq[x]/f(x), where f(x) is an
irreducible polynomial over Fq of degree n and θ = x mod f(x) is the
coset of x.
We improve the Gao’s construction and its modification by Conflitti
for any finite field Fqn . The method similar to that in [4, 5] is used for
the proof. Our main result is the following theorem.
Theorem 1. Set d =
⌈
2 logq n
⌉
, t = ⌊logd n⌋. The θ has in the field
Fq(θ) = Fqn = Fq[x]/f(x) the multiplicative order at least
(
n + t − 1
t
)
t−1
∏
i=0
1
di
. (1)
1. Preliminaries
We recall that the multiplicative order ord(β) of the element β ∈ Fqn
is the smallest positive integer u such that βu = 1.
Let m be the smallest power of q greater or equal to n. The Gao
approach [5] depends on the following conjecture.
R. Popovych 297
Conjecture. For any integer n, there exist a polynomial g(x) ∈ Fq[x] of
degree d at most 2 logq n such that xm − g(x) has irreducible factor f(x)
of degree n.
If the conjecture holds, then clearly θm = g(θ). Gao considered the
set S =
{
∑t−1
i=0 uim
i|0 6 ui 6 µ
}
and chase t and µ from the condi-
tion µdt < n. He proved that θu are distinct elements for u ∈ S, took
t =
⌊
logq n
2 logq d
⌋
, µ =
√
n and showed |S| = (µ + 1)t > n
logq n
4 logq(2 logq n)
− 1
2 .
Conflitti [4] considered the following set
S =
{
t−1
∑
i=0
uim
i|0 6 ui 6 µi,
n
tdi
− 1 6 µi 6
n
tdi
}
and chase t and µ from the condition
∑t−1
i=0 µid
i < n. He proved that θu
are distinct elements for u ∈ S, took t = ⌊logd n⌋ and showed
|St| =
t−1
∏
i=0
(µi + 1) >
(
n
t
)t t−1
∏
i=0
1
di
. (2)
Substituting t = ⌊logd n⌋ into (2), we obtain
ord(θ) >
(
nd
log2
d n
)
1
2
logd n
.
The results from [4, 5] are based on the following statement (see
[5, Theorem 1.4]).
Lemma 1. Suppose that f(x) ∈ Fq[x] is not a monomial nor a binomial of
the form axpl
+b, where p is the characteristic of Fq. Then the polynomials
f (1)(x) = f(x), f (k)(x) = f (k−1)(x), k > 2
are multiplicatively independent in Fq[x], that is, if
(f (1)(x))k1(f (2)(x))k2 . . . (f (s)(x))ks = 1
for any integers s > 1, k1,. . . ,ks, then k1 = k2 = . . . = ks = 0.
The following lemma [9] gives lower bound for the number of non-
negative solutions of linear Diophantine inequality.
298 On elements of high order in general finite fields
Lemma 2. Let a0, . . . , ar−1 be positive integers with gcd(a0, . . . , ar−1)=1.
Then the number of non-negative integer solutions x0, . . . , xr−1 of the
linear Diophantine inequality
r−1
∑
i=0
aixi 6 m,
is at least
(
m + r
r
)
r−1
∏
i=0
1
ai
.
2. Main result
To improve the Conflitti result we consider the set of solutions
u0, . . . , ur−1 of the linear Diophantine inequality
r−1
∑
i=0
diui 6 m,
and show that θu are distinct elements in Fqn for all u ∈ S.
We give below the proof of our main result.
Proof of Theorem 1. If θ is a root of xm − g(x) , then since m is a power
of q, applying iteratively the Frobenius automorphism we have
θmi
= g(i)(θ), i ∈ N. (3)
where as in the statement of lemma 1, g(i)(x) is the polynomial obtained
by composing g(x) with itself i times.
Consider the set
S =
{
t−1
∑
i=0
uim
i|
t−1
∑
i=0
diui 6 n − 1, ui > 0
}
.
For every element u ∈ S we construct the power θu that belongs to the
group generated by θ. We show that if two elements u, v ∈ S are distinct,
then the correspondent powers do not coincide.
Assume that elements u =
∑t−1
i=0 uim
i and v =
∑t−1
i=0 vim
i from S are
distinct, and the correspondent powers are equal: θu = θv. Then we have
t−1
∏
i=0
(
θmi
)ui
=
t−1
∏
i=0
(
θmi
)vi
.
R. Popovych 299
Taking into account the equality (3), we get
t−1
∏
i=0
(
g(i)(θ)
)ui
=
t−1
∏
i=0
(
g(i)(θ)
)vi
.
Define the following polynomials h1(x) =
∏
ui>vi
(
g(i)(θ)
)ui−vi
and
h2(x) =
∏
vi>ui
(
g(i)(θ)
)vi−ui
. Then h1(θ) = h2(θ), and since g(x) is the
characteristic polynomial of θ , we write: h1(x) = h2(x) mod f(x). As
g(i)(x) has degree di, h1(x) is of degree at most
∑t−1
i=0 uid
i 6 n − 1 and
h2(x) is of degree at most
∑t−1
i=0 vid
i 6 n − 1. Thus h1(x) and h2(x) must
be equal as polynomials over Fq. Therefore
t−1
∏
i=0
(
g(i)(x)
)ui−vi
= 1.
According to lemma 1 the polynomials g(i)(x) are multiplicatively inde-
pendent in Fq[x]. So ui = vi for i = 0, . . . , t − 1, and thus u = v - a
contradiction.
Hence, the number of elements of S (and the multiplicative order of θ)
is at least the number of nonnegative integer solutions of the Diophantine
inequality
∑t−1
i=0 dixi 6 n − 1. Finally, applying lemma 2, we have
|S| >
(
n + t − 1
t
)
t−1
∏
i=0
1
di
,
and the result follows.
Now we compare our result with the Conflitti result. Let us calculate
for this purpose the ratio R of the bound (1) to the bound (2):
R =
t−1
∏
i=1
n + i
n
· t
i
.
It is clear that R > 1 for any q and n (recall that t depends on q and n).
We provide below a few numerical examples of lower bounds on the
multiplicative orders of the considered previously element θ. Denote lower
bounds on the orders of θ obtained in [4] and in this paper by b1 and b2
respectively. Values of q, n, d, t, b1, b2 and R in examples 1-3 are given
in the table.
300 On elements of high order in general finite fields
No. q n d t b1 b2 R
1 127 1000 3 6 1, 49 · 106 9, 82 · 107 65,77
2 257 10000 3 8 2, 6 · 1011 1, 08·1014 417,26
3 19991 100000 2 16 4, 07·1024 3, 59 · 106 882716,52
References
[1] O. Ahmadi, I. E. Shparlinski, J. F. Voloch, Multiplicative order of Gauss periods,
Int. J. Number Theory, Vol.6 (2010), No.4, pp.877-882.
[2] Q. Cheng, On the construction of finite field elements of large order, Finite Fields
Appl., Vol.11 (2005), No.3, pp.358-366.
[3] Q. Cheng, S. Gao, D. Wan, Constructing high order elements through subspace
polynomials, Discrete algorithms: Proc. 23rd ACM-SIAM Symp. (Kyoto, Japan,
17–19 January 2012). – Omnipress, Philadelphia, USA, 2011, pp.1457–1463.
[4] A. Conflitti, On elements of high order in finite fields, Cryptography and com-
putational number theory: Proc. Workshop (Singapore, 22-26 November 1999). –
Birkhauser, Basel, 2001, pp.11–14.
[5] S. Gao, Elements of provable high orders in finite fields, Proc. Amer. Math. Soc.,
Vol.127 (1999), No.6, pp.1615-1623.
[6] J. von zur Gathen, I.E. Shparlinski, Orders of Gauss periods in finite fields, Appl.
Algebra Engrg. Comm. Comput., Vol.9 (1998), No.1, pp.15-24.
[7] J. von zur Gathen, I.E. Shparlinski, Gauss periods in finite fields, Finite Fields
and their Applications: Proc. 5th Conf. (Ausburg, Germany, 2–6 August 1999). –
Springer, Berlin, 2001, pp.162-177.
[8] M.-D.Huang, A. K. Narayanan, Finding primitive elements in finite fields of small
characteristic, arXiv 1304.1206, 2013.
[9] T. A. Lambe, Bounds on the Number of Feasible Solutions to a Knapsack Problem,
SIAM J. Applied Math., Vol.26 (1974), No.2, pp.302-305.
[10] R. Popovych, Elements of high order in finite fields of the form Fq[x]/Φr(x), Finite
Fields Appl., Vol.18 (2012), No.4, pp.700-710.
[11] R. Popovych, Elements of high order in finite fields of the form Fq[x]/(xm
− a),
Finite Fields Appl., Vol.19 (2013), No.1, pp.86-92.
[12] J.F. Voloch, On the order of points on curves over finite fields, Integers, Vol.7
(2007), A49.
[13] J.F. Voloch, Elements of high order on finite fields from elliptic curves, Bull.
Austral. Math. Soc., Vol.81 (2010), No.3, pp.425-429.
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: 13.02.2013
and in final form 08.12.2014.
|