dancing with my shadow: Explanation of POWMOD pseudocode

The following is a brute-force algorithm for computing B to the power of E mod M, assuming all the input numbers have N digits with base 256.

Explanation:

$B^E = (B^{E[N] \cdot (2^8)^{N-1}}\cdot B^{E[N-1] \cdot (2^8)^{N-2}}\cdot\dots\cdot B^{E[1] \cdot (2^8)^{0}})\\ \text{After ith iteration in the outer loop:}\\ R = (B^{E[i] \cdot (2^8)^{i-1}}\cdot B^{E[i-1] \cdot (2^8)^{i-2}}\cdot\dots\cdot B^{E[1] \cdot (2^8)^{0}}) \mod M\\ X= (B^{(2^8)^i}) \mod M\\ \text{The inner loop basically expands the byte E[i] in to bits.}\\ \text{So after jth iteration in the inner loop during ith iteration in the outer loop:} \\ R = (B^{(E[i][j]\cdot 2^{j-1}+E[i][j-1]\cdot 2^{j-2}+\dots +E[i][1]\cdot 2^{0})(2^8)^{i-1}}\cdot B^{E[i-1] \cdot (2^8)^{i-2}}\cdot\dots\cdot B^{E[1] \cdot (2^8)^{0}}) \mod M\\ X= (B^{2^j(2^8)^{i-1}}) \mod M\\$

dancing with my shadow

Pages

Friday, 28 October 2011

Explanation of POWMOD pseudocode

No comments:

Post a Comment