密码学数学基础之数论
密码学算法需要用到很多数学知识，主要包含数论和代数（群论、环论、有限域），本文主要讲述数论。
一些常见的数集表示符号
通常用大写的
、
、
、
分别表示整数、有理数、实数和复数集合。有时候还会用到自然数集
，其实就是
。
整除性理论
定义1：如果整数a, b, c满足关系a=bc，且b不为0，则称b整除a或者a能被b整除，称b是a的因子（或者因数），a是b的倍数，用符号记作b|a。
例：因为15=3x5，所以3|15，5|15。
例：因为-20=-2x10，所以-2|-20，10|-20。
一个常用结果：如果a|b且a|c，那么对任意整数x和y，a整除xb+yc。
定义2：两个整数a和b的最大公因子是满足以下两个条件的正整数d：
- （1）d是a与b的公共因子，即d|a且d|b。
- （2）如果c也是a与b的公共因子，则c一定是d的因子。
- a和b的最大公因子记为GCD(a, b)，或者(a, b)。
- (a, b)就是a和b的公共因子集合中最大的整数。
- 例：10和15的最大公因子为5；28和16的最大公因子为4。
例：14和15互素，2和9互素。
定理1（带余除法）：对于任意的整数a和b，其中b>0，一定存在唯一的一对整数k和r，其中r大于等于0，小于b，满足a=kb+r。
例：设b=5，则当a=83时，有a=kb+r=16*5+3。
欧几里得算法（辗转相除法）
利用带余除法求两个整数a和b的最大公因子的过程。
- 给定两个正整数a和b，假定a大于b，由带余除法，可以得到：
-
其中
就是a和b的最大公因子。
例：取a=121，b=25，利用欧几里得算法可以得到以下等式：
121=4x25+21；
25=1x21+4；
21=5x4+1；
4=4x1
因此得到(121,25)=1
定理2：对于任意两个正整数a和b，存在两个整数s和t，使得(a,b)=sa+tb。
求s和t的过程一般称为扩展的欧几里得算法。
余数
与a和b的关系为：%5E%7Bi-1%7Dr_%7Bi%7D%2Ci%3D1%2C2%2C...%2Cn)
余数
其中：
可以得到：
素数理论
定义4：设p为不等于1的正整数，若p的因子只有1和p，则称其为素数，否则称p为合数。
寻找素数的一个最基本的方法称为筛法。
例：20以内的素数。
可以看出不超过20的素数分别为：2、3、5、7、11、13、17、19。
定理3（算术基本定理）
任意正整数a可唯一分解为若干素数的乘积。
其中
为不同的素数，
为正整数。分解式不考虑素数出现的先后顺序。
例：
推论1：给定素数p和n个正整数 ，如果
，至少存在一个
能被
整除。
推论2：互素的两个整数没有公共的素因子。
推论3：若p为素数，a是比p小的正整数，则一定有(a, p)=1，也就是a和p互素。
推论4：如果(a, b)=d ，那么：%3D1)
。
同余理论
定义5：对于给定的正整数c，称整数a和b模c同余，指的是
，记作)
。
- 容易看出整数a和b模c同余的本质是用a和b分别除以c得到的余数相同。
- 用a mod c表示a除以c的余数，mod称为模运算。
-
例如：
，
，
-
（1）传递性：若)
，)
，则)
（2）对称性：若，则)
（3）反身性：总有)
（4）可加性：若%2Cc%5Cequiv%20d(modn))
，则)
（5）可乘性：若，则)
（6）可约性：若，
，
，且d和n互素，则)
整数集合Z根据模m的余数不同分为m个子集合：
令
称其为整数模m剩余类，则：
整数模m剩余类的全体记作
，则
其中，
定义6：给定正整数m，从上述m个剩余类中各取一个整数组成的集合称为整数模m的完全剩余系。
最简单的模m完全剩余系为：
。
定义7：设n是正整数，则欧拉函数)
指的是小于n且与n互素的正整数个数。
例：小于6且与6互素的正整数有：1, 5，因此φ(6)=2。
例：小于7且与7互素的正整数有：1, 2, 3, 4, 5, 6，因此φ(7)=6。
例：若p是素数，则φ(p)=p-1。因为此时1, 2, …, p-1都与p互素。
如果整数模n的其中一个剩余类中的数都与n互素，我们就称这个剩余类与n互素。
定义8：给定正整数m，从与m互素的剩余类中各取一个整数组成的集合，称为整数模m的简化剩余系。
- 根据定义，整数模n的简化剩余系中包含φ(n)个整数。
- 整数模6的简化剩余系只有两个数，1和5是典型代表。
- 整数模一个素数p的简化剩余系有p-1个数。
定理5（费马小定理）若p是一个素数，a是任意正整数，那么
百度成长空间 412人发布
