algoritmo de Euclides estendido

O Algoritmo de Euclides estendido é uma extensão do algoritmo de Euclides, que, além de calcular o máximo divisor comum (MDC) entre fornece os coeficientes tais que O algoritmo é utilizado, em especial, para o cálculo de inverso modular. Se e são coprimos, então é o inverso modular de módulo e é o inverso modular de módulo Essa propriedade é amplamente utilizada no estudo em Criptografia, mais especificamente, no processo de quebra de chaves privadas do método de encriptação RSA.