数论是密码学的基础，本文介绍一些关键的数论概念。
模算术
模算术（Modular Arithmetic）是数论中的一个分支。 最常见的一个例子是 12 小时的时钟，例如当前时间是 7 点，过 8 个小时之后是 3 点。在平常的加法运算中 7 + 8 = 15。但是在12时钟系统中，7 + 8 = 3。
如果两个数 和 除以 有相同的余数，那么 和 的关系称作模 同余（congruent modulo n），他们满足这个等式：， 为大于等于 的整数。
和 的模 同余关系用数学符号表示为
和 的关系叫做同余关系（congruence relation）。 叫做模数（modulus）。
对于模数 ，与数 同余的所有整数集合称为同余类（congruence class），用符号 表示。
模算术的性质
自反性：
对称性：如果 ，则有
传递性：如果 ，，则有
如果 ，， 则有：
消去律：如果 ，，且 ，则有
费马小定理
费马小定理（Fermat's Little Theorem）：假如 是一个整数， 是一个质数，且 ，那么有
证明：
设集合 ， 构成 的完全剩余系，即 中不存在两个数同余 。将 中的每个元素乘以 得到集合 。设 与 为 中任意两个元素，，这两个元素的差为 ，因为 与 互质，所以 不可能是 的倍数，因此 中任意两个元素除以 有不同的余数。
设 中每个元素除以 得到的余数集合是 ，因为 R 中的元素互不相等，因此 与 集合 含有相同的素。
将上述等式两边相乘得到：
令 ，上述等式简化为
因为 为质数，所以 ，因此根据模算数的消除律，等式两边消去 得到
欧拉函数
对于正整数 ，欧拉函数（Euler's totient function）是小于 的正整数中与 互质的数的个数。通常表示为：，计算函数表达式如下：
其中 表示 整除 ，上式的乘积针对的是 的所有不同质因数。
例如 12 的所有不同质因数为：2，3。那么根据欧拉函数计算得到：
也就是说小于 12 的数中有 4 个数与 12 互质，分别是：1，5，7，11。
性质
如果 为质数
如果 ， 互质，那么：
如果 是一个质数， 是大于等于 1 的正整数。那么：
所有能整除 的数的欧拉函数和为 。
例如 时，。
数论中的欧拉定理
欧拉定理有很多个，在数论中，欧拉定理（Euler's theorem）给出了两个互质数 和 之间拥有如下关系：
证明：
在证明欧拉定理之前，我们要证明：如果 ，且 ，则有 。也就是说如果 与 模 同余，且 与 互质，那么 与 也互质。
采用反正法，假设 ，且 。那么存在整数 和 ，使 ，。因为 ，则存在整数 ，使
因此， 与 都能被 整除，且 。这与条件 相矛盾，因此 。
下面开始证明欧拉定理：
假设小于 且与 互质的数的集合为 ，这个集合也叫做模 的简化剩余系（reduced residue system）。将集合中的每个元素乘以 得到，因为 和 互质，所以集合 中每个元素都与 互质。
设 与 为 中任意两个元素（），这两个元素的差为 ，因为 与 互质，所以 不可能是 的倍数，因此 中任意两个元素除以 有不同的余数。
设 中每个元素除以 得到的余数集合是 ，因为 中的每个元素与 互质，按照开始证明的结论，可知 中的每个元素也与 互质，而且 中的每个元素都小于 ，因此集合 与 含有相同的元素。
将上述等式两边相乘得到：
令 ，上述等式简化为
因为 为质数，所以 ，因此根据模算数的消除率，等式两边消去 得到
上面的证明过程与费马小定理的证明过程非常相似。实际上当 为质数时，因为 ，所以有：
这就是费马小定理的公式，因此费马小定理其实就是欧拉定理的特殊情况。
模 n 的本原根
对于模数 的每一个互质数 ，都存在一个整数 满足
那么就称 为模 的本原根 (primitive root modulo n)。
例子：
3 是模 7 的本原根。
不是每个数都有本原根。只有当 等于 ，其中 为奇质数时， 才有本原根。
当 有本原根时，本原根的个数为 。这个后面可以通过群论来证明。
没有一个公式可以直接求出模 的本原根，只有一些算法可以加快寻找本原根的速度。
