Elias Granja Jr.

Durante o projeto de criptografia do semestre passado, tivemos várias dificuldades para trabalhar com números grandes. Desde a limitação do long(contornamos usando BigInteger no java) a vagarosidade de se trabalhar com exponenciação modular.

Para evitar que x^y crescesse demais a ponto de ficar incalculável, resolvemos multiplicar x mod N, y vezes. Porém ainda assim o algoritmo era lento. No livro de Algoritmos do Sanjoy Dasgupta, Christos Papadimitriou e Umesh Vazirani, temos um exemplo muito mais prático que toma o tempo de O(log² N) que é multiplicar por potências que correspondem aos 1 da representação binária de y. Exemplo:

x^25 = x^11001 = x^16 * x^8 * x^1
Em python:

def exponenciacao(x,y,n):
    if y == 0:
        return 1
    z = exponenciacao(x,y/2,n)
    if y % 2 == 0:
        return (z**2) % n
    else:
        return ( x*z**2 ) % n