Exponenciação Modular

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