/src/Botan-3.4.0/src/lib/math/numbertheory/monty.cpp

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

#include <botan/internal/monty.h>

#include <botan/reducer.h>
#include <botan/internal/mp_core.h>

#include <utility>

namespace Botan {

Montgomery_Params::Montgomery_Params(const BigInt& p, const Modular_Reducer& 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 * BOTAN_MP_WORD_BITS);

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

Montgomery_Params::Montgomery_Params(const BigInt& 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 * BOTAN_MP_WORD_BITS);

   // It might be faster to use ct_modulo here vs setting up Barrett reduction?
   Modular_Reducer mod_p(p);

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

BigInt Montgomery_Params::inv_mod_p(const BigInt& x) const {
   // TODO use Montgomery inverse here?
   return inverse_mod(x, p());
}

BigInt Montgomery_Params::redc(const BigInt& x, secure_vector<word>& ws) const {
   const size_t output_size = m_p_words + 1;

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

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

   bigint_monty_redc(z.mutable_data(), m_p.data(), m_p_words, m_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 output_size = 2 * m_p_words + 2;

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

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

   BigInt z = BigInt::with_capacity(output_size);
   bigint_mul(z.mutable_data(),
              z.size(),
              x.data(),
              x.size(),
              std::min(m_p_words, x.size()),
              y.data(),
              y.size(),
              std::min(m_p_words, y.size()),
              ws.data(),
              ws.size());

   bigint_monty_redc(z.mutable_data(), m_p.data(), m_p_words, m_p_dash, ws.data(), ws.size());

   return z;
}

BigInt Montgomery_Params::mul(const BigInt& x, const secure_vector<word>& y, secure_vector<word>& ws) const {
   const size_t output_size = 2 * m_p_words + 2;
   if(ws.size() < output_size) {
      ws.resize(output_size);
   }
   BigInt z = BigInt::with_capacity(output_size);

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

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

   bigint_monty_redc(z.mutable_data(), m_p.data(), m_p_words, m_p_dash, ws.data(), ws.size());

   return z;
}

void Montgomery_Params::mul_by(BigInt& x, const secure_vector<word>& y, secure_vector<word>& ws) const {
   const size_t output_size = 2 * m_p_words;

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

   word* z_data = &ws[0];
   word* ws_data = &ws[output_size];

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

   bigint_mul(z_data,
              output_size,
              x.data(),
              x.size(),
              std::min(m_p_words, x.size()),
              y.data(),
              y.size(),
              std::min(m_p_words, y.size()),
              ws_data,
              output_size);

   bigint_monty_redc(z_data, m_p.data(), m_p_words, m_p_dash, ws_data, output_size);

   if(x.size() < output_size) {
      x.grow_to(output_size);
   }
   copy_mem(x.mutable_data(), z_data, output_size);
}

void Montgomery_Params::mul_by(BigInt& x, const BigInt& y, secure_vector<word>& ws) const {
   const size_t output_size = 2 * m_p_words;

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

   word* z_data = &ws[0];
   word* ws_data = &ws[output_size];

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

   bigint_mul(z_data,
              output_size,
              x.data(),
              x.size(),
              std::min(m_p_words, x.size()),
              y.data(),
              y.size(),
              std::min(m_p_words, y.size()),
              ws_data,
              output_size);

   bigint_monty_redc(z_data, m_p.data(), m_p_words, m_p_dash, ws_data, output_size);

   if(x.size() < output_size) {
      x.grow_to(output_size);
   }
   copy_mem(x.mutable_data(), z_data, output_size);
}

BigInt Montgomery_Params::sqr(const BigInt& x, secure_vector<word>& ws) const {
   const size_t output_size = 2 * m_p_words;

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

   BigInt z = BigInt::with_capacity(output_size);

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

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

   bigint_monty_redc(z.mutable_data(), m_p.data(), m_p_words, m_p_dash, ws.data(), ws.size());

   return z;
}

void Montgomery_Params::square_this(BigInt& x, secure_vector<word>& ws) const {
   const size_t output_size = 2 * m_p_words;

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

   word* z_data = &ws[0];
   word* ws_data = &ws[output_size];

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

   bigint_sqr(z_data, output_size, x.data(), x.size(), std::min(m_p_words, x.size()), ws_data, output_size);

   bigint_monty_redc(z_data, m_p.data(), m_p_words, m_p_dash, ws_data, output_size);

   if(x.size() < output_size) {
      x.grow_to(output_size);
   }
   copy_mem(x.mutable_data(), z_data, output_size);
}

Montgomery_Int::Montgomery_Int(const std::shared_ptr<const Montgomery_Params>& params,
                               const BigInt& v,
                               bool redc_needed) :
      m_params(params) {
   if(redc_needed == false) {
      m_v = v;
   } else {
      BOTAN_ASSERT_NOMSG(m_v < m_params->p());
      secure_vector<word> ws;
      m_v = m_params->mul(v, m_params->R2(), ws);
   }
}

Montgomery_Int::Montgomery_Int(const std::shared_ptr<const Montgomery_Params>& params,
                               const uint8_t bits[],
                               size_t len,
                               bool redc_needed) :
      m_params(params), m_v(bits, len) {
   if(redc_needed) {
      BOTAN_ASSERT_NOMSG(m_v < m_params->p());
      secure_vector<word> ws;
      m_v = m_params->mul(m_v, m_params->R2(), ws);
   }
}

Montgomery_Int::Montgomery_Int(std::shared_ptr<const Montgomery_Params> params,
                               const word words[],
                               size_t len,
                               bool redc_needed) :
      m_params(std::move(params)) {
   m_v.set_words(words, len);

   if(redc_needed) {
      BOTAN_ASSERT_NOMSG(m_v < m_params->p());
      secure_vector<word> ws;
      m_v = m_params->mul(m_v, m_params->R2(), ws);
   }
}

void Montgomery_Int::fix_size() {
   const size_t p_words = m_params->p_words();

   if(m_v.sig_words() > p_words) {
      throw Internal_Error("Montgomery_Int::fix_size v too large");
   }

   m_v.grow_to(p_words);
}

bool Montgomery_Int::operator==(const Montgomery_Int& other) const {
   return m_v == other.m_v && m_params->p() == other.m_params->p();
}

std::vector<uint8_t> Montgomery_Int::serialize() const {
   std::vector<uint8_t> v(size());
   BigInt::encode_1363(v.data(), v.size(), value());
   return v;
}

size_t Montgomery_Int::size() const {
   return m_params->p().bytes();
}

bool Montgomery_Int::is_one() const {
   return m_v == m_params->R1();
}

bool Montgomery_Int::is_zero() const {
   return m_v.is_zero();
}

BigInt Montgomery_Int::value() const {
   secure_vector<word> ws;
   return m_params->redc(m_v, ws);
}

Montgomery_Int Montgomery_Int::operator+(const Montgomery_Int& other) const {
   secure_vector<word> ws;
   BigInt z = m_v;
   z.mod_add(other.m_v, m_params->p(), ws);
   return Montgomery_Int(m_params, z, false);
}

Montgomery_Int Montgomery_Int::operator-(const Montgomery_Int& other) const {
   secure_vector<word> ws;
   BigInt z = m_v;
   z.mod_sub(other.m_v, m_params->p(), ws);
   return Montgomery_Int(m_params, z, false);
}

Montgomery_Int& Montgomery_Int::operator+=(const Montgomery_Int& other) {
   secure_vector<word> ws;
   return this->add(other, ws);
}

Montgomery_Int& Montgomery_Int::add(const Montgomery_Int& other, secure_vector<word>& ws) {
   m_v.mod_add(other.m_v, m_params->p(), ws);
   return (*this);
}

Montgomery_Int& Montgomery_Int::operator-=(const Montgomery_Int& other) {
   secure_vector<word> ws;
   return this->sub(other, ws);
}

Montgomery_Int& Montgomery_Int::sub(const Montgomery_Int& other, secure_vector<word>& ws) {
   m_v.mod_sub(other.m_v, m_params->p(), ws);
   return (*this);
}

Montgomery_Int Montgomery_Int::operator*(const Montgomery_Int& other) const {
   secure_vector<word> ws;
   return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false);
}

Montgomery_Int Montgomery_Int::mul(const Montgomery_Int& other, secure_vector<word>& ws) const {
   return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false);
}

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

Montgomery_Int& Montgomery_Int::mul_by(const secure_vector<word>& other, secure_vector<word>& ws) {
   m_params->mul_by(m_v, other, ws);
   return (*this);
}

Montgomery_Int& Montgomery_Int::operator*=(const Montgomery_Int& other) {
   secure_vector<word> ws;
   return mul_by(other, ws);
}

Montgomery_Int& Montgomery_Int::operator*=(const secure_vector<word>& other) {
   secure_vector<word> ws;
   return mul_by(other, ws);
}

Montgomery_Int& Montgomery_Int::square_this_n_times(secure_vector<word>& ws, size_t n) {
   for(size_t i = 0; i != n; ++i) {
      m_params->square_this(m_v, ws);
   }
   return (*this);
}

Montgomery_Int& Montgomery_Int::square_this(secure_vector<word>& ws) {
   m_params->square_this(m_v, ws);
   return (*this);
}

Montgomery_Int Montgomery_Int::square(secure_vector<word>& ws) const {
   return Montgomery_Int(m_params, m_params->sqr(m_v, ws), false);
}

Montgomery_Int Montgomery_Int::cube(secure_vector<word>& ws) const {
   return Montgomery_Int(m_params, m_params->sqr(m_v, ws), false);
}

Montgomery_Int Montgomery_Int::multiplicative_inverse() const {
   secure_vector<word> ws;
   const BigInt iv = m_params->mul(m_params->inv_mod_p(m_v), m_params->R3(), ws);
   return Montgomery_Int(m_params, iv, false);
}

Montgomery_Int Montgomery_Int::additive_inverse() const {
   return Montgomery_Int(m_params, m_params->p()) - (*this);
}

Montgomery_Int& Montgomery_Int::mul_by_2(secure_vector<word>& ws) {
   m_v.mod_mul(2, m_params->p(), ws);
   return (*this);
}

Montgomery_Int& Montgomery_Int::mul_by_3(secure_vector<word>& ws) {
   m_v.mod_mul(3, m_params->p(), ws);
   return (*this);
}

Montgomery_Int& Montgomery_Int::mul_by_4(secure_vector<word>& ws) {
   m_v.mod_mul(4, m_params->p(), ws);
   return (*this);
}

Montgomery_Int& Montgomery_Int::mul_by_8(secure_vector<word>& ws) {
   m_v.mod_mul(8, m_params->p(), ws);
   return (*this);
}

}  // namespace Botan

Coverage Report

Created: 2025-10-10 06:23

Line	Count	Source
1		/*
2		* (C) 2018 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/reducer.h>
10		#include <botan/internal/mp_core.h>
11
12		#include <utility>
13
14		namespace Botan {
15
16	14.7k	Montgomery_Params::Montgomery_Params(const BigInt& p, const Modular_Reducer& mod_p) {
17	14.7k	if(p.is_even() \|\| p < 3) {
18	23	throw Invalid_Argument("Montgomery_Params invalid modulus");
19	23	}
20
21	14.7k	m_p = p;
22	14.7k	m_p_words = m_p.sig_words();
23	14.7k	m_p_dash = monty_inverse(m_p.word_at(0));
24
25	14.7k	const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS);
26
27	14.7k	m_r1 = mod_p.reduce(r);
28	14.7k	m_r2 = mod_p.square(m_r1);
29	14.7k	m_r3 = mod_p.multiply(m_r1, m_r2);
30	14.7k	}
31
32	53.1k	Montgomery_Params::Montgomery_Params(const BigInt& p) {
33	53.1k	if(p.is_even() \|\| p < 3) {
34	0	throw Invalid_Argument("Montgomery_Params invalid modulus");
35	0	}
36
37	53.1k	m_p = p;
38	53.1k	m_p_words = m_p.sig_words();
39	53.1k	m_p_dash = monty_inverse(m_p.word_at(0));
40
41	53.1k	const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS);
42
43		// It might be faster to use ct_modulo here vs setting up Barrett reduction?
44	53.1k	Modular_Reducer mod_p(p);
45
46	53.1k	m_r1 = mod_p.reduce(r);
47	53.1k	m_r2 = mod_p.square(m_r1);
48	53.1k	m_r3 = mod_p.multiply(m_r1, m_r2);
49	53.1k	}
50
51	0	BigInt Montgomery_Params::inv_mod_p(const BigInt& x) const {
52		// TODO use Montgomery inverse here?
53	0	return inverse_mod(x, p());
54	0	}
55
56	57.4k	BigInt Montgomery_Params::redc(const BigInt& x, secure_vector<word>& ws) const {
57	57.4k	const size_t output_size = m_p_words + 1;
58
59	57.4k	if(ws.size() < output_size) {
60	57.4k	ws.resize(output_size);
61	57.4k	}
62
63	57.4k	BigInt z = x;
64	57.4k	z.grow_to(2 * m_p_words);
65
66	57.4k	bigint_monty_redc(z.mutable_data(), m_p.data(), m_p_words, m_p_dash, ws.data(), ws.size());
67
68	57.4k	return z;
69	57.4k	}
70
71	445k	BigInt Montgomery_Params::mul(const BigInt& x, const BigInt& y, secure_vector<word>& ws) const {
72	445k	const size_t output_size = 2 * m_p_words + 2;
73
74	445k	if(ws.size() < output_size) {
75	306k	ws.resize(output_size);
76	306k	}
77
78	445k	BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
79	445k	BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words);
80
81	445k	BigInt z = BigInt::with_capacity(output_size);
82	445k	bigint_mul(z.mutable_data(),
83	445k	z.size(),
84	445k	x.data(),
85	445k	x.size(),
86	445k	std::min(m_p_words, x.size()),
87	445k	y.data(),
88	445k	y.size(),
89	445k	std::min(m_p_words, y.size()),
90	445k	ws.data(),
91	445k	ws.size());
92
93	445k	bigint_monty_redc(z.mutable_data(), m_p.data(), m_p_words, m_p_dash, ws.data(), ws.size());
94
95	445k	return z;
96	445k	}
97
98	0	BigInt Montgomery_Params::mul(const BigInt& x, const secure_vector<word>& y, secure_vector<word>& ws) const {
99	0	const size_t output_size = 2 * m_p_words + 2;
100	0	if(ws.size() < output_size) {
101	0	ws.resize(output_size);
102	0	}
103	0	BigInt z = BigInt::with_capacity(output_size);
104
105	0	BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
106
107	0	bigint_mul(z.mutable_data(),
108	0	z.size(),
109	0	x.data(),
110	0	x.size(),
111	0	std::min(m_p_words, x.size()),
112	0	y.data(),
113	0	y.size(),
114	0	std::min(m_p_words, y.size()),
115	0	ws.data(),
116	0	ws.size());
117
118	0	bigint_monty_redc(z.mutable_data(), m_p.data(), m_p_words, m_p_dash, ws.data(), ws.size());
119
120	0	return z;
121	0	}
122
123	0	void Montgomery_Params::mul_by(BigInt& x, const secure_vector<word>& y, secure_vector<word>& ws) const {
124	0	const size_t output_size = 2 * m_p_words;
125
126	0	if(ws.size() < 2 * output_size) {
127	0	ws.resize(2 * output_size);
128	0	}
129
130	0	word* z_data = &ws[0];
131	0	word* ws_data = &ws[output_size];
132
133	0	BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
134
135	0	bigint_mul(z_data,
136	0	output_size,
137	0	x.data(),
138	0	x.size(),
139	0	std::min(m_p_words, x.size()),
140	0	y.data(),
141	0	y.size(),
142	0	std::min(m_p_words, y.size()),
143	0	ws_data,
144	0	output_size);
145
146	0	bigint_monty_redc(z_data, m_p.data(), m_p_words, m_p_dash, ws_data, output_size);
147
148	0	if(x.size() < output_size) {
149	0	x.grow_to(output_size);
150	0	}
151	0	copy_mem(x.mutable_data(), z_data, output_size);
152	0	}
153
154	1.60M	void Montgomery_Params::mul_by(BigInt& x, const BigInt& y, secure_vector<word>& ws) const {
155	1.60M	const size_t output_size = 2 * m_p_words;
156
157	1.60M	if(ws.size() < 2 * output_size) {
158	13.4k	ws.resize(2 * output_size);
159	13.4k	}
160
161	1.60M	word* z_data = &ws[0];
162	1.60M	word* ws_data = &ws[output_size];
163
164	1.60M	BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
165
166	1.60M	bigint_mul(z_data,
167	1.60M	output_size,
168	1.60M	x.data(),
169	1.60M	x.size(),
170	1.60M	std::min(m_p_words, x.size()),
171	1.60M	y.data(),
172	1.60M	y.size(),
173	1.60M	std::min(m_p_words, y.size()),
174	1.60M	ws_data,
175	1.60M	output_size);
176
177	1.60M	bigint_monty_redc(z_data, m_p.data(), m_p_words, m_p_dash, ws_data, output_size);
178
179	1.60M	if(x.size() < output_size) {
180	13.4k	x.grow_to(output_size);
181	13.4k	}
182	1.60M	copy_mem(x.mutable_data(), z_data, output_size);
183	1.60M	}
184
185	27.9k	BigInt Montgomery_Params::sqr(const BigInt& x, secure_vector<word>& ws) const {
186	27.9k	const size_t output_size = 2 * m_p_words;
187
188	27.9k	if(ws.size() < output_size) {
189	13.9k	ws.resize(output_size);
190	13.9k	}
191
192	27.9k	BigInt z = BigInt::with_capacity(output_size);
193
194	27.9k	BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
195
196	27.9k	bigint_sqr(z.mutable_data(), z.size(), x.data(), x.size(), std::min(m_p_words, x.size()), ws.data(), ws.size());
197
198	27.9k	bigint_monty_redc(z.mutable_data(), m_p.data(), m_p_words, m_p_dash, ws.data(), ws.size());
199
200	27.9k	return z;
201	27.9k	}
202
203	3.46M	void Montgomery_Params::square_this(BigInt& x, secure_vector<word>& ws) const {
204	3.46M	const size_t output_size = 2 * m_p_words;
205
206	3.46M	if(ws.size() < 2 * output_size) {
207	38.2k	ws.resize(2 * output_size);
208	38.2k	}
209
210	3.46M	word* z_data = &ws[0];
211	3.46M	word* ws_data = &ws[output_size];
212
213	3.46M	BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
214
215	3.46M	bigint_sqr(z_data, output_size, x.data(), x.size(), std::min(m_p_words, x.size()), ws_data, output_size);
216
217	3.46M	bigint_monty_redc(z_data, m_p.data(), m_p_words, m_p_dash, ws_data, output_size);
218
219	3.46M	if(x.size() < output_size) {
220	0	x.grow_to(output_size);
221	0	}
222	3.46M	copy_mem(x.mutable_data(), z_data, output_size);
223	3.46M	}
224
225		Montgomery_Int::Montgomery_Int(const std::shared_ptr<const Montgomery_Params>& params,
226		const BigInt& v,
227		bool redc_needed) :
228	546k	m_params(params) {
229	546k	if(redc_needed == false) {
230	459k	m_v = v;
231	459k	} else {
232	86.1k	BOTAN_ASSERT_NOMSG(m_v < m_params->p());
233	86.1k	secure_vector<word> ws;
234	86.1k	m_v = m_params->mul(v, m_params->R2(), ws);
235	86.1k	}
236	546k	}
237
238		Montgomery_Int::Montgomery_Int(const std::shared_ptr<const Montgomery_Params>& params,
239		const uint8_t bits[],
240		size_t len,
241		bool redc_needed) :
242	0	m_params(params), m_v(bits, len) {
243	0	if(redc_needed) {
244	0	BOTAN_ASSERT_NOMSG(m_v < m_params->p());
245	0	secure_vector<word> ws;
246	0	m_v = m_params->mul(m_v, m_params->R2(), ws);
247	0	}
248	0	}
249
250		Montgomery_Int::Montgomery_Int(std::shared_ptr<const Montgomery_Params> params,
251		const word words[],
252		size_t len,
253		bool redc_needed) :
254	0	m_params(std::move(params)) {
255	0	m_v.set_words(words, len);
256
257	0	if(redc_needed) {
258	0	BOTAN_ASSERT_NOMSG(m_v < m_params->p());
259	0	secure_vector<word> ws;
260	0	m_v = m_params->mul(m_v, m_params->R2(), ws);
261	0	}
262	0	}
263
264	322k	void Montgomery_Int::fix_size() {
265	322k	const size_t p_words = m_params->p_words();
266
267	322k	if(m_v.sig_words() > p_words) {
268	0	throw Internal_Error("Montgomery_Int::fix_size v too large");
269	0	}
270
271	322k	m_v.grow_to(p_words);
272	322k	}
273
274	0	bool Montgomery_Int::operator==(const Montgomery_Int& other) const {
275	0	return m_v == other.m_v && m_params->p() == other.m_params->p();
276	0	}
277
278	0	std::vector<uint8_t> Montgomery_Int::serialize() const {
279	0	std::vector<uint8_t> v(size());
280	0	BigInt::encode_1363(v.data(), v.size(), value());
281	0	return v;
282	0	}
283
284	0	size_t Montgomery_Int::size() const {
285	0	return m_params->p().bytes();
286	0	}
287
288	0	bool Montgomery_Int::is_one() const {
289	0	return m_v == m_params->R1();
290	0	}
291
292	0	bool Montgomery_Int::is_zero() const {
293	0	return m_v.is_zero();
294	0	}
295
296	57.4k	BigInt Montgomery_Int::value() const {
297	57.4k	secure_vector<word> ws;
298	57.4k	return m_params->redc(m_v, ws);
299	57.4k	}
300
301	0	Montgomery_Int Montgomery_Int::operator+(const Montgomery_Int& other) const {
302	0	secure_vector<word> ws;
303	0	BigInt z = m_v;
304	0	z.mod_add(other.m_v, m_params->p(), ws);
305	0	return Montgomery_Int(m_params, z, false);
306	0	}
307
308	0	Montgomery_Int Montgomery_Int::operator-(const Montgomery_Int& other) const {
309	0	secure_vector<word> ws;
310	0	BigInt z = m_v;
311	0	z.mod_sub(other.m_v, m_params->p(), ws);
312	0	return Montgomery_Int(m_params, z, false);
313	0	}
314
315	0	Montgomery_Int& Montgomery_Int::operator+=(const Montgomery_Int& other) {
316	0	secure_vector<word> ws;
317	0	return this->add(other, ws);
318	0	}
319
320	0	Montgomery_Int& Montgomery_Int::add(const Montgomery_Int& other, secure_vector<word>& ws) {
321	0	m_v.mod_add(other.m_v, m_params->p(), ws);
322	0	return (*this);
323	0	}
324
325	0	Montgomery_Int& Montgomery_Int::operator-=(const Montgomery_Int& other) {
326	0	secure_vector<word> ws;
327	0	return this->sub(other, ws);
328	0	}
329
330	0	Montgomery_Int& Montgomery_Int::sub(const Montgomery_Int& other, secure_vector<word>& ws) {
331	0	m_v.mod_sub(other.m_v, m_params->p(), ws);
332	0	return (*this);
333	0	}
334
335	206k	Montgomery_Int Montgomery_Int::operator*(const Montgomery_Int& other) const {
336	206k	secure_vector<word> ws;
337	206k	return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false);
338	206k	}
339
340	153k	Montgomery_Int Montgomery_Int::mul(const Montgomery_Int& other, secure_vector<word>& ws) const {
341	153k	return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false);
342	153k	}
343
344	1.60M	Montgomery_Int& Montgomery_Int::mul_by(const Montgomery_Int& other, secure_vector<word>& ws) {
345	1.60M	m_params->mul_by(m_v, other.m_v, ws);
346	1.60M	return (*this);
347	1.60M	}
348
349	0	Montgomery_Int& Montgomery_Int::mul_by(const secure_vector<word>& other, secure_vector<word>& ws) {
350	0	m_params->mul_by(m_v, other, ws);
351	0	return (*this);
352	0	}
353
354	0	Montgomery_Int& Montgomery_Int::operator*=(const Montgomery_Int& other) {
355	0	secure_vector<word> ws;
356	0	return mul_by(other, ws);
357	0	}
358
359	0	Montgomery_Int& Montgomery_Int::operator*=(const secure_vector<word>& other) {
360	0	secure_vector<word> ws;
361	0	return mul_by(other, ws);
362	0	}
363
364	1.08M	Montgomery_Int& Montgomery_Int::square_this_n_times(secure_vector<word>& ws, size_t n) {
365	2.17M	for(size_t i = 0; i != n; ++i) {
366	1.08M	m_params->square_this(m_v, ws);
367	1.08M	}
368	1.08M	return (*this);
369	1.08M	}
370
371	2.37M	Montgomery_Int& Montgomery_Int::square_this(secure_vector<word>& ws) {
372	2.37M	m_params->square_this(m_v, ws);
373	2.37M	return (*this);
374	2.37M	}
375
376	27.9k	Montgomery_Int Montgomery_Int::square(secure_vector<word>& ws) const {
377	27.9k	return Montgomery_Int(m_params, m_params->sqr(m_v, ws), false);
378	27.9k	}
379
380	0	Montgomery_Int Montgomery_Int::cube(secure_vector<word>& ws) const {
381	0	return Montgomery_Int(m_params, m_params->sqr(m_v, ws), false);
382	0	}
383
384	0	Montgomery_Int Montgomery_Int::multiplicative_inverse() const {
385	0	secure_vector<word> ws;
386	0	const BigInt iv = m_params->mul(m_params->inv_mod_p(m_v), m_params->R3(), ws);
387	0	return Montgomery_Int(m_params, iv, false);
388	0	}
389
390	0	Montgomery_Int Montgomery_Int::additive_inverse() const {
391	0	return Montgomery_Int(m_params, m_params->p()) - (*this);
392	0	}
393
394	0	Montgomery_Int& Montgomery_Int::mul_by_2(secure_vector<word>& ws) {
395	0	m_v.mod_mul(2, m_params->p(), ws);
396	0	return (*this);
397	0	}
398
399	0	Montgomery_Int& Montgomery_Int::mul_by_3(secure_vector<word>& ws) {
400	0	m_v.mod_mul(3, m_params->p(), ws);
401	0	return (*this);
402	0	}
403
404	0	Montgomery_Int& Montgomery_Int::mul_by_4(secure_vector<word>& ws) {
405	0	m_v.mod_mul(4, m_params->p(), ws);
406	0	return (*this);
407	0	}
408
409	0	Montgomery_Int& Montgomery_Int::mul_by_8(secure_vector<word>& ws) {
410	0	m_v.mod_mul(8, m_params->p(), ws);
411	0	return (*this);
412	0	}
413
414		} // namespace Botan