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.
I wonder if there exist $x$ and $y$ such that $x-y,x^2-y,x^3-y,\dots$ are all prime. It seems unlikely, but I don't see how to prove it can't happen. If there are infinitely many such $x$ and $y$, then the kind of bound you want won't exist.
EDIT: If $\gcd(x,y)=1$, $|x|\ge2$, and $x-y=p$ is prime, then $x^p-y$ is a multiple of $p$, so not a prime. But that doesn't give the kind of bound you're after.