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.

If $a$, $b$, and $c$ are known, is there an efficient way to find values of $x$ which satisfy $x^a\ \textrm{mod}\ b \geq c$ ?

share|improve this question
4  
What order are you using? Usually we don't think of an order on $\frac{\mathbb{Z}}{\mathbb{Z_p}}$ because of the circularity. –  Ross Millikan Apr 11 '11 at 16:52
    
@Ross: Since he is using the $\bmod$ operator, $x^a\bmod b$ is always the unique integer between $0$ and $b-1$ (or between $1$ and $b$) that is congruent to $x^a$ modulo $b$, rather than a congruence class. So you can compare $x^a\bmod b$ with an integer $c$ in the usual order. For example, we can ask if $3^5\bmod 7$ is greater than or equal to $4$ (it is, since $3^5\equiv 5\pmod{7}$, so $3^5\bmod 7 = 5$). –  Arturo Magidin Apr 11 '11 at 17:14
    
@Arturo: fair enough. –  Ross Millikan Apr 11 '11 at 17:18
1  
Note that $x$ might not exist, e.g., for $c\geq b$. Or it might be not unique... –  Fabian Apr 11 '11 at 17:33

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.