Apply Chinese Remainder Theorem to solve Discrete Logarithm Problem I have to find $\xi$ such that:
$$343857231343^\xi \underset{n}{\equiv} 146812954167 $$
with $n = 1022126907089$.
$n$ was chosen to ensure that $factor(n) = p * q$.
I have computed $\xi_1$ and $\xi_2$:
$$343857231343^{\xi_1} \underset{p}{\equiv} 146812954167 $$
$$343857231343^{\xi_2} \underset{q}{\equiv} 146812954167 $$
How can I apply the Chinese Remainder Theorem to find $\xi$ ?
 A: If you have found $\xi_1$ such that $g^{\xi_1} \equiv a \pmod p$, then you actually know that for any integer $k$, $g^{\xi_1 + k(p-1)} \equiv a \pmod p$, because $g^{p-1} \equiv 1 \pmod p$. Similarly, we have $g^{\xi_2 + l(q-1)} \equiv a \pmod q$ for any integer $l$.
Moreover, if $g$ is a primitive root modulo both $p$ and $q$, then these are all the possible solutions.
By one direction of the Chinese remainder theorem, we'll have the desired $g^{\xi} \equiv a \pmod n$ if and only if $g^{\xi} \equiv a \pmod p$ and $g^{\xi} \equiv b \pmod q$. To get there, we have to solve
$$
    \xi = \xi_1 + k(p-1) = \xi_2 + l(q-1)
$$
over the integers: equivalently, solve
$$
    \begin{cases}
         \xi \equiv \xi_1 \pmod{p-1} \\
         \xi \equiv \xi_2 \pmod{q-1}
    \end{cases}
$$
This is kind of the Chinese remainder theorem, and if we do this, we'll be done.
It's only kind of the Chinese remainder theorem, because $p-1$ and $q-1$ are not relatively prime (in particular, $p$ and $q$ are both odd primes, so $p-1$ and $q-1$ are both even). To apply the Chinese remainder theorem in its usual form, we can replace the second equation by the weaker condition
$$
    \xi \equiv \xi_2 \pmod m
$$
where $m = \frac{q-1}{\gcd(p-1,q-1)}$. (In this problem, $m = \frac{q-1}{2}$.)
The resulting system of modular equations is guaranteed to have a unique solution $\xi$ modulo $\lambda(n) = \operatorname{lcm}(p-1,q-1)$. Since the original equation also had a unique solution $\xi$ modulo $\lambda(n)$, this guarantees that we found the right answer in the end even though we relaxed one of the equations.
