Aлгоритм восстановления бинарной алгебраической операции в группах больших порядков

Введение

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

Определения

Бинарная алгебраическая операция в группе вводится тaким образом, чтобы имела место аксиома ассоциативности: для любых 3-х элементов a, b, c из G выполняется равенство

a·(b·c) = (a·b)·c           (1).

Известно, что если M ={gi | i=1,m} система образующих элементов,то g представим в виде:

,  где .

Представленный метод ассоциативного перебора показывает, что имея систему образующих элементов можно восстановить всю таблицу Кэли, т.е. необходимо показать что метод ассоциативного перебора восстанавливает степени всех образующих элементов и всевозможные их произведения.

Лемма

Если в (1) определены соотношения (b·c),(a·b) и a· (b·c)= a·h,

то определено и соотношение (a· b)·c= a· (b·c).

Теорема

Если определена система образующих элементов М группы G, то используя метод ассоциативного перебора и так называемую неполную таблицу Кэли группы G можно восстановить всю таблицу Кэли группы G.

Доказательство

Возьмем любой g из M и восстановим все его степени. Для любого e (единица в группе), h из G верно следующее:

k·h = (g·g)·h = g·(g·h) = g·c = e.

Таким образом восстанавливается вторая степень g. Далее восстанавливается 3-я степень

s·h = (g·k)·h = g·(k·h) = g·r = t.

Степени восстанавливаются вплоть до единичного элемента e и соответственно всевозможные произведения данных степеней.