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
}
.
Search WWH ::




Custom Search