1.5 Подібні підстановки, задача Лагранжа
Підстановки
називаються подібними, або спряженими
(),
якщо існує підстановка,
така, що.
У деяких
криптографічних застосуваннях виникає
задача Лагранжа, яка полягає в знаходженні
всіх розв’язків рівняння
при заданих.
Виявляється,
що розв’язок рівняння Лагранжа існує
тоді і тільки тоді, коли циклові структури
підстановок
іспівпадають.
Розв’язки
можна отримати за допомогою «оператора
Лагранжа»
.
Нехай
,
Розглянемо множинувсіх різних перестановок циклів, що
входять до циклічного запису підстановки
(включаючи цикли довжини 1). Маємо.
Виписку окремого циклу можна здійснювати
з довільного елемента циклу, тобто з
довільним циклічним зсувом вліво,
скажимо,.
Нехай- довільний циклічний зсуввліво.
Тоді
можна записати
ще у більшій кількості варіантів. Множину
цих варіантів записуу видіпозначимо через.
Оператор
Лагранжа
задає множину розв’язків,
що будуються наступним чином:
а)
виписуємо одну довільну перестановку
циклів
з множини,
під нею почергово записуемо всі
перестановкі циклівз,
але такі, щоб над відповідним циклом
довжиниз циклічного запису підстановкибув розташований цикл з циклічного
запису підстановкитієї ж довжини;
б) будуємо
чергову підстановку
,
забираючи дужки з запису циклів.
в)
записуємо
у канонічному виді.
Приклад.
,,,.
Оскільки
,
то розв’язки існують.
Тут
,
тобто,
,
,,
.