Pohlig Hellman Algorithm Calculator

Calculator Input

Prime modulus p

Use a prime number, such as 337.

Base g

The generator or subgroup base.

Target h

Solve g raised to x equals h.

Group order mode

Custom group order

Used only when custom mode is selected.

Max prime-power search

Raises safety for expensive subgroup logs.

Show detailed study rows

Formula Used

Discrete logarithm: find x where g^x ≡ h (mod p).

Group factorization: n = ∏ q_i^{e_i}. For a prime modulus, auto mode uses n = p - 1.

Prime-power reduction: for m_i = q_i^{e_i}, compute g_i = g^(n / m_i) and h_i = h^(n / m_i).

Subgroup logarithm: solve g_i^{x_i} ≡ h_i (mod p), giving x ≡ x_i (mod m_i).

CRT rebuild: combine all congruences to get x mod n.

How to Use This Calculator

Enter a prime modulus p.
Enter the base g and target h.
Keep auto order when the full multiplicative group is used.
Use custom order only when the subgroup order is known.
Set a search limit to prevent expensive subgroup solving.
Press calculate and review the result above the form.
Download the step table as CSV or PDF.

Example Data Table

Example input: p = 337, g = 10, h = 235, and n = 336. The answer is x ≡ 123 mod 336.

Prime power	n / power	Reduced base	Reduced target	Residue	Congruence
2^4 = 16	21	191	278	11	x ≡ 11 mod 16
3^1 = 3	112	128	1	0	x ≡ 0 mod 3
7^1 = 7	48	175	79	4	x ≡ 4 mod 7

Pohlig Hellman Algorithm Guide

Why the Method Matters

The Pohlig Hellman algorithm is a classic method for solving discrete logarithms when the group order is smooth. A smooth order has small prime power factors. That structure lets a hard problem become several smaller problems.

Core Problem

A discrete logarithm asks for x in g^x ≡ h mod p. Direct search may be slow. Pohlig Hellman first factors the group order n. It then solves x modulo each prime power factor. Each smaller congruence is easier than solving the full logarithm at once.

Calculator Method

This calculator uses the prime modulus group by default. It sets n = p - 1 when auto order is selected. You may also enter a custom group order. This helps when the base has a known subgroup order. The tool reduces the target for every prime power. Then it solves each reduced logarithm with baby-step giant-step search.

Result Reconstruction

After all residues are found, the calculator combines them with the Chinese Remainder Theorem. The final result is x modulo n. A verification step checks whether g^x matches h under the selected modulus. This is important because some inputs do not have a solution.

Reading the Steps

The step table is useful for learning. It shows each factor, exponent, reduced base, reduced target, residue, and congruence. These values make the method transparent. They also help students check manual work.

Graph Insight

The graph compares each prime power factor with its discovered residue. Large bars show which subgroup created the largest search task. Small bars show easier parts of the calculation. This view is simple, but it gives a fast check of the problem shape.

Practical Limits

Use small or moderate integers for browser and server comfort. Very large cryptographic numbers need big integer libraries and optimized code. This page is intended for education, coursework, demonstrations, and quick number theory experiments.

Security Lesson

Pohlig Hellman is powerful because it attacks structure. It does not make every discrete logarithm easy. It works best when the group order breaks into small factors. If the order contains one huge prime factor, that part still controls the cost. This is why secure systems choose groups with strong prime factors. For study problems, smooth orders are ideal. They reveal the complete flow of factoring, subgroup solving, and CRT reconstruction.

FAQs

What does this calculator solve?

It solves discrete logarithm problems of the form g^x ≡ h mod p. It is designed for prime modulus examples and smooth group orders.

Why must the group order be smooth?

The method becomes efficient when the group order splits into small prime powers. Each prime-power problem is much smaller than the full problem.

What is auto order mode?

Auto mode sets the group order to p - 1. This follows the size of the multiplicative group modulo a prime p.

When should I use custom order?

Use custom order when g belongs to a known subgroup. The custom order should divide p - 1 for prime modulus calculations.

What does the residue mean?

A residue gives x modulo one prime-power factor. The calculator combines all residues to form the final x using CRT.

Why can verification fail?

Verification can fail when h is not in the subgroup generated by g, the selected order is wrong, or no valid logarithm exists.

Can this handle real cryptographic sizes?

No. This version uses standard integer arithmetic for learning. Real cryptographic numbers need big integer support and specialized algorithms.

What export options are included?

You can export the computed factor table as a CSV file. You can also create a simple PDF summary from the result.