39195077976

Committed 18 Oct 2026 05:18PM UTC coverage: 92.258% (+0.06%) from 92.195%

Build # 39195077976

Build Type

push

github

Committed by

randombit

Commit Message

Update release notes [ci skip]

Coverage Stats

137358 of 148884 relevant lines covered (92.26%)

8967647.39 hits per line

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

95.73

/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/mod_inv.h>
   #include <botan/internal/monty.h>
   #include <algorithm>

namespace Botan_CLI {

namespace {

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"));

         if(auto inv = Botan::inverse_mod_general(n, mod)) {
            output() << *inv << "\n";
         } else {
            output() << "No modular inverse exists\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() << 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 {
         const 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 {
         const Botan::BigInt n(get_arg("n"));

         if(n.is_negative() || n < 2) {
            throw CLI_Usage_Error("Cannot factor integers less than 2");
         }

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

         output() << n << ":";
         for(const auto& factor : factors) {
            output() << " " << factor;
         }
         output() << "\n";
      }

   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;
            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) {
         const Botan::Montgomery_Params monty_n(n);

         const auto one = Botan::Montgomery_Int::one(monty_n);

         const auto two = Botan::BigInt::from_s32(2);
         const auto three = Botan::BigInt::from_s32(3);
         Botan::Montgomery_Int x(monty_n, Botan::BigInt::random_integer(rng, two, n - three), 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;
         size_t k = 2;

         while(true) {
            i++;

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

            x.square_this_n_times(ws, 1);  // x = x^2
            x = x + one;

            t = y - x;

            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 Botan::BigInt::zero();
      }

      // 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(Botan::BigInt::from_s32(2));
            n >>= 1;
         }

         for(size_t j = 0; j != Botan::PRIME_TABLE_SIZE; j++) {
            const auto prime = Botan::BigInt::from_s32(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

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

randombit / botan / 39195077976

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