Group Theory and Number
Theory for Cryptology
Irene Gassko and Peter Gemmell
Definition,Group
A set G of elements and operator @ form a group if,
? for all x,y in G,x @ y is also in G (inclusion)
? there is an identity element e such that for all x in G,e@x = x
? for all x in G,there is an inverse element x-1 such that x-1@x = e
? for all x,y,z in G,(x@y)@z = x@(y@z) (associativity)
? abelian groups have the property,for all x,y in G,x@y = y@x
Note,sometimes the group operator
may be denoted,*” or,+”,the identity denoted
“0” or,1” and the inverse of x,-x”,
Note 2,unless stated otherwise,we consider only abelian
groups
Examples of Groups
The integers under addition
G = Z = the integers = { … -3,-2,-1,0,1,2 …}
the group operator is,+”,ordinary addition
? the integers are closed under addition
? the identity is 0
? the inverse of x is -x
? the integers are associative
? the integers are commutative (so the group is abelian)
Examples of Groups
The non-zero rationals under multiplication
G = Q -{0} = {a/b} a,b non-zero integers
the group operator is,*”,ordinary multiplication
? If a/b,c/d are in Q-{0},then a/b * c/d = (ac/bd) is in Q-{0}
? the identity is 1
? the inverse of a/b is b/a
? the rationals are associative
? the rationals are commutative (so the group is abelian)
Examples of Groups
The non-zero reals under multiplication
G = R -{0}
the group operator is,*”,ordinary multiplication
? If a,b are in R-{0},then ab is in R-{0}
? the identity is 1
? the inverse of a is 1/a
? the reals are associative
? the reals are commutative (so the group is abelian)
Examples of Groups
The integers mod N under addition
G = Z+N = the integers modulo N = {0 … N -1}
the group operator is,+”,modular addition
? the integers modulo N are closed under addition
? the identity is 0
? the inverse of x is -x
? addition is associative
? addition is commutative (so the group is abelian)
Examples of Groups
The integers mod p under multiplication
G = Z*p = the non-zero integers modulo p = {1 … p -1}
the group operator is,*”,modular multiplication
? the integers modulo p are closed under multiplication,
this is so because if GCD(x,p) =1 and GCD(y,p) = 1
then GCD(xy,p) = 1
? the identity is 1
? the inverse of x is from Euclid’s algorithm,
ux + vp = 1 = GCD(x,p)
so x-1 = u
also x-1 = u = xp-2
? multiplication is associative
? multiplication is commutative (so the group is abelian)
Examples of Groups
Z*N, the multiplicative group mod N
G = Z*N = the positive integers modulo N relatively prime to N
the group operator is,*”,modular multiplication
? the integers modulo N are closed under multiplication,
this is so because if GCD(x,N) =1 and GCD(y,N) = 1
then GCD(xy,N) = 1
? the identity is 1
? the inverse of x is from Euclid’s algorithm,
ux + vN = 1 = GCD(x,N)
so x-1 = u (= x f(N)-1)
? multiplication is associative
? multiplication is commutative (so the group is abelian)
Examples of a non-abelian group
GL(2),2 by 2 non-singular real matrices
under matrix multiplication
? if A and B are non-singular,so is AB
? the identity is I = [ ]
?
= /(ad-bc)
? matrix multiplication is associative
? matrix multiplication is not commutative
GL(2) = {[ ],ad-bc = 0} a b c d
1 0
0 1
[ ]a b c d -1 [ ] d -b -c a
Subgroups
(H,@) is a subgroup of (G,@) if,
? H is a subset of G
? (H,@) is a group
Subgroups
Example
Let G = Z*7 = {1,2,3,4,5,6} = the multiplicative group modulo 7
Let H = {1,2,4} (mod 7) … a subset of G
Note,
1,H is closed under multiplication modulo 7
2,1 is still the identity
3,1 is 1 inverse,2 and 4 are inverses of each other
4,associativity still applies
5,commutativity still applies
H is a subgroup of G
Subgroups
Example
Let G = R-{0} = the non-zero reals under multiplication
Let H = Q-{0} = the non-zero rationals under multiplication
H is a subset of G and G,H are groups
H is a subgroup of G
Group order
The order of a group (G,@) equals the
size of set G
Notation,order(G),ord(G),|G|
Group order
example
order(Z+N) = N
order(Z*N) = f(N)
For all N,
Order of an element
Let x be an element of group G
The order of x is the least positive number k such that
xk= 1
Notation,order(x),ord(x)
Order of an element
Example,Z*7,the multiplicative group modulo 7
Z*7 = {1,2,3,4,5,6}
order(1) = 1 because 11 = 1
order(2) = 3 because 23 = 8 = 1 and 3 is the smallest such number
order(3) = 6 because 36 = 93 = 23 = 1 and 6 is …
order(4) = 3 because 43 = 64 = 1 and 6 is …
order(5) = 6 because 56 = 253 = 43 = 1 and 6 is …
order(6) = 2 because 62 = 36 = 1 and 6 is,.,
Theorem
For all groups G and every element x of G,
order(x) divides order(G)
Generated Sets
Let (G,@) be a group and let S = {s1,…,s k} be a subset of G
Define by <S> all elements of the form s1i1… s kik
where i1,…,i k are integers
<S> is the set generated by S
Lemma
For any subset S of group (G,@),
<S> is a subgroup of G
Proof,
Recall <S> = {s1i1… s kik } where i1,…,i k are integers
So,
? <S> is closed under @
? 1 is the identity
? (s1i1… s kik ) -1 = s1-i1… s k-ik
? associativity,commutativity still hold
Generated Groups
Example
Let G = Z*7 = {1,2,3,4,5,6} = the multiplicative group modulo 7
Let H = {1,2,4} (mod 7) … a subgroup of G
Let S = {2},Then <2> = {2i} for integers i
23 = 1 implies that <2> = {1,2,4} = H
2 generates the subgroup H of G
Generated Groups
Example
Let G = Z*7 = {1,2,3,4,5,6} = the multiplicative group modulo 7
Let S = {3},Then <3> = {3i} for integers i
36 = 1 implies that <3> = {1,3,2,6,4,5} = G
3 generates G
Fact
For every group G and element x of G,
order(x) = |<x>|
Cyclic groups
Let (G,@) be a group such that there exists an
element x of G such that G = <x> (“x generates G”)
Then G is a cyclic group
Cosets
Let (G,@) be a group and (H,@) be a subgroup of G
Let x be an element of G
xH = {xy,y in H} is a (left) coset of H
respect to G
Cosets
Lemma
Let H be a subgroup of G and let x,y be elements of G
Either xH = yH or xH and yH are disjoint
If xH = yH,then there are v,w in H such that xv = yw
Let z = xu be any element of xH,Then z = xu = ywv-1u
must be an element of yH because w,v-1,and u are elements
of H,This shows that xH is a subset of yH,A similar
argument shows that yH is a subset of xH,
proof,
Cosets
Lemma
Let H be a subgroup of G and let x be an element of G
Then |xH| = order(H)
proof,
Assume xH is not equal to H,For every element v in xH,
there is exactly 1 element h = x-1v in H such that v = xh,
Because of this 1-to-1 mapping,we have |xH| = |H|
corollary,order(H) divides order(G)
Euclid’s algorithm
to compute GCD(x,y)
example,GCD(68,24)
68 = 2(24) + 20
24 = 20 + 4
20 = 5(4)
GCD(68,24) = 4
Euclid’s algorithm
to compute GCD(x,y)
Definition of the algorithm
Assume x > y
let x = a1 y + b1 where b1 < y
let y = a2 b1 + b2 where b2 < b1
let b1 = a3 b2 + b3,.,
For the first i such that bi+1 = 0,we have GCD(x,y) = bi
Euclid’s extended GCD algorithm
to compute GCD(x,y),u,v,
where ux + vy = GCD(x,y)
Assume x > y
let x = a1 y + b1 where b1 < y
let y = a2 b1 + b2 where b2 < b1
let b1 = a3 b2 + b3
For the first i such that bi+1 = 0,we have GCD(x,y) = bi
Euclid’s extended GCD algorithm
to compute GCD(x,y),x-1 mod y,and
y-1 mod x
Problem,
A set G of elements and operator @ satisfy,
? for all x,y in G,x @ y is also in G (inclusion)
? there is an identity element e such that for all x in G,e@x = x
? G is finite
? For all x,y,z in G,if x@y = x@z,then y = z
? for all x,y,z in G,(x@y)@z = x@(y@z) (associativity)
Show that (G,@) is a group