Difficulty of calculation of discrete logarithm for any arbitrary Field is the basis for security of several popular cryptographic solutions. Pohlig-Hellman method is a popular choice to calculate discrete logarithm in finite field $F_p^*$. Pohlig-Hellman method does yield good results if p is smooth ( i.e. p-1 has small prime factors). We propose a practical alternative to Pohlig-Hellman algorithm for finding discrete logarithm modulo prime. Although, proposed method, similar to Pohlig-Hellman reduces the problem to group of orders $p_i$ for each prime factor and hence in worst case scenario (including when p=2q+1 , q being another prime) order of run time remains the same. However in proposed method, as there is no requirement of combining the result using Chinese Remainder Theorem and do the other associated work ,run times are much faster.
翻译:难以计算任意字段的离散对数是若干流行加密解决方案安全的基础。 Pohlig- Hellman 方法是计算有限字段的离散对数的流行选择 $F_ p ⁇ $。 Pohlig- Hellman 方法如果p 平滑( 即 p-1 有小主要因素 ), 确实会产生良好的效果 。 我们建议了比 Pohlig- Hellman 算法更实用的替代算法, 以寻找离散对数元元。 虽然, 与 Pohlig- Hellman 类似的方法, 将问题降低到每个质因子的单价 $p i, 从而在最坏的情况下( 包括当 p=2q+1, q 是另一个主数) 运行时间顺序仍然相同 。 但是, 在拟议方法中, 没有要求使用中文保留论和做其它相关工作的结果组合, 运行时间要快得多 。