模运算

几乎所有的加密算法都基于有限个元素的运算，而我们习惯的绝大多数数集都是无穷的。

模运算是在有限个整数集中执行算术运算的简单方法。

模运算的定义

假设a, r, m∈Z(其中Z是所有整数的集合)，并且m＞0。如果m除a-r, 可记作：
a≡r mod m
其中m称为模数，r称为余数。

余数的计算

总可以找到一个a∈Z，使得a=q×m+r。其中0≤r<m。也就是：a≡ r mod m。

余数不唯一

对任意给定的模数m和整数a，可能同时存在无数多个有效的余数。
例如：12≡3 mod 9,12≡21 mod 9,12≡-6 mod 9。

等价类中的所有成员的行为等价

对于一个给定模数m，选择等价类中任意一个元素用于计算的结果都一样。所以在固定模数的计算中，我们可以选择等价类中最易于计算的一个元素。

余数的选择问题

一般来说，我们会选择r满足0≤r<m-1条件的。但从数学角度看，选哪个都一样。

整数环

设有这样一个整数集合，它由0到m-1的整数，及这些整数之间的加法和乘法得到的数所组成。该整数集合对应的数学结构可以用环来表示。

整数环的定义

环的特征

1. 如果环内任意两个数相加或相乘得到的结果始终在环内，则这个环就是封闭的。
2. 加法和乘法满足结合性。即a＋(b+c)=(a＋b)＋c。a×(b×c)=(a×b)×c。
3. 加法中存在中性元素0，使得任意a都有a＋0≡a mod m。
4. 环中任何元素a都存在一个负元素-a，使得a＋(-a)≡0 mod m。即加法逆元始终存在。
5. 乘法中存在中性元素1，使得任意a都有a×1≡a mod m。如果a的乘法逆元存在，则可以做除法：b/a≡b×a^-1 mod m。
6. 找出某个元素的逆元比较困难，一般采用欧几里得算法，但也有一种简单的方法可以用来判断a的逆元是否存在：gcd(a,m)=1则a存在逆元。
7. 分配法则成立，即a×(b+c)=(a×b)＋(a×c)。