注：本文是作者学习周福才、徐剑《格理论与密码学》所做，仅供学习交流，转载请注明出处。
数学基础1
定义1.1 设a, b是整数，b≠0。若存在整数c，满足a=bc，则称b整除a或a被b整除，记为b|a。
命题：若a, b, c∈Z，且a|b，a|c，则a|(b+c)且a|(b-c)。
定义1.2 最大公因子是满足d|a，d|b的最大的正整数d，用gcd(a, b)来表示。
定理（扩展的欧几里得算法）设a, b是正整数，存在u, v满足 au+bv=gcd(a,b)。
模运算
定义1.3 设m为自然数，a和b是任意整数，如存在关系a=b+km，其中k为整数，则定义a≡b(modm)，其含义为：b是a除以m的余数（b为a模m的余数，或a与b模m同余）。
例如：(7+8)mod12=15mod12=3，也可以表示成：15≡3(mod12)
模运算（+，-，*）满足交换律、结合律和分配率。
命题 设整数m≥1，则有
（1）若a1≡a2(modm)，b1≡b2(modm)，则a1±b1≡a2±b2(modm)，且a1·b1≡a2·b2(modm)。
（2）设a为整数，当且仅当gcd(a, m)=1时，存在整数b满足a·b≡1(modm)。若这样的b存在，称其为a模m的乘法逆元。
对a做带余除法a=m·q+r, 0≦r<m。若要研究模m的整数，只需要取0≦r<m即可。由此引出同余类的概念。
定义1.4 记整数模m同余类环为 Z/m Z={0,1,2,···,m-1}
定义1.5 由命题（2） 若gcd(a,m)=1，则a存在模m的乘法逆元。这种具有逆元的元素成为单位，用如下记号来表示所有单位构成的集合： （Z/m Z）*={a∈Z/m Z: gcd(a,m)=1} 集合(Z/m Z)*称为整数模m单位群。
例：整数模24单位群为(Z/24 Z)*={1,5,7,11,13,17,19,23}；整数模7单位群为(Z/7 Z)*={1,2,3,4,5,6}。
定义1.6 欧拉函数表示(Z/m Z)*中元素的个数，记为 Φ(m)=#(Z/m Z)*=#{0≦a<m: gcd(a,m)=1}
