Monóides e o Algoritmo de Exponenciação

Monóides e o Algoritmo de Exponenciação

Lúıs Fernando Schultz Xavier da Silveira

Departamento de Informática e Estat́ıstica - INE - CTC - UFSC

12 de maio de 2010

Monóides e o Algoritmo de Exponenciação

Conteúdo

1 MonóidesDefiniçãoPropriedadesExemplos

2 Produtórios e Exponenciação em MonóidesDefiniçãoPropriedades

3 O Algoritmo de ExponenciaçãoEnunciadoProva de CorretudeAnálise da ComplexidadeImplementação

4 AplicaçõesExponenciação ModularCálculo Eficiente dos Números de Fibonacci

Monóides e o Algoritmo de Exponenciação

Monóides

Definição

Definição

DefiniçãoSeja M um conjunto e · : M →M uma função. Dizemos que (M, ·) é ummonóide se as seguintes propriedades forem satisfeitas:

· é associativa.Existe um elemento 1 ∈M tal que, para todo x ∈M , 1 · x = x · 1 = x.

Monóides e o Algoritmo de Exponenciação

Monóides

Propriedades

Propriedades

Proposição (Unicidade da Unidade)

Seja (M, ·) um monóide e 1, 1′ ∈M tais que, para todo x ∈M ,1 · x = x · 1 = 1′ · x = x · 1′ = x. Então 1 = 1′.

Demonstração.

Temos que 1 · 1′ = 1 e 1 · 1′ = 1′, logo 1 = 1′.

Com isso podemos definir a unidade de um monóide.

Monóides e o Algoritmo de Exponenciação

Monóides

Exemplos

Exemplos

São exemplos de monóides:

(R, ·) onde 1 = 1.(Z, +) onde 1 = 0.

(R2×2, ·), onde 1 =»1 00 1

–.

(Σ∗, ·), onde 1 = ε.(F(A, A), ◦), onde 1(x) = x.(L(A, A), ◦), onde 1(x) = x.(B(A, A), ◦), onde 1(x) = x.(2A,∪), onde 1 = {}.(2A,∩), onde 1 = A.(2A,⊕), onde 1 = {}.

Monóides e o Algoritmo de Exponenciação

Produtórios e Exponenciação em Monóides

Definição

Produtórios e Exponenciação em Monóides

DefiniçãoSeja (M, ·) um monóide e f : Z→M uma função. Definimos indutivamente

bYi=a

f(i) =

8>:1, b < a

f(a) ·

bY

i=a+1

f(i)

!, senão,

onde a, b ∈ Z.

DefiniçãoSeja (M, ·) um monóide, k ∈ N um número natural e x ∈M um elementoqualquer. Definimos

xk =

k−1Yi=0

x.

Monóides e o Algoritmo de Exponenciação

Produtórios e Exponenciação em Monóides

Propriedades

Propriedades dos Produtótios em Monóides

ProposiçãoSeja (M, ·) um monóide, f : Z→M uma função e a, c, b ∈ Z númerosinteiros satisfazendo a 6 c 6 b. Então

c−1Yi=a

f(i)

!·

b−1Yi=c

f(i)

!=

b−1Yi=a

f(i).

Monóides e o Algoritmo de Exponenciação

Produtórios e Exponenciação em Monóides

Propriedades

Propriedades dos Produtótios em Monóides

Demonstração.Por indução em c− a. No caso base a = c, logo

c−1Yi=a

f(i)

!·

b−1Yi=c

f(i)

!=

a−1Yi=a

f(i)

!·

b−1Yi=a

f(i)

!

= 1 ·

b−1Yi=a

f(i)

!

=

b−1Yi=a

f(i).

Monóides e o Algoritmo de Exponenciação

Produtórios e Exponenciação em Monóides

Propriedades

Propriedades dos Produtótios em Monóides

Demonstração.Para o passo indutivo, assuma a < c. Portanto

c−1Yi=a

f(i)

!·

b−1Yi=c

f(i)

!=

f(a) ·

c−1Y

i=a+1

f(i)

!!·

b−1Yi=c

f(i)

!

= f(a) ·

c−1Y

i=a+1

f(i)

!·

b−1Yi=c

f(i)

!!

= f(a) ·

b−1Y

i=a+1

f(i)

!=

b−1Yi=a

f(i).

Monóides e o Algoritmo de Exponenciação

Produtórios e Exponenciação em Monóides

Propriedades

Propriedades da Exponenciação em Monóides

Corolário.Seja (M, ·) um monóide, x ∈M um elemento qualquer e m, n ∈ N númerosnaturais. Então

xm+n = xm · xn.

Demonstração.

xm · xn =

m−1Yi=0

x

!·

n−1Yi=0

x

!=

m−1Yi=0

x

!·

0@(m+n)−1Yi=m

x

1A = (m+n)−1Yi=0

x

= xm+n.

Monóides e o Algoritmo de Exponenciação

Produtórios e Exponenciação em Monóides

Propriedades

Propriedades da Exponenciação em Monóides

ProposiçãoSeja (M, ·) um monóide, x ∈M um elemento qualquer e m, n ∈ N númerosnaturais. Então

(xm)n = xmn.

Demonstração.A prova será por indução em n. Para n = 0 o resultado é trivial.Seja n ∈ N qualquer e assuma que (xm)n = xmn. Então

(xm)(n+1) = (xm)n · (xm)1 = xmn · xm = xmn+m = xm(n+1).

Monóides e o Algoritmo de Exponenciação

Produtórios e Exponenciação em Monóides

Propriedades

Propriedades da Exponenciação em Monóides

Como uma observação final, note que 0x é 1 para todo x. Inclusive, 00 = 1.

Monóides e o Algoritmo de Exponenciação

O Algoritmo de Exponenciação

Enunciado

Enunciado

Seja (M, ·) um monóide, x ∈ M em elemento qualquer e k ∈ N um númeronatural. Considere então o seguinte algoritmo:

exp(x, k)

0 a, n, p← x, k, 11 enquanto n 6= 0 faça2 se n mod 2 = 1 então3 p← p · a4 a← a · a5 n←

¨n2

˝6 retorne p

Monóides e o Algoritmo de Exponenciação

O Algoritmo de Exponenciação

Prova de Corretude

Prova de Corretude

Teorema

O algoritmo anterior corretamente computa o valor xk.

Demonstração.A prova será através da seguinte invariante de loop:

“Sempre que o algoritmo passa pela linha 1, p · an = xk.”

Na primeira vez que ele chega à linha 1, essa invariante é trivialmentesatisfeita, pois p = 1, a = x e n = k em virtude da atribuição na linha 0.

Monóides e o Algoritmo de Exponenciação

O Algoritmo de Exponenciação

Prova de Corretude

Prova de Corretude

Demonstração.Suponha que o algoritmo chegou à linha 1 satisfazendo a invariante. Vamosmostrar que se ele retornar, a invariante ainda continua sendo satisfeita.O algoritmo irá voltar à linha 1 se, e somente se, n 6= 0. Iremos, portanto,assumir este fato.Se ele voltar, os novos valores para a, n e p serão

a′ = a · a, p′ = p · an mod 2, n′ =jn

2

k.

Mas então

p′ · a′n′

= p · an mod 2 · (a · a)bn2 c = p · an mod 2 · (a2)b

n2 c

= p · an mod 2 · a2·bn2 c = p · an mod 2 · an−(n mod 2)

= p · an = xk.

Monóides e o Algoritmo de Exponenciação

O Algoritmo de Exponenciação

Prova de Corretude

Prova de Corretude

Demonstração.

Portanto, ao fim do algoritmo, xk = p · an, mas como n = 0,xk = p · a0 = p · 1 = p. Logo o algoritmo corretamente retorna p = xk.

Monóides e o Algoritmo de Exponenciação

O Algoritmo de Exponenciação

Análise da Complexidade

Análise da Complexidade

Este algoritmo pode ter sua complexidade analisada com o Teorema Mestreatravés da recorrência

T (n) = T“n

2

”+ Θ(1).

Como Θ(1) = Θ(nlog2 1), temos

T ∈ Θ(log n).

Monóides e o Algoritmo de Exponenciação

O Algoritmo de Exponenciação

Implementação

Detalhes de Implementação

Se n estiver representado na base 2, este algoritmo pode ser eficientementeimplementado.Para n escrito em uma base geral b, precisamos adaptar o algoritmo comosegue:

expb(x, k)

0 a, n, p← x, k, 11 enquanto n 6= 0 faça2 p← p · an mod b3 a← ab4 n←

¨nb

˝5 retorne p

A demonstração de que ele funciona e roda em Θ(log n) para todo b fica comoexerćıcio.

Monóides e o Algoritmo de Exponenciação

Aplicações

Exponenciação Modular

Exponenciação Modular

Vários protocolos de criptografia assimétrica precisam computar eficiente-mente o valor de ab mod n para valores n ∈ N \ {0} e a, b ∈ Zn.Observando que (Zn, ·) é um monóide, esse problema pode facilmente serresolvido com o algoritmo que estudamos.

Monóides e o Algoritmo de Exponenciação

Aplicações

Cálculo Eficiente dos Números de Fibonacci

Cálculo Eficiente dos Números de Fibonacci

O n-ésimo número de Fibonacci é definido recursivamente por

fn =

8>:0, n = 0

1, n = 1

fn−2 + fn−1, senão.

Gostaŕıamos de ser capazes de computar eficientemente o n-ésimo númerode Fibonacci fn para um dado n ∈ N.

Monóides e o Algoritmo de Exponenciação

Aplicações

Cálculo Eficiente dos Números de Fibonacci

Cálculo Eficiente dos Números de Fibonacci

Conhecemos um algoritmo capaz de fazer isso, mas ele executa Θ(n) somas.Ainda, o n-ésimo número de Fibonacci tem da ordem de Θ(n) d́ıgitos emqualquer base. Se levarmos isso em conta este algoritmo leva Θ(n2) paraconcluir.Iremos mostrar um algoritmo para calcular o n-ésimo número de Fibonacciusando apenas Θ(log n) somas e multiplicações. Ainda, se considerarmosque uma multiplicação de dois números de n d́ıgitos pode ser executadaem O(n log n log log n), este algoritmo leva apenas O(n log2 n log log n) paraterminar, sendo bastante mais rápido.Mesmo usando o algoritmo de Karatsuba para multiplicar faz com que essealgoritmo rode em O(nlog2 3 log n), o que ainda é bem mais rápido.

Monóides e o Algoritmo de Exponenciação

Aplicações

Cálculo Eficiente dos Números de Fibonacci

Cálculo Eficiente dos Números de Fibonacci

A principal idéia por traz desse algoritmo vem da seguinte igualdade»fn+2fn+1

–=

»1 11 0

– »fn+1fn

–.

Por indução obtém-se »fn+1fn

–=

»1 11 0

–n »f1f0

–.

Mas como (N2×2, ·) é um monóide, segue que podemos calcular»1 11 0

–nrapidamente, usando apenas Θ(log n) vezes a operação do monóide, que éum produto matricial 2× 2 e que portanto pode ser implementado com Θ(1)somas e multiplicações.

Monóides e o Algoritmo de Exponenciação

Aplicações

Cálculo Eficiente dos Números de Fibonacci

Cálculo Eficiente dos Números de Fibonacci

Outra observação interessante é que como f0 = 0, f1 = 1, f2 = 1 e»fk+1fk

–=

»1 11 0

–k »f1f0

–,

»fk+2fk+1

–=

»1 11 0

–k »f2f1

–,

obtém-se que, para k > 1,»1 11 0

–k=

»fk+1 fkfk fk−1

–,

e como os número de Fibonacci são não decrescentes, temos que o maiornúmero que aparece em uma matriz no algoritmo de exponenciação é fn+1,que tem Θ(n) d́ıgitos em qualquer base.SeM(n) é o tempo que um algoritmo de multiplicação leva para multiplicardois inteiros de n d́ıgitos e M é da classe de complexidade de uma funçãoassintoticamente não decrescente, segue que podemos implementar esse al-goritmo em O(M(n) log n).

MonóidesDefiniçãoPropriedadesExemplos

Produtórios e Exponenciação em MonóidesDefiniçãoPropriedades

O Algoritmo de ExponenciaçãoEnunciadoProva de CorretudeAnálise da ComplexidadeImplementação

AplicaçõesExponenciação ModularCálculo Eficiente dos Números de Fibonacci