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

A method for computing discrete logarithm based on ICA

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.