C&SA | Contents

Volume 49>№ 2 MARCH — APRIL 2013

UDC 621.391:519.2

Alekseychuk A.N., Konyushok S.N.

AN IMPROVED TEST OF k-DIMENSIONALITY FOR BOOLEAN FUNCTIONS

Abstract. A probabilistic test of k-dimensionality for Boolean functions is proposed. The test has less time complexity and is less likely to be characterized by a first kind error probability (at the same upper bound of the second kind error probability) compared to the previously known test.

Keywords: testing property of Boolean functions, probabilistic algorithm, k-dimensional function, Walsh–Hadamard transform.

FULL TEXT

Алексейчук Антон Николаевич, доктор техн. наук, профессор Института специальной связи и защиты информации Национального технического университета Украины «Киевский политехнический институт,
e-mail: lex-crypto@mail.ru.

Конюшок Сергей Николаевич, кандидат техн. наук, доцент Института специальной связи и защиты информации Национального технического университета Украины «Киевский политехнический институт»,
e-mail: 3tooth@mail.ru.