7 / 14
Now we will estimate the number of independent cycles and their length
for the
h
0
permutation. According to (4) and (5) formulae, it’s impossible to
obtain
K
independent transpositions in the
h
0
decomposition, if the number
of independent cycles is strictly less than
K
and their length is strictly less
than 5. Therefore, the sum of the lengths of cycles in the
h
0
decomposition
does not exceed
4(
K
−
1)
.
A set of moving points of an arbitrary permutation
g
∈
S
(
Z
n
2
)
:
M
g
=
{
x
∈
Z
n
2
|
g
(x)
6
= x
}
can be denoted by
M
g
: given the foregoing,
|
M
h
|
6
2
n
,
|
M
h
0
|
6
4(
K
−
1)
.
According to (4)–(6) formulae, it is possible to get no more than
|
M
h
|
/K
groups in the decomposition of
h
permutation, each group
having
K
independent transpositions, and no more than
|
M
h
0
|
/
2
pairs
of independent transpositions in the decomposition of
h
0
permutation and
no more than one pair of dependent transpositions.
A pair of dependent transpositions
(
i, j
)
◦
(
i, k
)
can be expressed by
the product of two pairs of independent transpositions:
(
i, j
)
◦
(
i, k
) =
= ((
i, j
)
◦
(
r, s
))
◦
((
r, s
)
◦
(
i, k
))
.
Considering the above information, it is possible to estimate the upper
bound of
L
(
h
)
:
L
(
h
)
6
|
M
h
|
K
L
(
g
(
K
)
) +
|
M
h
0
|
2
L
(
g
(2)
) + 2
L
(
g
(2)
);
L
(
h
)
.
2
n
K
L
(
g
(
K
)
) + 2
KL
(
g
(2)
)
,
(7)
where
g
(
i
)
is an arbitrary permutation, representing the product of
i
independent transpositions.
Now we will estimate the value of
L
(
g
(
K
)
)
for the arbitrary
g
(
K
)
permu-
tation. Suppose
k
=
|
M
g
(
K
)
|
= 2
K
. Implementing the
g
(
K
)
permutation
with the gates from
Ω
2
n
set will be carried out by the method described
in work [7]: by conjugation we will reduce
g
(
K
)
permutation to a certain
permutation, defined by a simple way. The conjugation does not change the
cyclic structure of the permutation, as well as the result of the conjugation,
g
(
K
)
permutation will always remain as a composition of
K
independent
transpositions.
For
g
(
K
)
= (x
1
,
y
1
)
◦
. . .
◦
(x
K
,
y
K
)
permutation
A
matrix is as follows:
A
=
x
1
y
1
. . .
x
K
y
K
=
a
1
,
1
. . . a
1
,n
a
2
,
1
. . . a
2
,n
∙ ∙ ∙
∙ ∙ ∙
∙ ∙ ∙
a
k
−
1
,
1
. . . a
k
−
1
,n
a
k,
1
. . . a
k,n
.
(8)
ISSN 0236-3933. HERALD of the BMSTU. Series “Instrument Engineering”. 2015. No. 1 73