密码学算法需要用到很多数学知识，主要包含数论和代数（群论、环论、有限域），本文主要讲述数论。

一些常见的数集表示符号

通常用大写的、、、分别表示整数、有理数、实数和复数集合。有时候还会用到自然数集，其实就是。

整除性理论

定义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。
定义3：如果两个整数a和b的最大公因子为1，则称它们互素。
例：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的关系为：
其中：


可以得到：


素数理论

定义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 ，那么：。

同余理论

定义5：对于给定的正整数c，称整数a和b模c同余，指的是，记作。
  • 容易看出整数a和b模c同余的本质是用a和b分别除以c得到的余数相同。
  • 用a mod c表示a除以c的余数，mod称为模运算。
  • 例如：，，

同余关系的性质：
（1）传递性：若，，则
（2）对称性：若，则
（3）反身性：总有
（4）可加性：若，则
（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个数。
定理4（欧拉定理） 设m是大于1的整数，正整数a满足条件(a, m)=1，则：

定理5（费马小定理）若p是一个素数，a是任意正整数，那么