The decision version of the discrete log problem in $\mathbb{Z} /q \mathbb{Z}$ is to determine whether there exists a k so that $x^k$=y mod q.
Let gcd(x,y)=1. I am interested in an upper bound for the smallest odd prime q not dividing x or y so that $x^k=y$ mod q has a solution for some k.
Let w=max(x,y). Based on calculations I would guess the bound to be O$(log^i w)$ for some i>1.
i=1 is too small: x or y can be a product of consecutive primes starting from 2 and it is known that the product over the primes < ln(w) is O(w) so q must be larger than O(ln(w)).
Note that if q|y-1 then a solution is guaranteed, so a trivial bound is for q to be the smallest odd factor of y-1.