Sharpening of the explicit lower bounds for the order of elements in finite field extensions based on cyclotomic polynomials
We explicitly construct elements of high multiplicative order in any extensions of finite fields based on cyclotomic polynomials. Явно побудовано елементи великого мультиплікативного порядку у будь-яких розширеннях скінченних полів на основі циклотомічних поліномів....
Saved in:
| Published in: | Український математичний журнал |
|---|---|
| Date: | 2014 |
| Main Author: | |
| Format: | Article |
| Language: | English |
| Published: |
Інститут математики НАН України
2014
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/166078 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Sharpening of the explicit lower bounds for the order of elements in finite field extensions based on cyclotomic polynomials / R. Popovych // Український математичний журнал. — 2014. — Т. 66, № 6. — С. 815–825. — Бібліогр.: 12 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-166078 |
|---|---|
| record_format |
dspace |
| spelling |
Popovych, R. 2020-02-18T05:14:04Z 2020-02-18T05:14:04Z 2014 Sharpening of the explicit lower bounds for the order of elements in finite field extensions based on cyclotomic polynomials / R. Popovych // Український математичний журнал. — 2014. — Т. 66, № 6. — С. 815–825. — Бібліогр.: 12 назв. — англ. 1027-3190 https://nasplib.isofts.kiev.ua/handle/123456789/166078 512.624 We explicitly construct elements of high multiplicative order in any extensions of finite fields based on cyclotomic polynomials. Явно побудовано елементи великого мультиплікативного порядку у будь-яких розширеннях скінченних полів на основі циклотомічних поліномів. en Інститут математики НАН України Український математичний журнал Статті Sharpening of the explicit lower bounds for the order of elements in finite field extensions based on cyclotomic polynomials Підсилення явних нижніх границь для порядків елементів у розширеннях скінченних полів на основі циклотомічних поліномів Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Sharpening of the explicit lower bounds for the order of elements in finite field extensions based on cyclotomic polynomials |
| spellingShingle |
Sharpening of the explicit lower bounds for the order of elements in finite field extensions based on cyclotomic polynomials Popovych, R. Статті |
| title_short |
Sharpening of the explicit lower bounds for the order of elements in finite field extensions based on cyclotomic polynomials |
| title_full |
Sharpening of the explicit lower bounds for the order of elements in finite field extensions based on cyclotomic polynomials |
| title_fullStr |
Sharpening of the explicit lower bounds for the order of elements in finite field extensions based on cyclotomic polynomials |
| title_full_unstemmed |
Sharpening of the explicit lower bounds for the order of elements in finite field extensions based on cyclotomic polynomials |
| title_sort |
sharpening of the explicit lower bounds for the order of elements in finite field extensions based on cyclotomic polynomials |
| author |
Popovych, R. |
| author_facet |
Popovych, R. |
| topic |
Статті |
| topic_facet |
Статті |
| publishDate |
2014 |
| language |
English |
| container_title |
Український математичний журнал |
| publisher |
Інститут математики НАН України |
| format |
Article |
| title_alt |
Підсилення явних нижніх границь для порядків елементів у розширеннях скінченних полів на основі циклотомічних поліномів |
| description |
We explicitly construct elements of high multiplicative order in any extensions of finite fields based on cyclotomic polynomials.
Явно побудовано елементи великого мультиплікативного порядку у будь-яких розширеннях скінченних полів на основі циклотомічних поліномів.
|
| issn |
1027-3190 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/166078 |
| citation_txt |
Sharpening of the explicit lower bounds for the order of elements in finite field extensions based on cyclotomic polynomials / R. Popovych // Український математичний журнал. — 2014. — Т. 66, № 6. — С. 815–825. — Бібліогр.: 12 назв. — англ. |
| work_keys_str_mv |
AT popovychr sharpeningoftheexplicitlowerboundsfortheorderofelementsinfinitefieldextensionsbasedoncyclotomicpolynomials AT popovychr pídsilennââvnihnižníhgranicʹdlâporâdkívelementívurozširennâhskínčennihpolívnaosnovíciklotomíčnihpolínomív |
| first_indexed |
2025-11-25T04:47:18Z |
| last_indexed |
2025-11-25T04:47:18Z |
| _version_ |
1850507022994243584 |
| fulltext |
© R. POPOVYCH, 2014
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 6 815
UDC 512.624
R. Popovych (Nat. Univ. „Lviv Polytechnic”)
SHARPENING OF THE EXPLICIT LOWER BOUNDS
ON THE ORDER OF ELEMENTS IN FINITE FIELD EXTENSIONS BASED
ON CYCLOTOMIC POLYNOMIALS
ПІДСИЛЕННЯ ЯВНИХ НИЖНІХ ГРАНИЦЬ ДЛЯ ПОРЯДКІВ
ЕЛЕМЕНТІВ У РОЗШИРЕННЯХ СКІНЧЕННИХ ПОЛІВ
НА ОСНОВІ ЦИКЛОТОМІЧНИХ ПОЛІНОМІВ
We explicitly construct elements with high multiplicative order in any extensions of finite fields based on cyclotomic
polynomials.
Явно побудовано елементи великого мультиплікативного порядку у будь-яких розширеннях скінченних полів на
основі циклотомічних поліномів.
1. Introduction. It is well known that the multiplicative group of a finite field is cyclic [1, 2]. The
problem of constructing efficiently a generator of the group for a given finite field is notoriously
difficult in the computational theory of finite fields. That is why one considers less restrictive ques-
tion: to find an element with high multiplicative order [2]. 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: cryptography, coding theory, pseudo random number
generation, combinatorics.
Throughout this paper Fq is a field of q elements, where q is a power of prime number p .
Fq* is the multiplicative group of Fq . S denotes the number of elements of finite set S . A par-
tition of an integer c is a sequence of such nonnegative integers u1,…, uc that ju j = cj=1
c! .
),( dcU denotes the number of partitions of c , for which u1,…, uc ! d . !"# denotes the group
generated by ! , and G ! H — the direct product of groups G and H . For a prime k , !k (l)
is the highest power of k dividing integer l .
Gao [3] gives an algorithm for constructing high order elements for many (conjecturally all)
general extensions Fqm of finite field Fq . Voloch [4, 5] proposed another method for general ex-
tensions. For special finite fields, it is possible to construct elements which can be proved to have
much higher orders. Extensions based on the Kummer or Artin – Schreier polynomials are consid-
ered in [6 – 8]. A generalization of the extensions is given in [9].
Extensions connected with a notion of Gauss period are considered in [10 – 12]. More precisely,
the following extensions are constructed. Let r = 2s +1 be a prime number coprime with q . Let
q be a primitive root modulo r , that is the multiplicative 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 cy-
clotomic polynomial and ! = x(mod"r (x)) . It is clear that the equality !r= 1 holds. The ele-
816 R. POPOVYCH
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 6
ment ! = " + "#1 is called a Gauss period of type ((r !1)/2, 2) . It generates normal base over
Fq [11].
It is shown in [10] that ! has high multiplicative order: at least 2 r!1!2 . Bounds of such
kind: explicit and for any p and r , are of special interest in applications (particularly, cryptog-
raphy). The bounds allow to compare simply different field extensions.
The bounds using partitions U((r ! 3)/2, p !1) [11], U(r ! 2, p !1) [12] or asymptotic bound
exp 2, 5
2
1! 1
p
+ o(1)
"
#$
%
&'
r !1
"
#$
%
&'
[11] do not allow to obtain a bound on the element order for
fixed finite field. Explicit bounds in terms of p and r are derived in [12] from bounds in terms
of partitions. However, such bounds are obtained only for r ! p2 + 2 and r < p + 2 . Important
in applications case p + 2 ! r < p2 + 2 remains not described.
That is why we give in this paper better comparatively with [10] explicit lower bounds for any
p and r both on the order of element ! and similar form elements. To obtain the bounds we
count solutions of a linear Diophantine inequality instead of counting partitions. Our main result is
Theorem 2.
2. Preliminaries. Let c, d be positive integers ( d ! c ). Denote by L(c, d) the set of solu-
tions (u1,…, uc ) of the following linear Diophantine inequality:
ju j ! c
j=1
c
" , (1)
with the condition 0 ! u1,…, uc ! d .
For the extension Fq (!) we prove the following three lemmas.
Lemma 1. Let a be any non-zero element in the finite field Fq . If solutions (u1,…, ur!2 )
and (v1,…, vr!2 ) from L(r ! 2, p !1) are distinct, then the products (! j + a)u jj=1
r"2# and
(! j + a)v jj=1
r"2# are not equal.
Proof. We prove Lemma 1 by the way of contradiction. Assume that solutions (u1,…, ur!2 )
and (v1,…, vr!2 ) from the set L(r ! 2, p !1) are distinct, and the products are equal:
(! j + a)u j
j=1
r"2
# = (! j + a)v j
j=1
r"2
# .
Since the polynomial !r (x) is minimal polynomial for the element ! , we write
(x j + a)u j
j=1
r!2
" = (x j + a)v j (mod#r (x))
j=1
r!2
" .
SHARPENING OF THE EXPLICIT LOWER BOUNDS ON THE ORDER … 817
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 6
As there are polynomials of degree r ! 2 < deg"r (x) on the left- and on the right-hand side of the
equality, these polynomials are equal as polynomials over Fq , i.e.,
(x j + a)u j
j=1
r!2
" = (x j + a)v j
j=1
r!2
" . (2)
Let k be the smallest integer for which uk ! vk and, say uk > vk . After removing common
factors on both sides of (2), we obtain
(xk + a)uk!vk (x j + a)u j
j=k+1
r!2
" = (x j + a)v j
j=k+1
r!2
" . (3)
Denote the absolute term of the polynomial (x j + a)u jj=k+1
r!2" by b . It is clear that b ! 0 .
Then there is the term
(uk ! vk )auk!vk!1bxk
on the left-hand side of (3) with minimal nonzero power of x . Since 0 ! uk , vk ! p "1 , uk ! vk ,
a, b ! 0 , the term is nonzero. And such term does not occur on the right-hand side, which makes
the identity (3) impossible.
Lemma 1 is proved.
Lemma 2. Let a be such nonzero element in the finite field Fq that a2 ! "1 . If solutions
(u1,…, u(r!3)/2 ) and (v1,…, v(r!3)/2 ) from L((r ! 3)/2, p !1) are distinct, then the products
[(a! j +1)(! j + a)]u jj=1
(r"3)/2# and [(a! j +1)(! j + a)]v jj=1
(r"3)/2# are not equal.
Proof. Assume that solutions (u1,…, u(r!3)/2 ) and (v1,…, v(r!3)/2 ) from the set
L((r ! 3)/2, p !1) are distinct, and the products are equal:
[(a! j +1)(! j + a)]u j
j=1
(r"3)/2
# = [(a! j +1)(! j + a)]v j
j=1
(r"3)/2
# .
Then, analogously to the proof of Lemma 1, we obtain the following equality for polynomials of
degree r ! 3 < deg"r (x) :
[(ax j +1)(x j + a)]u j
j=1
(r!3)/2
" = [(ax j +1)(x j + a)]v j
j=1
(r!3)/2
" . (4)
Let k be the smallest integer for which uk ! vk and uk > vk . After removing common factors
on both sides of (4), we have
818 R. POPOVYCH
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 6
[ax2k + (a2 +1)xk + a]uk!vk [(ax j +1)(x j + a)]
u j
j=k+1
(r!3)/2
" = [(ax j +1)(x j + a)]v j
j=k+1
(r!3)/2
" . (5)
Denote the absolute term for the polynomial [(ax j +1)(x j + a)]u jj=k+1
(r!3)/2" by b . Obviously
b ! 0 . Applying the multinomial formula to [ax2k + (a2 +1)xk + a]uk!vk , we obtain that there is
the term
(uk ! vk )(a2 +1)auk!vk!1bxk
in the polynomial on the left-hand side of (5) with minimal nonzero power of x . Since 0 ! uk ,
vk ! p "1 , uk ! vk , a2 ! "1 , a, b ! 0 , the term is nonzero. And such term does not occur on
the right-hand side, which leads to a contradiction.
Lemma 2 is proved.
Lemma 3. Let a be such nonzero element in the finite field Fq that a2 ! 1 . If solutions
(u1,…, ur!2 ) and (v1,…, vr!2 ) from L((r ! 3)/2, p !1) are distinct, then the products
[(a! j +1)(! j + a)"1]u jj=1
(r"3)/2# and [(a! j +1)(! j + a)"1]v jj=1
(r"3)/2# are not equal.
Proof. Assume that solutions (u1,…, u(r!3)/2 ) and (v1,…, v(r!3)/2 ) from the set
L((r ! 3)/2, p !1) are distinct, and the products are equal:
[(a! j +1)(! j + a)"1]u j
j=1
(r"3)/2
# = [(a! j +1)(! j + a)"1]v j
j=1
(r"3)/2
# .
Then, analogously to the proof of Lemma 1, we obtain the following equality for polynomials of
degree r ! 3 < deg"r (x) :
(ax j +1)u j (x j + a)v j
j=1
(r!3)/2
" = [(ax j +1)v j (x j + a)u j
j=1
(r!3)/2
" . (6)
Let k be the smallest integer for which uk ! vk and uk > vk . After removing common factors
on both sides of (6), we obtain
(axk +1)uk!vk (ax j +1)u j (x j + a)
v j
j=k+1
(r!3)/2
" = (xk + a)uk !vk (ax j +1)v j (x j + a)u j
j=k+1
(r!3)/2
" . (7)
Denote the absolute term for the polynomial (ax j +1)u j (x j + a)v jj=k+1
(r!3)/2" by b , and the abso-
lute term for the polynomial (ax j +1)v j (x j + a)u jj=k+1
(r!3)/2" by c . Obviously b, c ! 0 . Since
absolute terms on both sides of (7) are equal, the identity b = auk!vk c holds. As coefficients near
SHARPENING OF THE EXPLICIT LOWER BOUNDS ON THE ORDER … 819
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 6
xk on both sides of (6) are equal, we have (uk ! vk )ab = (uk ! vk )auk!vk!1c , which implies the
identity b = auk!vk!2c . Comparing the identities, we obtain a2 = 1 — a contradiction to the lem-
ma assumption a2 ! 1 .
Lemma 3 is proved.
3. Lower bounds based on a number of linear Diophantine inequality solutions. All lower
bounds on elements order in Theorem 1 below involve a number of solutions (u1,…, uc ) of the
linear Diophantine inequality (1), where 0 ! u1,…, uc !p "1 . We use for the proof of parts (a),
(b), (c) of the theorem a technique similar to that in [10 – 12]. The idea was introduced by Gathen
and Shparlinski [10], and developed in [11, 12]. We take a linear binomial of some power of !
and all conjugates of it, that also belong to the group generated by the binomial, and construct their
distinct products. In this case, the conjugates are nonlinear binomials. To obtain the bounds we
count solutions of a linear Diophantine inequality instead of counting integer partitions.
Theorem 1. Let e be any integer, f be any integer coprime with r , a be any nonzero
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 ! "1 has the multiplicative order at least L((r ! 3)/2, p !1)
and this order divides q(r!1)/2 !1 ,
(c) !"2e(!" f + a)(! f + a)
"1
for a2 ! 1 has the multiplicative order at least
L((r ! 3)/2, p !1) and this order divides q(r!1)/2 +1 ,
(d) !e(! f + a) for a2 ! ±1 has the multiplicative order at least L((r ! 3)/2, p !1) 2 /2 .
Proof. (a) First we show that !e(! f + a) has the same order as !g (! + a) , where g !
! e f "1(mod r) . Clearly the map, taking ! to ! p , is the Frobenius automorphism of the field
Fq (!) . Since q is primitive modulo r , the congruence f ! qm (mod r) holds for some integer
m . As q is a power of p , the map, sending ! to ! f = !q
m
, is a power of the Frobenius au-
tomorphism and, therefore, is also an automorphism of the field Fq (!) . Since the last examined
automorphism takes !g (! + a) to !e(! f + a) , multiplicative orders of these elements coincide.
So, to prove (a), it is sufficient to show that !g (! + a) has the multiplicative order at least
L(r ! 2, p !1) .
As q is primitive modulo r , for each j = 1,…, r ! 2 , an integer !( j) exists such that
q!( j ) " ( jmod r) . The powers
!g (! + a)( )q
"( j )
= !gq
"( j )
(!q
"( j )
+ a) = !gj (! j + a)
belong to the group !"g (" + a)# . For every solution from L(r ! 2, p !1) we construct the follow-
ing product:
820 R. POPOVYCH
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 6
[!gj (! j + a)]u j
j=1
r"2
# = !
g ju jj=1
r"2$ (! j + a)u j
j=1
r"2
# = !g(r"2) (! j + a)u j
j=1
r"2
#
that also belong to the group. Note that all these products have the same factor !g(r"2) . According
to Lemma 1, if two solutions (u1,…, ur!2 ) and (v1,…, vr!2 ) from L(r ! 2, p !1) are distinct,
then the products (! j + a)u jj=1
r"2# and (! j + a)v jj=1
r"2# are not equal. Hence, the products
!g(r"2) (! j + a)u jj=1
r"2# and !g(r"2) (! j + a)v jj=1
r"2# , corresponding to distinct solutions, cannot
be equal and the result follows.
(b) The order of the group Fqr!1
* equals to qr!1 !1 = (q(r!1)/2 !1)(q(r!1)/2 +1) . Note that
since q is primitive modulo r , and r is prime, the congruencies qr!1 " 1(mod r) аnd
q(r!1)/2 " !1(mod r) are true. Then
[!e(! f + a)]q
(r"1)/2+1 = !e(q
(r"1)/2+1)(! fq
(r"1)/2
+ a)(! f + a) = (!" f + a)(! f + a) ,
and so, the order of (!" f + a)(! f + a) divides q(r!1)/2 !1 . We show that (!" f + a)(! f + a)
generates the group of the order at least L((r ! 3)/2, p !1) . Indeed, since the field automorphism,
taking ! to ! f , sends (!"1 + a)(! + a) to (!" f + a)(! f + a) , multiplicative orders of these
elements coincide. Hence, it is sufficient to prove that
(!"1+a)(! + a) = !"1(a! +1)(! + a)
has the multiplicative order at least L((r ! 3)/2, p !1) .
As q is primitive modulo r , for j = 1,…, (r ! 3)/2 , an integer !( j) exists such that
q!( j ) " j(mod r) . The powers
[!"1(a! +1)(! + a)]q
#( j )
= !" j (a! j +1)(! j + a)
belong to the group !"#1(a" +1)(" + a)$ . For every solution from the set L((r ! 3)/2, p !1) , we
construct the following product:
[!" j (a! j +1)(! j + a)]
u j
j=1
(r"3)/2
# =
= !
" ju jj=1
(r"3)/2# [(a! j +1)(! j + a)]u j
j=1
(r"3)/2
$ = !"(r"3)/2 [(a! j +1)(! j + a)]u j
j=1
(r"3)/2
$
that also belong to the group. Note that these products have the same factor 2/)3( −− rθ . According
SHARPENING OF THE EXPLICIT LOWER BOUNDS ON THE ORDER … 821
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 6
to Lemma 2, if two solutions from L((r ! 3)/2, p !1) are distinct, then the products
[(a! j +1)(! j + a)]u jj=1
(r"3)/2# and [(a! j +1)(! j + a)]v jj=1
(r"3)/2# are not equal. Hence, the result
follows.
(c) Since
[!e(! f + a)]q
(r"1)/2"1 = !e(q
(r"1)/2"1)(! fq
(r"1)/2
+ a)(! f + a)"1 = !"2e(!" f + a)(! f + a)"1 ,
the order of !"2e(!" f + a)(! f + a)"1 is a divisor of q(r!1)/2 +1 . We show that !"2e(!" f +
+ a)(! f + a)"1 generates the group of the order at least L((r ! 3)/2, p !1) . Indeed, since the field
automorphism, taking ! to ! f , sends !"2ef
"1
(!"1 + a)(! + a)"1 to !"2e(!" f + a)(! f + a)"1 ,
multiplicative orders of these elements coincide. Hence, it is sufficient to prove that
!"2ef
"1
(!"1 + a)(! + a)"1 = !t (a! +1)(! + a)"1 ,
where t = ! 2ef !1 !1 , has the multiplicative order at least L((r ! 3)/2, p !1) .
As q is primitive modulo r , for j = 1,…, (r ! 3)/2 , an integer !( j) exists such that
q!( j ) " j(mod r) . The powers
[!t (a! +1)(! + a)"1]q
#( j )
= ! jt (a! j +1)(! j + a)"1
belong to the group !"t (a" +1)(" + a)#1$ . For every solution from the set L((r ! 3)/2, p !1) , we
construct the following product:
[! jt (a! j +1)(! j + a)"1]u j = !
t ju jj=1
(r"3)/2# [(a! j +1)(! j + a)"1]u j
j=1
(r"3)/2
$
j=1
(r"3)/2
$ =
= !t(r"3)/2 [(a! j +1)(! j + a)"1]u j
j=1
(r"3)/2
#
that also belong to the group. Note that these products have the same factor !t(r"3)/2 . According
to Lemma 3 if two solutions from L((r ! 3)/2, p !1) are distinct, then the products
[(a! j +1)(! j + a)"1]u jj=1
(r"3)/2# and [(a! j +1)(! j + a)"1]v jj=1
(r"3)/2# are not equal. Hence, the
result follows.
(d) Recall that the order of Fqr!1
* equals to qr!1 !1 = (q(r!1)/2 !1)(q(r!1)/2 +1) . Factors
q(r!1)/2 !1 and q(r!1)/2 +1 have the greatest common divisor 2, since their sum equals to
2q(r!1)/2 . Consider the subgroup of Fqr!1
* generated by !e(! f + a) . This subgroup contains two
subgroups: first one is generated by
822 R. POPOVYCH
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 6
w1 = [!e(! f + a)]q
(r"1)/2+1 = (!" f + a)(! f + a) ,
and second one — by
w2 = [!e(! f + a)]q
(r"1)/2"1 = !"2e(!" f + a)(! f + a)"1 .
According to part (b), the order of w1 divides q(r!1)/2 !1 , and according to part (c), the order of
w2 divides q(r!1)/2 +1 .
Construct the element
w =
w12w2 if !2(q(r"1)/2 "1) = 2,
w1w22 if !2(q(r"1)/2 +1) = 2.
#
$
%%
&
%
%
If !2(q(r"1)/2 "1) = 2 , then (q(r!1)/2 !1)/2 is odd and coprime with q(r!1)/2 +1 . Clearly the
order of w12 is a divisor of (q(r!1)/2 !1)/2 . Hence, in this case, !z" = !w12 " # !w2 " . Similar to the
previous consideration, if !2(q(r"1)/2 +1) = 2 , then !z" = !w1" # !w22 " . In both cases, the order of
w is the product of the orders of w1 and w2 divided by 2. According to part (b) and part (c), the
order of w , and so, the order of !e(! + a) is at least L((r ! 3)/2, p !1) 2 /2 .
Theorem 1 is proved.
Corollary 1. The Gauss period ! has the multiplicative order at least L(r ! 2, p !1) and
this order divides q(r!1)/2 !1 .
Proof. It follows from Theorem 1, part (a) that the multiplicative order of
! = " + "#1= "#1("2 +1) is at least L(r ! 2, p !1) . Since
(! + !"1)q
(r"1)/2"1 = (!q
(r"1)/2
+ !"q
(r"1)/2
)(! + !"1)"1 = (!"1 + !)(! + !"1)"1 = 1 ,
the order of ! divides q(r!1)/2 !1 .
Corollary 1 is proved.
Let a be any nonzero element in Fq . We use below the following denotations:
! = ("#1 + a)(" + a)#1 and z =
!2" if #2(q(r$1)/2 $1) = 2,
!" 2 if #2(q(r$1)/2 +1) = 2.
%
&
'
(
'
Corollary 2. The element z for a2 ! 1 has the multiplicative order at least
L(r ! 2, p !1) L((r ! 3)/2, p !1) /2 .
SHARPENING OF THE EXPLICIT LOWER BOUNDS ON THE ORDER … 823
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 6
Proof. According to Corollary 1, ! has the order that divides q(r!1)/2 !1 and is at least
L(r ! 2, p !1) . According to Theorem 1, part (c) (if to put e = 2!1(mod r) , f = 1 ), ! has the
order that divides q(r!1)/2 +1 and is at least L((r ! 3)/2, p !1) . Analogously to the proof of
Theorem 1, part (d), the order of z is the product of the orders of ! and ! divided by 2.
Hence, the result follows.
Corollary 2 is proved.
4. Explicit lower bounds on orders for any p and r . Explicit lower bounds on the orders
of finite field elements in terms of p and r are of special interest in applications. That is why
we count in this section a number of solutions of the linear Diophantine inequality to derive explicit
lower bounds on the multiplicative orders of the examined elements !e(! f + a) and z .
Lemma 4. The number L(c, d) of solutions of linear Diophantine inequality (1) with the
condition 0 ! u1,…, uc ! d , is at least
(d +1) c /2!2 if d = 1, 2,
5 c /2!2 if d " 4.
#
$
%
&
%
Proof. Let ! , 1 ! " ! d , be an integer which we shall choose later. Take the biggest integer
! such that ii=1
!" # $ c . Since
i!
i=1
"
# = !"(" +1)/2 < !(" +1)2 /2 ,
we choose ! from the inequality !(" +1)2 # 2c , that is ! = 2c/"#$ %& '1 . Clearly, if to take
ui !{0,…, " #1} for i = 0,…,! and u i= 0 for i = ! +1,…, c , we obtain a solution of (1).
The number of such solutions equals to (! +1)" # (! +1) 2c /!$2 = (! +1) 2c /! /(! +1)2 .
To choose ! , we find maximum of the numerator f (!) = (! +1) 2c /! of the last bound. Ob-
viously ! = d in the case d = 1, 2 .
So, we assume below that d ! 4 . Represent the numerator in the form f (!) =
= exp ln (! +1) 2c/!( ) . Then we have
!f (") = (" +1) 2c /" 2c/" 1
" +1
# ln (" +1)
2"
$
%&
'
() .
If to write !f (") = 0 , then 1
! +1
" ln (! +1)
2!
= 0 . The value 3,92155 < !0 < 3,921555 is a point
824 R. POPOVYCH
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 6
of function maximum. The nearest integer to maximum is ! = 4 . The function f (!) monoton-
ically decreases for ! " !0 , and the denominator (! +1)2 monotonically increases. Hence, we
take ! = 4 in this case, and the result follows.
Lemma 4 is proved.
Our main result is the following theorem that gives explicit lower bounds on the elements orders.
Theorem 2. Let q be a power of prime number p , r = 2s +1 be a prime number coprime
with q , q be a primitive root modulo r , ! generates the extension Fq (!) = Fqr"1 , e be any
integer, f be any integer coprime with r , a be any nonzero element in the finite field Fq .
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 ! ±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,
#
$
%%
&
%
%
(c) z for a2 ! 1 has the multiplicative order at least
2( 2+1) r!3!5 if p = 2,
3( 2+1) r!3/2!4 /2 if p = 3,
5( 2+1) r!3/2!4 /2 if p " 5.
#
$
%%
&
%
%
Proof. (a) According to Theorem 1, part (a) and Lemma 4.
(b) According to Theorem 1, part (d) and Lemma 4.
(c) According to Corollary 2 and Lemma 4.
Theorem 2 is proved.
We obtain the following corollary from Theorem 2.
Corollary 3. The Gauss period ! 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.
#
$
%
&
%
The bound in Corollary 3 improves the previous bound 2 r!1!2 from [10] on the multiplica-
tive order of the element ! .
1. Lidl R., Niederreiter H. Finite fields. – 2nd ed. – Cambridge: Cambridge Univ. Press, 1997. – 755 p.
2. Mullen G. L., Panario D. Handbook of finite fields. – CRC Press, 2013. – 1068 p.
3. Gao S. Elements of provable high orders in finite fields // Proc. Amer. Math. Soc. – 1999. – 127, № 6. – P. 1615 –
1623.
4. Voloch J. F. On the order of points on curves over finite fields // Integers. – 2007. – 7. – P. 49.
5. Voloch J. F. Elements of high order on finite fields from elliptic curves // Bull. Austral. Math. Soc. – 2010. – 81, № 3.
– P. 425 – 429.
SHARPENING OF THE EXPLICIT LOWER BOUNDS ON THE ORDER … 825
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 6
6. Cheng Q. On the construction of finite field elements of large order // Finite Fields Appl. – 2005. – 11, № 3. –
P. 358 – 366.
7. Popovych R. Elements of high order in finite fields of the form Fq[x]/(xm ! a) // Finite Fields Appl. – 2013. – 19,
№ 1. – P. 86 – 92.
8. Попович Р. Елементи великого порядку в розширеннях Артіна – Шраєра скінченних полів // Мат. студ. –
2013. – 39, № 2. – С. 115 – 118.
9. Cheng Q., Gao S., Wan D. Constructing high order elements through subspace polynomials // Proc. 23rd ACM-SIAM
Symp. Discrete Algorithms (Kyoto, Japan, 17 – 19 January 2012). – Philadelphia, USA, 2011. – P. 1457 – 1463.
10. Gathen J., Shparlinski I. E. Orders of Gauss periods in finite fields // Appl. Algebra Engrg. Comm. Comput. –
1998. – 9, № 1. – P. 15 – 24.
11. Ahmadi O., Shparlinski I. E., Voloch J. F. Multiplicative order of Gauss periods // Int. J. Number Theory. – 2010. – 6,
№ 4. – P. 877 – 882.
12. Popovych R. Elements of high order in finite fields of the form Fq[x]/!r (x) // Finite Fields Appl. – 2012. – 18, № 4.
– P. 700 – 710.
Received 29.07.13
|