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

Useful method to decode RSA

作　　者：杜立智[1,2] 

机构地区：[1]武汉科技大学计算机科学与技术学院,武汉430065 [2]智能信息处理与实时工业系统湖北省重点实验室,武汉430065

出　　处：《计算机工程与应用》2016年第14期119-124,共6页Computer Engineering and Applications

基　　金：湖北省自然科学基金(No.2014CFC1121)

摘　　要：通过长年研究得到了快速高效的Hamilton路算法。利用多项式规约将3SAT问题转化为对Hamilton路的求解。尽管国际上已有过如何将3SAT问题转化为Hamilton路的方法,但那只是为了证明Hamilton路的NP完全性,因而只要求转化的结果是多项式,而不注重转化效率。为了得到将3SAT直接转化为Hamilton路的高效转化方法,以便有可能通过对后者的高效计算来实现高效计算3SAT,采取用无向图的两个节点模拟3SAT的一个变量,用13个节点的图形结构来模拟3SAT的一个子式的方法,最终实现了上述转化。该转化所需要的节点数及其边数是最优的。将大数的质因子分解转化为对3SAT的求解,从而最终通过求解Hamilton环达到破译RSA密码之目的。It gets a fast algorithm on the Hamilton path. It transforms the 3SAT to the Hamilton path by a polynomial transform. Though there has been some methods to transform 3SAT to Hamilton path, that is only for NPC proof. It is polynomial but not the most efficient. In order to get the most efficient transform from 3SAT to Hamilton path, so as to calculate 3SAT efficiently by calculating the Hamilton path in a possibly good way, this paper uses two vertices to denote a variable in 3SAT, uses a good graph structure which contains 13 vertices to denote a clause in 3SAT, then realizes the above goal. It needs the least number of vertices and edges. It transforms the problem of large number of qualitative factors to 3SAT. So at last, it can decode the RSA by calculating the Hamilton path.

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

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]