Cryptography Reference
In-Depth Information
A. Permutation Polynomials
Before addressing the quadratic PP, we will define the general form of a
polynomial and discuss how to verify whether a polynomial is a PP over the
ring of integers modulo
N
,
2
,apolynomial
f
(
x
)=
a
0
+
a
1
+
a
2
x
2+
...
+
a
m
x
m
modulo
N
(7.19)
where the coecients
a
0
,a
1
,a
2
,...,a
m
and
m
are non-negative integers, is said
to be permutation polynomial over
Z
N
. Given an integer
N
≥
}
[7.41]. Since we have modulo
N
operation, it is sucient for the coecients
a
0
,a
1
,a
2
,...,a
m
to be in
Z
N
when
f
(
x
)
permutes
{
0
,
1
,
2
,...,N
−
1
Z
N
. Let us recall that the formal derivative of the
polynomial
f
(
x
)
is given by
f
(
x
)=
a
1
+2
a
2
x
+3
a
3
x
2
+
...
+
ma
m
x
m−
1
modulo
N
(7.20)
To verify whether a polynomial is a PP over
Z
N
, let us discuss the following
three cases a) the case
N
=2
n
,where
n
is an element of the positive integers
Z
+
,b)thecase
N
=
p
n
where
p
is any prime number, and c) the case where
N
is an arbitrary element of
Z
+
.
1. Case I (
N
=2
n
): a theorem in [7.36] states that
f
(
x
)
is a PP over the
integer ring
2
if and only if 1)
a
1
is odd, 2)
a
2
+
a
4
+
a
6
+
...
is even,
and 3)
a
3
+
a
5
+
a
7
+
...
is even.
Z
Example 1
for
N
=2
3
=8:
f
(
x
)=1+5
x
+
x
2
+
x
3
+
x
5
+3
x
6
is
aPPover
Z
N
=8
because it maps the sequence
{
0
,
1
,
2
,
3
,
4
,
5
,
6
,
7
}
to
{
.Notethat
a
1=5
is odd,
a
2
+
a
4
+
a
6
=1+0+3=4
is even, and
a
3
+
a
5
=1+1=2
is even.
1
,
4
,
7
,
2
,
5
,
0
,
3
,
6
}
Example 2
for
N
=2
3
=8:
f
(
x
)=1+4
x
+
x
2
+
x
3
+
x
5
+3
x
6
is
not PP over
Z
N
=8
because it maps the sequence
{
0
,
1
,
2
,
3
,
4
,
5
,
6
,
7
}
to
.Notethat
a
1
=4
is even.
2. Case II (
N
=
p
n
): a theorem in [7.33] guarantees that
f
(
x
)
is a PP
modulo pn if and only if
f
(
x
)
is a PP modulo
p
and
f
(
x
)
{
1
,
3
,
5
,
7
,
1
,
3
,
5
,
7
}
=0
modulo
p
,
p
. Note that the Case I is simply a special case of
the Case II because
p
=2
is a prime number.
for every integer
x
∈
Z
3
because
f
(0) = 1
modulo
3=1
,f
(1) = 6
modulo
3=0
,
f
(2) = 17
modulo
3=2
,
and
f
(
x
)=2+6
x
=2
modulo
3=2
is a non-zero constant for all
xin
Example 1
for
N
=3
n
(
p
=3):
f
(
x
)=1+2
x
+3
x
2
is a PP over
Z
3
.
Z
Example 2
for
N
=3
n
(
p
=3):
f
(
x
)=1+6
x
+3
x
2
is not a PP
3
because
Z
f
(
x
)=6+6
x
=0
modulo
3=0
for all
xin
3
. For instance, for
N
=3
2
=
Z
9
,
f
(
x
)
maps the sequence
{
0
,
1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
}
to
{
1
,
1
,
7
,
1
,
1
,
7
,
1
,
1
,
7
}
.