一种改进的Index Calculus算法

An improving algorithm of index calculus

IC(index calculus)是一种计算离散对数的概率型算法,存在盲目性和计算效率不高的问题,为此,利用多项式度逐渐下降的方法,提出一种基于IC算法的改进算法,简称IIC算法。改进算法讨论了当光滑界为指数的1/2时,将所求对数中未知多项式因式逐个变换到分解基中,然后计算出离散对数。IIC算法将IC算法中尝试求解的方法改变成寻找已知不可约多项式的方法,即从概率型算法转换为确定型算法,避免了盲目性,计算效率有了一定的提升。实例验证表明,IIC算法的可行和有效性。复杂性分析表明,IIC算法具有明显的优越性。

The IC（ index calculus） is a probabilistic algorithm of computing discrete logarithms,which has problems of blind on solving discrete logarithms and low efficiency on computation. Therefore,as the smooth boundary be index of 1 /2,with strategy of polynomial degree gradually declining,an improved algorithm based on IC was put forward,referred to as IIC. The IIC transforms unknown irreducible polynomial factor to factor base one by one.Finally,an individual discrete logarithm was computed by the IIC. The ICC transformed the IC＇s testing way to find irreducible polynomial based on factor base so that the ICC became an algorithm of determining. The IIC was high effective because of avoiding blindness. Some examples showed the IIC was feasible and effective. By complexity analysis,the IIC has the obvious superiority.