Simultaneous Discrete Logarithm with Small Exponent

Question

Given two distinct safe primes $p_1 = 2 \cdot q_1 + 1$, $p_2 = 2 \cdot q_2 +1$, consider the following two instances of the discrete logarithm problem with the same unknown exponent $x$.

$$ g_1^x \equiv y_1 \mod p_1 $$ $$ g_2^x \equiv y_2 \mod p_2 $$ where the multiplicative orders of $g_1, g_2$ are $q_1, q_2$ respectively.

In general, we can solve the two discrete logarithms independently to find $(x \mod q_1)$ and $(x \mod q_2)$, then combine with the Chinese Remainder Theorem to get $(x \mod q_1 q_2)$.

Can we do better if we know that $x$ satisfies $ 0 < x < \min(q_1, q_2)$? Is there any approach faster than solving one of the discrete logarithms?

Answer 1

For $i\in\{1,2\}$ it is given prime $p_i$ with $q_i=(p_i-1)/2$ also prime, integer $g_i$ of multiplicative order $q_i$, and integer $y_i$ such that for some untold integer $x$ common to both $i$, it holds ${g_i}^x\equiv y_i\pmod{p_i}$.

With the additional information that $0<x<\min(q_1, q_2)$, if we can solve either of the two Discrete Logarithm Problems, then we can solve the other with a single modular reduction.

Proof: WLoG, say we solved for $x$ the DLP ${g_1}^x\equiv y_1\pmod{p_1}$ and a solution is $x=x_1$ (swap the indices if we solved the other DLP). Compute $s=x_1\bmod q_1$. It holds that all solutions to that DLP are of the form $x=k\,q_1+s$ with $k\in\Bbb Z$. And $x=s$ is the only solution to that first DLP with $0\le x<q_1$. Hence $s$ is the only possible solution to that first DLP matching the stronger condition $0<x<\min(q_1, q_2)$. Hence that $s$ must be a solution to both DLP, and the only such one (formally, we do not even need to check that $0<s<\min(q_1, q_2)$ and ${g_2}^s\equiv y_2\pmod{p_2}$, even though in practice we would).

Since we need to solve only one DLP, and anyone of the two possibly according to which we find easier, that's "better" than "solv(ing) the two discrete logarithms independently"; and that improvement is directly enabled by $0<x<\min(q_1, q_2)$. This answers in the affirmative a possible reading of the question.

But we are told that the question really asks: assuming $0<x<\min(q_1, q_2)$, is there an approach which solves the two DLPs simultaneously that is faster than solving either DLP? That's a much harder question, and right now I have no clue.

---

Note: even the weaker additional information $0<x<\max(q_1,q_2)$ and solving one of the two DLPs in isolation would greatly help towards solving both. When $p_1\ge p_2$, the $s$ computed as above would be the only possible $x$. And for $p_1<p_2$ we could reduce the search of $x$ to the search of $k$ in a DLP of the form $g^k\equiv y\pmod{p_2}$ with $0\le k<\lceil q_2/q_1\rceil$, making the search easier (by enumerating $k$ when $p_1$ and $p_2$ have about the same size, or Baby-Step/Giant-Step if they differ by a few dozen bits). $g$ and $y$ are easily computed as $g={g_2}^{q_1}\bmod p_2$ and $y={g_2}^{-s}\,y_2\bmod p_2$.