logoZK Academy

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:

Example of modulo with 12 hours clock
Use slider to count more hours
121234567891011
12 mod 120on the clock

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

Well - to be clear you get a value from 0 to 11 by doing the actual modulo operation, but you see 12 on the clock when the input is cleanly divisible by 12 - that's just how clocks are usually labeled and it is a bit quirky

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:

Clock with adjustable hours per step
Change hours per step to see how the clock behaves
01234567891011
0 mod 120remainder

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:

Circle with a prime number of ticks
Try any step size — you can never make it skip
012345678910111213141516
0 mod 170remainder

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!

On this page