Шептунов М. В. - Теория множеств (1023559), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

a b c a b c

     

а) б)

Рис. 2.4. Геометрическое представление прямого (а) и обратного (б)

соответствий

2.4. Отображения

Рассмотрим два множества X и Y.

Определение 2.13. Если бинарное отношение R между двумя

множествами X и Y является всюду определённым соответствием, т. е. каждому элементу x соответствует элемент y, то имеет место отображение X в Y. Это записывается в виде:

Другая форма записи:

.

Из данного определения очевидно, что отображение является частным случаем соответствия.

Пример 2.7. Если в примере 2.6 исключить из рассмотрения шофёра c и грузовик  и пересадить шофёра b на автобус  вместо шофёра a, то получим отображение

,

в котором X={a, b} – множество шоферов,

Y={, } – множество автомашин,

f={(a, ), (b, )} – распределение шоферов по автомашинам (см. рис. 2.5).

a b

 

Рис. 2.5. Геометрическое представление отображения

Определение 2.14. Отображение множества X на само себя, т. е.

называется перестановкой множества X.

2.5. Взаимосвязь понятий “отношение”, “соответствие”, “отображение”

Взаимосвязь понятий “отношение”, “соответствие” и “отображение”

показана на рис. 2.6.

Отношения

Соответствия

Функции

Унарное

n-местное

Бинарное

Не всюду

определённое

Всюду

определённое

Полная (отображение)

Частичная

Рис. 2.6. Взаимосвязь понятий “отношение”, “соответствие”,

“отображение”

2.6. Функции

2.6.1. Понятие функции

Определение 2.15. Функцией (полной) называется отображение

f: X Y,

причём область определения данной функции совпадает с множеством X.

Определение 2.16. Функции, не являющиеся отображениями, но являющиеся не всюду определёнными соответствиями, называются частичными.

Рассмотрим некоторые наиболее общие свойства функций, не касаясь свойств конкретных классов функций.

Пример 2.8. Из данного города в другой можно добраться по железной дороге, автобусом либо самолётом. Стоимость билета соответственно пусть будет 19, 5 и 90 руб.

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

X={ж/д, авт., сам.};

Y={19, 5, 90}.

Функция

f: X Y,

получаемая из условий примера, может быть записана в виде множества:

f={(ж/д, 19), (авт., 5), (сам., 90)}.

Таким образом, символ f используется при определении функции в двух смыслах:

1) f является множеством, элементами которого являются пары (x, y), участвующие в соответствии;

2) f(x) является обозначением для , соответствующего данному .

Существуют 3 способа задания функции: табличный, аналитический

и графический.

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

Формальное определение функции записывается в виде:

}.

С понятием функции связано ещё одно понятие, называемое

сужением функции.

Определение 2.17. Пусть f: X Y – произвольная функция и – произвольное множество. Сужением функции f на множество A называется функция f_A, содержащая все те и только те пары ,

в которых , а значит, . Следовательно,

.

По указанному принципу построены таблицы логарифмов,

тригонометрических функций и некоторых других.

2.6.2. Инъективная, сюръективная и биективная функции

Пусть имеет место функция f: X  Y.

Определение 2.18. Функция называется инъективной, если

 .

Определение 2.19. Функция называется сюръективной, если

, где y=f(x).

Определение 2.20. Функция f называется биективной (или, что то же самое, взаимнооднозначной), если она одновременно является

инъективной и сюръективной.

X Y X Y X Y

x₁

x₂

a) б) в)

Рис. 2.7. Функции: a) инъективная, но не сюръективная;

б) сюръективная, но не инъективная;

в) биективная.

2.6.3. Обратная функция

Понятие обратной функции применимо лишь для полных функций (т. е. обязательно являющихся отображениями).

Определение 2.21. Функцией, обратной по отношению к функции

, называется функция

,

определяемая обратным отображением .

При аналитическом способе задания функции f принято аргумент и прямой, и обратной функции обозначать одной и той же буквой, например, x. Поэтому для нахождения обратной функции следует уравнение разрешить относительно x и затем x и y обменять

местами. При этом обратная функция запишется в виде

.

2.6.4. Понятие функционала

Важным для теории и практики является случай, когда множество X представляет собой множество функций, а множество Y – множество вещественных чисел. Этот случай приводит к понятию функционала.

Представим себе некоторую линию y=f(x), соединяющую точки A и B (рис. 2.8), по которой свободно скатывается шарик. Обозначим через t время, необходимое шарику для перемещения из т. A в т. B. Это время зависит от характера линии AB, т. е. от вида функции f(x).

y

A

f(x)

B

x Рис. 2.8. К понятию функционала

Обозначим далее через F(x) множество возможных траекторий движения шарика, а через T обозначим множество вещественных чисел t, определяющих время движения шарика. Тогда зависимость времени t движения шарика от вида функции f(x) может быть записана в виде бинарного отношения

,

где , причём ; .

Если же  – не только бинарное отношение, но и функция, то

будет функционалом, где  – функция от f(x); t – функционал.

2.7. Понятия о неразрешимых вычислительных проблемах

Под вычислительно сложными задачами (трудно решаемыми задачами) понимаются задачи, заведомо имеющие решение, но требующие для его нахождения выполнения чрезвычайно большого числа операций вычислителя (ЭВМ).

Другими словами, использование всех вычислительных устройств, которые могут быть вовлечены в единый вычислительный процесс, не позволит найти решение с существенной вероятностью (например, 0,01) за обозримое время (десятилетия, столетия и т. д.).

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

Проблема оценки сложности заключается в том, что значение сложности зависит от алгоритма поиска решения. Для разных алгоритмов в общем случае получаются различные значения сложности. Для конкретной трудно решаемой задачи доказательство того, что найден алгоритм с минимальной трудоёмкостью (т. е. наилучший), является нетривиальным.

Определение 2.22. Условно стойкими называют шифры, вероятность отыскания решения которых криптоаналитиком с ограниченными вычислительными ресурсами чрезвычайно мала (за время, в течение которого информация имеет ценность).

Стойкость этих шифров целиком основана на высокой вычислительной сложности решения конкретной криптоаналитической задачи.

Цель разработчика упомянутых условно стойких криптосистем

состоит в задании столь высокого уровня сложности этой задачи, что

для её решения требовались бы затраты экономически невыгодные.

Определение 2.23. Вычислительно стойкими называют шифры,

нахождение решения которых является вычислительно нереализуемым.

Наибольшее распространение получили именно вычислительно стойкие криптосистемы.

Под стойкостью криптосистем такого типа понимается сложность решения криптоаналитической задачи в определённых условиях.

Американский учёный К. Шеннон ввёл понятие рабочей характеристики шифра, что обычно обозначается как W(n). Это есть среднее количество работы по нахождению ключа по известным n знакам криптограммы при использовании наилучшего алгоритма криптоанализа.

Количество работы может быть измерено, например, количеством операций, которое необходимо выполнить для вычисления ключа шифрования.

Определение 2.24. Ключ шифрования – это конкретное секретное состояние некоторых параметров алгоритма шифрования (криптографического преобразования) данных, обеспечивающее выбор только одного варианта из всех возможных для данного алгоритма.

Такой параметр, как среднее количество работы W(n) по нахождению ключа, непосредственно связан с алгоритмом вычисления ключа. Сложность же определения величины W(n) связана со сложностью отыскания лучшего способа раскрытия. Особый интерес представляет значение W(n) при .

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

достигнутой оценкой рабочей характеристики , которую получают

для наилучшего из известных методов вычисления ключа.

Существуют также криптосистемы другого типа, являющиеся безусловно стойкими (по Шеннону совершенно секретными).

Определение 2.25. Безусловно стойкими называют шифры, для которых криптоаналитик даже с бесконечными вычислительными ресурсами не может улучшить оценку исходного сообщения M на основе знания криптограммы C, по сравнению с оценкой при

неизвестной криптограмме.

2.7. Однонаправленные функции

Существуют два весьма важных математических понятия, часто применяемых в криптографии. Таковыми являются однонаправленная функция и однонаправленная функция с “потайным ходом” (другое название – “односторонняя функция с “лазейкой””).

Рассмотрим произвольные множества X и Y, а также некоторую функцию

Характеристики

Список файлов книги