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