Mathematical Background of Cryptography

Group Theory

Group: A group is a set together with a law of composition that has the following properties:

• Associative Law The law of composition is associative: for all in .
• Identity Law contains an identity element , such that and for all in .
• Inverse Law Every element of has an inverse, an element such that and .

if, in addition, composition satisfies the

• Commutative Law , for all .

then the group is called a commutative group or an abelian group.

群的定义：设 是一个非空集合，在上定义了一个二元运算，若满足下面条件，则称为一个群。

• 对于任意的，有
• 在中存在一个元素，它对中的任意元素，有
• 对于中任意元素都存在中的一个元素使

定义10-1： 有限循环群是交换群（对于所有的元素都有）.

定义10-2：素数阶群没有真子群；是循环群。

定义10-3：为阶有限循环群，则的统计生成元共有（欧拉函数）个。（)）。即，小于的整数中与互质的数的个数。

定理10-4：阶有限循环群，若,则存在阶子群并且是唯一的；也是循环群。

Multiplicative Order: In number theory, given an integer and a positive integer with , the multiplicative order of a modulo is the smallest positive integer with .

Conjugate: Let be a group. Two elements are conjugate if there exists an element such that , in which case is called a conjugate of and is called a conjugate of .

Normal subgroup: In abstract algebra, a normal subgroup (also known as an invariant subgroup or self-conjugate subgroup) is a subgroup that is invariant under conjugation by members of the group of which it is a part.

Quotient group: A quotient group is a mathematical group obtained by aggregating similar elements of a larger group using an equivalence relation that preserves some of the group structure.

Multiplicative group of integers modulo : In modular arithmetic, the integers coprime (relatively prime) to from the set of non-negative integers form a group under multiplication modulo , called the multiplicative grokup of integers modulo . Equivalently, the elements of this group can be thought of as the congruence classes, also known as residues modulo , that are coprime to . Hence another name is the group of primitive residue classes modulo .

Lagrange's Theorem: Let be a finite group and let . Then the order of a divides the order . More precisely, let be the order of and let be the order of , i.e., is the smallest positive power of that is equal to . Then

The Chinese remainder theorem: Let be a collection of pairwise relatively prime integers. This means that

Definition of Ring: A ring is a set that has two operations, which we denote by and , satisfying the following properties:

• Properties of

  • Identity Law There is an additive identity such that for every .
  • Inverse Law For every element there is an additive inverse such that .
  • Associative Law for all .
    
  • Commutative Law for all ,

(Breifly, if we look at with only the operation , then it is a commutative group with (additive) identity element .)

• Properties of

  • Identity Law There is a multiplicative identity such that for every .
  • Associative Law for all .
  • Commutative Law for all

• Property Linking and

  • Distribution Law for all .

Definition of Field: A (commutative) ring in which every nonzero element has a multiplicative inverse is called a field.

Definition A partially ordered set in which any two elements have a supremum and an infimum is called a lattice.

Definition A lattice satisfying below is said to be modular.

Definition of Categories: A Category consists of a class of objects and a class of morphisms or maps. With each morphism two objects are associated, its source and target; if they are respectively, we write or and say: goes from to . The collection of all morphisms from to is written or simply . These objects and morphisms are subject to the following rules:

• is a set and unless and .
• If , so that and are both defined, then .
• For each object there exists a morphism such that for each , we have .

Definition A left R-module consists of an abelian group and an operation such that for all in and in , we have

• 1 x = x.

Definition of Polynomial Ring: Let be a ring. A polynomial in the indeterminate and with coefficients in is a finite linear combination of nonnegative 'power' of with coefficients in :

where all are elements of (the coefficients) and we requires for . Two polynomials are taken to be equal if all the coefficients are equal:

The set of polynomials in over is denoted by .

Definition Let be a ring. A subgroup of is a left-ideal of if for all ; that is,

Notation For we let

that is, denotes the set of integer multiples of .

Notation Let be a positive integer. Consider the equivalence relation on defined by

This is called congruence modulo . The set of equivalence classes is often denoted by , , . We will denote by the equivalence class of the integer modulo , or simply if no ambiguity arises.

Notation The degree of a nonzero polynomial , denoted , is the largest integer for which .

References

[1]

[2]