Difficult# Public-key Cryptography: Decoding

ABSALG-E13WZL

You ask a friend, who we call *Encoder*, to think of a number $w$ between 1 and 52, that she keeps secret.

You then ask *Encoder* to raise the number $w$ to the power $13$ on her calculator and to give you the number $w^{13}$ explicitly.

You now act as *Decoder*, in that you wish to: **compute the number $w$ Encoder chose from the number $w^{13}$ she gave you.**

You also must achieve this using a **single computation of the form (SC)**: $$x^{y_0}\; {\textrm mod}\; 77 \qquad (SC)$$...where $x$ and $y_0$ are **positive integers** and $y_0\not=13$.

In particular, the computation $w=\left({w^{13}}\right)^{1/13}$ on your calculator is **strictly forbidden**. As $y_0\not=13$, you are also **not allowed** to use a calculator to compute $x^{13}$ **repeatedly** so as to generate the list of numbers $1^{13}$, $2^{13}$, $3^{13}$,$\ldots$ until the calculator hits on the number $w^{13}$ given to you.

Suppose *Encoder* tells you that, $\qquad w^{13}=1220703125$

**Without** using a calculator, and by using the **true facts**:

$1220703125\equiv 26$ mod $77$, $\quad (26)^5\equiv 45$ mod $77$, $\quad(45)^7\equiv 45$ mod $77$, $\quad 45\times 26\times 26\equiv 5$ mod $77$

...answer the following.

**The answers are numbers**