Projeto 2012.1

Equipes de no máximo 3 pessoas!

Um problema matemático recorrente em Ciência da Computação é a exponenciação de números muito grandes.

A função expMod(a,b,n), que computa ab mod n, sendo a, b e n números inteiros é usada em algoritmos de criptografia e compactação de dados.

Ocorre que computá-la não é trivial do ponto de vista da complexidade computacional, já que multiplicar sucessivamente a por a b vezes e em seguida computar o resto da divisão dste produto por n consome muitos ciclos de CPU.

A primeira parte do projeto é elaborar uma função exp_mod (int a, int b, int n) em C que calcule ab mod n. Vale 1.0

Felizmente há um algoritmo mais rápido, que computa diretamente ab mod n, como segue abaixo.

int exp_mod(a, b, n)

1. d <- 1

2. Let <bk-1, ..., b0> b2 //binary representation of b

3. for i= k-1 downto 0

4. d <- d2 mod n

5. if bi = 1

6. d <- (d*a) mod n

7. Return d

Por exemplo, para calcular 105103 mod 143.

A segunda parte do projeto é elaborar uma função em assembly que implemente o algoritmo acima. Vale 3.0

A terceira parte é a elaboração de um conjunto de testes que permita comparar o desempenho da função implementada em C e da função implementada em Assembly. Vale 3.0.

A última parte é a elaboração de um relatório descrevendo as funções, detalhes de sua implementação, os experimentos realizados e discutindo os resultados. Leia aqui sobre a estruturação de um texto científico. Vale 3.0.