diff options
Diffstat (limited to 'src/math')
| -rw-r--r-- | src/math/numbertheory/powm_fw.cpp | 35 |
1 files changed, 29 insertions, 6 deletions
diff --git a/src/math/numbertheory/powm_fw.cpp b/src/math/numbertheory/powm_fw.cpp index b764ee7aa..e4272f20d 100644 --- a/src/math/numbertheory/powm_fw.cpp +++ b/src/math/numbertheory/powm_fw.cpp @@ -77,17 +77,40 @@ BigInt Fixed_Window_Exponentiator::execute() const { const u32bit exp_nibbles = (exp.bits() + window_bits - 1) / window_bits; - BigInt x = 1; - for(u32bit j = exp_nibbles; j > 0; --j) + if(exp_nibbles == 0) + return 1; + + BigInt x1 = 1; + + for(u32bit j = 0; j != exp_nibbles / 2; ++j) + { + for(u32bit k = 0; k != window_bits; ++k) + x1 = reducer.square(x1); + + u32bit nibble = exp.get_substring(window_bits*(exp_nibbles-1-j), + window_bits); + + if(nibble) + x1 = reducer.multiply(x1, g[nibble-1]); + } + + for(u32bit k = 0; k != window_bits; ++k) + x1 = reducer.square(x1); + BigInt x2 = 1; + + for(u32bit j = exp_nibbles / 2; j != exp_nibbles; ++j) { for(u32bit k = 0; k != window_bits; ++k) - x = reducer.square(x); + x2 = reducer.square(x2); + + u32bit nibble = exp.get_substring(window_bits*(exp_nibbles-1-j), + window_bits); - u32bit nibble = exp.get_substring(window_bits*(j-1), window_bits); if(nibble) - x = reducer.multiply(x, g[nibble-1]); + x2 = reducer.multiply(x2, g[nibble-1]); } - return x; + + return reducer.multiply(x1, x2); } /* |