Об одном алгоритме проверки существования подквазигрупп

Чебышевский сборник. 2021. Т. 22. № 2. С. 76–89.

Галатенко А. В., Панкратьев А. Е., Староверов В. М., Староверов В. М.

Криптографические алгоритмы на основе квазигрупп активно изучаются в рамках перспективных исследований; кроме того, в последние годы регулярно появляются квази-
групповые алгоритмы-кандидаты на конкурсах криптографических стандартов. С точки зрения обеспечения стойкости одним из желательных требований, предъявляемых к квазигруппам, является отсутствие подквазигрупп (в противном случае преобразование
может вырождаться). В работе предлагаются оптимизированные по временной сложности
(за счет увеличения пространственной сложности) алгоритмы проверки наличия подквазигрупп и подквазигрупп порядка не меньше 2 в квазигруппах, заданных таблицей Кэли.
Доказываются утверждения о сложности в худшем случае, а также приводятся оценки эффективности программной реализации на квазигруппах большого порядка. Результа-
ты работы были анонсированы в рамках доклада на XVIII Международной конференции «Алгебра, теория чисел и дискретная геометрия: современные проблемы, приложения и проблемы истории».

Ключевые слова: quasigroup, subquasigroup, квазигруппа, подквазигруппа, Cayley table, таблица Кэли