Mais um blog inútil.

Viva amiquinhos. Hoje venho blogar sobre a multiplicação de Montgomery.

Para que é que serve? Para multiplicar números módulo um inteiro p, sem ter de recorrer a divisões, que são imensamente lentas na maioria dos CPUs. O algoritmo que Montgomery propôs em 1985 é uma generalização de um já conhecido método para multiplicar módulo primos de Mersenne (2^n-1).

Seja P o módulo a usar e R uma potência de 2 superior a P. Em primeiro lugar, convertemos as entradas para a forma de Montgomery: xR mod P. Isto terá de ser feito com métodos convencionais, ou redução de Barrett.
Agora, resolvemos a equação R.R^-1 - P.P' = 1, para P' desconhecido: P' = -P^-1 (mod R). Tendo isto, a redução em si resume-se a:

Mont(x,y)

{

xy = x*y;

y = (xy*P' mod R)*P + xy / R;

return y mod P;
}

Torna-se óbvio porque é que R deve ser uma potência de 2. As divisões desaparecem e são substituídas por And e Shift. Obtemos assim finalmente:

Mont(x,y)

{

xy = x*y;

y = ((xy*P' & (R-1))*P + xy) >> log2(R);

if(y >= P) y = y-p;

return y;

}

Obtemos assim uma multiplicação+redução em apenas 3 multiplicações (pode-se reduzir isto para ~2.6), um shift e uma adição. Mas o resultado não está normalizado; ainda está na forma de Montgomery. Para converter, basta multiplicar o resultado por 1: Mont(xyR, 1) = xyRR^-1 = xy. Devido às pré-computações envolvidas, só compensa usar este método quando é preciso multiplicar repetidamente módulo o mesmo valor (e.g. exponenciação, multiplicação em curvas elípticas, redução de matrizes módulo primos (index calculus), etc).

Em anexo está um exemplo da brincadeira disto a funcionar. Dongs