[fabianmedina]

Hola, necesito ayuda con la complejidad de estos algoritmos

Con base en el algoritmo de [Cor 2009], para calcular \( a^b \) \(  mod \) \(   n \) donde \( a, b \)  y \(   n \) son enteros positivos:

Código: [Seleccionar]

ModExpo (a,b,n)

1  x=a
2  y=b
3  z=1
     // Inv: 0<=y && z*x^y==a^b mod n

4  while y!=0
5      if y==0 mod 2
6              then y=y/2
7                      x=x*x mod n
8              else  y=y-1
9                      z=z*x mod n
10 return z
1) ¿Cuál es la Complejidad de este algoritmo?

2) Escribe un algoritmo donde "a" es una matriz cuadrada (Matrix_ModExp (Matriz a, int b, int c)) y calcule la complejidad de este algoritmo

3) Cómo se puede usar la exponenciación modular de Matrix para calcular la secesión de Fibonacci cuando:

\( F_0=0 \)
\( F_1=1 \)
\( F_{n+2}=F_n+F_{n+1}\qquad , n\geq 0 \)

\( \begin{pmatrix} F_{n+1}\\F_n\\\end{pmatrix}=
\begin{pmatrix}1 &1 \\ 1& 0\\\end{pmatrix}
\begin{pmatrix} F_{n}\\F_{n-1}\\\end{pmatrix} \)

Gracias por cualquier ayuda,

Saludos