5123321399

Committed 30 May 2023 04:06PM UTC coverage: 92.213% (+0.004%) from 92.209%

Build # 5123321399

Build Type

Pull #3558

github

Committed by

web-flow

Commit Message

Merge dd72f7389 into 057bcbc35

Pull Request Pull Request #3558: Add braces around all if/else statements

Run Details

75602 of 81986 relevant lines covered (92.21%)

11859779.3 hits per line

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

95.41

/src/cli/math.cpp

/*
* (C) 2009,2010,2015 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include "cli.h"

#if defined(BOTAN_HAS_NUMBERTHEORY)

   #include <botan/numthry.h>
   #include <botan/internal/monty.h>
   #include <iterator>

namespace Botan_CLI {

class Modular_Inverse final : public Command {
   public:
      Modular_Inverse() : Command("mod_inverse n mod") {}

      std::string group() const override { return "numtheory"; }

      std::string description() const override { return "Calculates a modular inverse"; }

      void go() override {
         const Botan::BigInt n(get_arg("n"));
         const Botan::BigInt mod(get_arg("mod"));

         output() << Botan::inverse_mod(n, mod) << "\n";
      }
};

BOTAN_REGISTER_COMMAND("mod_inverse", Modular_Inverse);

class Gen_Prime final : public Command {
   public:
      Gen_Prime() : Command("gen_prime --hex --count=1 bits") {}

      std::string group() const override { return "numtheory"; }

      std::string description() const override { return "Samples one or more primes"; }

      void go() override {
         const size_t bits = get_arg_sz("bits");
         const size_t cnt = get_arg_sz("count");
         const bool hex = flag_set("hex");

         for(size_t i = 0; i != cnt; ++i) {
            const Botan::BigInt p = Botan::random_prime(rng(), bits);

            if(hex) {
               output() << "0x" << std::hex << p << "\n";
            } else {
               output() << p << "\n";
            }
         }
      }
};

BOTAN_REGISTER_COMMAND("gen_prime", Gen_Prime);

class Is_Prime final : public Command {
   public:
      Is_Prime() : Command("is_prime --prob=56 n") {}

      std::string group() const override { return "numtheory"; }

      std::string description() const override { return "Test if the integer n is composite or prime"; }

      void go() override {
         Botan::BigInt n(get_arg("n"));
         const size_t prob = get_arg_sz("prob");
         const bool prime = Botan::is_prime(n, rng(), prob);

         output() << n << " is " << (prime ? "probably prime" : "composite") << "\n";
      }
};

BOTAN_REGISTER_COMMAND("is_prime", Is_Prime);

/*
* Factor integers using a combination of trial division by small
* primes, and Pollard's Rho algorithm
*/
class Factor final : public Command {
   public:
      Factor() : Command("factor n") {}

      std::string group() const override { return "numtheory"; }

      std::string description() const override { return "Factor a given integer"; }

      void go() override {
         Botan::BigInt n(get_arg("n"));

         std::vector<Botan::BigInt> factors = factorize(n, rng());
         std::sort(factors.begin(), factors.end());

         output() << n << ": ";
         std::copy(factors.begin(), factors.end(), std::ostream_iterator<Botan::BigInt>(output(), " "));
         output() << std::endl;
      }

   private:
      std::vector<Botan::BigInt> factorize(const Botan::BigInt& n_in, Botan::RandomNumberGenerator& rng) {
         Botan::BigInt n = n_in;
         std::vector<Botan::BigInt> factors = remove_small_factors(n);

         while(n != 1) {
            if(Botan::is_prime(n, rng)) {
               factors.push_back(n);
               break;
            }

            Botan::BigInt a_factor = 0;
            while(a_factor == 0) {
               a_factor = rho(n, rng);
            }

            const auto rho_factored = factorize(a_factor, rng);
            for(const auto& factor : rho_factored) {
               factors.push_back(factor);
            }

            n /= a_factor;
         }

         return factors;
      }

      /*
      * Pollard's Rho algorithm, as described in the MIT algorithms book.
      * Uses Brent's cycle finding
      */
      static Botan::BigInt rho(const Botan::BigInt& n, Botan::RandomNumberGenerator& rng) {
         auto monty_n = std::make_shared<Botan::Montgomery_Params>(n);

         const Botan::Montgomery_Int one(monty_n, monty_n->R1(), false);

         Botan::Montgomery_Int x(monty_n, Botan::BigInt::random_integer(rng, 2, n - 3), false);
         Botan::Montgomery_Int y = x;
         Botan::Montgomery_Int z = one;
         Botan::Montgomery_Int t(monty_n);
         Botan::BigInt d;

         Botan::secure_vector<Botan::word> ws;

         size_t i = 1, k = 2;

         while(true) {
            i++;

            if(i >= 0xFFFF0000)  // bad seed? too slow? bail out
            {
               break;
            }

            x.square_this(ws);  // x = x^2
            x.add(one, ws);

            t = y;
            t.sub(x, ws);

            z.mul_by(t, ws);

            if(i == k || i % 128 == 0) {
               d = Botan::gcd(z.value(), n);
               z = one;

               if(d == n) {
                  // TODO Should rewind here
                  break;
               }

               if(d != 1) {
                  return d;
               }
            }

            if(i == k) {
               y = x;
               k = 2 * k;
            }
         }

         // failed
         return 0;
      }

      // Remove (and return) any small (< 2^16) factors
      static std::vector<Botan::BigInt> remove_small_factors(Botan::BigInt& n) {
         std::vector<Botan::BigInt> factors;

         while(n.is_even()) {
            factors.push_back(2);
            n /= 2;
         }

         for(size_t j = 0; j != Botan::PRIME_TABLE_SIZE; j++) {
            uint16_t prime = Botan::PRIMES[j];
            if(n < prime) {
               break;
            }

            Botan::BigInt x = Botan::gcd(n, prime);

            if(x != 1) {
               n /= x;

               while(x != 1) {
                  x /= prime;
                  factors.push_back(prime);
               }
            }
         }

         return factors;
      }
};

BOTAN_REGISTER_COMMAND("factor", Factor);

}  // namespace Botan_CLI

#endif

1	/*
2	* (C) 2009,2010,2015 Jack Lloyd
3	*
4	* Botan is released under the Simplified BSD License (see license.txt)
5	*/
6
7	#include "cli.h"
8
9	#if defined(BOTAN_HAS_NUMBERTHEORY)
10
11	#include <botan/numthry.h>
12	#include <botan/internal/monty.h>
13	#include <iterator>
14
15	namespace Botan_CLI {
16
17	class Modular_Inverse final : public Command {
18	public:
19	Modular_Inverse() : Command("mod_inverse n mod") {}	6✔
20
21	std::string group() const override { return "numtheory"; }	1✔
22
23	std::string description() const override { return "Calculates a modular inverse"; }	1✔
24
25	void go() override {	2✔
26	const Botan::BigInt n(get_arg("n"));	4✔
27	const Botan::BigInt mod(get_arg("mod"));	4✔
28
29	output() << Botan::inverse_mod(n, mod) << "\n";	4✔
30	}	4✔
31	};
32
33	BOTAN_REGISTER_COMMAND("mod_inverse", Modular_Inverse);	3✔
34
35	class Gen_Prime final : public Command {
36	public:
37	Gen_Prime() : Command("gen_prime --hex --count=1 bits") {}	6✔
38
39	std::string group() const override { return "numtheory"; }	1✔
40
41	std::string description() const override { return "Samples one or more primes"; }	1✔
42
43	void go() override {	2✔
44	const size_t bits = get_arg_sz("bits");	2✔
45	const size_t cnt = get_arg_sz("count");	2✔
46	const bool hex = flag_set("hex");	2✔
47
48	for(size_t i = 0; i != cnt; ++i) {	4✔
49	const Botan::BigInt p = Botan::random_prime(rng(), bits);	2✔
50
51	if(hex) {	2✔
52	output() << "0x" << std::hex << p << "\n";	×
53	} else {
54	output() << p << "\n";	2✔
55	}
56	}	2✔
57	}	2✔
58	};
59
60	BOTAN_REGISTER_COMMAND("gen_prime", Gen_Prime);	3✔
61
62	class Is_Prime final : public Command {
63	public:
64	Is_Prime() : Command("is_prime --prob=56 n") {}	8✔
65
66	std::string group() const override { return "numtheory"; }	1✔
67
68	std::string description() const override { return "Test if the integer n is composite or prime"; }	1✔
69
70	void go() override {	3✔
71	Botan::BigInt n(get_arg("n"));	6✔
72	const size_t prob = get_arg_sz("prob");	3✔
73	const bool prime = Botan::is_prime(n, rng(), prob);	3✔
74
75	output() << n << " is " << (prime ? "probably prime" : "composite") << "\n";	4✔
76	}	3✔
77	};
78
79	BOTAN_REGISTER_COMMAND("is_prime", Is_Prime);	4✔
80
81	/*
82	* Factor integers using a combination of trial division by small
83	* primes, and Pollard's Rho algorithm
84	*/
85	class Factor final : public Command {
86	public:
87	Factor() : Command("factor n") {}	8✔
88
89	std::string group() const override { return "numtheory"; }	1✔
90
91	std::string description() const override { return "Factor a given integer"; }	1✔
92
93	void go() override {	3✔
94	Botan::BigInt n(get_arg("n"));	6✔
95
96	std::vector<Botan::BigInt> factors = factorize(n, rng());	3✔
97	std::sort(factors.begin(), factors.end());	3✔
98
99	output() << n << ": ";	3✔
100	std::copy(factors.begin(), factors.end(), std::ostream_iterator<Botan::BigInt>(output(), " "));	3✔
101	output() << std::endl;	3✔
102	}	6✔
103
104	private:
105	std::vector<Botan::BigInt> factorize(const Botan::BigInt& n_in, Botan::RandomNumberGenerator& rng) {	4✔
106	Botan::BigInt n = n_in;	4✔
107	std::vector<Botan::BigInt> factors = remove_small_factors(n);	4✔
108
109	while(n != 1) {	5✔
110	if(Botan::is_prime(n, rng)) {	4✔
111	factors.push_back(n);	3✔
112	break;	3✔
113	}
114
115	Botan::BigInt a_factor = 0;	1✔
116	while(a_factor == 0) {	2✔
117	a_factor = rho(n, rng);	1✔
118	}
119
120	const auto rho_factored = factorize(a_factor, rng);	1✔
121	for(const auto& factor : rho_factored) {	2✔
122	factors.push_back(factor);	1✔
123	}
124
125	n /= a_factor;	1✔
126	}	2✔
127
128	return factors;	4✔
129	}	4✔
130
131	/*
132	* Pollard's Rho algorithm, as described in the MIT algorithms book.
133	* Uses Brent's cycle finding
134	*/
135	static Botan::BigInt rho(const Botan::BigInt& n, Botan::RandomNumberGenerator& rng) {	1✔
136	auto monty_n = std::make_shared<Botan::Montgomery_Params>(n);	1✔
137
138	const Botan::Montgomery_Int one(monty_n, monty_n->R1(), false);	1✔
139
140	Botan::Montgomery_Int x(monty_n, Botan::BigInt::random_integer(rng, 2, n - 3), false);	5✔
141	Botan::Montgomery_Int y = x;	1✔
142	Botan::Montgomery_Int z = one;	1✔
143	Botan::Montgomery_Int t(monty_n);	1✔
144	Botan::BigInt d;	1✔
145
146	Botan::secure_vector<Botan::word> ws;	1✔
147
148	size_t i = 1, k = 2;	1✔
149
150	while(true) {	147,199✔
151	i++;	147,199✔
152
153	if(i >= 0xFFFF0000) // bad seed? too slow? bail out	147,199✔
154	{
155	break;
156	}
157
158	x.square_this(ws); // x = x^2	147,199✔
159	x.add(one, ws);	147,199✔
160
161	t = y;	147,199✔
162	t.sub(x, ws);	147,199✔
163
164	z.mul_by(t, ws);	147,199✔
165
166	if(i == k \|\| i % 128 == 0) {	147,199✔
167	d = Botan::gcd(z.value(), n);	2,311✔
168	z = one;	1,156✔
169
170	if(d == n) {	1,156✔
171	// TODO Should rewind here
172	break;
173	}
174
175	if(d != 1) {	1,156✔
176	return d;	1✔
177	}
178	}
179
180	if(i == k) {	147,198✔
181	y = x;	17✔
182	k = 2 * k;	17✔
183	}
184	}
185
186	// failed
187	return 0;	×
188	}	2✔
189
190	// Remove (and return) any small (< 2^16) factors
191	static std::vector<Botan::BigInt> remove_small_factors(Botan::BigInt& n) {	4✔
192	std::vector<Botan::BigInt> factors;	4✔
193
194	while(n.is_even()) {	8✔
195	factors.push_back(2);	×
196	n /= 2;	×
197	}
198
199	for(size_t j = 0; j != Botan::PRIME_TABLE_SIZE; j++) {	19,651✔
200	uint16_t prime = Botan::PRIMES[j];	19,648✔
201	if(n < prime) {	19,648✔
202	break;
203	}
204
205	Botan::BigInt x = Botan::gcd(n, prime);	19,647✔
206
207	if(x != 1) {	19,647✔
208	n /= x;	2✔
209
210	while(x != 1) {	4✔
211	x /= prime;	2✔
212	factors.push_back(prime);	4✔
213	}
214	}
215	}	19,647✔
216
217	return factors;	4✔
218	}	×
219	};
220
221	BOTAN_REGISTER_COMMAND("factor", Factor);	4✔
222
223	} // namespace Botan_CLI
224
225	#endif

randombit / botan / 5123321399

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