Предположим, что даны таблица умножения конечной группы и некоторая перестановка её элементов. Нужно проверить, является ли эта перестановка автоморфизмом.
По определению, необходимо проверить
где уже дано по условию, что
— биекция. То есть технически для проверки требуется два вложенных цикла, чтобы прогнать это соотношение по всем возможным парам элементов.
Мой вопрос: можно ли это сделать более эффективно?
То есть сделать меньше проверок. Одна очевидная оптимизация заключается в том, что надо проверить, что нейтральный элемент отображается в нейтральный, а из остальных проверок его можно исключить, потому что это будут обычные тождества вида
. Но меня интересует более серьёзная оптимизация. Например, пусть известны (или посчитаны заранее) порождающие элементы данной группы. Их количество будет не более
. Можно ли воспользоваться ими и проверить только верность соотношений только для пар образующая-произвольный элемент? Тогда сложность операции упадёт с
до всего лишь
, что будет вполне достаточно для моих целей. Можно ли будет улучшить это дальше проверяя только пары образующая-образующая?
- переставьте 
и 
.
есть образующие группы. Пусть элемент 
И пусть мы проверили все равенства 
Тогда 
То есть мы отщепляем с конца по одной образующей до тех пор, пока не "освободится" первый множитель, а потом уже собираем назад второй множитель, но без первого. В результате получается искомое тождество.