Blockchain Basic: Understanding Modulo Operation

[Maus0728]

.UNDERSTANDING MODULO

While I am searching in this forum about blockchain topic, I came across in this topic secp256k1 parameters: when to use what as a modulus? that pertains to a familiar term called Modulo. Modulo is one of the lesson we’ve covered in one of the required subject in my course called Discrete Mathematics, so I decided to review my lecture notes and create an informative post since I have a basic understanding how Modulo operates.

How Modulo is related in cryptography?

Upon searching on the internet, having an understanding of Modulo is one of the basic mathematical foundations necessary to understand blockchain and elliptic curve cryptography. Based on the last topic that I have created about Hash Function Blockchain Basic: Number System | Random Number | Hash Function, we can say that hashes are irreversible meaning that it is a one way process. It is irreversible in the sense that for each input you have exactly one output or multiple input can yield the same exact output. In simpler terms, we cannot determine the input value based only in the output value because there are many possible number input in order to get the same exact answer. (ref1, ref2, ref3)

Key Takeaway

• The mathematical law of Modulo operator is similar to the irreversibility of cryptographic hashes.
• Cryptographic hashes are designed to be irreversible and collision resistant

.MODULO

We define Z_n as the set of integers from {0, 1, 2, 3, ... n-1} modulo n. Note that  Z_n has exactly n nonnegative integers. In particular, we define Z_n with the following set of positive integers.

Z₃ = {0, 1, 2}, modulo 3
Z₅ = {0, 1, 2, 3, 4}, modulo 5
Z₇ = {0, 1, 2, 3, 4, 5, 6}, modulo 7

In Z_n, modulo is simply the remainder r when an integer a ∈ Z is divided by n, i.e.

a/n has remainder r < n

.Example 1

Find the remainder of the integers a) 9 ; b) 29 in Z₃, Z₄, Z₅ and Z₇

Solution:

a) 9

Z₃ : r = 0 Explanation: 9 / 3 = 3 with 0 remainder
Z₄ : r = 1 Explanation: 9 / 4 = 2 ; 4 * 2 = 8 ; 9 - 8 = 1 remainder ==> This is an example irreversibility meaning different input can yield the same exact output
Z₅ : r = 4 Explanation: 9 / 5 = 1 ; 5 * 1 = 5 ; 9 - 5 = 4 remainder
Z₇: r = 2  Explanation: 9 / 7 = 1 ; 7 * 1 = 1 ; 9 - 7 = 2 remainder

b) 29

Z₃ : r = 2 Explanation: 29 / 3 = 9 ; 3 * 9 = 27 ; 29 - 27 = 2
Z₄ : r = 1 Explanation: 29 / 4 = 7 ; 4 * 7 = 28 ; 29 - 28 = 1 ==> This is an example irreversibility meaning different input can yield the same exact output
Z₅ : r = 4 Explanation: 29 / 5 = 5 ; 5 * 5 = 25 ; 29 - 25 = 4
Z₇ : r = 1 Explanation: 29 / 7 = 4 ; 7 * 4 = 28 ; 29 - 28 = 1

.Example 2

Perform the following in Z₃, Z₅, Z₇

a)  3 + 5
b)  6 ∙ 2

Solution:

a)  3 + 5

Z₃ :3 + 5 = 2 Explanation: Sum = 8 ; 8 / 3 = 2 ; 3 * 2 = 6 ; 8 - 6 = 2
Z₅ :3 + 5 = 3 Explanation: Sum = 8 ; 8 / 5 = 1 ; 5 * 1 = 5 ; 8 - 5 = 3
Z₇ :3 + 5 = 1 Explanation: Sum = 8 ; 8 / 7 = 1 ; 7 * 1 = 7 ; 8 - 7 = 1

b)  6 ∙ 2

Z₃ :6 ∙ 2 = 0 Explanation: Product = 12 ; 12 / 3 = 4 ; 3 * 4 = 12 ; 12 - 12 = 0
Z₅ :6 ∙ 2 = 2 Explanation: Product = 12 ; 12 / 5 = 2 ; 5 * 2 = 10 ; 12 - 10 = 2
Z₇ :6 ∙ 2 = 5 Explanation: Product = 12 ; 12 / 7 = 1 ; 7 * 1 = 7 ; 12 - 7 = 5

CONSTRUCTING TABLES OF Z_n

1. In Z₃ = {0, 1, 2}

Z₃ is closed under the binary operations of multiplication of integers modulo 3

Find the following:

1. -1 (add value of n) = 2
2. -2 (add value of n) = 1
3. 1 / 2(multiplicative inverse of 2; or 2-1) = 2 ==> refer to the table above in order to get the modulo involving fractions

Note: If there is a negative integer add the value of n to get the modulo. In this example n = 3

2. In Z₅ = {0, 1, 2, 3, 4}

Z₅ is closed under the binary operations of multiplication of integers modulo 5.

Find the following:

1. -1 = 4 Explanation: -1 + 5 = 4
2. -2 = 3 Explanation: -2 + 5 = 3
3. -3 = 2 Explanation: -3 + 5 = 2
4. -4 = 1 Explanation: -4 + 5 = 1
5. 1 / 2 = 3 Explanation: refer to the table above
6. 1 /3 = 2 Explanation: by looking at the numerator
7. 1 / 4 = 4 Explanation: and denominator
8. 2 / 3 = 4
9. - 3 / 4 = 3

In the next following example there will be no explanation to the correct answer given

3. In Z₃, find the following:

a) 2 - 3 = 2 + 0 = 2
b) -2 - 1 = 1 + 2 = 0
c) -1 / 2 = -2 = 1
d) -3 + 1 / 2 = 0 + 2 = 2
e) 2[-2 ÷ (-1)] = 2[1 ÷ 2] = 2 (1 / 2) = 2(2) = 1
f) -1 ÷ (-2) = 2 / 1 = 2

4. In Z₅, find the following:

a) 1 / 3+ 1 /2 = 2 + 3 = 0
b) -3 + 1 / 4 = 2 + 4 = 1
c) -1 / 3 + 1 / 4 = -2 + 4 = 3 + 4 = 2
d) - 2 / 3 + 3 / 4 = -4 + 2 = 1 + 2 = 3

5. Construct the table for Z₄ using the binary operation of multiplication and find the following:

a) -3 + 5
b) 2 - 1 / 3
c) 1 / 2

a) -3 + 5 = 1 + 5 = 2
b) 2 - 1 / 3 = 2 - 3 = 2 + 1 = 3
c) 1 / 2 = does not exist (DNE)

.MORE EXERCISES

1. -4 + 2/5 in Z₇
= 3 + 6
= 9
= 2

2. - 3 / 10 + 6 – 4 / 7 in Z₁₁
= -8 + 6 – 10
= 3 + 6 + 1
= 10

3. -6 – 4 / 9 + 1 / 4 in Z₁₀
= 4 – 6 + ?
= does not exist/ undefined

4. 7 - 75 in Z₇
= 7 – 75 = -68
= -61 = -54= -47= -40= -33= -26= -19= -12= -5= 2 Explanation: add value of n until the answer become positive integer.

General note: Negative answer in modulo is restricted


Thank you for reading my topic regarding modulo. I hope that this topic helps you to understand the underlying importance behind the concept of blockhain. Thank you

[1715118071]

1715118071

[1715118071]

1715118071

[nutoskaleo]

Please tell me, is it possible to understand all this things if you are not a mathematican and even not a technical specialst? All these rules are so about maths... Hard to push your brain into the understanding but it looks like it's important if you hope to understand how blockchain works.

[cryptomaniac_xxx]

I'm sorry OP but this kind of post should not be in this board, this is too much for a non technical incline newbie registering in this community and checking the Beginners & Help board trying to understand bitcoin and blockchain. Probably better on some Bitcoin technical discussion board.

[pooya87]

Please tell me, is it possible to understand all this things if you are not a mathematican and even not a technical specialst?

finding the remainder is the elementary school level mathematics. and for the most part the modular arithmetic is also pretty simple and straight forward, in simple terms it says perform the arithmetic as before but when you are done you should compute the remainder of the result instead. for example to compute 5*6 (mod 7) you first compute 5*6=30 then compute the remainder 30%7=2. you don't need to be a mathematician to understand this.
the hard part (which is not included here) is the optimizations used such as mathematical theories to solve modular multiplicative inverse, or something as simple as MultMod.

[Maus0728]

finding the remainder is the elementary school level mathematics. and for the most part the modular arithmetic is also pretty simple and straight forward, in simple terms it says perform the arithmetic as before but when you are done you should compute the remainder of the result instead.

Correct, I don't know why everyone is having a difficulty in understanding modulo operator and find it complicated, maybe because of the way I write the lecture and examples. If they are going to carefully examine the problem and the explanation of the first part of the lecture, they can understand it very well up to the very last example.

the hard part (which is not included here) is the optimizations used such as mathematical theories to solve modular multiplicative inverse, or something as simple as MultMod.

I did not consider including that topic here because you cannot easily solve modular multiplicative inverse if they do not understand the basic principle of modulo. That topic is very interesting and fun to solve. It is similar with Division Algorithm and Euclidean Algorithm.

I am thinking if I will going to create another post regarding those mathematical concept. Do you think it is a good idea @pooya87?

Thanks for having an interest in topic. It gives me hope, thank you so much.

[pooya87]

I did not consider including that topic here because you cannot easily solve modular multiplicative inverse if they do not understand the basic principle of modulo. That topic is very interesting and fun to solve. It is similar with Division Algorithm and Euclidean Algorithm.

true. and it is fine to exclude any topic you think is complicated and stick to basics.
but you could also include a simple definition of the term. ie. modular multiplicative inverse of a is to find x so that a*x ≡ 1 (mod m)
eg. a = 2, m = 7 => x=4 because 2*4 ≡ 8 ≡ 1 (mod 7)

I am thinking if I will going to create another post regarding those mathematical concept. Do you think it is a good idea @pooya87?

that would be a great idea.

[rhomelmabini]

It is an interesting topic though I don't want to deep dive in this for my web development career, but it's interesting and I just learned this modulo on learning basics of JavaScript and came across also on free courses of Python, most course do include this one. Are you somehow a computer science student or have you graduated already?

I am thinking if I will going to create another post regarding those mathematical concept. Do you think it is a good idea @pooya87?

Why not, there are still room for it I guess but just research a little if there are no similar topic that has been done before.

[Maus0728]

It is an interesting topic though I don't want to deep dive in this for my web development career, but it's interesting and I just learned this modulo on learning basics of JavaScript and came across also on free courses of Python, most course do include this one. Are you somehow a computer science student or have you graduated already?

I am a first year Computer Engineering Student and yes, modulo operator is a basic requirement for a programmer to understand. I remember during our early exercises in C++ Programming, we used this operator in order to find the odd and even numbers. And I know there are lots of use cases of modulo operation in different algorithm especially in the field of cryptography, that is why I decided to create this topic.

Understanding a different mathematical operation is I think a good foundation if someone wishes to be a good programmer specifically if he wanted to pursue in understanding the blockchain technology. I admire you people!

Why not, there are still room for it I guess but just research a little if there are no similar topic that has been done before.

Yes, I'll be creating another informative thread regarding Algorithm, Division and Euclidea to precise!. Thank you for having such an interest!

I'll be posting the lecture soon in this section!

[pooya87]

I remember during our early exercises in C++ Programming, we used this operator in order to find the odd and even numbers.

you could have used bitwise AND (&) to check if the least significant bit is set or not to determine odd and even-ness of a number.
it makes a big difference (speed-wise) for bigger integers such as 256-bit ones we use in bitcoin.

[NotATether]

Thanks for the guide. So in other words when you multiply two numbers in a set of integers, or group as they are called formally, you just take their product normally and take the modulus of it, order n, assuming the group is Z_n.

And when you make a multiplication table of this the modulus of the product should also be taken. And then the resulting table is symmetrical which is what allows division to be possible. because a property of division is a / b = c; a / c = b. And so if you construct a multiplication table you can easily define division in a group as the inverse of multiplication, so since In Z₃  2 ∙ 2 = 1, then 1 / 2 = 2 in Z₃, and we also have 1 ∙ 1 = 1 in Z₃ (since it's just multiplication and the product was too low to take the remainder of), then we also have 1 / 1 = 1 in Z₃.

You mentioned:

3. 1 / 2(multiplicative inverse of 2; or 2-1) = 2 ==> refer to the table above in order to get the modulo involving fractions

Is there a way to perform the division using the subtraction operation? This subtraction didn't make sense to me since 2 and 1 are both in Z₃ so subtracting 2 - 1 would've given 1. But the table, which I know gives the correct answer, would give 2.

Correct me if I'm wrong but in a % b, the modulo refers to a, while the denominator refers to b?

Also, what would be the result of 2 / 2 in Z₄? Do we have a name for this kind of result where there's more than one possible value?

Now I see the importance of using only prime numbers as orders of n, to avoid making the multiplication table degenerate as in some divisions do not exist or have ambiguous (two or more) answers.

[pooya87]

So in other words when you multiply two numbers in a set of integers, or group as they are called formally, you just take their product normally and take the modulus of it, order n, assuming the group is Z_n.

by definition, yes that is how modular multiplication is defined but in practice it would be very slow to perform it like this since x*y if both are n-bits would become as big as 2n-bits and then division (to find the remainder) is a slow process. instead optimized algorithms such as Montgomery is used.