.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 ( ) = 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