文档名：计算Hermite标准型的新算法
作为整数矩阵的一种标准型,HermiteNormalForm(HNF)在计算数论和(基于格的)公钥密码体制中有着重要的应用.现有的算法常通过使用模行列式的方法来控制中间系数膨胀.在本文中,基于解线性同余方程组的思想,提出两个计算整数矩阵的HNF的新算法.由于同余方程组中的模数是行列式的因子,在实际中往往比行列式小,因此能更好地控制中间系数膨胀的问题.基于这一技术,(1)首先给出一个想法上更清晰易懂的算法.在不考虑快速矩阵运算的情况下,该算法与目前计算HNF最快的算法有相同的时间复杂度.(2)将这一算法进一步改进,得到一个在实际中效率更高的算法.对于随机生成的方阵,新算法比NTL库中实现的算法快4倍.
作者：刘仁章 潘彦斌
作者单位：卫士通摩石实验室,北京市丰台区,100070中国科学院数学与系统科学研究院,北京市海淀区,100190
母体文献：中国密码学会2018年年会论文集
会议名称：中国密码学会2018年年会
会议时间：2018年10月27日
会议地点：成都
主办单位：中国密码学会
语种：chi
分类号：TP3O15
关键词：密码算法 整数矩阵 Hermite标准型 中间系数膨胀 同余方程组
在线出版日期：2021年12月15日
基金项目：
相似文献
相关博文
- 文件大小:
- 721.04 KB
- 下载次数:
- 60
-
高速下载
|
|
