# Encryption/Decryption Modulo function

I have an encryption line of code as follows:

a^x mod y = rem // ^ is the power fx


Given x, y, amd rem during decryption, how can we find the value of a?

I was thinking of using xth root of rem mod y, but it's not working; probably because of modulo congruence.

Can someone please guide me as to what needs to be done?

• That looks like RSA. Search for ways to break RSA and you should also find a solution for your problem. Remember that you can rename your equation to better understand other solutions: m^e mod N = c – Nova Apr 14 '18 at 1:40
• Is $y$ prime? If so, then the solution is easy, much easier than factoring. – Ella Rose Apr 14 '18 at 13:51
• @EllaRose no unfortunately y is not a prime. But now I am curious at to how it can be simplified in case y is prime. Can you please guide me in the right direction? – Adnan Apr 15 '18 at 8:49
• If $y$ was prime and $x$ was coprime to $y - 1$, then you could compute the inverse of $x$ modulo $y - 1$ to obtain an exponent $z$. $a^{xz} \equiv a^{1} \equiv a \bmod y$ – Ella Rose Apr 15 '18 at 16:17

You will have to find $d \in \mathbb{Z}_{\varphi(y)}: x * d \equiv 1 (mod\ \varphi(y))$. Then $rem^d=a^{xd}=a^1$ (Euler's theorem) in $\mathbb{Z}_{y}$. To do so you will need to calculate the prime decomposition of $y$ so you can calculate the value of Euler's phi ($\varphi$) in $y$. Then the problem of finding $d$ reduces to the problem of finding inverse (extended Euclidian algorithm on the power and the modulus -- find $a,b$ such that $1=GCD(x,\varphi(y))=ax+b\varphi(y)\equiv ax (mod\ \varphi(y))$). Note that the inverse does not exist if $GCD(x,\varphi(y))\neq1$.
E.g. in RSA the public key ($e$ that corresponds to your $x$) has an inverse ($d$) computed during the key generation and the inverse is then stored in the private key.
• One does not have to find $d\in\mathbb{Z}_{\varphi(y)}:x\cdot d\equiv1\pmod{\varphi(y)}$. What's (apparently) true is that we have to factor $y$. But 1) Another strategy exists, and is what's most used in practice: solving the equation modulo factors of $y$, then forming the final solution with the CRT. 2) The answer's method works for a larger choice of $d$ : those with $x\cdot d\equiv1\pmod{\lambda(y)}$, where $\lambda$ is the Charmichael function; that slightly simplifies. – fgrieu Apr 14 '18 at 7:38
• @boethius Amazingly explained. Thank you so much. It took a day to visit the concepts to understand it all, but finally I got it. The place I was getting stuck was once I found 'd' , I was simply calculating $rem^d$ instead of $rem^d( mod y)$. One concept I am not fully able to understand is why we are using $\varphi(y)$ instead of y in Extended Euclidian algo. I wanna understand how Euler's Totient helps us in all this. – Adnan Apr 15 '18 at 8:43
• @Adnan we are utilizing Euler's theorem ($a^{\varphi(y)}\equiv 1 (mod\ y)$ if $a,\,y \in \mathbb{N}$ and $GCD(a,y)=1$). That means we want the power to be multiple of $\varphi(y)$ plus one which is exactly why we are finding an inverse modulo $\varphi(y)$. – boethius Apr 16 '18 at 7:01