If you have $a^b \bmod n = c$, and $b,n,$ and $c$ values are given, is it possible to find a value for $a$ within a given range?

So is it possible to find $a$ in $a^{2051} \bmod 3149=636$ knowing a lies in between $1900$ and $2000$?

  • $\begingroup$ For your practical application of this (?) How large are n and the range? Is n usually a prime? $\endgroup$ – SEJPM Nov 17 '19 at 6:21
  • $\begingroup$ Hmm... If you know that "a lies in between 1900 and 2000" you can simply try all these values, can't you? $\endgroup$ – tum_ Nov 17 '19 at 9:12

Hint: consider that as the problem of deciphering $c$ in textbook RSA encryption with public key $(n,b)$.

| improve this answer | |
  • $\begingroup$ It's not given that $n = pq$, though... $\endgroup$ – fkraiem Dec 17 '19 at 12:16
  • $\begingroup$ @fkraiem: yes. But one step of Fermat factors $n=3149$. Compute $r=\lceil\sqrt n\,\rceil=57$, $p=57-\sqrt{r^2-n}=47$, $q=2r-p=67$. I'd rather do this than try $a$ blindly. Of course I got that you where joking, me too. $\endgroup$ – fgrieu Dec 17 '19 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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