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$ ?
Find $x$ satisfying $x^a\ \textrm{mod}\ b \geq c$ where $a$, $b$, and $c$ are known
1
$\begingroup$
modular-arithmetic
-
4What order are you using? Usually we don't think of an order on $\frac{\mathbb{Z}}{\mathbb{Z_p}}$ because of the circularity. – 2011-04-11
-
0@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$). – 2011-04-11
-
0@Arturo: fair enough. – 2011-04-11
-
1Note that $x$ might not exist, e.g., for $c\geq b$. Or it might be not unique... – 2011-04-11