加密算法——应用密码学数学引论

Ξ近代密码学理论设计数学领域基础包含：数论、群论。优先于理论、几双复杂性理论等数学知识。

数论：研究整数性质的一个数学分支，数论中许多概念是设计公开密钥密码算法的基础，数论研究重点是素数。

公钥密码最核心的内容—数论。

素数

除数：a = mb,a,m,b为整数，b≠0时，可以说b能整除a,即a除以b余数为0，记为b|a,一般只考虑非负整数。

素数：又称质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数，只能被1和它本身整除的整数。

算数基本定理：任何大于1的整数a都可以因式分解写成唯一的表达式（素数幂之积）如下所示。

素数定理：一个正整数n是素数，当且仅当它不能被任何一个整数d（1<d≤√n）整除。

最大公约数：a和b的最大公约数记为gcd(a,b) = d.

d满足两点—1、d是a和b的公约数；2、对a和b的任何一个公约数c，有c|d。

0能被所有非0整数整除，所以有gcd(a,0) = a(a>0).

gcd(a,b) = 1;则称a和b是互素的，即a和b互为素数。

模运算

带余除法

a mod n为a除以n的非负余数.

整数同余 ：如果a mode n =b mod n ,则称整数a和b模n同余，写为a ≡ b(modn)

notic : 如果a Ξ 0 mod n,则n|a。

模运算

模运算，模m运算可实现对所有整数进行分类，得到的整数集合称为剩余类集合Zm表示所有整数模m后得到的剩余类集合。