Exercício 4

Para 09/10

1. Construa um sistema RSA onde p e q são os primos ímpares seguintes aos três últimos dígitos do seu RA. Exemplo: RA 960001, os primos são 3 e 5.

   Basta dar o b, o e e o f para responder à questão.

2. Com quantas multiplicações deve alguém fazer um produto de matrizes 3x3 para bater o método de Strassen assintoticamente?
3. Escreva a recorrência para o número de multiplicações da transformada rápida de Fourier num polinômio de n termos. Explique cada termo e resolva a recorrência assintoticamente.