| title |
tags |
07. 费马小定理 |
zk |
basic |
chinese remainder theorem |
|
之前我们介绍了模运算中的加减乘除，这一讲，我们介绍模幂和小费马定理。
模幂指对模进行的幂运算，在密码学中很常用：
$$
b = a^c \mod{n}
$$
其中 $0 \le b < n$。
举个例子，给定 $(a, c, n) = (7, 5, 13)$，我们可以计算得到 $7^5=16807$，除以 $13$ 余 $11$，因此 $b = 11$。
当然，模幂也可以写为同余的形式：
$$
b \equiv a^c \pmod{n}
$$
$a^c$ 是个很大的数，很占计算机的内存，而模运算的结果 $0 \le b < n$，因此，我们可以运用模运算的特性节省计算时的内存。
根据模运算，有：
$$
x \cdot y \mod{n} = (x \mod{n}) \cdot (y \mod{n}) \mod{n}
$$
如果 $x$ 和 $y$ 很大的时候，我们可以先进行取模运算，再进行乘法运算，节省内存。而幂运算可以展开为连乘：
$$
a^c \mod{n} = a \cdot a \cdot a \cdot ... \mod{n}
$$
因此，我们可以每一步乘 $a$ 再取模，将乘积转化为一个较小的数，再继续乘 $a$ 取模，直到运算结束。
$$
a^c \mod{n} = (((a \cdot a \mod{n}) \cdot a \mod{n}) \cdot ... )\mod{n}
$$
以 $(a, c, n) = (7, 5, 13)$ 为例：
-
第一步，计算 $7 * 7 \mod{13} =10$。
-
第二步，计算 $10 * 7 \mod{13} = 5$。
-
第三步，计算 $5 * 7 \mod{13} = 9$。
-
第四步，计算 $9 * 7 \mod{13} = 11$，结束。因此 $b = 11$。
我们用python实现模幂的优化算法：
def mod_pow(base, exponent, modulus):
result = 1
# 将指数展开为二进制形式，从高位到低位逐位处理
while exponent > 0:
# 如果当前位是1，则乘上当前的 base，然后取模
if exponent % 2 == 1:
result = (result * base) % modulus
# 将 base 平方，然后取模
base = (base * base) % modulus
# 右移一位，相当于除以2
exponent //= 2
return result
# 示例：计算 (7^5) % 13
a = 7
c = 5
n = 13
result = mod_pow(a, c, n)
print(f"{a}^{c} mod {n} = {result}")
# 7^5 mod 13 = 11费马小定理是数论中的一个重要定理，为解决模幂问题提供了有力的工具。
费马小定理指出，如果 $p$ 是一个质数，则对于任意整数 $a$ 是，有
$$
a^{p} \equiv a \pmod{p}
$$
也就是说 $a^p -a$ 可以被 $p$ 整除。举个例子， $a = 3$ ， $p = 5$ ，有 $3^5 - 3 = 240 = 48 \cdot 5$。
费马小定理还可以写成另一个形式。当 $a$ 与 $p$ 互质时，我们可以在等式左右两端同除以 $a$ ，得到下面这个形式：
$$
a^{p-1} \equiv 1 \pmod{p}
$$
也就是说 $a^{p-1} -1$ 可以被 $p$ 整除。举个例子， $a = 3$ ， $p = 5$ ，有 $3^4 -1 = 80 = 16 \cdot 5$。
首先我们要证明对于质数 $p$，以下等式成立：
$$
(x+y)^p \equiv x^p +y^p \pmod{p}
$$
我们对原式进行二项式展开，除了 $x^p$ 和 $y^p$，其余项都含有 $p$，可以被 $p$ 整除消去：
$$
(x+y)^p \equiv x^p +y^p + p(...) \equiv x^p +y^p \pmod{p}
$$
通过归纳法，我们可以得到：
$$
(x_1 + ... + x_n)^p \equiv x_1^p + ... + x_n^p \pmod{p}
$$
如果我们将 $a$ 展开为 $a$ 个 $1$ 相加 $a = 1+ ... +1$，并代入上式展开，就有：
$$
a^p \equiv (1 + ... + 1)^p \equiv 1^p + ... + 1^p \equiv a \pmod{p}
$$
证明完成。
费马小定理在计算模逆元时也能派上用场。如果 $p$ 是素数，且 $a$ 不可被 $p$ 整除，那么 $a^{p-2}$ 就是 $a$ 在模 $p$ 意义下的逆元。即：
$$
a \cdot a^{p-2} \equiv 1 \pmod{p}
$$
举个例子， $a = 3$ ， $p = 5$ ，那么 $a$ 的逆元就是 $3^{5-2} \equiv 27 \equiv 2 \pmod{5}$。
费马小定理可用于进行概率性的素数测试。如果对于给定的素数 $p$，随机选择一个整数 $a$ 并检查是否满足 $a^{p-1} \equiv 1 \pmod{p}$。如果不满足，则一定不是素数；如果满足，则 $p$ 有可能是素数。然而，需要注意的是，存在伪素数，即不是素数但通过测试的数。
这一讲，我们介绍了模幂和费马小定理，费马小定理是一个在数论和密码学领域中非常有用的工具，具有广泛的应用。通过深入理解费马小定理，我们可以更好地应用它解决与素数测试、模逆元等相关的数学问题。