challenges

Successive Powers

The following integers: $\{588,665,216,113,642,4,836,114,851,492,819,237\}$ are successive large powers of an integer $x$, modulo a three digit prime $p$.

Find $p$ and $x$ to obtain the flag.

This means that we have a system of equations like:

$$\{\begin{array}{l}588\equiv x^1\mathrm{mod}p\\ 665\equiv x^2\mathrm{mod}p\\ 216\equiv x^3\mathrm{mod}p\\ ...\\ 237\equiv x^{12}\mathrm{mod}p\end{array}$$

We can restructure the system of equations like:

$$\{\begin{array}{ll}588& \equiv x\mathrm{mod}p\\ 588x& \equiv 665\mathrm{mod}p\\ 665x& \equiv 216\mathrm{mod}p\\ ...& \end{array}$$

So getting the second one means finding a $x$:

$$588^2=665+kp⟹p=\frac{588^2-665}{k}$$

$665+k_{2}p=(558+k_{1}p{)}^2$

$665+p-588^2-588p-p^2=0⟹p^2-587p+(588^2-665)$