Документ Microsoft Word (1014230)

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

Сохранение структуры множества при отображении (преобразовании) означает, что если a1 отображается в b1, а а2 - в b2, то результат a3 их "сложения" или "умножения" отображается в элемент b3 - результат соответствующей операции над b1 и b2. Выделим подмножество A_I, составленное из произвольно выбранных элементов a_i, и подмножество А_R, составленное из результатов операции над любой парой a_i. Пусть множество A_I отображается в множество B_I,. Тогда результат операции над любыми двумя элементами подмножества B_I будет принадлежать множеству B_R, которое является отображением множества А_R.
Понятие морфизмов полезно при поиске способов упрощенного в вычислительном отношении способа выполнения операций в множестве прообразов. Простейший пример - забытая ныне логарифмическая линейка, где операции умножения и деления заменяются операциями сложения и вычитания, которые реализуются перемещением "движка" (подвижной шкалы) вправо и влево относительно неподвижной шкалы. Для этого оцифрованные деления шкал нанесены в логарифмическом масштабе.
Пример из радиотехники - вычисление отклика фильтра на входной сигнал. Выходной сигнал - это свертка входного сигнала с импульсной характеристикой фильтра. При длинных сигналах и импульсных характеристиках фильтра проще вычислить, используя алгоритм БПФ, спектр сигнала и преобразование Фурье от импульсной характеристики, затем перемножить результаты и взять обратное БПФ от произведения, вернувшись тем самым в пространство прообразов - сигналов.
При формировании и проверке цифровой подписи используются свойства эквивалентности результатов решения линейного уравнения (в конечном поле) в множестве прообразов и операции умножения чисел (старый стандарт) или сложения точек эллиптической кривой (новый стандарт) в множестве образов.
Понятия разновидностей морфизма (мономорфизм, эпиморфизм и т.д.) вводятся для выяснения однозначности прямого и обратного отображения и оценки сложности подбора элементов исходного множества при известных значениях в множестве образов. Эта сложность определяет стойкость криптографического алгоритма по отношению к простому перебору.

Что такое самосинхронизация процесса расшифровки?

Самосинхронизация - способность алгоритма возобновить правильную расшифровку передаваемого сообщения после пропадания в канале передачи одного или нескольких символов или после ошибочного разделения одного переданного символа на два.

Как следует понимать операцию умножения точки эллиптической кривой на число?

Скалярное умножение точки P эллиптической кривой на целое число n
при n > 0 есть ее n-кратное суммирование P+P+...+P,
при n = 0 результатом умножения 0*P считается точка на бесконечности,
при n < 0 произведение есть -(-n)*P.

Что нужно знать при ответе на вопрос о генерации простых чисел?

Генерация простых чисел осуществляется путем генерации целых пседослучайных чисел и последующей проверки числа на простоту. Таким образом, нужно знать, как генерируются целые псевдослучайные числа, например, с помощью линейных и нелинейных конгруэнтных генераторов. Далее нужно знать функцию распределения простых чисел, чтобы оценить среднее количество повторений генерации до того, как попадется простое число в заданном диапазоне. И, наконец, - один из алгоритмов проверки числа на простоту, например тест Миллера-Рабина.

Что такое сбалансированные отображения?

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

Что такое делители нуля?

Если в некотором кольце, например в кольце вычетов по модулю составного числа (15), произведение двух ненулевых элементов x и y равно 0, то они называются делителями нуля: 3*5 mod 15 = 0.

Как следует давать определения морфизмам?

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

Где можно найти ответы на вопросы со 2 по 6 ?

Вопросы со 2 по 6 рассчитаны ваше на знакомство с основополагающей работой Клода Шеннона "Теория связи в секретных системах".
Истории криптологии и историческим шифрам были посвящены первые две лекции нашего курса. Этот вопрос рассматривается практически в любой книге по криптографии, в том числе и у Фомичева. В статье Шенонна этим разделам посвящен параграф 4. Примеры секретных систем (с. 9-12).
На вопрос 3 отвечает параграф 6. Алгебра секретных систем. (с. 13-15) работы Шеннона.
На вопрос 4 отвечает параграф 7. Чистые и смешанные шифры. (с. 15-19).
На вопрос 5 отвечает параграф 10. Совершенная секретность. (с. 21-24).
Вопросу 6 соответствуют параграфы: 11. Ненадежность, 12. Свойства ненадежности. 17. Идеальные секретные системы и 18. Примеры идеальных секретных систем.(с. 27-30, 36, 37).

Как доказать, что простых чисел бесконечно много (вопрос 39)?

Докажем теорему Евклида о бесконечности количества простых чисел.
Пусть нам известны простые числа p₁, p₂, ... p_k. Найдем их произведение и добавим 1.
Тогда число p = p₁· p₂· ... p_k+1 будет либо простым, либо будет иметь неизвестный нам простой делитель, отличный от p₁, p₂, ... p_k, поскольку при делении p на любое из чисел p₁, p₂, ... p_k в остатке окажется 1.

В чем смысл алгоритмов Евклида для нахождения НОД и числа обратного данному по модулю другого числа (вопрос 42)?

• Пояснения к программе, реализующей поиск НОД

• Пояснения к программе обобщенного алгоритма Евклида для решения уравнения
  вида a*u + b*v = НОД, где при НОД = 1 число a = 1/u mod v.

Что такое мультиграф, и как доказать теорему о существовании эйлерова цикла?

• Некоторые определения, относящиеся к графам, и теорема о существовании эйлерова цикла.

Как доказать теорему Эйлера (вопросы 33 и 40)?

• Доказательство теоремы Эйлера

Каким образом отношение эквивалентности разбивает множество на подмножества (вопрос 14)?

Отношение эквивалентности определяет подмножество H множества G, все элементы которого эквивалентны в определенном смысле. Например, сравнимы по модулю m, или являются элементами циклической подгруппы {h = a^k mod m, k = 1,2,3...} группы вычетов по модулю m
(см. на сайте материал по первообразным корням ). Класс эквивалентности образуют сообщения, принадлежащие одному остаточному классу сообщений по определению Шеннона (см. Теория связи в секретных системах, с.16). На примере последних хорошо видно, что множество сообщений распадается на классы и является их объединением. Множество этих остаточных классов и есть фактор-множество по отношению к операции шифрования - расшифрования любой комбинацией ключей Ki-Kj.

Почему число неупорядоченных подмножеств мощности m множества мощности n в m! раз меньше, чем упорядоченных подмножеств такой же мощности?

Каждый элемент неупорядоченного подмножества {a₁, a₂,... a_m}, мощности m, составленный из элементов множества {a₁, a₂,... a_n} мощности n > m, представляет собой объединение m! элементов, являющихся перестановками элементов a₁, a₂,... a_m.

Что такое инволюция, и когда f · f(x) = x?

• О инволюциях и произведении преобразований. Примеры инволюций