# Reverse modular exponentiation : finding the base given the exponenent, the modulus semi‑prime and the result…

Simple question, Given c=$$b$$$$e$$ mod $$m$$, we all know finding $$e$$‎ is equivalent to solving the discrete logarithm.
But what about finding $$b$$ from c ; $$e$$ and the semi‑prime $$m$$ ? Is it something harder than factoring $$m$$ too ?

If yes as this is different from the ʀꜱᴀ problem, how to compute $$b$$ when $$e$$ is more than 128‑bits long (so not small) ? Is the possibility to set c to arbitrary values while changing prime $$e$$ is making things easier to get at least 1 example where $$b$$ is found ?

• Mar 19 at 14:26
• @kelalaka the exponent in my case if far larger than anything used for ʀꜱᴀ and there’s to be no special cases : $c$ can be arbitrary values and $e$ too if it’s a large prime. Mar 19 at 15:46
• The only requirement for RSA's $e$ is $\textrm{gcd}(e,\lambda(m))=1$ so that the inverse exists and is unique. Choosing $e$ small is preferred to reduce the costs. Mar 19 at 16:50
• @kelalaka in my case, e is a random 256‒bits prime that can only be predicted, so it can’t be small. Does this makes things simpler that $gcd(e,λ(m))≥1$ which means several solutions exists ? Mar 19 at 17:06

This is equivalent to finding the RSA plaintext $$b$$ given the public key $$(m,e)$$. Usually called The RSA Problem. It is no harder than factoring $$m$$. There is however no evidence that it is easier than factoring.
Edit: As @DanielS points out I was a bit sloppy. For the mapping to be one-to-one, i.e., for the encryption to be reversible, we require $$\textrm{gcd}(e,\lambda(m))=1$$ and the term RSA problem denotes this case.
• Slight quibble: it's the RSA problem when $(e,\lambda(m))=1$. Although not quite well-defined in the case $(e,\lambda(m))>1$, it is equivalent to factoring in such cases (at least in a PPT-sense for small $(p-1,q-1)$, though other results may be out there). Mar 19 at 12:40
• @DanielS I don’t have this in the case of the ʀꜱᴀ problem but in the case of the adaptive root problem where the random exponent can be predicted… So does the fact e c can be arbitrary values don’t change anything ? The only requirement, I have if for e to be a large prime. What’s $λ(m)$ ? In my case, I’m almost sure (e,λ(m)) will be greater than 1. Mar 19 at 15:44
• @user2284570: $λ$ is the Carmichael function. If $m=p\,q$ with $p$ and $q$ distinct primes, then $λ(n)=\operatorname{lcm}(p-1,q-1)$, and $b=c^{(e^{-1}\bmodλ(n))}\bmod m$. In python (3.8 or better): b=pow(c,pow(e,-1,math.lcm(p-1,q-1)),m). Or b=pow(c,pow(e,-1,m-p-q+1),m). Update: that's for $\gcd(e,\lambda(m))=1$. For $\gcd(e,\lambda(m))>1$ there might be several, or no solution.
• @fgrieu-modelectiontime so this requires to factorize $m$? Mar 19 at 16:39