Projeto 2014.2

Equipes de no máximo 3 pessoas! 

Atenção! Consultem a formação definitiva das equipes no final da página!

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.

Equipes

Equipes Espontaneas

GLEISSON CARILLO DE SOUZA

VALTER BARBOSA TORQUATO JUNIOR

MICHAEL HELDER PAIXÃO CARDOSO

PEDRO LIMA DE OLIVEIRA

RAVELLY OLIVEIRA DOS SANTOS SALES

FLÁVIO VICTOR SOUZA DE MELO

SILVANO MOREIRA JUNIOR

DENILSON OLIVEIRA MELO

BRUNO NASCIMENTO DE OLIVEIRA

Equipes Compulsórias:

ADRIELE SILVA OLIVEIRA

GABRIEL RAMOS FERNANDES

SAMUEL SANTOS ALVES

YURI BONIFACIO OLIVEIRA