How to determine the exponent when using RSA Can someone please explain to me how, when using RSA, to determine the exponent to be used in encryption and decryption? I have attempted a worked example on using RSA (shown below) but I can't ever get the decryption algorithm to work.

Worked example:

$p  = 29$

$q  = 37$

$n  = 29*37
 = 1073$

$\phi  = (29-1)(37-1)
     = 1008$

$e = 3$

$d  = (2(1008))+1)/3
 = 672.3333333$

$m  = 121512$ (taking the positions in the alphabet for 'L', 'O' and 'L')

Encrypt:  $ c = 121512^3 \mod 1073 = 878$

Decrypt: $ 878^{672.3333333} \mod 1073 = 352.91536313837299042255202310536$
There are three main errors here:


Exponent $e$ must be chosen to be coprime with  $\phi$. In your question, exponent $e = 3$ is not coprime with $\phi = 1008$. You can choose $e = 5$ instead.
You must use integer arithmetic, not floating-point. In other words, you cannot have values expressed with decimals.
You cannot encrypt a message bigger than the modulo (in this case, $n = 1073$). 


Taking these aspects into account, the remaining steps are as follows. The private key $d$ must be computed so $e \cdot d = 1 \mod \phi$. Using this online tool, we find the private key $d = 605$. Next, we cannot encipher message 121512 since is bigger than the modulo, but we can encipher the first three digits, so $m_1 = 121$. Hence, the other half of the message is $m_2 = 512$. The encryption of $m_1$ is $c_1 = (m_1)^{e} \mod n = 121^{5} \mod 1073 = 25937424601 \mod 1073 = 544$.

You can figure out the rest.