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

Improve this question
$\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
    Commented Mar 6, 2016 at 21:46
  • $\begingroup$ yes all of them are $\endgroup$
    – David 天宇 Wong
    Commented 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
    Commented 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$
    – David 天宇 Wong
    Commented Mar 7, 2016 at 14:55

1 Answer 1

Reset to default
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$.

Improve this answer
$\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$
    – David 天宇 Wong
    Commented 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$
    – David 天宇 Wong
    Commented 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.