Botan 3.9.0
Crypto and TLS for C&
barrett.h
Go to the documentation of this file.
1/*
2* (C) 2025 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7#ifndef BOTAN_BARRETT_REDUCTION_H_
8#define BOTAN_BARRETT_REDUCTION_H_
9
10#include <botan/bigint.h>
11
12namespace Botan {
13
14/**
15* Barrett Reduction
16*/
17class BOTAN_TEST_API Barrett_Reduction final {
18 public:
19 /**
20 * Setup for reduction where the modulus itself is public
21 *
22 * Requires that m > 0
23 */
24 static Barrett_Reduction for_public_modulus(const BigInt& m);
25
26 /**
27 * Setup for reduction where the modulus itself is secret.
28 *
29 * This is slower than for_public_modulus since it must avoid using
30 * variable time division.
31 *
32 * Requires that m > 0
33 */
34 static Barrett_Reduction for_secret_modulus(const BigInt& m);
35
36 /**
37 * Perform modular reduction of x
38 *
39 * The parameter must be greater than or equal to zero, and less than 2^(2*b), where
40 * b is the bitlength of the modulus.
41 */
42 BigInt reduce(const BigInt& x) const;
43
44 /**
45 * Multiply mod p
46 * @param x the first operand in [0..p)
47 * @param y the second operand in [0..p)
48 * @return (x * y) % p
49 */
50 BigInt multiply(const BigInt& x, const BigInt& y) const;
51
52 /**
53 * Square mod p
54 * @param x a value to square must be in [0..p)
55 * @return (x * x) % p
56 */
57 BigInt square(const BigInt& x) const;
58
59 /**
60 * Cube mod p
61 * @param x the value to cube
62 * @return (x * x * x) % p
63 *
64 * TODO(Botan4) remove this, last few remaining callers go away in Botan4
65 */
66 BigInt cube(const BigInt& x) const { return this->multiply(x, this->square(x)); }
67
68 /**
69 * Return length of the modulus in bits
70 */
71 size_t modulus_bits() const { return m_modulus_bits; }
72
73 private:
74 Barrett_Reduction(const BigInt& m, BigInt mu, size_t mw);
75
76 BigInt m_modulus;
77 BigInt m_mu;
78 size_t m_mod_words;
79 size_t m_modulus_bits;
80};
81
82} // namespace Botan
83
84#endif
#define BOTAN_TEST_API
Definition api.h:41
static Barrett_Reduction for_public_modulus(const BigInt &m)
Definition barrett.cpp:33
size_t modulus_bits() const
Definition barrett.h:71
BigInt cube(const BigInt &x) const
Definition barrett.h:66
static Barrett_Reduction for_secret_modulus(const BigInt &m)
Definition barrett.cpp:22
BigInt reduce(const BigInt &x) const
Definition barrett.cpp:194
BigInt multiply(const BigInt &x, const BigInt &y) const
Definition barrett.cpp:162
BigInt square(const BigInt &x) const
Definition barrett.cpp:183