Pohlig-Hellman Algorithm for solving a DLP - can $x_0$ have > 1 solution?

Question

I have taken generator $g=3$, $h=5$, and prime $p=101$ So;

$$3^x=5 \mod 101$$

Following steps of Polig-Helman I get;

1. $p-1=100=5^{2}.2^{2}$ Hence largest prime power divisor $q^e=5^2$.
2. Calculate $g^{\frac{p-1}{q^e}}=81 \mod 101$
3. Calculate $h^{\frac{p-1}{q^e}}=19 \mod 101$
4. Hence $$81^x=19, \mod 101$$
5. Now since $q=5$ and $e=2$, I set $x=x_0+5x_1$, with $0 \leq x_i<q=5$
6. Now raising both sides of 4. to $q^e$ I get: $$(81^{5^2})^{x_0}=19^{5^2} \mod 101$$
7. Simplifying this I get: $$1^{x_0}=1 \mod 101$$

Now since $0 \leq x_i<q=5$, the possible values of $x_0$ from 7. are: $(0,1,2,3,4)$.

Questions:

1. Is my working correct?
2. Can there be more than one solution for $x_0$ similar to the example above? If yes, why?

Answer 1

As a guide, we will use the MSE post - Use Pohlig-Hellman to solve discrete log.

A description of the algorithm can be found in

• $(1)$ A Course in Number Theory and Cryptography, 2nd Ed., N. Koblitz
• $(2)$ An Introduction to Mathematical Cryptography, J. Hoffstein, J. Pipher, J. H. Silverman
• $(3)$ Number Theory for Computing, 2nd Ed., S. Y. Yan
• $(4)$ An Introduction to Cryptography, R. A. Mollin

We will use the Pohlig-Hellman algorithm to solve a Discrete Log Problem to find $x$ in

$$3^x = 5 \pmod{101}$$

Using the notation from $(2)$

$$g^x = h \pmod p$$

We have

$$g = 3, h = 5, p = 101, N = p - 1 = 100 = \prod_{i=1}^{n} q_i^{e_i} = q_1^{e_1} \cdot q_2^{e_2} = 2^2 \cdot 5^2 $$

We can summarize the necessary algorithm calculations in a handy table as

$$\begin{array}{|c|c|c|c|c|} \hline \large q & \large e & \large g^{(p-1)/q^e} & \large h^{(p-1)/q^e} & \mbox{Solve}~ \large \left(g^{(p-1)/q^e} \right)^x = ~ \large h^{(p-1)/q^e}~ \mbox{for} ~ \large x \\ \hline 2 & 2 & 10 & 1 & \mbox{Calculation I = ?}\\ \hline 5 & 2 & 81 & 19 & \mbox{Calculation II = ?}\\ \hline \end{array}$$

Calculation I: Solve

$$x \equiv x_0 + x_1q + \ldots + x_{e-1}q^{e−1} \pmod {2^2} \equiv x_0 + 2x_1 \pmod {2^2}$$

• Solve $(10)^x = 1 \pmod {101}$ for $x_0, x_1$.
• $x_0: (10^{2^1})^{x_0} = 100^{x_0} = 1^{2^1} \pmod {101} \implies (100)^{x_0} = 1 \pmod{101} \implies x_0 = 2$
• $x_1: (10^{2^1})^{x_1} = 100^{x_1} = (1 \times 10^{-x_0})^{2^0} \pmod {101} \implies (100)^{x_1} = 100 \pmod{101} \implies x_1 = 1$

Our first result is

$$x \equiv x_0 + 2 x_1 \pmod {2^2} \equiv 2 + 2 \pmod {2^2} \equiv 0 \pmod {2^2}$$

Calculation II: Solve

$$x \equiv x_0 + x_1q + \ldots + x_{e-1}q^{e−1} \pmod {5^2} \equiv x_0 + 5 x_1 \pmod {5^2}$$

• Solve $(81)^x = 19 \pmod {101}$ for $x_0, x_1$.
• $x_0: (81^{5^1})^{x_0} = 84^{x_0} = 19^{5^1} \pmod {101} = 84 \pmod{101} \implies x_0 = 1$.
• $x_1: (81^{5^1})^{x_1} = 84^{x_1} = (19 \times 81^{-x_0})\pmod{101} = (19 \times 81^{-1})\pmod{101} = (19 \times 5)\pmod{101} = 95\pmod{101} \implies x_1 = 4$

Our second result is

$$x \equiv x_0 + 5 x_1 \pmod {5^2} \equiv 21 \pmod {5^2}$$

Next, use the Chinese Remainder Theorem to solve the simultaneous congruence's

$$x \equiv 0 \pmod {2^2} , ~~ x \equiv 21\pmod {5^2}$$

The result is

$$x \equiv 96 \pmod{2^2 \times 5^2}$$

Check the answer

$$3^{96} = 5 \pmod {101} ~~ \Large{\checkmark}$$

Addendum

The answers to your two specific questions are

• Is my working correct? No, see the answer above.
• Can there be more than one solution for $x_0$ similar to the example above? Yes. If yes, why? Because of modular arithmetic, but you should always use the smallest one. Also, whichever you choose, it will not affect the final answer.