I am trying to solve an RSA problem. In order to calculate $d$, I have to calculate $d$ with $e=3$ and $$d\cdot e\equiv1 \pmod{40}$$ Obviously the answer is $d=27$, but I want to solve this with the extended Euclidean algorithm.
Though I know how this works, I am stuck because in the first step of the algorithm I get $$40=3\cdot13+1$$

The remainder is 1 and the algorithm stops there. How do I get $d=27$ by using the extended Euclidean algorithm?

I dont have a problem solving other similar examples that dont stop in the first step. But here, because it stops in the first step of the algorithm, I get confused.

  • 5
    $\begingroup$ Possible duplicate of Calculating RSA private exponent when given public exponent and the modulus factors using extended euclid. If the answer doesn't satisfy you, les us know. $\endgroup$
    – kelalaka
    Mar 11 '19 at 11:12
  • $\begingroup$ From $40=3\cdot13+1$ you know $e\cdot13+1\equiv0\pmod{40}$. That is $e\cdot13\equiv-1\pmod{40}$. How do you get from that to a value of $d$ with $d\cdot e\equiv1\pmod{40}$? This is fine for manual computation, but notice that a proper Extended Euclidean Algorithm, like HAC algorithm 2.107, or the Half-Extended variant there specifically intended for computation of modular inverses, won't leave you without a solution. $\endgroup$
    – fgrieu
    Mar 11 '19 at 12:07

First, 40 = 3*13 + 1

So, we have found 1 in the first step. Then I can write 1 as following:

1 = 40 - 3*13 and this is equivalent to

1 = 40 - 13*3. 40 is equivalent to 0 mod40.

1 = -13*3. Here we get the inverse of 3 as -13 which is equivalent to 27.


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