О ВЫЧИСЛЕНИИ СИСТЕМЫ ПЕРЕПИСЫВАЮЩИХ ПРАВИЛ В КОНЕЧНОЙ ГРУППЕ

В формуле (6) содержится порядка 23n дизъюнкций длины 3 и п. На основе полученных формул генерируется входной файл для SAT-решателя. Формулы можно также использовать для тестирования работы новых SAT-решателей, созданных для криптографических задач.

ЛИТЕРАТУРА

1. Огородников Ю. Ю. Комбинированная атака на алгоритм RSA с использованием SAT-подхода // Динамика систем, механизмов и машин. Омск: ОмГТУ, 2016. С. 276-284.

2. Заикин О. С., Отпущенников И. В., Семёнов А. А. Оценки стойкости шифров семейства Trivium к криптоанализу на основе алгоритмов решения проблемы булевой выполнимости // Прикладная дискретная математика. Приложение. 2016. №9. С. 46-48.

3. Schmittner S. E. A SAT-based Public Key Cryptography Scheme. IACR Cryptol. ePrint Arch. 2015. https://eprint.iacr.org/2015/771.pdf.

4. Wille R., Lye A., and Niemann P. Checking reversibility of Boolean functions // LNCS. 2016. V. 9720. P. 322-337.

УДК 519.688 DOI 10.17223/2226308X/13/39

О ВЫЧИСЛЕНИИ СИСТЕМЫ ПЕРЕПИСЫВАЮЩИХ ПРАВИЛ

В КОНЕЧНОЙ ГРУППЕ

А. А. Кузнецов

Представлен алгоритм, определяющий переписывающую систему конечной группы, заданной фиксированным порождающим множеством. Необходимым условием эффективной реализации алгоритма является наличие быстрой процедуры умножения элементов в группе. Такой групповой операцией может быть композиция подстановок, умножение матриц, вычисление полиномов Холла и т.д. Алгоритм был применён для исследования переписывающих систем в конечных дву-порождённых группах периода 5.

Ключевые слова: система переписывающих правил, группа Бернсайда.

Решение некоторых задач теории кодирования и криптографии сводится к исследованию подходящих графов Кэли, например открытая проблема эффективного восстановления вершин в графе Хэмминга [1].

Поиск кратчайших путей в графах Кэли является труднорешаемой проблемой, поэтому исследователям приходится идти на различные уловки и приёмы, чтобы получить решение за приемлемое время. Например, в [2] сначала определяют автоматическую структуру группы, которая порождает соответствующий граф Кэли. Автоматическая структура группы состоит из конечных автоматов специального вида [3]. Для их вычисления требуется определить множество соотношений в группе, используя известный алгоритм Кнута — Бендикса [4].

Зачастую алгоритм Кнута — Бендикса работает недопустимо долго, например в конечных группах, заданных коммутаторными соотношениями. В этом случае разворачивание коммутаторных соотношений приводит к очень длинным словам, что катастрофически замедляет работу алгоритма.

Настоящая работа представляет собой попытку устранить указанный недостаток. Остановимся подробнее на основных определениях.

Пусть G = {X) — конечная группа, порождённая упорядоченным множеством X = {x1 — x2 — ... — xm}, которое также называют алфавитом. Множество всех

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

133

слов (строк) над алфавитом X будем обозначать X*. Пусть т = Х\Х2 ... х — слово над X и |т| = I —его длина. На множестве X* также определим отношение порядка. Пусть V и т — два произвольных слова в алфавите X. Тогда V — т, если |V| < |т|, а в случае равенства длин меньшее слово определяется согласно введённому лексикографическому порядку на порождающих. Если необходимо подчеркнуть, что строка V Е X* соответствует элементу д Е С, то будем писать vg. Строку V будем называть минимальным словом элемента д, если для всех других т Е X*, таких, что ^ = тд, выполняется V — т. Очевидно, что каждому д Е С соответствует уникальное минимальное слово. Единице группы е соответствует пустое слово е: |е| = 0.

Пусть Я — система переписывающих правил (переписывающая система), состоящая из множества пар вида (и^), где ид = ьд и и У V [4]. При этом слово и называют левой стороной правила, а строку V — правой. Иногда правила записывают в виде и ^ V. Действие системы Я над некоторым словом т означает осуществление замен вида хиу ^ х^ до тех пор, пока не будет получено несократимое относительно Я слово т', т. е. Я(т) = иЛ

Если изменение порядка применения правил не влияет на конечный результат, то Я называют конфлюэнтной.

Переписывающую систему Я называют несократимой, если для любой пары (и, V) Е Я выполняется Я'(и) = и и Я'^) = V, где Я' = Я \ {(и, V)}.

Алгоритм 1 определяет переписывающую систему конечной группы С = (X, о). Необходимым условием эффективной реализации алгоритма является наличие быстрой процедуры умножения элементов в группе. Например, групповой операцией о может быть композиция подстановок, умножение матриц, вычисление полиномов Холла и т. д.

Алгоритм 1. Я = RewritingSystem

Вход: С = (X, о).

Выход: система переписывающих правил Я группы С. 1: Р0 := {е} —множество минимальных слов.

2: К0 := {(е, е)} — словарь вида (элемент группы, его минимальное слово). 3: Я := 0.

4: Для всех г = 1, 2,... , то:

5: К := К;_ь Р := 0. 6: Для всех х Е X и р Е Рг-1: 7: и := хр — конкатенация слов, 8: д := х о р — групповое умножение. 9: Если д Е К^, то

10: если Я(и) = и, то V := Кг[д], добавить (и, V) в Я,

11: иначе

12: добавить и в Рг, добавить (д,и) в К8.

13: Если Рг = 0, то 14: Вернуть Я.

Теорема 1. Пусть Я — система переписывающих правил, полученная при помощи алгоритма 1, тогда Я конфлюэнтна и несократима.

Рассмотрим примеры. Пусть Во(2,5) = (01,02) —наибольшая конечная двупо-рождённая бернсайдова группа периода 5, порядок которой равен 534 [5]. Для каж-

дого элемента данной группы существует уникальное коммутаторное представление вида а^1  а22  •••  аОз34, где а € Ъ5, I = 1, 2,..., 34. Здесь а1 и а2 —порождающие элементы В0 (2, 5), а3,...,а34 — коммутаторы, которые вычисляются рекурсивно через а1 и а2. Определим фактор-группу группы В0(2,5) следующего вида: Вк = Во(2, 5)/{ак+1,... ,аэ4). Очевидно, что |Вк| = 5к.

Пусть Як — переписывающая система группы В к. На рис. 1 представлены графики роста Як для минимального порождающего множества X = (а1,а2), а также симметричного У = (а1,а2, а-1, а-1).

се' '

О-1-1-1-1-1-

2 4 6 8 10 12 14

к

Рис. 1. Графики роста соотношений в Бк ЛИТЕРАТУРА

1. Константинова Е. В. Комбинаторные задачи на графах Кэли. Новосибирск: НГУ, 2010. 110с.

2. Camelo M., Papadimitriou D., Fabrega L., and Vila P. Efficient routing in Data Center with underlying Cayley graph // Proc. 5th Workshop Complex Networks CompleNet. 2014. P. 189197.

3. Epstein D., Paterson M., Cannon J., et al. Word Processing in Groups. Boston: Jones and Barlett Publ., 1992. 330 p.

4. Sims C. Computation with Finitely Presented Groups. Cambridge: Cambridge University Press, 1994. 628 p.

5. Havas G., Wall G., and Wamsley J. The two generator restricted Burnside group of exponent five // Bull. Austral. Math. Soc. 1974. No. 10. P. 459-470.