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

欧拉函数算法实现及其应用 欧拉函数 ψ( N) 是数论中重要的函数, 由 18 世纪数学界最杰出的人 )( )( )( p- 1) 为奇数。所以 p, pps 都是偶数。这显然是前 1p- 1p- 1 s12 23物之一欧拉提出, 内容如下 : 小于自然数 N 并与 N 互质( 除 1 以外无其 后矛盾, 即原假设不成立。所以欧拉函数 ψ( N) 的值为偶数。 他公因子) 的自然数的个数称为欧拉函数 ψ( N) 。该函数在很多领域有广 推论二: 对于任意素数 p 有 ψ( p) =p- 1。泛的应用, , 如在数论中证明歌德巴赫猜想在离散数学中求循环群的生 证明: 对于 N 的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 分解式为 N=p^q×p^q× p^q, 则 ψ( N) 计算 1122ss成员, 在计算机网络安全中的 RSA 体制等。 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 是: 实现欧拉函数 ψ( N) 通常有 3 种算法, 每种算法都有它的优缺点, 只 ψ( N) =p( ^ q- 1) ×p( ^ q- 1) p( ^ q- 1) ×( p- 1)( p- 1)( p- 1) ( p- 1122ss123s( 该论文的 3 , 证明省略, 种算法都是正确的可参考相关要证明是正确的 1) , 因为 P 是质数, p 的标准分解式 p=p, 代入 ψ( p) 的 计算公式 六西格玛计算公式下载结构力学静力计算公式下载重复性计算公式下载六西格玛计算公式下载年假计算公式 , 即 ψ( p)1书籍, ) 就可以用来证明或者反驳推论和猜想, 得到更多的正确推论。 =p- 1×( p- 1) =p- 1, 得证。, 当 N??时, , 在求欧拉函数时人工计算是不现实的利用计算机计 1, 计算结果正确而且运行速度快。另外, 利用计算机软 算可以减轻工作量推论三: 设 N 为质数 P 的平方, 即 N=P×P, 则 ψ( N) =( P- 1) ×P。 ( 如 RSA 体制) , 可以给使用者 件模拟那些比较复杂、运算量大的概念时证明: 利用 N , 的标准分解式证明方法和过程如推论一。 带来许多方便。 推论四: 设 N 为质数 p 的 n 次方( n?2) 则 ψ( N) =N×( 1- 1/p) ,证明: 已知 N=pn, 对于 N 的标 准 分 解 式 为 N=p^q×p^q× p^q 1122ss 则 ψ( N) 计算公式是: ψ( N) =p(^ q- 1) ×p(q- 1) p(^ q- 1) ×( p- 1)( p- 1) 112 2ss12 1 欧拉函数的算法( p - 1) ( p - 1) 。显然, ψ( N) =p - 1×( p - 1) =p - 1×p×( 1- 1/p) =p( 1- 1/p) = 3 s n 1 n n 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) 。 算法二: 利用欧拉函数和它本身不同质因数的关系, P 是数 N 的质 因数。 3 欧拉函数的应用欧拉函数和它本身不同质因数 的 关 系 : 欧 拉 函 数 ψ( N) =N{ ?p|N} ( 1- 1/p) 。 欧拉函数在离散数学中的应用3.1 设 G〈= a〉是循环群, ψ( 10) =10×( 1- 1/2) ×( 1- 1/5) =4;- 1 ( 1) 若 G 是无限循环群, 则只有 a 和 a是 G 的生成元。 ψ( 30) =30×( 1- 1/2) ×( 1- 1/3) ×( 1- 1/5) =8; ψ( 49) =49×( 1- 1/7) =42。( 2) 若 G 是 n 阶限循环群, 则 G 有 ψ( n) 个生成元, 对于每个小于等 算法三: 利用欧拉函数 ψ( N) 和 N 的标准分解式的关系求解欧拉函 于 n 且与 n 互质的整数 r, ar 是 G 的生成元。例如: 求下述循环群 G 的生 数。成元, G 为模 20 加群〈 Z, $〉20解 : Z〈= 1〉, 小 于 20 且 与 20 互 质 的 正 整 数 为 1, 3, 5, 7, 9, 11, 13, 20 13^q, 则 ψ( N) 计算公式是: p如果 N=p^q×p^q× 17, 19, 而 1=1, 1=1, 1 和 3 都是生成元。同理 7, 9, 11, 13, 17, 19 也是生 ss1122 成元。( ψ( N) =p(^ q- 1) ×p(^ q- 1) p(^ q- 1) ×( p- 1)( p- 1)( p- 1) p- 1122ss123s Z 中的 n 很大时( ) , 若 不超过计算机的计算范围利用上面提供的算1) 121 法可以很快求出它的生成员。如 234=2×3×13 ( 1- 1) ( 2- 1) ( 1- 1) 3.2 欧拉函数在网络安全( 加密学) 中的应用 则 ψ( 234) =2×3×13×( 2- 1) ×( 3- 1) ×( 13- 1) 在计算机领域中广泛使用的 RSA 公钥密码算法也正是以欧拉函数 2 欧拉函数的几个推论 为基础的。 RSA 公开密钥密码体制所根据的原理是: 根据数论, 寻求两个大素 推论一: 欧拉函数 ψ( N) 的值为偶数。 数比较简单, 而将它们的乘积分解开极其困难。 证明: 利用算法三, 若 N 的标准分解式为 N=p^q×p^q×1122ps^qs, 则 在这一个体制中, 每个用户有两个密钥: 加密密钥 PK={ e, n} 和解密 ψ( N) 计算公式是:密钥 SK={ d, n} 。用户把加密密钥公开, 使得系统中的任何其他用户都可 ψ( N) =p(^ q- 1) ×p(^ q- 1) p(^ q- 1) ×( p- 1)( p- 1)( p- 1) ( p- 1122ss123s以使用, 而对解密 d 保密。这里, n=p×q, 其中 p, q 一般为 100 位以上的十 1) , 假设欧拉函数 ψ( N) 的值为奇数, 则根据算法三, p(^ q- 1) ×p(^ q- 1) 1122进制数, e 和 d 满足一定的关系( 下面要介绍) 。这样, 即使知道 e 和 n, 也 p(^ q- 1) 和( p- 1)( p- 1)( p- 1) ( p- 1) 都是奇数 , 根据 p(^ q- 1) ×ss123s11很难求出 d。 ()p(^ q- 1) 为奇数, 所以 p, p p都是奇数。但是, 根据( p- p^ q- 1 ss12s 122 RSA 体制的基本原理如下: 公开密钥密码体制模拟器”)n=p×q 3.2.1 加密算法 若用整数 X 表示明文, 用整数 Y 表示密文( X 和 Y 均小于 n) , 则加 Text1.Text=n 密和解密运算为: End Sub e加密: Y=Xmod n Private Sub Label2_Click( ) d解密: X=Ymod n oula=( p- 1) ×( q- 1)3.2.2 产生密钥的算法 Text2.Text=oula ( 1) 计算 n。用户随机选择两个大素数 p 和 q, 计算出 n=p×q。n 称为End Sub RSA 算法的模数。 Private Sub Label3_Click( ) ( 2) 计算 ψ( n) 。用户再计算出 n 的欧拉函数 ψ( n) =( p- 1) ×( q- 1)( 根 i=0 据推论五) 。 Dim n, m, t, tAs Integer1 ( 3) 选择 e。用户从[ 0, ψ( n) - 1] 中选择一个与 ψ( n) 互素的数 e 作为 For t=2 To oula 公开的加密指数。 m=zhishu( t) ( 4) 计算 d。用户计算出下式的 d, e×d=1 mod ψ( n) 作为解密指数。If( m=0) Then ( 5) 得出所需要的公开密钥和秘密密钥: 公开密钥( 即加密密钥) PK= i=i+1 { e, n} , 秘密密钥( 即解密密钥) SK={ d, n} 。 下面是用 VB 开发的 RSA 公开密钥密码体制模拟器。 ReDimPre serve a( i) 实现工具: Visual Basic 6.0 企业版。 a( i) =t 界面 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 见图 1。 End If Next Randomize e=a( In(t i×Rnd( i) +1) ) Text3.Text=e End Sub Private Sub Label4_Click( ) Dim m As Long m=1 Do While( ( e×m) Mod oula <> 1) m=m+1 Loop Text4.Text=m 1 界面设计 图 d=m 在模块中添加如下代码, 作为公共变量:End Sub Option Explicit Private Sub Label8_Click( ) Text5.TexPublic p As Long “t=“{ & e &”“, & n &”} ” End Sub Public q As Long Private Sub Label9_Click( ) Text6.TexPublic n As Long “t=“{ & d & ”“, & n &”} ” End Sub Public oula Long 点“击 实例”按钮, 转到下面的 窗体, 见图 。 Form2 2Public e As Long Public d As Long Public i As Long Public a( ) 在 Form1 中编写如下代码: Option Explicit Function zhishu( ByVal n As Integer) As Integer Dim t, k As Integer For t=2 To In(t n/2) If( n Mod t=0) Then k=1 zhishu=k 2 Form2 窗体 图 Exit Function 在 Form2 窗体中, 添加如下代码: End If Option Explicit Next Dim Y As Long k=0 Dim X As Long zhishu=k Private Sub Command1_Click( ) End Function X=Va(l Text1.Text) Private Sub Label1_Click( ) Y=X ^e Mod n p=InputBox“( 请输入计算 RSA 算法的模数 N的大素数 p : ”“, RSA 公开密钥密码体制模拟器”) Text2.Text=Y q=InputBox“( 请输入计算 RSA 算法的模数 N的大素数 q : ”“, End Sub RSA 中图分类号: TG33 文献标识码: A 热连轧机组的张力复合控制是一个具有世界领先水平的课 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 , 作为理论基础是虎克定律。所以, 公式( 1) 偏向于用弹性变形来描述带钢的张 张力复合控制的实现基础, 首先要解决机架间张力解耦控制的问题, 然 力。公式( 2) 和( 3) 是从静态力矩平衡的角度来描述张力, 它们偏向于描 , 最 后以分离的机架间张力为控制目标各自设计单机架的张力控制算法述带钢张力的稳态值, 不反映带钢张力的收敛情况。公式( 2) 和( 3) 两者 终实现热连轧机组的张力复合控制。机架间张力解耦控制的研究任务作 之间计算精度上略有差异。, 主要是利用渐近收敛状态观测器提供 为复合张力控制项目的派生项目总之, 公式( 1) (, 2) 和( 3) 都是从各自的侧面来描述带钢张力的动态 的状态量, 研究张力增量的动态互不相关控制。 变化过程, 虽然反映出的趋势是比较一致的, 但都有片面性, 数字仿真结 果也证明了这一点。因此, 可以考虑综合应用公式( 1) (, 2) 和( 3) , 以期获 1 张力动态控制模型验证 得更为全面的张力信息。 连轧张力状态方程: 2 技术研究内容 d( t) E "1) ( = 〔 A( t) +V( t) 〕 "! dt L 渐近收敛状态观测器设计2.1 西门子张力计算模型:考虑连轧张力状态方程: 1 d"( t) E T( i) = 〔 P( i) 2a +b( i) T( i- 1) - M( i) 〕( 2) 0 = 4) ( 〔 A( t) +V( t) 〕 "!C( i) Ldt 新日铁张力计算模型: :当张力趋于平衡时 ( i) P( i) ( i- 1) ( i- 1) ( i) MMRR 1 〕( 〕〔T( i) = {l ( i) - l ( i- 1) 〔-- ++ Ti- !V( ?)( ?) =- ( 5) "R( i) P( i) P( i- 1) P( i- 1) P( i) A ( i- 1)R 设计渐近收敛状态观测器方程为: ) 1- T( i- 2) }( 3) P( i- 1) d"( t) E = 6) ( 〔 A"( t) +!V( t) +L T( t) - L "( t) +L !V( t) 〕 1 2 3 上述公式( 1) 是从运动学的角度来描述张力的动态变化过程 , 它的 Ldt !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!Private Sub Command2_Click( ) ( 2) 欧拉函数 ψ( N) 一定存在的散列值有 1, N- 1。如果 N 为偶数, 则 X=Y ^d Mod n 必存在下列散列对值之一,( N+2) /2,( N- 2) /2 或( N+4) /2,( N- 4) /2; 如果 Text3.Text=X N 为奇数, ,( N+1) /2,( N- 1) /2 ( N+3) /2, 则必存在下列散列对值之一或 ( N- 3) /2。 End Sub 参考文献 需要注意的是, 由于处理的是整数, 在 VB 的开发环境中, 即使采用 Long 类型, 它的最大值为 2 147 483 647, 所以在模拟时, 只能选择比较小 1] [ 谢希仁.计算机网络[ M] .第 4 版.北京: 电子工业出版社, 2003. 的质数 p 和 q, 以免在以后的计算中溢出。实际上, 只要计算机的计算范 耿素云, 屈婉玲.离散数学[ M] .北京: 北京大学出版社, 2003. [ 2] 围足够大, 利用上面的程序, 就可以计算出 d。 ( 责任编辑: ) 薛培荣 ???????????????4 关于欧拉函数的几个猜想 第一作者简介: 陈征峰, 男, 1979 年 8 月生, 2003 年毕业于北京邮电 #大学, 助教, 北华航天工业学院, 河北省廊坊市 13015 分箱, 065000. ( 1) 欧拉函数 ψ( N) 的散列值中一定存在 n和 n, 使得 n+n=N。 1 212 The Realization and Application of the Algor ithm of the Euler Function CHEN Zheng-feng, ZHAO Li-yan ABSTRACT: This paper introduces three kinds of algorithms and five deductions of the Euler Function, discusses on the application of the Euler Function in the discrete mathematics and the network security (cryptography), and puts forward several guesses of the Euler Function. KEY WORDS: Euler Function; application of Euler Function; discrete mathematics; cryptography