欧拉函数算法实现及其应用

《欧拉函数算法实现及其应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、科技情报开发与经济SCI-TECHINFORMATIONDEVELOPMENT&ECONOMY2006年第16卷第10期文章编号:1005-6033(2006)10-0176-03收稿日期:2005-12-27欧拉函数算法实现及其应用陈征峰,赵丽艳(北华航天工业学院,河北廊坊,065000)摘要:介绍了欧拉函数的3种算法和5个推论,论述了欧拉函数在离散数学和网络安全(加密学)中的应用,并提出了欧拉函数的几个猜想。关键词:欧拉函数;欧拉函数应用;离散数学;加密学中图分类号:O156;TP393文献标识码:A欧拉函数ψ(N)是数论中重

2、要的函数,由18世纪数学界最杰出的人1)(p2-1)(p3-1)⋯(ps-1)为奇数。所以p1,p2⋯ps都是偶数。这显然是前物之一欧拉提出,内容如下:小于自然数N并与N互质(除1以外无其后矛盾,即原假设不成立。所以欧拉函数ψ(N)的值为偶数。他公因子)的自然数的个数称为欧拉函数ψ(N)。该函数在很多领域有广推论二:对于任意素数p有ψ(p)=p-1。泛的应用,如在数论中证明歌德巴赫猜想,在离散数学中求循环群的生证明:对于N的标准分解式为N=p1^q1×p2^q2×⋯⋯ps^qs,则ψ(N)计算成员,在计算机网络安全中的RSA体制等

3、。公式是:实现欧拉函数ψ(N)通常有3种算法,每种算法都有它的优缺点,只ψ(N)=p1^(q1-1)×p2^(q2-1)⋯ps^(qs-1)×(p1-1)(p2-1)(p3-1)⋯(ps-要证明是正确的(该论文的3种算法都是正确的,证明省略,可参考相关1),因为P是质数,p的标准分解式p=p1,代入ψ(p)的计算公式,即ψ(p)书籍,)就可以用来证明或者反驳推论和猜想,得到更多的正确推论。=p1-1×(p-1)=p-1,得证。在求欧拉函数时,当N→∞时,人工计算是不现实的,利用计算机计推论三:设N为质数P的平方,即N=P×P,则ψ

4、(N)=(P-1)×P。算可以减轻工作量,计算结果正确而且运行速度快。另外,利用计算机软证明:利用N的标准分解式证明,方法和过程如推论一。件模拟那些比较复杂、运算量大的概念时(如RSA体制),可以给使用者推论四:设N为质数p的n次方(n≥2)则ψ(N)=N×(1-1/p)带来许多方便。证明:已知N=pn,对于N的标准分解式为N=p1^q1×p2^q2×⋯⋯ps^qs,则ψ(N)计算公式是:ψ(N)=p1(^q1-1)×p(2q2-1)⋯ps(^qs-1)×(p1-1)(p2-1)1欧拉函数的算法(p3-1)⋯(ps-1)。显然,ψ

5、(N)=pn-1×(p1-1)=pn-1×p×(1-1/p)=p(n1-1/p)=N×(1-1/p)欧拉函数的条件:小于自然数N并与N互质(除1以外无其他公因得证。子)的自然数。推论三是推论四的一个特例。欧拉函数ψ(N)的散列值满足欧拉函数条件的数值序列,比如:ψ(10)推论五:设N为两个不同质数p,q之积,N=p×q,则ψ(N)=(p-1)×的散列值有1,3,7,9。(q-1)。算法一:从1到N-1逐个判断是否满足欧拉函数的条件,如果满足,证明:利用N的标准分解式证明,方法和过程如推论一。则输出该数,并计算出欧拉函数ψ(N)。算

6、法二:利用欧拉函数和它本身不同质因数的关系,P是数N的质3欧拉函数的应用因数。欧拉函数和它本身不同质因数的关系:欧拉函数ψ(N)=N{∏p

7、N}3.1欧拉函数在离散数学中的应用(1-1/p)。设G〈=a〉是循环群,ψ(1)若G是无限循环群,则只有a和a-1是G的生成元。(10)=10×(1-1/2)×(1-1/5)=4;ψ(30)=30×(1-1/2)×(1-1/3)×(1-1/5)=8;(2)若G是n阶限循环群,则G有ψ(n)个生成元,对于每个小于等ψ(49)=49×(1-1/7)=42。于n且与n互质的整数r,ar是G的生成元

8、。例如:求下述循环群G的生算法三:利用欧拉函数ψ(N)和N的标准分解式的关系求解欧拉函成元,G为模20加群〈Z20,$〉数。解:Z20〈=1〉,小于20且与20互质的正整数为1,3,5,7,9,11,13,如果N=p^q×p^q×,则ψ(N)计算公式是:131122⋯⋯ps^qs17,19,而1=1,1=1,1和3都是生成元。同理7,9,11,13,17,19也是生ψ(N)=p1(^q1-1)×p2(^q2-1)⋯⋯ps(^qs-1)×(p1-1)(p2-1)(p3-1)⋯(ps-成元。1)若Z中的n很大时(不超过计算机的计算范围

9、),利用上面提供的算如234=21×32×131法可以很快求出它的生成员。则ψ(234)=2(1-1)×3(2-1)×13(1-1)×(2-1)×(3-1)×(13-1)3.2欧拉函数在网络安全(加密学)中的应用在计算机领域中广泛使用的RSA公钥密