D. Khovratovich - Divisibility of a Hamming Weight by 2^k and Monomial Criteria for Boolean Functions (794370)
Текст из файла
Divisibility of the Hamming Weight by 2k andMonomial Criteria for Boolean FunctionsDmitry Khovratovich, diho@rnt.ruMoscow State University, Faculty of Computational Mathematics and CyberneticsAbstract. In this paper we consider the notions of the Hamming weight and thealgebraic normal form. We solve an open problem devoted to checking divisibility ofthe weight by 2k . We generalize the criterion for checking the evenness of the weightin two ways.
Our main result states that for checking whether the Hamming weight off is divisible by 2k , k > 1, it is necessary and sufficient to know its algebraic normalform accurate to an additive constant.Keywords: boolean functions, Hamming weight, algebraic normal form, coding theory.1IntroductionIn this paper we consider the notion of the weight of a boolean function. We solve an openproblem from [1]: we formulate criteria for divisibility of the weight by powers of two.In the sequel, the following notation will be used (see, i.e. [3]). A boolean function f ofn variables is a function from Fn2 into F2 .
It can be expressed as a polynomial, called itsalgebraic normal form (ANF):f (x) =Mcα xα ,cα ∈ F2 ,(1)α∈Fn2αn1 α2where ⊕ denotes the addition over F2 , α = (α1 , . . . , αn ) and xα = xα1 x2 · · · xn .defDenote by wt(f ) the (Hamming) weight of f , i.e.
the size of the set Nf = {x ∈ Fn2 |f (x) =1}. We say that wt(f ) is divisible by t if wt(f ) ≡ 0 (mod t).As noticed in [1], divisibility of wt(f ) by 2k for some k is a property of a function thatis useful in coding theory. Assume we know the ANF of f (1). Then it may be proved thatProposition 1 ([1]). The weight of f is divisible by 2 iff c(1,1,...,1) = 0.Hence we do not need to know all cα . Logachev et al.
[1] set a problem: can this propertybe somehow extended to other divisors of the form 2k ?They also conjectured that the following theorem by McEliece could be generalized withrespect to the set of all non-zero ANF coefficients.Proposition 2 ([2]). Suppose f is a boolean function, and its algebraic normal form is apolynomial of degree r. Then wt(f ) is divisible by 2dm/re−1 .2The main result of the paperWe find the relationship between the set of non-zero coefficients of algebraic normal formand divisibilty of the weight by 2k . We generalize the proposition 1 in two ways. We considerboth ways and show that only trivial criteria may be formulated.3First generalizationDenote by Cf the set of all α giving non-zero coefficients in the ANF (1).
Also denote(11 . . . 1) by 1 and(00 . . . 0) by 0. With respect to this notation we obtainwt(f ) ≡ 0(mod 2) ⇔ Cf ⊆ Fn2 \ {1}.(2)from Pr. 1.Let us give an appropriate definition.We say that a set G ⊂ Fn2 is a strongly criterial with respect to the property C if for anyf ∈ Fn the following condition holds:f has C ⇐⇒ Cf ⊆ G.One may assume that such a condition is too strong. Indeed, we have the followingtheorem.Theorem 1. Suppose k is a positive integer and not greater than n. Then a strongly criterialset with respect to divisibility of the weight by 2k exists iff k = 1 or k = n.Proof. We consider three cases.– k = 1.
Using (2) we obtain that Fn2 \ {1} is a strongly criterial set w.r.t. divisibility ofthe weight by two.– k = n. We get wt(f ) ≡ 0 (mod 2n ). Taking into account the fact that 0 6 wt(f ) 6 2nwe obtain that f is a constant. Obviously C0 = ∅ and C1 = {0}. Denote by G the set{0}.
It is easy to prove thatwt(f ) ≡ 0(mod 2n ) ⇐⇒ Cf ⊆ G.This implies that G is strongly criterial.– 1 < k < n. Now we show that no strongly criterial set exists for such k. Assume theconverse. Let G be a strongly criterial set w.r.t. divisibility of the weight by 2k . Supposefunctions f1 , f2 satisfy following conditions:wt(f1 ) ≡ 0(mod 2k ),wt(f2 ) ≡ 0(mod 2k ).(3)Then we haveCf1 ⊆ G, Cf2 ⊆ G =⇒ G ⊇ Cf1 ∪ Cf2 ⊇ Cf1 ⊕f2 .Therefore, we havewt(f1 ⊕ f2 ) ≡ 0 (mod 2k ).(4)To get a contradiction, we construct functions f1 and f2 which satisfy (3) and do notsatisfy (4).Indeed, the condition 1 < k < n implies the following.
The reader will easily prove thatthere exist sets A1 , A2 ⊂ Fn2 such that|A1 | = |A2 | = 2k ,|(A1 ∩ A2 )| = 1.Now we define f1 and f2 . By definition, putfi (x) = 1 ⇔ x ∈ Ai ,i = 1, 2.We obtain|Nf1 | = |Nf2 | = 2k ≡ 0(mod 2k );|Nf1 ⊕f2 | = |(A1 4 A2 )| = 2 · 2k − 2 6≡ 0(mod 2k ).Therefore, f1 and f2 satisfy (3) and do not satisfy (4). This contradiction proves thetheorem.Therefore, our generalization implies too strong conditions. Let us make them weaker.4Second generalizationWe say that a set G ⊂ Fn2 is a weakly criterial with respect to the property C, if for any f1and f2 the conditionEither f1 or f2 has CimpliesG ∩ Cf1 6= G ∩ Cf2 .We will omit the phrase ¡¡with respect to C¿¿ when C is clear from context.Example. Using (2) we obtain that the set {1 = (1, 1, . .
. , 1)} is a weakly criterial w.r.t.divisibility of the weight by 2.Let us remark that such a definition is actually weaker than the former one. Any weaklycriterial set only divides the set of all boolean functions into equivalence classes: M1 ∼ M2 ⇔G ∩ M1 = G ∩ M2 .We claim that there exist only trivial weakly criterial sets.Theorem 2. Let k be a positive integer such that 2 6 k 6 n. Then for the set G to beweakly criterial w.r.t. divisibility of the weight by 2k it is necessary and sufficient to have(Fn2 \ {0}) ⊆ G.Proof. First of all, we prove sufficiency. Secondly, we prove necessity for k = n. Finally, weprove necessity for 2 6 k 6 n − 1.Sufficiency. Let G be a set of n-tuples such that (Fn2 \ {0}) ⊆ G.
Then only two cases arepossible: G = Fn2 and G = Fn2 \ {0}.The first case is trivial: obviously, Fn2 is a weakly criterial set. Consider the second case.Let f be a boolean function such thatwt(f ) ≡ 0(mod 2k ).(5)Now we prove that G = Fn2 \ {0} is a weakly criterial set.Assume the converse: there exists a function f 0 such thatwt(f 0 ) 6≡ 0(mod 2k ),(6)butG ∩ Cf = G ∩ Cf 0 .(7)Hence we haveG = Fn2 \ {0} =⇒ G ∩ Cf = Cf \ {0}, G ∩ Cf 0 = Cf 0 \ {0}.If we combine this with (6), we getCf \ {0} = Cf 0 \ {0}.(8)It implies that the ANF of f equals the ANF of f 0 accurate to a constant.
Using thecondition f 6= f 0 we get f 0 = f ⊕ 1. It is easy to prove that wt(f ) + wt(f ⊕ 1) = 2n for anyf . Combining it with (5) and the condition k 6 n − 1, we obtain wt(f 0 ) ≡ 0 (mod 2k ). Itimplies the contradiction with (7).Thus G is a weakly criterial set of tuples.Necessity for k = n. By definition, put f1 ≡ 0 and f2 = xa , where a is an arbitrary non-zerotuple. Then the following conditions hold:f1 has the property of 2n -divisibility;f2 does not have the property of 2n -divisibility;Cf1 = ∅, Cf2 = {a}.Take any weakly criterial set G with respect to divisibility of the weight by 2k .
ThisimpliesG ∩ Cf1 6= G ∩ Cf2 .Hence we obtain G ∩ Cf2 = {a}. Arbitrariness of a implies(Fn2 \ {0}) ⊆ G.Necessity for 2 6 k 6 n − 1. Let k belongs to [2; n − 1] and let G be a weakly criterial setw.r.t. divisibility of the weight by 2k . Now we prove that (Fn2 \ {0}) ⊆ G.Assume the converse: (Fn2 \{0}) * G. Fix an arbitrary tuple α ∈ Fn2 \({0}∪G). Considertwo cases.– α = 1. Consider the functions f1 ≡ 0 and f2 ≡ xα = x1 x2 · · · xn .
It follows easily thatwt(f1 ) ≡ 0(mod 2k );wt(f2 ) ≡ 1 (mod 2k );G ∩ Cf1 = G ∩ Cf2 = ∅.Hence G is not a weakly criterial set, so we get a contradiction.– α 6= 1. Denote by A the set {a ∈ Fn2 | α 4 a 4 1}, where α 4 β describes the partialordering on the Boolean lattice. Also denote the number of units (non-zero elements) inα by m. Then we obtain|A| = 2n−m , m 6 n − 1, |Fn2 \ A| > 2n−1 .(9)xα = 1 ⇔ x ∈ A.(10)Note that(9) implies the existence of a function f such that|Nf ∩ A| = 2n−m−1 − 1, |Nf \ A| = 2n−1 − 2n−m−1 + 1.(11)Fix an arbitrary f that satisfies (11). Define a function f 0 by the rulef 0 = f ⊕ xα .It impliesG ∩ Cf = G ∩ Cf 0 .(12)Nf \ A = Nf 0 \ A from (10);|Nf ∩ A| + |Nf 0 ∩ A| = |A|.(13)(14)Therefore, we haveCombining (11) with the condition k 6 n − 1, we getwt(f ) = 2n−m−1 − 1 + 2n−1 − 2n−m−1 + 1 = 2n−1 ≡ 0(mod 2k ).(15)0To evaluate wt(f ), we combine the equations (13) and (14) with (9) and (11).
Then wesee thatwt(f 0 ) = 2n−m − (2n−m−1 − 1) + 2n−1 − 2n−m−1 + 1 = 2n−1 + 2 ≡ 2(mod 2k ). (16)Therefore, the weight of f 0 is not divisible by 2k , which is contrary to (12). This contradiction proves the theorem.5SummaryHence for checking whether the Hamming weight of f is divisible by 2k , k > 1, it is necessaryand sufficient to know its algebraic normal form accurate to an additive constant.The author is grateful to professors Alekseev V.B. and Logachev O.
A. for constantattention to this work.This research was partially supported by RFBR grant 06-01-10023.References1. O. A. L o g a c h e v, A. A. S a l n i k o v, V. V. Y a s c h e n k o ”Boolean functions in codingtheory and cryptology”, Moscow, MCCME, 2004 (In Russian).2. R. J. M c E l i e c e ”Weight congruences for p-ary cyclic codes”, Discrete Math 3 (1972), pp177–192.3. A. C a n t e a u t, E. F i l i o l, ”Ciphertext Only Reconstruction of Stream Ciphers Based onCombination Generators”, FSE 2000, number 3027 in Lecture Notes in Computer Science, pages165–180.
Springer-Verlag, 2000..
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
