Современная криптография стоит на теории чисел: остатки, НОД, обратные элементы и быстрая степень. Именно трудность некоторых задач — разложения на множители и дискретного логарифма — делает шифры стойкими.
Что нужно знать
- Основная теорема арифметики: разложение на простые множители единственно.
- $a \equiv b \pmod{m}$, если $a$ и $b$ дают одинаковый остаток; с остатками можно складывать и умножать.
- Алгоритм Евклида: $\gcd(a, b) = \gcd(b, a \bmod b)$; расширенный находит $x$: $ax \equiv 1 \pmod m$ — обратный элемент (существует при $\gcd(a, m) = 1$).
- Функция Эйлера: $\varphi(p) = p - 1$, $\varphi(pq) = (p-1)(q-1)$.
- Малая теорема Ферма: $a^{p-1} \equiv 1 \pmod p$; теорема Эйлера: $a^{\varphi(m)} \equiv 1 \pmod m$.
- Быстрое возведение в степень: квадрирование и умножение по битам показателя — $O(\log n)$ умножений.
- Трудные задачи: разложение больших чисел на множители (RSA), дискретный логарифм (Диффи — Хеллман).
Где чаще всего ошибаются
- Искать обратный элемент при $\gcd(a, m) \ne 1$.
- Считать $\varphi(pq) = pq - 1$.
- Возводить в большую степень «в лоб» без взятия остатка на каждом шаге.
Проверить себя
По этой же теме курса есть проверочная работа из 15 заданий на 30 минут. Проверка автоматическая, результат виден сразу — и по работе целиком, и по каждой теме.
Информационная безопасность · 10–11 классы · Математические основы криптологии