about the complexity of recursive sequence
I calculated the first few values of your sequence:
$$
4,2,2,2,2,2,2,2,2,\ldots
$$
Indeed, $a_2 = 4^2-2 \bmod{2^2-1} = 14 \bmod{3} = 2$, and henceforward we have $a_{n-1}^2-2 = 2^2-2 = 2$ and so $a_n = 2$.