![](https://habrastorage.org/getpro/habr/post_images/ef5/61d/1af/ef561d1af305f5a6eff4c134d8eabe72.jpg)
Приготовьтесь, вас ждёт крайне педантичная статья, которая вполне может спасти вас на собеседовании или сэкономить несколько часов при вылавливании бага в продакшне!
Я сейчас активно работаю над вторым сезоном «Руководства для самозванца» и пишу о шифре RSA для SSH, который, очевидно, является самым загружаемым фрагментом кода в истории IT.
Хочется полностью разобраться в этой истории. Кто придумал этот шифр, как он работает, почему работает и будет ли работать в будущем. Сейчас я раскопал одну чертовски интересную историю. Я не криптоманьяк и вижу, как других буквально засасывает в эту область. Но мне это тоже интересно, потому что повсюду есть маленькие норки, а меня как сороку привлекают блестящие штучки в глубоких норках. Я также очень хорош в метафорах.
В любом случае: на прошлой неделе я узнал что-то странное и хочу поделиться: оказывается, mod и остаток от деления — не одно и то же. Действительно забавно то, что некоторые читатели при этих словах выпрыгивают со своих кресел и орут: «А ведь именно это я всегда пытался сказать вам и всем остальным!»
Позовите ребят из секты «mod не остаток»! Это для вас.
Что такое mod?
Я должен был изучить это, как и в прошлый раз, когда всплыла такая тема. Это одна из тех вещей, которые ты знаешь, но не запоминаешь. Когда вы применяете mod, то делите одно число на другое и берёте остаток. Итак: 5 mod 2 будет 1, потому что 5/2=2 с остатком 1.
Термин mod означает операцию modulo, с модулем 2 в данном случае. Большинство языков программирования используют
%
для обозначения такой операции: 5 % 2 = 1
. Вот где мы попадаем в странную серую область.
Математика циферблата
Помню, как учил это в школе, а потом забыл. Существует тип математики, называемый «модульной арифметикой», которая имеет дело с циклическими структурами. Самый простой способ представить это — циферблат с циклом 12. Для математика циферблат — это
mod 12
. Если хотите понять, можно ли равномерно разделить 253 часа на дни, то можете применить операцию 253 mod 24
, результатом будет 13, поэтому ответ «нет»! Мы можем ответить «да» только если результат 0.Другой вопрос, который вы можете задать: «Если я выеду в 6 вечера, сколько времени будет по приезду через 16 часов?». Это будет
6 + 16 mod 12
, то есть 10.Криптографы любят
mod
, потому что при использовании с действительно большими числами можно создать нечто, известное как «односторонние функции». Это специальные функции, которые позволяют легко вычислить что-то в одном направлении, но не в обратном.Если я скажу вам, что 9 является результатом возведения в квадрат, вы можете легко определить, что на входе было 3. Перед вами весь процесс от начала до конца. Если я скажу, что 9 является результатом
mod 29
, то будет сложнее понять, что на входе.Криптографам нравится эта идея, потому что они могут использовать деление с остатком с гигантскими простыми числами для генерации криптографических ключей. Это совсем другая история: если хотите прочитать об этом, то можете купить книгу или, ещё лучше, поддержать мои усилия написать её.
Впрочем, не будем отклоняться от темы.
Остатки и математика циферблата
Теперь переходим к сути: modulo и простой остаток одинаковы, когда числа положительны, но отличаются в случае отрицательных чисел.
Рассмотрим такую задачу:
const x = 19 % 12;
console.log(x);
Каково значение
x
? Делим числа и получаем 7 как остаток от 12. Это верный ответ. Как насчет такого:const y = 19 % -12;
console.log(y);
Используя обычную математику, мы можем умножить -12 на -1, что даёт 12, и у нас по-прежнему остаётся 7, поэтому наш ответ снова 7.
JavaScript с этим согласен:
![](https://habrastorage.org/getpro/habr/post_images/fa7/ab2/74b/fa7ab274b9a6cf591767f4d18c51824d.png)
C# тоже согласен:
![](https://habrastorage.org/getpro/habr/post_images/96f/9a1/7b2/96f9a17b2e8fbfe528143b4ae385df6e.png)
Google согласен с первым утверждением, но не согласен со вторым:
![](https://habrastorage.org/getpro/habr/post_images/1ad/8dd/54b/1ad8dd54b309a3c5c9b16c85bd2a4677.png)
Ruby согласен с Google:
![](https://habrastorage.org/getpro/habr/post_images/155/875/445/15587544547bab1a4c382f993e99bb31.png)
Во имя Дейкстры, что здесь происходит?
Вращение часов назад
Чтобы ответить на вопрос, следует понять разницу между остатком и modulo. Программисты объединяют эти операции, но не должны этого делать, потому что они дают одинаковый результат только в случае, если делитель (в нашем случае 12) положителен. Вы можете легко отправить баги в продакшн, если делитель отрицательный.
Но почему существует разница? Рассмотрим положительный делитель
19 mod 12
на часах:![](https://habrastorage.org/getpro/habr/post_images/533/366/a02/533366a02b7640b5aeb2b09679915fd8.png)
Конечный результат 7. Мы это знаем и мы можем доказать математически. Но что насчёт
19 mod -12
? Здесь нужно использовать другие часы:![](https://habrastorage.org/getpro/habr/post_images/248/5e2/d30/2485e2d309e65adb3435bf95799673e9.png)
Модуль равен -12, и мы не можем игнорировать или изменить его, умножив на -1, поскольку модульная арифметика так не работает. Единственный способ правильно рассчитать результат — переставить метки на часах так, чтобы мы двигались от -12 или вращали часы против часовой стрелки, что даёт тот же результат.
Почему не начать метки с -1, двигаясь к -2, и т.д.? Потому что в таком случае мы будем двигаться назад и постоянно уменьшать результат, пока не достигнем -12, и в этот момент сделаем прыжок +12, а modulo так не работает.
Это известная вещь
Прежде чем назвать меня сумасшедшим и начать гуглить тему: это известный факт. На самом деле MDN (Mozilla Developer Network) даже дошла до того, чтобы назвать
%
операцией «остатка» (remainder), а не modulo:Оператор remainder возвращает остаток от деления одного операнда на другой. Он всегда принимает знак делимого.
Вот что Эрик Липперт, один из богов C#, говорит о modulo в C#:
Однако это совсем не то, что оператор % реально делает в C#. Оператор % не является каноническим оператором modulus, это оператор остатка.
А как на вашем языке?
Ну и что?
Могу понять, если вы дочитали досюда, а теперь чешете голову и задаётесь вопросом, стоит ли беспокоиться. Думаю, что стоит по двум причинам:
- Я представляю, как этот вопрос займёт меня врасплох на собеседовании.
- Я представляю, как этот попадёт в продакшн, а разработчики будут несколько часов выяснять, почему математика не работает.
Это также забавный факт на случай, если рядом появится ваш педантичный друг-программист.