- •10. Алгоритм rsa.
- •11. Алгоритмы быстрого умножения чисел
- •12. Алгоритм Тоома Кука
- •13. Алгоритм быстрого деления.
- •14. Тесты простоты. Числа Камайкла
- •15. Алгоритмы факторизации. Метод Полларда
- •16. Система Мак-Элиса
- •19. Атака на систему Мак-Элиса
- •20. Построение конечной проективной плоскости
- •21. Код для защиты от подлога
- •Алгоритм
- •24. Алгоритм Евклида
- •25. Теорема Эйлера
- •26. Китайская теорема об остатках
- •Операции
- •Алгоритм Гаусса
- •Алгоритм Гарнера
16. Система Мак-Элиса
_________________________________1
__________________________________2
17-18. Задача декодирования линейных кодов - труднорешаемая задача
19. Атака на систему Мак-Элиса
20. Построение конечной проективной плоскости
Инцидентностной структурой называется тройка множеств (P,L; I), где P ∩L = ∅, I⊂P×L.Элементымножества P и L называются точками и прямыми, соответственно, аI—отношением инцидентности. Инцидентностная структура называется конечной, если множества P и L, а, следовательно, и I являются конечными множествами.
Наиболее изученными видами инцидентностных структур являются конечные проективные
плоскости. Конечной проективной плоскостью P(2, n) порядка n называется инцидентностная
структура π = (P,L, I), удовлетворяющая следующим акcиомам:
P1 Для любых двух различных точек P и Q существует единственная прямая lтакая, чтоPIl
и Q I l.
21. Код для защиты от подлога
22. Цифровая подпись Эль-Гамаля
Подпись сообщений
Для подписи сообщения выполняются следующие операции:
Вычисляется дайджест сообщения:
Выбирается случайное число взаимно простое си вычисляется
Вычисляется число .
Подписью сообщения является пара.
Проверка подписи
Зная открытый ключ , подписьсообщенияпроверяется следующим образом:
Проверяется выполнимость условий: и. Если хотя бы одно из них не выполняется,то подпись считается неверной.
Вычисляется дайджест
Подпись считается верной, если выполняется сравнение:
23. Задача дискретного логарифмирования
Задача дискретного логарифмирования заключается в том, чтобы по данным целым ,,решить уравнение:
где и—взаимно просты (примечание: если они не взаимно просты, то описанный ниже алгоритм является некорректным; хотя, предположительно, его можно модифицировать, чтобы он по-прежнему работал).
Здесь описан алгоритм, известный как "baby-step-giant-step algorithm", предложенный Шэнксом (Shanks) в 1971 г., работающий за время за . Часто этот алгоритм просто называют алгоритмом"meet-in-the-middle" (потому что это одно из классических применений техники "meet-in-the-middle": "разделение задачи пополам").
Алгоритм
Итак, мы имеем уравнение:
где ивзаимно просты.
Преобразуем уравнение. Положим
где — это заранее выбранная константа (как её выбирать в зависимости от, мы поймём чуть позже). Иногданазывают "giant step" (поскольку увеличение его на единицу увеличиваетсразу на), а в противоположность ему— "baby step".
Очевидно, что любое (из промежутка— понятно, что такого диапазона значений будет достаточно) можно представить в такой форме, причём для этого будет достаточно значений:
Тогда уравнение принимает вид:
откуда, пользуясь тем, что ивзаимно просты, получаем:
Чтобы решить исходное уравнение, нужно найти соответствующие значения и, чтобы значения левой и правой частей совпали. Иначе говоря, надо решить уравнение:
Эта задача решается с помощью метода meet-in-the-middle следующим образом. Первая фаза алгоритма: посчитаем значения функции для всех значений аргумента, и отсортируем эти значения. Вторая фаза алгоритма: будем перебирать значение второй переменной, вычислять вторую функцию, и искать это значение среди предвычисленных значений первой функции с помощью бинарного поиска.