Finding discrete logarithm in F_p^*

arXiv2104.13310MaRDI QIDQ6366271FDOQ6366271

Publication date: 27 April 2021

Abstract: 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.

This page was built for publication: Finding discrete logarithm in $F_p^* $

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6366271)