2
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – Yuval Filmus Feb 28 '17 at 22:23
  • $\begingroup$ $M_n=2^n-1$ is Mersenne number all are reduced with respect to $mod M_{n}$ $\endgroup$ – Ramez Hindi Feb 28 '17 at 22:37
  • $\begingroup$ So $a_n = a_{n-1}^2-2 \bmod{2^n-1}$? $\endgroup$ – Yuval Filmus Feb 28 '17 at 22:39
  • $\begingroup$ yes Yuval Filmus $\endgroup$ – Ramez Hindi Mar 1 '17 at 7:13
  • 1
    $\begingroup$ You still haven't explained what is "complexity time". $\endgroup$ – Yuval Filmus Mar 1 '17 at 13:33
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.