费马小定理及其简单应用

· · 算法·理论

数论好玩，但显然大家都会以下的内容。

费马小定理

法国律师、业余数学家皮耶·德·费马告诉我们如下事实：

费马小定理：对于所有质数 p，若正整数 a 满足 p \nmid a，则 a^{p-1}\equiv 1\pmod p。

证明

首先我们可以证明 0, a, 2a, \cdots, (p-1)a 在模 p 意义下互不相等。我们假设有 i, j\in\mathbb{Z}_p 且 i\neq j 使 ai\equiv aj\pmod p，就意味着 a(i-j)\equiv 0\pmod p，但 p\nmid a 且 p\nmid (i-j)，所以假设不成立。所以 \prod_{i=1}^{p-1}ai\equiv(p-1)!\pmod p。

然后我们可以做一些小的推导：

\begin{align*} \prod_{i=1}^{p-1}ai&\equiv\left(\prod_{i=1}^{p-1}a\right)\left(\prod_{i=1}^{p-1}i\right)\equiv a^{p-1}(p-1)!\pmod p \\ &\equiv(p-1)!\pmod p \end{align*}

第一个等号是显然的，第二个等号也不奇怪，第三个等号出自我们最初证明的结论。

a^{p-1}(p-1)!\equiv(p-1)!\pmod p (a^{p-1}-1)(p-1)!\equiv 0\pmod p

这说明 a^{p-1}-1 和 (p-1)! 中至少有一个是 p 的倍数，但因为 p 是质数，所以 (p-1)! 不可能是 p 的倍数，故 a^{p-1}-1\equiv 0\pmod p。

另外这里有一些费马小定理的推论：

命题 A：对于所有质数 p，若 a 为正整数，则 a^p\equiv a\pmod p。

若 p\nmid a 命题显然成立（由费马小定理），若 p\mid a，命题显然也成立。

命题 B：对于所有质数 p，若正整数 a 与 p 互质，则 a^m\equiv a^{m\operatorname{mod}(p-1)}\pmod p 对所有正整数 m 成立。

根据乘方的性质可以简单地证明。

Miller-Rabin 素性测试

这是由 CMU 的 Gary Lee Miller 教授发明，由以色列耶路撒冷希伯来大学的 Michael O. Rabin 教授改进的能在 \Theta(k\log n) 的时间内判断 n 是否为质数的一个随机算法。

（发明线性同余发生器的教授也叫 Miller，但他的全名是 Keith W. Miller。）

我们考虑费马小定理的逆定理，虽然它不成立，但如果对于足够多的 a 使得 a^{p-1}\equiv 1\pmod p，那么 p 为合数的概率就会达到任意小。实践中我们会选择 k 个 a\in[2, n-1] 来检验 p 的素性。

代码如下：

std::mt19937 mr(std::mt19937(time(0))); // 随机函数

int exp(int a, int b, int m) { // 快速幂
    if(b==0) return 1;
    int x(exp(a, b>>1, m));
    x=(long long)x*x%m;
    if(b&1) return (long long)x*a%m;
    else return x;
}

bool isprime(int n) {
    if(n<3) return n==2;
    for(int i(1); i<=10; i++) { // 此处 k=10
        int a(mr()%(n-2)+2);
        if(exp(a, n-1, n)!=1) return 0;
    }
    return 1;
}

时间复杂度显然为 \Theta(k\log n)。

但这个算法的错误率有一点高，让我们来考虑优化。首先我们有一个引理：

二次探测定理：对于所有质数 p\gt 2，x^2\equiv 1\pmod p 的解有且仅有 x\equiv 1 \pmod p 或 x\equiv p-1 \pmod p。

首先有 x^2-1\equiv (x-1)(x+1)\equiv 0\pmod p，所以 p\mid (x-1)(x+1)，因为 p 是一个质数，所以 p\mid x-1 或 p\mid x+1，能满足这个条件的只有上面的两个解。

然后我们继续来考虑素性测试：根据二次探测定理，如果 p\gt 2 是一个质数，令 u 为满足 2^tu=p-1 的最小正整数，则 \{a^u, a^{2u}, a^{4u}, \cdots, a^{n-1}\}\subset\{1, p-1\} 对所有 a\in[2, p-2] 都成立。反之，若 p 不是一个质数，这个命题不成立。由此我们可以得到一个新的素性测试算法。

改进后的代码（Miller-Rabin 算法）：

bool isprime(long long n) {
    if(n<4) return n==2 || n==3;
    long long u(n-1), t(0);
    while(!(u&1)) u>>=1, t++;
    for(long long i(1); i<=7; i++) {
        long long a(mr()%(n-3)+2); // 这里只取 [2, n-2] 之间的数，因为 1，2，n-1 都可以直接通过测试
        long long v(exp(a, u, n));
        if(v==1) continue;
        long long s(0);
        while(s<t) {
            if(v==n-1) break;
            s++;
            v=(__int128)v*v%n;
        }
        if(s==t) return 0;
    }
    return 1;
}

求模意义下的乘法逆元

我们知道，对于质数 p，所有 0\lt a\lt p 都满足 a^{p-1}\equiv 1\pmod p，然后我们又知道此时 a^{-1}a\equiv 1\pmod p。也就是说 a^{p-1}\equiv a^{-1}a\pmod p，那么 a 在模 p 意义下的乘法逆元 a^{-1}\equiv a^{p-2}\pmod p。

代码如下：

int inv(int x, int m) {
    return exp(x, m-2, m);
}

本文参考了 oi-wiki 以及百度百科相关词条。