# about the complexity of recursive sequence

If i have a recursive sequence $a_1=4$ and $a_{n}=a_{n-1}^{2}-2$ in $\mathbb{Z}_{M_{n}}$ where $M_n=2^n-1$

how i can calculate the complexity time of this sequence ? if we put it in the loop for n-1 iteration .

pseudocode :

S=4; i=2;

While($i<n$,

$S=S^2-2 (\mod M_n)$

If( S==0 then Break[]);

);

im not sure that overall complexity is $O(log^3(M_n))$

• What do you mean by "the complexity time" of this sequence? Also, what do you mean by $\mathbb{Z}_{M_n}$? Are you computing each $a_n$ with respect to a different modulus? – Yuval Filmus Feb 28 '17 at 22:23
• $M_n=2^n-1$ is Mersenne number all are reduced with respect to $mod M_{n}$ – Ramez Hindi Feb 28 '17 at 22:37
• So $a_n = a_{n-1}^2-2 \bmod{2^n-1}$? – Yuval Filmus Feb 28 '17 at 22:39
• yes Yuval Filmus – Ramez Hindi Mar 1 '17 at 7:13
• You still haven't explained what is "complexity time". – Yuval Filmus Mar 1 '17 at 13:33

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$.