Return to Answer

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 an $x$ solution to both DLP, and the only such one (formally, we do not even need to check that $0<x<\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, that's "better" than "solv(ing) the two discrete logarithms independently". This answers in the affirmative a possible reading of the question.

But we now 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 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 otherwise 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$.

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$.

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 an $x$ solution to both DLP, and the only such one (formally, we do not even need to check that $0<x<\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, that's "better" than "solv(ing) the two discrete logarithms independently". This answers in the affirmative a possible reading of the question.

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 otherwise 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=s^{-1}\,y_2\bmod p_2$ or something on that tune.

We now 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 harder, and right now I have no clue on that one.

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 an $x$ solution to both DLP, and the only such one (formally, we do not even need to check that $0<x<\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, that's "better" than "solv(ing) the two discrete logarithms independently". This answers in the affirmative a possible reading of the question.

But we now 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 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 otherwise 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$.

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)$, we can solve either of the two Discrete Logarithm Problems, and that will greatly help solving the other.

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 notation 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 $s$ must an $x$ solution to both DLP, and the only such one (formally, we do not even need to check that $0<x<\min(q_1, q_2)$ and ${g_2}^s\equiv y_2\pmod{p_2}$, even though in practice we would).

Note: this is not an indication that the additional information $0<x<\min(q_1, q_2)$ makes the problem easier than it is to solve both DLPs simultaneously (an alternate way of understanding the question as worded). I reserve my position on that one.

Note: even knowing that $0<x<\max(q_1,q_2)$ and solving one of the two DLP 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 otherwise we could reduce the search of $k$ to 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=s^{-1}\,y_2\bmod p_2$ or something on that tune.

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 an $x$ solution to both DLP, and the only such one (formally, we do not even need to check that $0<x<\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, that's "better" than "solv(ing) the two discrete logarithms independently". This answers in the affirmative a possible reading of the question.

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 otherwise 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=s^{-1}\,y_2\bmod p_2$ or something on that tune.

We now 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 harder, and right now I have no clue on that one.