📂Number Theory

Discrete Logarithm Problems Solved Easily Under Certain Conditions

Review ¹

Assume element $g$ of group $G = F_{p}$ has an order of $N$. Then, the Discrete Logarithm problem $g^{x} = h$ becomes relatively easy to solve under the following conditions:

• (i): $p$ is a smooth prime number.
• (ii): $p \equiv 3 \pmod{4}$ and $a$ are quadratic residues modulo $p$.

Proof

(i)

If $p$ is a smooth prime, the Pohlig-Hellman algorithm can be used, so the Discrete Logarithm problem is relatively easy to solve.

■

(ii)

$$x^{2} \equiv a \pmod{p}$$ $a$ being a quadratic residue modulo $p$ means there exists a solution that satisfies the above congruence equation. If the remainder of prime $p$ divided by $4$ is $3$, $$b \equiv a^{(p+1)/4} \pmod{p}$$ then for some $a \equiv g^{2k} \pmod{p}$, $$\begin{align*} b^{2} \equiv & a^{{ p+1 } \over { 2 }} & \pmod{p} \\ \equiv & \left( g^{2k} \right)^{{ p+1 } \over { 2 }} & \pmod{p} \\ \equiv & g^{(p+1)k} & \pmod{p} \\ \equiv & g^{2k + (p-1)k} & \pmod{p} \\ \equiv & a \cdot \left( g^{p-1} \right)^{k} & \pmod{p} \\ \equiv & a & \pmod{p} \end{align*}$$ thus it becomes a solution to the given congruence equation. With this formula, the square root of $a$ can be found very quickly, making the Discrete Logarithm problem relatively easy to solve.

■

See Also

• Discrete Logarithm problem

Security algorithms utilizing the difficulty of the Discrete Logarithm problem

• Diffie-Hellman Key Exchange algorithm
• ElGamal Public Key Cryptosystem

Attack algorithms for the Discrete Logarithm problem

• Shanks’ algorithm
• Pohlig-Hellman algorithm
• Conditions under which the Discrete Logarithm problem is easily solved