非对称加密中的离散对数难题，到底难在哪？

质数

因数只有 1 和 它本身的数叫质数否则叫合数，1 既不是质数也不是合数。

如 5 = 1 x 5，没有其他因数了，所以 5 是 质数。

如 9 = 1 x 9 或 9 = 3 x 3，所以 9 不是质数。

互质

两个数的因数除了 1 以外，没有其他公因数了。

如：

7 的因数：1 和 7

4 的因数：1，4，2

7 和 4 的共同因数只有 1，所以 7 和 4 互质。

Code

不难发现有如下规律：
（一）1 和任意自然数构成互质关系

（二）质数和质数构成互质关系

（三）质数和比他小的任意自然数构成互质关系（比它小的数的因数不可能包含它）

（四）质数和不是它倍数的数构成互质关系（是它倍数那它们就有公因数了）

（五）p是大于1的整数，则p和p-1构成互质关系，比如57和56

（六）p是大于1的奇数，则p和p-2构成互质关系，比如17和15

欧拉函数

任意给定正整数 n，在小于等于 n 的正整数之中，有多少个与 n 构成互质关系的数，求这个数的过程叫欧拉函数，用 φ(n) 表示。

φ(n) = n * (1 - 1/p₁) * (1 - 1/p₂) * (1 - 1/p₃) * … * (1 - 1/p_n)

其中 p₁ ~ p_n 是 n 的质因数。

如 120 = 2×2×2×3×5，120 的质因数为 2、3、5，那么 φ(120) = 120 * (1 - 1/2) * (1 - 1/3) * (1 - 1/5) = 32

欧拉定理

如果两个正整数 a 和 n 互质，则 n 的欧拉函数 φ(n) 可以让下面的等式成立

a ^φ(n) % n = 1 或写成 a ^φ(n) ≡ 1 % n

也就是说，a 的φ(n)次方被 n 除的余数为 1，或者说 a 的 φ(n) 次方减去 1，可以被 n 整除。

比如，3 和 7 互质，而 7 的欧拉函数φ(7) 等于 6，所以 3 的 6 次方（729）减去 1，可以被7整除（728/7=104）。

又由于质数和比它小的自然数都互质，所以质数的欧拉数 φ(n) = n-1，所以当 n 为质数 时有：

a^n-1 % n = 1 或写成 a^n-1 ≡ 1 % n

上面的等式又叫“费马小定理”，是欧拉定理的一个特例。

阶

两正整数 a 和 n ：a ^x % n = 1；

等式成立时，x 可能有多个取值，x 的最小取值 叫做 a 模 n 的阶。

如：3 ^x % 7 = 1，那 x 最小取多少时成立呢？不妨从 1 开始试：

3¹ % 7 = 3

3² % 7 = 2

3³ % 7 = 6

3⁴ % 7 = 4

3⁵ % 7 = 5

3⁶ % 7 = 1

从中可用看到，当 x = 6 时等式成立，所以 6 是 3 模 7 的阶。

使等式成立 x 还可以取 12、18、24 等等，但最小取值 6 才是阶。

原根

两正整数 a 和 n ：a^x % n = 1；

当 n 为质数，且 a 模 n 的阶恰好为 φ(n) 时，求使得等式成立时的 a。

如 7 是质数，质数的欧拉函数很好求 φ(7) = 7 - 1 = 6

a⁶ % 7 = 1 时，a 可以取哪些值呢？比如 3 或 5

当 n 是质数，a 是 n 的一个原根时，有什么意义呢？

比如 7 是质数，7 的欧拉函数是 6，7 的一个原根 3，观察下面的等式：

3¹ % 7 = 3

3² % 7 = 2

3³ % 7 = 6

3⁴ % 7 = 4

3⁵ % 7 = 5

3⁶ % 7 = 1

---

3⁷ % 7 = 3

3⁸ % 7 = 2

3⁹ % 7 = 6

3¹⁰ % 7 = 4

3¹¹ % 7 = 5

3¹² % 7 = 1

---

3¹³ % 7 = 3
3¹⁴ % 7 = 2
……

从上面可以看出：当 x 从 1 取到 6 时，等式右边的取值范围也是 1 到 6 且各不相等，当 x 取值大过 6 后，右边的取值就开始循环了，一直是按 3、2、6、4、5、1的顺序循环。

即从 a¹ % n 到 a^φ(n) % n 的取值范围是 1 到 φ(n) 且互不相等。超过 a^φ(n) % n 后就开始循环。

离散对数

b 是任意整数，n 是任意质数，a 是 n 的原根：a^x % n = b

那么 x 叫做：b 以 a 为基数模 n 的离散对数。

由于 n 是质数，所以 x 的取值范围是 [1,n-1] ，b的取值范围也是 [1,n-1]

离散对数难题是指

两正整数 a 和 n 互质：a^x % n = b

当知道一个大质数 n 和它的一个原根 a ，如果给定一个整数 x，要计算 b 的值是相当容易的。

但已知一个大质数 n 和它的一个原根 a ，如果给定一个整数 b，要计算 x 的值是相当困难的。

因为 a 是 n 的元根，n 又是质数，不难发现：

x 的取值范围为[1,n-1]，b 的取值范围也是[1,n-1]，x 每取一个值都有 b 中唯一的一个值和它对应，而且 b 的取值是没有任何规律的。

所以知道 b 要求 x，只要 x 从 1 开始，不断尝试求 a^x % n，直到 x 取某个值时等式右边恰好等于 b，那么这个值就是我们要找的 x，最多暴力尝试 n-1 次即可求出 x。

但是如果 n 很大呢？ 如 1024 位的二进制数, 也就是十进制 2¹⁰²⁴ 大概是 10³⁰⁰。 暴力破解 10³⁰⁰ 次是什么概念，宇宙原子总数大概是 10⁸⁰。

从这里也能看出，为什么求离散对数难，还可以看出为什么基于离散对数的非对称加密性能低，因为要计算的很大值的幂模运算，模运算虽然可以取一些特殊值提升性能，但幂运行底层是做加法运算要考虑进位等，而对称加密一般都是异或运算，异或运算比加法运算快得多。