Fast Bitwise Implementation of the Algebraic Normal Form Transform


Бакоев, Валентин (2017) Fast Bitwise Implementation of the Algebraic Normal Form Transform Serdica Journal of Computing 11 (2017), No 1, pp. 45-57. ISSN 1314-7897 – Online, ISSN 1312-6555 – Print; http://serdica-comp.math.bas.bg/index.php/serdicajcomputing/article/view/304


 The representation of Boolean functions by their algebraic normal forms (ANFs) is very important for cryptography, coding theory and other scientific areas. The ANFs are used in computing the algebraic degree of S-boxes, some other cryptographic criteria and parameters of error-correcting codes. Their applications require these criteria and parameters to be computed by fast algorithms. Hence the corresponding ANFs should also be obtained by fast algorithms. Here we continue our previous work on fast computing of the ANFs of Boolean functions. We represent and investigate the full version of bitwise implementation of the ANF transform. When we use a bitwise representation of Boolean functions in 64-bits computer words, we obtain a time-complexity $\Theta((n+44).2^{n-7})$ and $\Theta(2^{n-6})$ space complexity. The experimental results show that this implementation is more than 25 times faster in comparison to the well-known byte-wise ANF transform.
  Статия
 Boolean function, algebraic normal form transform, M\"obius (Moebius) transform, Zhegalkin transform, positive polarity Reed-Muller transform, bitwise implementation


Природни науки, математика и информатика
Природни науки, математика и информатика Информатика и компютърни науки

Natural sciences, mathematics and informatics
Natural sciences, mathematics and informatics Informatics and Computer Science

 Издадено
  20213
 Валентин Бакоев

Научният архив поддържа инициативата за отворен достъп OAI 2.0 с начален адрес: http://da.uni-vt.bg/oai2/