Hola. Escribo el problema y comento:
Sea f(n) el número de bits del n-ésimo número de Fibonacci.
1. Estimar f(n) usando la notación O. Encontrar una función simple que sea asintóticamente igual a f(n).
2. Estimar el tiempo necesario para obtener la suma de los n primeros números de Fibonacci.
Este ejercicio forma parte de la asignatura de criptografía. El principal problema que tengo es que no poseo una base sólida sobre complejidad y tampoco tengo ejercicios resueltos sobre complejidad aritmética con enteros. Además he buscado en internet pero no hallo lo que necesito ya que lo que me encuentro son escuetas introducciones que se quedan en la teoría y no hacen ni un solo ejemplo. Con esto quiero decir que no puedo presentar una duda porque el problema en sí para mi es una duda. Pensé en hacer el primer apartado utilizando la fórmula explícita para el termino n-ésimo de la sucesión de Fibonacci pero tiene términos con raíces (no enteros) y por lo que hemos tratado en clase lo debemos resolver mediante complejidad aritmética con enteros. Lo que requiero es que me den alguna indicación para poder ponerme a trabajar en el problema y lo más importante, necesitaría que me recomendaran alguna referencia donde haya ejercicios resueltos sobre complejidad aritmética con enteros y complejidad aritmética en cuerpos finitos, que es otro tema que estamos dando. Gracias por su atención.
Perdón acabo de ver que hay una sección de criptografía en el foro, este tema debería ir a esa sección pero no se como puedo trasladarlo yo, ni siquiera se si puedo. Mis disculpas.
