Перестановка и подстановка: Понятие о подстановке и перестановке. Алгебра — Математика

Перестановка | это… Что такое Перестановка?

В комбинаторике перестано́вка — это упорядоченный набор чисел обычно трактуемый как биекция на множестве , которая числу i ставит соответствие i-й элемент из набора. Число n при этом называется порядком перестановки. Как синоним слову «перестановка» в этом смысле некоторые авторы используют слово расстановка.

В теории групп под перестановкой произвольного множества подразумевается биекция этого множества на себя. Как синоним слову «перестановка» в этом смысле некоторые авторы используют слово подстановка. (Другие авторы подстановкой называют наглядный способ записи перестановки.)

Содержание 1 Свойства 2 Связанные определения 2.1 Специальные типы перестановок 2.2 Подстановки и произведения циклов 3 Перестановки с повторением 4 Случайная перестановка 5 См. также 6 Примечания 7 Литература 8 Ссылки

Свойства

• Число всех перестановок порядка равно числу размещений из n по n, то есть факториалу:^[1][2][3][4]

• Композиция определяет операцию произведения на перестановках одного порядка: Относительно этой операции множество перестановок порядка n образует группу, которую называют симметрической и обычно обозначают .
• Любая группа является подгруппой группы перестановок множества элементов этой группы (теорема Кэли). При этом каждый элемент сопоставляется с перестановкой , задаваемой тождеством где g — произвольный элемент группы G, а  — групповая операция.

Связанные определения

• Носитель перестановки  — это подмножество множества , определяемое как
• Неподвижной точкой перестановки является всякая неподвижная точка отображения , то есть элемент множества Множество всех неподвижных точек перестановки является дополнением её носителя в .
• Инверсией в перестановке порядка n называется всякая пара индексов такая, что и . Чётность числа инверсий в перестановке определяет чётность перестановки.
• Знак перестановки определяется как +1 для чётной перестановки и −1 для нечётной, что выражается формулой , где  — количество инверсий в перестановке . Знак перестановки может быть также определен как , где m — количество транспозиций в разложении в произведение транспозиций. Несмотря на то, что такое разложение не единственно, чётность количества транспозиций во всех разложениях одна и та же, и поэтому знак перестановки корректно определён.

Специальные типы перестановок

• Инволюция — перестановка которая является обратной самой себе, то есть
• Беспорядок — перестановка без неподвижных точек.
• Циклом длины называется такая подстановка которая тождественна на всём множестве кроме подмножества и Обозначается
• Транспозиция — перестановка элементов множества , которая меняет местами два элемента. Транспозиция является циклом длины 2.

Подстановки и произведения циклов

Перестановка множества может быть записана в виде подстановки, например:

где и

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

Перестановки с повторением

Рассмотрим n элементов m различных типов, причем в каждом типе все элементы одинаковы. Тогда перестановки из всех этих элементов с точностью до порядка следования однотипных элементов называются перестановками с повторением. Если k_i — количество элементов i-го типа, то и количество всевозможных перестановок с повторениями равно мультиномиальному коэффициенту

Случайная перестановка

Основная статья: Обобщённая схема размещения

Случайной перестановкой называется случайный вектор все элементы которого принимают натуральные значения от 1 до и при этом вероятность совпадения любых двух элементов равна 0.

Независимой случайной перестановкой называется такая случайная перестановка , для которой

для некоторых таких что

Если при этом не зависят от , то перестановку называют одинаково распределённой. Если же нет зависимости от , то есть то называют однородной.

См. также

• Гигантская компонента
• Сочетание
• Размещение
• Анаграмма

Примечания

1. ↑ Виленкин Н. Я. Глава III. Комбинаторика кортежей и множеств. Размещения с повторениями // Популярная комбинаторика. — М.: Наука, 1975. — С. 80. — 208 с.
2. ↑ Теория конфигураций и теория перечислений
3. ↑ Глава 3. Элементы комбинаторики. // Лекции по теории вероятностей.
4. ↑ Дональд Э. Кнут — Искусство программирования. Том 1. Основные алгоритмы. 1.2.5. Перестановки и факториалы

Литература

• Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0

Ссылки

• Аранжеман // Энциклопедический словарь Брокгауза и Ефрона: В 86 томах (82 т. и 4 доп.). — СПб., 1890—1907.

НОУ ИНТУИТ | Лекция | Подстановки, перестановки

< Лекция 9 || Лекция 10: 1234

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

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

Подстановки, перестановки

Теорема 5.0.4. Множество S(U) всех биекций

с операцией произведения (композиции) отображений gf для , , обладает следующими свойствами:

1. операция произведения ассоциативна ( h(gf)=(hg)f для всех ),
2. нейтральным элементом для этой операции является тождественное отображение 1_U ( 1_Uf=f=f1_U для всех ),
3. для всякой биекции существует обратный элемент — биекция g=f^-1 ( fg=1_U=gf ).

(Другими словами, S(U) — группа относительно операции произведения отображений; S(U) — подгруппа моноида T(U): .)

Доказательство. следует из теоремы 1.6.4 и леммы 1.8.4.

Биекции множества U часто называются подстановками . Наиболее важный для нас случай U={1,2,…,n}, в этом случае группу S_n = S({1,2,…,n}) называют группой подстановок множества {1,2,…,n} из n элементов (иногда называемой симметрической группой).

Запись подстановок. Перестановки

Если — подстановка, то рассмотрим ее каноническую запись

В нижней строчке (f(1), f(2),…, f(n)), поскольку f — биекция, встречаются все элементы i, , при этом только по одному разу. Такие строчки элементов (i₁

,…,i_n), , где каждый элемент i_j, , встречается один и только один раз, называются перестановками элементов 1,2,. ..,n .

Лемма 5.1.1. Число всех перестановок (i₁,…,i_n) из n элементов равно .

Доказательство. Для i₁ имеем n возможностей. При выбранном i₁ для i₂ имеем (n-1) возможность. Таким образом, число различных перестановок равно !.

Лемма 5.1.2. Число различных подстановок множества {1,2,…,n} равно n! (т. е. | S_n|=n!).

Доказательство. Для рассмотрим каноническую запись

Таким образом, различных подстановок столько же, сколько различных перестановок n элементов, т. е. n!.

Во многих случаях удобно рассматривать записи подстановки , располагая в верхней строчке произвольную перестановку (i₁,i₂,…,i_n):

Каждый столбец этой таблицы имеет вид

intuit.ru/2010/edi»>Пример 5.1.3

1. Для тождественной подстановки в S₂ имеем Для биекции , f(1)=2, f(2)=1, имеем
2. Если то
3. Так как , то В частности,
4. Обозначим через (i₁ i₂… i_r) цикл длины r в группе подстановок S_n: подстановку, переводящую i_k в i_k+1 для , i_r в i₁, и оставляющую все элементы из {1,2,…,n}, отличные от i₁,…,i_r, на месте. Тогда в S₃ имеем шесть подстановок: При этом в S_n для имеем следовательно, группа S₃ и любая группа S_n при некоммутативны. Так как S₁={e} и S₂={e, (1 2)} — коммутативные группы, то получаем, что группа S_n коммутативна тогда и только тогда, когда n=1 или n=2.

Дальше >>

< Лекция 9 || Лекция 10: 1234

Шифрование

— шифр замены против шифра перестановки

Шифры замены

Шифры замены заменяют единицы открытого текста единицами зашифрованного текста.

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

Например, если значение смещения равно $s = 3$, то открытый текст $caesar$ будет закодирован как зашифрованный текст $fdhvdu$.

Класс шифров, к которому принадлежит шифр Цезаря, — это моноалфавитных шифра замены .

Другим классом шифров замены являются полиалфавитные шифры замены . Шифр Виженера представляет собой простой пример, в котором значения открытого текста заменяются значениями зашифрованного текста с использованием серии шифров Цезаря, которые определяются ключевым словом. 9{88}$, упомянутые в вашем вопросе, могут быть получены из шифра Виженера с 26-символьным алфавитом и ключевым словом $k \in K$ длиной 26 символов. Вычисление составляет $26!$, что говорит нам о количестве различных конфигураций, в которых мы можем расположить 26 символов.

Это подводит нас к концепции сложности грубой силы . Сложность грубой силы — это мера вычислительных усилий, которые требуются для исчерпывающего поиска решения проблемы. Чтобы сложность грубой силы имела смысл в криптографическом контексте, необходимо, чтобы не было никаких сокращений, которые можно было бы использовать для уменьшения пространства, которое необходимо искать.

Шифр ​​Виженера обычно не соответствует этому требованию. Если длина открытого текста превышает 26 символов или одно и то же ключевое слово используется для шифрования нескольких сообщений, злоумышленник может использовать методы частотного анализа для восстановления информации о зашифрованных сообщениях.

Обе эти постройки очень старые. Теория информации Клода Шеннона и ее применение к криптографическим системам в качестве теоретико-информационной безопасности иногда приписывают преобразование криптографии из искусства в науку и являются важной основой современной криптографии.

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

Шифры с перестановкой

Шифры с перестановкой пытаются скрыть информацию от злоумышленника, перестраивая открытый текст так, чтобы его больше нельзя было распознать. Простой пример — шифр ограждения рельсов , который транспонирует открытый текст, располагая его по диагонали в несколько рельсов. На практике это очень небезопасно, так как количество рельсов невелико и может быть атаковано грубой силой.

Современные блочные шифры

Некоторые современные шифры, такие как AES , многократно применяют как подстановку, так и перестановку в раундах, применяя конструкцию, известную как сеть подстановки-перестановки (SPN). AES гораздо более безопасен, чем любой из упомянутых выше шифров, и не так уязвим для частотного анализа, как алфавитные шифры. Для лучшего понимания AES я рекомендую прочитать: Руководство по расширенному стандарту шифрования (AES) 9.Шифрование 0005

— Как работает перестановка и замена?

спросил 4 года 11 месяцев назад

Изменено 4 года, 11 месяцев назад

Просмотрено 1к раз

$\begingroup$

Я немного запутался в том, как работает перестановка и замена, я читал о S-DES и о том, как он проходит через P-блоки и S-блоки, но что происходит внутри P или S в алгоритме?

Являются ли эти поля p и B сгенерированными из ключа?

Если, например, у меня есть какой-то открытый текст 11010011011110100001 и я хочу переставить или заменить его, какой процесс я должен выполнить? — Желательно вручную, чтобы я мог понять. ..

• шифрование
• симметричное
• шифр подстановки
• перестановка

$\endgroup$

2

$\begingroup$

Здесь речь идет о диффузии и путанице, цель диффузии — распространить влияние одного бита на все биты. Задача путаницы состоит в том, чтобы скрыть взаимосвязь между входом и выходом.

S-блоки путают (преобразовывают ряды битов в разные биты), P-блоки смешивают (перетасовывают биты).

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

Предположим, что некоторые входные данные поступают в некоторое количество S-блоков. Они радикально изменились.