Discrete Logarithm Problems Solved Easily Under Certain Conditions
Review 1
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
Security algorithms utilizing the difficulty of the Discrete Logarithm problem
Attack algorithms for the Discrete Logarithm problem
- Shanks’ algorithm
- Pohlig-Hellman algorithm
- Conditions under which the Discrete Logarithm problem is easily solved
Hoffstein. (2008). An Introduction to Mathematical Cryptography: p84~92. ↩︎