![Cover image for ZK Series #4 [ Sets, Groups, Rings , Finite Fields and Prime Fields]](https://media2.dev.to/dynamic/image/width=1000,height=420,fit=cover,gravity=auto,format=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2Fi7z5bqe41o7ato80lw51.jpg)
In Series #3 we spoke about Modular Arithmetic and there were some statements that I made that had no backing. I intend to use this part to give the whole picture and link things up.
Set Theory
I am sure from Elementary School we all learn about sets but a quick reminder is think of a group of items that are related. If I ask you to name the top 10 richest people in the world, the list you enumerated creates a set. In math, we call it a set of people of the top 10 richest people.
We are going to lay some foundational concepts by getting some Set Theory vocabulary; Our new words are
-
Set Equality: Sets are equal if they contain the same elements, regardless of the order.
- For example, the sets {1, 2, 3} and {3, 2, 1} are considered equal because they contain the same elements.
Cardinality: This refers to the number of elements in a set.
Super Set: A set that contains all the elements of another set, possibly with additional elements.
Subset: A set whose elements are all contained within another set.
I would like to talk about the properties of number systems because we are going to be defining key terms based on this foundational principle
| Property | Explanation |
|---|---|
| Commutative | The order of operands can be swapped without changing the result. |
| For addition: (a + b = b + a) | |
| For multiplication: (a \times b = b \times a) | |
| Closure | When you perform an operation on two elements, the result is always another element of the same type. |
| For addition: Adding any two whole numbers gives you another whole number. | |
| For multiplication: Multiplying any two real numbers gives you another real number. | |
| Associative | The grouping of operations doesn't affect the result. |
| For addition: ((a + b) + c = a + (b + c)) | |
| For multiplication: ((a \times b) \times c = a \times (b \times c)) | |
| Identity | There exists a special element called the identity element, which leaves other elements unchanged when combined. |
| For addition: The identity element is 0, because (a + 0 = a) for any (a). | |
| For multiplication: The identity element is 1, because (a \times 1 = a) for any (a). | |
| Distributive | Describes how multiplication interacts with addition. |
| For integers: (a \times (b + c) = (a \times b) + (a \times c)) | |
| For real numbers: (a \times (b + c) = (a \times b) + (a \times c)) |
Group
Closure: Imagine you have a box of colorful marbles. Each marble has a number on it. When you pick any two marbles from the box and add them together, you always get another marble from the same box. For instance, if you have a blue marble with the number 3 and a red marble with the number 5, and you add them together, you'll get a purple marble with the number 8. That's closure!
In Math Lingo: A={0, 1,2,3, 4,5} a + b = c and c is a member of A so if we take 2 + 3 = 5 ; 5 is a memeber of A so that is closure
Associativity: Think of three numbered blocks, labeled A, B, and C. You want to stack them on top of each other. It doesn't matter if you first stack A on B and then C on top, or if you first stack B on C and then A on top. Either way, you'll end up with the same tower of blocks. That's associativity!
Inverse: Now, imagine you have a special block called the "magic zero block." When you combine this block with any other block, you get back the same block you started with. For example, if you have a green block with the number 7 and its magic zero block, when you put them together, you get the green block with the number 7 again. That's the inverse property!
Identity: Lastly, let's talk about the "superhero" block. This block doesn't change anything when you combine it with other blocks. So, if you have a yellow block with the number 10 and you add it to the superhero block, you'll still end up with the yellow block with the number 10. It's like the superhero block keeps everything in order!
So, in your box of colorful marbles, you have closure because adding any two marbles gives you another marble from the same box. You have associativity because the order in which you stack the blocks doesn't matter. You have inverses because every block has a magic zero block that returns the original block. And finally, you have the superhero block, which keeps everything stable and unchanged. That's the magic of your block group
Examples of Groups: In terms of the binary operators, addition is commonly used so the examples here are with respect to the addition binary operators
Integers (Z) under addition
:
Closure: 3 + 5 = 8; Associativity: (2 + 3) + 4 = 2 + (3 + 4); Identity: 0 (a + 0 = a); Inverse: -5 is the inverse of 5 (5 + (-5) = 0).Real Numbers (R) under addition: Similar properties hold for addition of real numbers.
Non-zero rational numbers (Q \ {0}) under multiplication: Closure: (2/3) * (3/4) = 1/2; Associativity: (2 * 3) * 4 = 2 * (3 * 4); Identity: 1 (a * 1 = a); Inverse: Every non-zero rational number has a multiplicative inverse (a * a^-1 = 1).
_The set of Natural Numbers with the binary operator being addition does not fall into a group _
Abelian Group: An abelian group is one where the operation (usually addition) is commutative.
Rings
Rings extend groups by introducing a second binary operation (often multiplication) alongside the existing operation (usually addition). Rings satisfy the following properties:
Ring Properties: Inherit all group properties (closure, associativity, identity, and inverse for addition).
Distributive Property: The interaction between the two operations is defined. (a \times (b + c) = (a \times b) + (a \times c)).
Examples of rings
The set of integers (Z)
The set of Real Numbers(R)
The set of Complex Numbers (C)
In Multiplication 1 is the identity element because if we multiply any number by 1 we get the same number.
**
Matrices are not an example of Rings. If I have a set of 2x3 matrices we cannot multiply them.
**
(2x3) * (2*3) is impossible in matrices
(2x3) * (3*2) this is what we need and since 3 by 2 matrices is not a part of the set we cannot have Matrices being an example of a Ring
Field
A Field is a set on which addition, subtraction , multiplication and division are defined
Addition
Additive Inverse
-Multiplication
-Multiplicative Inverse for every number that is not zero
Consider the set of rational numbers (a/b) where a and b are integers and b is not equal to 0 .
- They are commutative with addition
- They are commutative with multiplication
- All elements have a multiplicative inverse
Sets of integers do not form a field eg: we take a number 4 ; its multiplicative inverse is 1/4
set of 2x2 matrices do not form a field
But remember last time we spoke about the problems with infinite forms of sets in the normal number system and how we need finite set of numbers; now we want to apply that here
Perform mod 2 on any integer
| Integer | Mod 2 Arithmetic |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 0 |
| 3 | 1 |
| 4 | 0 |
| 5 | 1 |
| ... | ... |
If we continue, we observe that the results of modulo 2 arithmetic alternate between 0 and 1, indicating that our new number system consists of just two elements: {0, 1}.
Performing mod 5 arithmetic on any integer yields the following pattern:
| Integer | Mod 5 Arithmetic |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 4 |
| 5 | 0 |
| 6 | 1 |
| 7 | 2 |
| 8 | 3 |
| 9 | 4 |
| 10 | 0 |
| 11 | 1 |
| ... | ... |
Thus, we can conclude that the set of integers modulo 5 consists of the numbers {0, 1, 2, 3, 4}.
Classification
Now, let's classify whether Z mod 2 is a Group, Ring, or Field:
Addition
- We expect the solution to be part of the set of integers mod 2, {0, 1}.
- Example: (3 \mod 2 + 4 \mod 2 = 1)
- Example: (5 \mod 2 + 10 \mod 2 = 0)
- This demonstrates closure, as the output is within our set.
Multiplication
- Again, we expect the solution to be part of the set of integers mod 2, {0, 1}.
- Example: ((3 \mod 2) \times (4 \mod 2) = 3 \times 4 \mod 2 = 12 \mod 2 = 0)
- Example: ((5 \mod 2) \times (10 \mod 2) = 5 \times 10 \mod 2 = 50 \mod 2 = 0)
- This also shows closure.
Conclusion
- As every element has a multiplicative inverse (1's inverse is always 1), {0, 1} forms a finite field.
- Finite fields are also called Galois Fields (GF).
- Z mod 2 is represented as GF(2).
- Finite fields exist only in the form P^m, where P is a prime number and m is a positive integer.
- Example: GF(3^4) = GF(81)
- If m > 1, it's called an extension field, such as GF(p^m).
This classification helps us understand the properties and structures of different mathematical systems.
In the next series we would talk more touch the surface of Elliptic Curve Cryptography
Top comments (0)