Algoritmo euclidiano extendido

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Método para calcular la relación de dos enteros con su mayor divisor común

En aritmética y programación informática, el algoritmo euclidiano extendido es una extensión del algoritmo euclidiano y calcula, además del máximo común divisor (mcd) de números enteros a y b, también los coeficientes de la identidad de Bézout, que son números enteros x e y tales que

ax+by=gcd(a,b).

Este es un algoritmo de certificación, porque el gcd es el único número que puede satisfacer esta ecuación y dividir las entradas simultáneamente. Permite calcular también, casi sin coste adicional, los cocientes de a y b por su máximo común divisor.

Algoritmo euclidiano extendido también se refiere a un algoritmo muy similar para calcular el máximo común divisor polinómico y los coeficientes de la identidad de Bézout de dos polinomios univariados.

El algoritmo euclidiano extendido es particularmente útil cuando a y b son coprimos. Con esa disposición, x es el inverso multiplicativo modular de a módulo b, y y es el inverso multiplicativo modular de b módulo a. De manera similar, el algoritmo euclidiano polinomial extendido permite calcular el inverso multiplicativo en extensiones de campos algebraicos y, en particular, en campos finitos de orden no primo. De ello se deduce que ambos algoritmos euclidianos extendidos se utilizan ampliamente en criptografía. En particular, el cálculo del inverso multiplicativo modular es un paso esencial en la derivación de pares de claves en el método de cifrado de clave pública RSA.

Descripción

El algoritmo estándar de Euclidean procede de una sucesión de divisiones de Euclidea cuyos cocientes no se utilizan. Sólo el restantes se mantienen. Para el algoritmo extendido, se utilizan los cocientes sucesivos. Más precisamente, el algoritmo Euclideano estándar con a y b como entrada, consiste en calcular una secuencia $q_{1},ldotsq_{k}$ de cocientes y una secuencia $r_{0},ldotsr_{{k+1}}$ de los restos

<math alttext="{displaystyle {begin{aligned}r_{0}&=a\r_{1}&=b\&,,,vdots \r_{i+1}&=r_{i-1}-q_{i}r_{i}quad {text{and}}quad 0leq r_{i+1}r0=ar1=b⋮ ⋮ ri+1=ri− − 1− − qiriy0≤ ≤ ri+1.SilencioriSilencio(Esto defineqi)⋮ ⋮ {fnMicrosoft Sans Serif} \r_{i+1} {i-1}-q_{i}r_{i}quad {text{and}quad 0leq {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif}}\fnMicrosoft Sans Serif}}<img alt="{displaystyle {begin{aligned}r_{0}&=a\r_{1}&=b\&,,,vdots \r_{i+1}&=r_{i-1}-q_{i}r_{i}quad {text{and}}quad 0leq r_{i+1}

Es la propiedad principal de la división euclidiana que las desigualdades en la derecha definen singularmente $q_{i}$ y $r_{{i+1}}$ desde $r_{{i-1}}$ y $r_{{i}}.$

El cálculo se detiene cuando uno llega a un resto $r_{{k+1}}$ que es cero; el mayor divisor común es entonces el último no cero restante $r_{{k}}.$

El algoritmo euclidiano extendido procede de manera similar, pero agrega otras dos secuencias, de la siguiente manera

<math alttext="{displaystyle {begin{aligned}r_{0}&=a&r_{1}&=b\s_{0}&=1&s_{1}&=0\t_{0}&=0&t_{1}&=1\&,,,vdots &&,,,vdots \r_{i+1}&=r_{i-1}-q_{i}r_{i}&{text{and }}0&leq r_{i+1}r0=ar1=bs0=1s1=0t0=0t1=1⋮ ⋮ ⋮ ⋮ ri+1=ri− − 1− − qiriy0≤ ≤ ri+1.SilencioriSilencio(Esto defineqi)si+1=si− − 1− − qisiti+1=ti− − 1− − qiti⋮ ⋮ {displaystyle {begin{aligned}r_{0} limit=a limitr_{1} {=b\s_{0} {=1 limits_{1} limit=0t_{0} limit=0_{1} limit=1=1\\\\\,,,,,,,,,, ",,,vdots \r_{i+1} limit=r_{i-1}-q_{i}r_{i} limit{text{y }0, {fnMicrosoft Sans Serif}s_{i} {fnMicrosoft Sans Serif}}s_{i}}s_{i+1} {i-1}-q_{i}s_{i}i}t_{i}}t_{i}=t_=t_}-q_{i}i}\i\\\\\c]\ccc]c]cH00}c]c]ccccH00}ccH00}cccH00}ccH00}cccccccccccccH00}cccccH00}cccccH00}cH00}cH00cH00ccH00cccH00}cccH vdots end{aligned}}<img alt="{displaystyle {begin{aligned}r_{0}&=a&r_{1}&=b\s_{0}&=1&s_{1}&=0\t_{0}&=0&t_{1}&=1\&,,,vdots &&,,,vdots \r_{i+1}&=r_{i-1}-q_{i}r_{i}&{text{and }}0&leq r_{i+1}

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

$r_{k}$ es el mayor divisor común de la entrada $a=r_{0}$ y ${displaystyle b=r_{1}.}$
Los coeficientes de Bézout son $s_{k}$ y ${displaystyle t_{k},}$ eso es ${displaystyle gcd(a,b)=r_{k}=as_{k}+bt_{k}}$
Los cocientes de a y b por su mayor divisor común $s_{{k+1}}=pm {frac {b}{gcd(a,b)}}$ y $t_{{k+1}}=pm {frac {a}{gcd(a,b)}}$

Además, si a y b son positivos y ${displaystyle gcd(a,b)neq min(a,b)}$ , entonces

{displaystyle |s_{i}|leq leftlfloor {frac {b}{2gcd(a,b)}}rightrfloor quad {text{and}}quad |t_{i}|leq leftlfloor {frac {a}{2gcd(a,b)}}rightrfloor }

para ${displaystyle 0leq ileq k,}$ Donde $lfloor xrfloor$ denota la parte integral de $x$ , que es el mayor entero no mayor que $x$ .

Esto implica que el par de coeficientes de Bézout proporcionado por el algoritmo euclidiano extendido es el par mínimo de coeficientes de Bézout, ya que es el único par que satisface las dos desigualdades anteriores.

También significa que el algoritmo se puede realizar sin desbordamiento de enteros mediante un programa informático que utilice números enteros de un tamaño fijo mayor que el de a y b.

Ejemplo

La siguiente tabla muestra cómo procede el algoritmo euclidiano extendido con entrada 240 y 46. El máximo común divisor es la última entrada distinta de cero, 2 en la columna "resto". El cálculo se detiene en la fila 6, porque el resto es 0. Los coeficientes de Bézout aparecen en las dos últimas entradas de la penúltima fila. De hecho, es fácil verificar que −9 × 240 + 47 × 46 = 2. Finalmente, las dos últimas entradas 23 y −120 de la última fila son, hasta el signo, los cocientes de la entrada 46 y 240 por el máximo común divisor 2.

índice i	quotient q_i−1	Restante r_i	s_i	t_i
0		240	1	0
1		46	0	1
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
4	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 - 120

Prueba

As $<math alttext="{displaystyle 0leq r_{i+1}0≤ ≤ ri+1.SilencioriSilencio,{displaystyle 0leq [R_{i+1}]<img alt="0leq r_{{i+1}}$ la secuencia de la $r_{i}$ es una secuencia decreciente de enteros no negativos (de i = 2 on). Así debe detenerse con algunos ${displaystyle r_{k+1}=0.}$ Esto demuestra que el algoritmo termina eventualmente.

As $r_{{i+1}}=r_{{i-1}}-r_{i}q_{i},$ el mayor divisor común es el mismo para ${displaystyle (r_{i-1},r_{i})}$ y ${displaystyle (r_{i},r_{i+1}).}$ Esto muestra que el mayor divisor común de la entrada ${displaystyle a=r_{0},b=r_{1}}$ es lo mismo que el de ${displaystyle r_{k},r_{k+1}=0.}$ Esto prueba que $r_{k}$ es el mayor divisor común a y b. (Hasta este punto, la prueba es la misma que la del algoritmo clásico de Euclidean.)

As $a=r_{0}$ y $b=r_{1},$ tenemos $as_{i}+bt_{i}=r_{i}$ para i = 0 y 1. La relación sigue por inducción para todos $1}" xmlns="http://www.w3.org/1998/Math/MathML">i■1{displaystyle i confía1}1" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dea233301b9ca8fe5dde94824f918c0ceaf7fd5f" style="vertical-align: -0.338ex; width:5.063ex; height:2.176ex;"/>$ :

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

Así $s_{k}$ y $t_{k}$ son coeficientes de Bézout.

Considere la matriz

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

La relación de recurrencia se puede reescribir en forma de matriz

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

La matriz $A_{1}$ es la matriz de identidad y su determinante es uno. El determinante de la matriz más correcta en la fórmula anterior es −1. De ahí que el determinante $A_{i}$ es $(-1)^{{i-1}}.$ En particular, para ${displaystyle i=k+1,}$ tenemos ${displaystyle s_{k}t_{k+1}-t_{k}s_{k+1}=(-1)^{k}.}$ Ver esto como identidad de Bézout, esto muestra que ${displaystyle s_{k+1}}$ y ${displaystyle t_{k+1}}$ son coprime. La relación $as_{{k+1}}+bt_{{k+1}}=0$ que ha sido probado arriba y el lema de Euclid muestra que ${displaystyle s_{k+1}}$ divideciones $b$ , eso es ${displaystyle b=ds_{k+1}}$ para algunos enteros $d$ . Dividiendo por ${displaystyle s_{k+1}}$ la relación $as_{{k+1}}+bt_{{k+1}}=0$ da ${displaystyle a=-dt_{k+1}.}$ Entonces, ${displaystyle s_{k+1}}$ y ${displaystyle -t_{k+1}}$ son los enteros coprime que son los cocientes $a$ y $b$ por un factor común, que es por lo tanto su mayor divisor común o su opuesto.

Para probar la última afirmación, asuma que a y b son positivos y ${displaystyle gcd(a,b)neq min(a,b)}$ . Entonces, ${displaystyle aneq b}$ , y si $<math alttext="{displaystyle a a.b{displaystyle a meantb} <img alt="a$ , se puede ver que el s y t secuencias para (a,b) bajo el EEE son, hasta los 0 y 1 iniciales, los t y s secuencias para (b,a). Las definiciones entonces muestran que el (a,b) caso reduce a la (b,a) caso. Entonces asume que $b}" xmlns="http://www.w3.org/1998/Math/MathML">a■b{displaystyle a prendab}b" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/83fc0063781fb9bf4ec7608b2fd11ed6d5b05a13" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;"/>$ sin pérdida de generalidad.

Se puede ver que $s_{2}$ 1 y $s_{3}$ (que existe por ${displaystyle gcd(a,b)neq min(a,b)}$ ) es un entero negativo. Después, el $s_{i}$ alterna en señal y aumenta estrictamente la magnitud, que sigue inductivamente de las definiciones y el hecho de que ${displaystyle q_{i}geq 1}$ para $1leq ileq k$ , el caso $i=1$ Oportunidad $b}" xmlns="http://www.w3.org/1998/Math/MathML">a■b{displaystyle a prendab}b" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/83fc0063781fb9bf4ec7608b2fd11ed6d5b05a13" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;"/>$ . Lo mismo es cierto para el $t_{i}$ después de los primeros términos, por la misma razón. Además, es fácil ver que ${displaystyle q_{k}geq 2}$ (cuando a y b son positivos y ${displaystyle gcd(a,b)neq min(a,b)}$ ). Así,

${displaystyle |s_{k+1}|=left|{frac {b}{gcd(a,b)}}right|geq 2|s_{k}|qquad {text{and}}qquad |t_{k+1}|=left|{frac {a}{gcd(a,b)}}right|geq 2|t_{k}|.}$

Esto, acompañado por el hecho de que ${displaystyle s_{k},t_{k}}$ son mayores o iguales al valor absoluto que cualquier anterior $s_{i}$ o $t_{i}$ respectivamente completó la prueba.

Algoritmo polinomial euclidiano extendido

Para polinomios univariados con coeficientes en un campo, todo funciona de forma similar, división euclidiana, identidad de Bézout y algoritmo euclidiano extendido. La primera diferencia es que, en la división Euclidea y el algoritmo, la desigualdad $<math alttext="{displaystyle 0leq r_{i+1}0≤ ≤ ri+1.SilencioriSilencio{displaystyle 0leq [R_{i+1}]<img alt="0leq r_{{i+1}}$ debe ser reemplazado por una desigualdad en los grados $<math alttext="{displaystyle deg r_{i+1}deg⁡ ⁡ ri+1.deg⁡ ⁡ ri.{displaystyle deg r_{i+1}.<img alt="deg r_{{i+1}}$ De lo contrario, todo lo que precede en este artículo sigue siendo el mismo, simplemente reemplazando los enteros por polinomios.

Una segunda diferencia radica en el límite del tamaño de los coeficientes de Bézout proporcionados por el algoritmo euclidiano extendido, que es más preciso en el caso polinomial, lo que lleva al siguiente teorema.

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

$as+bt=gcd(a,b)$

$<math alttext="{displaystyle deg s<deg b-deg(gcd(a,b)),quad deg tdeg s.deg b- - deg ()gcd()a,b)),deg t.deg a- - deg ()gcd()a,b)).{displaystyle deg s obtenidosdeg b-deg(gcd(a,b)),quad deg t madedeg a-deg(gcd(a,b)} <img alt="deg s<deg b-deg(gcd(a,b)),quad deg t$

Una tercera diferencia es que, en el caso del polinomio, el máximo común divisor se define solo hasta la multiplicación por una constante distinta de cero. Hay varias formas de definir sin ambigüedades un máximo común divisor.

En matemáticas, es común exigir que el divisor más común sea un polinomio monico. Para conseguir esto, basta dividir cada elemento de la salida por el coeficiente líder de $r_{{k}}.$ Esto permite que, si a y b son coprime, uno consigue 1 en el lado derecho de la desigualdad de Bézout. De lo contrario, uno puede conseguir cualquier no cero constante. En álgebra computarizada, los polinomios suelen tener coeficientes enteros, y esta manera de normalizar el divisor común más grande introduce demasiadas fracciones para ser conveniente.

La segunda manera de normalizar el mayor divisor común en el caso de los polinomios con coeficientes enteros es dividir cada salida por el contenido de $r_{{k}},$ para conseguir un divisor común más primitivo. Si los polinomios de entrada son coprime, esta normalización también proporciona un divisor común más grande igual a 1. El inconveniente de este enfoque es que muchas fracciones deben ser calculadas y simplificadas durante el cálculo.

Un tercer enfoque consiste en extender el algoritmo de secuencias pseudo-remanente subresultantes de una manera similar a la extensión del algoritmo de Euclidean al algoritmo de Euclidean extendido. Esto permite que, al comenzar con polinomios con coeficientes enteros, todos los polinomios que se computan tienen coeficientes enteros. Además, todos los restos calculados $r_{i}$ es un polinomio subresultante. En particular, si los polinomios de entrada son coprime, entonces la identidad de Bézout se convierte en

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

Donde $operatorname {Res}(a,b)$ denota el resultado de a y b. En esta forma de identidad de Bézout, no hay ningún denominador en la fórmula. Si uno divide todo por el resultante obtiene la identidad clásica de Bézout, con un denominador común explícito para los números racionales que aparecen en ella.

Pseudocódigo

Para implementar el algoritmo que se describe arriba, primero se debe señalar 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 los demás algoritmos de este artículo) utilizan asignaciones paralelas. En un lenguaje de programación que no tenga esta función, las asignaciones en paralelo deben simularse con una variable auxiliar. Por ejemplo, el primero,

(old_r, r):= (r, old_r - quotient * r)

es equivalente a

prov:= r;
r:= old_r - quotient × prov;
old_r:= prov;

y de manera similar para las otras asignaciones paralelas. Esto conduce al siguiente código:

función extended_gcd(a, b)
(old_r, r):= (a, b)
(old_s, s):= (1, 0)
(old_t, t):= (0, 1)

 mientras r ل 0 doquotient:= old_r div r
(old_r, r):= (r, old_r - quotient × r)
(old_s, s):= (s, old_s - quotient × s)
(old_t, t):= (t, old_t - quotient × t)

 Producto "Bézout coeficientes:", (old_s, old_t)
 Producto "Divisor común más grande", old_r
 Producto "cocientes por el gcd:", (t, s)

Los cocientes de a y b por su máximo común divisor, que es la salida, pueden tener un signo incorrecto. Esto es fácil de corregir al final del cálculo, pero no se ha hecho aquí para simplificar el código. De manera similar, si a o b es cero y el otro es negativo, el máximo común divisor resultante es negativo y todos los signos de la salida deben cambiarse.

Finalmente, note que en la identidad de Bézout, ${displaystyle ax+by=gcd(a,b)}$ , uno puede resolver para $y$ dado ${displaystyle a,b,x,gcd(a,b)}$ . Así, una optimización al algoritmo anterior es calcular sólo el $s_{k}$ secuencia (que produce el coeficiente Bézout $x$ ), y luego compute $y$ al final:

función extended_gcd(a, b)
s:= 0; old_s:= 1
r:= b; old_r:= a

 mientras r ل 0 doquotient:= old_r div r
(old_r, r):= (r, old_r - quotient × r)
(old_s, s):= (s, old_s - quotient × s)

 si b ل 0 entoncesbezout_t:= (old_r - old_s × a) div b
 másbezout_t:= 0

 Producto "Bézout coeficientes:", (old_s, bezout_t)
 Producto "Divisor común más grande", old_r

Sin embargo, en muchos casos esto no es realmente una optimización: mientras que el algoritmo anterior no es susceptible de desbordarse cuando se usa con números enteros de máquina (es decir, números enteros con un límite superior fijo de dígitos), la multiplicación de old_s * a en el cálculo de bezout_t puede desbordarse, lo que limita esta optimización a las entradas que se pueden representar en menos de la mitad del tamaño máximo. Cuando se usan números enteros de tamaño ilimitado, el tiempo necesario para la multiplicación y división crece cuadráticamente con el tamaño de los números enteros. Esto implica que la "optimización" reemplaza una secuencia de multiplicaciones/divisiones de números enteros pequeños por una sola multiplicación/división, lo que requiere más tiempo de cálculo que las operaciones que reemplaza, en conjunto.

Simplificación de fracciones

Una fracción $a / b$ está 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 del pseudocódigo anterior por

si  $s = 0$  luego salida "División por cero"
si  $s 0$  entonces  $s := - s$ ;  $t := - t$  ()para evitar denominadores negativos)
si  $s = 1$  luego salida  $- t$  ()para evitar denominadores iguales 1)
Producto  $- t / s$

La prueba de este algoritmo se basa en el hecho de que $s$ y $t$ son dos enteros coprime tales que $como + bt = 0$ , y así ${frac {a}{b}}=-{frac {t}{s}}$ . Para obtener la forma simplificada canónica, basta con mover el signo menos por tener un denominador positivo.

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

Cálculo de inversos multiplicativos en estructuras modulares

El algoritmo euclidiano extendido es la herramienta esencial para calcular los inversos multiplicativos en estructuras modulares, generalmente los enteros modulares y las extensiones de campos algebraicos. Un ejemplo notable del último caso son los campos finitos de orden no primo.

Enteros modulares

Si $n$ es un número entero positivo, el anillo $Z/nZ$ puede identificarse con el conjunto ${0, 1,..., n -1}$ de los restos de la división euclidiana entre $n$ , la suma y la multiplicación consistentes en tomar el resto por $n$ del resultado de la suma y la multiplicación de números enteros. Un elemento $a$ de $Z / n Z$ tiene un inverso multiplicativo (es decir, es una unidad) si es coprimo con $n$ . En particular, si $n$ es primo, $a$ tiene un multiplicativo inversa si no es cero (módulo $n$ ). Por lo tanto, $Z / n Z$ es un campo si y solo si $n$ es primo.

La identidad de Bézout afirma que $a$ y $n$ son coprimos si y solo si existen los enteros $s$ y $t tal que$

$ns+at=1$

Reduciendo este módulo de identidad $n$ da

${displaystyle atequiv 1mod n.}$

Así $t$ , o, más exactamente, el resto de la división de $t$ por $n$ , es el inverso multiplicativo de $a$ módulo $n$ .

Para adaptar el algoritmo euclidiano extendido a este problema, se debe señalar que el coeficiente de Bézout de $n$ no es necesario y, por lo tanto, no es necesario para ser computado Además, para obtener un resultado positivo y menor que n, se puede usar el hecho de que el entero $t$ proporcionado por el algoritmo satisface $| t | < n$ . Es decir, si $t < 0$ , se debe agregar $n$ al final. Esto da como resultado el pseudocódigo, en el que la entrada n es un número entero mayor que 1.

función inverso(a, n)
t:= 0; newt:= 1
r:= n; newr:= a

 mientras newr ل 0 doquotient:= r div newr
(t, newt):= (newt, t - quotient × newt)
(r, newr):= (newr, r− quotient × newr)

 si r 1 entonces retorno "a no es invertible"
 si t entoncest:= t + n

 retorno t

Extensiones de campos algebraicos simples

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

Una extensión algebraica simple $L$ de un campo $K$ , generado por la raíz de un polinomio irreducible $p$ grado $d$ puede ser identificado al anillo de cociente $K[X]/langle prangle$ , y sus elementos están en correspondencia bijetiva con los polinomios de grado menos que $d$ . La adición $L$ es la adición de polinomios. La multiplicación en $L$ es el resto de la división euroclidiana por $p$ del producto de los polinomios. Así, para completar la aritmética en $L$ , permanece sólo para definir cómo computar los inversos multiplicativos. Esto es hecho por el algoritmo de Euclidean extendido.

El algoritmo es muy similar al proporcionado anteriormente para calcular el inverso multiplicativo modular. Hay dos diferencias principales: en primer lugar, la penúltima línea no es necesaria, porque el coeficiente de Bézout que se proporciona siempre tiene un grado menor que $d$ . En segundo lugar, el máximo común divisor que se proporciona, cuando los polinomios de entrada son coprimos, puede ser cualquier elemento distinto de cero de $K$ ; este coeficiente de Bézout (un polinomio generalmente de grado positivo) debe pues ser multiplicado por el inverso de este elemento de $K$ . En el pseudocódigo que sigue, $p$ es un polinomio de grado mayor que uno, y $a$ es un polinomio.

función inverso(a, p)
t:= 0; newt:= 1
r:= p; newr:= a

 mientras newr ل 0 doquotient:= r div newr
(r, newr):= (newr, r− quotient × newr)
(t, newt):= (newt, t - quotient × newt)

 si grado(r) 0 entonces retorno "O p no es irreducible o un es un múltiplo de p"

 retorno (1/r) × t

Ejemplo

Por ejemplo, si el polinomio utilizado para definir el campo finito GF(2⁸) es p = x⁸ + x⁴ + x³ + x + 1, y a = x⁶ + x⁴ + x + 1 es el elemento cuyo inverso se desea, luego, al realizar el algoritmo, se obtiene el cálculo descrito en la siguiente tabla. Recordemos que en campos de orden 2ⁿ, se tiene -z = z y z + z = 0 para cada elemento z en el campo). Dado que 1 es el único elemento distinto de cero de GF(2), no es necesario el ajuste en la última línea del pseudocódigo.

paso	quotient	r, newr	s, news	t, newt
		p=x⁸ + x⁴ + x³ + x + 1	1	0
		a=x⁶ + x⁴ + x + 1	0	1
1	x² + 1	x² = p - a ()x² + 1)	1	x² + 1 = 0 - 1 ×x² + 1)
2	x⁴ + x²	x + 1 = a - x² ()x⁴ + x²)	x⁴+x² = 0 - 1(x⁴+x²)	x⁶ + x² + 1 = 1 - (x⁴ + x²)x² + 1)
3	x + 1	1 = x² -x + 1)x + 1)	x⁵+x⁴+x³+x²+1 = 1 - (x +1)(x⁴ +²)	x⁷ + x⁶ + x³ + x =x² + 1) - (x + 1)x⁶ + x² + 1)
4	x + 1	0 =x + 1) - 1 ×x + 1)	x⁶ +⁴ + x + 1 = x⁴+x²) - (x+1)(x⁵+x⁴+x³+x²+1)

Por lo tanto, el inverso es x⁷ + x⁶ + x ³ + x, como se puede confirmar multiplicando los dos elementos y tomando el resto por $p$ del resultado.

El caso de más de dos números

Uno puede manejar el caso de más de dos números iterativamente. Primero mostramos que $gcd(a,b,c)=gcd(gcd(a,b),c)$ . Para probar esto $d=gcd(a,b,c)$ . Por definición de gcd $d$ es un divisor de $a$ y $b$ . Así $gcd(a,b)=kd$ para algunos $k$ . Del mismo modo $d$ es un divisor de $c$ Así que... $c=jd$ para algunos $j$ . Vamos $u=gcd(k,j)$ . Por nuestra construcción de $u$ , $ud|a,b,c$ pero $d$ es el mayor divisor $u$ es una unidad. Y desde ${displaystyle ud=gcd(gcd(a,b),c)}$ el resultado está probado.