Подібні підстановки, задача Лагранжа

Date: 2015-10-07; view: 426.

Підстановки називаються подібними, або спряженими ( ), якщо існує підстановка , такий, що .

У деяких криптографічних застосуваннях виникає задача Лагранжа, яка полягає в знаходженні всіх розв'язків рівняння при заданих .

Виявляється, що розв'язок рівняння Лагранжа існує тоді і тільки тоді, коли циклові структури підстановок і співпадають.

Розв'язки можна отримати за допомогою «оператора Лагранжа» .

Нехай , Розглянемо множину всіх різних перестановок циклів, що входять до циклічного запису підстановки (включаючи цикли довжини 1). Маємо . Виписку окремого циклу можна здійснювати з довільного елемента циклу, тобто з довільним циклічним зсувом вліво, скажимо, . Нехай - довільний циклічний зсув вліво.

Тоді можна записати ще у більшій кількості варіантів. Множину цих варіантів запису у виді позначимо через .

Оператор Лагранжа задає множину розв'язків , що будуються наступним чином:

а) виписуємо одну довільну перестановку циклів з множини , під нею почергово записуемо всі перестановкі циклів з , але такі, щоб над відповідним циклом довжини з циклічного запису підстановки був розташований цикл з циклічного запису підстановки тієї ж довжини ;