preprint Open access

Finding discrete logarithm in $F_p^* $

  • arXiv (Cornell University)
  • Cornell University
Research footprint

At a glance

Citations
0
References
4
Comments
0
Paper overview

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.

Record transparency

Publication details

DOI
10.48550/arxiv.2104.13310
OpenAlex
W3159672157
Document type
preprint
Language
EN
Source
arXiv (Cornell University)
Last metadata update
Community

Comments

Log in to join the discussion.

  1. No comments yet. Start the discussion.