一个可行的RSA密码破译方法

摘要：

通过长年研究得到了快速高效的Hamilton路算法。利用多项式规约将3SAT问题转化为对Hamilton路的求解。尽管国际上已有过如何将3SAT问题转化为Hamilton路的方法，但那只是为了证明Hamilton路的NP完全性，因而只要求转化的结果是多项式，而不注重转化效率。为了得到将3SAT直接转化为Hamilton路的高效转化方法，以便有可能通过对后者的高效计算来实现高效计算3SAT，采取用无向图的两个节点模拟3SAT的一个变量，用13个节点的图形结构来模拟3SAT的一个子式的方法，最终实现了上述转化。该转化所需要的节点数及其边数是最优的。将大数的质因子分解转化为对3SAT的求解，从而最终通过求解Hamilton环达到破译RSA密码之目的。

关键词：非确定性多项式(NP)完全、多项式规约、Hamilton路、3SAT、RSA密码

所属期刊栏目：52

分类号：TP301.5(计算技术、计算机技术)

资助基金：湖北省自然科学基金No.2014CFC1121。

在线出版日期：2016-08-03（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：119-124