Apply Chinese Remainder Theorem to solve Discrete Logarithm Problem

943 Views Asked by At

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

1

There are 1 best solutions below

0
On

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.