2
$\begingroup$

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.

1 Answers 1

2

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.

  • 0
    @Robert, not really, but of course I should have dotted those "i"s and crossed those "t"s.2011-06-01