# Extended Euclidean Algorithm (back substitution)

I have found from the values of P (11) and Q(7) that n=77, (p-1)(q-1)=60 and that e=43 as it is relatively prime with 60.

However, I believe the value I got for d (7) is wrong. Here is my workings out:

60x + 43y = 1

60=1(43)+17
43=2(17)+9
17=1(9)+8
9=1(8)+1

Then:

1=9 - 1(8)
1=9 - 1(17 - 1[9])
1=1(9) - 1(17) + 1(1[9])
1=1(9) + 1(1[9]) - 1(17)
1=2(9) - 1(17)

1=2(43 - 2[17]) - 1(17)
1=2(43) - 4(17) - 1(17)
1=2(43) - 5(17)

1=2(43) - 5(60 - 1[43])
1=2(43) - 5(60) + 5(1[43])
1=7(43) - 5(60)

therefore d=7, right? It seems to not work in practice and I can't figure out why :(

The issue is when I apply these values into these formulas:

$$C = M^e \bmod n$$ $$M = C^d \bmod n$$

For example, when I make M=2 (for B) the result is C = 53.0009765625... But using the formula to decrypt it doesn't return back to the original value

I would really appreciate any advice and apologies if I have worded it badly.

• I'm voting to close this question as off-topic because it's about math with no immediate connection to cryptography. So it is more suitable for one of the math stackexchanges. – Ella Rose Sep 6 '18 at 17:18
• For $M = 2$ we have $C = 2^{43} \bmod{77} = 30$. Therefore $M = 30^7 \bmod{77} = 2$. So your $N, e, d$ are correct. If $C$ is coming back as a float you're doing modular exponentiation wrong. – puzzlepalace Sep 6 '18 at 19:31

$d=7$ is correct; this can easily be verified by computing:
$$43 \times 7 \bmod 60 = 301 \bmod 60 = 1$$