Модульная арифметика
Арифметика остатков, где числа «заворачиваются» по модулю, — основа почти всей классической и современной криптографии.
В арифметике по модулю 26 число 27 равно 1 — именно это использует шифр Цезаря, сдвигая буквы по алфавиту по кругу. Аффинный шифр обобщает его до ax + b mod 26, где a должно быть взаимно простым с 26, чтобы шифр был обратимым.
Тот же принцип, но с числами в сотни знаков, лежит в основе RSA. Модульное возведение в степень с большими простыми числами легко вычислить в прямом направлении, но для обратного нужен закрытый ключ, — это функция с лазейкой. То, что криптосистема держится на чём-то столь скромном, как арифметика остатков, — один из загадочных фактов этой науки.