Botan  2.4.0
Crypto and TLS for C++11
Public Member Functions | List of all members
Botan::Modular_Reducer Class Reference

#include <reducer.h>

Public Member Functions

BigInt cube (const BigInt &x) const
 
const BigIntget_modulus () const
 
bool initialized () const
 
 Modular_Reducer ()
 
 Modular_Reducer (const BigInt &mod)
 
BigInt multiply (const BigInt &x, const BigInt &y) const
 
BigInt reduce (const BigInt &x) const
 
BigInt square (const BigInt &x) const
 

Detailed Description

Modular Reducer (using Barrett's technique)

Definition at line 18 of file reducer.h.

Constructor & Destructor Documentation

◆ Modular_Reducer() [1/2]

Botan::Modular_Reducer::Modular_Reducer ( )
inline

Definition at line 52 of file reducer.h.

52 { m_mod_words = 0; }

◆ Modular_Reducer() [2/2]

Botan::Modular_Reducer::Modular_Reducer ( const BigInt mod)
explicit

Definition at line 16 of file reducer.cpp.

References Botan::MP_WORD_BITS, Botan::BigInt::power_of_2(), Botan::BigInt::sig_words(), and Botan::square().

17  {
18  if(mod <= 0)
19  throw Invalid_Argument("Modular_Reducer: modulus must be positive");
20 
21  m_modulus = mod;
22  m_mod_words = m_modulus.sig_words();
23 
24  m_modulus_2 = Botan::square(m_modulus);
25 
26  m_mu = BigInt::power_of_2(2 * MP_WORD_BITS * m_mod_words) / m_modulus;
27  }
BigInt square(const BigInt &x)
Definition: mp_numth.cpp:19
static BigInt power_of_2(size_t n)
Definition: bigint.h:499
size_t sig_words() const
Definition: bigint.h:398
const size_t MP_WORD_BITS
Definition: mp_core.h:22

Member Function Documentation

◆ cube()

BigInt Botan::Modular_Reducer::cube ( const BigInt x) const
inline

Cube mod p

Parameters
xthe value to cube
Returns
(x * x * x) % p

Definition at line 47 of file reducer.h.

References Botan::square().

48  { return multiply(x, this->square(x)); }
BigInt square(const BigInt &x) const
Definition: reducer.h:39
BigInt multiply(const BigInt &x, const BigInt &y) const
Definition: reducer.h:31

◆ get_modulus()

const BigInt& Botan::Modular_Reducer::get_modulus ( ) const
inline

Definition at line 21 of file reducer.h.

21 { return m_modulus; }

◆ initialized()

bool Botan::Modular_Reducer::initialized ( ) const
inline

Definition at line 50 of file reducer.h.

Referenced by Botan::Blinder::blind(), and Botan::Blinder::unblind().

50 { return (m_mod_words != 0); }

◆ multiply()

BigInt Botan::Modular_Reducer::multiply ( const BigInt x,
const BigInt y 
) const
inline

Multiply mod p

Parameters
xthe first operand
ythe second operand
Returns
(x * y) % p

Definition at line 31 of file reducer.h.

Referenced by Botan::Blinder::blind(), botan_mp_mod_mul(), Botan::Fixed_Window_Exponentiator::execute(), Botan::ressol(), Botan::Fixed_Window_Exponentiator::set_base(), and Botan::Blinder::unblind().

32  { return reduce(x * y); }
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:32

◆ reduce()

BigInt Botan::Modular_Reducer::reduce ( const BigInt x) const

Definition at line 32 of file reducer.cpp.

References Botan::BigInt::cmp(), Botan::BigInt::is_negative(), Botan::BigInt::is_positive(), Botan::BigInt::mask_bits(), Botan::MP_WORD_BITS, Botan::BigInt::Positive, Botan::BigInt::power_of_2(), and Botan::BigInt::set_sign().

Referenced by Botan::Montgomery_Exponentiator::Montgomery_Exponentiator(), and Botan::Montgomery_Exponentiator::set_base().

33  {
34  if(m_mod_words == 0)
35  throw Invalid_State("Modular_Reducer: Never initalized");
36 
37  if(x.cmp(m_modulus, false) < 0)
38  {
39  if(x.is_negative())
40  return x + m_modulus; // make positive
41  return x;
42  }
43  else if(x.cmp(m_modulus_2, false) < 0)
44  {
45  BigInt t1 = x;
46  t1.set_sign(BigInt::Positive);
47  t1 >>= (MP_WORD_BITS * (m_mod_words - 1));
48  t1 *= m_mu;
49 
50  t1 >>= (MP_WORD_BITS * (m_mod_words + 1));
51  t1 *= m_modulus;
52 
53  t1.mask_bits(MP_WORD_BITS * (m_mod_words + 1));
54 
55  BigInt t2 = x;
56  t2.set_sign(BigInt::Positive);
57  t2.mask_bits(MP_WORD_BITS * (m_mod_words + 1));
58 
59  t2 -= t1;
60 
61  if(t2.is_negative())
62  {
63  t2 += BigInt::power_of_2(MP_WORD_BITS * (m_mod_words + 1));
64  }
65 
66  while(t2 >= m_modulus)
67  t2 -= m_modulus;
68 
69  if(x.is_positive())
70  return t2;
71  else
72  return (m_modulus - t2);
73  }
74  else
75  {
76  // too big, fall back to normal division
77  return (x % m_modulus);
78  }
79  }
void mask_bits(size_t n)
Definition: bigint.h:281
static BigInt power_of_2(size_t n)
Definition: bigint.h:499
const size_t MP_WORD_BITS
Definition: mp_core.h:22

◆ square()

BigInt Botan::Modular_Reducer::square ( const BigInt x) const
inline

Square mod p

Parameters
xthe value to square
Returns
(x * x) % p

Definition at line 39 of file reducer.h.

References Botan::square().

Referenced by Botan::Blinder::blind(), Botan::Fixed_Window_Exponentiator::execute(), Botan::Montgomery_Exponentiator::Montgomery_Exponentiator(), Botan::power_mod(), and Botan::ressol().

40  { return reduce(Botan::square(x)); }
BigInt square(const BigInt &x)
Definition: mp_numth.cpp:19
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:32

The documentation for this class was generated from the following files: