refer 8.2

Groups

Definition 8.2.1 Group

A group is a set of elements G together with an operation ◦ which combines two elements of G. A group has the following properties.

Note:

in cryptography we use both multiplicative groups, i.e., the operation “◦” denotes multiplication, and additive groups where “◦” denotes addition. The latter notation is used for elliptic curves as we’ll see later. Roughly speaking, a group is set with one operation and the corresponding inverse operation. If the operation is called addition, the inverse operation is subtraction; if the operation is multiplication, the inverse operation is division (or multiplication with the inverse element).

Closure

The group operation ◦ is closed. That is, for all a,b,∈ G, it holds that a ◦ b = c ∈ G.

Associative

The group operation is associative 结合律 . That is, a◦(b◦c) = (a◦b)◦c for all a,b,c ∈ G.

Note: associative is non trivial

例1:

x1 x2 x3
x1   x1◦x2  
x2     x2◦x3
x3      

假设G只有三个元素 x1 x2 x3

(x1◦x2)◦x3 根据闭合属性,x1◦x2 的值肯定是属于G也就是x1/x2/x3其中一个,所以 (x1◦x2)◦x3的值就落在最后一列

x1◦(x2◦x3) 同理,(x2◦x3) 的值也是属于G也就是x1/x2/x3其中一个,所以其值落在第一行

可见想让第一行的某个值和最后一列的某个值相等并不是显而易见的事情,所以说non trivial

例2:

集合set {a, b},定义set permutation如下:

i(identity):

a->a

b->b

t(transform):

a->b

b->a

然后在此基础定义Group G={i, t},即将两个set permutation操作符号本身抽象为G的元素,

然后定义composition 操作,如

i◦t是指在t的基础上进行i操作:

a->b ->b

b->a ->a

=>

a->b

b->a

即i◦t=t

很容易得到

i t
i i t
t t i

很容易理解:

i◦t◦t = (i◦t)◦t = i◦(t◦t)

所以由此也可以看出Group定义中的Associativity也是一种元素排列的复杂数据结构

Neutrual/Identity element

There is an element 1 ∈ G, called the neutral element (or identity element), such that a ◦ 1 = 1 ◦ a = a for all a ∈ G.

Inverse

For each a ∈ G there exists an element a−1 ∈ G, called the inverse of a, such that a ◦ a−1 = a−1 ◦ a = 1.

Commutative(Abelian Group)

A group G is abelian (or commutative) 交换律 if, furthermore, a ◦ b = b ◦ a for all a,b ∈ G.

take above example, commutative means that in the table it’s symmetric down the diagonal line

Example: To illustrate the definition of groups

However, all of these groups do not play a significant role in cryptography because we need groups with a finite number of elements. Let us now consider the group Zn which is very important for many cryptographic schemes such as:

构造Group(Set=>Group)

假设自然数 natural number

n ∈ N = {1, 2, 3, 4, 5, 6, ……….}

Set集合 S1 S2 …….. Sn

n=1,S1 = {1}

n=2,S2 = {1,2}

如果通过Set构造Group呢?

构造1:Set Permutation (Symmetric Group)

n=2

集合set S2={1, 2},定义set permutation如下(1对1全映射 bijections,不能多对1):

i(identity):

1->1

2->2

t(transform):

1->2

2->1

然后在此基础定义Group G={i, t},即将两个set permutation Symbols操作符号本身抽象为G的元素,

然后定义composition 操作,如

i◦t是指在t的基础上进行i操作:

1->2 ->2

2->1 ->1

=>

1->2

2->1

即i◦t=t

很容易得到

i t
i i t
t t i

构造2:模运算 Theorem 8.2.1

The set Zn which consists of all integers i=0,1, . . . ,n−1 for which gcd(i,n) = 1 forms an abelian group under multiplication modulo n. The identity element is e = 1.

Example 8.3. If we choose n = 9, Zn consists of the elements {1,2,4,5,7,8}.

Multiplication table for Z9

× mod 9 1 2 4 5 7 8
1 1 2 4 5 7 8
2 2 4 8 1 5 7
4 4 8 7 2 1 5
5 5 1 2 7 8 4
7 7 5 1 8 4 2
8 8 7 5 4 2 1

从上面的表很容易看到定义的 1 3 5都满足,2不能直接从上表看出,但是也是满足的,至于4逆元也可以通过 extended Euclidean algorithm 来计算出

这不就是一种set permutation吗,

S={1 2 4 5 7 8}

permutation1: S*1 mod 9 结果映射 1 2 4 5 7 8

permutation2: S*2 mod 9 结果映射 2 4 8 1 5 7

。。。。。

其实更适合后面 Cayley’s theorem, 对于 G={1 2 4 5 7 8} ,aG=G

Group的序 Size/Order

从上面两个例子可以看出,模运算的构造其实也是一种Set Permutation!

本质都是Set集合一对一的全排列,

比如Sn:

1,2,3…….n 映射到 1,2,3…….n

从1开始,1有n种选择,2有n-1种……..

总共

~~Sn的序 Order = Sn = n(n-1)(n-2)…..1 = n!~~

其实应该是Sn构造的Group的序 = n(n-1)(n-2)…..1 = n!

Symmetric Groups

上面例子通过Set Permutation构造的Sn就是Symmetric Group,

注意S1和S2比较简单,都满足communitative,所以都是abliean group,

但是S3不满足!

所以Symmetric Group不一定是abliean group

定义:

In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operations is the composition of functions. In particular, the finite symmetric group Sn defined over a finite set of n symbols consists of the permutations that can be performed on the n symbols.

举例:

S3

i t12 t13 t23 σ σ2
1->1
2->2
3->3
1->2
2->1
3->3
1->3
2->2
3->1
1->1
2->3
3->2
1->2
2->3
3->1
1->3
2->1
3->2
i t12 t13 t23 σ σ2
i i t12 t12 t23 σ σ2
t12 t12   σ2      
t13 t13 σ        
t23 t23          
σ σ          
σ2 σ2          

t12 ◦ t13 = σ2

t13 ◦ t12 = σ

所以S3不是abelian group

Cyclic Groups

假设自然数 natural number

n ∈ N = {1, 2, 3, 4, 5, 6, ……….n}

跟Sn类似,这次用 Cn 表示,Cn构造的Group的元素也类似前面的Set Permutation,这次换成了 Cyclic Permutation:

想象一个圆盘/钟表,将其按照360度/n等分为n份,从刻度1开始,下一个刻度2,。。。。直到n,

比如n=2,就是12点钟刻度位置放1,6点钟刻度位置放2

然后,Cyclic Permutation就是rotate旋转圆盘(每次旋转360/n),所以

旋转0次:

1->1 2->2 ………….n->n 用i表示

旋转一次就是:

1->2 2->3 ……….n->1 用σ 表示

旋转两次

1->3 2->4………..n-1->1 n->2 用σ2 表示

……

旋转n-1次

1->n 2->1 ……….n->n-1 用σn-1 表示

首先这种构造满足Group的定义:

1) closure, x,y ∈ Cn x◦y ∈ Cn

证明:Cn包含了所有的Cyclic Permutation/rotation的可能性,所以任意的xy组合也一定属于Cn

2) Associativity

3) Identity: i 旋转0次

4) Inverse ∀ g ∈ Cn, ∃ g-1∈ Cn, s.t. g◦g-1=g-1◦g=i

证明:假设g是旋转m次,即 m(360/n),其inverse就是(n-m)(360/n),因为两者加起来就是旋转360度,相当于旋转0度,即等于i

5) 并且还满足commutative,即Cyclic Group必然是Abelian Group

证明:x◦y和y◦x都是代表总共旋转x+y次,所以结果是一样的

容易得到, Cn 的序=n 也就是所有的Cyclic Permutation总共有n种可能,可以联想之所以set Permutation是n阶乘,而这里是n,主要是这里1 2 3。。。。n这些元素是联动的,也就是当1旋转到了2,2必然对应3,而set Permutation中可以自由选择

举例:

C4

i σ σ2 σ3
1->1
2->2
3->3
4->4
1->2
2->3
3->4
4->1
1->3
2->4
3->1
4->2
1->4
2->1
3->2
4->3
i σ σ2 σ3
i i σ σ2 σ3
σ σ σ2 σ3 i
σ2 σ2 σ3 i σ
σ3 σ3 i σ σ2

Dihedral Groups

假设自然数 natural number

n ∈ N = {1, 2, 3, 4, 5, 6, ……….n}

这次用 Dn 表示

这次的Permutation是在rotation/Cyclic Permutation的基础上增加了flipping,按照对称轴翻转,

比如 {1,2,3,4}就可以按照1-3 2-4两条对称轴+12和34间的轴线+14和23之间的轴线,总共4条对称轴,

对于{1,2,3,4,5} 五条对称轴则都是穿过每个数字

所以

Dn =n(cyclic permutation)+n(flipping) = 2n

那么Cyclic Permutation和flipping结合起来呢?结论是也会落在这2n个可能性里面

D1=S1, D2=S2, D3=S3

但是D4!=S4而是介于 C4和S4之间,当然D4不是abelian Group

Dn不是abelian group

Klein 4 Group

n {1, 2, 3, 4}

V = Klein 4 Group = {i, t12, t34, D}4

i t12 t34 D
1->1
2->2
3->3
4->4
1->2
2->1
3->3
4->4
1->1
2->2
3->4
4->3
1->2
2->1
3->4
4->3
i t12 t34 D
i i t12 t34 D
t12 t12 i D t34
t34 t34 D i t12
D D t34 t12 i

Group Isomorphisms

G = S2 = {i, t}

G’= {+1, -1}

G和G’ 两者除了符号不同,性质相同,可以relabeling

i<->+1

t<->-1

G&G’ are isomorphic if exists:

φ: G<->G’ φ is bijective

for ∀ x,y ∈ G, φ(x ◦ y) = φ(x) ◦ φ(y)

G y ….
     
x   x ◦ y  
     
G’ φ(y)
     
φ(x)   φ(x) ◦ φ(y)  
     

注意:order相同的两个group未必是isomorphic的,比如 C4和Klein 4 group,对比两者的 i 明显规律不同!klein 4 group的每个元素都是自己跟自己互逆,而C4则不是

Isomorphism Class:

taking all groups that are isomorphic to one another and sticking them into a great big class, all of them are just the equivalent algebraic structure but with difference symbols used to denote the different elements of the group

举例:

G:

(R, +) 实数是Filed,不过这里只考虑其在加法结构上的Abelian Group结构

G’:

(R+, *) R+ = {x ∈ R x > 0 } 正实数在乘法结构上是Abelian Group

φ: G->G’

x,y ∈ G, ◦ 是 +, x ◦ y = x + y

φ(x),φ(y) ∈ G’, ◦ 是 *, φ(x) = ex, φ(y) = ey

for ∀ x,y ∈ G,

φ(x ◦ y) = φ(x + y) = ex+y= exey = φ(x)φ(y) = φ(x) ◦ φ(y)

Subgroups

H ⊂ G 或 H < G , every subgroup is a subset

closure for H suddenly becomes non-trivial, because it’s hard to say that for ∀ x,y ∈ H, x ◦ y also ∈ H not outside of H

H需要包含G的identity

two trivial sub group:identity & the entire group

例子1:

S3= { i, t12, t13, t23, σ, σ2 }

C3 = { i, σ, σ2 }

C3 ⊂ S3

H = { i, t12 } (isomorphic to S2)

H ⊂ S3

例子2:

Integer Z= {0, 1, -1, 2, -2, ……….}

aZ = {za z ∈ Z } = { 0, a, -a, 2a, -2a, …….}

aZ ⊂ Z

0Z = {0} 1Z = Z 刚好是Z的two trivia sub group

如何证明aZ也是group?

closure: 利用ring的分配律(因为Integer是ring):za+z’a = (z+z’)a = z’‘a, z’‘=z+z’ ∈ Z, z’‘a ∈ aZ

其他 associative inverse identity都很显然

结论:H < Z and b ∈ H and b is the smallest positive integer, prove that H = bZ ⊂ Z

证明:

先证明 bZ ⊂ H

b存在inverse -b,b+b=2b…………从而构造出

{0, b, -b, 2b, -2b, ……} 如果任何一个元素不存在与H中,那么H就不是闭合的,就不是group,所以bZ ⊂ H

再证明H can’t contain any other integers that are not within the set bZ

let a ∈ H but not in bZ, so:

if a<b, contradict to b is the smallest integers;

if a>b, then a = zb + r, z ∈ Z and b>r>0 (if r=b then a=(z+1)b, contradict to a not in bz)

=> r = a + (-zb) , because a ∈ H, -zb also ∈ H, so we have r ∈ H, contradict to b is the smallest integers

结论:it’s impossible for a finite group to be isomorphic to it’s subgroup, however in infinite group very that’s not the case.

aZ isomorphic to Z

aZ = {za z ∈ Z }

φ: aZ -> Z

for ∀ x,y ∈ G, φ(x) = x/a

φ(x ◦ y) = φ(x + y) = φ(za+z’a) = φ((z+z’)a) = z+z’

φ(x) ◦ φ(y) = φ(x) + φ(y) = φ(za) + φ(z’a) = z+z’

结论:subgroup intersection交集也是subgroup

H1,H2 < G ,H1 ∩ H2 < G

H1 ∩ H2 = { g ∈ G g∈H1,g∈H2 }

证明H1 ∩ H2是group即可:

首先不需要担心associativity 因为很显然如果其交集不遵守的话,H1和H2也就不是group,identity也显然即存在于H1又存在于H2,主要看其他几个性质:

关于closure, for ∀ x,y ∈ H1 ∩ H2 证明 xy ∈ H1 ∩ H2,很简单由于 x,y ∈ H1,所以xy ∈ H1,同理xy ∈ H2,得证

关于inverse,∀ x ∈ H1 ∩ H2,证明 x-1 ∈ H1 ∩ H2,跟closure的证明一样x ∈ H1,所以x-1 ∈ H1 ,同理x-1 ∈ H2

Cyclic Groups and subgroups

finite & infinite Cyclic group

n ∈ N = {1, 2, 3, 4, 5, 6, ……….n}

Cyclic Permutation就是rotate旋转圆盘(每次旋转360/n),所以

旋转0次:

1->1 2->2 ………….n->n 用i表示

旋转一次就是:

1->2 2->3 ……….n->1 用σ 表示

旋转两次

1->3 2->4………..n-1->1 n->2 用σ2 表示

……

旋转n-1次

1->n 2->1 ……….n->n-1 用σn-1 表示

前面是finite Cyclic group,

但是如果我们假设研究infinite Cyclic group,比如整个自然数就会在旋转一次的时候遇到问题:

1->2 2->3 ………. 由于是整个自然数,无法得到自然数的最后一个数让其指向1,所以无法实现Permutation,

现在考虑更大的集合 Integer 整数,Z = { 0, 1, -1, 2, -2, …….}

旋转一次就是:

….. -3->-2 -2->-1 -1->0 0->1 1->2 2->3 …………….. 现在随便找一个Integer 都能找到其对应的map

但是现在又有个问题,前面的finite Cyclic group Cn当旋转n-1次相当于逆时针旋转1次,旋转a次的逆是n-a次,旋转n次就回到了i,但是这里因为是infinite,如果向一个方向旋转是回不到i的,所以这里需要引入反方向的旋转,反方向旋转一次:

….-2->-3 -1->-2 0->-1 1->0 2->1 3->2…………

现在定义一组新的符号:

identity:0

顺时针(向右旋转)一次:+1

逆时针(向左旋转)一次:-1

{ 0, 1, -1, 2, -2,…… } 神奇的发现产生的这个infinite Cyclic group跟我们考虑的整个Integer Z是完全一样的

Cyclic Subgroup

for cyclic group G, x ∈ G (x is not identity element), <x> called Cyclic subgroup generated by x

<x> = {e, x, x2,x3…………. x-1, x-2……} 根据group的性质,肯定包含identity,e= x0,然后根据闭合性质,x跟自己compose成 x2(参考前面Cyclic Permutation的例子,相当于旋转两次),接着生成 x3等,并且每个元素都存在逆

注意:如果G是finite group,那么subgroup <x> 也必然是finite group(x的某个次幂=e),如果<x> 是infinite group,G必然也是infinite group

我们下面考虑 infinite group的情况,证明<x> 是group:

closure 闭合:∀ a,b ∈ Z (<x> 元素的次幂是Integer)

x ◦ xb = xa+b

xa = x ◦ x ……..◦ x 表示x compose自己a次,所以xa ◦ xb就是x compose with自己a+b次,所以是满足闭合

inverse显然存在,

例子:

for (Z,+) Integer under addition,

<2> = { 0, 2, 4, 6…….., -2, -4, -6……….} = 2Z(前面subgroup举例的aZ)

结论:infinite Cyclic subgroup is always isomorphic to the infinite Cyclic group

<x> isomorphic to (Z,+)

<x> = {e, x, x2,x3…………. x-1, x-2……}

φ: <x> ->(Z,+) , φ(xn) = n

for ∀ a,b ∈ <x>,

φ(a ◦ b) = φ(xm ◦ xn) = φ(xm+n) = m+n

φ(a) ◦ φ(b) = φ(xm) + φ(xn) = m + n φ(a ◦ b)= φ(a) ◦ φ(b) 得证

finite Group

<x> = {e, x, x2,x3………….}

if <x> is finite group, then must exist m∈N is the smallest that give an entry that already had(start cyclic), so that<x> = {e, x, x2, x3, ……xm-1 }, and it must be xm = e

Prove:

suppose xm = xn ∈N and n<m

(x-1)n xm = (x-1)n xn

=> xm-n = e this contradict to m is the smallest that give an entry that already had

不难证明 <x> = {e, x, x2, x3, ……xm-1 } 是一个group,满足group的属性:

closuer: xa ◦ xb = xa+b if a+b<m显然属于<x>, 等于m则 xm = e ,大于m比如介于(m,2m)则 xa ◦ xb = xm(xr)=xr r<m

inverse: 根据 xm = e => x1 ◦ xm-1 = e 找到complementary power即可

结论: <x> = {e, x, x2, x3, ……xm-1 } is isomorphic to Cm = {e, σ1, σ2, ……., σm-1}

由上述得出Cyclic Group 定义

Cyclic group both the finite and infinite cyclic groups what they contain basically is they need to contain an element x ∈ C such that the subgroup group generated by x <x> is actually equal to the entire group

<1> = { 0, +1, +2, +3……., -1, -2, -3,……….}

Cayley’s theorem

引入

前面讲了group的定义和属性,以及如何通过set Permutation来构造group,但是还没有回答一个问题就是:

so the questions now becomes is it the case that we can always think of a group as being a set of symbols where these symbols are representing set permutations of some set.

G={……..}

a ∈ G,

aG = {a◦g g ∈ G}
<—G—> every elements in G
 
a a◦g
….  
Ga = {g◦a g ∈ G}
a
<–   g◦a  
G every elements in G   g◦a  
–>   g◦a  

结论:aG = Ga = G for ∀ a ∈ G

for aG and Ga, every elements appear once and only once,

Prove:

首先根据Group闭合的性质,a ∈ G,所以aG ∈ G,然后:

先证明appear only once:

assume g<>g’ but a◦g = a◦g’

<—   G every elements in G —>
       
a   a◦g a◦g’  
….        

=> a-1◦a◦g = a-1◦a◦g’

=> g = g’ contradict to g<>g’

再来证明every elements appear once:

对于finite group来说,很简单,因为假设G的order是n,那么由于前面证明了g<>g’=>a◦g <> a◦g’ 所以aG产生的n个元素也各不相同,所以得证;

然后对于infinite group来说,由于是infinite,换种思路:

for 任意 g ∈ G,只要可以找到ax=g, x ∈ G不就可以了么

=> x=a-1g,所以对于任意g都可以找到x=a-1g 从而让ax=g 得证

凱萊定理

官方定义:

In group theory, Cayley’s theorem, named in honour of Arthur Cayley, states that every group G is isomorphic to a subgroup of the symmetric group acting on G.[1] This can be understood as an example of the group action of G on the elements of G.[2] The theorem can be obtained by explicitly constructing the representation within the representation of the symmetric group of permutation matrices, which is sometimes known as the regular representation.

A permutation of a set G is any bijective function taking G onto G. The set of all permutations of G forms a group under function composition, called the symmetric group on G, and written as Sym(G).[3]

解释:

for group G={e…..}

let’s just take the the symbols from the Group G (not taking the composition law, only the symbols), so we got a Set

S={e……}

this is the SET that we’re going to think of every element of the group as representing a set permutation of and the composition law is then going to represent the composition of those set permutations

take any g ∈ S, a ∈ G,

set permutation is bijective map from the SET to itself,

we define **set permutation: a(g) **

and because g ∈ S, and it’s the same symbol from group G, so we can have:

a(g) = a ◦ g,前面已经证明了 aG=G,every elements appear once and only once,所以必然是双射

then we can define a new composition law based on this set permutation, it will be the same composition as the Group G

<———G———->
e <———G———->
 
a <———aG———->
 

eG 就像之前set Permutation的i

aG 就像之前set Permutation的其他双射 比如之前研究过的t12 ,σ

然后我们定义新的composition就是set Permutation的composition,换句话就是对 i t12 σ这些符号所对应的set Permutation的composition law,当然我们这里不需要使用这些符号了,可以直接用 我们定义的 **set permutation: a(g) **g ∈ S, a ∈ G,假设新的composition符号是&

所以对于∀ a,b ∈ G,a&b就代表 先进行set Permutation:b(g),g ∈ S, b ∈ G,然后再进行set Permutation:a(b(g)), b(g) ∈ S, a ∈ G

进而我们可以证明实际上这个a&b = a(b(g)) 等同于 a和b先在G上composite a◦b,然后再进行我们定义的set Permutation (a◦b)(g), g ∈ S, a◦b ∈ G,即:

(a◦b)(g) = a(b(g))

很容易 根据我们的定义a(g) = a ◦ g 加上G上的associative性质即得证

但是注意,我们不可以定义set Permutation:a(g) = g ◦ a 虽然前面知道 Ga也是双射,但是

(a◦b)(g) = a(b(g)) 不成立,因为

(a◦b)(g) = g◦(a◦b) 而 a(b(g)) = a(g◦b) = (g◦b)◦a = g◦(b◦a) 但是我们知道对于group a◦b并不一定等于b◦a,只有abelian group才有这个属性

Cosets + Lagranges

G={……..}

a ∈ G,

aG = {a◦g g ∈ G}
Ga = {g◦a g ∈ G}

aG == Ga == G, every elements in the group appear once and only once

Quotient Groups

N < G, G/N

∀ n ∈ N

∀ g ∈ G

gng-1 ∈ N