RUS  ENG
Полная версия
ЖУРНАЛЫ // Прикладная дискретная математика. Приложение // Архив

ПДМ. Приложение, 2021, выпуск 14, страницы 187–190 (Mi pdma563)

Вычислительные методы в дискретной математике

DPLL-подобный решатель задачи выполнимости над системой уравнений в АНФ

А. В. Ткачевa, К. В. Калгинab

a Новосибирский государственный университет, г. Новосибирск
b Институт вычислительной математики и математической геофизики СО РАН, г. Новосибирск

Аннотация: Описаны SAT-решатель, использующий системы булевых уравнений в алгебраической нормальной форме (АНФ) для внутреннего представления задачи, и особенности реализации типичных для SAT-решателей методик для работы с таким представлением. Приводится сравнение данного решателя с рядом классических SAT-решателей при решении некоторых задач криптоанализа (как, например, атака «guess-and-determine» на потоковый шифр Grain).

Ключевые слова: SAT-решатель, АНФ, криптоанализ, потоковые шифры.

УДК: 004.4

DOI: 10.17223/2226308X/14/44



© МИАН, 2024