¿Existe una forma sencilla de saber si para un determinado $n$ hay $m$ tal que el algoritmo euclidiano sobre $n,m$ se ejecuta para un número determinado de pasos, y/o una manera de encontrar $m$ eficientemente (aparte de probar todos $m<n$ por fuerza bruta)? Para simplificar, limítese a $m$ relativamente primo a $n$ . Por ejemplo, si $n=13$ y queremos 1 paso, entonces $m=6$ funciona: $13=2\cdot6+1$ . Y para 3 pasos $m=7$ funciona: $13=1\cdot7+5$ , $7=1\cdot5+2$ y $5=2\cdot2+1$ .
Dado que el algoritmo se utiliza para encontrar la inversa modular $m^{-1}$ (mod $n$ ) cuantos menos pasos se den más fácil es encontrarlo (por lo que en particular las ejecuciones de pocos pasos son convenientes para hacer problemas de tarea ). Obsérvese que es fácil encontrar pares para una longitud dada del algoritmo. Dado que la fracción continua de $n/m=[q_0;q_1,\dots,q_k]$ registra los cocientes se puede tomar una fracción continua arbitraria de longitud dada, y encontrar $n,m$ contratándolo. Por lo tanto, una forma alternativa de plantear la pregunta es si existe una manera eficiente de "parametrizar" todas las fracciones continuas con un numerador dado.
Si la pregunta general es demasiado difícil, ¿qué se puede decir de $n$ primo, y/o longitudes pequeñas como 2,3,4? Es fácil para 1, ya que $n=q\cdot m+1$ los requisitos $m$ no son más que los divisores de $n-1$ . Pero ya para 2 tenemos que encontrar $m,r$ que satisfagan simultáneamente $m|(n-r)$ y $r|(m-1)$ que no parece obvio cómo hacerlo.
