Botan 3.14.1
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 * Currently implemented identically to for_secret_modulus; the
23 * distinction documents the caller's intent
24 *
25 * Requires that m > 0
26 */
27 static Barrett_Reduction for_public_modulus(const BigInt& m);
28
29 /**
30 * Setup for reduction where the modulus itself is secret.
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 /**
74 * Return mu = floor(2^(2*WB*k) / m), where WB is the word size in bits
75 * and k is the number of words in the modulus m
76 */
77 const BigInt& mu() const { return m_mu; }
78
79 private:
80 Barrett_Reduction(const BigInt& m, BigInt mu, size_t mw);
81
82 BigInt m_modulus;
83 BigInt m_mu;
84 size_t m_mod_words;
85 size_t m_modulus_bits;
86};
87
88} // namespace Botan
89
90#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:23
BigInt reduce(const BigInt &x) const
Definition barrett.cpp:178
const BigInt & mu() const
Definition barrett.h:77
BigInt multiply(const BigInt &x, const BigInt &y) const
Definition barrett.cpp:146
BigInt square(const BigInt &x) const
Definition barrett.cpp:167