🤖 RSA почти никогда не делит числа по модулю напрямую

Операции с огромными числами слишком дорогие, поэтому реализации RSA используют редукцию Монтгомери.

Идея Питера Монтгомери из 1985 года:

выбирается R = 2^k
деление на R заменяется битовым сдвигом
модульные вычисления выполняются через умножения, сложения и сдвиги

За счёт этого быстрее считается:

a^e mod N

Это критично для:

шифрования и расшифровки
цифровых подписей
TLS-соединений
банковских операций

Редукция Монтгомери десятилетиями работает внутри криптографических библиотек, хотя большинство пользователей даже не знает о её существовании.