# How to compute the discrete logarithm of Diffie-Hellman with a composite modulus?

Imagine $n = pq$ with $p-1 = 2 p_1 p_2$ and $q-1 = 2 q_1 q_2$.

I can compute the discrete logarithm of $y = g^x \pmod{n}$ by computing the discrete logarithm of $y$ modulo $p$ and $q$. But then how to recompute it?

What I'm doing right now is recomputing it in $2p_1p_2q_1q_2 = \frac{(p-1)(q-1)}{2}$ with CRT (they all happen to be co-prime). But we're still not modulo $(p-1)(q-1)$ (it lacks the last 2). I usually have a solution though, and I can get the other solution by adding $(p-1)(q-1)/2$ to it.

I figured out I should find the $x$, but I find two other solutions. I can't seem to understand why, shouldn't I find the exact $x$ this way?

Also here I'm lucky, most primes (except one of the $2$) were co-prime. What about when $lcm(p-1, q-1)$ is way smaller than $(p-1)(q-1)$ ?

• You should specify more precisely how your variables are defined. Are $p$ and $q$ prime numbers? Same remark for $p_1$, $p_2$, $q_1$ and $q_2$? Commented Mar 6, 2016 at 21:46
• yes all of them are Commented Mar 7, 2016 at 14:38
• So $gcd(p, q) = 1$ and you can directly recompute it modulo $n$ without considering $p_1$, $p_2$, $q_1$, $q_2$. Commented Mar 7, 2016 at 14:42
• the $g^x$ mod $p$ and $q$ have solutions in $p-1$ and $q-1$, so I cannot recompute it in $pq$, rather $(p-1)(q-1)$ which is the order of $\mathbb{Z}^\ast_n$. It is the discrete log that I'm trying to recompute, not $y = g^x$ that I already know Commented Mar 7, 2016 at 14:55

I think the problem is that you are trying to recompute the result in $(p-1)(q-1)$ instead of $n$ and that is why you don't find the exact $x$.

I can compute the discrete logarithm of $y=g^x \mod n$ by computing the discrete logarithm of $y$ modulo $p$ and $q$. But then how to recompute it?

As I understand, you want to find the discrete logarithm of $y$ modulo $n$, not modulo $(p-1)(q-1)$.

Let be $x_p$ the discrete logarithm modulo $p$ and $x_q$ the discrete logarithm modulo $q$. So to recompute the result we have to solve the system $\left\{ \begin{array}{l} x \equiv x_p \mod p \\ x \equiv x_q \mod q \end{array} \right.$

If $gcd(p,q) = 1$ then you can apply the chinese remainder theorem by using the Gauss algorithm (check also the Garner algorithm which is more efficient) without having to consider $p_1$, $p_2$, $q_1$, $q_2$ and you will find a unique solution.

What about when $lcm(p−1,q−1)$ is way smaller than $(p−1)(q−1)$?

If $gcd(p,q) \not = 1$ but $gcd(p,q) \text{ | } x_p - x_q$ the system can still be solved but there exist several solutions.

Otherwise, you will not be able to recompute the solutions modulo $p$ and $q$ into the modulo $n$.

• the discrete logarithms are modulo $p-1$ and $q-1$ in the multiplicative groups $\mathbb{Z}^\ast_p$ and $\mathbb{Z}^\ast_q$. So I guess no Garner. I know that there exists different solutions, from my calculations I reduced the solutions to two, and they still are different than the real solution. But I guess this is because I'm trying to do the CRT in a different group (not mod $pq$) Commented Mar 7, 2016 at 14:44
• Also I didn't know that Garner algorithm! Seems way faster than the CRT algorithm, but then it is so fast anyway that it doesn't really matter in my case. Commented Mar 7, 2016 at 14:53