Group Theory and Number Theory for Cryptology rene gassko and Peter gemmell
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 ing(inclusion) there is an identityelement e such that for all x in G, e ax=x for all x in G, there is an inverse elemental such that x lax=e for all, y, z in G,(x@yaz=x@(y(@z)(associativity) abelian groups have the property: for all x,y in G, x@y=yax Note: sometimes the group operator may be denoted“*”Or“+”, the identity denoted “0or“1 and the inverse of x“-x2 Note 2: unless stated otherwise. we consider only abelian groups
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 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 "x,, ordinary multiplication If a/b, c/d are in Q-10), thena/b * c/d=(ac/bd) is in Q-10) the identity 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 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 the group operator is"x>, ordinary multiplication If a, b are inR-109, then ab is inR-10) the identity the inverse of a is 1/a the reals are associative the reals 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)