一种适用于信息加密技术应用的素数族快速生成方法

摘要

本发明公布了一种适用于信息加密技术应用的素数族快速生成方法，通过选择模M＝30的缩剩余系，建立可能素数族；并根据可能素数族中合数的分布规律和特点，可筛选出可能素数族中的全部合数，从而实现准确、快速、完整生成计算机存储限定范围内的任意区段的全部素数；在信息安全和密码学领域，大素数获取和提供是公钥算法中必不可少的流程之一；传统方法每次只能提供单个素数，而且大多数必须进行素性检测，运算时间过长，本发明方法应用计算机软件经过简单的筛选运算即可生成素数族，从而在计算机上实现了无复杂运算的快速生成；不仅省去了素性检测环节，而且不再受素数产生技术的限制，从而可做到一次一密，有利于相关公钥体系的完美发挥。

主权项

1.一种适用于信息加密技术应用的素数族快速生成方法，其特征是： 步骤1，压缩正整数，建立模m=30的缩剩余系；选取m=30为模，求其对正整数的同余类，并做出其缩剩余系，由Euler函数 得从而可形成八个等差数列； 步骤2，建立可能素数族；在与模m=30互素的八类中各取出一个代表数a₁，…，a₈，它们依次为 1、7、11、13、17、19、23、29 于是7以上的素数p均可用模m=30的缩剩余系表出，即 本发明将上式表示的全部数值定义为可能素数族，并记作Kp，于是有 Kp=a+30(n-1)式中，n≥1，a<30、且(a，30)=1； 步骤3，根据计算机存储空间的许可和实际需要，可选定30n为最大取值范围； 步骤4，生成可能素数族Kp₁，Kp₂，…，Kp_i，i=1，2，…，i，Kp_i≤30n-1； 步骤5，可能素数族中的“1”是一个特殊数，而非素数，予以删除； 步骤6，采用删除法，删除可能素数族中的合数；按照可能素数族Kp₁，Kp₂，…，Kp_i的数值大小，从小至大，依次进行如下操作：根据含Kp_i因子的合数的分布特点，保留Kp_i，而将含Kp_i因子的合数全部删除，直至我们要选择的范围30n； 步骤7，可能素数族Kp₁，Kp₂，…，Kp_i中的任一数值，一旦已在前面的操 作过程中被删除后，即不再保留，也不再重复上述步骤6的操作； 步骤8，删除操作直到选择范围30n内的最大素因子Kp_m，根据含Kp_m因子的合数的分布特点，保留Kp_m，而将含Kp_m因子的合数删除，直至我们要选择的范围30n，步骤9，经删除处理后，未被删除的数全都是素数，通过整序，存入计算机固定的存储单元内； 步骤10，根据用户需求，可提供全部和任意区段的素数族； 步骤11，利用大素数建立RSA密码系统的基本原理，完成下列步骤： (1)从步骤10提供的素数族中随机选择或挑选两个不相同的大素数p和q； (2)计算N=pq； (3)根据欧拉函数，不大于N而且与N互质的整数个数(4)选择一个整数e与(p-1)(q-1)互质，并且e小于(p-1)(q-1)； (5)用以下公式计算d：d×e≡1(mod(p-1)(q-1))； (6)将p和q的纪录销毁； (N，e)是公钥，(N，d)是私钥，(N，d)是秘密的，用户A将他的公钥(N，e)传给用户B，而将他的私钥(N，d)密藏起来； 加密消息：假设用户B想给用户A发送一个消息m，他知道用户A产生的N和e；他使用预先与用户A约定好的格式将m转换为一个小于N的整数M，比如他可以将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字；假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为M；用下面这个公式他可以将M加密为C： M^e≡C(mod N) 计算C并不复杂，用户B算出C后就可以将它传递给用户A； 解密消息：用户A得到用户B的消息C后就可以利用他自己的密钥d来解码；他可以用以下这个公式来将C转换为M： C^d≡M(mod N) 得到M后，他可以将原来的信息m重新复原。