四兩撥千斤的Montgomery's Algorithm

上班到現在一直在研究RSA的演算法，以軟體程式來說，RSA也許蠻好寫的，但要實現成硬體可就沒那麼簡單囉~因為RSA加密的方法牽扯到次方與模數，這些繁雜的運算要做成硬體，勢必得考慮到成本與效能，在設計上得多加小心，而在數個解決的方法裡，有一個叫做Montgomery’s Algorithm的，它將複雜的模數運算轉變為乘法與幾個簡單的加法，要知道以硬體設計來說，寧可要多幾個加法、乘法器，也不要一個除法器，看到前人想出的方法，此等以簡單的加法與乘法完成複雜的模數運算，衷心的佩服其智慧巧思，希望哪天我也能到達這樣的境界。
柔道講求以柔克鋼，太極可四兩撥千斤，誰說電腦就是硬邦邦的呢~看！這不正也是個四兩撥千斤的實例呀~所以說天地萬物運行自有其法則，只要細心體會，一理通，百理階通，且看古代的不世高人們，皆是精通此道的佼佼者呀~


MM[n]=A*B *2-2n (mod N)

MM(A, B, N)
S[0] = 0;
for (i=0;i qi = (S[i]+aiB) (mod 2);
S[i+1] = (S[i]+ aiB +qiN)/2;
return S[n];