Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 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.

share|improve this answer
1  
I guess you're not interested in cases where $x=0$, $1$ or $-1$... –  Robert Israel Jun 1 '11 at 1:45
    
@Robert, not really, but of course I should have dotted those "i"s and crossed those "t"s. –  Gerry Myerson Jun 1 '11 at 1:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.