离散对数求解算法

摘要

离散对数问题是算法数论中的一个重要研究课题,而且有广泛的应用。特别地,离散对数问题的求解困难性是相关密码学方案安全性的基础。文章描述了以有限阶循环群为基本研究对象的离散对数问题定义和其变形,综述了离散对数问题的求解算法。首先,介绍了通用算法,其中量子算法可以高效求解一大类离散对数问题,而经典的通用算法时间复杂度较高。其次,展示了指标计算框架,在具体加速求解离散对数中有广泛的应用。最后,重点介绍基于有限域乘法单位群和椭圆曲线加法群离散对数的求解算法和相关进展。基于有限域乘法群单位群离散对数问题的求解困难性和有限域的特征密切相关,基于小特征的有限域离散对数可以设计更高效的求解算法。而目前求解一般椭圆曲线离散对数问题的经典算法仍然是指数时间的算法。

关键词

离散对数问题 / 算法 / 有限域 / 椭圆曲线

基金资助

国家自然科学基金资助项目(62002015); 国家重点研发计划资助项目(2018YFA0704702,2021YFB3100200); 中央高校基本科研业务费专项资金资助项目(2021RC259); 山东省自然科学基金重大基础研究资助项目(ZR202010220025)