# Cycling Attack Proof by Induction

This is not a hard question, but I am stuck trying to prove the following by induction: Let \begin{align}C_1&\equiv C^e\pmod n\text{ and}\\ C_{j+1}&\equiv C_j^e\pmod n\end{align} for all $j\in\mathbb{N}$, with $0 < C_1 < n$ and $(e,\phi(n))=1$.

Show that $C_j\equiv C^{e^j}\pmod n$, with $0 < C_j < n$.

This is what I have tried:

Base:

$$C_1\equiv C^{e^1}\pmod n.$$

($j=1$):

$$C_2\equiv C_1^e\equiv(C^e)^e\equiv C^{e^2}\pmod n.$$

Hence the base case is met.

Step:

$$C_{k+1}\equiv C_k^e\pmod n.$$

($j=k+1$):

$$C_{k+2}\equiv C_{k+1}^e\equiv(C_k^e)^e\equiv C_k^{e^2}\pmod n.$$

I get stuck here, however; I do not know how to proceed. How can I finish this proof?

-

Step:

$$C_{k}\equiv C^{e^k}\pmod n.$$

$$C_{k+1}\equiv C_{k}^e\equiv(C^{e^k})^e\equiv C^{e^{k+1}}\pmod n.$$

-
So, in the induction step, do I have to assume what I am trying to prove? – EsX_Raptor Apr 16 '12 at 13:53
You have to assume it for k and prove it for k+1 – Wonder Apr 16 '12 at 13:57