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?

  • 2
    $\begingroup$ 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 $\endgroup$ – Nova Apr 14 '18 at 1:40
  • $\begingroup$ Is $y$ prime? If so, then the solution is easy, much easier than factoring. $\endgroup$ – Ella Rose Apr 14 '18 at 13:51
  • $\begingroup$ @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? $\endgroup$ – Adnan Apr 15 '18 at 8:49
  • $\begingroup$ 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$ $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – fgrieu Apr 14 '18 at 7:38
  • $\begingroup$ @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. $\endgroup$ – Adnan Apr 15 '18 at 8:43
  • $\begingroup$ @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)$. $\endgroup$ – boethius Apr 16 '18 at 7:01

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.