¿Cuál es el peor caso para el algoritmo euclidiano en $\mathbb Z[i]$ ?

Question

Como saben, el peor caso para el algoritmo euclidiano en $\mathbb Z$ son dos números consecutivos de Fibonacci. Como cualquier calculadora GCD en línea que muestre los pasos del algoritmo euclidiano demostrará, la computación $\gcd (F_n, F_{n + 1})$ resulta en una lista en orden descendente de los números de Fibonacci de $F_{n - 1}$ todo el camino hasta 0 (asumiendo $n$ es positivo para empezar, algunas de las calculadoras en línea se niegan a hacer nada con números negativos como $-89$ o $-144$ ).

¿Cuál es el peor caso para $\mathbb Z[i]$ el dominio euclidiano de números enteros gausianos?

Lo primero que intenté fue $\gcd (F_n i, F_{n + 1})$ pero se reduce a lo mismo que en $\mathbb Z[i]$ .

Lo segundo que intenté fue buscar en Google. El primer resultado fue Wikipedia. Ugh.

Fue entonces cuando decidí hacer la pregunta aquí. Me advierten que esta pregunta "parece subjetiva y es probable que esté cerrada".

Pero creo que hay un criterio objetivo de lo que constituye un mal caso para el algoritmo euclidiano.

Answer 1

El documento que se presenta a continuación ataca exactamente este problema:

Heinrich Rolletschek, Sobre el número de divisiones del algoritmo euclidiano aplicado a números enteros gaussianos , Revista de Computación Simbólica 2 (1986), no. 3, 261-291.

Demuestra un análogo del teorema de Lamé sobre el número máximo de pasos, pero parece que encontrar pares que alcancen este máximo sigue siendo un problema abierto. (O al menos lo era en 1986).