费马小定理

引言

一直打算把自己平时看的东西通过Blog之类的整理一下，结果一摸摸了几个月的鱼，这个也搁置下来了，实在是对不起自己的那份心思。

学东西的最高效的复习办法就是把学习过的知识讲给别人听，在教的过程里可以把知识真正的掌握在自己手里，所以，为了帮助一些同样学习上有问题的人自己复习写下这些东西，如有勘误，还请多多包涵。

Mathematics is the queen of the sciences - and number theory is the queen of mathematics.

——Gauss

Fermat’s little theorem

正如高斯所言，数论是数学中的皇后，在数论里面，很多问题虽然感觉很”初等”，但是从这些初等的知识里，数学家们发明了无数的数学思想和数学工具。密码学的很多算法，就是从数论里催生出来的。费马小定理作为初等数论最基本的定理，也是公钥密码学的一个奠基石，很适合作为入门内容进行密码学与数论的学习。

费马小定理的数学表示很清楚:

$$\begin{aligned} &if \quad gcd(a,p) = 1 \\ &a^{p-1} \equiv 1\pmod p \end{aligned}$$

描述出来就是: 如果 p 是素数，正整数 a 不能被 p 整除， 那么 a 的 p-1 次幂除以 p 的余数恒等于 1。

这里的正整数 a 不能被 p 整除，与 a 与 p 互素，a 与 p的最大公约数 = 1意思相同。

密码学里，费马小定理的作用是素性测试，也就是判断一个数是不是素数。素性测试是密码学里很重要的一部分，大名鼎鼎的RSA算法中就需要找到两个很大的素数，目前我们还没有简单有效的方法能解决这个问题。本文之后会介绍一种简单的素性测试算法来展示费马小定理的应用。

Proofs of Fermat’s little theorem

证明费马小定理的方法很多，本文主要通过一种初等方法和一种近代数学方法证明费马小定理。

初等方法

考虑小于 p 的正整数集合

$$X = \{1,\cdots,p-1\}$$

用 a 乘以集合中的所有元素并取模，可以得到

$$Y = \{a \ mod\ p,\cdots,a(p-1)\ mod \ p\}$$

X , Y 被称为模 p 的简化剩余系，在这里不用过于纠结这些名词的意思，从数学运算上继续进行推理。

因为 p 不能整除 a ，所以 Y 里的元素都不等于 0， 并且他们两两互不相等。 这个不等于 0 很好理解，而互不相等就需要进行一点推理了。

在这里，引入一个模运算的性质:

如果 a 与 p 互素， 若

$$\left( a*b\right) \equiv \left( a*c\right) mod\ p$$

则

$$b\equiv c\ mod\ p$$

这个性质的证明很容易，从同余的出发定义即可，这里就不多阐述。

回到刚刚的话题，为了证明 Y 里的元素两两互不相等，这里使用反证法进行证明:

假设有两个数 x , y 满足

$$xa\equiv ya\ mod\ p$$

且

$$1\leq x <y\leq p-1$$

因为 a 与 p 互素，所以根据刚刚引入的性质，可以消去等式两边的 a, 则有:

$$x\equiv y\ mod\ p$$

很明显， 因为 x , y 都是集合 X 中的元素，他们两两互不相等，所以假设不成立。

所以Y 中的元素和 X 中的元素构成相同，他们都有 p-1 个元素，而且 mod p 运算的正整数只能从 [1 , P-1] 中取值。
所以他们有相同的构成，只是顺序不同。

有了上面的结果，将 X , Y 中的所有元素分别相乘， 并对结果取 mod p, 则有:

$$\begin{aligned} a\times 2a\times \ldots \times \left( p-1\right) a &\equiv \left[ 1\times 2\times \ldots \times \left( p-1\right) \right] \left( mod\ p\right) \\a^{p-1}\left( p-1\right) !&\equiv \left( p-1\right) !mod \ p \end{aligned}$$

根据同余除法性质，因为 p 是素数，所以可以约去等式两边 （p-1）的阶乘，这样就得到了费马小定理的证明。

$$a^{p-1} \equiv 1\pmod p$$

近代数学方法

用群论可以很简洁的证明费马小定理，
但如果没有相关知识解释起来需要大量篇幅，本文将证明贴在下面
，有一定基础的读者可以自行查看。如果以后有时间，我会写一篇详细的用群论证明费马小定理的过程咕咕咕。

证明

Application

Miller-Rabin算法基于费马小定理，可以以很大的概率判断一个数是不是素数。

在阐述算法之前，先引入一些必要的知识:

首先我们可以表示一个奇整数 n 为

$$n-1=2^{k}q \quad k >0 \quad q\ is\ add$$

为了证明这一点，很显然 n-1 是一个偶数，将这个偶数不断的除以2，最后所得的 q 一定是个奇数，除法执行的次数为 k 次。

接下来引入素数的两个性质。

第一个性质如下:

若 p 为素数，a 是小于 p 的一个正整数，则

$$a^{2}\ mod\ p=1\leftrightarrow a\ mod\ p=1\ ||\ a\ mod\ p=-1$$

这个根据模运算的规则很容易得到，只需要将a^2拆为a*a即可，写出这个性质是为了证明下个性质。

第二个性质如下:

设 p 是大于 2 的素数， 由奇数的表示可得

$$p-1=2^{k}q$$

设 a 为整数且 1 < a < p - 1

则下面有两个条件之一成立:

1. $$a^{q} \equiv 1\pmod p$$
2. 存在一个 j （1 <= j <= k）满足: $$a^{(2j-1)q}\ mod\ p=-1\ mod\ p=p-1$$

证明:

根据费马小定理，我们有

$$a^{p-1} \equiv 1\pmod p$$

根据奇数的表示

$$p - 1 = 2^{k}q$$

所以有

$$a^{2^{k}q} \equiv 1\pmod p$$

思考整数

$$a^{q},a^{2q},a^{4q},...a^{2^{k-1}q}$$

模p运算时，每个数都是前一个数的平方，并且最后一个数的平方为 1 ，那么，根据性质 1 ，只有两种可能性:

1. a^q mod p = 1 ， 即第一个数 mod p 为 1
2. 在这个整数中有一个数，其 mod p 结果为 -1 即为 p - 1

也就是说， 我们要得到 1 的结果, 其上一个数一定是 1 或者 -1（p - 1）， 而得到 -1 的结果，上个数可以为其他的数。

证明完毕。

详细的算法

TEST(n)
Find k,q k > 0, q is odd, make n - 1 = 2^kq
Randomly select a, 1 < a < n - 1
if a^q mod n = 1, then return n is uncertain prime number.
for j = 1 to k-1
    if a^2jq mod n = n-1 
    then return n is uncertain prime number.
return n is composite number

python代码

from random import randrange

def MillerRabin(n):
    if n < 0:
        n = -n   
    if n < 2: 
        return False
    if n == 2 or n == 3:
        return True
    q = n - 1 # calculate q and k
    k = 0
    while q % 2 == 0:
        q //= 2
        k += 1
    a = randrange(2, n - 1) 
    x = pow(a, q, n)
    if x == 1 or x == n - 1:
        return True
    for j in range (1, k - 1):
        x = pow(x, 2, n)
        if x == 1:
            return False
        if x == n - 1:
            return True
        k -= 1
    return False
    
# MillerRabin(5039) true
# MillerRabin(4797) false

准确性

细心的读者可能会发现，刚才在描述算法的时候，如果返回值不是合数(composite number)，则返回的是一个不确定的质数(uncertain prime number)，为什么会有这个结果呢？

根据费马小定理

$$a^{p-1} \equiv 1\pmod p$$

假设 a = 2, 很容易发现，有很多符合费马小定理的数，比如:

$$\begin{aligned}2^{7-1}-1=63\\ 7|63\end{aligned}$$

7|63 表示 7是63的因数，即63可以被7整除，虽然7是个素数，但如果我们举更多的例子，能保证每个数都是素数吗？

1819年有数学家找出了反例:

$$\begin{aligned}341|2^{341}-1 \\ 341 = 11 * 31 \end{aligned}$$

341虽然符合费马小定理的公式，但是他是个合数！

在这之后，数学家们又发现了许多数字，他们能整除 2^n - 2（是2^(n-1) - 1的等价条件）， 但他们是合数。

事实上，费马小定理是个充分非必要条件，这些数字也被成为伪素数(Fermat pseudoprime)，那么问题来了，MillerRabin算法是不是准确性上得不到保证？

并不是这样的，如果更换底数 a ， 重复执行算法，就能极大的减少误判几率，比如：

在 0 - 10^9 里大约有 5000 个 满足 a = 2 的伪素数，然而将这些伪素数用底数 a = 3 再筛一遍，则只剩下大概 1300个伪素数，根据文献，对于执行算法后判断的”素数”，每 random pick 一个 a 重新执行算法, 是伪素数的概率大约为原来的 1/4 , 所以可以连续执行多次算法(一般为6次)， 此时该素数为伪素数的概率为 0.00025 ，所以，再执行了多次算法后，被验数此时是素数的准确性是很高的。

聪明的读者可能发现了，如果我们执行这个算法无数次，那么是否还有伪素数能“抵抗”住任何筛选呢，答案自然是有的。

这些数就叫做卡迈克尔数(Carmichael number), 卡迈克尔数性质的证明需要用到中国剩余定理，篇幅过多，在这里也不过多阐述了。

证明

幸好的是，卡迈克尔数的数量实在是很少，在0-10^10个正整数中只有500+个卡迈克尔数。如何高效的发现卡迈克尔数也是数论研究的一点，目前还没有很高效的方法可以完整的计算出卡迈克尔数。

结语

最近读了一些数论的书，越发感受到数学的纯粹的美，就是脑细胞有点不够用了XD。

以后也会基于一些现在密码学基础的东西写一些blog，尽量还原自己在看书的时候从看不懂到看懂的过程中的思考，让复杂的数学证明看起来简单点。

では、まだね。