| 理想格上格基的快速三角化算法研究 |
| |
| 引用本文： | 张洋, 刘仁章, 林东岱. 理想格上格基的快速三角化算法研究[J]. 电子与信息学报, 2020, 42(1): 98-104. doi: 10.11999/JEIT190725 |
| |
| 作者姓名： | 张洋 刘仁章 林东岱 |
| |
| 作者单位： | 1.中国科学院信息工程研究所信息安全国家重点实验室 北京 100093;;2.中国科学院大学网络空间安全学院 北京 100049;;3.卫士通摩石实验室 北京 100166 |
| |
| 摘 要： | 为了提高理想格上格基的三角化算法的效率，该文通过研究理想格上的多项式结构提出了一个理想格上格基的快速三角化算法，其时间复杂度为O(n3log2B)，其中n是格基的维数，B是格基的无穷范数。基于该算法，可以得到一个计算理想格上格基Smith标准型的确定算法，且其时间复杂度也比现有的算法要快。更进一步，对于密码学中经常所使用的一类特殊的理想格，可以用更快的算法将三角化矩阵转化为格基的Hermite标准型。
|
| 关 键 词： | 理想格 Hermite标准型 Smith标准型 三角化 |
| 收稿时间： | 2019-09-19 |
| 修稿时间： | 2019-11-15 |
Fast Triangularization of Ideal Latttice Basis |
| |
| Yang ZHANG, Renzhang LIU, Dongdai LIN. Fast Triangularization of Ideal Latttice Basis[J]. Journal of Electronics & Information Technology, 2020, 42(1): 98-104. doi: 10.11999/JEIT190725 |
| |
| Authors: | Yang ZHANG Renzhang LIU Dongdai LIN |
| |
| Affiliation: | 1. State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China;;2. School of Cyber Security,University of Chinese Academy of Sciences, Beijing 100049, China;;3. Westone Cryptologic Research Center, Beijing 100166, China |
| |
| Abstract: | To improve the efficiency of the triangularization of ideal lattice basis, a fast algorithm for triangularizing an ideal lattice basis is proposed by studying the polynomial structure, which runs in time O(n3log2B), where n is the dimension of the lattice, B is the infinity norm of lattice basis. Based on the algorithm, a deterministic algorithm for computing the Smith Normal Form (SNF) of ideal lattice is given, which has the same time complexity and thus is faster than any previously known algorithms. Moreover, for a special class of ideal lattices, a method to transform such triangular bases into Hermite Normal Form (HNF) faster than previous algorithms will be present. |
| |
| Keywords: | Ideal lattice Hermite Normal Form (HNF) Smith Normal Form (SNF) Triangularization |
|
| 点击此处可从《电子与信息学报》浏览原始摘要信息 |
|
点击此处可从《电子与信息学报》下载全文 |
|
