← Back to branch summary

~ubuntu-branches/debian/sid/botan/sid

« back to all changes in this revision

Viewing changes to src/cli/math.cpp

  • Committer: Package Import Robot
  • Author(s): Laszlo Boszormenyi (GCS)
  • Date: 2018-03-01 22:23:25 UTC
  • mfrom: (1.2.2)
  • Revision ID: package-import@ubuntu.com-20180301222325-7p7vc45gu3hta34d
Tags: 2.4.0-2
* Don't remove .doctrees from the manual if it doesn't exist.
* Don't specify parallel to debhelper.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/cli/math.cpp
 
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/reducer.h>
 
12
#include <botan/numthry.h>
 
13
#include <iterator>
 
14
 
 
15
namespace Botan_CLI {
 
16
 
 
17
class Modular_Inverse final : public Command
 
18
   {
 
19
   public:
 
20
      Modular_Inverse() : Command("mod_inverse n mod") {}
 
21
 
 
22
      void go() override
 
23
         {
 
24
         const Botan::BigInt n(get_arg("n"));
 
25
         const Botan::BigInt mod(get_arg("mod"));
 
26
 
 
27
         output() << Botan::inverse_mod(n, mod) << "\n";
 
28
         }
 
29
   };
 
30
 
 
31
BOTAN_REGISTER_COMMAND("mod_inverse", Modular_Inverse);
 
32
 
 
33
class Gen_Prime final : public Command
 
34
   {
 
35
   public:
 
36
      Gen_Prime() : Command("gen_prime --count=1 bits") {}
 
37
 
 
38
      void go() override
 
39
         {
 
40
         const size_t bits = get_arg_sz("bits");
 
41
         const size_t cnt = get_arg_sz("count");
 
42
 
 
43
         for(size_t i = 0; i != cnt; ++i)
 
44
            {
 
45
            const Botan::BigInt p = Botan::random_prime(rng(), bits);
 
46
            output() << p << "\n";
 
47
            }
 
48
         }
 
49
   };
 
50
 
 
51
BOTAN_REGISTER_COMMAND("gen_prime", Gen_Prime);
 
52
 
 
53
class Is_Prime final : public Command
 
54
   {
 
55
   public:
 
56
      Is_Prime() : Command("is_prime --prob=56 n") {}
 
57
 
 
58
      void go() override
 
59
         {
 
60
         Botan::BigInt n(get_arg("n"));
 
61
         const size_t prob = get_arg_sz("prob");
 
62
         const bool prime = Botan::is_prime(n, rng(), prob);
 
63
 
 
64
         output() << n << " is " << (prime ? "probably prime" : "composite") << "\n";
 
65
         }
 
66
   };
 
67
 
 
68
BOTAN_REGISTER_COMMAND("is_prime", Is_Prime);
 
69
 
 
70
/*
 
71
* Factor integers using a combination of trial division by small
 
72
* primes, and Pollard's Rho algorithm
 
73
*/
 
74
class Factor final : public Command
 
75
   {
 
76
   public:
 
77
      Factor() : Command("factor n") {}
 
78
 
 
79
      void go() override
 
80
         {
 
81
         Botan::BigInt n(get_arg("n"));
 
82
 
 
83
         std::vector<Botan::BigInt> factors = factorize(n, rng());
 
84
         std::sort(factors.begin(), factors.end());
 
85
 
 
86
         output() << n << ": ";
 
87
         std::copy(factors.begin(), factors.end(), std::ostream_iterator<Botan::BigInt>(output(), " "));
 
88
         output() << std::endl;
 
89
         }
 
90
 
 
91
   private:
 
92
 
 
93
      std::vector<Botan::BigInt> factorize(const Botan::BigInt& n_in,
 
94
                                           Botan::RandomNumberGenerator& rng)
 
95
         {
 
96
         Botan::BigInt n = n_in;
 
97
         std::vector<Botan::BigInt> factors = remove_small_factors(n);
 
98
 
 
99
         while(n != 1)
 
100
            {
 
101
            if(Botan::is_prime(n, rng))
 
102
               {
 
103
               factors.push_back(n);
 
104
               break;
 
105
               }
 
106
 
 
107
            Botan::BigInt a_factor = 0;
 
108
            while(a_factor == 0)
 
109
               {
 
110
               a_factor = rho(n, rng);
 
111
               }
 
112
 
 
113
            std::vector<Botan::BigInt> rho_factored = factorize(a_factor, rng);
 
114
            for(size_t j = 0; j != rho_factored.size(); j++)
 
115
               {
 
116
               factors.push_back(rho_factored[j]);
 
117
               }
 
118
 
 
119
            n /= a_factor;
 
120
            }
 
121
 
 
122
         return factors;
 
123
         }
 
124
 
 
125
      /*
 
126
      * Pollard's Rho algorithm, as described in the MIT algorithms book. We
 
127
      * use (x^2+x) mod n instead of (x*2-1) mod n as the random function,
 
128
      * it _seems_ to lead to faster factorization for the values I tried.
 
129
      */
 
130
      Botan::BigInt rho(const Botan::BigInt& n, Botan::RandomNumberGenerator& rng)
 
131
         {
 
132
         Botan::BigInt x = Botan::BigInt::random_integer(rng, 0, n - 1);
 
133
         Botan::BigInt y = x;
 
134
         Botan::BigInt d = 0;
 
135
 
 
136
         Botan::Modular_Reducer mod_n(n);
 
137
 
 
138
         size_t i = 1, k = 2;
 
139
         while(true)
 
140
            {
 
141
            i++;
 
142
 
 
143
            if(i == 0) // overflow, bail out
 
144
               {
 
145
               break;
 
146
               }
 
147
 
 
148
            x = mod_n.multiply((x + 1), x);
 
149
 
 
150
            d = Botan::gcd(y - x, n);
 
151
            if(d != 1 && d != n)
 
152
               {
 
153
               return d;
 
154
               }
 
155
 
 
156
            if(i == k)
 
157
               {
 
158
               y = x;
 
159
               k = 2 * k;
 
160
               }
 
161
            }
 
162
         return 0;
 
163
         }
 
164
 
 
165
      // Remove (and return) any small (< 2^16) factors
 
166
      std::vector<Botan::BigInt> remove_small_factors(Botan::BigInt& n)
 
167
         {
 
168
         std::vector<Botan::BigInt> factors;
 
169
 
 
170
         while(n.is_even())
 
171
            {
 
172
            factors.push_back(2);
 
173
            n /= 2;
 
174
            }
 
175
 
 
176
         for(size_t j = 0; j != Botan::PRIME_TABLE_SIZE; j++)
 
177
            {
 
178
            uint16_t prime = Botan::PRIMES[j];
 
179
            if(n < prime)
 
180
               {
 
181
               break;
 
182
               }
 
183
 
 
184
            Botan::BigInt x = Botan::gcd(n, prime);
 
185
 
 
186
            if(x != 1)
 
187
               {
 
188
               n /= x;
 
189
 
 
190
               while(x != 1)
 
191
                  {
 
192
                  x /= prime;
 
193
                  factors.push_back(prime);
 
194
                  }
 
195
               }
 
196
            }
 
197
 
 
198
         return factors;
 
199
         }
 
200
   };
 
201
 
 
202
BOTAN_REGISTER_COMMAND("factor", Factor);
 
203
 
 
204
}
 
205
 
 
206
#endif