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?
$\begingroup$
$\endgroup$
6
-
3$\begingroup$ 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. $\endgroup$– marstatoDec 28, 2015 at 20:04
-
$\begingroup$ @marstato is there a way where i can simplify the problem to be able to compute it on a calculator. Thanks $\endgroup$– JamesDec 28, 2015 at 20:29
-
$\begingroup$ 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 $\endgroup$– marstatoDec 28, 2015 at 20:41
-
1$\begingroup$ @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. $\endgroup$– Maarten Bodewes ♦Dec 29, 2015 at 12:09
-
$\begingroup$ 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$. $\endgroup$– SEJPMDec 29, 2015 at 12:36
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
1
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$
answered Dec 28, 2015 at 22:41
-
$\begingroup$ 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}$$ $\endgroup$– fgrieu ♦Jun 28, 2017 at 18:22