Algoritmo de Euclides extendido

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 9 de marzo de 2022; las comprobaciones requieren 7 ediciones .

El algoritmo de Euclides extendido es una extensión del algoritmo de Euclides , que calcula, además del máximo común divisor (MCD) de los números enteros a y b , también los coeficientes de la relación de Bezout , es decir, los números enteros x e y , tales que

hacha+por={\text{gcd}}(a,b).

El algoritmo está validando porque gcd es el único número que satisface la ecuación y divide los números de entrada. El algoritmo también permite calcular los cocientes de a y b por su máximo común divisor casi sin coste adicional.

El Algoritmo Euclidiano Extendido también se refiere a un algoritmo muy similar para calcular el máximo común divisor de polinomios y calcular los coeficientes de proporción de Bezout de dos polinomios en una variable.

El algoritmo de Euclides extendido es especialmente útil cuando a y b son coprimos . Bajo estas condiciones, x es el módulo recíproco de a módulo b , y y es el módulo recíproco de b módulo a . De manera similar, el algoritmo de Euclides extendido para polinomios permite calcular el recíproco en extensiones algebraicas y, en particular, en campos finitos de orden no simple. Por lo tanto, ambos algoritmos de Euclides extendidos son ampliamente utilizados en criptografía . En particular, calcular el módulo inverso es un paso esencial para obtener un par de claves en el método de cifrado de clave pública RSA .

Descripción

El algoritmo estándar de Euclides se realiza mediante divisiones sucesivas con resto , mientras que no se utiliza el cociente, solo se conserva el resto . El algoritmo extendido también usa cocientes de división. Más precisamente, el algoritmo euclidiano estándar para los números a y b como entrada consiste en calcular una secuencia de cocientes y una secuencia de residuos tales que ${\displaystyle q_{1},\ldots,q_{k))$ ${\displaystyle r_{0},\ldots,r_{k+1))$

{\begin{alineado}r_{0}&=a\\r_{1}&=b\\&\,\,\,\vdots \\r_{i+1}&=r_{i- 1}-q_{i}r_{i}\quad {\text{i}}\quad 0\leqslant r_{i+1}<|r_{i}|\quad {\text{(esto define }}q_ {i})\\&\,\,\,\vdots \end{alineado}}

La principal propiedad de la división con resto es que la desigualdad de la derecha determina la unicidad tanto de para como de $q_{yo}$ $r_{i+1}$ $r_{i-1}$ ${\ estilo de visualización r_ {i}.}$

El cálculo se detiene cuando llegamos al resto cero . El máximo común divisor es entonces igual al último resto distinto de cero $r_{k+1}$ $r_{k}.$

El algoritmo de Euclid extendido funciona de manera similar pero agrega otras dos secuencias

{\begin{alineado}r_{0}&=a&r_{1}&=b\\s_{0}&=1&s_{1}&=0\\t_{0}&=0&t_{1}& =1\\&\,\,\,\vpuntos &&\,\,\,\vpuntos \\r_{i+1}&=r_{i-1}-q_{i}r_{i}&{\ texto{ y }}0&\leqslant r_{i+1}<|r_{i}|&{\text{(esto define }}q_{i}{\text{)))\\s_{i+1} &=s_{i-1}-q_{i}s_{i}\\t_{i+1}&=t_{i-1}-q_{i}t_{i}\\&\,\,\ ,\vdots \end{alineado}}

El cálculo también se detiene cuando y como resultado obtenemos $r_{k+1}=0$

$r_{k}$ es igual al máximo común divisor de los valores de entrada , y ${\displaystyle a=r_{0))$ $b=r_{1}.$
Los coeficientes de Bezout son iguales a y , es decir ${\ Displaystyle s_ {k}}$ $t_{k},$ ${\text{gcd}}(a,b)=r_{k}=as_{k}+bt_{k}$
Los cocientes de dividir a y b por su máximo común divisor están dados por y $s_{k+1}=\pm {\frac {b}({\text{gcd}}(a,b)))$ $t_{k+1}=\pm {\frac {a}({\text{gcd}}(a,b)))$

Además, si ambos números a y b son positivos y , entonces ${\text{gcd}}(a,b)\neq \min(a,b)$

|s_{i}|\leqslant \left\lfloor {\frac {b}{2{\text{gcd}}(a,b)))\right\rfloor \quad {\text{i}} \quad |t_{i}|\leqslant \left\lfloor {\frac {a}{2{\text{gcd}}(a,b)))\right\rfloor

para , donde significa la parte entera del número x , es decir, el entero más grande que no exceda de x . $0\leqslant i\leqslant k,$ $\lpiso x\rpiso$

De ello se deduce que el par de coeficientes de Bezout dado por el algoritmo de Euclides extendido es el par mínimo de coeficientes de Bezout, ya que es el único par que satisface las dos desigualdades anteriores.

También se deduce que el algoritmo puede ejecutarse sin riesgo de desbordamiento de enteros por un programa que utiliza enteros de un tamaño fijo que es mayor que a y b .

Ejemplo

La siguiente tabla muestra cómo funciona el algoritmo de Euclides extendido con los números de entrada 240 y 46 . El máximo común divisor es el último elemento distinto de cero, 2 en la columna de resto. El cálculo termina en la línea 6 porque el resto es 0 . Los coeficientes de Bezout aparecen en las dos últimas celdas de la penúltima fila. Es fácil comprobar que −9 × 240 + 47 × 46 = 2 . Finalmente, los dos últimos valores 23 y −120 de la última fila, hasta un signo, son los cocientes de los valores de entrada 46 y 240 divididos por el máximo común divisor 2 .

índice i	cociente q i −1	resto r yo	si yo	yo _
0		240	una	0
una		46	0	una
2	240 ÷ 46 = 5	240 − 5 × 46 = 10	1 − 5 × 0 = 1	0 − 5 × 1 = −5
3	46 ÷ 10 = 4	46 − 4 × 10 = 6	0 − 4 × 1 = −4	1 − 4 × −5 = 21
cuatro	10 ÷ 6 = 1	10 − 1 × 6 = 4	1 − 1 × −4 = 5	−5 − 1 × 21 = −26
5	6 ÷ 4 = 1	6 − 1 × 4 = 2	−4 − 1 × 5 = −9	21 − 1 × −26 = 47
6	4 ÷ 2 = 2	4 − 2 × 2 = 0	5 − 2 × −9 = 23	−26 − 2 × 47 = −120

Prueba

Porque la secuencia es una secuencia decreciente de enteros no negativos (a partir de i = 2). Entonces el algoritmo debe detenerse en algún punto , lo que prueba que el algoritmo finalmente terminará. $0\leqslant r_{i+1}<|r_{i}|,$ ${\ Displaystyle r_ {i}}$ $r_{k+1}=0.$

Dado que el máximo común divisor será el mismo para y Esto demuestra que el máximo común divisor de las entradas será el mismo que para Esto demuestra que es el máximo común divisor de a y b . (Hasta este punto, la prueba es la misma que para el algoritmo clásico de Euclides). $r_{i+1}=r_{i-1}-r_{i}q_{i},$ ${\ estilo de visualización (r_ {i-1}, r_ {i})}$ ${\ estilo de visualización (r_{i},r_{i+1}).}$ ${\displaystyle a=r_{0},b=r_{1))$ $r_{k},r_{k+1}=0.$ ${\ Displaystyle r_ {k}}$

Como y , tenemos para i = 0 y 1. La relación se prueba por inducción para todo : ${\displaystyle a=r_{0))$ $b=r_{1},$ $as_{i}+bt_{i}=r_{i}$ $yo>1$

r_{i+1}=r_{i-1}-r_{i}q_{i}=(as_{i-1}+bt_{i-1})-(as_{i}+bt_{ i})q_{i}=(como_{i-1}-como_{i}q_{i})+(bt_{i-1}-bt_{i}q_{i})=como_{i+1} +bt_{i+1}.

Entonces y son coeficientes de Bezout. ${\ Displaystyle s_ {k}}$ $gracias$

Considere la matriz

A_{i}={\begin{pmatrix}s_{i-1}&s_{i}\\t_{i-1}&t_{i}\end{pmatrix}}.

Las relaciones recurrentes se pueden reescribir en forma de matriz

A_{i+1}=A_{i}\cdot {\begin{pmatrix}0&1\\1&-q_{i}\end{pmatrix)).

La matriz es la matriz identidad y su determinante es uno. El determinante de la matriz más a la derecha aquí es −1. De ello se deduce que el determinante es En particular, porque tenemos Si consideramos esto como una relación de Bézout, obtenemos eso y son coprimos . La relación anterior y el lema de Euclides muestran que b divide a , es decir, a algún número entero d . Dividiendo por la razón , obtenemos que Así, y son enteros coprimos que son cocientes de dividir a y b por un divisor común, que es su máximo común divisor o su opuesto . $A_{1}$ $Ai}$ ${\ estilo de visualización (-1) ^ {i-1}.}$ ${\ estilo de visualización i = k + 1}$ $s_{k}t_{k+1}-t_{k}s_{k+1}=(-1)^{k}.$ $s_{k+1}$ $t_{k+1}$ ${\ estilo de visualización como_{k+1}+bt_{k+1}=0}$ $s_{k+1}$ $b=ds_{k+1}$ $s_{k+1}$ ${\ estilo de visualización como_{k+1}+bt_{k+1}=0}$ $a=-dt_{k+1}.$ $s_{k+1}$ ${\ estilo de visualización -t_{k+1}}$

Para probar la última afirmación, suponga que a y b son positivos y . Entonces , y si , se puede ver que las secuencias s y t para ( a , b ) en el algoritmo extendido son, hasta los ceros y unos iniciales, las secuencias t y s para ( b , a ). Las definiciones muestran entonces que el caso ( a , b ) se reduce al caso ( b , a ). Por lo tanto, sin pérdida de generalidad, podemos suponer que . ${\text{gcd}}(a,b)\neq \min(a,b)$ ${\ estilo de visualización a \ neq b}$ $a<b$ $a>b$

Puedes ver que es igual a 1, y (que existe debido a ) es negativo. Por lo tanto, cambia de signo y aumenta estrictamente en valor absoluto, lo que se sigue por inducción de la definición y el hecho de que para . El caso de está satisfecho porque . Lo mismo ocurre después de los primeros términos por las mismas razones. Además, es fácil ver que (si a y b son positivos y ). Después $s_{2}$ ${\ estilo de visualización s_ {3))$ ${\text{gcd}}(a,b)\neq \min(a,b)$ $si}$ $q_{i}\geqslant 1$ $1\leqslant i\leqslant k$ $yo=1$ $a>b$ $t_{yo}$ ${\ Displaystyle q_ {k} \ geqslant 2}$ ${\text{gcd}}(a,b)\neq \min(a,b)$

|s_{k+1}|=\left|{\frac {b}({\text{GCD))(a,b)))\right|\geqslant 2|s_{k}|\qquad {\text{u}}\qquad |t_{k+1}|=\left|{\frac {a}({\text{gcd}}(a,b)))\right|\geqslant 2|t_ {k}|.

Esto, junto con el hecho de que no es menor en valor absoluto que cualquier anterior o respectivamente, completa la prueba. ${\ Displaystyle s_ {k}, t_ {k}}$ $si}$ $t_{yo}$

Una extensión del algoritmo de Euclides para polinomios

Para polinomios en una variable con coeficientes en un campo, todo funciona de manera similar, incluida la división de Euclides, la relación de Bezout y el algoritmo de Euclides extendido. La primera diferencia es que en la división euclidiana y en el algoritmo se debe reemplazar la desigualdad por la desigualdad de grados, el resto sigue igual, solo se reemplazan los enteros por polinomios. $0\leqslant r_{i+1}<|r_{i}|$ $\grados r_{i+1}<\grados r_{i}.$

La segunda diferencia radica en los límites sobre el tamaño de los coeficientes de Bézout dados por el algoritmo de Euclides extendido, que son más precisos en el caso de los polinomios, lo que conduce al siguiente teorema.

Si a y b son dos polinomios distintos de cero, el algoritmo euclidiano extendido produce un par único de polinomios ( s , t ) tales que

as+bt={\text{gcd}}(a,b)

\deg s<\deg b-\deg({\text{gcd))(a,b)),\quad \deg t<\deg a-\deg({\text{gcd))(a ,b)).

La tercera diferencia es que para los polinomios, el máximo común divisor se define hasta la multiplicación por una constante distinta de cero. Hay varias formas de determinar el máximo común divisor de forma única.

En matemáticas, por lo general se requiere que el máximo común divisor sea un polinomio reducido . Para lograr esto, basta con dividir todos los elementos del resultado por el factor principal , lo que permite, si ayb son coprimos , obtener 1 en el lado derecho de la desigualdad de Bezout. De lo contrario, obtenemos una constante distinta de cero. En álgebra informática, los polinomios suelen tener coeficientes enteros, y esta forma de normalizar el máximo común divisor da como resultado una gran cantidad de fracciones. $r_{k}.$

Otra forma de normalizar el máximo común divisor para el caso de coeficientes enteros es dividir el polinomio de salida por el mcd de los coeficientes del polinomio para obtener un máximo común divisor primitivo . Si los polinomios de entrada son coprimos, la normalización da como resultado el máximo común divisor de 1. La desventaja de este enfoque es la gran cantidad de fracciones que deben calcularse y simplificarse. $r_{k},$

El tercer enfoque es extender el algoritmo para calcular secuencias intermedias de pseudoresiduales ( subresultados ) de manera similar a extender el algoritmo de Euclides al algoritmo de Euclides extendido. Esto permite, a partir de un polinomio con coeficientes enteros, obtener polinomios con coeficientes enteros en el proceso de cálculo. Además, cada residuo calculado sigue siendo un subresultado. En particular, si los polinomios son coprimos, entonces la relación de Bézout se convierte en $Rhode Island}$

as+bt=\operatorname {Res} (a,b),

donde significa la resultante de a y b . De esta forma, la relación de Bezout no tiene denominador en la fórmula. Si dividimos todo por la resultante, obtenemos la clásica relación de Bezout con un denominador común explícito para los números racionales que aparecen. ${\ estilo de visualización \ nombre del operador {Res} (a, b)}$

Pseudocódigo

Para implementar el algoritmo anterior, se debe tener en cuenta que solo se necesitan los dos últimos valores de las variables indexadas en cada paso. Por lo tanto, para ahorrar memoria, cada variable indexada debe reemplazarse por solo dos variables.

Para simplificar, el siguiente algoritmo (y otros algoritmos en este artículo) usan asignaciones paralelas . En los lenguajes de programación que no soportan esta función, la asignación en paralelo debe realizarse mediante una variable adicional. Por ejemplo, la primera tarea

(r_antiguo, r) := (r, r_antiguo - cociente * r)

equivalente a

prueba := r; r := old_r - cociente × prov; antiguo_r := prueba;

y lo mismo para otras asignaciones paralelas. Esto conduce al siguiente código:

función extended_gcd(a, b) (antiguo_r, r) := (a, b) (antiguo_s, s) := (1, 0) (antiguo_t, t) := (0, 1) while r ≠ 0 do cociente := old_r div r (r_antiguo, r) := (r, r_antiguo − cociente × r) (antiguo_s, s) := (s, antiguo_s − cociente × s) (ant_t, t) := (t, old_t − cociente × t) salida "Coeficientes de Bezout:", (old_s, old_t) salida "máximo común divisor:", old_r salida "cocientes por mcd:", (t, s)

Los cocientes de dividir a y b por su máximo común divisor, que también está en la salida, pueden tener el signo equivocado. Esto es fácil de arreglar al final del cálculo, pero no se hace aquí para simplificar el código. De manera similar, si a o b es cero y el segundo número es negativo, el máximo común divisor en la salida es negativo, por lo que todos los signos en la salida deben invertirse.

Finalmente, notamos que la relación de Bezout se puede resolver relativamente para dado . Luego, una optimización para el algoritmo anterior solo calcularía la secuencia (que conduce al coeficiente de Bézout ) y calcularía el valor al final del algoritmo: $hacha+por={\text{gcd}}(a,b)$ $y$ $a,b,x,{\text{gcd}}(a,b)$ ${\ Displaystyle s_ {k}}$ $X$ $y$

función extended_gcd(a, b) s := 0; viejo_s := 1 r := b; viejo_r := un while r ≠ 0 do cociente := old_r div r (r_antiguo, r) := (r, r_antiguo − cociente × r) (antiguo_s, s) := (s, antiguo_s − cociente × s) si b ≠ 0 entonces bezout_t := (old_r − old_s × a) div b else bezout_t := 0 salida "coeficientes bezout:", (old_s, bezout_t) salida "máximo común divisor:", old_r

Sin embargo, en muchos casos esto no será una optimización real: el algoritmo anterior es insensible al desbordamiento cuando se usan números enteros en la máquina (es decir, números enteros con un límite superior fijo en la representación), multiplicando old_s * a al calcular bezout_t puede causar un desbordamiento , que limita la optimización a solo datos de entrada que no excedan la mitad del tamaño máximo de enteros. Si se usan números enteros de tamaño ilimitado, el tiempo requerido para la multiplicación y división crece cuadráticamente con el tamaño de los números enteros. De esto se deduce que la "optimización" reemplaza una secuencia de multiplicaciones/divisiones de números pequeños con una sola multiplicación/división, lo que requiere más tiempo de ejecución que las operaciones que reemplaza tomadas en conjunto.

División simplificada

Divisiónabestá en forma canónica simplificada si a y b son coprimos y b es positivo. Esta forma simplificada canónica se puede obtener reemplazando las tres líneas de salida con pseudocódigo

si s = 0 entonces genera "División por cero" si s < 0 entonces s := − s ; t := − t ( para evitar divisores de cero ) si s = 1 , entonces salida - t ( para evitar divisores de 1) salida -t_ _s

La prueba de este algoritmo se basa en el hecho de que s y t son dos enteros coprimos tales que , y luego . Para obtener una forma canónicamente simplificada, basta con cambiar el signo para obtener un divisor positivo. ${\ estilo de visualización como + bt = 0}$ ${\frac{a}{b}}=-{\frac{t}{s}}$

Si b divide a a partes iguales, el algoritmo realiza solo una iteración y tenemos s = 1 al final del algoritmo. Este es el único caso en el que la salida es un número entero.

Cálculo de la inversa en estructuras modulares

El algoritmo de Euclides extendido es un medio importante para calcular recíprocos en estructuras modulares, generalmente enteros modulares y extensiones de campos algebraicos . Un ejemplo importante del último caso son los campos finitos de orden no simple.

Módulo enteros

Si n es un entero positivo, el anillo Z / n Z se puede identificar con el conjunto {0, 1, ..., n -1} de restos de división con resto de n , suma y multiplicación es tomando el resto de división por n de los resultados de la suma y multiplicación de números enteros. Un elemento a Z / n Z tiene un inverso (es decir, un elemento invertible ) si es relativamente primo con n . En particular, si n es primo , a tiene un inverso si es distinto de cero (módulo n ). Es decir, Z / n Z es un campo si y solo si n es primo.

La relación de Bezout establece que a y n son coprimos si y solo si hay números enteros s y t tales que

ns+at=1

El módulo de comparación n da

at\equiv 1\mod n.

Entonces t , o más precisamente, el resto de dividir t por n , es igual al recíproco de un módulo n .

Para adaptar el algoritmo de Euclides extendido a este problema, se debe tener en cuenta que el coeficiente de Bezout de n no es necesario y, por lo tanto, no es necesario calcularlo. Además, para obtener el resultado como un número positivo menor que n , puede usar el hecho de que el número entero t proporcionado por el algoritmo satisface la relación . Es decir, si , puede agregar n al final. Esto da como resultado un pseudocódigo donde el valor de entrada n es un número entero mayor que 1. ${\ estilo de visualización | t | < n}$ $t<0$

function inverse(a, n) t := 0; newt := 1 r := n; newr := a while newr ≠ 0 do quotient := r div newr (t, newt) := (newt, t − quotient × newt) (r, newr) := (newr, r − quotient × newr) if r > 1 then return "не обратимо" if t < 0 then t := t + n return t

Extensiones de campos algebraicos

El algoritmo de Euclides extendido es también la herramienta principal para calcular los inversos de las extensiones de campos algebraicos . Un caso importante, muy utilizado en criptografía y teoría de la codificación , es el caso de los campos finitos de orden no simple. De hecho, si p es simple y q = p d , el campo de orden q es una extensión algebraica del campo primo con p elementos formado por la raíz de un polinomio irreducible de grado d .

La extensión algebraica L del cuerpo K generado por la raíz de un polinomio irreducible p de grado d se puede identificar con el anillo del cociente , y sus elementos están en relación biyectiva con polinomios de grado menor que d La suma en L es la suma de polinomios La multiplicación en L es el resto de la división con resto por p del producto de polinomios. Así, para completar la aritmética en L , solo queda determinar cómo calcular los elementos inversos. Esto se hace con el algoritmo de Euclid extendido. $K[X]/\langle p\rangle ,$

El algoritmo es muy similar al anterior para calcular el inverso modular. Hay dos diferencias principales: en primer lugar, no se necesita la penúltima línea, ya que los coeficientes de Bezout resultantes siempre tienen un grado menor que d . En segundo lugar, el máximo común divisor que resulta si las entradas son polinomios coprimos puede ser cualquier elemento distinto de cero de K . Este coeficiente de Bézout (un polinomio suele tener un grado positivo) debe multiplicarse por el recíproco de este elemento en K . En el pseudocódigo (abajo), p es un polinomio de grado mayor que uno y a es un polinomio.

function inverse(a, p) t := 0; newt := 1 r := p; newr := a while newr ≠ 0 do quotient := r div newr (r, newr) := (newr, r − quotient × newr) (t, newt) := (newt, t − quotient × newt) if degree(r) > 0 then return "Either p is not irreducible or a is a multiple of p" return (1/r) × t Ejemplo

Por ejemplo, deje que el polinomio defina el campo final y sea el elemento cuyo inverso se busque. Luego, el funcionamiento del algoritmo se muestra en la siguiente tabla. Recuerde que en un campo de orden , tenemos - z = z y z + z = 0 para cualquier elemento o z del campo). Dado que 1 es el único elemento distinto de cero de GF(2), no es necesario ajustar la última línea del pseudocódigo. $p=x^{8}+x^{4}+x^{3}+x+1$ $FG(2^{8})$ $a=x^{6}+x^{4}+x+1$ $2^{n}$

paso	privado	r, nuevo	s, noticias	t, tritón
		$p=x^{8}+x^{4}+x^{3}+x+1$	una	0
		$a=x^{6}+x^{4}+x+1$	0	una
una	$x^{2}+1$	${\ estilo de visualización x^{2}=pa(x^{2}+1)}$	una	${\ estilo de visualización x^{2}+1=0-1\veces (x^{2}+1)}$
2	${\ estilo de visualización x^{4}+x^{2}}$	$x+1=hacha^{2}(x^{4}+x^{2})$	${\ estilo de visualización x^{4}+x^{2}=0-1(x^{4}+x^{2})}$	$x^{6}+x^{2}+1=1-(x^{4}+x^{2})(x^{2}+1)$
3	x +1	${\ estilo de visualización 1 = x ^ {2} - (x + 1) (x + 1)}$	$x^{5}+x^{4}+x^{3}+x^{2}+1=1-(x+1)(x^{4}+x^{2})$	$x^{7}+x^{6}+x^{3}+x=(x^{2}+1)-(x+1)(x^{6}+x^{2} +1)$
cuatro	x +1	${\ estilo de visualización 0 = (x + 1) -1 \ veces (x + 1)}$	$x^{6}+x^{4}+x+1=(x^{4}+x^{2})-(x+1)(x^{5}+x^{4} +x^{3}+x^{2}+1)$

Así, el elemento inverso es , que se confirma multiplicando los dos elementos y tomando el resto sobre p del resultado. ${\ estilo de visualización x^{7}+x^{6}+x^{3}+x}$

El caso de más de dos números

Puede manejar el caso de más de dos números de forma iterativa. Primero mostremos eso . Para la demostración, pongamos . Por definición, mcd es un divisor de y . Entonces para algunos . Del mismo modo , es un divisor , por lo que para algunos . deja _ Por construcción , , pero dado que es el máximo divisor, es un elemento invertible de . Y puesto que , el resultado está probado. ${\text{gcd}}(a,b,c)={\text{gcd}}({\text{gcd}}(a,b),c)$ $d={\text{gcd}}(a,b,c)$ $d$ $a$ $b$ ${\text{gcd}}(a,b)=kd$ $k$ $d$ $C$ ${\ estilo de visualización c = jd}$ $j$ $u={\text{gcd}}(k,j)$ $tu$ $ud|a,b,c$ $d$ $tu$ $ud={\text{gcd}}({\text{gcd}}(a,b),c)$

Así, si , es decir, y , tal que , de modo que la ecuación final será $na+mb={\text{gcd}}(a,b)$ $X$ $y$ $x{\text{mcd}}(a,b)+yc={\text{mcd}}(a,b,c)$

x(na+mb)+yc=(xn)a+(xm)b+yc={\text{gcd}}(a,b,c).\,

Para ir a n números, usamos inducción

{\text{gcd}}(a_{1},a_{2},\dots ,a_{n})={\text{gcd}}(a_{1},\,{\text{mcd }}(a_{2},\,{\text{mcd}}(a_{3},\puntos,{\text{mcd}}(a_{n-1}\,,a_{n}))) ,\puntos ),

Véase también

Notas

Literatura

Donald Knuth. Capítulo 4 // El arte de la programación informática . — Addison-Wesley. - T. 2. .
- Traducido por Donald Knuth. El arte de programar. - 1998. - V. 2. Algoritmos obtenidos.
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein . apartado 31.2: Máximo común divisor. // Introducción a los Algoritmos . - Segunda edicion. - MIT Press y McGraw-Hill, 2001. - P. 859-861. — ISBN 0-262-03293-7 .
- Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmos: construcción y análisis , 3.ª edición = Introducción a los algoritmos, tercera edición. - M. : "Williams" , 2013. - 1328 p. - ISBN 978-5-8459-1794-2 .

Enlaces

Fuente de la forma del algoritmo utilizado para determinar el inverso multiplicativo en GF(2^8)

Algoritmos de teoría de números
Pruebas de simplicidad	Molinero Miller - Rabín Luca-Lemaire pepina Agrawala - Kayala - Sajonia Ruiseñor - Strassen
Encontrar números primos	Iterando sobre divisores Tamiz de Eratóstenes tamiz de atkin Tamiz Sundarama
Factorización	Iterando sobre divisores método Fermat p −1 Método de Pollard Algoritmo ρ de Pollard método Lehmann Método de la curva elíptica (algoritmo de Lenstra) algoritmo de dixon tamiz cuadrado
logaritmo discreto	Algoritmo de Gelfond-Shanks Algoritmo de Polig-Hellman Método ρ de Pollard Algoritmo del canguro de Pollard algoritmo de Adleman algoritmo COS
Encontrar MCD	Algoritmo de Euclides Algoritmo avanzado Algoritmo binario
Módulo aritmético	algoritmo de Montgomery Teorema del resto chino
Multiplicación y división de números.	Algoritmo Karatsuba Algoritmo de Toom-Cook Algoritmo de Schönhage-Strassen Algoritmo del Führer Algoritmo de Harvey-van der Hoeven Algoritmo de Burnickel-Ziegler
Calcular la raíz cuadrada	Algoritmo de Tonelli-Shanks Algoritmo de Berlekamp-Rabin