11087146043

Committed 28 Sep 2024 09:28PM UTC coverage: 92.003% (+0.7%) from 91.274%

Build # 11087146043

Build Type

push

github

Committed by

web-flow

Commit Message

Create terraform.yml

Run Details

82959 of 90170 relevant lines covered (92.0%)

9376319.11 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

96.2

/src/lib/math/numbertheory/numthry.cpp

/*
* Number Theory Functions
* (C) 1999-2011,2016,2018,2019 Jack Lloyd
* (C) 2007,2008 Falko Strenzke, FlexSecure GmbH
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/numthry.h>

#include <botan/reducer.h>
#include <botan/rng.h>
#include <botan/internal/ct_utils.h>
#include <botan/internal/divide.h>
#include <botan/internal/monty.h>
#include <botan/internal/monty_exp.h>
#include <botan/internal/mp_core.h>
#include <botan/internal/primality.h>
#include <algorithm>

namespace Botan {

/*
* Tonelli-Shanks algorithm
*/
BigInt sqrt_modulo_prime(const BigInt& a, const BigInt& p) {
   BOTAN_ARG_CHECK(p > 1, "invalid prime");
   BOTAN_ARG_CHECK(a < p, "value to solve for must be less than p");
   BOTAN_ARG_CHECK(a >= 0, "value to solve for must not be negative");

   // some very easy cases
   if(p == 2 || a <= 1) {
      return a;
   }

   BOTAN_ARG_CHECK(p.is_odd(), "invalid prime");

   if(jacobi(a, p) != 1) {  // not a quadratic residue
      return BigInt::from_s32(-1);
   }

   Modular_Reducer mod_p(p);
   auto monty_p = std::make_shared<Montgomery_Params>(p, mod_p);

   // If p == 3 (mod 4) there is a simple solution
   if(p % 4 == 3) {
      return monty_exp_vartime(monty_p, a, ((p + 1) >> 2));
   }

   // Otherwise we have to use Shanks-Tonelli
   size_t s = low_zero_bits(p - 1);
   BigInt q = p >> s;

   q -= 1;
   q >>= 1;

   BigInt r = monty_exp_vartime(monty_p, a, q);
   BigInt n = mod_p.multiply(a, mod_p.square(r));
   r = mod_p.multiply(r, a);

   if(n == 1) {
      return r;
   }

   // find random quadratic nonresidue z
   word z = 2;
   for(;;) {
      if(jacobi(BigInt::from_word(z), p) == -1) {  // found one
         break;
      }

      z += 1;  // try next z

      /*
      * The expected number of tests to find a non-residue modulo a
      * prime is 2. If we have not found one after 256 then almost
      * certainly we have been given a non-prime p.
      */
      if(z >= 256) {
         return BigInt::from_s32(-1);
      }
   }

   BigInt c = monty_exp_vartime(monty_p, BigInt::from_word(z), (q << 1) + 1);

   while(n > 1) {
      q = n;

      size_t i = 0;
      while(q != 1) {
         q = mod_p.square(q);
         ++i;

         if(i >= s) {
            return BigInt::from_s32(-1);
         }
      }

      BOTAN_ASSERT_NOMSG(s >= (i + 1));  // No underflow!
      c = monty_exp_vartime(monty_p, c, BigInt::power_of_2(s - i - 1));
      r = mod_p.multiply(r, c);
      c = mod_p.square(c);
      n = mod_p.multiply(n, c);

      // s decreases as the algorithm proceeds
      BOTAN_ASSERT_NOMSG(s >= i);
      s = i;
   }

   return r;
}

/*
* Calculate the Jacobi symbol
*/
int32_t jacobi(const BigInt& a, const BigInt& n) {
   if(n.is_even() || n < 2) {
      throw Invalid_Argument("jacobi: second argument must be odd and > 1");
   }

   BigInt x = a % n;
   BigInt y = n;
   int32_t J = 1;

   while(y > 1) {
      x %= y;
      if(x > y / 2) {
         x = y - x;
         if(y % 4 == 3) {
            J = -J;
         }
      }
      if(x.is_zero()) {
         return 0;
      }

      size_t shifts = low_zero_bits(x);
      x >>= shifts;
      if(shifts % 2) {
         word y_mod_8 = y % 8;
         if(y_mod_8 == 3 || y_mod_8 == 5) {
            J = -J;
         }
      }

      if(x % 4 == 3 && y % 4 == 3) {
         J = -J;
      }
      std::swap(x, y);
   }
   return J;
}

/*
* Square a BigInt
*/
BigInt square(const BigInt& x) {
   BigInt z = x;
   secure_vector<word> ws;
   z.square(ws);
   return z;
}

/*
* Return the number of 0 bits at the end of n
*/
size_t low_zero_bits(const BigInt& n) {
   size_t low_zero = 0;

   auto seen_nonempty_word = CT::Mask<word>::cleared();

   for(size_t i = 0; i != n.size(); ++i) {
      const word x = n.word_at(i);

      // ctz(0) will return sizeof(word)
      const size_t tz_x = ctz(x);

      // if x > 0 we want to count tz_x in total but not any
      // further words, so set the mask after the addition
      low_zero += seen_nonempty_word.if_not_set_return(tz_x);

      seen_nonempty_word |= CT::Mask<word>::expand(x);
   }

   // if we saw no words with x > 0 then n == 0 and the value we have
   // computed is meaningless. Instead return BigInt::zero() in that case.
   return static_cast<size_t>(seen_nonempty_word.if_set_return(low_zero));
}

/*
* Calculate the GCD in constant time
*/
BigInt gcd(const BigInt& a, const BigInt& b) {
   if(a.is_zero()) {
      return abs(b);
   }
   if(b.is_zero()) {
      return abs(a);
   }

   const size_t sz = std::max(a.sig_words(), b.sig_words());
   auto u = BigInt::with_capacity(sz);
   auto v = BigInt::with_capacity(sz);
   u += a;
   v += b;

   u.const_time_poison();
   v.const_time_poison();

   u.set_sign(BigInt::Positive);
   v.set_sign(BigInt::Positive);

   // In the worst case we have two fully populated big ints. After right
   // shifting so many times, we'll have reached the result for sure.
   const size_t loop_cnt = u.bits() + v.bits();

   using WordMask = CT::Mask<word>;

   // This temporary is big enough to hold all intermediate results of the
   // algorithm. No reallocation will happen during the loop.
   // Note however, that `ct_cond_assign()` will invalidate the 'sig_words'
   // cache, which _does not_ shrink the capacity of the underlying buffer.
   auto tmp = BigInt::with_capacity(sz);
   size_t factors_of_two = 0;
   for(size_t i = 0; i != loop_cnt; ++i) {
      auto both_odd = WordMask::expand(u.is_odd()) & WordMask::expand(v.is_odd());

      // Subtract the smaller from the larger if both are odd
      auto u_gt_v = WordMask::expand(bigint_cmp(u.data(), u.size(), v.data(), v.size()) > 0);
      bigint_sub_abs(tmp.mutable_data(), u.data(), sz, v.data(), sz);
      u.ct_cond_assign((u_gt_v & both_odd).as_bool(), tmp);
      v.ct_cond_assign((~u_gt_v & both_odd).as_bool(), tmp);

      const auto u_is_even = WordMask::expand(u.is_even());
      const auto v_is_even = WordMask::expand(v.is_even());
      BOTAN_DEBUG_ASSERT((u_is_even | v_is_even).as_bool());

      // When both are even, we're going to eliminate a factor of 2.
      // We have to reapply this factor to the final result.
      factors_of_two += (u_is_even & v_is_even).if_set_return(1);

      // remove one factor of 2, if u is even
      bigint_shr2(tmp.mutable_data(), u.data(), sz, 1);
      u.ct_cond_assign(u_is_even.as_bool(), tmp);

      // remove one factor of 2, if v is even
      bigint_shr2(tmp.mutable_data(), v.data(), sz, 1);
      v.ct_cond_assign(v_is_even.as_bool(), tmp);
   }

   // The GCD (without factors of two) is either in u or v, the other one is
   // zero. The non-zero variable _must_ be odd, because all factors of two were
   // removed in the loop iterations above.
   BOTAN_DEBUG_ASSERT(u.is_zero() || v.is_zero());
   BOTAN_DEBUG_ASSERT(u.is_odd() || v.is_odd());

   // make sure that the GCD (without factors of two) is in u
   u.ct_cond_assign(u.is_even() /* .is_zero() would not be constant time */, v);

   // re-apply the factors of two
   u.ct_shift_left(factors_of_two);

   u.const_time_unpoison();
   v.const_time_unpoison();

   return u;
}

/*
* Calculate the LCM
*/
BigInt lcm(const BigInt& a, const BigInt& b) {
   if(a == b) {
      return a;
   }

   auto ab = a * b;
   ab.set_sign(BigInt::Positive);  // ignore the signs of a & b
   const auto g = gcd(a, b);
   return ct_divide(ab, g);
}

/*
* Modular Exponentiation
*/
BigInt power_mod(const BigInt& base, const BigInt& exp, const BigInt& mod) {
   if(mod.is_negative() || mod == 1) {
      return BigInt::zero();
   }

   if(base.is_zero() || mod.is_zero()) {
      if(exp.is_zero()) {
         return BigInt::one();
      }
      return BigInt::zero();
   }

   Modular_Reducer reduce_mod(mod);

   const size_t exp_bits = exp.bits();

   if(mod.is_odd()) {
      auto monty_params = std::make_shared<Montgomery_Params>(mod, reduce_mod);
      return monty_exp(monty_params, reduce_mod.reduce(base), exp, exp_bits);
   }

   /*
   Support for even modulus is just a convenience and not considered
   cryptographically important, so this implementation is slow ...
   */
   BigInt accum = BigInt::one();
   BigInt g = reduce_mod.reduce(base);
   BigInt t;

   for(size_t i = 0; i != exp_bits; ++i) {
      t = reduce_mod.multiply(g, accum);
      g = reduce_mod.square(g);
      accum.ct_cond_assign(exp.get_bit(i), t);
   }
   return accum;
}

BigInt is_perfect_square(const BigInt& C) {
   if(C < 1) {
      throw Invalid_Argument("is_perfect_square requires C >= 1");
   }
   if(C == 1) {
      return BigInt::one();
   }

   const size_t n = C.bits();
   const size_t m = (n + 1) / 2;
   const BigInt B = C + BigInt::power_of_2(m);

   BigInt X = BigInt::power_of_2(m) - 1;
   BigInt X2 = (X * X);

   for(;;) {
      X = (X2 + C) / (2 * X);
      X2 = (X * X);

      if(X2 < B) {
         break;
      }
   }

   if(X2 == C) {
      return X;
   } else {
      return BigInt::zero();
   }
}

/*
* Test for primality using Miller-Rabin
*/
bool is_prime(const BigInt& n, RandomNumberGenerator& rng, size_t prob, bool is_random) {
   if(n == 2) {
      return true;
   }
   if(n <= 1 || n.is_even()) {
      return false;
   }

   const size_t n_bits = n.bits();

   // Fast path testing for small numbers (<= 65521)
   if(n_bits <= 16) {
      const uint16_t num = static_cast<uint16_t>(n.word_at(0));

      return std::binary_search(PRIMES, PRIMES + PRIME_TABLE_SIZE, num);
   }

   Modular_Reducer mod_n(n);

   if(rng.is_seeded()) {
      const size_t t = miller_rabin_test_iterations(n_bits, prob, is_random);

      if(is_miller_rabin_probable_prime(n, mod_n, rng, t) == false) {
         return false;
      }

      if(is_random) {
         return true;
      } else {
         return is_lucas_probable_prime(n, mod_n);
      }
   } else {
      return is_bailie_psw_probable_prime(n, mod_n);
   }
}

}  // namespace Botan

1	/*
2	* Number Theory Functions
3	* (C) 1999-2011,2016,2018,2019 Jack Lloyd
4	* (C) 2007,2008 Falko Strenzke, FlexSecure GmbH
5	*
6	* Botan is released under the Simplified BSD License (see license.txt)
7	*/
8
9	#include <botan/numthry.h>
10
11	#include <botan/reducer.h>
12	#include <botan/rng.h>
13	#include <botan/internal/ct_utils.h>
14	#include <botan/internal/divide.h>
15	#include <botan/internal/monty.h>
16	#include <botan/internal/monty_exp.h>
17	#include <botan/internal/mp_core.h>
18	#include <botan/internal/primality.h>
19	#include <algorithm>
20
21	namespace Botan {
22
23	/*
24	* Tonelli-Shanks algorithm
25	*/
26	BigInt sqrt_modulo_prime(const BigInt& a, const BigInt& p) {	6,911✔
27	BOTAN_ARG_CHECK(p > 1, "invalid prime");	6,911✔
28	BOTAN_ARG_CHECK(a < p, "value to solve for must be less than p");	6,911✔
29	BOTAN_ARG_CHECK(a >= 0, "value to solve for must not be negative");	6,911✔
30
31	// some very easy cases
32	if(p == 2 \|\| a <= 1) {	13,820✔
33	return a;	6,914✔
34	}
35
36	BOTAN_ARG_CHECK(p.is_odd(), "invalid prime");	13,816✔
37
38	if(jacobi(a, p) != 1) { // not a quadratic residue	6,908✔
39	return BigInt::from_s32(-1);	2,656✔
40	}
41
42	Modular_Reducer mod_p(p);	4,252✔
43	auto monty_p = std::make_shared<Montgomery_Params>(p, mod_p);	4,252✔
44
45	// If p == 3 (mod 4) there is a simple solution
46	if(p % 4 == 3) {	4,252✔
47	return monty_exp_vartime(monty_p, a, ((p + 1) >> 2));	18,505✔
48	}
49
50	// Otherwise we have to use Shanks-Tonelli
51	size_t s = low_zero_bits(p - 1);	551✔
52	BigInt q = p >> s;	551✔
53
54	q -= 1;	551✔
55	q >>= 1;	551✔
56
57	BigInt r = monty_exp_vartime(monty_p, a, q);	551✔
58	BigInt n = mod_p.multiply(a, mod_p.square(r));	551✔
59	r = mod_p.multiply(r, a);	551✔
60
61	if(n == 1) {	551✔
62	return r;	18✔
63	}
64
65	// find random quadratic nonresidue z
66	word z = 2;
67	for(;;) {	5,385✔
68	if(jacobi(BigInt::from_word(z), p) == -1) { // found one	10,770✔
69	break;
70	}
71
72	z += 1; // try next z	4,853✔
73
74	/*
75	* The expected number of tests to find a non-residue modulo a
76	* prime is 2. If we have not found one after 256 then almost
77	* certainly we have been given a non-prime p.
78	*/
79	if(z >= 256) {	4,853✔
80	return BigInt::from_s32(-1);	1✔
81	}
82	}
83
84	BigInt c = monty_exp_vartime(monty_p, BigInt::from_word(z), (q << 1) + 1);	3,192✔
85
86	while(n > 1) {	24,286✔
87	q = n;	23,760✔
88
89	size_t i = 0;	23,760✔
90	while(q != 1) {	1,164,304✔
91	q = mod_p.square(q);	1,140,550✔
92	++i;	1,140,550✔
93
94	if(i >= s) {	1,140,550✔
95	return BigInt::from_s32(-1);	6✔
96	}
97	}
98
99	BOTAN_ASSERT_NOMSG(s >= (i + 1)); // No underflow!	23,754✔
100	c = monty_exp_vartime(monty_p, c, BigInt::power_of_2(s - i - 1));	95,016✔
101	r = mod_p.multiply(r, c);	23,754✔
102	c = mod_p.square(c);	23,754✔
103	n = mod_p.multiply(n, c);	23,754✔
104
105	// s decreases as the algorithm proceeds
106	BOTAN_ASSERT_NOMSG(s >= i);	23,754✔
107	s = i;
108	}
109
110	return r;	532✔
111	}	9,613✔
112
113	/*
114	* Calculate the Jacobi symbol
115	*/
116	int32_t jacobi(const BigInt& a, const BigInt& n) {	110,786✔
117	if(n.is_even() \|\| n < 2) {	332,358✔
118	throw Invalid_Argument("jacobi: second argument must be odd and > 1");	×
119	}
120
121	BigInt x = a % n;	110,786✔
122	BigInt y = n;	110,786✔
123	int32_t J = 1;	110,786✔
124
125	while(y > 1) {	1,033,375✔
126	x %= y;	939,236✔
127	if(x > y / 2) {	2,817,708✔
128	x = y - x;	408,020✔
129	if(y % 4 == 3) {	408,020✔
130	J = -J;	198,974✔
131	}
132	}
133	if(x.is_zero()) {	1,347,256✔
134	return 0;
135	}
136
137	size_t shifts = low_zero_bits(x);	922,589✔
138	x >>= shifts;	922,589✔
139	if(shifts % 2) {	922,589✔
140	word y_mod_8 = y % 8;	270,344✔
141	if(y_mod_8 == 3 \|\| y_mod_8 == 5) {	270,344✔
142	J = -J;	141,473✔
143	}
144	}
145
146	if(x % 4 == 3 && y % 4 == 3) {	922,589✔
147	J = -J;	205,402✔
148	}
149	std::swap(x, y);	922,589✔
150	}
151	return J;
152	}	204,947✔
153
154	/*
155	* Square a BigInt
156	*/
157	BigInt square(const BigInt& x) {	3,313,804✔
158	BigInt z = x;	3,313,804✔
159	secure_vector<word> ws;	3,313,804✔
160	z.square(ws);	3,313,804✔
161	return z;	3,313,804✔
162	}	3,313,804✔
163
164	/*
165	* Return the number of 0 bits at the end of n
166	*/
167	size_t low_zero_bits(const BigInt& n) {	1,135,683✔
168	size_t low_zero = 0;	1,135,683✔
169
170	auto seen_nonempty_word = CT::Mask<word>::cleared();	1,135,683✔
171
172	for(size_t i = 0; i != n.size(); ++i) {	12,033,087✔
173	const word x = n.word_at(i);	10,897,404✔
174
175	// ctz(0) will return sizeof(word)
176	const size_t tz_x = ctz(x);	10,897,404✔
177
178	// if x > 0 we want to count tz_x in total but not any
179	// further words, so set the mask after the addition
180	low_zero += seen_nonempty_word.if_not_set_return(tz_x);	10,897,404✔
181
182	seen_nonempty_word \|= CT::Mask<word>::expand(x);	10,897,404✔
183	}
184
185	// if we saw no words with x > 0 then n == 0 and the value we have
186	// computed is meaningless. Instead return BigInt::zero() in that case.
187	return static_cast<size_t>(seen_nonempty_word.if_set_return(low_zero));	1,135,683✔
188	}
189
190	/*
191	* Calculate the GCD in constant time
192	*/
193	BigInt gcd(const BigInt& a, const BigInt& b) {	22,099✔
194	if(a.is_zero()) {	23,852✔
195	return abs(b);	4✔
196	}
197	if(b.is_zero()) {	42,178✔
198	return abs(a);	2✔
199	}
200
201	const size_t sz = std::max(a.sig_words(), b.sig_words());	22,093✔
202	auto u = BigInt::with_capacity(sz);	22,093✔
203	auto v = BigInt::with_capacity(sz);	22,093✔
204	u += a;	22,093✔
205	v += b;	22,093✔
206
207	u.const_time_poison();	22,093✔
208	v.const_time_poison();	22,093✔
209
210	u.set_sign(BigInt::Positive);	22,093✔
211	v.set_sign(BigInt::Positive);	22,093✔
212
213	// In the worst case we have two fully populated big ints. After right
214	// shifting so many times, we'll have reached the result for sure.
215	const size_t loop_cnt = u.bits() + v.bits();	22,093✔
216
217	using WordMask = CT::Mask<word>;	22,093✔
218
219	// This temporary is big enough to hold all intermediate results of the
220	// algorithm. No reallocation will happen during the loop.
221	// Note however, that `ct_cond_assign()` will invalidate the 'sig_words'
222	// cache, which _does not_ shrink the capacity of the underlying buffer.
223	auto tmp = BigInt::with_capacity(sz);	22,093✔
224	size_t factors_of_two = 0;
225	for(size_t i = 0; i != loop_cnt; ++i) {	2,802,054✔
226	auto both_odd = WordMask::expand(u.is_odd()) & WordMask::expand(v.is_odd());	8,339,883✔
227
228	// Subtract the smaller from the larger if both are odd
229	auto u_gt_v = WordMask::expand(bigint_cmp(u.data(), u.size(), v.data(), v.size()) > 0);	2,779,961✔
230	bigint_sub_abs(tmp.mutable_data(), u.data(), sz, v.data(), sz);	2,779,961✔
231	u.ct_cond_assign((u_gt_v & both_odd).as_bool(), tmp);	2,779,961✔
232	v.ct_cond_assign((~u_gt_v & both_odd).as_bool(), tmp);	2,779,961✔
233
234	const auto u_is_even = WordMask::expand(u.is_even());	5,559,922✔
235	const auto v_is_even = WordMask::expand(v.is_even());	5,559,922✔
236	BOTAN_DEBUG_ASSERT((u_is_even \| v_is_even).as_bool());	2,779,961✔
237
238	// When both are even, we're going to eliminate a factor of 2.
239	// We have to reapply this factor to the final result.
240	factors_of_two += (u_is_even & v_is_even).if_set_return(1);	2,779,961✔
241
242	// remove one factor of 2, if u is even
243	bigint_shr2(tmp.mutable_data(), u.data(), sz, 1);	2,779,961✔
244	u.ct_cond_assign(u_is_even.as_bool(), tmp);	2,779,961✔
245
246	// remove one factor of 2, if v is even
247	bigint_shr2(tmp.mutable_data(), v.data(), sz, 1);	2,779,961✔
248	v.ct_cond_assign(v_is_even.as_bool(), tmp);	2,779,961✔
249	}
250
251	// The GCD (without factors of two) is either in u or v, the other one is
252	// zero. The non-zero variable _must_ be odd, because all factors of two were
253	// removed in the loop iterations above.
254	BOTAN_DEBUG_ASSERT(u.is_zero() \|\| v.is_zero());	22,093✔
255	BOTAN_DEBUG_ASSERT(u.is_odd() \|\| v.is_odd());	22,093✔
256
257	// make sure that the GCD (without factors of two) is in u
258	u.ct_cond_assign(u.is_even() /* .is_zero() would not be constant time */, v);	44,186✔
259
260	// re-apply the factors of two
261	u.ct_shift_left(factors_of_two);	22,093✔
262
263	u.const_time_unpoison();	22,093✔
264	v.const_time_unpoison();	22,093✔
265
266	return u;	22,093✔
267	}	66,285✔
268
269	/*
270	* Calculate the LCM
271	*/
272	BigInt lcm(const BigInt& a, const BigInt& b) {	500✔
273	if(a == b) {	500✔
274	return a;	×
275	}
276
277	auto ab = a * b;	500✔
278	ab.set_sign(BigInt::Positive); // ignore the signs of a & b	500✔
279	const auto g = gcd(a, b);	500✔
280	return ct_divide(ab, g);	500✔
281	}	1,000✔
282
283	/*
284	* Modular Exponentiation
285	*/
286	BigInt power_mod(const BigInt& base, const BigInt& exp, const BigInt& mod) {	203✔
287	if(mod.is_negative() \|\| mod == 1) {	406✔
288	return BigInt::zero();	×
289	}
290
291	if(base.is_zero() \|\| mod.is_zero()) {	548✔
292	if(exp.is_zero()) {	2✔
293	return BigInt::one();	1✔
294	}
295	return BigInt::zero();	×
296	}
297
298	Modular_Reducer reduce_mod(mod);	202✔
299
300	const size_t exp_bits = exp.bits();	202✔
301
302	if(mod.is_odd()) {	404✔
303	auto monty_params = std::make_shared<Montgomery_Params>(mod, reduce_mod);	179✔
304	return monty_exp(monty_params, reduce_mod.reduce(base), exp, exp_bits);	716✔
305	}	179✔
306
307	/*
308	Support for even modulus is just a convenience and not considered
309	cryptographically important, so this implementation is slow ...
310	*/
311	BigInt accum = BigInt::one();	23✔
312	BigInt g = reduce_mod.reduce(base);	23✔
313	BigInt t;	23✔
314
315	for(size_t i = 0; i != exp_bits; ++i) {	6,260✔
316	t = reduce_mod.multiply(g, accum);	6,237✔
317	g = reduce_mod.square(g);	6,237✔
318	accum.ct_cond_assign(exp.get_bit(i), t);	12,474✔
319	}
320	return accum;	23✔
321	}	248✔
322
323	BigInt is_perfect_square(const BigInt& C) {	708✔
324	if(C < 1) {	708✔
325	throw Invalid_Argument("is_perfect_square requires C >= 1");	×
326	}
327	if(C == 1) {	708✔
328	return BigInt::one();	×
329	}
330
331	const size_t n = C.bits();	708✔
332	const size_t m = (n + 1) / 2;	708✔
333	const BigInt B = C + BigInt::power_of_2(m);	708✔
334
335	BigInt X = BigInt::power_of_2(m) - 1;	1,416✔
336	BigInt X2 = (X * X);	708✔
337
338	for(;;) {	1,680✔
339	X = (X2 + C) / (2 * X);	5,040✔
340	X2 = (X * X);	1,680✔
341
342	if(X2 < B) {	1,680✔
343	break;
344	}
345	}
346
347	if(X2 == C) {	708✔
348	return X;	708✔
349	} else {
350	return BigInt::zero();	645✔
351	}
352	}	2,061✔
353
354	/*
355	* Test for primality using Miller-Rabin
356	*/
357	bool is_prime(const BigInt& n, RandomNumberGenerator& rng, size_t prob, bool is_random) {	52,134✔
358	if(n == 2) {	52,134✔
359	return true;
360	}
361	if(n <= 1 \|\| n.is_even()) {	104,264✔
362	return false;
363	}
364
365	const size_t n_bits = n.bits();	52,130✔
366
367	// Fast path testing for small numbers (<= 65521)
368	if(n_bits <= 16) {	52,130✔
369	const uint16_t num = static_cast<uint16_t>(n.word_at(0));	32,791✔
370
371	return std::binary_search(PRIMES, PRIMES + PRIME_TABLE_SIZE, num);	32,791✔
372	}
373
374	Modular_Reducer mod_n(n);	19,339✔
375
376	if(rng.is_seeded()) {	19,339✔
377	const size_t t = miller_rabin_test_iterations(n_bits, prob, is_random);	19,339✔
378
379	if(is_miller_rabin_probable_prime(n, mod_n, rng, t) == false) {	19,339✔
380	return false;
381	}
382
383	if(is_random) {	3,350✔
384	return true;
385	} else {
386	return is_lucas_probable_prime(n, mod_n);	3,157✔
387	}
388	} else {
389	return is_bailie_psw_probable_prime(n, mod_n);	×
390	}
391	}	19,339✔
392
393	} // namespace Botan

randombit / botan / 11087146043

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous