I'm having a hard time creating a functioning RSA algorithm for some reason even though I have all the steps right (or at least I think I do). So I have the following :

I picked prime numbers, p and q as :

p = 13691 q = 29387

I picked n as p*q n 402337417

So phi(n) 402294340

I picked a random e between 1 and phi(n) e 46117

My message was M=3

I got d by the Extended Euclidean Algorithm as the following: d= 7795

When I do the encryption using M^e mod n I get: c= 399797630

When I do the decryption using C^d mod n , I get 243069037, which is not M = 3?

Any idea what can be the reason behind this? my guess that d is incorrect

I'm having a hard time creating a functioning RSA algorithm for some reason even though I have all the steps right (or at least I think I do). So I have the following :

I picked prime numbers, $p$ and $q$ as:

$$p = 13691$$ $$q = 29387$$

I picked $n$ as $p \cdot q$ $$n = 402337417$$

So $$\phi(n) = 402294340$$

I picked a random $e$ between $1$ and $\phi(n)$ $e = 46117$

My message was $M=3$

I got $d$ by the Extended Euclidean Algorithm as the following: $d= 7795$

When I do the encryption using $M^e \,\text{mod}\, n$ I get: $c= 399797630$

When I do the decryption using $C^d \,\text{mod}\, n$, I get $243069037$, which is not $M = 3$?

Any idea what can be the reason behind this? My guess is that $d$ is incorrect.

I'm having a hard time creating a functioning RSA algorithm for some reason even though I have all the steps right (or at least I think I do). So I have the following :

I picked prime numbers, p and q as :

p = 13691 q = 29387

I picked n as p*q n 402337417

So phi(n) 402294340

I picked a random e between 1 and phi(n) e 46117

My message was M=3

I got d by the Extended Euclidean Algorithm as the following: d= 7795

When I do the encryption using M^e mod n I get: c= 399797630

When I do the decryption using C^d mod n , I get 243069037, which is not M = 3?

Any idea what can be the reason behind this?

I'm having a hard time creating a functioning RSA algorithm for some reason even though I have all the steps right (or at least I think I do). So I have the following :

I picked prime numbers, p and q as :

p = 13691 q = 29387

I picked n as p*q n 402337417

So phi(n) 402294340

I picked a random e between 1 and phi(n) e 46117

My message was M=3

I got d by the Extended Euclidean Algorithm as the following: d= 7795

When I do the encryption using M^e mod n I get: c= 399797630

When I do the decryption using C^d mod n , I get 243069037, which is not M = 3?

Any idea what can be the reason behind this? my guess that d is incorrect