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

6.3.3  欧拉函数

下面来学习公钥密码体制( 尤其是RSA)中非常有用的一个工具。在环Zm ={0,1,…,m-1} 中,我们感兴趣的问题( 这个问题在此处显得有点奇怪) 就是这个集合中有多少个数字与m 互素。这个数目可以由欧拉( Euler's Phi) 函数给出,其定义如下:

定义6.3.1  欧拉函数

Zm内与m 互素的整数的个数可以表示为Φ(m)。

首先来看几个示例,并通过手动统计Zm内所有互素的整数来计算欧拉函数。
 
示例6.8   假设m = 6 ,对应的集合为Z6= {0, 1, 2, 3, 4, 5}。

gcd(0, 6) = 6
gcd(1, 6) = 1  ★
gcd(2, 6) = 2
gcd(3, 6) = 3
gcd(4, 6) = 2
gcd(5, 6) = 1  ★

由于该集合中有两个与6 互素的数字,即 1 和5 ,所以欧拉函数的值为 2 ,即 Φ(6)  = 2。
 
再看一个例子。

示例6.9   假设m = 5 ,对应的集合为Z5 = {0, 1, 2, 3, 4 }。

gcd(0, 5) = 5
gcd(1, 5) = 1  ★
gcd(2, 5) = 1  ★
gcd(3, 5) = 1  ★
gcd(4, 5) = 1  ★

由于该集合中有4 个与5 互素的数字,所以 Φ(5) = 4。
 
从上面的例子可以推测出,如果数值非常大的话,将集合内的元素从头至尾都处理一遍并计算gcd 的欧拉函数的计算方法会非常慢。实际上,使用这种最直接的方法计算公钥密码学中使用的非常大的整数对应的欧拉函数是非常困难的。幸运的是,如果 m 的因式分解是已知的,则存在一个更简单的计算方法,如以下定理所示。

定理6.3.1   假设m 可以因式分解为以下数的连乘

 
 

其中,pi 表示不同素数的个数,ei 表示正整数,则有

 
 

即使对很大的整数m 而言,n 的值( 即不同素因子的个数) 也总是很小,所以评估乘积符号∏ 在计算上也是非常简单的。下面列举一个使用这个关系计算欧拉函数的例子。
 
示例6.10    假设m=240,240 因式分解对应的连乘形式为:


 

其中有三个不同的质因子,即n  = 3 ,则欧拉函数的值为


 

这意味着在范围{0 ,1 ,…,239} 内存在64个整数与m = 240 互素。而替代方法需要计算240 次gcd,即使对较小的整数而言,这个计算过程也会非常慢。

需要强调的一点是,在用这种方法快速计算欧拉函数时,我们必须知道m 的因式分解。在第7 章我们将了解到,这个特性也是 RSA 公钥方案的核心;相反地,如果已知某个整数的因式分解,就可以计算出欧拉函数并解密密文。如果因式分解未知,也就不能计算欧拉函数,也无法解密。  

点击复制链接 与好友分享!回本站首页
分享到: 更多
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力  
上一篇:1.3 功能
下一篇:1.5 小结
相关文章
图文推荐
JavaScript网页动画设
1.9 响应式
1.8 登陆页式
1.7 主题式
排行
热门
文章
下载
读书

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