8
$\begingroup$

Finding a discrete log in a finite cyclic group, like $(Z_N)^x$, seems hard and in some cases a solution may not even exist. Consider $N=15$ and the generator function $2^k=m \bmod 15$. This will produce the following values for $m$ given any non negative integer $k$...

$1, 2, 4, 8, 1, \dots$

Therefor, the equation $2^k=3 \bmod 15$ would have no (real?) solution. Is there a "fast" way of determining if any solution exists without factoring N?

  • 0
    related: https://math.stackexchange.com/q/1301314/1632017-02-09

2 Answers 2

5

I don't know of a fast way to solve the decision version of discrete log but given the problem of deciding if a solution to $a^x=b \bmod n$ exists for known $a$,$b$ the following steps will often show that a solution does not exist:

(1) Factor the modulus into prime powers. By the Chinese remainder theorem a solution exists if it exists mod each prime power
(2) For each of these factor $p$-1
(3) Compute the order of $a$ and $b$ mod $p^k$ using the factorization of $p$-1 (can be done quickly using a generalization of Euler's criterion)
(4) A solution does not exist if the order of $b$ does not divide the order of $a$.

Misc remarks:
(1) It is unknown if factoring $n$ reduces to being able to solve the decision discrete log mod $n$.
(2) Its not hard to show factoring $n$ reduces to the computational version of discrete log mod $n$ (discrete log can be used to compute the order of any element mod $n$ and there is a well known way to factor $n$ given this. It's described on the Wikipedia page for Shor's algorithm).
(3) Given the factors of $n$, discrete log mod $n$ reduces to discrete log mod $p$. It is unknown if a fast method for factoring any number would imply that the discrete log mod primes can also be solved quickly.

0

I am not sure if Chinese Remainder Theorem applies here. Note that $2^k = 7$ has no solution mod $15$, but has solutions mod $3$ and $5$.