Notation
N 表示正整数，p 表示正质数。
$Z_N$ 表示集合 {0,1,2,…,N-1} ，事实上这不仅是一个整数集合，我们可以在上面做加法和乘法，只要我们始终取模 N 即可。$Z_N$ 表示了一个环，其加法和乘法都定义为模 N 的。
所有关于加法和乘法的运算法则，在 $Z_N$ 中也同样适用。
最大公约数 gcd
假设给你两个整数 x 和 y ，我们说 x 和 y 的 gcd 是它们的最大共有因数，即 最大的可以同时整除 x 和 y 的整数。
如果给你两个数 x 和 y ，总是存在另外两个整数 a 和 b ，使得 ax + by 是 x 和 y 的 gcd 。gcd(x,y) 是 x 和 y 使用整数 a 和 b 的一个线性组合，根据整数模 N 乘法群中逆元的存在性，可知 a 和 b 存在但不唯一，有一个简单有效的算法可以找到这些整数 a 和 b，这个算法被称为扩展的欧几里德算法，能在 x 和 y 的对数的平方的时间里找到 a 和 b 。
如果 gcd(x,y)=1 ，那么，x 和 y 是互质的。
模逆
模逆：数和它的逆的乘法结果等于单位元 1 。即，2 的逆是 1/2 。
当我们工作在模 N 上时，逆是什么？
$Z_N$ 中的一个元素 x 的逆，就是 $Z_N$ 中的另一元素 y ，使得 xy 等于 $Z_N$ 中的 1 。换句话说， xy =1 in $Z_N$ 。y 记为 $x^{-1}$ ，如果 y 存在，事实上它是唯一的。
N 是一个奇数，求 2 在 $Z_N$ 上的逆？(N+1)/2 。
$Z_N$ 中哪些元素有逆？
引理：如果 $Z_N$ 中的一个元素 x 有逆，当且仅当 x 与 N 互质。
证明：
假设 gcd(x,N)=1，那么 x 与 N 互质，根据 gcd 的性质，存在整数 a 和 b ，满足 ax+bN 等于 x 和 N 的 gcd ，也就是 1 ，即 ax+bN=1，两边取模 N ，意思是在 $Z_N$ 中，ax=1，只要我们对这个方程取模 N ，bN 这一项会被消除，因为 bN 被 N 整除，因此是 0 模 N 。
事实上，x 在 $Z_N$ 中的逆就是 a ，所以因为 x 与 N 互质，可以证明 x 可逆，并且构造出了 $x^{-1}$ mod N 。
如果 gcd>1 会怎样？那么我们想证明没有逆。
如果说 a 正好是 x 的模 N 逆，我们看 ax ，ax=1 mod N ，但如果 gcd(x,N)>1 ，那么 gcd(ax,N)>1 ，如果 gcd(ax,N)>1 ，那么 ax 不可能等于 1，所以 ax 必须也大于 1 ，因此 a 不可能是 x 的模 N 逆。
这就证明了，事实上，当 gcd>1，x 不可能有逆，因为没有 a ，使得 ax=1 mod N 。
举个例子，假设 gcd(x,N)=2，我们声称因此 x 不是模 N 逆的，为什么？对于所有的 a ，我们知道 ax 一定是偶数，原因是，2 整除 x ，2 整除 N ，这意味着不可能有 ax=1 mod N ，特别地，不可能有 ax=bx+1 ，因为，2整除 N ，bN 是偶数，bN+1 是奇数，偶数不可能等于奇数，所以对于任意的整数 b ，ax=bN+1 都不可能成立。特别地，这意味着 a 不可能是 x 的逆，因为 ax 不可能是 1 mod N ，所以 x 不是模 N 逆的。
记 $Z_N^*$ 为 $Z_N$ 中所有可逆元素（所有满足 gcd(x,N)=1 的元素组成的集合）。
举个例子，从一个质数 p 开始，我们知道从 0 到 p-1 的所有整数除了整数 0 ，其它都与 p 互质，因为 gcd(p,0) 不是 1 ，==所以如果 p 是质数， $Z_p^*$ 就是 $Z_p$ 除去 0 ，意味着 $Z_p$ 中除 0 外的所有元素都是可逆的==。
所以，如果想计算 $Z_p^*$ 的大小，答案就是 p-1 。
如果给你一个 $Z_p^*$ 里的元素 x ，你可以使用扩展的欧几里德算法很快地找出它的逆。如果给你一个线性方程，让你在模 N 下解出来是非常容易的，只需要把 b 移到另一边就有了一个 -b ，然后再乘以 $a^{-1}$ ，使用欧几里德算法找到 $a^{-1}$ ，再用 -b乘以它，取模 N ，得到这个线性方程的解。
欧几里德算法实际上花掉 $log^2$N 的时间，与 $(logN)^2$ 成正比，对于解模 N 的线性方程而言，这是一个平方算法。
Fermat and Euler
费马小定理
假设给大家一个质数 p ，对 $Z_p^*$ 里的任意元素 x ，如果研究 $x^{p-1}$ ，我在 $Z_p$ 中就会得到 1 。
简单应用1：假设我看 $Z_p^*$ 里的一个元素 x ，p 必须是质数，我们知道 $x^{p-1}$=1 ，那么 x·$x^{p-2}$=1 ，这就是说 x 模 p 的逆正好就是 $x^{p-2}$ ，这就给了我们另外一个计算 x 模质数的逆的算法，计算 $x^{p-2}$ 就会得到 x 的逆。这个算法与欧几里德算法相比有两个不足，①它只能工作在质数模上，而欧几里德算法也能工作在合数模上，②效率低，运行时间实际上是 O($(log)^3$p) 。
简单应用2：假设我们想生成一个随机的大质数，我们要找的质数是 $2^{1024}$ 的量级，我们可以从一个指定的区间里面选择一个随机整数，然后检测这个选取的整数是不是满足费马小定理，如果等式不成立，那么我们选择的 p 一定不是质数，我们需要返回第一步尝试另一个数，一次次这么做直到最终找到一个整数满足费马小定理的条件，然后输出。事实上，如果一个随机数通过了检测，那么它极有可能是质数，特别地，对于 1024 位的数来说，p 不是质数的概率非常小，小于 $2^{-60}$ 。随着数的变大，一个数通过检测却不是质数的概率迅速向 0 衰减。
我们无法保证输出一定是质数，只知道它非常可能是一个质数。在实际中，并不用这个方法来生成质数。
$Z_p^*$的结构
$Z_p^*$ 是一个循环群。
这意味着 $Z_p^*$ 里有某个元素 g ，如果我们取 g，计算 g 的一组幂，$g^2$ 、$g^3$ 、$g^4$ 直到 $g^{p-2}$ ，没有点超过 $g^{p-2}$ ，因为根据费马小定理，$g^{p-1}$=1 ，回到了 1 得到了一个循环。
欧拉证明了事实上，有这么一个元素 g ，如果你看到了它的所有幂，可以扩展成整个群 $Z_p^*$ 。
g 的幂给出了 $Z_p^*$ 里的所有元素，这样的元素 g 叫做生成元。不是每个元素都是生成元。
给定 $Z_p^*$ 里的一个元素 g ，如果我们看 g 的全体幂组成的集合，得到的集合叫做 g 的生成群，记为
我们把 g 的生成群的大小叫做 g 在 $Z_p^*$ 里的阶，记为 $ord_p$(g) 。
事实上，1 模任意质数的阶总是 1 。
拉格朗日定理：有限子群的阶必然整除有限群的阶。拉格朗日定理意味着，如果你看 g 模 p 的阶，这个阶始终整除 p-1 。费马小定理某种意义上是拉格朗日定理的直接推论。
欧拉定理
欧拉定理是一个费马小定理的直接推广。
给定一个整数 N ，欧拉定义了函数 φ ，φ(N) 表示 $Z_p^*$ 的大小，有时也叫做欧拉的 φ 函数。
我们知道，$Z_p^*$ 包含了 $Z_p$ 中除 0 以外的全部元素，因此，对于任意质数 p ，φ(p)=p-1 。有一个特例，如果 N 正好是两个质数 p 和 q 的乘积，那么 φ(N)=N-p-q+1 ，为什么？N 是 $Z_N$ 的大小，现在我们需要移除所有与 m 不是互质的元素，一个元素如何才能不与 m 互质呢？它要不被 p 整除，要不就被 q 整除，在 0 到 m-1 之间，有多少元素能被 p 整除？一定有 q 个。有多少元素能被 q 整除？一定有 p 个。那么我们减去 p ，来除去那些被 q 整除的数；减去 q ，来除去那些被 p 整除的数，注意我们减了 0 两次，因为 0 被 p 和 q 同时整除，所以我们再加 1 。
欧拉定理：如果给我 $Z_N^*$ 中任意的元素 x ，事实上，$x^{φ(N)} 在 $Z_N$ 中一定等于 1 。特别地，费马小定理只适用于质数的情况，对质数而言，我们知道 φ(p)=p-1 ，换句话说，如果 N 是质数，将 φ(N) 可替换为 p-1 ，就得到了费马小定理。
欧拉定理不仅仅适用于质数，还适用于合数。欧拉定理也是拉格朗日定理的特例。
事实上，欧拉定理是 RSA 密码系统的基础。
Modular e’th roots
我们已经知道通过使用求逆的算法去解线性方程，那么，怎么解高次多项式方程呢？
我们固定质数 p ，c 是 $Z_p$ 中的某元素，在 $Z_p$ 中，x 满足 $x^e$=c ，我们就说 x 是 c 的 e 次方根。
注意，这些 e 次方根不一定总是存在的。例如，$2^{1/2}$ 在 $Z_{11}$ 中不存在。
什么时候这些 e 次方根存在？当我们知道它们存在时，我们能否有效地计算它们？
简单例子(e与p-1互质)
看一个简单的例子，当我们想计算某个数的 e 次方根时，正好有 e 与 p-1 互质，这时 $c^{1/e}$ 始终存在，且有一非常容易的算法可以计算出 c 在 $Z_p$ 中的 e 次方根。
首先，因为 e 与 p-1 互质，我们知道 e 模 p-1 有逆，我们计算这个逆，并记之为 d ，然后我们宣称，事实上， $c^{1/e}$ 就是 $c^d$ mod p ，如果这个等式成立，那么首先它证明了对 $Z_p$ 中的所有 c ，c 的 e 次方根总是存在。进一步地，它给出了一个非常有效的算法来计算 c 的 e 次方根，通过简单计算 e 模 p-1 的逆，然后计算 c 的逆次方。
那么，$c^{1/e}$ = $c^d$ mod p 这个方程为何成立？首先，一个事实是，d·e=1 mod p-1 ，这意味着存在某个整数 k ，使得 d·e=k(p-1)+1 ，现在可以确认 $c^d$ 是 c 的一个 e 次方根了，如何确定？取 $c^d$，计算它的 e 次方，如果 $c^d$ 真的是 c 的一个 e 次方根，那么当我们计算它的 e 次方，我们应该会得到 c ，为什么？如图推导，因为 c 在 $Z_p$ 中，根据费马定理，我们知道 $c^{p-1}$=1 ，从而推出最后结果 c ，证明了 $c^d$ 是 c 的 e 次方根。
事实上，当 e 与 p-1 互质时，e 次方根总是存在，根是容易计算的。
经典例子(e与p-1不互质)
当 e 与 p-1 不互质时，一个经典例子是当 e=2 的情况。
假设我们想计算在 $Z_p$ 中 c 的平方根，那么如果 p 是一个奇质数，事实上从今往后我们一直都关心奇质数，事实上，p-1 是偶数，意味着 2 整除 p-1 ，gcd(2,p-1)≠1 ，所以这不是容易的情况。
当我们工作在奇质数模下，平方函数实际上是 2 到 1 函数，它把 x 和 -x 映射到了同一个值 $x^2$ ，因此说这个函数是 2 到 1 函数。
看当我们计算模 11 的平方会发生什么，1 和 -1 模 11 都被映射到了 1 ；2 和 -2 模 11 都被映射到了 4 ；… ，事实上，1，4，9，5，3，都是有平方根的，比如，4 的平方根是 2 和 9 。事实上，$Z_11$ 里的其它元素都没有平方根，这就引出二次剩余。
二次剩余：说一个 $Z_p$ 中的元素 x ，如果事实上它在 $Z_p$ 中有一个平方根，我们称之为一个二次剩余；如果没有，就称为二次非剩余。例如，4 模 11 是一个二次剩余。
如果 p 是一个奇质数，$Z_p$ 中的二次剩余一共有多少个？这个平方函数是 2 到 1 的映射，意味着 $Z_p$ 中有一半的元素在这个映射中没有原像，所以二次剩余的总数是 (p-1)/2+1 ，因为我们知道 $Z_p$ 中的一半元素是二次剩余的，因为平方函数是 2 到 1 的映射，所以映射的像最多有 (p-1)/2 个元素，在 $Z_p^*$ 里有 (p-1)/2 个二次剩余，$Z_p$ 中还有 0 也是二次剩余的，$Z_p$ 中一共有(p-1)/2+1 个二次剩余。
我们能否对 $Z_p^*$ 里的一个元素 x 判断出 x 是否有平方根呢？
欧拉提出了一个非常清楚的标准测试这些元素是否是二次剩余。特别地，他说在 $Z_p$ 中，x 是二次剩余，当且仅当 $x^{(p-1)/2}$=1 mod p 。
当我们工作在模 11 下时，可以看到 $x^{(p-1)/2}$ 始终是 1 或 -1 ，在二次剩余1，3，4，5，9上它一定是 1 ；而其它元素不是二次剩余，没有平方根。事实上，工作在模 11 下，如果我们取一个非 0 的数 x ，我们看 $x^{(p-1)/2}$ ，我们可以把它写成 $x^{p-1}$ 的平方根，根据费马小定理，$x^{p-1}$=1 ，$x^{(p-1)/2}$ 就是 1 的平方根，一定是 1 或 -1 。
$x^{(p-1)/2}$ 这个值有个名字叫勒让德符号，$Z_p$ 中所有元素的勒让德符号不是 1 就是 -1 取决于 x 是否是二次剩余的。
如果我们想计算一个二次剩余的平方根，这个引理并没有告诉我们怎么办。
计算质数模的平方根
分两种情况。
第一种情况：p=3 (mod 4) 时，非常容易计算平方根，这种情况下，c 的平方根就是 $c^{(p+1)/4}$ ，p=3 (mod 4) 必然有 p+1=0 mod 4 ，意味着 p+1 被 4 整除，因此 (p+1)/4 是一个整数，就允许计算这个幂，给了我们 c 的平方根。
解模 p 的二次方程：假设给你一个二次方程，让你找到 $Z_p$ 中这个二次方程的解，使用如图方法。
计算合数模的根
什么时候模 N 的 e 次方根存在？如果我们知道它存在能否有效地计算它？
事实上，我们只知道计算合数模的 e 次方根与分解合数一样困难，现在，对于一个普通的数 e 不知道是否是最优的，但我们有的最好的计算模 N 的 e 次方根的算法，需要我们分解这个模，一旦我们分解了这个模，那么实际上每个质数因数的 e 次方根是容易计算的，我们可以组合所有的这些 e 次方根，来得到合数模 N 的 e 次方根。
Arithmetic algorithms
加法有进位，减法有借位，这些都是线性时间操作，换句话说，如果你想加或者减两个 n 位整数，运行时间与 n 成线性。
天然的乘法会花平方时间，1960年 Karatsuba 发现运行时间只需要 $n^{1585}$ ，很常用，大多数的密码学库都是用这个算法实现乘法。实际上可以用大约 n·log(n) 的时间（几乎线性的时间）来计算乘法，它忽略了很大的常数，只有当乘数十分巨大时才实用，实际上用的不多。
带余数的除法，实际上也是个平方时间算法。
求幂问题
这个指数问题，设想我们有一个有限循环群 G ，这意味着这个群是由生成元 g 的各个幂生成的，共有群的阶数个幂。比如群 $Z_p^*$ ，g 是某个 G 的生成元，事实上还有很多有限循环群的例子。
现在，我们的目标是，给定这个生成元 g ，以及某个指数 x ，计算 $g^x$ 。通常情况下你会认为，如果 x=3 ，我要计算 $g^3$ 。这会花费指数级时间，如何在 x 非常大的情况下依然很快地计算 $g^x$ ？使用重复平方算法。
重复平方算法工作过程：假设要计算 53 个 g 的乘积，把 53 写成二进制，如图，53 是 32+16+4+1 ，这意味着 $g^{53}$ 就是 $g^{32+16+4+1}$ ，我们可以把指数分解开，使用指数法则。这给出了一个计算想法，我们取 g ，然后开始计算平方、再平方等，然后简单的乘合适的幂，就可以得到结果。
下图中，z 累乘着合适的幂。循环次数是 $log_2$x 。
运行时间小结
假设我们有一个 N 位模，$Z_N$ 上的加减法花线性时间；简化乘法需平方时间；指数需要 log(x) 次循环，每轮做两次乘法即 log(x) 次乘法，乘法的时间是平方的，所以运行时间是 $n^2$log(x) ，指数算法是立方时间算法。
Intractable problems
简单问题
如果给我一个整数 N ，给我一个 $Z_N$ 中的指数 x ，使用欧几里德算法找到 x 的逆是很容易的。
如果给我一个质数 p ，给我某个多项式 f ，找到 $Z_N$ 中的一个元素，使得它是这个多项式的根也很容易。实际上有一个有效的算法，用时与多项式次数呈线性，至少对于低次数的多项式，找到这些方程的质数模的根很容易。
经典的质数模的困难问题
困难的问题组成了许多公钥密码系统的基础。
固定某个大质数 p ，固定 $Z_p^*$ 中的某个元素 g ，我们假设这个元素 g 的阶正好是数 q ，现在，考虑一个指数函数，将 x 映射到 $g^x$ ，，这个函数是容易计算的。
现在，看相反的问题，给定 $g^x$ ，想找出它的对数，即值 x 。在实数上，给定 $g^x$ ，找 x 就是对数函数的定义，但在这里找的是模 p 下的对数，这个问题叫离散对数问题，Dlog ，$g^x$ 的以 g 为底的离散对数是这个指数 x 。我们的目标是输出指数 x ，x 在 0 到 q-2 的范围里正好是 $log_2$x 。
看一个例子，假设看整数模 11 ，写下 $Z_11$ 里的离散对数函数，底数为 2 ，这个函数如下工作：首先，1 的离散对数是 0 ，因为 $2^0$ 是 1 。
一般情况下的离散对数函数的计算是很困难的，当然，对于小质数而言是很容易的，做一张表可以读到离散对数值，但如果质数 p 是个大数，计算离散对数是很困难的。
更一般地定义离散对数问题，不再局限于群 $Z_p^*$ ，更为抽象的看一个普通群。
我们有一个有限循环群，生成元是 g ，这意味着，这个群由 g 的各次幂组成。我们取所有的幂，一共有阶数个，这里 G 的阶正好是 q ，那么我们取 g 所有的幂，组成了群 G ，群 G 的离散对数问题是困难的，事实上没有有效的算法能够计算离散对数函数。
如果你从群 G 中随机选择一个元素 g ，再随机选择一个指数 x ，同时给出这个群的描述、阶数，但最初的元素只有 g 和 $g^x$ ，这个算法会计算出离散对数的概率是可忽略的。如果这点对所有的有效算法都成立，那么我们说在群 G 上，离散对数问题是困难的。
没有有效的算法能以不可忽略的概率计算出离散对数。
亚指数算法
在 $Z_p^*$ 中计算离散对数有一个亚指数算法，如果你有一个 n 位的质数，这个算法的运行时间的指数大约是 n 的立方根，事实上，在这个算法的运行时间里，这里有很多其他项，但最主要的项是质数的位数的立方根，即 n 的立方根。因为有这个算法，如果我们想让离散对数问题变得与破解相应的对称密钥一样难，我们必须使用较大的模 p 。
如果看椭圆曲线群，参数会好很多，事实上在一个椭圆曲线群里，我们对离散对数的最好算法运行时间为 $2^{n/2}$ 。
椭圆曲线大小是对称密钥大小两倍的原因是由于指数里的因子 2 ，我们必须将椭圆曲线群的大小扩大一倍，以获得 $2^n$ 的运行时间。
离散对数困难性的直接应用
特别地，我们基于离散对数问题构建一个抗碰撞哈希函数，我们选择一个群 G ，G 上的离散对数问题是困难的，可以把 G 想象成群 $Z_p^*$ ，我们假设群 G 有质数阶 q ，那么 q 是某个质数且正好为 |G| ，即群 G 里元素的个数，现在我们选择群 G 中的两个元素 g 和 h 定义如下哈希函数 H ：哈希函数的输入为 x 和 y 时，输出 $g^x$· $h^y$ 。
这个函数 H 事实上是抗碰撞的，就是说，找到一个 H 的碰撞与计算 G 上的离散对数一样困难。特别地，如果你可以找到一个 H 的碰撞，你就能计算 g 底 h 的离散对数，由于计算离散对数是困难的，所以找 H 的碰撞也是困难的。
证明：假设我们有一个函数 H 的碰撞，碰撞为两对不同的信息对，($x_0$,$y_0$) 与 ($x_1$,$y_1$) ，它们正好在函数 H 上发生碰撞，也就是说，如果计算函数值 H($x_0$,$y_0$) 和 H($x_1$,$y_1$) ，就会得到一个碰撞，也就是会得到相等的结果。然后做一些变换，取两边的 ($y_1$-$y_0$) 次方根，另一边得到 h 。我们用 g 的某个幂表示了 h ，所以就计算出了 g 底 h 的离散对数。那么这个指数里除以 ($y_1$-$y_0$) 是什么意思呢？这个意思就是让我们计算 ($y_1$-$y_0$) 的模 q 的逆，然后把结果与 ($x_0$-$x_1$) 相乘。
这也展示了为什么我们希望 q 是质数，因为我们需要确保 ($y_1$-$y_0$) 始终可逆，那么事实上我们知道，当我工作在质数模时，除了 0 ，所有数都可逆，这就遇到了一个难以理解的地方，如果 $y_1$-$y_0$=0 会怎样？如果是这种情况，我们无法得到离散对数，我们不能除以 0 ，如果 $y_1$-$y_0$=0 ，意味着 $y_1$=$y_0$ ，看上图式子最左侧，$x_1$ 也必须等于 $x_0$ ，这与碰撞的前提相矛盾，相当于给了同样的信息对两次，因此，不需要去找离散对数了。但如果给我一个碰撞，$y_1$ 与 $y_0$ 有必要是不同的，然后将计算 h 底 g 的离散对数，由于群 G 上的离散对数被认为是困难的，这意味着这个非常简单的函数 H 一定是抗碰撞的。
尽管这个函数有一个漂亮的抗碰撞的证明，但不怎么用，因为每次哈希需要计算两次指数，相对较慢。
合数模的经典难题
1024 位数，定义集合 $Z_{(2)}(n)$ 表示所有的整数，正好是两个质数的乘积，这两个质数都是 n 位的，2 对应于这个集合的数都有两个质因子，这两个质因子差不多大小都是 n 位的质数
难题一：如果选择 $Z_{(2)}(n)$ 中的一个随机整数，如何分解它？
1024 位的数尽管还没有被解出来，但很有可能这个数量级的数将很快被因子分解，现在推荐的值是 2048 位的数。
难题二：给出某个非线性多项式，如果多项式次数大于 1 ，给出 $Z_{(2)}(n)$ 中的某个随机的合数，如何找到这个方程的根 x ？
如果次数等于 1 那就是解线性方程，很容易；但当次数变成非线性时，我们不知道怎么解这个模 N 的方程。