Математические основы криптологии: модульная арифметика, НОД — тест

Современные шифры держатся не на хитрости, а на теории чисел: на том, что перемножить два больших простых числа легко, а разложить произведение обратно — практически невозможно. Раздел направления «Информационная безопасность» о математических основах криптологии даёт инструменты, без которых RSA и протокол Диффи — Хеллмана останутся «чёрным ящиком». Работа проверяет вычисления и понимание их смысла.

Темы

Делимость, простые и составные числа, основная теорема арифметики. Сравнения по модулю и действия с остатками, кольцо классов вычетов. Наибольший общий делитель, алгоритм Евклида и расширенный алгоритм Евклида, взаимно простые числа, обратный элемент по модулю. Функция Эйлера для простого числа и для произведения двух простых. Малая теорема Ферма и теорема Эйлера. Быстрое возведение в степень по модулю. Почему задача разложения на множители и задача дискретного логарифма считаются трудными.

Формат

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

Разбор

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

Где использовать

Работа подходит после раздела о математических основах в десятом классе и непосредственно перед темой асимметричной криптографии: каждое задание здесь — шаг, который понадобится при разборе RSA. Слабые места по результатам лучше закрыть до перехода к шифрам.

Как проходит работа

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