Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Is it computationally infeasible to solve $x^a\equiv b \pmod p$ as that in discrete logarithm problem to solve $a^x\equiv b \pmod p$, where $p$ is a large prime and $a,b$ are both positive integer below $p-1$

share|improve this question
add comment

2 Answers

If $a$ is relatively prime to $p-1$, you can solve for $c$ from $ac\equiv 1$ (mod $p-1$) and raise both sides to the power $c$. You obtain $x\equiv x^{ca}\equiv b^c$ (since $x^{p-1}\equiv 1$) (mod $p$).

If $a$ is not relatively prime to $p-1$, the congruence is not always solvable. However, there should be a least $d$ for which $ac\equiv d$ (mod $p-1$) has a solution and raise both sides to the power $c$. Then one has the congruence $x^d\equiv b^c$ (mod $p-1$). In most cases this will be simpler than the original congruence. The congruence has no solution if $b$ is not a $d$-th power modulo $p$. It should be clear that $d$ will be a divisor of $p-1$ (since it can be computed as the gcd of $a$ and $p-1$) and that $b$ will be a $d$-th power if $b^{p-1/d}\equiv 1$ (mod $p-1$).

That is as far as I can help.

share|improve this answer
add comment

There are probabilistic algorithms to solve your equation with complexity polynomial in $\log p$. That means that you can solve such equations in practice. You can find the algorithms in any book on computational/algorithmic number theory. Funnily enough, there is no known deterministic such algorithm even for $a=2$.

share|improve this answer
    
For $a=2$ there's Schoof's algorithm. It's polynomial time. I had thought it was deterministic, but I may be misremembering. –  Joe Silverman Jan 29 '11 at 14:59
    
@Joe: as far as I know it is deterministic. –  GH from MO Jan 29 '11 at 15:18
4  
Schoof's algorithm is deterministic but requires an elliptic curve with CM by a field with discriminant $\pm b$ so the running time is proportional to $b$ (but polynomial in $\log p$) so is only really polynomial time for fixed $b$. –  Felipe Voloch Jan 29 '11 at 18:50
    
Being pedantic: proportional to $\sqrt{|b|}$, and polynomial time for $b=O(log^C(p))$, $C$ a constant. –  Dror Speiser Jan 29 '11 at 23:25
    
Also, note that if $a$ isn't fixed and grows with $p$, say, more than polynomially, this is an open problem. –  Dror Speiser Jan 29 '11 at 23:27
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.