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

Improve this question
$\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$ Commented 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$ Commented Feb 28, 2017 at 22:37
  • $\begingroup$ So $a_n = a_{n-1}^2-2 \bmod{2^n-1}$? $\endgroup$ Commented Feb 28, 2017 at 22:39
  • $\begingroup$ yes Yuval Filmus $\endgroup$ Commented Mar 1, 2017 at 7:13
  • 1
    $\begingroup$ You still haven't explained what is "complexity time". $\endgroup$ Commented Mar 1, 2017 at 13:33

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
0

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.