Mod и остаток — не одно и то же
Приготовьтесь, вас ждёт крайне педантичная статья, которая вполне может спасти вас на собеседовании или сэкономить несколько часов при вылавливании бага в продакшне!
Я сейчас активно работаю над вторым сезоном «Руководства для самозванца» и пишу о шифре 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 и простой остаток одинаковы, когда числа положительны, но отличаются в случае отрицательных чисел.
Рассмотрим такую задачу:
Каково значение x ? Делим числа и получаем 7 как остаток от 12. Это верный ответ. Как насчет такого:
Используя обычную математику, мы можем умножить -12 на -1, что даёт 12, и у нас по-прежнему остаётся 7, поэтому наш ответ снова 7.
JavaScript с этим согласен:
C# тоже согласен:
Google согласен с первым утверждением, но не согласен со вторым:
Ruby согласен с Google:
Во имя Дейкстры, что здесь происходит?
Вращение часов назад
Чтобы ответить на вопрос, следует понять разницу между остатком и modulo. Программисты объединяют эти операции, но не должны этого делать, потому что они дают одинаковый результат только в случае, если делитель (в нашем случае 12) положителен. Вы можете легко отправить баги в продакшн, если делитель отрицательный.
Но почему существует разница? Рассмотрим положительный делитель 19 mod 12 на часах:
Конечный результат 7. Мы это знаем и мы можем доказать математически. Но что насчёт 19 mod -12 ? Здесь нужно использовать другие часы:
Модуль равен -12, и мы не можем игнорировать или изменить его, умножив на -1, поскольку модульная арифметика так не работает. Единственный способ правильно рассчитать результат — переставить метки на часах так, чтобы мы двигались от -12 или вращали часы против часовой стрелки, что даёт тот же результат.
Почему не начать метки с -1, двигаясь к -2, и т.д.? Потому что в таком случае мы будем двигаться назад и постоянно уменьшать результат, пока не достигнем -12, и в этот момент сделаем прыжок +12, а modulo так не работает.
Это известная вещь
Прежде чем назвать меня сумасшедшим и начать гуглить тему: это известный факт. На самом деле MDN (Mozilla Developer Network) даже дошла до того, чтобы назвать % операцией «остатка» (remainder), а не modulo:
Вот что Эрик Липперт, один из богов C#, говорит о modulo в C#:
А как на вашем языке?
Ну и что?
Могу понять, если вы дочитали досюда, а теперь чешете голову и задаётесь вопросом, стоит ли беспокоиться. Думаю, что стоит по двум причинам:
Intro to Modular Arithmetic
This article is useless, wanna know why? Because you already know how to do modular arithmetic even if you’ve never heard of it before. In fact, I bet you use it all the time.
Let me show you.
The Old-Fashioned Way
First I want you to go back…way, way, waaaaaay back to when you very first learned long-hand division. Now I bet your primary school teacher didn’t walk in and say “hey kiddos, today I’m going to show you how long division is also modular arithmetic,” but it’s the truth.
Let’s start with a simple problem.
To solve this problem all you need to do is divide 11 by 4 the old-fashioned way.
Remember how your teacher used to have you write “R3” at the top for “remainder 3." Later on you learned more sophisticated ways of expressing that extra amount like decimals and fractions, but for modular arithmetic that little ole remainder guy is exactly what we want.
Yep, A mod B is the same as saying “how much is left over when you divide A by B.”
That’s all there is to it! Simple right?
Modulus Time
See that clock on the wall?
It’s modulus 12.
Why? Because the standard method for telling time is to split the day into two 12 hour segments. Instead of counting up to 24, we count to 12 twice.
In fact, circular counting is a fundamental representation of modular arithmetic.
Furthermore when you convert between military time and standard time, you’re performing modular arithmetic. For example, we know that 15:00 is the same as 3:00pm because when we divide 15 by 12, we’re left with 3 as a remainder.
So let me posit this: what time would it be right now in a universe that used modulus 8 in their time system?
As I’m writing this it’s 10pm. In a universe that uses modulus 8, the time would be 6 o’clock.
(solution: 10pm is the 22nd hour of the day. So we take 22 mod 8. Eight of course goes into 22 twice with a remainder of 6. That means 22 mod 8 = 6.)
Equivalence Classes
Now your probably thinking that modular arithmetic is kinda useless because you keep getting the same answers over and over again.
You’re right! In fact that’s the beauty of modular arithmetic. It gives us a new way to relate numbers to one another.
Let’s represent modulus 4 with the following circle diagram.
Recall that when you divide by 4, you have 4 possible remainders: 0 (aka no remainder), 1, 2, and 3.
Let’s calculate 0, 1, 2 and 3 mod 4:
Place the numbers in their respective sections of the modulus 4 diagram.
And continue calculating:
Add these numbers to the diagram:
Each of these sections represents an equivalence class.
For example we could say:
Since 1 and 5 are in the same equivalence class (i.e. they both have a remainder of 1 when divided by 4) they’re congruent.
Furthermore, we can write formulas for each equivalence class of modulus 4:
- Values in the “0” equivalence class are multiples of 4 → 4x
- Values in the “1” equivalence class are multiples of 4 plus 1 → 4x + 1
- Values in the “2” equivalence class are multiples of 4 plus 2 → 4x + 2
- Values in the “3” equivalence class are multiples of 4 plus 3 → 4x + 3
where x = 0, 1, -1, 2, -2, and so forth
There you go! The basics of modular arithmetic, and you see it’s actually quite elementary. Till next time! Happy math-ing!!