# Modular exponentiation on calculator for textbook RSA

How do you encrypt $51$ with public key $(n,e) = (91,23)$

I understand that $c = 51^{23} \bmod 91$. How can I calculate the result on a calculator?

• Standard calculators cannot do that because $15^{23}$ is too big for a calculator to store. Computers use special algorithms to combine the exponentiation and the modulus in one calcuation step thus avoiding having to calculate $m^e$. If you get hands on a scientific calcuator that allows custom programs to be written on it, you can implement such an algorithm. – marstato Dec 28 '15 at 20:04
• @marstato is there a way where i can simplify the problem to be able to compute it on a calculator. Thanks – James Dec 28 '15 at 20:29
• As said: there are algorithms. Google for mod pow operation. But you dont want to type these out on your small calculator. Use sth. like this: javascripter.net/math/calculators/100digitbigintcalculator.htm – marstato Dec 28 '15 at 20:41
• @otus It's still about cryptography though, and I think the question will pop up again if we close it anyways. There are currently three upvotes and three downvotes. I suggest we keep it as it is obviously disputed, and I think we should leave disputed questions be disputed but open. – Maarten Bodewes Dec 29 '15 at 12:09
• I've edited the question to change $(n,e)=(23,91)$ to $(n,e)=(91,23)$ as $n<e$ made no sense and $n\in\mathbb P$ also made no sense. I think this was intended by the OP as he used $c=51^{23}\bmod 91$ using $n=91$ and $e=23$. – SEJPM Dec 29 '15 at 12:36

If your calculator is able to compute $n^2$, you can compute $m^e \bmod n$ using the binary exponential method.

In this method, you should first compute the binary form of $e$. Let $\ell$ be the number of bits in $e$, and let $e_i$ denote the $i$-th bit of $e$, so that $e=\sum\limits_{i=0}^\ell e_i \cdot 2^i$.

Now, with the algorithm below, you can compute $c$:

$z:=1$
$\text{for } i:= \ell \text{ down to } 0 \text{ do:}$
$\quad z:=z^2 \bmod n$
$\quad \text{if } e_i = 1 \text{ then } z:=(z \cdot m) \bmod n$
$\text{end for}$
$\text{return } z$

• As described, except for $e=0$, and since $\ell$ is the number of bits in $e$, it holds that $e_\ell=0$, and $e_{\ell-1}=1$. The algorithm always performs one more loop than there are bits in $e$, and at the end of the second loop $z=m$ always holds. It follows the algorithm is best changed to\begin{align}&z:=m\\&\text{for } i:= \ell-2 \text{ down to } 0 \text{ do:}\\&\quad z:=z^2 \bmod n\\&\quad\text{if }e_i=1\text{ then }z:=(z\cdot m)\bmod n\\&\text{end for}\\&\text{return }z\end{align} – fgrieu Jun 28 '17 at 18:22