Cryptographers love mod because when you use it with really large numbers you can create what are known as *one-way functions. * These are special functions which allow you to easily calculate something in one direction, but not reverse it.
If I tell you that 9 is the result of my squaring operation, you can easily deduce that the input was 3. You would have the entire process front to back. If I tell you that 9 is the result of my function mod 29, you would have a harder time trying to figure out what the input was.
This gives the wrong idea about one-way functions. For something to be one-way, one should not be able to compute any answers to the question (not just the one the questioner intended). For example, 9 is an answer to your question, which is easy to compute.
I smelled that the author is pushing his own, so I went to see what’s going on.
This is actually post-rationalization because although it gives a good rational, this is not really what’s going on. What is actually going on is that the modulus and division are connected.
The way how they are connected can be described as: a = (a / b) * b + a % b.
Division gives a different result depending on rounding. C99 spec says that the rounding goes toward to zero, but we have also had floor division implementations and systems where you can decide on the rounding mode.
If you have floor division, the 19 / -12 gives you -2. That is correct when the modulo operator gives you -5. If you do a round-towards-zero-division, the 19 mod -12 must give you 7.
On positive numbers, the rounding to zero and floor rounding give the same results.
Also checked on x86 spec. It’s super confusing about this. If the online debugger I tried was correct, then the x86 idiv instruction is doing floor division.
Forgive my extreme mathematical naivety, but a = (a / b) * b + a % b doesn’t make much sense to me. Given (a / b) * b will always equal a, doesn’t this imply that a % b is always 0?
The division operator in this case is not division in the algebraic sense, and it does not cancel with the multiplication such that (a / b * b = a) {b != 0}. Otherwise your reasoning would be correct.
To still make this super clear, lets look at 19 / -12. The real number division of this would give you -1.58... But we actually have division rounded toward negative (floor division) or division rounded toward zero, and it’s not necessarily clear which one is it. Floor division returns -2 and division rounding toward zero returns -1.
The modulus is connected by the rule that I gave earlier. Therefore 19 = q*-12 + (19 % -12). If you plug in -2 here, you’ll get -5 = 19 % -12, but if you plug in -1 then you get 7 = 19 % -12.
Whatever intuition here was is lost due to constraints to stick into integers or approximate numbers, therefore it’s preferable to always treat it as if modulus was connected with floor division because the floor division modulus contains more information than remainder. But this is not true on every system because hardware and language designers are fallible just like everybody else.
This gives the wrong idea about one-way functions. For something to be one-way, one should not be able to compute
anyanswers to the question (not just the one the questioner intended). For example,9is an answer to your question, which is easy to compute.I smelled that the author is pushing his own, so I went to see what’s going on.
This is actually post-rationalization because although it gives a good rational, this is not really what’s going on. What is actually going on is that the modulus and division are connected.
The way how they are connected can be described as:
a = (a / b) * b + a % b.Division gives a different result depending on rounding. C99 spec says that the rounding goes toward to zero, but we have also had floor division implementations and systems where you can decide on the rounding mode.
If you have floor division, the
19 / -12gives you-2. That is correct when the modulo operator gives you-5. If you do a round-towards-zero-division, the19 mod -12must give you7.On positive numbers, the rounding to zero and floor rounding give the same results.
Also checked on x86 spec. It’s super confusing about this. If the online debugger I tried was correct, then the x86 idiv instruction is doing floor division.
Forgive my extreme mathematical naivety, but
a = (a / b) * b + a % bdoesn’t make much sense to me. Given(a / b) * bwill always equala, doesn’t this imply thata % bis always 0?/in this context is integer division, not rational division, so e.g.7 / 3 = 2.The division operator in this case is not division in the algebraic sense, and it does not cancel with the multiplication such that
(a / b * b = a) {b != 0}. Otherwise your reasoning would be correct.To still make this super clear, lets look at
19 / -12. The real number division of this would give you-1.58... But we actually have division rounded toward negative (floor division) or division rounded toward zero, and it’s not necessarily clear which one is it. Floor division returns-2and division rounding toward zero returns-1.The modulus is connected by the rule that I gave earlier. Therefore
19 = q*-12 + (19 % -12). If you plug in-2here, you’ll get-5 = 19 % -12, but if you plug in-1then you get7 = 19 % -12.Whatever intuition here was is lost due to constraints to stick into integers or approximate numbers, therefore it’s preferable to always treat it as if modulus was connected with floor division because the floor division modulus contains more information than remainder. But this is not true on every system because hardware and language designers are fallible just like everybody else.