RSA算法中的代数结构

Algebra Structure of RSA Arithmetic

本文首次应用二次剩余理论对RSA中的代数结构进行了研究.计算出了Zn*中模n的二次剩余和二次非剩余的个数,对它们之间的关系进行了分析,并用所有二次剩余构成的群对Zn*进行了分割,证明了所有陪集构成的商群是一个Klein四元群.对强RSA的结构进行了研究,证明了强RSA中存在阶为φ(n)/2的元素,并且强RSA中Zn*可由三个二次非剩余的元素生成.确定了Zn*中任意元素的阶,证明了Zn*中所有元素阶的最大值是lcm(p-1,q-1),并且给出了如何寻找Zn*中最大阶元素方法.从而解决了RSA中的代数结构.

Based on the theory of quadratic residues,the algebra structure of RSA arithmetic is researched in this paper.This work calculates numbers of quadratic residues and non-residues in the group Zn^＊ and investigates their relationship.Zn^＊ is divided up by the group made up with all quadratic residues in Zn^＊ and all cosets form a quotient group of order 4 which is a Klein group.Studyed the structure of strong RSA further,it shows that the element of order （n）/2 exists and the group Zn^＊ can be generated by three elements of quadratic non-residues.Let the facterization n=p·q,the order of each element can be calculated,and the biggest order of all element is lcm（p-1,q-1） in Zn^＊.It also shows how to find the element of the biggest order.So the algebra structure of RSA arithmetic is solved.