Мета: розглянути поняття підстановки, тотожною підстановки,
пояснити, як виконуються дії множення підстановок, знаходження зворотної підстановки,
перерахувати властивості твори підстановок,
розглянути поняття інверсії, парності-непарності підстановок
показати, як підстановки застосовуються в тайнопису
Отримав якось Фома від одного зі своїх друзів телеграму. Ця телеграма була якоюсь дивною. Ось що в ній було написано: «йажзеірпончорс Медж».
Чи зможете ви "прочитати" цей текст? Фома ж, трохи подумавши, зрозумів секрет цієї телеграми. Його запрошували в гості. Він вирішив відповісти в тому ж дусі. Склав відповідну телеграму і зашифрував її таким же способом. Вийшла запис з двох рядків:
"Приїду в суботу зустрічайте",
Після закінчення шифровки Фома захотів всю свою переписку з одним вести тільки зашифрованими текстами, змінюючи час від часу спосіб шифровки. Тому він завзято взявся за розробку методу шифрування.
Букви вихідного тексту він вирішив замінювати номерами позицій, які займають ці літери. Ось який список номерів отримав Фома для телеграми одного:
Потім він помітив, що зашифрований текст відрізняється від вихідного тільки зміненим порядком буки. Як змінюється порядок букв, легко побачити за допомогою тих же номерів позицій. Наприклад, зашифрований текст телеграми одного Фома тепер зміг представляти і вигляді списку:
Зіставлення цих двох списків дає ключ до Шиф-ровке тексту:
.
Символьна запис читається так: «1 переходить в 18». Замість неї часто використовується інший запис.
Напрямок стрілок визначає порядок шифровки тексту. Наприклад, буква, що стоїть в шіфруемоготексту в першій позиції, повинна зайняти в зашифрованому тексті 18-ю позицію.
Якщо напрямок стрілок змінити на протилежне, то та ж дворядкова таблиця буде визначати порядок розшифровки тексту. Наприклад, буква, що стоїть в зашифрованому тексті в 18-й позиції, повинна зайняти в розшифрованому тексті першу позицію.
Нарешті, якщо перший рядок буде завжди пов'язана з вихідним текстом, то відпаде необхідність у використанні стрілок. (При кодуванні вихідним текстом є шіфруемий текст, а при розшифровці - зашифрований).
Зрозумівши все це, Фома швидко записав ключ до 2-ий кодуванні своєї телеграми:
Залишилося тільки повідомити будь-яким чином цей ключ своєму другові, і таємниця листування гарантована!
Якщо ідеї Фоми ви зрозуміли, то ось вам зашифроване улюблене його вислів:
Воно зашифровано ключем:
Спробуйте-но прочитати цей вислів!
Ключ до кодуванні:
"Довіряй але перевіряй!"
Ви, ймовірно, вже здогадуєтеся, що шифрувальних ключів подібного виду можна придумати дуже багато. Кожен з них можна представити у вигляді дворядкового таблиці:
.
Тут у верхньому рядку стоять всі натуральні числа від 1 до п в зростаючому порядку. Нижня рядок виходить деякою перестановкою чисел з верхнього рядка. Вся таблиця в цілому називається підстановкою порядку п.
Розглянемо безліч, де, кожен елемент в якій представлений тільки один раз. Тоді взаємно-однозначне відображення множини на себе називається підстановкою ступеня п.
Безліч підстановок п-го ступеня позначається.
Ставлення бінарне, тому підстановки прийнято записувати у вигляді дворядної матриці, в першому рядку якої записані прообрази, а в другій - їх образи:
Якщо прообрази (аргументи) розташовані в порядку зростання (при то запис підстановки такого виду називають канонічною. Якщо аргументи не записані в порядку зростання, то, переставляючи стовпці (при цьому сама підстановка не змінюється, а змінюється лише порядок вимови відповідностей), можна верхній рядок привести до впорядкованого вигляду:
По можливості будемо користуватися саме канонічної записом. Такий запис зустрічалася, коли ми записували перестановку з п елементів. Відзначимо, що прообразом перестановки служить довільне кінцеве безліч, а прообразом підстановки - обов'язково.
Знайдемо число можливих різних підстановок ступеня п. Оскільки кожної канонічної записи підстановки еквівалентна відповідна перестановка, то число підстановок п-го ступеня дорівнює числу перестановок з п елементів, т. Е. Безліч складається з елементів.
Повернемося до Хоми. За допомогою підстановки-ключа
він зашифрував повідомлення, що складається з одного слова, і відправив його одного. Нерозшифрованими повідомлення той зашифрував ще раз, але вже за допомогою іншого ключа
Розшифруйте це повідомлення. , «Сосна»
Процес розшифровки ви можете провести значно швидше, якщо будете знати, як над підстановками виконується одна алгебраїчна операція. Ця операція називається множенням підстановок. (При бажанні ви можете назвати її по-іншому, бо вона ніяк не пов'язана зі звичайним множенням чисел).
Розглянемо на прикладі, як вона виконується. Помножимо підстановки, за допомогою яких зашифрованих повідомлень Хомі:
Процедура множення зводиться до послідовного проведення підстановок.
У першій підстановці (А): 1 → 5;
у другій підстановці (В). 5 → 1;
В результаті отримуємо: 1 → 1.
Аналогічно, з "2 → 2" і "2 → 3" слід: "2 → 3". Провівши ще три міркування такого типу, отримаємо підстановку-твір
Використовуючи підстановку АВ як шифратор, ви можете тепер в один прийом розшифрувати повідомлення Фоми "сноас". Заодно проконтролюєте себе. (ВА = «насос»)
Якщо вам буде цікаво, то можете придумати свої підстановки-шифратори повідомлень і вести таємне листування з друзями.
Займаючись розшифровкою повідомлень, ви познайомилися з алгебраїчній операцією над новими об'єктами підстановками. Якщо когось із вас зацікавили не тільки шифровки, а й самі по собі підстановки, то ви можете краще познайомитися з ними, виконавши такі завдання.
ЗАВДАННЯ 1. Знайдіть твори підстановок:
ЗАВДАННЯ 2. Знайдіть твір ВА підстановок А верб, розглянутих вище. Використовуючи підстановку ВА як шифратор, розшифруйте ще раз повідомлення "сноас". Порівняйте результат з результатом попередньої розшифровки. Після цього ви зможете сказати, чи володіє множення підстановок властивістю коммутативности.
Нехай задані дві підстановки і, причому