Table of contents
1.
Introduction
2.
Know the minds behind the force:
2.1.
Stephen Pohlig
2.2.
Martin Edward Hellman
3.
Pohlig-Hellman algorithm
4.
Frequently Asked Questions
4.1.
In cryptography, what is a discrete logarithm problem?
4.2.
Is the discrete logarithm problem complex?
4.3.
What does a finite abelian group imply in the Pohlig–Hellman algorithm?
4.4.
How does the Pohlig-Hellman algorithm work?
5.
Conclusion
Last Updated: Mar 27, 2024

Pohlig and Hellman joined forces for this Algorithm

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Discrete logarithms are set-theoretic counterparts of regular algorithms in mathematics, notably in abstract algebra and its applications. A solution of the equation ax = b over the real or complex number is an ordinary algorithm loga(b). This article's blog incorporates information about how Pohlig and Hellman joined forces for the Pohlig–Hellman algorithm. Let's get started.

Pohlig and Hellman joined forces for this Algorithm

Know the minds behind the force:

Albert Einstein rightly said, "Everybody knows that something cannot be done until somebody shows up not knowing this and does it." To solve discrete logarithm problems like finding x in h=gx, utilize Pohlig-Logarithm Hellman's algorithm. The great minds of Stephen Pohlig and Martin Hellman came together to make this algorithm.

Stephen Pohlig

Stephen Pohlig

Stephen Pohlig, born on April 14, 1953, was an MIT Lincoln Laboratory electrical engineer. As a doctoral student of Martin Hellman at Stanford University, he helped create the principles of Diffie-Hellman key exchange, such as the Pohlig-Hellman exponentiation cipher and the Pohlig-Hellman algorithm for calculating discrete logarithms. That cipher is a forerunner of RSA (Rivest, Shamir, and Adleman) because all that is required to convert it to RSA is to change the arithmetic from modulo a prime integer to modulo a composite number. 

Martin Edward Hellman

Martin Edward Hellman

Martin Edward Hellman, born on October 2, 1945, is a mathematician and cryptologist best known for his work on public key cryptography alongside Whitfield Diffie and Ralph Merkle. Hellman has long been involved in the computer privacy debate and has used risk analysis to predict the breakdown of nuclear deterrence. Hellman was elected to the NAE in 2002 for his contributions to cryptography theory and practice.

Pohlig-Hellman algorithm

The Pohlig-Hellman approach computes the discrete logarithm in a multiplicative group with the order that is a smooth integer or an integer that factors entirely into small prime integers. The Poholig-Hellman algorithm computes the discrete log x such that e=gx mod p if such an x exists. 

Compute a0 in the equation given below:

eq1-------1

ais the first element of element a. α and β are positive real numbers. Next, compute γ, which is another real number. 

eq2 till we find γi = βn/q

For any, i ≤ q − 1. Now we can declare a0 = i.

Consider c=1 and β0 = β. Now we can generalize eq1 as follows:

eq3 

We can now understand that βj+1 can now be computed from βj 

eq4 

Frequently Asked Questions

In cryptography, what is a discrete logarithm problem?

The discrete logarithm problem is described as finding the discrete logarithm of base g of h in group G. Discrete logarithm problems are not usually complex. The difficulty of obtaining discrete logarithms varies according to the groupings.

Is the discrete logarithm problem complex?

While the DLP is widely regarded as a "hard problem," its complexity is determined not by the group's order (or structure) but by how the group is explicitly represented.

What does a finite abelian group imply in the Pohlig–Hellman algorithm?

A finite abelian group meets the corresponding conditions: it has both finite and abelian properties. 

How does the Pohlig-Hellman algorithm work?

The Pohlig-Hellman Algorithm computes a Discrete Logarithm for multiplicative groups where their order is a smooth integer. That is, its order may be factored into tiny primes. Here, y is the public key, and x is the secret key we're attempting to compute. 

Conclusion

This article incorporates information about how Pohlig and Hellman joined forces for the Pohlig–Hellman algorithm.

To learn more about cryptography, check out the following articles.

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Happy Learning!

Live masterclass