# How to calculate base value in modular exponentiation

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

• For your practical application of this (?) How large are n and the range? Is n usually a prime? – SEJPM Nov 17 '19 at 6:21
• Hmm... If you know that "a lies in between 1900 and 2000" you can simply try all these values, can't you? – 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)$$.
• It's not given that $n = pq$, though... – fkraiem Dec 17 '19 at 12:16
• @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. – fgrieu Dec 17 '19 at 16:38