跳到主要内容

WTF zk教程第7讲：费马小定理

之前我们介绍了模运算中的加减乘除，这一讲，我们介绍模幂和小费马定理。

1. 模幂​

模幂指对模进行的幂运算，在密码学中很常用：

b=acmod  nb = a^c \mod{n}

其中 0≤b<n0 \le b < n。

举个例子，给定 (a,c,n)=(7,5,13)(a, c, n) = (7, 5, 13)，我们可以计算得到 75=168077^5=16807，除以 1313 余 1111，因此 b=11b = 11。

当然，模幂也可以写为同余的形式：

b≡ac(modn)b \equiv a^c \pmod{n}

1.1 优化算法​

aca^c 是个很大的数，很占计算机的内存，而模运算的结果 0≤b<n0 \le b < n，因此，我们可以运用模运算的特性节省计算时的内存。

根据模运算，有：

x⋅ymod  n=(xmod  n)⋅(ymod  n)mod  nx \cdot y \mod{n} = (x \mod{n}) \cdot (y \mod{n}) \mod{n}

如果 xx 和 yy 很大的时候，我们可以先进行取模运算，再进行乘法运算，节省内存。而幂运算可以展开为连乘：

acmod  n=a⋅a⋅a⋅...mod  na^c \mod{n} = a \cdot a \cdot a \cdot ... \mod{n}

因此，我们可以每一步乘 aa 再取模，将乘积转化为一个较小的数，再继续乘 aa 取模，直到运算结束。

acmod  n=(((a⋅amod  n)⋅amod  n)⋅...)mod  na^c \mod{n} = (((a \cdot a \mod{n}) \cdot a \mod{n}) \cdot ... )\mod{n}

以 (a,c,n)=(7,5,13)(a, c, n) = (7, 5, 13) 为例：

  1. 第一步，计算 7∗7mod  13=107 * 7 \mod{13} =10。

  2. 第二步，计算 10∗7mod  13=510 * 7 \mod{13} = 5。

  3. 第三步，计算 5∗7mod  13=95 * 7 \mod{13} = 9。

  4. 第四步，计算 9∗7mod  13=119 * 7 \mod{13} = 11，结束。因此 b=11b = 11。

1.2 代码实现​

我们用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

2. 费马小定理​

费马小定理是数论中的一个重要定理，为解决模幂问题提供了有力的工具。

2.1 定义​

费马小定理指出，如果 pp 是一个质数，则对于任意整数 aa 是，有

ap≡a(modp)a^{p} \equiv a \pmod{p}

也就是说 ap−aa^p -a 可以被 pp 整除。举个例子， a=3a = 3 ， p=5p = 5 ，有 35−3=240=48⋅53^5 - 3 = 240 = 48 \cdot 5。

费马小定理还可以写成另一个形式。当 aa 与 pp 互质时，我们可以在等式左右两端同除以 aa ，得到下面这个形式：

ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}

也就是说 ap−1−1a^{p-1} -1 可以被 pp 整除。举个例子， a=3a = 3 ， p=5p = 5 ，有 34−1=80=16⋅53^4 -1 = 80 = 16 \cdot 5。

2.2 证明​

首先我们要证明对于质数 pp，以下等式成立：

(x+y)p≡xp+yp(modp)(x+y)^p \equiv x^p +y^p \pmod{p}

我们对原式进行二项式展开，除了 xpx^p 和 ypy^p，其余项都含有 pp，可以被 pp 整除消去：

(x+y)p≡xp+yp+p(...)≡xp+yp(modp)(x+y)^p \equiv x^p +y^p + p(...) \equiv x^p +y^p \pmod{p}

通过归纳法，我们可以得到：

(x1+...+xn)p≡x1p+...+xnp(modp)(x_1 + ... + x_n)^p \equiv x_1^p + ... + x_n^p \pmod{p}

如果我们将 aa 展开为 aa 个 11 相加 a=1+...+1a = 1+ ... +1，并代入上式展开，就有：

ap≡(1+...+1)p≡1p+...+1p≡a(modp)a^p \equiv (1 + ... + 1)^p \equiv 1^p + ... + 1^p \equiv a \pmod{p}

证明完成。

2.3 应用​

2.3.1 计算逆元​

费马小定理在计算模逆元时也能派上用场。如果 pp 是素数，且 aa 不可被 pp 整除，那么 ap−2a^{p-2} 就是 aa 在模 pp 意义下的逆元。即：

a⋅ap−2≡1(modp)a \cdot a^{p-2} \equiv 1 \pmod{p}

举个例子， a=3a = 3 ， p=5p = 5 ，那么 aa 的逆元就是 35−2≡27≡2(mod5)3^{5-2} \equiv 27 \equiv 2 \pmod{5}。

2.3.2 素数测试​

费马小定理可用于进行概率性的素数测试。如果对于给定的素数 pp，随机选择一个整数 aa 并检查是否满足 ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}。如果不满足，则一定不是素数；如果满足，则 pp 有可能是素数。然而，需要注意的是，存在伪素数，即不是素数但通过测试的数。

3. 总结​

这一讲，我们介绍了模幂和费马小定理，费马小定理是一个在数论和密码学领域中非常有用的工具，具有广泛的应用。通过深入理解费马小定理，我们可以更好地应用它解决与素数测试、模逆元等相关的数学问题。