2
$\begingroup$

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)$ ?

$\endgroup$
4
  • $\begingroup$ 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$? $\endgroup$
    – Raoul722
    Mar 6, 2016 at 21:46
  • $\begingroup$ yes all of them are $\endgroup$ Mar 7, 2016 at 14:38
  • $\begingroup$ So $gcd(p, q) = 1$ and you can directly recompute it modulo $n$ without considering $p_1$, $p_2$, $q_1$, $q_2$. $\endgroup$
    – Raoul722
    Mar 7, 2016 at 14:42
  • $\begingroup$ 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 $\endgroup$ Mar 7, 2016 at 14:55

1 Answer 1

3
$\begingroup$

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

Your question is:

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

$\endgroup$
2
  • $\begingroup$ 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$) $\endgroup$ Mar 7, 2016 at 14:44
  • $\begingroup$ 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. $\endgroup$ Mar 7, 2016 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.