3
$\begingroup$

Is it possible to efficiently solve the discrete log problem for $r$: $$ g^r\equiv v\pmod N $$ When the following constants are know: $$ N,\ g,\ v,\ \phi=(p-1)(q-1)\text{ s.t. }N=p\,q $$

$\endgroup$
1

1 Answer 1

5
$\begingroup$

As far as we know, no, there is no general method to efficiently solve the Discrete Logarithm Problem for composite $N$ even when $\phi(N)$ is given and $N$ is the product of two distinct primes†. Argument: make $p$ any large prime with $(p-1)/2$ prime such as this, $q=3$, $N\gets p\,q$, $\phi\gets2(p-1)$, $g=2$, and $v$ computed as $g^r\bmod N$ for $r$ a random integer the size of $(p-1)/2$. Ability to solve the DLP modulo $N$ implies ability to solve it modulo $p$, which is widely believed hard.

The best method we have goes:

  • First factor $N$, which is possible from $N$ and $\phi$, see e.g. this.
  • Reduce the original problem to two DLPs modulo $p$ and $q$ using the Chinese Remainder Theorem. For some rare values of $g$ and $v$ that may allow to conclude there can't be a solution, or exhibit solution(s).
  • Try to factor $p-1$ and $q-1$.
  • Apply the Pohlig-Hellman algorithm, which when $(p-1)/2$ and $(q-1)/2$ are not prime and have known factors will reduce each of the two DLPs to several simpler ones, that we perhaps can solve using the function field sieve, index calculus, Pollard's kangaroo or Pollard's rho.

† The question's equation $\phi=(p-1)(q-1)$ is equivalent to $p$ and $q$ being distinct primes when we restrict to strictly positive $p$ and $q$; see there.

$\endgroup$

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.