I was reading an answer about an attack on a weak group for the discrete logarithm problem and wanted to formalize and verify that the attack was correct. That is, that it was guaranteed to always find $x$ (and quickly) given $g$, $h$, and $p$ for $h \equiv g^x \pmod p$. Please read the answer here. In the process I think I found a mistake on the author's part, but figured out how to quickly solve the problem anyway. A number of other questions came up in the process that I'll ask below.
- I'll start by proving the first assumption of the attack. How do we know $\forall i: \exists x_i: g^{x_i} \equiv h \pmod {a_i}$?
We know $a_i | p$. Let $b_i = p / a_i$. We also know $g^{x} = py + h$ for some $y \in \mathbb N$. This implies $g^{x} = a_i \cdot b_i \cdot y + h$, so $g^x \equiv a_i \cdot b_i \cdot y + h\equiv h \pmod {a_i}$. Thus, $x$ satisfies $x_i$ in the equation above, so $\forall i$ there is at least one solution and $x \equiv x_i \pmod {a_i}$.
- How do we most efficiently compute the $x_i$?
It seems like according to these records listed on Wikipedia that a number field sieve algorithm will be the fastest since these are fields of form $(\mathbb Z / p \mathbb Z)^\times$, $p$ prime, and that's what the records are for. On the other hand, it must be faster, even for the best implementation of this algorithm to simply do trial multiplication until $p$ is at least so large.
- How do we know that $\exists x': \forall i: x' \equiv x_i \pmod {\phi(a_i)}$?
Now, the author suggests using the Chinese Remainder Theorem (CRT), but because the $\phi(a_i)$ are not pairwise coprime (in particular, $2$ is a divisor for each $\phi(a_i)$), this doesn't follow. This really threw me off because for a while I was trying to prove that such an $x'$ existed, and was trying to understand how the group order of each cyclic subgroup was relevant to finding $x$.
If you think can explain where the author may have been going, please let me know.
What we're actually looking for is a $x'$ such that $x' \equiv x_i \pmod {a_i}$ holds $\forall i$. By the CRT we know that such a $x'$ exists, and is unique (up its residue modulo $p$). Thus we know $x' \equiv x \pmod p$.
Now we just need to efficiently compute $x'$.
- How do we efficiently compute $x$ that satisfies the $x \equiv x_i \pmod {a_i}$ equivalences?
Again, reading from Wikipedia it lists solving the equivalences for the first two moduli using the extended Euclidean algorithm and Bézout's identity, followed by extending the solution to all equations as the fastest way to solve this. Will any optimized algorithm, in general or in particular, such as a number field sieve or the Pollard rho method work faster than the two steps listed above? That is when the group is "weak" (or when it is "weak" in this particular way being a composite of many small primes) is there such an algorithm that will always work faster and implicitly take advantages of the weaknesses?
- Am I missing any important ideas? Is there a more illuminating way to explain anything I did above?