线性同余方程组的快速解法及在现代密码学的应用

摘要：

对于大整数n,提出判断模数m的n阶线性同余方程组是否有解并在有解时求出解的快速算法,算法的时间复杂度仅为O(n<”2>)次模m乘法,优于现有快速算法的O(n<”2.81>)次模m乘法时间复杂度。NTRU密码体制是当今最先进、最高效的公钥密码方案之一,但由于多项式截断环上的乘法逆元素不一定存在,给构造私钥造成一定困难。应用本快速算法可以快速地生成NTRU密码体制的私钥。结论可用于信息检索与分析、多媒体内容安全领域。

关键词： 快速算法 线性同余方程组 平方时间 公钥密码 NTRU密码体制

作者: 王泽辉 方小洵

作者单位: 中山大学科学计算与计算机应用系 广州 510275 广东省科技情报所 广州 510033

会议类型: 国内会议

会议名称: 第五届全国数字博物馆与文化自然遗产数字化及保护研讨会

会议地点: 苏州

会议语种:中文

页码: 227-230

在线出版日期: 2007-12-07（万方平台首次上网日期，不代表论文的发表时间）