Solve $(kp)^{e} = (kp)\ mod\ (pq)$ where p, q are odd primes, $0 < k \le q$.

134 Views Asked by At

Is there a fast way to solve this modular equation without evaluating the equation for all possible values of k and e: $(kp)^{e} = (kp)\ mod\ (pq)$ where p, q are odd primes, $0 < k \le q$. We would like to determine the set of $e$'s for a given $k$. Note that $kp$ and $pq$ are not co-prime, if they were co-prime, then, this would just be the discrete-logarithm problem.

1

There are 1 best solutions below

0
On

Let $k = aq + b$ where $a = k / q$ and $b = k\ mod\ q$ , then $(apq + bp)^{e} = (apq + bp)\ mod\ (pq)$. This means we need to search for $k \in [1, q]$