离散对数求解算法

作     者：庄金成 朱玉清 ZHUANG Jin-cheng;ZHU Yu-qing

作者机构：山东大学网络空间安全学院/密码技术与信息安全教育部重点实验室山东青岛266237 北京交通大学智能交通数据安全与隐私保护技术北京市重点实验室/计算机与信息技术学院北京100044 

出 版 物：《广州大学学报（自然科学版）》 (Journal of Guangzhou University:Natural Science Edition)

年 卷 期：2021年第20卷第4期

页      面：16-28页

学科分类：0839[工学-网络空间安全] 08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

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

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

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