Escrito por rogrp

Algoritmo Extendido de Euclides

El algoritmo de Euclides para el cálculo del MCD se vio en este post, este post trata del proceso extendido de dicho algoritmo, como veremos se le dice extendido ya que el proceso del algoritmo es prácticamente mismo con la diferencia que ahora en cada iteración tomamos cierta información que nos es útil para calcular los coeficientes de Bezout, es decir seguimos el procedimiento para el cálculo del MCD y en ese proceso calculamos los coeficientes de Bezout los cuales son:

MCD(A, B) = A (s) + B (t)

s y t se conocen como coef. de Bezout, y se demuestra que existen con el Teorema de Bezout

Dicho de otra forma queremos encontrar s y t tal que el MCD(A, B) se exprese como combinación lineal de A y B.

Recordando el cálculo del MCD por el alg. de Ecuclides, si tenemos dos números 25 y 11, se generan los siguientes residuos:

Ojo: por conveniencia r1 = 25 y r2 = 11, luego r3, r4, … son los residuos generados

r1 = 25 
r2 = 11
r3 = 3  --> 25 mod 11 = (25) - (11) * 2  |  cociente: 2
r4 = 2  -->  3 mod 2  = (11) - (3)  * 3  |  cociente: 3
r5 = 1  -->  2 mod 1  =  (2) - (1)  * 1  |  cociente: 1
r6 = 0  -->  1 mod 0  =  (1) - (1)  * 1  |  cociente: 1
-------
MCD = 1

Queremos expresar el MCD que es 1 como combinación lineal de 25 y 11. Es decir queremos hallar s y t tal que: 

MCD (25, 11) = 1 = (25) * s + (11) * t

El proceso consiste en ir expresando cada residuo como combinación de 25 y 11, de tal forma cuando lleguemos al residuo r5 (que es 1) lo podremos expresar como comb. lineal de 25 y 11, el proceso es sencillo:
Hagamos las siguientes observaciones:

i) Observamos que el primer residuo (r3) está expresado como combinación lineal de 25 y 11: 

r3 = 3 = (25) - (11) * 2

ii) El segundo residuo (r4) está expresado como combinación lineal de 11 y 3, pero ese 3 (que es r3) se puede expresar como comb. lineal de 25 y 11 (por la observación anterior i):

r4 = (11) - (3) * 3 
   = (11) - ((25) - (11) * 2) * 3
   = (25) * (-3) + (11) * 7

iii) El tercer residuo (r5) es el MCD y está expresado como comb. lineal de 3 y 2. Luego, por la observación i podemos expresar 3 como comb. lineal de 25 y 11 y por la observación ii a 2 como comb. lineal de 25 y 11. Entonces:

r5 = (3) - (2) * 1
   = ((25) - (11) * 2) - ((25) * (-3) + (11) * 7) * 1
   = (25) * 4 + (11) * (-9)

De esta manera obtenemos: 

r5 = 1 = MCD (25, 11) = (25) * 4 + (11) * (-9)

Entonces s = 4 y t = -9 son nuestros coeficientes de Bezout.

Algoritmo

Del ejemplo anterior, tenemos:

r1 = 25 
r2 = 11
r3 = 3  --> (25) - (11) * 2  --> r1 - r2 * 2
r4 = 2  --> (11) - (3)  * 3  --> r2 - r3 * 3
r5 = 1  -->  (2) - (1)  * 1  --> r3 - r2 * 1
r6 = 0  -->  (1) - (1)  * 1  --> r4 - r3 * 1

Podemos generalizar el residuo n-esimo:

{Ecuacion 1:} \\ \\ r_n= r_{n-1} - q \cdot r_{n-2} \\ \\ {Donde:}\\ \\ q = \left \lfloor \frac{ r_{i-2} } { r_{i-1} } \right \rfloor\

Y ahora queremos expresar cada n-esimo residuo como combinación lineal de 25 y 11. Es decir hallar s-esimo y t-esimo tal que:

{Ecuacion 2:} \\ \\ r_n= 25 \cdot s_n + 11 \cdot t_n

Usando la ecuación 2 y ecuación1:

{Por Ecuacion1:} \\ \\ r_n= r_{n-2} - q \cdot r_{n-1} \\ \\ \\ \\ {Por Ecuacion2:} \\ \\ r_n = 25 \cdot s_n + 11 \cdot t_n , \\ \\ r_{n-2} = 25 \cdot s_{n-2} + 11 \cdot t_{n-2} \\ \\ r_{n-3} = 25 \cdot s_{n-1} + 11 \cdot t_{n-1} \\ \\ \\ {Reemplazando:} \\ \\ 25 \cdot s_n + 11 \cdot t_n = 25 \cdot s_{n-2} + 11 \cdot t_{n-2} - q \cdot ( 25 \cdot s_{n-1} + 11 \cdot t_{n-1} ) \\ \\ 25 \cdot s_n + 11 \cdot t_n = 25 \cdot ( s_{n-2} - q \cdot s_{n-1} ) + 11 \cdot (t_{n-2} - q \cdot t{n-1} ) \\ \\ \\ \therefore {Tenemos: } \\ \\ s_n = s_{n-2} - q \cdot s_{n-1} \\ \\ t_n = t_{n-2} - q \cdot t_{n-1} \\ \\ {Donde:}\\ \\ q = \left \lfloor \frac{ r_{i-2} } { r_{i-1} } \right \rfloor, n>3, r_1 = 25, r_2 = 11 .

De esta manera podemos hallar fácilmente s y t para cada n-esimo residuo con las formulas demostradas en el párrafo anterior. Y dado que podemos representar la función piso en C++ como int( ), es decir:

{Funcion Piso: } \\ \\ \left \lfloor x \right \rfloor {= int(x)}

Dicho esto el algoritmo quedaría de la siguiente manera:

#include <iostream>
#include <tuple>

std::tuple<int,int,int> extended_euclidean(int a, int b) {

    int r0 = a>b? a:b;
    int r1 = r0==a? b:a;
    int s0=1, s1=0, t0=0, t1=1;

    while (r1 != 0) {
        int r = r0 % r1;
        int q = int(r0/r1);
        int s = s0 - q * s1;
        int t = t0 - q * t1;

        r0 = r1;
        r1 = r;
        s0 = s1;
        s1 = s;
        t0 = t1;
        t1 = t;
    }

    return std::make_tuple(r0, s0, t0);
}

Probamos nuestra función:

int main() {
    int mcd, s, t;
    int a=4013, b=4057;
    std::tie(mcd, s, t)= extended_euclidean(a,b);
    printf("\t.::Bezout Coeficients::.\n");
    printf("MCD(%d, %d) = %d = %d*(%d) + %d*(%d) \n", a,b,mcd,a,s,b,t);
    return 0;
}

OUTPUT
        .::Bezout Coeficients::.
MCD(4013, 4057) = 1 = 4013*(-456) + 4057*(461)

Advertencia: Este post puede contener errores, si encuentra uno puede colocarlo en los comentarios para contribuir a mejorar esta web.
Puede escribir al autor en rogrp6@gmail.com

¡Gracias por visitar este post!

Un comentario sobre “Algoritmo Extendido de Euclides”

  1. Pingback: Cálculo del Inverso Modular

Deja un comentario