读书频道 > 安全 > 深入浅出密码学——常用加密技术原理与应用
6.3.4 费马小定理与欧拉定理
2012-09-26 15:44:36     我来说两句 
收藏    我要投稿   
本书拥有的诸多特征使得它成为密码学从业者和学生独一无二的资源—本书介绍了绝大多数实际应用中使用的加密算法,并重点突出了它们的实用性。对于每种加密模式,我们都给出了最新的安全评估和推荐使用的密钥长度...  立即去当当网订购

下面将介绍公钥密码学中非常有用的两个定理,首先介绍费马小定理(Fermat’s Little Theorem1)。此定理在素性测试和公钥密码学的其他很多方面都非常有用。在做指数模整数操作时,此定理得到的结果将非常令人惊讶。

定理6.3.2   费马小定理

假设a 为一个整数,p 为一个素数,则

ap=a( mod p)

  
请注意,有限域 GF(p)上的算术运算都是通过mod p 实现的,因此,对有限域GF(p)内的所有整数元素a 而言,此定理始终成立。此定理也可表示为以下形式:

 ap-1=1(mod p)

这种形式在密码学中非常有用,其中一个应用就是计算有限域内某个元素的逆元。此等式也可以写成a.ap-2=1(mod p) ,这个表示形式正是乘法逆元的定义。因此,我们立刻可以得到反转整数a 模一个素数的方法:


 

请注意,只有在p 为素数时这种反转方法才成立。下面来看一个示例:

示例6.11    假设p  = 7 ,a  = 2 ,计算a 的逆元可以表示为:


 

结果的验证也很容易:2⋅4 = 1mod7 。

计算等式(6.7) 中的指数运算通常比使用扩展的欧几里得算法要慢很多。然而,使用费马小定理在有些情况下也具有一定的优势,比如在智能卡或其他拥有快速指数硬件加速器的设备中。但这些情况都不常见,因为很多公钥算法都需要指数计算,这在后续章节中会看到。

将费马小定理的模数推广到任何整数模,即不一定为素数的模,就可得到欧拉定理。

定理6.3.3   欧拉定理

假设a 和m 都是整数,且gcd( a ,m )=1 ,则有:


 

由于这个定理对模数m 适用,所以它也适用于整数环Zm内的所有整数。下面来看一个使用欧拉定理计算较小数字的例子。

示例6.12    假设m = 12,a  = 5 。首先计算m 的欧拉函数:


 

现在验证欧拉定理:


 

很容易看出来,费马小定理是欧拉定理的一个特例。如果 p 为一个素数,则Φ(p)=(p1-p0)=p-1成立。如果将这个值用于欧拉定理,则可得到:aΦ(p)=ap-1=1(mod p) ,  而这正是费马小定理。

_____________________________________________________________
1. 请不要把费马小定理和费马最后定理混为一谈,费马最后定理是一个非常著名的数论问题,并于20世纪90年代( 即自它诞生350 年之后) 才被论证。

点击复制链接 与好友分享!回本站首页
分享到: 更多
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力  
上一篇:定义6.3.1 欧拉函数
下一篇:6.4 讨论及扩展阅读
相关文章
图文推荐
排行
热门
文章
下载
读书

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训
版权所有: 红黑联盟--致力于做实用的IT技术学习网站