理想格上格基的快速三角化算法研究

作     者：张洋 刘仁章 林东岱 ZHANG Yang;LIU Renzhang;LIN Dongdai

作者机构：中国科学院信息工程研究所信息安全国家重点实验室北京100093 中国科学院大学网络空间安全学院北京100049 卫士通摩石实验室北京100166 

出 版 物：《电子与信息学报》 (Journal of Electronics & Information Technology)

年 卷 期：2020年第42卷第1期

页      面：98-104页

核心收录：

学科分类：11[军事学] 1105[军事学-军队指挥学] 0839[工学-网络空间安全] 08[工学] 110505[军事学-密码学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：理想格 Hermite标准型 Smith标准型 三角化 

摘      要：为了提高理想格上格基的三角化算法的效率,该文通过研究理想格上的多项式结构提出了一个理想格上格基的快速三角化算法,其时间复杂度为O(n3log2B),其中n是格基的维数,B是格基的无穷范数。基于该算法,可以得到一个计算理想格上格基Smith标准型的确定算法,且其时间复杂度也比现有的算法要快。更进一步,对于密码学中经常所使用的一类特殊的理想格,可以用更快的算法将三角化矩阵转化为格基的Hermite标准型。