Algoritmo Euclidiano estendido - Extended Euclidean algorithm

Em aritmética e programação de computador , o algoritmo euclidiano estendido é uma extensão do algoritmo euclidiano e calcula, além do máximo divisor comum (mdc) dos inteiros a e b , também os coeficientes de identidade de Bézout , que são inteiros x e y de tal modo que

Este é um algoritmo de certificação , pois o mdc é o único número que pode satisfazer simultaneamente esta equação e dividir as entradas. Ele permite calcular também, quase sem nenhum custo extra, os quocientes de a e b por seu maior divisor comum.

O algoritmo Euclidiano estendido também se refere a um algoritmo muito semelhante para calcular o maior divisor comum do polinômio e os coeficientes da identidade de Bézout de dois polinômios univariados .

O algoritmo de Euclides estendido é particularmente útil quando um e b são primos entre si . Com esta disposição, x é o inverso multiplicativo modular de um módulo b , e y é o inverso multiplicativo modular de b módulo um . Da mesma forma, o algoritmo euclidiano estendido polinomial permite calcular o inverso multiplicativo em extensões de campos algébricos e, em particular, em campos finitos de ordem não primária. Conclui-se que ambos os algoritmos euclidianos estendidos são amplamente usados ​​em criptografia . Em particular, o cálculo do inverso multiplicativo modular é uma etapa essencial na derivação de pares de chaves no método de criptografia de chave pública RSA .

Descrição

O algoritmo euclidiano padrão procede por uma sucessão de divisões euclidianas cujos quocientes não são usados. Apenas os restos são mantidos. Para o algoritmo estendido, os quocientes sucessivos são usados. Mais precisamente, o algoritmo de Euclides padrão com um e b como entrada, consiste em calcular uma sequência de quocientes e uma sequência de restos de tal modo que

É a propriedade principal da divisão euclidiana que as desigualdades à direita definem exclusivamente e de e

O cálculo pára quando se chega a um resto que é zero; o maior divisor comum é então o último resto diferente de zero

O algoritmo Euclidiano estendido procede de forma semelhante, mas adiciona duas outras sequências, como segue

O cálculo também para quando e dá

  • é o maior divisor comum da entrada e
  • Os coeficientes de Bézout são e isso é
  • Os quocientes de a e b por seu maior divisor comum são dados por e

Além disso, se a e b forem positivos e , então

pois onde denota a parte integral de x , que é o maior inteiro não maior que x .

Isso implica que o par de coeficientes de Bézout fornecido pelo algoritmo Euclidiano estendido é o par mínimo de coeficientes de Bézout, como sendo o par único que satisfaz as duas desigualdades acima.

Também significa que o algoritmo pode ser executado sem estouro de inteiros por um programa de computador usando inteiros de tamanho fixo maior que o de a e b .

Exemplo

A tabela a seguir mostra como o algoritmo Euclidiano estendido procede com a entrada 240 e 46 . O maior divisor comum é a última entrada diferente de zero, 2 na coluna "resto". O cálculo para na linha 6, porque o resto nele é 0 . Os coeficientes de Bézout aparecem nas duas últimas entradas da penúltima linha. Na verdade, é fácil verificar que −9 × 240 + 47 × 46 = 2 . Finalmente, as duas últimas entradas 23 e -120 da última linha são, até o sinal, os quocientes da entrada 46 e 240 pelo maior divisor comum 2 .

índice i quociente q i -1 Restante r i s eu t eu
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

Prova

Como a seqüência de é uma seqüência decrescente de inteiros não negativos (de i = 2 em diante). Portanto, deve parar com algum. Isso prova que o algoritmo para eventualmente.

Como o máximo divisor comum é o mesmo para e Isso mostra que o maior divisor comum da entrada é o mesmo de Isso prova que é o máximo divisor comum de a e b . (Até este ponto, a prova é a mesma do algoritmo euclidiano clássico.)

Como e temos para i = 0 e 1. A relação segue por indução para todos :

Assim e são coeficientes de Bézout.

Considere a matriz

A relação de recorrência pode ser reescrita na forma de matriz

A matriz é a matriz identidade e seu determinante é um. O determinante da matriz mais à direita na fórmula anterior é -1. Segue-se que o determinante de é Em particular, pois temos Vendo isso como uma identidade de Bézout, isso mostra que e são coprimes . A relação que foi provado acima e lema de Euclides mostra que divide b e divide um . Como eles são primos entre si, eles são, até seu sinal os quocientes de b e um por seu maior divisor comum.

Para provar a última afirmação, suponha que um e b são ambos positivos e . Em seguida, e se , pode ser visto que os s e t sequcias de ( a , b ) no âmbito da EEE são, até 0s e 1s iniciais, o t e s sequcias para ( b , a ). As definições mostram então que o caso ( a , b ) se reduz ao caso ( b , a ). Portanto, assuma isso sem perda de generalidade.

Pode-se ver que é 1 e (que existe por ) é um número inteiro negativo. Depois disso, o sinal alternado e estritamente aumenta em magnitude, o que decorre indutivamente das definições e do fato de que para , o caso vale porque . O mesmo é verdade após os primeiros termos, pelo mesmo motivo. Além disso, é fácil ver que (quando um e b são ambos positivos e ). Assim,

Este, acompanhado do fato de serem maiores ou iguais em valor absoluto do que qualquer anterior ou respectivamente concluído na prova.

Algoritmo Euclidiano estendido polinomial

Para polinômios univariados com coeficientes em um campo , tudo funciona de forma semelhante, divisão euclidiana, identidade de Bézout e algoritmo euclidiano estendido. A primeira diferença é que, na divisão euclidiana e no algoritmo, a desigualdade deve ser substituída por uma desigualdade nos graus. Caso contrário, tudo o que precede neste artigo permanece o mesmo, simplesmente substituindo inteiros por polinômios.

Uma segunda diferença reside no limite do tamanho dos coeficientes de Bézout fornecidos pelo algoritmo euclidiano estendido, que é mais preciso no caso polinomial, levando ao teorema a seguir.

Se aeb são dois polinômios diferentes de zero, então o algoritmo Euclidiano estendido produz o par único de polinômios ( s , t ) de modo que

e

Uma terceira diferença é que, no caso polinomial, o máximo divisor comum é definido apenas até a multiplicação por uma constante diferente de zero. Existem várias maneiras de definir inequivocamente um maior divisor comum.

Em matemática, é comum exigir que o máximo divisor comum seja um polinômio mônico . Para conseguir isso, basta dividir cada elemento da saída pelo líder coeficiente de Isto permite que, se um e b são primos entre si, obtém-se 1 no lado direito da desigualdade de Bézout. Caso contrário, pode-se obter qualquer constante diferente de zero. Em álgebra de computador , os polinômios geralmente têm coeficientes inteiros, e essa maneira de normalizar o maior divisor comum introduz muitas frações para ser conveniente.

A segunda maneira de normalizar o máximo divisor comum no caso de polinômios com coeficientes inteiros é dividir cada saída pelo conteúdo de para obter um máximo divisor comum primitivo . Se os polinômios de entrada são coprimos, essa normalização também fornece um maior divisor comum igual a 1. A desvantagem dessa abordagem é que muitas frações devem ser calculadas e simplificadas durante o cálculo.

Uma terceira abordagem consiste em estender o algoritmo de sequências de pseudo-resto subresultantes de uma forma que seja semelhante à extensão do algoritmo euclidiano para o algoritmo euclidiano estendido. Isso permite que, ao iniciar com polinômios com coeficientes inteiros, todos os polinômios que são calculados tenham coeficientes inteiros. Além disso, todo resto computado é um polinômio subresultante . Em particular, se os polinômios de entrada são coprime, então a identidade do Bézout torna-se

onde denota a resultante de a e b . Nessa forma de identidade de Bézout, não há denominador na fórmula. Se dividirmos tudo pela resultante, obteremos a identidade clássica de Bézout, com um denominador comum explícito para os números racionais que aparecem nele.

Pseudo-código

Para implementar o algoritmo descrito acima, deve-se primeiro observar que apenas os dois últimos valores das variáveis ​​indexadas são necessários em cada etapa. Assim, para economizar memória, cada variável indexada deve ser substituída por apenas duas variáveis.

Para simplificar, o algoritmo a seguir (e os outros algoritmos neste artigo) usa atribuições paralelas . Em uma linguagem de programação que não possui esse recurso, as atribuições paralelas precisam ser simuladas com uma variável auxiliar. Por exemplo, o primeiro,

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

é equivalente a

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

e da mesma forma para as outras atribuições paralelas. Isso leva ao seguinte código:

function extended_gcd(a, b)
    (old_r, r) := (a, b)
    (old_s, s) := (1, 0)
    (old_t, t) := (0, 1)
    
    while r ≠ 0 do
        quotient := 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)
    
    output "Bézout coefficients:", (old_s, old_t)
    output "greatest common divisor:", old_r
    output "quotients by the gcd:", (t, s)

Os quocientes de um e b por seu maior divisor comum, que é a saída, pode ter um sinal incorreto. Isso é fácil de corrigir no final do cálculo, mas não foi feito aqui para simplificar o código. Da mesma forma, se a ou b for zero e o outro for negativo, o maior divisor comum que é a saída é negativo e todos os sinais da saída devem ser alterados.

Finalmente, observe que na identidade de Bézout,, pode-se resolver como dado . Assim, uma otimização para o algoritmo acima é calcular apenas a sequência (que produz o coeficiente de Bézout ) e, em seguida, calcular no final:

function extended_gcd(a, b)
    s := 0;    old_s := 1
    r := b;    old_r := a
         
    while r ≠ 0 do
        quotient := old_r div r
        (old_r, r) := (r, old_r − quotient × r)
        (old_s, s) := (s, old_s − quotient × s)
    
    if b ≠ 0 then
        bezout_t := (old_r − old_s × a) div b
    else
        bezout_t := 0
    
    output "Bézout coefficients:", (old_s, bezout_t)
    output "greatest common divisor:", old_r

No entanto, em muitos casos, isso não é realmente uma otimização: enquanto o algoritmo anterior não é suscetível a estouro quando usado com inteiros de máquina (ou seja, inteiros com um limite superior fixo de dígitos), a multiplicação de old_s * a no cálculo de bezout_t pode estourar, limitando essa otimização a entradas que podem ser representadas em menos da metade do tamanho máximo. Ao usar números inteiros de tamanho ilimitado, o tempo necessário para a multiplicação e divisão aumenta quadraticamente com o tamanho dos números inteiros. Isso implica que a "otimização" substitui uma sequência de multiplicações / divisões de pequenos inteiros por uma única multiplicação / divisão, o que requer mais tempo de computação do que as operações que ela substitui, tomadas em conjunto.

Simplificação de frações

Uma fração uma/bestá na forma simplificada canônica se a e b forem coprimos e b for positivo. Esta forma simplificada canônica pode ser obtida substituindo as três linhas de saída do pseudo código anterior por

if s = 0 then output "Division by zero"
if s < 0 then s := −s;  t := −t   (for avoiding negative denominators)
if s = 1 then output -t        (for avoiding denominators equal to 1)
output -t/s

A prova desse algoritmo baseia-se no fato de que s e t são dois inteiros coprime tais como + bt = 0 e, portanto . Para obter a forma simplificada canônica, basta mover o sinal de menos para ter um denominador positivo.

Se b divide a uniformemente, o algoritmo executa apenas uma iteração e temos s = 1 no final do algoritmo. É o único caso em que a saída é um número inteiro.

Calculando inversos multiplicativos em estruturas modulares

O algoritmo euclidiano estendido é a ferramenta essencial para calcular inversos multiplicativos em estruturas modulares, normalmente os inteiros modulares e as extensões de campo algébrico . Um exemplo notável do último caso são os campos finitos de ordem não primária.

Inteiros modulares

Se n é um número inteiro positivo, o anel Z / n Z pode ser identificado com o conjunto {0, 1, ..., n -1} dos restos da divisão euclidiana por n , a adição e a multiplicação consistindo em tomar o resto por n do resultado da adição e da multiplicação de inteiros. Um elemento a de Z / n Z tem um inverso multiplicativo (ou seja, é uma unidade ) se for coprime com n . Em particular, se n for primo , a tem um inverso multiplicativo se não for zero (módulo n ). Assim, Z / n Z é um campo se e somente se n for primo.

A identidade de Bézout afirma que a e n são coprime se e somente se existirem inteiros s e t tais que

Reduzir este módulo de identidade n

Assim , t , ou, mais exatamente, o resto da divisão de t por n , é o inverso multiplicativo de um módulo n .

Para adaptar o algoritmo euclidiano estendido a este problema, deve-se observar que o coeficiente de Bézout de n não é necessário e, portanto, não precisa ser calculado. Além disso, para obter um resultado positivo e inferior a n , pode-se usar o fato de que o inteiro t fornecido pelo algoritmo satisfaz | t | < n . Ou seja, se t <0 , deve-se adicionar n a ele no final. Isso resulta no pseudocódigo, no qual a entrada n é um número inteiro maior que 1.

 function inverse(a, n)
    t := 0;     newt := 1
    r := n;     newr := a

    while newr ≠ 0 do
        quotient := r div newr
        (t, newt) := (newt, t − quotient × newt) 
        (r, newr) := (newr, r − quotient × newr)

    if r > 1 then
        return "a is not invertible"
    if t < 0 then
        t := t + n

    return t

Extensões de campo algébrico simples

O algoritmo euclidiano estendido também é a principal ferramenta para calcular inversos multiplicativos em extensões de campo algébrico simples . Um caso importante, amplamente utilizado na criptografia e na teoria da codificação , é o dos campos finitos de ordem não primária. De fato, se p é um número primo eq = p d , o campo de ordem q é uma extensão algébrica simples do campo primo de p elementos, gerado por uma raiz de um polinômio irredutível de grau d .

Uma extensão algébrica L simples de um campo K , gerada pela raiz de um polinômio irredutível p de grau d pode ser identificada ao anel quociente , e seus elementos estão em correspondência bijetiva com os polinômios de grau menor que d . A adição em L é a adição de polinômios. A multiplicação em L é o resto da divisão euclidiana por p do produto dos polinômios. Assim, para completar a aritmética em L , resta apenas definir como calcular inversos multiplicativos. Isso é feito pelo algoritmo Euclidiano estendido.

O algoritmo é muito semelhante ao fornecido acima para calcular o inverso multiplicativo modular. Existem duas diferenças principais: em primeiro lugar, a última, mas uma linha não é necessária, porque o coeficiente de Bézout que é fornecido sempre tem um grau menor que d . Em segundo lugar, o maior divisor comum que é fornecido, quando os polinômios de entrada são coprimos, pode ser qualquer elemento diferente de zero de K ; este coeficiente Bézout (um polinómio de grau geralmente positivo), portanto, tem de ser multiplicado pelo inverso deste elemento de K . No pseudocódigo que se segue, p é um polinômio de grau maior que um e a é um polinômio.

function inverse(a, p)
    t := 0;     newt := 1
    r := p;     newr := a

    while newr ≠ 0 do
        quotient := r div newr
        (r, newr) := (newr, r − quotient × newr)
        (t, newt) := (newt, t − quotient × newt)

    if degree(r) > 0 then 
        return "Either p is not irreducible or a is a multiple of p"

    return (1/r) × t

Exemplo

Por exemplo, se o polinômio usado para definir o campo finito GF (2 8 ) é p = x 8  +  x 4  +  x 3  +  x  + 1, e a = x 6  +  x 4  +  x  + 1 é o elemento cujo inverso é desejado, então a execução dos resultados do algoritmo no cálculo descrito na tabela a seguir. Vamos lembrar que nos campos de ordem 2 n , tem-se - z = z e z + z = 0 para cada elemento z no campo). Como 1 é o único elemento diferente de zero de GF (2), o ajuste na última linha do pseudocódigo não é necessário.

Passo  quociente  r, newr s, notícias t, salamandra
   p  =  x 8 + x 4 + x 3 + x + 1  1  0
   a  =  x 6 + x 4 + x + 1 0  1
1  x 2 + 1  x 2 = p - a ( x 2 + 1) 1  x 2 + 1 = 0 - 1 × ( x 2 + 1)
2  x 4 + x 2  x + 1 = a - x 2 ( x 4 + x 2 ) x 4 + x 2 = 0 - 1 (x 4 + x 2 )  x 6 + x 2 + 1 = 1 - ( x 4 + x 2 ) ( x 2 + 1)
3  x + 1  1 = x 2 - ( x + 1) ( x + 1) x 5 + x 4 + x 3 + x 2 +1 = 1 - (x +1) (x 4 + x 2 )  x 7 + x 6 + x 3 + x = ( x 2 + 1) - ( x + 1) ( x 6 + x 2 + 1)
4  x + 1  0 = ( x + 1) - 1 × ( x + 1) x 6 + x 4 + x + 1 = (x 4 + x 2 ) - (x + 1) (x 5 + x 4 + x 3 + x 2 +1)  

Assim, o inverso é x 7  +  x 6  +  x 3  +  x , como pode ser confirmado multiplicando os dois elementos juntos , e tomando o resto por p do resultado.

O caso de mais de dois números

Pode-se lidar com o caso de mais de dois números de forma iterativa. Primeiro, mostramos isso . Para provar isso, deixe . Por definição, mdc é um divisor de e . Assim, para alguns . Da mesma forma, é um divisor de so para alguns . Deixe . Pela nossa construção de , mas desde que o maior divisor é uma unidade . E desde que o resultado seja comprovado.

Então, se houver e de modo que a equação final será

Então, para aplicar a n números, usamos indução

com as equações seguintes diretamente.

Veja também

Referências

  • Knuth, Donald . The Art of Computer Programming . Addison-Wesley. Volume 2, Capítulo 4.
  • Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest e Clifford Stein . Introdução aos algoritmos , segunda edição. MIT Press e McGraw-Hill, 2001. ISBN  0-262-03293-7 . Páginas 859-861 da seção 31.2: Máximo divisor comum.

links externos