Information Technology Reference
In-Depth Information
degree of
F
(
X
). Note that each mapping of IF
p
can be represented by a polyno-
mial. However, a representation as rational mapping can provide much stronger
results.
For example, in the special case
F
(
X
)=
aX
p−
2
+
b,
IF
p
,b
a
∈
∈
IF
p
,
the much stronger result
S
χ
=
O
T
1
/
2
p
1
/
4
was obtained in [7], which is nontrivial whenever
T>p
1
/
2
.Since
x
p−
2
=
x
−
1
IF
p
, the sequence (
u
n
) can up to at most one sequence element be
defined with the rational function
F
(
X
)=
aX
−
1
+
b
.
In [2] we investigated another special class of nonlinear recurring sequences
(1) constructed via
Dickson polynomials
F
(
X
)=
D
e
(
X
)
for all
x
∈
∈
IF
p
[
X
] defined by the
recurrence relation
D
e
(
X
)=
XD
e−
1
(
X
)
−
D
e−
2
(
X
)
,
e
=2
,
3
,...,
with initial values
D
0
(
X
)=2
,
1
(
X
)=
X.
Under the condition gcd(
e, p
2
1) = 1, which characterizes the Dickson permuta-
tion polynomials, see [5, Theorem 3.2], we obtained nontrivial bounds provided
that
T>p
1
/
2+
ε
and if
T
=
p
1+
o
(1)
we obtained
S
χ
=
O
p
7
/
8+
o
(1)
.
−
This article deals with the special class of nonlinear recurring sequences (1)
constructed via
Redei functions
defined in the sequel, which have some similar
properties as Dickson polynomials.
Suppose that
r
(
X
)=
X
2
IF
p
[
X
]
is an irreducible quadratic polynomial with the two different roots
ξ
and
ζ
=
ξ
p
in IF
p
2
. Then any polynomial
b
(
X
)
−
αX
−
β
∈
IF
p
2
[
X
] can uniquely be written in the
form
b
(
X
)=
g
(
X
)+
h
(
X
)
ξ
with
g
(
X
)
,h
(
X
)
∈
∈
IF
p
[
X
]. For a positive integer
e
,
we consider the elements
(
X
+
ξ
)
e
=
g
e
(
X
)+
h
e
(
X
)
ξ.
(2)
Note that
g
e
(
X
)and
h
e
(
X
) do not depend on the choice of the root
ξ
of
r
(
X
).
Evidently,
e
isthedegreeofthepolynomial
g
e
(
X
), and
h
e
(
X
) has degree at
most
e
1, where equality holds if and only if gcd(
e, p
) = 1, see [5, p. 22] or [10].
The
Redei function
R
e
(
X
)ofdegree
e
is then given by
−
R
e
(
X
)=
g
e
(
X
)
h
e
(
X
)
.
