diff options
author | lloyd <[email protected]> | 2012-09-04 14:55:54 +0000 |
---|---|---|
committer | lloyd <[email protected]> | 2012-09-04 14:55:54 +0000 |
commit | 0943effa1b4393d0119f7cb267c1d67279cb2e72 (patch) | |
tree | d1d74d6005abdc168a2dc84338ee80f06f03a07f | |
parent | b72900c62a5c27e588a5512e65ced402bb508871 (diff) |
Avoid conditionals in the power mod ops
-rw-r--r-- | src/math/numbertheory/powm_fw.cpp | 20 | ||||
-rw-r--r-- | src/math/numbertheory/powm_mnt.cpp | 37 |
2 files changed, 35 insertions, 22 deletions
diff --git a/src/math/numbertheory/powm_fw.cpp b/src/math/numbertheory/powm_fw.cpp index 13aeee63b..16a48a5b0 100644 --- a/src/math/numbertheory/powm_fw.cpp +++ b/src/math/numbertheory/powm_fw.cpp @@ -26,10 +26,12 @@ void Fixed_Window_Exponentiator::set_base(const BigInt& base) { window_bits = Power_Mod::window_bits(exp.bits(), base.bits(), hints); - g.resize((1 << window_bits) - 1); - g[0] = base; - for(size_t j = 1; j != g.size(); ++j) - g[j] = reducer.multiply(g[j-1], g[0]); + g.resize((1 << window_bits)); + g[0] = 1; + g[1] = base; + + for(size_t i = 2; i != g.size(); ++i) + g[i] = reducer.multiply(g[i-1], g[0]); } /* @@ -40,13 +42,15 @@ BigInt Fixed_Window_Exponentiator::execute() const const size_t exp_nibbles = (exp.bits() + window_bits - 1) / window_bits; BigInt x = 1; - for(size_t j = exp_nibbles; j > 0; --j) + + for(size_t i = exp_nibbles; i > 0; --i) { - for(size_t k = 0; k != window_bits; ++k) + for(size_t j = 0; j != window_bits; ++j) x = reducer.square(x); - if(u32bit nibble = exp.get_substring(window_bits*(j-1), window_bits)) - x = reducer.multiply(x, g[nibble-1]); + const u32bit nibble = exp.get_substring(window_bits*(i-1), window_bits); + + x = reducer.multiply(x, g[nibble]); } return x; } diff --git a/src/math/numbertheory/powm_mnt.cpp b/src/math/numbertheory/powm_mnt.cpp index 53e75d2b1..a3eac1f83 100644 --- a/src/math/numbertheory/powm_mnt.cpp +++ b/src/math/numbertheory/powm_mnt.cpp @@ -27,12 +27,12 @@ void Montgomery_Exponentiator::set_base(const BigInt& base) { m_window_bits = Power_Mod::window_bits(m_exp.bits(), base.bits(), m_hints); - m_g.resize((1 << m_window_bits) - 1); + m_g.resize((1 << m_window_bits)); BigInt z(BigInt::Positive, 2 * (m_mod_words + 1)); secure_vector<word> workspace(z.size()); - m_g[0] = (base >= m_modulus) ? (base % m_modulus) : base; + m_g[0] = 1; bigint_monty_mul(z.mutable_data(), z.size(), m_g[0].data(), m_g[0].size(), m_g[0].sig_words(), @@ -42,10 +42,20 @@ void Montgomery_Exponentiator::set_base(const BigInt& base) m_g[0] = z; - const BigInt& x = m_g[0]; + m_g[1] = (base >= m_modulus) ? (base % m_modulus) : base; + + bigint_monty_mul(z.mutable_data(), z.size(), + m_g[1].data(), m_g[1].size(), m_g[1].sig_words(), + m_R2_mod.data(), m_R2_mod.size(), m_R2_mod.sig_words(), + m_modulus.data(), m_mod_words, m_mod_prime, + &workspace[0]); + + m_g[1] = z; + + const BigInt& x = m_g[1]; const size_t x_sig = x.sig_words(); - for(size_t i = 1; i != m_g.size(); ++i) + for(size_t i = 2; i != m_g.size(); ++i) { const BigInt& y = m_g[i-1]; const size_t y_sig = y.sig_words(); @@ -86,18 +96,17 @@ BigInt Montgomery_Exponentiator::execute() const x = z; } - if(u32bit nibble = m_exp.get_substring(m_window_bits*(i-1), m_window_bits)) - { - const BigInt& y = m_g[nibble-1]; + const u32bit nibble = m_exp.get_substring(m_window_bits*(i-1), m_window_bits); - bigint_monty_mul(z.mutable_data(), z_size, - x.data(), x.size(), x.sig_words(), - y.data(), y.size(), y.sig_words(), - m_modulus.data(), m_mod_words, m_mod_prime, - &workspace[0]); + const BigInt& y = m_g[nibble]; - x = z; - } + bigint_monty_mul(z.mutable_data(), z_size, + x.data(), x.size(), x.sig_words(), + y.data(), y.size(), y.sig_words(), + m_modulus.data(), m_mod_words, m_mod_prime, + &workspace[0]); + + x = z; } x.grow_to(2*m_mod_words + 1); |