Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have just read a very basic introduction to the RSA algorithm.

Let's suppose my two prime numbers are $p=29$ and $q=37$. Then $n=pq=1073$ and $e=5$. $n$ and $e$ are public.

If I want to send the letter U, which is n°21 in the alphabet, I would send $21^e$ (mod $1073$) that is $263$.

Normally I should calculate $(21^e)^d$, where $d=605$. But why not calculate $(263)^{1/5}$ ?

share|cite|improve this question
Computing roots under modulo is a VERY HARD task. – Gautam Shenoy Nov 14 '12 at 16:01
The problem is that calculating $(263)^{1/5}$ is hard, when working modulo an $n$ with unknown prime factors. How would you calculate this $5$th root? – TMM Nov 14 '12 at 16:02
up vote 1 down vote accepted

Because modular exponentiation is easy. How would you calculate $263^{1/5}?$ If you could, the encryption would not be secure.

share|cite|improve this answer
Thanks to all of you. Is it hard or impossible ? – Tom Nov 14 '12 at 16:50
@Tom: For this case, you can just try all the numbers from $1$ to $1072$ and see which works. If there were a general answer, that would break RSA. – Ross Millikan Nov 14 '12 at 16:58
Thank you very much ! – Tom Nov 14 '12 at 18:48

You already calculated $ d= 605 \equiv 5^{-1} \equiv 1 / 5 \pmod{ \phi(n)} $ .

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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