/src/botan/src/lib/math/numbertheory/monty.cpp

Source
/*
* (C) 2018,2024,2025 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/internal/monty.h>

#include <botan/internal/barrett.h>
#include <botan/internal/mp_core.h>
#include <array>

namespace Botan {

namespace {

// If the modulus is at most this many words, then use the stack instead
// of a heap variable for some temporary values
constexpr size_t MontgomeryUseStackLimit = 32;

}  // namespace

Montgomery_Params::Data::Data(const BigInt& p, const Barrett_Reduction& mod_p) {
   if(p.is_even() || p < 3) {
      throw Invalid_Argument("Montgomery_Params invalid modulus");
   }

   m_p = p;
   m_p_words = m_p.sig_words();
   m_p_dash = monty_inverse(m_p.word_at(0));

   const BigInt r = BigInt::power_of_2(m_p_words * WordInfo<word>::bits);

   m_r1 = mod_p.reduce(r);
   m_r2 = mod_p.square(m_r1);
   m_r3 = mod_p.multiply(m_r1, m_r2);

   // Barrett should be at least zero prefixing up to modulus size
   BOTAN_ASSERT_NOMSG(m_r1.size() >= m_p_words);
   BOTAN_ASSERT_NOMSG(m_r2.size() >= m_p_words);
   BOTAN_ASSERT_NOMSG(m_r3.size() >= m_p_words);
}

Montgomery_Params::Montgomery_Params(const BigInt& p, const Barrett_Reduction& mod_p) :
      m_data(std::make_shared<Data>(p, mod_p)) {}

Montgomery_Params::Montgomery_Params(const BigInt& p) :
      Montgomery_Params(p, Barrett_Reduction::for_secret_modulus(p)) {}

bool Montgomery_Params::operator==(const Montgomery_Params& other) const {
   if(this->m_data == other.m_data) {
      return true;
   }

   return (this->m_data->p() == other.m_data->p());
}

BigInt Montgomery_Params::redc(const BigInt& x, secure_vector<word>& ws) const {
   const size_t p_size = this->p_words();

   if(ws.size() < p_size) {
      ws.resize(p_size);
   }

   BigInt z = x;
   z.grow_to(2 * p_size);

   bigint_monty_redc_inplace(z.mutable_data(), this->p()._data(), p_size, this->p_dash(), ws.data(), ws.size());

   return z;
}

BigInt Montgomery_Params::mul(const BigInt& x, const BigInt& y, secure_vector<word>& ws) const {
   const size_t p_size = this->p_words();
   BigInt z = BigInt::with_capacity(2 * p_size);
   this->mul(z, x, y, ws);
   return z;
}

void Montgomery_Params::mul(BigInt& z, const BigInt& x, const BigInt& y, secure_vector<word>& ws) const {
   const size_t p_size = this->p_words();

   if(ws.size() < 2 * p_size) {
      ws.resize(2 * p_size);
   }

   BOTAN_DEBUG_ASSERT(x.sig_words() <= p_size);
   BOTAN_DEBUG_ASSERT(y.sig_words() <= p_size);

   if(z.size() < 2 * p_size) {
      z.grow_to(2 * p_size);
   }

   bigint_mul(z.mutable_data(),
              z.size(),
              x._data(),
              x.size(),
              std::min(p_size, x.size()),
              y._data(),
              y.size(),
              std::min(p_size, y.size()),
              ws.data(),
              ws.size());

   bigint_monty_redc_inplace(z.mutable_data(), this->p()._data(), p_size, this->p_dash(), ws.data(), ws.size());
}

void Montgomery_Params::mul(BigInt& z, const BigInt& x, std::span<const word> y, secure_vector<word>& ws) const {
   const size_t p_size = this->p_words();

   if(ws.size() < 2 * p_size) {
      ws.resize(2 * p_size);
   }
   if(z.size() < 2 * p_size) {
      z.grow_to(2 * p_size);
   }

   BOTAN_DEBUG_ASSERT(x.sig_words() <= p_size);

   bigint_mul(z.mutable_data(),
              z.size(),
              x._data(),
              x.size(),
              std::min(p_size, x.size()),
              y.data(),
              y.size(),
              std::min(p_size, y.size()),
              ws.data(),
              ws.size());

   bigint_monty_redc_inplace(z.mutable_data(), this->p()._data(), p_size, this->p_dash(), ws.data(), ws.size());
}

void Montgomery_Params::mul_by(BigInt& x, const BigInt& y, secure_vector<word>& ws) const {
   const size_t p_size = this->p_words();

   if(ws.size() < 4 * p_size) {
      ws.resize(4 * p_size);
   }

   word* z_data = ws.data();
   word* ws_data = &ws[2 * p_size];

   BOTAN_DEBUG_ASSERT(x.sig_words() <= p_size);

   bigint_mul(z_data,
              2 * p_size,
              x._data(),
              x.size(),
              std::min(p_size, x.size()),
              y._data(),
              y.size(),
              std::min(p_size, y.size()),
              ws_data,
              2 * p_size);

   bigint_monty_redc_inplace(z_data, this->p()._data(), p_size, this->p_dash(), ws_data, 2 * p_size);

   if(x.size() < 2 * p_size) {
      x.grow_to(2 * p_size);
   }
   copy_mem(x.mutable_data(), z_data, 2 * p_size);
}

BigInt Montgomery_Params::sqr(const BigInt& x, secure_vector<word>& ws) const {
   BOTAN_DEBUG_ASSERT(x.sig_words() <= this->p_words());
   return this->sqr(std::span{x._data(), x.size()}, ws);
}

BigInt Montgomery_Params::sqr(std::span<const word> x, secure_vector<word>& ws) const {
   const size_t p_size = this->p_words();
   BigInt z = BigInt::with_capacity(2 * p_size);
   this->sqr(z, x, ws);
   return z;
}

void Montgomery_Params::sqr(BigInt& z, const BigInt& x, secure_vector<word>& ws) const {
   this->sqr(z, std::span{x._data(), x.size()}, ws);
}

void Montgomery_Params::sqr(BigInt& z, std::span<const word> x, secure_vector<word>& ws) const {
   const size_t p_size = this->p_words();

   if(ws.size() < 2 * p_size) {
      ws.resize(2 * p_size);
   }

   if(z.size() < 2 * p_size) {
      z.grow_to(2 * p_size);
   }

   bigint_sqr(z.mutable_data(), z.size(), x.data(), x.size(), std::min(p_size, x.size()), ws.data(), ws.size());

   bigint_monty_redc_inplace(z.mutable_data(), this->p()._data(), p_size, this->p_dash(), ws.data(), ws.size());
}

Montgomery_Int::Montgomery_Int(const Montgomery_Params& params, secure_vector<word> words) :
      m_params(params), m_v(std::move(words)) {
   BOTAN_ASSERT_NOMSG(m_v.size() == m_params.p_words());
}

Montgomery_Int Montgomery_Int::one(const Montgomery_Params& params) {
   return Montgomery_Int(params, params.R1(), false);
}

Montgomery_Int Montgomery_Int::from_wide_int(const Montgomery_Params& params, const BigInt& x) {
   secure_vector<word> ws;
   auto redc_x = params.mul(params.redc(x, ws), params.R3(), ws);
   return Montgomery_Int(params, redc_x, false);
}

Montgomery_Int::Montgomery_Int(const Montgomery_Params& params, const BigInt& v, bool redc_needed) :
      m_params(params), m_v(m_params.p_words()) {
   BOTAN_ASSERT_NOMSG(v < m_params.p());

   const size_t p_size = m_params.p_words();

   auto v_span = v._as_span();

   if(v_span.size() > p_size) {
      // Safe to truncate the span since we already checked v < p
      v_span = v_span.first(p_size);
   }

   BOTAN_ASSERT_NOMSG(m_v.size() >= v_span.size());

   copy_mem(std::span{m_v}.first(v_span.size()), v_span);

   if(redc_needed) {
      secure_vector<word> ws;
      this->mul_by(m_params.R2()._as_span().first(p_size), ws);
   }
}

Montgomery_Int::Montgomery_Int(const Montgomery_Params& params, std::span<const word> words) :
      m_params(params), m_v(words.begin(), words.end()) {
   BOTAN_ARG_CHECK(m_v.size() == m_params.p_words(), "Invalid input span");
}

std::vector<uint8_t> Montgomery_Int::serialize() const {
   return value().serialize();
}

BigInt Montgomery_Int::value() const {
   secure_vector<word> ws(m_params.p_words());

   secure_vector<word> z = m_v;
   z.resize(2 * m_params.p_words());  // zero extend

   bigint_monty_redc_inplace(
      z.data(), m_params.p()._data(), m_params.p_words(), m_params.p_dash(), ws.data(), ws.size());

   return BigInt::_from_words(z);
}

Montgomery_Int Montgomery_Int::operator+(const Montgomery_Int& other) const {
   BOTAN_STATE_CHECK(other.m_params == m_params);

   const size_t p_size = m_params.p_words();
   BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.m_v.size() == p_size);

   secure_vector<word> z(2 * p_size);

   word* r = std::span{z}.first(p_size).data();
   word* t = std::span{z}.last(p_size).data();

   // t = this + other
   const word carry = bigint_add3(t, m_v.data(), p_size, other.m_v.data(), p_size);

   // Conditionally subtract r = t - p
   bigint_monty_maybe_sub(p_size, r, carry, t, m_params.p()._data());

   z.resize(p_size);  // truncate leaving only r
   return Montgomery_Int(m_params, std::move(z));
}

Montgomery_Int Montgomery_Int::operator-(const Montgomery_Int& other) const {
   BOTAN_STATE_CHECK(other.m_params == m_params);

   const size_t p_size = m_params.p_words();
   BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.m_v.size() == p_size);

   secure_vector<word> t(p_size);
   const word borrow = bigint_sub3(t.data(), m_v.data(), p_size, other.m_v.data(), p_size);

   bigint_cnd_add(borrow, t.data(), m_params.p()._data(), p_size);

   return Montgomery_Int(m_params, std::move(t));
}

Montgomery_Int Montgomery_Int::mul(const Montgomery_Int& other, secure_vector<word>& ws) const {
   BOTAN_STATE_CHECK(other.m_params == m_params);

   const size_t p_size = m_params.p_words();
   BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.m_v.size() == p_size);

   if(ws.size() < 2 * p_size) {
      ws.resize(2 * p_size);
   }

   secure_vector<word> z(2 * p_size);

   bigint_mul(z.data(), z.size(), m_v.data(), p_size, p_size, other.m_v.data(), p_size, p_size, ws.data(), ws.size());

   bigint_monty_redc_inplace(z.data(), m_params.p()._data(), p_size, m_params.p_dash(), ws.data(), ws.size());
   z.resize(p_size);  // truncate off high zero words

   return Montgomery_Int(m_params, std::move(z));
}

Montgomery_Int& Montgomery_Int::mul_by(const Montgomery_Int& other, secure_vector<word>& ws) {
   BOTAN_STATE_CHECK(other.m_params == m_params);
   return this->mul_by(std::span{other.m_v}, ws);
}

Montgomery_Int& Montgomery_Int::mul_by(std::span<const word> other, secure_vector<word>& ws) {
   const size_t p_size = m_params.p_words();
   BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.size() == p_size);

   if(ws.size() < 2 * p_size) {
      ws.resize(2 * p_size);
   }

   auto do_mul_by = [&](std::span<word> z) {
      bigint_mul(z.data(), z.size(), m_v.data(), p_size, p_size, other.data(), p_size, p_size, ws.data(), ws.size());

      bigint_monty_redc_inplace(z.data(), m_params.p()._data(), p_size, m_params.p_dash(), ws.data(), ws.size());

      copy_mem(m_v, z.first(p_size));
   };

   if(p_size <= MontgomeryUseStackLimit) {
      std::array<word, 2 * MontgomeryUseStackLimit> z{};
      do_mul_by(z);
   } else {
      secure_vector<word> z(2 * p_size);
      do_mul_by(z);
   }

   return (*this);
}

Montgomery_Int& Montgomery_Int::square_this_n_times(secure_vector<word>& ws, size_t n) {
   const size_t p_size = m_params.p_words();
   BOTAN_ASSERT_NOMSG(m_v.size() == p_size);

   if(ws.size() < 2 * p_size) {
      ws.resize(2 * p_size);
   }

   auto do_sqr_n = [&](std::span<word> z) {
      for(size_t i = 0; i != n; ++i) {
         bigint_sqr(z.data(), 2 * p_size, m_v.data(), p_size, p_size, ws.data(), ws.size());

         bigint_monty_redc_inplace(z.data(), m_params.p()._data(), p_size, m_params.p_dash(), ws.data(), ws.size());

         copy_mem(m_v, std::span{z}.first(p_size));
      }
   };

   if(p_size <= MontgomeryUseStackLimit) {
      std::array<word, 2 * MontgomeryUseStackLimit> z{};
      do_sqr_n(z);
   } else {
      secure_vector<word> z(2 * p_size);
      do_sqr_n(z);
   }

   return (*this);
}

Montgomery_Int Montgomery_Int::square(secure_vector<word>& ws) const {
   auto z = (*this);
   z.square_this_n_times(ws, 1);
   return z;
}

}  // namespace Botan

Coverage Report

Created: 2026-10-28 06:31

Line	Count	Source
1		/*
2		* (C) 2018,2024,2025 Jack Lloyd
3		*
4		* Botan is released under the Simplified BSD License (see license.txt)
5		*/
6
7		#include <botan/internal/monty.h>
8
9		#include <botan/internal/barrett.h>
10		#include <botan/internal/mp_core.h>
11		#include <array>
12
13		namespace Botan {
14
15		namespace {
16
17		// If the modulus is at most this many words, then use the stack instead
18		// of a heap variable for some temporary values
19		constexpr size_t MontgomeryUseStackLimit = 32;
20
21		} // namespace
22
23	454	Montgomery_Params::Data::Data(const BigInt& p, const Barrett_Reduction& mod_p) {
24	454	if(p.is_even() \|\| p < 3) {
25	0	throw Invalid_Argument("Montgomery_Params invalid modulus");
26	0	}
27
28	454	m_p = p;
29	454	m_p_words = m_p.sig_words();
30	454	m_p_dash = monty_inverse(m_p.word_at(0));
31
32	454	const BigInt r = BigInt::power_of_2(m_p_words * WordInfo<word>::bits);
33
34	454	m_r1 = mod_p.reduce(r);
35	454	m_r2 = mod_p.square(m_r1);
36	454	m_r3 = mod_p.multiply(m_r1, m_r2);
37
38		// Barrett should be at least zero prefixing up to modulus size
39	454	BOTAN_ASSERT_NOMSG(m_r1.size() >= m_p_words);
40	454	BOTAN_ASSERT_NOMSG(m_r2.size() >= m_p_words);
41	454	BOTAN_ASSERT_NOMSG(m_r3.size() >= m_p_words);
42	454	}
43
44		Montgomery_Params::Montgomery_Params(const BigInt& p, const Barrett_Reduction& mod_p) :
45	454	m_data(std::make_shared<Data>(p, mod_p)) {}
46
47		Montgomery_Params::Montgomery_Params(const BigInt& p) :
48	28	Montgomery_Params(p, Barrett_Reduction::for_secret_modulus(p)) {}
49
50	174k	bool Montgomery_Params::operator==(const Montgomery_Params& other) const {
51	174k	if(this->m_data == other.m_data) {
52	174k	return true;
53	174k	}
54
55	0	return (this->m_data->p() == other.m_data->p());
56	174k	}
57
58	6.34k	BigInt Montgomery_Params::redc(const BigInt& x, secure_vector<word>& ws) const {
59	6.34k	const size_t p_size = this->p_words();
60
61	6.34k	if(ws.size() < p_size) {
62	3.17k	ws.resize(p_size);
63	3.17k	}
64
65	6.34k	BigInt z = x;
66	6.34k	z.grow_to(2 * p_size);
67
68	6.34k	bigint_monty_redc_inplace(z.mutable_data(), this->p()._data(), p_size, this->p_dash(), ws.data(), ws.size());
69
70	6.34k	return z;
71	6.34k	}
72
73	32.5k	BigInt Montgomery_Params::mul(const BigInt& x, const BigInt& y, secure_vector<word>& ws) const {
74	32.5k	const size_t p_size = this->p_words();
75	32.5k	BigInt z = BigInt::with_capacity(2 * p_size);
76	32.5k	this->mul(z, x, y, ws);
77	32.5k	return z;
78	32.5k	}
79
80	430k	void Montgomery_Params::mul(BigInt& z, const BigInt& x, const BigInt& y, secure_vector<word>& ws) const {
81	430k	const size_t p_size = this->p_words();
82
83	430k	if(ws.size() < 2 * p_size) {
84	1.63k	ws.resize(2 * p_size);
85	1.63k	}
86
87	430k	BOTAN_DEBUG_ASSERT(x.sig_words() <= p_size);
88	430k	BOTAN_DEBUG_ASSERT(y.sig_words() <= p_size);
89
90	430k	if(z.size() < 2 * p_size) {
91	6.91k	z.grow_to(2 * p_size);
92	6.91k	}
93
94	430k	bigint_mul(z.mutable_data(),
95	430k	z.size(),
96	430k	x._data(),
97	430k	x.size(),
98	430k	std::min(p_size, x.size()),
99	430k	y._data(),
100	430k	y.size(),
101	430k	std::min(p_size, y.size()),
102	430k	ws.data(),
103	430k	ws.size());
104
105	430k	bigint_monty_redc_inplace(z.mutable_data(), this->p()._data(), p_size, this->p_dash(), ws.data(), ws.size());
106	430k	}
107
108	109k	void Montgomery_Params::mul(BigInt& z, const BigInt& x, std::span<const word> y, secure_vector<word>& ws) const {
109	109k	const size_t p_size = this->p_words();
110
111	109k	if(ws.size() < 2 * p_size) {
112	0	ws.resize(2 * p_size);
113	0	}
114	109k	if(z.size() < 2 * p_size) {
115	0	z.grow_to(2 * p_size);
116	0	}
117
118	109k	BOTAN_DEBUG_ASSERT(x.sig_words() <= p_size);
119
120	109k	bigint_mul(z.mutable_data(),
121	109k	z.size(),
122	109k	x._data(),
123	109k	x.size(),
124	109k	std::min(p_size, x.size()),
125	109k	y.data(),
126	109k	y.size(),
127	109k	std::min(p_size, y.size()),
128	109k	ws.data(),
129	109k	ws.size());
130
131	109k	bigint_monty_redc_inplace(z.mutable_data(), this->p()._data(), p_size, this->p_dash(), ws.data(), ws.size());
132	109k	}
133
134	16.5k	void Montgomery_Params::mul_by(BigInt& x, const BigInt& y, secure_vector<word>& ws) const {
135	16.5k	const size_t p_size = this->p_words();
136
137	16.5k	if(ws.size() < 4 * p_size) {
138	8.28k	ws.resize(4 * p_size);
139	8.28k	}
140
141	16.5k	word* z_data = ws.data();
142	16.5k	word* ws_data = &ws[2 * p_size];
143
144	16.5k	BOTAN_DEBUG_ASSERT(x.sig_words() <= p_size);
145
146	16.5k	bigint_mul(z_data,
147	16.5k	2 * p_size,
148	16.5k	x._data(),
149	16.5k	x.size(),
150	16.5k	std::min(p_size, x.size()),
151	16.5k	y._data(),
152	16.5k	y.size(),
153	16.5k	std::min(p_size, y.size()),
154	16.5k	ws_data,
155	16.5k	2 * p_size);
156
157	16.5k	bigint_monty_redc_inplace(z_data, this->p()._data(), p_size, this->p_dash(), ws_data, 2 * p_size);
158
159	16.5k	if(x.size() < 2 * p_size) {
160	4.24k	x.grow_to(2 * p_size);
161	4.24k	}
162	16.5k	copy_mem(x.mutable_data(), z_data, 2 * p_size);
163	16.5k	}
164
165	7.22k	BigInt Montgomery_Params::sqr(const BigInt& x, secure_vector<word>& ws) const {
166	7.22k	BOTAN_DEBUG_ASSERT(x.sig_words() <= this->p_words());
167	7.22k	return this->sqr(std::span{x._data(), x.size()}, ws);
168	7.22k	}
169
170	7.22k	BigInt Montgomery_Params::sqr(std::span<const word> x, secure_vector<word>& ws) const {
171	7.22k	const size_t p_size = this->p_words();
172	7.22k	BigInt z = BigInt::with_capacity(2 * p_size);
173	7.22k	this->sqr(z, x, ws);
174	7.22k	return z;
175	7.22k	}
176
177	260k	void Montgomery_Params::sqr(BigInt& z, const BigInt& x, secure_vector<word>& ws) const {
178	260k	this->sqr(z, std::span{x._data(), x.size()}, ws);
179	260k	}
180
181	278k	void Montgomery_Params::sqr(BigInt& z, std::span<const word> x, secure_vector<word>& ws) const {
182	278k	const size_t p_size = this->p_words();
183
184	278k	if(ws.size() < 2 * p_size) {
185	1.67k	ws.resize(2 * p_size);
186	1.67k	}
187
188	278k	if(z.size() < 2 * p_size) {
189	5.90k	z.grow_to(2 * p_size);
190	5.90k	}
191
192	278k	bigint_sqr(z.mutable_data(), z.size(), x.data(), x.size(), std::min(p_size, x.size()), ws.data(), ws.size());
193
194	278k	bigint_monty_redc_inplace(z.mutable_data(), this->p()._data(), p_size, this->p_dash(), ws.data(), ws.size());
195	278k	}
196
197		Montgomery_Int::Montgomery_Int(const Montgomery_Params& params, secure_vector<word> words) :
198	174k	m_params(params), m_v(std::move(words)) {
199	174k	BOTAN_ASSERT_NOMSG(m_v.size() == m_params.p_words());
200	174k	}
201
202	12.4k	Montgomery_Int Montgomery_Int::one(const Montgomery_Params& params) {
203	12.4k	return Montgomery_Int(params, params.R1(), false);
204	12.4k	}
205
206	0	Montgomery_Int Montgomery_Int::from_wide_int(const Montgomery_Params& params, const BigInt& x) {
207	0	secure_vector<word> ws;
208	0	auto redc_x = params.mul(params.redc(x, ws), params.R3(), ws);
209	0	return Montgomery_Int(params, redc_x, false);
210	0	}
211
212		Montgomery_Int::Montgomery_Int(const Montgomery_Params& params, const BigInt& v, bool redc_needed) :
213	24.9k	m_params(params), m_v(m_params.p_words()) {
214	24.9k	BOTAN_ASSERT_NOMSG(v < m_params.p());
215
216	24.9k	const size_t p_size = m_params.p_words();
217
218	24.9k	auto v_span = v._as_span();
219
220	24.9k	if(v_span.size() > p_size) {
221		// Safe to truncate the span since we already checked v < p
222	24.9k	v_span = v_span.first(p_size);
223	24.9k	}
224
225	24.9k	BOTAN_ASSERT_NOMSG(m_v.size() >= v_span.size());
226
227	24.9k	copy_mem(std::span{m_v}.first(v_span.size()), v_span);
228
229	24.9k	if(redc_needed) {
230	12.4k	secure_vector<word> ws;
231	12.4k	this->mul_by(m_params.R2()._as_span().first(p_size), ws);
232	12.4k	}
233	24.9k	}
234
235		Montgomery_Int::Montgomery_Int(const Montgomery_Params& params, std::span<const word> words) :
236	12.4k	m_params(params), m_v(words.begin(), words.end()) {
237	12.4k	BOTAN_ARG_CHECK(m_v.size() == m_params.p_words(), "Invalid input span");
238	12.4k	}
239
240	0	std::vector<uint8_t> Montgomery_Int::serialize() const {
241	0	return value().serialize();
242	0	}
243
244	12.4k	BigInt Montgomery_Int::value() const {
245	12.4k	secure_vector<word> ws(m_params.p_words());
246
247	12.4k	secure_vector<word> z = m_v;
248	12.4k	z.resize(2 * m_params.p_words()); // zero extend
249
250	12.4k	bigint_monty_redc_inplace(
251	12.4k	z.data(), m_params.p()._data(), m_params.p_words(), m_params.p_dash(), ws.data(), ws.size());
252
253	12.4k	return BigInt::_from_words(z);
254	12.4k	}
255
256	0	Montgomery_Int Montgomery_Int::operator+(const Montgomery_Int& other) const {
257	0	BOTAN_STATE_CHECK(other.m_params == m_params);
258
259	0	const size_t p_size = m_params.p_words();
260	0	BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.m_v.size() == p_size);
261
262	0	secure_vector<word> z(2 * p_size);
263
264	0	word* r = std::span{z}.first(p_size).data();
265	0	word* t = std::span{z}.last(p_size).data();
266
267		// t = this + other
268	0	const word carry = bigint_add3(t, m_v.data(), p_size, other.m_v.data(), p_size);
269
270		// Conditionally subtract r = t - p
271	0	bigint_monty_maybe_sub(p_size, r, carry, t, m_params.p()._data());
272
273	0	z.resize(p_size); // truncate leaving only r
274	0	return Montgomery_Int(m_params, std::move(z));
275	0	}
276
277	0	Montgomery_Int Montgomery_Int::operator-(const Montgomery_Int& other) const {
278	0	BOTAN_STATE_CHECK(other.m_params == m_params);
279
280	0	const size_t p_size = m_params.p_words();
281	0	BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.m_v.size() == p_size);
282
283	0	secure_vector<word> t(p_size);
284	0	const word borrow = bigint_sub3(t.data(), m_v.data(), p_size, other.m_v.data(), p_size);
285
286	0	bigint_cnd_add(borrow, t.data(), m_params.p()._data(), p_size);
287
288	0	return Montgomery_Int(m_params, std::move(t));
289	0	}
290
291	174k	Montgomery_Int Montgomery_Int::mul(const Montgomery_Int& other, secure_vector<word>& ws) const {
292	174k	BOTAN_STATE_CHECK(other.m_params == m_params);
293
294	174k	const size_t p_size = m_params.p_words();
295	174k	BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.m_v.size() == p_size);
296
297	174k	if(ws.size() < 2 * p_size) {
298	0	ws.resize(2 * p_size);
299	0	}
300
301	174k	secure_vector<word> z(2 * p_size);
302
303	174k	bigint_mul(z.data(), z.size(), m_v.data(), p_size, p_size, other.m_v.data(), p_size, p_size, ws.data(), ws.size());
304
305	174k	bigint_monty_redc_inplace(z.data(), m_params.p()._data(), p_size, m_params.p_dash(), ws.data(), ws.size());
306	174k	z.resize(p_size); // truncate off high zero words
307
308	174k	return Montgomery_Int(m_params, std::move(z));
309	174k	}
310
311	0	Montgomery_Int& Montgomery_Int::mul_by(const Montgomery_Int& other, secure_vector<word>& ws) {
312	0	BOTAN_STATE_CHECK(other.m_params == m_params);
313	0	return this->mul_by(std::span{other.m_v}, ws);
314	0	}
315
316	363k	Montgomery_Int& Montgomery_Int::mul_by(std::span<const word> other, secure_vector<word>& ws) {
317	363k	const size_t p_size = m_params.p_words();
318	363k	BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.size() == p_size);
319
320	363k	if(ws.size() < 2 * p_size) {
321	12.4k	ws.resize(2 * p_size);
322	12.4k	}
323
324	363k	auto do_mul_by = [&](std::span<word> z) {
325	363k	bigint_mul(z.data(), z.size(), m_v.data(), p_size, p_size, other.data(), p_size, p_size, ws.data(), ws.size());
326
327	363k	bigint_monty_redc_inplace(z.data(), m_params.p()._data(), p_size, m_params.p_dash(), ws.data(), ws.size());
328
329	363k	copy_mem(m_v, z.first(p_size));
330	363k	};
331
332	363k	if(p_size <= MontgomeryUseStackLimit) {
333	363k	std::array<word, 2 * MontgomeryUseStackLimit> z{};
334	363k	do_mul_by(z);
335	363k	} else {
336	0	secure_vector<word> z(2 * p_size);
337	0	do_mul_by(z);
338	0	}
339
340	363k	return (*this);
341	363k	}
342
343	350k	Montgomery_Int& Montgomery_Int::square_this_n_times(secure_vector<word>& ws, size_t n) {
344	350k	const size_t p_size = m_params.p_words();
345	350k	BOTAN_ASSERT_NOMSG(m_v.size() == p_size);
346
347	350k	if(ws.size() < 2 * p_size) {
348	0	ws.resize(2 * p_size);
349	0	}
350
351	350k	auto do_sqr_n = [&](std::span<word> z) {
352	1.75M	for(size_t i = 0; i != n; ++i) {
353	1.40M	bigint_sqr(z.data(), 2 * p_size, m_v.data(), p_size, p_size, ws.data(), ws.size());
354
355	1.40M	bigint_monty_redc_inplace(z.data(), m_params.p()._data(), p_size, m_params.p_dash(), ws.data(), ws.size());
356
357	1.40M	copy_mem(m_v, std::span{z}.first(p_size));
358	1.40M	}
359	350k	};
360
361	350k	if(p_size <= MontgomeryUseStackLimit) {
362	350k	std::array<word, 2 * MontgomeryUseStackLimit> z{};
363	350k	do_sqr_n(z);
364	350k	} else {
365	0	secure_vector<word> z(2 * p_size);
366	0	do_sqr_n(z);
367	0	}
368
369	350k	return (*this);
370	350k	}
371
372	0	Montgomery_Int Montgomery_Int::square(secure_vector<word>& ws) const {
373	0	auto z = (*this);
374	0	z.square_this_n_times(ws, 1);
375	0	return z;
376	0	}
377
378		} // namespace Botan