一种基于ICA的离散对数求解方法  

A method for computing discrete logarithm based on ICA

作　　者：胡建军 HU Jianjun(School of Digital Media,Lanzhou University of Arts and Science,Lanzhou 730010,China)

机构地区：[1]兰州文理学院数字媒体学院,甘肃兰州730010

出　　处：《武汉大学学报（工学版）》2021年第9期874-878,共5页Engineering Journal of Wuhan University

基　　金：国家自然科学基金项目(编号:61070162、71071028);甘肃省高等学校科学研究项目(编号:2015B-136);兰州文理学院服务地方经济社会发展计划项目(编号:2021FWDF15)。

摘　　要：ICA(index calculus algorithm)是一种计算离散对数的概率型算法,存在盲目性和计算效率不高的问题,为此,利用取整函数的一些性质和同余运算的特点,提出一种基于ICA的改进算法,即IICA(improved index calculus algorithm)。IICA将所求对数中未知的素因子逐个变换到分解基中的元素,然后计算离散对数。实例验证表明,该算法是可行和有效的,与已有算法相比,具有明显的优越性。The index calculus algorithm(ICA) is a probabilistic algorithm of computing discrete logarithms. The ICA is blind on solving discrete logarithms, and is not high for computation efficiency. Therefore, by using some properties of integral function and the characteristics of congruence arithmetic, an improved algorithm based on ICA is put forward. The improved index calculus algorithm(IICA)transforms the unknown element factors of the logarithm to the elements in the decomposition base one by one. Finally, the IICA computes discrete logarithm. Example shows that the IICA is feasible and effective. Compared with the existing algorithm, the IICA has the obvious superiority.

关 键 词：离散对数 分解基 取整函数 因子分解 乘法群 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]