01. What Remainder Remembers
Modulo Operation and finite fields
How we got to modulo
In cryptography we base our computations and protocols on integers. We do this because fundamental pillars of cryptography such as Number Theory and Boolean Logic work only with discrete values
Reason for that is actually quite fascinating - despite integers intuitively being just a "subset" of rational numbers - we actually lose properties going from integers to rationals. Crucially we lose prime factorization required by core of Number Theory. We lose it because we can define rational numbers by infinite different combinations of factors, while each integer can be defined by only a unique combination of primes
Working with discrete numbers is not that different compared to working with rational numbers (such as 3/5 or 1.16834). We can add, multiply and subtract rationals and integers just the same. Difference comes when we try to divide integers. If you divide 13 / 5 and want to get an integer... well how do you actually do that?
While we are speaking, a CPU on your device actually did that a bunch of times. It simply calculates integer value of division and checks what is left - getting a remainder. So 13 / 5 is just:
13 / 5 = 2 (and remainder of 3)You kind of get two parts produced by a pair of operators - full integer division and modulo operator (for getting a remainder)
You could actually see how exactly modulo works looking at mechanical clocks:
You always get an answer from a finite number of integers, though hours keep going by. You get a number from 1 to 12, though it could pass much more than 12 hours
Modulo is essential for cryptography. The interesting property of modulo operation is that it is easy to do in one direction, but impossible to revert. If you count hours, and 42 hours have passed - you know that you will see 6 on the clock. But if someone will steal your clock and they will see 6 hours - they wouldn't know if you waited for 42 hours, or 30 hours, or 18 hours
Modulo and Primes
Another interesting thing happens when we increase the "step" we do going in modulo clock. Previously we were sliding one hour at a time, let's look at how the modulo clock will behave if we will add more hours per time:
Do you notice how going 2, 3, 4, and 6 makes the clock "skip" some numbers? I mean if you think about that it's quite logical - for example a step of 3 is basically going a quarter of clock every time. It doesn't matter how long you jump 3 hours ahead - you can't get a number that would get 2 as a result of modulo operation
Same with 4 - you go 1/3 of the clock each time because well - 4 is 1/3 of 12
Example of ones that give you whole spectrum of numbers as result of modulo are:
- Of course number 1 (but it's too boring)
- 5
- 7
You can notice that 5 and 7 don't divide 12 cleanly. This "always off" division is what makes values get pushed as clock keeps going around
Though jumping over numbers feels quite cool - it sucks for properties of the operation. If jumping 3 steps over a 12 hours clock is the same as jumping 1 step over a 4 ticks circle - why pay more?
Let's see how the same interactive clock will behave when we have a prime number as base of the clock. We pick 17 for no particular reason, try to move sliders to see how it will behave now:
As you can see, whatever step we pick - it always cover the full numbers range. The reason is - we can't pick such a step that would divide the prime number cleanly, that's literally the only property defining a prime number
Small summary
We learned a cool property of modulo operation - "one direction-ness", as well as how to pick a modulo base that would juice the heck out of it. Let's try to do something practical now!