费马小定理

费马小定理是法国数学家费马于1636年发现的。他在1640年10月18日写给友人法国数学家贝西(Bernard Frénicle de Bessy)的信中首次提出了这个定理。1736年,欧拉给出了费马小定理的一个证明。但从莱布尼茨未发表的手稿中发现他在1683年以前已经得到几乎相同的证明。之所以命名为“小定理”是为了区别于举世闻名的费马大定理。

enter image description here

数论中费马小定理是说:若p是素数,对任何满足0 < a < p的整数a都有,a^(p−1) − 1能被p整除。

应用

今天,费马小定理已经走进人们的日常生活中,不管是网络购物还是电子交易。1976年,美国斯坦福大学的教授马丁·赫尔曼(Martin Hellman)和惠特菲尔德·迪菲(Whitfield Diffie)提出了非对称公钥加密算法的思想。1977年美国麻省理工学院的罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Len Adleman)提出了构造单向函数的数论方法,从而产生了以这三个人姓氏首字母命名的RSA算法。

RSA算法的核心思想是人们可以容易地将两个大素数乘在一起得到一个合数,然而在不事先知道这两个素数的情况下,对这个合数做因数分解却非常困难。对于一个200位以上的的大数做因式分解,即使用强大的超级计算机,所耗费的时间也要超过宇宙的年龄。因此,如果能够迅速地找到大素数,就可以构造难以破解的密钥。但是素数的存在规律是神秘的,人们没有找到素数的“通项公式”。最原始的办法是挑选一个数n,然后逐一验证从1到√n之间的整数能否整除n。但这种方法非常低效,对大数进行素数检测,同样会超过宇宙年龄所需的时间。稍好的方法是埃拉托斯特尼筛法。 列出从2开始到n之间的整数,然后从2开始,先筛除所有2的倍数,然后再筛除3的倍数,这样每次都从没有被筛除的第一个数开始重复这一步骤,直到把不大于√n的所有倍数都筛除为止。这样就可以获得n以内的所有素数。但这样方法同样只是对较小的整数n有效。无法达到大素数检测的目的。

费马小定理恰好给出了一种大素数检验的办法。对于一个大整数n,我们可以随机挑选一个小于n的正整数a,将其称为“证人”(witness),然后检查a^(n−1)模n的余数是否等于1,如果不是1,根据费马小定理,n一定不是素数。如果等于1,则n有可能是素数。

根据这一思想构造的“费马素数检测”算法如下:

function primality(n)
    随机选择正整数a < n 
    if a^(n−1) ≡1 mod n then
        return 素数 
    else
        return 合数

我们并不需要真的计算a的n − 1次方然后再求除n的余数,而是通过模乘运算。并且还可以进一步利用中间的计算结果加速,例如当我们得到b = a^2 mod n时,可以直接计算b^2 mod n从而得到a^4 mod n。假设要计算a^11 mod n,因为: a^11 = a^(8+2+1) = ((a^2)^2)^2 * a^2 * a mod n 所以我们真正需要计算的只有a^2 mod n, (a^2)^2 mod n, ((a^2)^2)^2 mod n。为此,我们可以把n表示为2进制,然后仅仅迭代计算数字为1所在位上的模乘结果,这是一个复杂度为O(lg n)的算法。因此费马素数检测的速度很快。

但某个数即使通过了费马素数检测,仍然不一定是素数,例如341 = 11 × 31,但是2^340 ≡ 1 mod 341。为了减少费马检验的“假阳性”,人们进行了一系列改进。首先是适当增加证人的数量。人们发现,如果一个数无法通过费马检验,那么至少存在一半小于n的数都无法通过费马检验。

实际的RSA算法采用“米勒——拉宾”进行素数测试。它也是一种概率算法。如果选择超过100个证人,错误率会低于1/2^100 。高德纳说:“该测试的错误率要比计算机因为宇宙辐射而丢失某个二进制位的概率还要低。”

同构的证明

采用初等数论的方法证明费马小定理比较复杂。我们可以采用同构的方法,把这一较难的证明问题“同构”成一个简单的数数的问题,从而攻破它。

考虑有a种不同颜色的珍珠,我们要串一条长为p的珍珠串。其中p为素数。显然一共有a^p种不同的串,这是因为串中每个位置都可以在a种颜色的珍珠中选择,共选p次。

例如有两种颜色A红、B绿的珍珠,要串长度为5的串。即a = 2, p = 5,一共有2^5 = 32种不同的串:

AAAAA, AAAAB, AAABA, ..., BBBBA, BBBBB.

对应

红红红红红, 红红红红绿, 红红红绿红, ..., 绿绿绿绿红, 绿绿绿绿绿.

我们要证明,在这a^p串珍珠中,如果去掉a个颜色完全相同的串(在上述例子中是串AAAAA和BBBBB), 剩下的a^p − a串珍珠可以分成若干组,每个组恰好有p串珍珠。也就是说p整除a^p − a。 如果把每串珍珠首尾连接起来做成项链。原来有些不同的串会变成相同的项链。如果一个串可以通过旋转变换成另一个,这两个串必然做成相同的项链。例如下面的5个串珍珠可以做成相同的项链:

AAAAB, AAABA, AABAA, ABAAA, BAAAA.

enter image description here

一串含3种颜色的项链代表7种不同的串:ABCBAAC, BCBAACA, CBAACAB, BAACABC, AACABCB, ACABCBA, CABCBAA

enter image description here

相同颜色珍珠串成的项链只代表一种串:AAAAAAA

用这种方法,上面例子中的32串珍珠可以分成5种不同颜色的项链和2种同色的项链:

[AAABB, AABBA, ABBAA, BBAAA, BAAAB];
[AABAB, ABABA, BABAA, ABAAB, BAABA];
[AABBB, ABBBA, BBBAA, BBAAB, BAABB];
[ABABB, BABBA, ABBAB, BBABA, BABAB];
[ABBBB, BBBBA, BBBAB, BBABB, BABBB];
[AAAAA];
[BBBBB].

一串项链可以代表多少种不同的串呢?如果一个串S由若干相同的子串T 复制连接而成,而T 无法再继续分拆成相同的子串,则由S构成的项链可代表|T |种不同的串,其中|T |表示串T 的长度。例如 串S =ABBABBABBABB,由相同的子串T=ABB复制多次而成,如果我们一次旋转一颗珍珠,一共可以得到3串不同的结果:

ABBABBABBABB,
BBABBABBABBA,
BABBABBABBAB.

除去这3种之外,不可能再有其它不同种类的串了。ABB的长度为3,再次旋转必然会循环得到相同的结果。这样,所有的a^p串珍珠可分成两类。一类是a串颜色相同的串;另一类颜色不同,但是由于这些串的长度p是素数,它绝不可能由若干子串复制连接出来。所以任何一个这样的串连成的项链,总共代表p种不同的串。而这样的串总共有a^p − a种,它们可以通过连成项链后分组,每组恰好p个串,代表一种不同的项链。因此a^p − a = a^(p−1)一定可以被p整除。

证毕

项链证明法可能是费马小定理已知证法中最容易的,它不需要太多的数学知识。核心思想是利用两种不同的方式数数的结果必然是一样的。

同构到群论中的拉格朗日定理

如果我们进一步把这一问题同构到群,则可以用群论中的拉格朗日定理给出更加简短的证明:

考虑整数模p乘法群。这个群的元素由所有模p的非零余数构成,因为p是素数,所以群元素为 1, 2, ..., p − 1,单位元e = 1,群的阶为p − 1。根据拉格朗日定理的推论,有: a^(p−1) = e 因为单位元为1,所以上式可写为:

a^(p−1)≡1 mod p

故p整除a^(p−1) − 1。

证毕

扩展

同构——编程中的数学》中文版已可以从github上下载:https://github.com/liuxinyu95/unplugged

enter image description here