Mathmatic
这个章节下面会介绍一些在密码中会用到的数学知识。
Number Theory vs Group Theory
Number Theory: Number Theory is the branch of mathematic that deals with properties and relationships of numbers, particularly integers. It encompoasses the study of integers, prime numbers, divisibility, modular arithmetric, Diaphantine equations, and various number-theoretic funtions and sequences.
Key topics in number theory include:
- Prime numbers and factorization: Understanding the properties of prime numbers, prime factorization, prime factor decompositions, and ralated concepts like prime gaps and prime distribution.
- Diophantine equation: Solving equations that involve integer solutions, such as the famous Fermat's Last Theorem.
- Modular arithmetric: Examining arithmetic operations performed within a fixed modulus, including congruences, modular inverses, and Chinese remainder theorem.
- Number-theoretic functions: Investigating functions such as Euler's totient function, the Möbius function, and various arithemetic functions like the divisor function and the sum of divisors function.
Group Theory: Group theory is the branch of abstract algebra that studies algebraric structures known as groups. A group is a set equipped with an operation that combines any two elements and satisfies certain properties, including closure, associativity, identity element, and inverses. The concept of central to abstract algebra: other well-known algebraic structures, such as rings,fields,and vector spaces, can all be seen as groups endowed with additional operations and axioms.
Key topics in group theory include:
- Group properties: Investigating the fundamental properties of groups, such as closure, associativity, identity element, and inverses.
- Subgroups: Analyzing subsets of a group that form a group themselves.
- Group homomorphisms and isomorphisms: Studying mappings between groups that preserve the group structure.
- Cyclic groups: Exploring groups generated by a single element, known as generators.
- Permutation groups: Examining groups that represent permutations or rearrangements of a set.
Group theory has applications in various areas of mathematics, including algebraric structures, symmetry, geometry, cryptography, and physics.
Summary: In summary, number theory focuses on the properties and relationships of integers and their arithmetic, while group theory is concerned with the abstract algebraric structures knowns as groups and their properties.
Frequently used Number-Theory Lemmas in Cryptophy
- \( Z_N=\{0,1,\cdots,N-1\} \) for all positive integer, if integer eq or more than N , the result is integer mod N.
- \( Z_N^* \) is the multiplicative group modulo N. \( Z_N^* \) is a sub set of \(Z_N\) that values in the sub set is coprime to N , denoted as \( \{x\in Z_N | gcd(x,N)=1\} \)
- we use \( p|N \) to denote that "p divedes N"
- Euler's phi or totient funtion is defined for all positve integer N as:
\[ \phi(N)= |Z_N^*| \]
known as the order of \( Z_N^* \), or, equivalently, the number of items in \( Z_N^* \).
Specially if \( N=pq \) where p,q are two distinct primes it holds that: \[ \phi(N)=(p-1)(q-1) \] More generally, if the prime factorization of N is \( N=P_1^{\alpha_1} \times \cdots \times P_k^{\alpha_k} \), then \( \phi(N)=(P_1^{\alpha_1 -1} \times\cdots\times P_k^{\alpha_k -1}) \cdot ((P_1-1) \times\cdots\times (P_k-1)) \)
Rrequently used Group-Theory in Cryptophy
The order of group & the order of group element
The order of group is number of its elements.
The order of an element of a group(also called period length or period) is the order of the subgroup generated by the element. If the group operation is denoted as a multiplicaton, the order of the an element \( \alpha \) of a group, is thus the smallest positive integer m that \( \alpha^m=e \), where e denotes the identity element of the group.
负数取模
对负数的取模运算在不同的语言里面定义不一样，主要是除法的选择不一样（地板除，截断除），不过计算机在计算模运算的过程可以表示为： $$ a \bmod b= a- a/b \times b $$