Puede alguien darme una explicación dirigida a un estudiante de secundaria de por qué encontrar elgcd de dos números es más rápido utilizando el algoritmo euclidiano en comparación con el uso de la factorización, no debería haber ninguna eficiencia del algoritmo involucrado, sólo una explicación general, algo que mi hermano en el grado 9 puede entender.
Respuestas
¿Demasiados anuncios?
El algoritmo euclidiano es una receta definida que te dice exactamente lo que tienes que hacer en cada paso; no hay que adivinar, ni hacer pruebas y errores. Intentar factorizar un número (incluso con algunos de los mejores métodos conocidos en la actualidad) implica conjeturas y ensayo y error; la división de prueba es, por supuesto, el ejemplo clásico, pero incluso algunos de nuestros mejores métodos (la factorización de la curva elíptica y el tamiz del campo numérico, por nombrar dos) implican algunas "conjeturas aleatorias" y ensayos para intentar encontrar factores. Por supuesto, son formas más inteligentes de probar que simplemente probar todo lo que hay, pero aún así se acaba haciendo un montón de trabajo sucio en el camino que no lleva a ninguna parte (dividir por un número que no es un factor en la división de prueba; no conseguir buenas relaciones en el tamiz de campo numérico; realizar todos los cálculos en una curva elíptica modulo $n$ y no encontrar ningún elemento no invertible), o realizar cálculos de buena apariencia que terminan con un factor trivial ( $1$ o $n$ ). En esencia, se trata de un "esfuerzo desperdiciado", un desperdicio que simplemente no se produce con el algoritmo euclidiano.
Añadido: Tenga en cuenta que esto es un reflejo de nuestros métodos actuales de factorización conocidos, y no necesariamente (como señala Bill Dubuque, no sabemos de ninguna manera) una dificultad inherente a la factorización. No se quiere comparar la "factorización" con el "algoritmo euclidiano", se quiere comparar formas específicas de la factorización con el algoritmo euclidiano. Y las formas que conocemos (y las formas que conocen los estudiantes de secundaria, que probablemente sean la división de prueba más un puñado o dos de pruebas de divisibilidad para hacer la primera más sencilla) tienen estos inconvenientes.
Tal vez una analogía sería que el algoritmo euclidiano es como tener una receta completa para preparar un plato, y todos los ingredientes dispuestos para ser utilizados; la factorización implica empezar a preparar el plato, rebuscar entre tus provisiones para encontrar los ingredientes, y posiblemente darte cuenta a mitad de camino de que no tienes los ingredientes adecuados, lo que te obliga a empezar de nuevo con un nuevo plato para el que esperas tener los ingredientes. Incluso si la primera situación implica un plato complejo mientras que la segunda es una serie de intentos de platos muy sencillos y rápidos, lo más probable es que pases menos tiempo en total con el método de la receta completa y todos los ingredientes dispuestos que con el método de "probemos esto y esperemos tener todos los ingredientes".
David HAust
Puntos
2696
Se reduce al hecho de que los algoritmos de factorización conocidos actualmente son mucho más lentos que los algoritmos gcd más rápidos conocidos. Sería difícil decir mucho más que eso que sea comprensible para un estudiante de noveno grado (de hecho, se podría argumentar que ni siquiera los expertos saben mucho más que eso).
Kristopher Johnson
Puntos
265
Para números muy pequeños, la factorización es más rápida que el algoritmo euclidiano. Pero el algoritmo euclidiano da más; permite calcular recíprocos en aritmética modular.
Para números más grandes, encontrar factorizaciones puede ser lento o incluso prácticamente imposible imposible, pero el algoritmo eulcidiano sigue funcionando bien. También los modernos métodos de factorización, desde el Pollard rho hasta el tamiz del campo numérico, hacen uso esencial del algoritmo euclidiano.
