Botan::Barrett_Reduction Class Reference

#include <barrett.h>

Public Member Functions
BigInt	cube (const BigInt &x) const
size_t	modulus_bits () const
BigInt	multiply (const BigInt &x, const BigInt &y) const
BigInt	reduce (const BigInt &x) const
BigInt	square (const BigInt &x) const

Static Public Member Functions
static Barrett_Reduction	for_public_modulus (const BigInt &m)
static Barrett_Reduction	for_secret_modulus (const BigInt &m)

Detailed Description

Barrett Reduction

Definition at line 17 of file barrett.h.

Member Function Documentation

cube()

BigInt Botan::Barrett_Reduction::cube ( const BigInt & x ) const

inline

Cube mod p

Parameters

x	the value to cube

Returns

(x * x * x) % p

TODO(Botan4) remove this, last few remaining callers go away in Botan4

Definition at line 66 of file barrett.h.

{ return this->multiply(x, this->square(x)); }

for_public_modulus()

Barrett_Reduction Botan::Barrett_Reduction::for_public_modulus ( const BigInt & m )

static

Setup for reduction where the modulus itself is public

Requires that m > 0

Definition at line 33 of file barrett.cpp.

                                                                         {
   BOTAN_ARG_CHECK(!mod.is_zero(), "Modulus cannot be zero");
   BOTAN_ARG_CHECK(!mod.is_negative(), "Modulus cannot be negative");
 
   size_t mod_words = mod.sig_words();
 
   // Compute mu = floor(2^{2k} / m)
   const size_t mu_bits = 2 * WordInfo<word>::bits * mod_words;
   return Barrett_Reduction(mod, BigInt::power_of_2(mu_bits) / mod, mod_words);
}

References BOTAN_ARG_CHECK, for_public_modulus(), Botan::BigInt::is_negative(), Botan::BigInt::is_zero(), Botan::BigInt::power_of_2(), and Botan::BigInt::sig_words().

Referenced by Botan::EC_Group::EC_Group(), for_public_modulus(), Botan::sqrt_modulo_prime(), and Botan::EC_Group::verify_group().

for_secret_modulus()

Barrett_Reduction Botan::Barrett_Reduction::for_secret_modulus ( const BigInt & m )

static

Setup for reduction where the modulus itself is secret.

This is slower than for_public_modulus since it must avoid using variable time division.

Requires that m > 0

Definition at line 22 of file barrett.cpp.

                                                                         {
   BOTAN_ARG_CHECK(!mod.is_zero(), "Modulus cannot be zero");
   BOTAN_ARG_CHECK(!mod.is_negative(), "Modulus cannot be negative");
 
   size_t mod_words = mod.sig_words();
 
   // Compute mu = floor(2^{2k} / m)
   const size_t mu_bits = 2 * WordInfo<word>::bits * mod_words;
   return Barrett_Reduction(mod, ct_divide_pow2k(mu_bits, mod), mod_words);
}

References BOTAN_ARG_CHECK, Botan::ct_divide_pow2k(), for_secret_modulus(), Botan::BigInt::is_negative(), Botan::BigInt::is_zero(), and Botan::BigInt::sig_words().

Referenced by botan_mp_mod_mul(), for_secret_modulus(), Botan::generate_rsa_prime(), Botan::is_prime(), Botan::power_mod(), and Botan::random_prime().

modulus_bits()

size_t Botan::Barrett_Reduction::modulus_bits ( ) const

inline

Return length of the modulus in bits

Definition at line 71 of file barrett.h.

{ return m_modulus_bits; }

Referenced by Botan::EC_Point_Base_Point_Precompute::EC_Point_Base_Point_Precompute().

multiply()

BigInt Botan::Barrett_Reduction::multiply	(	const BigInt &	x,
		const BigInt &	y ) const

Multiply mod p

Parameters

x	the first operand in [0..p)
y	the second operand in [0..p)

Returns

(x * y) % p

Definition at line 162 of file barrett.cpp.

                                                                         {
   BOTAN_ARG_CHECK(acceptable_barrett_input(x, m_modulus).as_bool(), "Invalid x param for Barrett multiply");
   BOTAN_ARG_CHECK(acceptable_barrett_input(y, m_modulus).as_bool(), "Invalid y param for Barrett multiply");
 
   secure_vector<word> ws(2 * (m_mod_words + 2));
   secure_vector<word> xy(2 * m_mod_words);
 
   bigint_mul(xy.data(),
              xy.size(),
              x._data(),
              x.size(),
              std::min(x.size(), m_mod_words),
              y._data(),
              y.size(),
              std::min(y.size(), m_mod_words),
              ws.data(),
              ws.size());
 
   return barrett_reduce(m_mod_words, m_modulus, m_mu, xy, ws);
}

References Botan::BigInt::_data(), Botan::bigint_mul(), BOTAN_ARG_CHECK, multiply(), and Botan::BigInt::size().

Referenced by Botan::is_lucas_probable_prime(), and multiply().

reduce()

BigInt Botan::Barrett_Reduction::reduce

(

const BigInt &

x

)

const

Perform modular reduction of x

The parameter must be greater than or equal to zero, and less than 2^(2*b), where b is the bitlength of the modulus.

Definition at line 194 of file barrett.cpp.

                                                      {
   BOTAN_ARG_CHECK(x.is_positive(), "Argument must be positive");
 
   const size_t x_sw = x.sig_words();
   BOTAN_ARG_CHECK(x_sw <= 2 * m_mod_words, "Argument is too large for Barrett reduction");
 
   x.grow_to(2 * m_mod_words);
 
   secure_vector<word> ws;
   return barrett_reduce(m_mod_words, m_modulus, m_mu, x._as_span(), ws);
}

References Botan::BigInt::_as_span(), BOTAN_ARG_CHECK, Botan::BigInt::grow_to(), Botan::BigInt::is_positive(), reduce(), and Botan::BigInt::sig_words().

Referenced by Botan::is_lucas_probable_prime(), and reduce().

square()

BigInt Botan::Barrett_Reduction::square

(

const BigInt &

x

)

const

Square mod p

Parameters

x	a value to square must be in [0..p)

Returns

(x * x) % p

Definition at line 183 of file barrett.cpp.

                                                      {
   BOTAN_ARG_CHECK(acceptable_barrett_input(x, m_modulus).as_bool(), "Invalid x param for Barrett square");
 
   secure_vector<word> ws(2 * (m_mod_words + 2));
   secure_vector<word> x2(2 * m_mod_words);
 
   bigint_sqr(x2.data(), x2.size(), x._data(), x.size(), std::min(x.size(), m_mod_words), ws.data(), ws.size());
 
   return barrett_reduce(m_mod_words, m_modulus, m_mu, x2, ws);
}

References Botan::BigInt::_data(), Botan::bigint_sqr(), BOTAN_ARG_CHECK, Botan::BigInt::size(), and square().

Referenced by Botan::is_lucas_probable_prime(), Botan::passes_miller_rabin_test(), and square().

---

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

• src/lib/math/numbertheory/barrett.h
• src/lib/math/numbertheory/barrett.cpp