El algoritmo de Euclides tiene como función hallar el máximo común divisor de dos números enteros a,b , dando como salida c = m.c.d(a,b).

Paso 1 : Hacer g[0] = a

Paso 2 : Hacer g[1] = b

Paso 3 : Hacer i = 1

Paso 4 : Mientras  g[i] ≠ 0 seguir los pasos 5 y 6

Paso 5 : Hacer g[i+1] = g[i-1] mod g [i]

Paso 6 : Hacer i = i+1

Paso 7 : Salida c = g[i-1]

Paso 8 : Parar

    Con este seudo código podrás implementar el algoritmo en cualquier lenguaje de programación, en el siguiente enlace pongo un ejemplo compilado en pascal.  Euclides zip  (Actualización 19/02/2004)

Cálculo de inversos modulare

    Una vez implementado el algoritmo de Euclides realizaremos un par de modificaciones para que el programa nos calcule el inverso modular de un entero a-1 (mod b).

Entrada: dos enteros a,b relativamente primos.

Salida: Entero c = a-1 (mod b).

    En el siguiente fichero adjunto el seudo código y un programa ejemplo en pascal, este documento fue la primera practica del taller de criptografía de la universidad de la Laguna.  Practica 1 zip (Actualización 19/02/2004)