Fast Triangularization of Ideal Latttice Basis
摘要
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.
引用本文（GB/T 7714）
Yang Zhang, Renzhang Liu, Dongdai Lin. Fast Triangularization of Ideal Latttice Basis[J]. 未知来源, 2020.
引文网络
本站仅收录题录与摘要供学习参考，全文版权归属出版方；如有侵权请联系我们删除。