W algorytmie szyfrowania AES jednym z kroków jest przekształcenie
liniowe nad ciałem GF(2). Przekształcenie to można przedstawić jako
zestaw formuł logicznych, na ogół na wiele sposobów. Im krótsze są to
formuły, tym łatwiej solverowi programowania logicznego złamać szyfr. W
szczególnym przypadku (tzn. straight line program) problem zestawu
najkrótszych formuł jest problemem NP-Zupełnym [1]. Ponadto przedstawię
uogólnienie tego problemu oraz kombinatorykę, która się w nim kryje.
[1] Boyar, J., Matthews, P. & Peralta, R.:
Logic Minimization Techniques
with Applications to Cryptology
J. Cryptol. 26 (2013), 280-312.
https://doi.org/10.1007/s00145-012-9124-7