21 Groups, Rings and Fields
Hiteishi Diwanji
Groups, Rings and Fields
- Groups, Rings, Fields are Fundamental elements of abstract algebra.
- Combine two elements of set, to obtain a third element of set.
Groups:
- A group G, denoted by [G, ●]
- Set of elements with a binary operation denoted by ● that associates to each ordered pair (a,b) of elements in G, an element (a ● b) in G, such that following axioms are obeyed.
- (A1) Closure: If a and b belong to G, then a ● b is also in G.
- (A2) Associative : a ● (b ● c) = (a ● b) ● c for all a,b,c in G.
- (A3) Identity element: element e in G such that a ● e = e ● a = a for all a in G
- (A4) Inverse Element : For each a in G, there is an element a’ in G such that a ● a’= a’ ● a= e
Finite Group
- If a group has finite number of elements, it is referred as a finite Group.
- Number of elements in the group is called the order of the group.
- A group with infinite number of elements is called infinite group. Abelian group
- A group is abelian if follows the following axiom in addition to (A1) to (A4) (A5) commutative : a ● b = b ● a for all a,b in G.
The set of integers(positive,negative and 0) under addition follow all axioms
(A1) Closure: adding two positive integers is positive integer, two negative integers is negative integers, positive and negative may end up in positive or negative integer.
5+2 = 7-2+3=1 -3+-3=-6
(A2)Associative: 3+(4+5)=(3+4)+5 -2+(-5+-6)=(-2+-5)+-6
(A3)Identity element: 5+0=0+5=5 3+0=0+-3=-3
(A4) Inverse element : 5+(-5)=0
(A5) Commutative : 5 + -7 = -7+5
- * For group operation addition, the identity element is 0, inverse element of a is –a. subtraction is defined as a-b = a+(-b).
Cyclic group
- a4= axaxaxa
- a0=e(as identity element)
- a-n=(a’)n where a’ is the inverse element of a within the group.
- A group G is cyclic if every element of G is a power ak (k is an integer) of a fixed element aεG. The element a is said to generate the group G or to be a generator of G. A cyclic group is always abelian and may be finite or infinite.
- The additive group of integers is an infinite cyclic group generated by the element 1.
- Powers are interpreted as addition so that nth power of 1.
- 11+21+31+ ….
Rings:
- A ring R, denoted by {R, +, x} is a set of elements with two binary operations(addition and multiplication) such that all axioms are followed for all a,b,c in R .
- (A1-A5) – R satisfies A1 through A5 for addition so R is an abelian group with respect to addition.
- (M1) Closure under multiplication – ab is in R if a and b belong to R.
- (M2) Associativity of multiplication – a(bc)=(ab)c for all a,b,c in R.
- (M3) distributive laws –
- a(b+c) = ab+ac for all a,b,c in R.
- (a+b)c = ac+bc for all a,b,c in R.
- * Ring can do addition, multiplication and subtraction. Subtraction is [a-b=a+(-b)].
- A set of integer numbers(positive, negative and 0) is a ring, with respect to addition and multiplication.
- The set of all matrices is a ring.
- Ring is commutative If following axiom is satisfied.
(M4) commutative(multiplication): ab=ba for all a,b, in R.
Integral domain:
- Integral domain is a commutative ring if following axioms are satisfied.(M5) Multiplicative identity – the element 1 in R such that a1=1a=a for all a in R. (M6)No zero divisor – if a,b in R and ab=0 then either a=0 or b=0.
- Let S be the set of integers positive, negative and 0 under operation of addition and multiplication, S is an integral domain.
Fields:
- A field F denoted by [F, +,x] is set of elements with two binary operations, called addition and multiplication, such that all a,b,c in F follows following axioms.(A1-M6) : F is an integral domain if F satisfies axioms A1 through A5 and M1 through M6. (M7) Multiplicative inverse : For each a in F, except 0 , there is an element a-1 in F such that aa-1 in F such that aa-1=(a-1)a=1 In Field, addition, subtraction, multiplication and division results in the same set.
- Division is defined as a/b=a(b-1)
- All rational, real and complex numbers are field.
Finite Fields of the Form GF(p)
- Finite fields are important in cryptography
- Order of a finite field that is number of elements in the field must be a power of a prime pn, where n is a positive integer.
GF(pn)
- Finite field of order pn is GF(pn).
- GF stands for Galois field, in the honor of mathematician who studied this for the first time.
- Two special cases exist.
- n=1, finite field GF(p)
- n>1
Finite fields of Order p
- For a given prime p, finite field of order p, Gf(p) as the set Zp of integers {0,1…p-1} together with the arithmetic operations modulo p.
- Zp is a commutative ring, with the arithmetic operations modulo p.
- Any integer in Zp has multiplicative inverse if and only if that integer is relatively prime to p.
- If p is prime, then all nonzero integers in Zp are relatively prime to p so for all elements multiplicative inverse exist.
GF(2) – addition is equivalent to XOR and multiplication is equivalent to logical AND.
+ | 0 | 1 | ||
0 | 0 | 1 | ||
1 | 1 | 0 | ||
x | 0 | |||
0 | 0 | 0 | ||
1 | ||||
1 | 0 |
Finding the multiplicative inverse in GF(p)
- if a and b are relatively prime, then b has a multiplicative inverse modulo a.
- For positive integer b<a there exists b-1<a such that bb-1=1 mod a.
if by mod a=1 then y=b-1
Addition modulo 5 GF(5)
- For a given prime p, finite field of order p, GF(p), as the set of Zp of integers [0,1,…,p-1} together with the arithmetic operations modulo p.
- An integer in Zp has a multiplicative inverse, if and only if that integer is relatively prime to p.
- If p is prime, then all nonzero integers in Zp are relatively prime to p and therefore there exists a multiplicative inverse for all nonzero integers in Zp.Multiplicative inverse(w-1) For each wεZp , w≠0, there exist a zεZp such that wxz≡1(mod p). GF(p) has following properties
- GF(p) consists of p elements
- The binary operations + and x are defined over set. The operations of addition, subtraction, multiplication and division can be performed without leaving the set. Each element of the set other than 0 has a multiplicative inverse.
Suggested Reading:
- Cryptography and Network Security Principles and Practice by William Stallings, sixth Edition, PEARSON.
- Security in Computing by Charles Pfleeger & Shari Lawrence Pfleeger, fourth Edition, PEARSON.
- Network Security by Charlie Kaufman, Radia Perlman, Mike Speciner, second Edition, PHI.
- The Complete Reference – Network Security by Roberta Bragg, Mark Rhodes-Ousley & Keith Strassberg, Tata McGraw Hill
- Network Security Bible by Eric Cole, Ronald Krutz, James Conley, Wiley
- Hacking 6 Exposed by Stuart McClure, Joel Scambray & George Kurtz , Tata McGraw Hill .
- www.snort.org
- https://nmap.org