Botan 2.1.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- Class List
- Class Index
- Class Hierarchy
- Class Members

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 BigInt & | get_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

Botan::Modular_Reducer::Modular_Reducer | ( |  | ) |
| inline

Definition at line 52 of file reducer.h.

52 { m_mod_words = 0; }

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 }
Botan::BigInt::sig_words
size_t sig_words() const
Definition: bigint.h:393
Botan::BigInt::power_of_2
static BigInt power_of_2(size_t n)
Definition: bigint.h:492
Botan::square
BigInt square(const BigInt &x)
Definition: mp_numth.cpp:19
Botan::MP_WORD_BITS
const size_t MP_WORD_BITS
Definition: mp_core.h:21

## Member Function Documentation

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

Cube mod p

Parameters

  x |

Returns
  (x * x * x) % p

Definition at line 47 of file reducer.h.

References Botan::square().

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

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

Definition at line 21 of file reducer.h.

21 { return m_modulus; }

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); }

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

Multiply mod p

Parameters

  x |
  y |

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); }
Botan::Modular_Reducer::reduce
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:32

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 }
Botan::BigInt::Positive
Definition: bigint.h:34
Botan::BigInt::mask_bits
void mask_bits(size_t n)
Definition: bigint.h:276
Botan::BigInt::power_of_2
static BigInt power_of_2(size_t n)
Definition: bigint.h:492
Botan::MP_WORD_BITS
const size_t MP_WORD_BITS
Definition: mp_core.h:21

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

Square mod p

Parameters

  x |

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(), and Botan::ressol().

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

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

- src/lib/math/numbertheory/reducer.h
- src/lib/math/numbertheory/reducer.cpp