Encontrar el gcd mediante el algoritmo de Euclides

Question

Encuentre $\gcd(47,6)$ utilizando el algoritmo de euclides

Sé que si $\gcd(a,b)=\gcd(b,r)$ donde $a=qb+r$

Así que en ese caso $47=7\cdot6+5$ o $47=8\cdot6-1$ ¿debo preferir la descomposición de los números primos? ¿hará el proceso más corto?

Answer 1

Excepto en los casos en los que la descomposición de los factores primos está disponible, se debería preferir el algoritmo de Euclides, ya que es mucho más eficiente computacionalmente. El algoritmo de Euclides es como máximo lineal en el número de dígitos del número menor $O(\log n)$ , mientras que la factorización de enteros es un problema notoriamente más difícil, mejor tiempo de funcionamiento publicado es $O\left(exp\sqrt[3]{\frac{64}{9}\log n (\log\log n)^2}\right)$ . La dificultad de la factorización de enteros es la base de los algoritmos de clave pública RSA.

Answer 2

Si la pregunta es para encontrar el GCD, puedes usar el que encuentres que te llevará más rápido a la respuesta. Si quieren que encuentres dos números tales que $ax+by=gcd(a,b)$ entonces tienes que usar el algoritmo de Euclides

Answer 3

Depende de cuáles sean los números iniciales. Prueba con $\gcd(F_{n + 1}, F_n)$ , donde $F_n$ es el $n$ número de Fibonacci.

Sin embargo, por lo general, el algoritmo euclidiano es más rápido, o es sólo un poco más lento que la factorización de primos, por lo que no merece la pena preocuparse por el rendimiento.

En el caso concreto de $\gcd(47, 6)$ La factorización en primo parece más rápida sólo porque ya sabemos que 47 es primo y 6 es semiprimo, por lo que parece que sabemos inmediatamente que los dos números son coprimos.

Me parece que el algoritmo euclidiano se suele implementar para hacer primero $\frac{a}{b}$ con $a > b$ y ambos números son positivos. Así que después de $47 = 7 \times 6 + 5$ Lo hacemos $6 = 1 \times 5 + 1$ y ahí tenemos nuestra respuesta en dos pasos.

Ahora intente $\gcd(100459, 14351)$ . Tengo la sensación de que el algoritmo de Euclides te da la respuesta en dos pasos. Para saber si 100459 es primo, puede que tengas que hacer 316 divisiones de prueba.