Sea \( m, e \in{} \mathbb{N} \), y supongamos que m no divide a e. El siguiente algoritmo encuentra un a tal que a | m y mcd(a, e)=1.
ALGORITMO: \( g_0 := m; h_0 := mcd(m,e). \forall{} i \geq{} 1: g_i := g_{i-1} / h_{i-1}; h_i := (g_i, h_{i-1}) \) hasta \( h_l = 1 \). Entonces \( a:=g_l \).
Me piden calcular su complejidad.
Como en cada paso hay que hacer una división y un mcd, había pensado en calcular la complejidad de la división y la complejidad del mcd, y sumarlas. No sé si esto será correcto. Creo que el resultado debería ser una \( O((logm)^3) \), pero no sé justificarlo del todo.
