On one-to-one property of a vectorial Boolean function of the special type.pdf Let n G Sn be a permutation such that nn(x) = x. Consider some x G Fn, x = (x1, ... ,xn), define n(x) = (xn(1),...,xn(n)). Let f be a Boolean function in n variables, we construct vectorial Boolean function Fn : Fn ^ Fn by the following rule: Fn(x) = (f (x), f (n(x)),f (n8(x)),..., f (nn-1(x))). Let An,n be the set of all these functions. Define p(x) = (xn, x1, x2,..., xn-1), i.e., p = = (n, 1,2,..., n - 1). Proposition 1. Let n G Sn be such that nn(x) = x, Fn G An,n. Then Fn(n(x)) = = p-1(Fn(x)) for all x G Fn We define action of n on Fn by the rule: if x G Fn, then x о n = n(x). This action splits Fn into orbits with respect to n. If x is in some orbit o, we call x a generator of o. We call On(x) the orbit with respect to the action of n. Example 1. For n = 4, the set Fn is divided into six orbits with respect to the permutation p: 0p((0,0, 0, 0)) (0, 0, 0,0) Op((1,0, 0, 0)) (1, 0, 0,0), (0,1,0,0), (0, 0,1,0), (0,0,0,1) Op((1,0,1, 0)) (1, 0,1,0), (0,1,0,1) Op((1,0, 0,1)) (1, 0, 0,1), (1,1,0,0), (0,1,1,0), (0,0,1,1) 0p((0,1,1,1)) (0,1,1,1), (1, 0,1,1), (1,1,0,1), (1,1,1,0) Op((1,1,1,1)) (1,1,1,1) We denote by en,n the set of all orbits with respect to the action of n on Fn. Proposition 1 implies that, for arbitrary Fn G Ann, values of elements of some п-orbit g G en,n are elements of some p-orbit q G epn, since Fn(nl(x)) = p-i(Fn (x)). Let Mkn = {g G enn : |g| = k}. ' Let ,n : en,n ^ ep,n be a mapping defined by the rule ,n(On(x)) = Op(Fn(x)). Now we can formulate conditions for Fn to be one-to-one in terms of ,n. Theorem 1. Fn G An,n is an one-to-one function if and only if ,n is one-to-one. If ^Fn,n is one-to-one, then |Ф^,n(g)| = |g|, for all g G вп,„. As a corollary of Theorem 1, we obtain the following result. Proposition 2. If |МП?)П| = |Mp,n| for some k, then the set of one-to-one functions from Ann is empty. Theorem 1 means that in order to construct one-to-one functions Fn G An,n we can use bijective maps Фп : On>n ^ 0An that satisfy |Фп(g)| = |g|, where g G On>n. Then, depending on them, we can construct Fn G An n such that ,n = Фп. Proposition 3. Let Фп : On,n ^ 0An satisfy |Фп(g)| = |g| for all g G On,n. Then, for all k G N, the restriction of Фп on Mknn is a permutation of Mkn. Now consider the case n = p. We define M^ = Mpn. Consider an one-to-one function Фп which satisfies ^n(g)| = |g| for all g G On,n. Let us construct function Fp G Apn based on Фп. Let O G Opn be an orbit of length k. If the value of Fp for some xgO is determined, then the value of Fp is determined for all x G O, since Fp(pn(x)) = p-n(Fp(x)). Thus, for every Ф^Р)П, we are able to construct П k|Mn 1 functions, where In = {z G N : z|n}, and all fcein of them are pairwise different. Proposition 4. For any k G N, £ t ■ M | = 2fc. This formula allows us to calculate |M^ | for every k. There are always only two orbits of length one, so we can calculate |M^| for every prime k. Then we can calculate it for every k. Therefore, we get the number of one-to-one functions from Apn: Theorem 2. The number of one-to-one vectorial Boolean functions in class Apn is equal to П M|! ■ klMkl. fcein

Скачать электронную версию публикации