# 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$? – Raoul722 Mar 6 '16 at 21:46
• yes all of them are – David 天宇 Wong Mar 7 '16 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$. – Raoul722 Mar 7 '16 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 – David 天宇 Wong Mar 7 '16 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$) – David 天宇 Wong Mar 7 '16 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. – David 天宇 Wong Mar 7 '16 at 14:53