基于中国剩余定理的素数搜索算法
发布时间：2021-02-10 04:35
公钥密码算法是素数的一个重要应用途径,例如经典的RSA算法现已渗透到人们信息生活的各个方面,保护着用户的信息安全。公钥密码算法的优点在于不需要像对称加密算法一样采用安全的信道传输密钥,但是公钥密码的计算开销以及前期的素数产生开销都比较大。针对素数产生开销大这一问题,本文借助于中国剩余定理对素数在多维空间中的分布规律进行了研究,并在此基础之上设计了一种相对高效的素数搜索算法,能够有效减少在一个区间内搜索素数时所需检查整数的数量,在一定程度上减小了素数搜索的负担,增加了素数搜索的效率。
【文章来源】：网络安全技术与应用. 2019,(06)
【文章页数】：2 页
【部分图文】：
[0,34]区间整数映射结果
安全模型、算法与编程‖28‖数被映射到一个三维空间。由于在区间内的数均小于M，故三元组中元素k=y/M始终为0，因此可将映射结果在1,2平面上投影，如图1所示。如果对区间中包含大于M的数进行映射，如将区间[0,699]中的整数进行映射，则效果如图2所示，此时k≥0，是k取不同值时图1在垂直方向上的叠加。图中用“o”标注的位置，其坐标(1,2)中均不含0元素，是素数可能出现的位置，而用“×”标注的位置，其坐标(1,2)中至少含有一个0元素，这些位置一定不会出现素数。图1[0,34]区间整数映射结果图2[0,699]区间整数映射结果从图1、图2可以看出，在一个区间内搜索素数时并不需要搜索全部的整数，而只需要搜索、检查图中由“o”标记的映射点所对应的整数即可找到该区间内的全部素数，这样便实现了缩小素数搜索范围的目的，提升了算法的性能。但从图2可以看出，实际要搜索的点并没有减少很多，搜索范围仅仅缩小到了原来的0.6857（480/700）。原因在于，算法的性能与序列的取值及元素个数均有关系，在上述例子中，为了所绘制的图像易于理解，序列元素的个数及取值并不是最优的，选取更优的序列将进一步缩小整数的搜索范围，带来更大的性能提升。4算法思路及性能分析由上述分析我们得知了素数在多维空间中分布的大致规律，而算法也将按照此分布规律在区间中只筛选部分整数进行检查，以加快在区间内的素数搜索的速度。算法首先根据选定的序列构造所有不带0元素的序列，并利用中国剩余定理分别求解各序列所对应同余方程组在[0,M]区间内的解，对于得到的每一个解，都将作为一次搜索的起点。算法搜索过程每次都将从一个未检查过的
潭?实际搜索整数数量搜索区间长度。当选取的序列为{1,2,3,…,}时，一个随机整数与中元素分别做模运算可能产生的序列共有∏=1组，除去包含0元素的序列后，剩余∏(1)=1组，不难看出，对于选定的序列而言，算法的性能优化公式为:∏(1)=1∏=1，根据公式可知道算法性能的极限为：lim→∞∏(1)=1∏=1。如果序列选取从2开始的一系列素数作为其元素，选取不同的个数将对应于不同的搜索性能，如图3所示的是当序列选取素数集中由2开始的连续n个元素时对应∏(1)=1∏=1的散点图。该图的最后一个点是当选取从2开始的连续83个素数作为序列中元素时的性能优化程度，此时∏(1)=1∏=1=0.0946，寻找素数所要搜索的整数集合已经缩小至原来的10%以下。值得一提的是，算法前期预处理工作的时间复杂度只与序列的元素数量有关，而与所要搜索区间的区间长度无关。并且预处理工作完成后，可将预处理工作的结果保留下来，以便下一次使用时可以直接导入程序，避免不必要的重复计算。图3算法性能优化程度散点图分析性能优化公式可知，随着序列中元素越来越多，∏(1)=1∏=1越来越小，也就意味着，素数可能出现的位置越来越少。这一分析结果间接验证了这样一个事实：整数越大，其成为素数的可能性就越低，同样长度的连续区间中，数值均值越大的区间，素数的个数可能越少。5算法实验结果及结论验证理解了算法的原理就可以利用具体的编程语言对算法进行实现，本文结合上述理论，利用Java语言实现了该算法，并打印出了关键的数据作?
【参考文献】：
期刊论文
[1]RSA算法中快速生成大素数方法的改进[J]. 王萍,廖芳燕,廖芳午,张树贵. 重庆文理学院学报(自然科学版). 2009(03)
本文编号：3026790
【文章来源】：网络安全技术与应用. 2019,(06)
【文章页数】：2 页
【部分图文】：
[0,34]区间整数映射结果
安全模型、算法与编程‖28‖数被映射到一个三维空间。由于在区间内的数均小于M，故三元组中元素k=y/M始终为0，因此可将映射结果在1,2平面上投影，如图1所示。如果对区间中包含大于M的数进行映射，如将区间[0,699]中的整数进行映射，则效果如图2所示，此时k≥0，是k取不同值时图1在垂直方向上的叠加。图中用“o”标注的位置，其坐标(1,2)中均不含0元素，是素数可能出现的位置，而用“×”标注的位置，其坐标(1,2)中至少含有一个0元素，这些位置一定不会出现素数。图1[0,34]区间整数映射结果图2[0,699]区间整数映射结果从图1、图2可以看出，在一个区间内搜索素数时并不需要搜索全部的整数，而只需要搜索、检查图中由“o”标记的映射点所对应的整数即可找到该区间内的全部素数，这样便实现了缩小素数搜索范围的目的，提升了算法的性能。但从图2可以看出，实际要搜索的点并没有减少很多，搜索范围仅仅缩小到了原来的0.6857（480/700）。原因在于，算法的性能与序列的取值及元素个数均有关系，在上述例子中，为了所绘制的图像易于理解，序列元素的个数及取值并不是最优的，选取更优的序列将进一步缩小整数的搜索范围，带来更大的性能提升。4算法思路及性能分析由上述分析我们得知了素数在多维空间中分布的大致规律，而算法也将按照此分布规律在区间中只筛选部分整数进行检查，以加快在区间内的素数搜索的速度。算法首先根据选定的序列构造所有不带0元素的序列，并利用中国剩余定理分别求解各序列所对应同余方程组在[0,M]区间内的解，对于得到的每一个解，都将作为一次搜索的起点。算法搜索过程每次都将从一个未检查过的
潭?实际搜索整数数量搜索区间长度。当选取的序列为{1,2,3,…,}时，一个随机整数与中元素分别做模运算可能产生的序列共有∏=1组，除去包含0元素的序列后，剩余∏(1)=1组，不难看出，对于选定的序列而言，算法的性能优化公式为:∏(1)=1∏=1，根据公式可知道算法性能的极限为：lim→∞∏(1)=1∏=1。如果序列选取从2开始的一系列素数作为其元素，选取不同的个数将对应于不同的搜索性能，如图3所示的是当序列选取素数集中由2开始的连续n个元素时对应∏(1)=1∏=1的散点图。该图的最后一个点是当选取从2开始的连续83个素数作为序列中元素时的性能优化程度，此时∏(1)=1∏=1=0.0946，寻找素数所要搜索的整数集合已经缩小至原来的10%以下。值得一提的是，算法前期预处理工作的时间复杂度只与序列的元素数量有关，而与所要搜索区间的区间长度无关。并且预处理工作完成后，可将预处理工作的结果保留下来，以便下一次使用时可以直接导入程序，避免不必要的重复计算。图3算法性能优化程度散点图分析性能优化公式可知，随着序列中元素越来越多，∏(1)=1∏=1越来越小，也就意味着，素数可能出现的位置越来越少。这一分析结果间接验证了这样一个事实：整数越大，其成为素数的可能性就越低，同样长度的连续区间中，数值均值越大的区间，素数的个数可能越少。5算法实验结果及结论验证理解了算法的原理就可以利用具体的编程语言对算法进行实现，本文结合上述理论，利用Java语言实现了该算法，并打印出了关键的数据作?
【参考文献】：
期刊论文
[1]RSA算法中快速生成大素数方法的改进[J]. 王萍,廖芳燕,廖芳午,张树贵. 重庆文理学院学报(自然科学版). 2009(03)
本文编号：3026790
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3026790.html
