Свойства отношений
-
Рефлексивность:.
-
Антирефлексивность
-
Симметричность:.
-
Антисимметричность:.
-
Транзитивность:.
-
Асимметричность:
18.Отношение эквивалентности.
Отношение эквивалентности (∼) на множестве X — это бинарное отношение, для которого выполнены следующие условия:
-
Рефлексивность:
для
любого a
в X, -
Симметричность: если
,
то
, -
Транзитивность: если
и
,
то
.
Запись
вида «
»
читается как «a
эквивалентно b».
Связанные определения
-
Классом эквивалентности C(a) элемента a называется подмножество элементов, эквивалентных a.
Множество всех классов эквивалентности обозначается X / ∼.
-
Для класса эквивалентности элемента a используются следующие обозначения: [a], a / ∼,
. -
Множество классов эквивалентности по отношению ∼ является разбиением множества.
19. Понятий соответствий, отображений. Свойства отображений.
Отображение
из множества
в множество
считается заданным, если каждому элементу
из
сопоставлен по правилу
ровно
один элемент
из
.
Это обозначается так:
Множество
X называется областью
определения
отображения
и обозначается
.
Свойства отображений.
-
Отображение
называют сюръективным
если
его область значений совпадает со всем
множеством
.
В
таком случае говорят, что
отображается
на
.
-
Отображение
называют инъективным
если
каждый элемент из области его значений
имеет единственный прообраз, т.е. из
следует, что
для любых
и
из
.
-
Отображение
называют биективным
если
оно одновременно инъективно и сюръективно.
21.НОД. НОК. Алгоритм Евклида. Взаимнопростые числа.
Наибольшим общим делителем для двух целых чисел m и n называется наибольший из их общих делителейНаибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не ноль.
Возможные обозначения наибольшего общего делителя чисел m и n:
-
НОД(m, n)
-
(m, n)
-
gcd(m, n)
Наименьшее общее кратное (НОК) двух целых чисел m и n — это наименьшее натуральное число, которое делится на m и n. Обозначается НОК(m,n) или [m,n],
НОК для ненулевых чисел m, n всегда существует и связан с НОД следующим соотношением:
Алгори́тм Евкли́да — алгоритм для нахождения наибольшего общего делителя двух целых чисел. Пусть a и b — целые числа, не равные одновременно нулю, и последовательность чисел
Взаимно простые числа
Числа m и n называются взаимно-простыми, если у них нет общих делителей, кроме единицы. Для таких чисел НОД(m,n) = 1. Обратно, если НОД(m,n) = 1, то числа взаимно просты.
24.Задачи теории шифрования и области ее применения. Шифры замены.
Наиболее известными и часто используемыми шифрами являются шифры замены. Они характеризуются тем, что отдельные части сообщения (буквы, слова, ...) заменяются на какие-либо другие буквы, числа, символы и т.д. При этом замена осуществляется так, чтобы потом по шифрованному сообщению можно было однозначно восстановить передаваемое сообщение.
25.Перестановочные шифры. Проблема раскрытия шифра для незаконного пользователя
Простой перестановочный шифр с фиксированным периодом n подразумевает разбиение исходного текста на блоки по n символов и использование для каждого такого блока некоторой перестановки E. Ключом такого шифра является используемая при шифровании перестановочная матрица P или вектор t, указывающий правило перестановки. Таким образом, общее число возможных ключей определяется длиной блока n и равно n!.
26.Понятие о шифросистемах с “открытым” ключом.
Криптосистема RSA
RSA – криптографическая система открытого ключа, обеспечивающая такие
механизмы защиты как шифрование и цифровая подпись (аутентификация –
установление подлинности). Криптосистема RSA разработана в 1977 году и
названа в честь ее разработчиков Ronald Rivest, Adi Shamir и Leonard
Adleman.
Алгоритм RSA работает следующим образом: берутся два достаточно больших
простых числа p и q и вычисляется их произведение n = p*q; n называется
модулем.