?

Abstract Algebra

Free Version

Upgrade subject to access all content

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