关于RSA算法中代数结构的进一步研究  

Further study on algebraic structure of RSA algorithm

作　　者：裴东林[1] 李旭[1] 

机构地区：[1]兰州文理学院师范学院

出　　处：《计算机应用》2013年第11期3244-3246,3266,共4页journal of Computer Applications

摘　　要：针对RSA算法中Z*φ(n)的代数结构问题,提出了一种在强素数条件下应用二次剩余理论进行研究的方法。给出了Z*φ(n)中元素阶的计算公式和元素的最大阶表达式,计算了Z*φ(n)中二次剩余的个数和二次非剩余的个数,同时估计出Z*φ(n)中元素的最大阶上限为φ(φ(n))/4并得到了Z*φ(n)中元素的最大阶达到φ(φ(n))/4的一个充要条件。另外还给出了全部二次剩余构成的子群A1成为循环子群的充分条件及Z*φ(n)的一种分解方法。最后证明了Z*φ(n)可由7个二次非剩余元素生成,商群Z*φ(n)/A1是一个Klein八元群。By making use of the theory of quadratic residues under the condition of strong prime, a method for studying the algebraic structure of Z~ of RSA （Rivest-Shamir-Adleman） algorithm was established in this work. A formula to determine the order of element in Zc＊/n） and an expression of maximal order were proposed; in addition, the numbers of quadratic residues and non-residues in the group Z^n） were calculated. This work gave an estimate that the upper bound of maximal order was q^（ go（n） ）/4 and obtained a necessary and sufficient condition on maximal order being equal to ^（ ^p（n） ）/4. Furthermore, a sufficient condition for A1 being cyclic group was presented, where Al was a subgroup composed of all quadratic residues in Z^n） , and a method of the decomposition of Z~） was also established. Finally, it was proved that the group Zn） could be generated by seven elements of quadratic non-residues and the quotient group Z）/A1 was a Klein group of order 8.

关 键 词：RSA算法 代数结构 二次剩余 强素数 循环群 欧拉函数 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]