基于密码学技术应用的大数快速分解方法

摘要

本发明公开了一种基于密码学技术应用的大数快速分解方法，采用同余理论与合数分布规律的有机结合，通过压缩正整数、建立殆素数族、选定最大取值范围、生成殆素数族、分解大数、对数位进行设定及删合数除等步骤，生成一种创造性的大数快速分解方法。本方法不同于传统大数分解方法，不须依赖计算速度就可对n内任意选取的一个大数进行快速因子分解，不必进行大量耗的复杂运算，而是应用计算机软件经过简单的鉴别处理即可实现，因此可以实现快速分解。从而能极大地推动相关公钥体系安全性的评估和改善，可广泛应用于信息安全和密码学技术应用领域。

主权项

1.一种基于密码学技术应用的大数快速分解方法：其分解步骤如下：步骤1，压缩正整数，建立模M＝30的缩剩余系。选取M＝30为模，求其对正整数的同余类，并做出其缩剩余系，由Euler函数：得到：从而可形成八个等差数列；步骤2，建立素数族，在与模M＝30互素的八类中各取出一个代表数a₁，，…，a₈，它们依次为：1、7、11、13、17、19、23、29；于是7以上的素数p均可用模M＝30的缩剩余系表出，即：$P=\left\{\begin{array}{c}{a}_1\\ ·\\ ·\\ ·\\ a_8\end{array}\right.\left(\mathrm{mod}30\right);$本发明将上式表示的全部数值定义为殆素数族，并记作Kp，于是有：Kp＝a+30(n-1)；其中：n≥1，a＜30、且(a，30)＝1；步骤3，根据计算机存储空间的许可和实际需要，可选定30n为最大取值范围；步骤4，生成殆素数族Kp₁，Kp₂，…，Kp_s，其中，Kp_s≤30n-1；步骤5，将拟分解的大数M代入公式：Kp＝a+30(n-1)，即：M＝a+30(n-1)；从而可找出该数值M在殆素数表中的确定位置，即所在列(n)和行(a)的位置；步骤6，将该数位进行设定，即当计算机执行删除程序并删除到该数位时，程序能够自动停止并发出提示；步骤7，采用删除法，删除殆素数族中的合数；按照殆素数族Kp₁，Kp₂，…，Kp_m的数值大小(其中)，依次进行如下操作：根据含Kp_i因子的合数的分布特点，将含Kp_i因子的合数全部删除，直至要选择的范围30n；步骤8，当删除操作运行到删除数值M所在位置时，程序自动停止运行并发出提示；步骤9，程序停止前正执行的是删除某素因子合数的操作，该素因子即为数值M的因子；步骤10，将其另一个因子也按上述方法处理，直至确认它也是素因子为止。