中国矿业大学：密码学_NTHEORY2（Group Theory and Number Theory for Cryptology）

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)

Examples of Groups The integers mod under addition G=ZN=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 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=Zn=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)=l and gcd(y p)=1 then GCD(xy p) · the identity is 1 the inverse of x is from euclids algorithm ux+ vp=1=GCD(x,p) u also x U= X multiplication is associative multiplication 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 ZN: the multiplicative group mod N G=ZN=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)=l and gCd(y, n)=1 then gCD(xy, n)=1 the identity is the inverse of x is from Euclids algorithm Ux+VN=1=GCD(X, N) SOX=u=Xp(N)-1 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 matric multiplication b GL(2)={Led」,adbe=0 if A and b are non-singular, So is aB the identity is I=[o1 I a c a /(ad-bc matrix multiplication is associative matrix multiplication is not commutative

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

S b subgroups H, @) is a subgroup of(G, @)if H is a subset ofg a is a grou

Subgroups (H,@) is a subgroup of (G,@) if: • H is a subset of G • (H,@) is a group