一种基于行公因子提取的改进Coppersmith算法

摘要

1996年欧密会上,Coppersmith提出一种对单变元模方程求小根的多项式时间算法,该算法对公钥密码系统的安全性分析具有重要意义.结合Coppersmith算法中格基矩阵的结构特点和元素性质提出一种改进算法,通过逐次提取格基矩阵不同块中行向量的公因子,有效降低了Coppersmith算法的求解时间.同时通过实验证明了此改进算法可有效兼容一种预处理算法,通过将这两种算法结合,进一步提高了Coppersmith算法的求解效率,实验表明较原Cop-persmith算法最高可提升22.64％.