1
$\begingroup$

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$ ?

  • 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.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
  • 1
    Note that $x$ might not exist, e.g., for $c\geq b$. Or it might be not unique...2011-04-11

0 Answers 0