⭐ Merited by cabalism13 (10) ,fillippone (4) ,Heisenberg_Hunter (2) ,pooya87 (1) ,rhomelmabini (1) ,NotATether (1) ,ETFbitcoin (1) ,GreatArkansas (1)
.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
.MODULO
We define Zn as the set of integers from {0, 1, 2, 3, ... n-1} modulo n. Note that Zn has exactly n nonnegative integers. In particular, we define Zn with the following set of positive integers.
Z3 = {0, 1, 2}, modulo 3
Z5 = {0, 1, 2, 3, 4}, modulo 5
Z7 = {0, 1, 2, 3, 4, 5, 6}, modulo 7
In Zn, 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 Z3, Z4, Z5 and Z7
Solution:
a) 9
Z3 : r = 0 Explanation: 9 / 3 = 3 with 0 remainder
Z4 : 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
Z5 : r = 4 Explanation: 9 / 5 = 1 ; 5 * 1 = 5 ; 9 - 5 = 4 remainder
Z7: r = 2 Explanation: 9 / 7 = 1 ; 7 * 1 = 1 ; 9 - 7 = 2 remainder
b) 29
Z3 : r = 2 Explanation: 29 / 3 = 9 ; 3 * 9 = 27 ; 29 - 27 = 2
Z4 : 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
Z5 : r = 4 Explanation: 29 / 5 = 5 ; 5 * 5 = 25 ; 29 - 25 = 4
Z7 : r = 1 Explanation: 29 / 7 = 4 ; 7 * 4 = 28 ; 29 - 28 = 1
.Example 2
Perform the following in Z3, Z5, Z7
a) 3 + 5
b) 6 ∙ 2
Solution:
a) 3 + 5
Z3 :3 + 5 = 2 Explanation: Sum = 8 ; 8 / 3 = 2 ; 3 * 2 = 6 ; 8 - 6 = 2
Z5 :3 + 5 = 3 Explanation: Sum = 8 ; 8 / 5 = 1 ; 5 * 1 = 5 ; 8 - 5 = 3
Z7 :3 + 5 = 1 Explanation: Sum = 8 ; 8 / 7 = 1 ; 7 * 1 = 7 ; 8 - 7 = 1
b) 6 ∙ 2
Z3 :6 ∙ 2 = 0 Explanation: Product = 12 ; 12 / 3 = 4 ; 3 * 4 = 12 ; 12 - 12 = 0
Z5 :6 ∙ 2 = 2 Explanation: Product = 12 ; 12 / 5 = 2 ; 5 * 2 = 10 ; 12 - 10 = 2
Z7 :6 ∙ 2 = 5 Explanation: Product = 12 ; 12 / 7 = 1 ; 7 * 1 = 7 ; 12 - 7 = 5
CONSTRUCTING TABLES OF Zn
1. In Z3 = {0, 1, 2}
Z3 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 Z5 = {0, 1, 2, 3, 4}
Z5 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 Z3, 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 Z5, 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 Z4 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 Z7
= 3 + 6
= 9
= 2
2. - 3 / 10 + 6 – 4 / 7 in Z11
= -8 + 6 – 10
= 3 + 6 + 1
= 10
3. -6 – 4 / 9 + 1 / 4 in Z10
= 4 – 6 + ?
= does not exist/ undefined
4. 7 - 75 in Z7
= 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
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 Zn as the set of integers from {0, 1, 2, 3, ... n-1} modulo n. Note that Zn has exactly n nonnegative integers. In particular, we define Zn with the following set of positive integers.
Z3 = {0, 1, 2}, modulo 3
Z5 = {0, 1, 2, 3, 4}, modulo 5
Z7 = {0, 1, 2, 3, 4, 5, 6}, modulo 7
In Zn, 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 Z3, Z4, Z5 and Z7
Solution:
a) 9
Z3 : r = 0 Explanation: 9 / 3 = 3 with 0 remainder
Z4 : 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
Z5 : r = 4 Explanation: 9 / 5 = 1 ; 5 * 1 = 5 ; 9 - 5 = 4 remainder
Z7: r = 2 Explanation: 9 / 7 = 1 ; 7 * 1 = 1 ; 9 - 7 = 2 remainder
b) 29
Z3 : r = 2 Explanation: 29 / 3 = 9 ; 3 * 9 = 27 ; 29 - 27 = 2
Z4 : 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
Z5 : r = 4 Explanation: 29 / 5 = 5 ; 5 * 5 = 25 ; 29 - 25 = 4
Z7 : r = 1 Explanation: 29 / 7 = 4 ; 7 * 4 = 28 ; 29 - 28 = 1
.Example 2
Perform the following in Z3, Z5, Z7
a) 3 + 5
b) 6 ∙ 2
Solution:
a) 3 + 5
Z3 :3 + 5 = 2 Explanation: Sum = 8 ; 8 / 3 = 2 ; 3 * 2 = 6 ; 8 - 6 = 2
Z5 :3 + 5 = 3 Explanation: Sum = 8 ; 8 / 5 = 1 ; 5 * 1 = 5 ; 8 - 5 = 3
Z7 :3 + 5 = 1 Explanation: Sum = 8 ; 8 / 7 = 1 ; 7 * 1 = 7 ; 8 - 7 = 1
b) 6 ∙ 2
Z3 :6 ∙ 2 = 0 Explanation: Product = 12 ; 12 / 3 = 4 ; 3 * 4 = 12 ; 12 - 12 = 0
Z5 :6 ∙ 2 = 2 Explanation: Product = 12 ; 12 / 5 = 2 ; 5 * 2 = 10 ; 12 - 10 = 2
Z7 :6 ∙ 2 = 5 Explanation: Product = 12 ; 12 / 7 = 1 ; 7 * 1 = 7 ; 12 - 7 = 5
CONSTRUCTING TABLES OF Zn
1. In Z3 = {0, 1, 2}
Z3 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 Z5 = {0, 1, 2, 3, 4}
Z5 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 Z3, 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 Z5, 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 Z4 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 Z7
= 3 + 6
= 9
= 2
2. - 3 / 10 + 6 – 4 / 7 in Z11
= -8 + 6 – 10
= 3 + 6 + 1
= 10
3. -6 – 4 / 9 + 1 / 4 in Z10
= 4 – 6 + ?
= does not exist/ undefined
4. 7 - 75 in Z7
= 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