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

  • blocksight
  • 更新于 2020-06-03 22:22
  • 阅读 3564

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

写在前面

上一节介绍了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算法

点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
blocksight
blocksight
江湖只有他的大名,没有他的介绍。