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

1 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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