区块链中的数学 - 费马小定理

写在前面

上一节介绍了ElGamal算法，包括签名和加解密算法。
这一节介绍之前文章提到多次的费马小定理。最近一次是上一节Elgamal签名验证原理中用到，没印象的可以再看看。

费马小定理

费马小定理(Fermat's little theorem)是数论中的一个重要定理，描述非常简洁：

P是一个素数，整数a只要不是P 的倍数（即a,p互质） 则：
$a^{p-1}$≡ 1（mod p）
下面看下证明过程。

证明过程

设素数𝑝与整数𝑎互质，那么集合𝑆={𝑎,2𝑎,3𝑎,...(𝑝−1)𝑎}中任意任意两个元素均不可能模𝑝同余。也即是:
当j≠k 时，𝑗𝑎≢𝑘𝑎(𝑚𝑜𝑑𝑝)。
这里可以用反证法证明：假设 𝑗𝑎≡𝑘𝑎(𝑚𝑜𝑑𝑝)， 由于a,p 互素，两边消去a， 得j=k ， 与条件矛盾不成立。

所以集合S中各元素mod p的集合等于{1,2,3...,p-1}各元素mod p的集合,结果都是mod p的完全剩余系
[注：在模n的剩余类中各取一个元素，则这n个数就构成了模n的一个完全剩余系。基本性质：模n的完全剩余系中两两元素不同余，参考反证法]
于是有：
𝑎×2𝑎×3𝑎...×(𝑝−1)𝑎 ≡ 1×2×3...×(𝑝−1)(𝑚𝑜𝑑𝑝)
整理后可得：
(𝑝−1)!×$a^{p-1}$ ≡ (𝑝−1)!(𝑚𝑜𝑑𝑝)
由于𝑔𝑐𝑑((𝑝−1)!,𝑝)=1【注：由于p是素数，从1到P-1的整数都与p互素，其乘积与p互素】，
所以，可以两边消去(𝑝−1)!【同余式性质】
得到：
$a^{p-1}$≡ 1（mod p）

费马小定理扩展

以下均要求P是素数

1. 如果a是任意整数，$a^p$ ≡ a（mod p）【也称为费马小定理另一种表示形式】
   证明：
   （1）如果a与p互素，$a^{p-1}$ ≡ 1（mod p）两边乘以a可证
   （2）如果a与p不互素，a是p的倍数，$a^p$ ≡ a（mod p）= 0 可证

2. 如果整数 m ≡ n mod (p-1) 则任意整数a, 则$a^m$ ≡ $a^n$(mod p)，
   证明过程：
   由于m ≡ n mod (p-1)， 假设余数是r， 所以存在k1,k2 使得：
   m = k1 * (p-1)+ r，
   n = k2 * (p-1) + r
   可得：
   $a^m \equiv a^{k1*(p-1)+r} \equiv a^{(p-1)^{k1}} * a^r \equiv ((a^{(p-1)}modp)^{k1} * a^r \ mod\ p) mod p \equiv a^r (mod\ p)$
   同样可得：$a^n \equiv a^r (mod\ p)$
   得证：$a^m \equiv a^n(mod\ p)$

   以上是a与p互素情况，如果a是p的倍数 显而易见成立！模运算结果均为0， 不再多说。

   【注：这就是为什么上节中Elgamal签名选择一个临时随机数k,k要与p-1互素而不是与p互素的原因】

小结

费马小定理是初等数论四大定理（威尔逊定理，欧拉定理（数论中的欧拉定理），中国剩余定理(又称孙子定理），费马小定理）之一，其他定理如欧拉定理，之前文章也提过，后续会抽时间单独介绍。关于费马小定理的应用，在求解模逆运算的时候第一种方法便是使用费马小定理求解，还可应用在快速幂模运算等。

好了，下一节继续讲RSA算法。