Em matemática , o algoritmo euclidiano estendido é uma variante do algoritmo euclidiano . De dois inteiros a e b , calcula não só a sua maior divisor comum (GCD), mas também um dos seus pares de coeficientes Bézout , ou seja, dois inteiros u e v tais que au + bv = GCD ( a , b ). Quando uma e b são primos entre si , em seguida, o retorno é o inverso para a multiplicação de um módulo b (e v é do mesmo modo o inverso modular de b , módulo um ), o que é um caso particularmente útil. Enquanto o algoritmo de Euclides determina quando uma equação Diofantina ax + by = c tem uma solução, o algoritmo estendido de Euclides também fornece uma solução particular, da qual a solução geral é facilmente deduzida.
Como o algoritmo de Euclides, o algoritmo estendido generaliza para anéis euclidianos, como o de polinômios com uma variável sobre um campo comutativo . Quanto aos inteiros, torna-se possível calcular o inverso de um módulo polinomial um polinômio com o qual é primo e, portanto, cálculos do inverso nos anéis ou campos construídos por quociente no anel dos polinômios: campo de ruptura , corpos finitos etc.
Considere, por exemplo, o cálculo do GCD de 120 e 23 com o algoritmo de Euclides:
| 120 ÷ 23 = 5 resto 5 |
| 23 ÷ 5 = 4 permanecem 3 |
| 5 ÷ 3 = 1 resto 2 |
| 3 ÷ 2 = 1 resto 1 |
| 2 ÷ 1 = 2 resto 0 |
Nesse caso, o restante obtido na penúltima linha dá o GCD igual a 1; ou seja, 120 e 23 são coprime. Agora vamos apresentar as divisões anteriores de forma diferente:
| Descanso | = | Dividendo | - | Quociente | × | Divisor |
| 5 | = | 120 | - | 5 | × | 23 |
| 3 | = | 23 | - | 4 | × | 5 |
| 2 | = | 5 | - | 1 | × | 3 |
| 1 | = | 3 | - | 1 | × | 2 |
| 0 | = | 2 | - | 2 | × | 1 |
Observe que 120 e 23 aparecem nas duas primeiras linhas. Por outro lado, a mais à direita valor em cada linha (a partir do 2 nd linha da tabela) é o resto da linha anterior, e o dividendo é - em cada laço do 3 rd fileira - o restante obtido duas linhas mais alto. Podemos, assim, calcular gradualmente cada resto sucessivo como uma combinação linear dos dois valores iniciais 120 e 23.
No entanto, esse método não é o mais eficiente. Primeiramente, escrevemos esses cálculos para revelar um algoritmo mais direto:
| r | = | você | × | no | + | v | × | b | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 120 | = | 1 | × | 120 | + | 0 | × | 23 | ||||||||||||
| 23 | = | 0 | × | 120 | + | 1 | × | 23 | ||||||||||||
| 5 | = | 120 | - | 5 | × | 23 | = | 1 | × | 120 | + | -5 | × | 23 | ||||||
| 3 | = | 23 | - | 4 | × | 5 | = | 1 × 23 | - | 4 | × | (1 × 120 - 5 × 23) | = | -4 | × | 120 | + | 21 | × | 23 |
| 2 | = | 5 | - | 1 | × | 3 | = | (1 × 120 - 5 × 23) | - | 1 | × | (-4 × 120 + 21 × 23) | = | 5 | × | 120 | + | -26 | × | 23 |
| 1 | = | 3 | - | 1 | × | 2 | = | (-4 × 120 + 21 × 23) | - | 1 | × | (5 × 120 - 26 × 23) | = | -9 | × | 120 | + | 47 | × | 23 |
Observe que a última linha dá 1 = -9 × 120 + 47 × 23, e nos dá exatamente o que queremos: u = -9 ev = 47. Isso significa que -9 é o inverso para a multiplicação de 120 módulo 23, porque 1 = -9 × 120 (mod 23). Da mesma forma, 47 é o inverso, para a multiplicação do módulo 120, de 23.
Temos em roxo os cálculos sucessivos que levam ao mdc pelo restante da divisão dos dois números anteriores (algoritmo euclidiano comum). Os quocientes correspondentes foram anotados em amarelo. As duas colunas verdes dar os cálculos sucessivos que levam aos coeficientes Bézout ( u e v ). Podemos verificar que esses coeficientes são calculados a partir dos dois coeficientes que os precedem na mesma coluna, usando os quocientes da coluna amarela: as fórmulas são especificadas na tabela do parágrafo seguinte.
Apresentamos, em forma de sequência, o cálculo do GCD e dos coeficientes de Bézout para dois números naturais a e b . O quociente (inteiro) de x por y é denotado por x ÷ y . Para um = 120 e b = 23, que vai verificar se os condutores de cálculo para as três colunas de r , u e v do exemplo.
| r | você | v |
|---|---|---|
| r 0 = a | u 0 = 1 | v 0 = 0 |
| r 1 = b | u 1 = 0 | v 1 = 1 |
| ... | ... | ... |
| r i-1 | u i-1 | v i-1 |
| r i | você eu | v eu |
| r i-1 - (r i-1 ÷ r i ) r i | u i-1 - (r i-1 ÷ r i ) u i | v i-1 - (r i-1 ÷ r i ) v i |
| ... | ... | ... |
| r n = mdc (a, b) | u n = u | v n = v |
| 0 | u n + 1 | v n + 1 |
Obtemos assim (cf. “ finitude e exatidão do algoritmo euclidiano simples ”) uma sequência finita ( r i , u i , v i ), recorrente de ordem 2, de índice máximo n + 1, tal que r n +1 = 0 e r n = pgcd ( a , b ). Além disso, em cada etapa, r i = au i + bv i , por indução a partir dos dois termos anteriores (ver tabela). Em particular, mdc ( a , b ) = r n = au n + bv n .
No decorrer da prova, nunca precisamos assumir o teorema de Bézout e, de fato, ele também fornece uma prova desse teorema para dois inteiros naturais e imediatamente o deduzimos para dois inteiros relativos.
A definição por indução da sequência ( r i , u i , v i ) fornece diretamente um algoritmo para calcular os coeficientes de Bézout. O algoritmo calculará a cada etapa dois triplos consecutivos na sequência (duas linhas consecutivas da tabela acima). Por exemplo, obtemos o mdc e os dois coeficientes de Bézout pela seguinte definição recursiva :
eucl(r, u, v, 0, u', v') = (r, u, v) eucl(r, u, v, r', u', v') = eucl(r', u', v', r - (r÷r')*r', u - (r÷r')*u', v - (r÷r')*v') pour r' ≠ 0 euclid(a, b) = eucl(a, 1, 0, b, 0, 1)Temos então euclídeo (a, b) = eucl (a, 1, 0, b, 0, 1) = (pgcd (a, b), u, v) com pgcd (a, b) = a * u + b * v.
De forma aproximadamente equivalente, temos o seguinte algoritmo imperativo, que usa um loop while e uma atribuição simultânea (ou em paralelo) de várias variáveis (o que é possível em algumas linguagens como Python , Ruby , etc.). A atribuição é indicada como ": =".
Entrée : a, b entiers (naturels) Sortie : r entier (naturel) et u, v entiers relatifs tels que r = pgcd(a, b) et r = a*u+b*v Initialisation : (r, u, v, r', u', v') := (a, 1, 0, b, 0, 1) q quotient entier les égalités r = a*u+b*v et r' = a*u'+b*v' sont des invariants de boucle tant que (r' ≠ 0) faire q := r÷r' (r, u, v, r', u', v') := (r', u', v', r - q *r', u - q*u', v - q*v') fait renvoyer (r, u, v)Para linguagens de programação que não possuem tal atribuição simultânea, variáveis auxiliares são introduzidas para manter os valores das outras variáveis durante o cálculo, por exemplo, como segue:
Os cálculos de u i e v i ambos dependem de que r i , mas são independentes uns dos outros. Podemos, portanto, simplificar esse algoritmo calculando apenas ( r i , u i ). Isso é suficiente se estivermos procurando o inverso de a módulo b (caso em que a e b são coprimos). Em qualquer caso, o segundo coeficiente pode então ser calculado diretamente a partir do primeiro.
Cormen et al. em Introdução a Algoritmia oferece uma versão recursiva :
Entrée : a, b entiers (naturels) Sortie : un triplet (d, u, v) où d est le pgcd de a et b, et u, v sont des entiers relatifs avec au + bv = d fonction euclide-étendu(a, b) si b = 0 alors retourner (a, 1, 0) sinon (d', u', v') := euclide-étendu(b, a mod b) retourner (d', v', u' - (a÷b)v')O algoritmo euclidiano estendido tem a mesma estrutura do algoritmo euclidiano: o número de iterações é o mesmo, apenas o número de operações muda a cada iteração.
Para avaliar o número de etapas de iteração, ou seja, o número inteiro anotado n + 1 acima, primeiro assumimos que a ≥ b , de modo que a sequência ( r i ) está diminuindo desde o início. Notamos então que o quociente é, por construção, sempre maior ou igual a 1. Tomando a sequência ( r i ) na ordem inversa, ou seja ( r n + 1 - i ), e substituindo a cada passo o quociente por 1, reconhecemos a sequência de Fibonacci , com a diferença de que se o primeiro termo, r n + 1 - 0 , é de fato 0, o segundo, r n + 1 - 1 , é o GCD de a e b . Observando d = pgcd ( a , b ) e (f i ) a sequência de Fibonacci, obtemos:
r n + 1 - i ≥ d .f ie, portanto (teorema de Lamé):
r 1 = b ≥ d .f n onde o número de iterações do algoritmo é n +1.Este número é efectivamente alcançado para um e b dois números consecutivos da sequência de Fibonacci, ou em múltiplas da mesma: a sequência de Fibonacci sendo a aumentar, o quociente é de facto um em cada passo.
Como f n ~ [(1 + √5) / 2] n (veja o artigo sobre a sequência de Fibonacci ), o número de iterações está, portanto, em log b , exceto para uma constante multiplicativa.
É pouco realista, exceto para lidar apenas com pequenos números, considerar que o custo das operações realizadas a cada iteração, divisão, multiplicação e subtração, é constante. Se assumirmos que isso é linear no tamanho da entrada (em binário), obtemos uma complexidade em O (log² (sup ( a , b ))), ou seja, até uma constante multiplicativa, a de o algoritmo euclidiano comum.
Poderíamos facilmente reduzir o cálculo do mdc e dos coeficientes de Bézout de dois inteiros relativos ao de dois números naturais. O algoritmo indicado, entretanto, se aplica sem nenhuma modificação aos inteiros relativos . Basta notar que, na divisão euclidiana , é então o valor absoluto do resto que é menor que o valor absoluto do divisor, que garante o término do algoritmo . Com efeito, se definem do mesmo modo a partir de dois inteiros relativos a e b da sequência ( r i , u i , v i ), desta vez, é a sequência dos valores absolutos da r i que é estritamente decrescente a partir de a segunda linha. Mostramos de forma idêntica que r n , o termo penúltimo da sequência, é um divisor comum de um e b , múltiplo de qualquer divisor comum de um e b , isto é, um maior (no sentido de divisibilidade) divisor comum de um e b , e portanto o mdc de a e b ou seu oposto. Pelas mesmas razões, os números u n , v n satisfazem a identidade de Bézout.
O anel de inteiros relativos é um anel euclidiano , e essas são as únicas propriedades úteis para o algoritmo euclidiano estendido. Portanto, é generalizado diretamente para anéis euclidianos e é justificado da mesma maneira. Apenas as operações básicas e a divisão mudam . Quanto aos inteiros relativos, não há necessariamente unicidade, e o algoritmo determina um maior divisor comum, os outros são deduzidos dele por multiplicação por uma unidade (1 e -1. Para os inteiros relativos). Quanto aos inteiros, ele pode ser ligeiramente modificado quando o mdc for definido exclusivamente por uma condição adicional, de modo que o resultado verifique esta.
Michel Demazure , Curso de álgebra: primalidade, divisibilidade, códigos [ detalhe das edições ]