big_int.h
1 /*
2 ** ClanLib SDK
3 ** Copyright (c) 1997-2013 The ClanLib Team
4 **
5 ** This software is provided 'as-is', without any express or implied
6 ** warranty. In no event will the authors be held liable for any damages
7 ** arising from the use of this software.
8 **
9 ** Permission is granted to anyone to use this software for any purpose,
10 ** including commercial applications, and to alter it and redistribute it
11 ** freely, subject to the following restrictions:
12 **
13 ** 1. The origin of this software must not be misrepresented; you must not
14 ** claim that you wrote the original software. If you use this software
15 ** in a product, an acknowledgment in the product documentation would be
16 ** appreciated but is not required.
17 ** 2. Altered source versions must be plainly marked as such, and must not be
18 ** misrepresented as being the original software.
19 ** 3. This notice may not be removed or altered from any source distribution.
20 **
21 ** Note: Some of the libraries ClanLib may link to may have additional
22 ** requirements or restrictions.
23 **
24 ** File Author(s):
25 **
26 ** Mark Page
27 ** Michael J. Fromberger
28 */
29 
30 // This class is based on the original MPI library (not NSS, because of license restrictions) with some modifications.
31 // Some ideas and algorithms are from NSS (Netscape Security Suite). Where they have been used, the function contains a reference note
32 //
33 // Note, since September 2011, I believe the MPI homepage is now: http://spinning-yarns.org/michael/mpi/
34 // Note, since 2013, the MPI page no longer exists, however the internet archive has the details here: http://web.archive.org/web/20100426001741/http://spinning-yarns.org/michael/mpi/README
35 // The license is as follows
36 // This software was written by Michael J. Fromberger,
37 // http://www.dartmouth.edu/~sting/
38 //
39 // See the MPI home page at
40 // http://www.dartmouth.edu/~sting/mpi/
41 //
42 // This software is in the public domain. It is entirely free, and you
43 // may use it and/or redistribute it for whatever purpose you choose;
44 // however, as free software, it is provided without warranty of any
45 // kind, not even the implied warranty of merchantability or fitness for
46 // a particular purpose.
47 
48 
49 #pragma once
50 
51 #include "../api_core.h"
52 #include "../System/cl_platform.h"
53 #include <memory>
54 
55 namespace clan
56 {
59 class BigInt_Impl;
60 
62 class BigInt
63 {
66 public:
68  BigInt();
69 
71  explicit BigInt(ubyte32 value);
72 
74  explicit BigInt(byte32 value);
75 
77  explicit BigInt(ubyte64 value);
78 
80  explicit BigInt(byte64 value);
81 
83  BigInt(const BigInt &other);
84 
86  ~BigInt();
87 
88  BigInt &operator=(const BigInt& other);
89 
93 
94 public:
95 
99 
100 public:
101  void read_unsigned_octets( const unsigned char *input_str, unsigned int input_length);
102 
103  void zero();
104 
105  bool make_prime(unsigned int num_bits);
106 
108  int cmp_z() const;
109 
110  void set_bit(unsigned int bit_number, unsigned int value);
111 
112  int significant_bits() const;
113 
114  void sieve(const ubyte32 *primes, unsigned int num_primes, std::vector<unsigned char> &sieve);
115 
117  ubyte32 mod_d(ubyte32 d) const;
118 
120  void div_d(ubyte32 d, BigInt *q, ubyte32 *r) const;
121 
127  bool fermat(ubyte32 w) const;
128 
133  bool pprime(int nt) const;
134 
136  void set(byte32 d);
137  void set(ubyte32 d);
138  void set(ubyte64 d);
139  void set(byte64 d);
140 
144  void get(ubyte32 &d);
145  void get(ubyte64 &d);
146  void get(byte64 &d);
147  void get(byte32 &d);
148 
156  void exptmod(const BigInt *b, const BigInt *m, BigInt *c) const;
157 
159  void mod(const BigInt *m, BigInt *c) const;
160 
166  void div(const BigInt &b, BigInt *q, BigInt *r) const;
167  void div(ubyte32 d, BigInt *q, BigInt *r) const;
168 
170  BigInt operator + (const BigInt& b);
172 
174  BigInt operator += (const BigInt& b);
176 
178  BigInt operator - (const BigInt& b);
180 
182  BigInt operator -= (const BigInt& b);
184 
186  BigInt operator * (const BigInt& b);
188 
190  BigInt operator *= (const BigInt& b);
192 
194  BigInt operator / (const BigInt& b);
196 
198  BigInt operator /= (const BigInt& b);
200 
202  BigInt operator % (const BigInt& b);
204 
206  BigInt operator %= (const BigInt& b);
208 
209  int cmp(const BigInt *b) const;
210 
212  int cmp_d(ubyte32 d) const;
213 
215  void neg(BigInt *b) const;
216 
217  unsigned int trailing_zeros() const;
218 
219  void sqrmod(const BigInt *m, BigInt *c) const;
220  void sqr(BigInt *b) const;
221 
230  void random();
231 
236  void exch(BigInt *mp2);
237 
242  bool invmod(const BigInt *m, BigInt *c) const;
243 
248  void xgcd(const BigInt *b, BigInt *g, BigInt *x, BigInt *y) const;
249 
251  void abs(BigInt *b) const;
252 
254  bool is_even() const;
255 
257  bool is_odd() const;
258 
260  void div_2(BigInt *c) const;
261 
262  void to_unsigned_octets( unsigned char *output_str, unsigned int output_length) const;
263 
264  int unsigned_octet_size() const;
268 private:
269  std::unique_ptr<BigInt_Impl> impl;
270 
272 
273 };
274 
275 }
276 
278 
void div(const BigInt &b, BigInt *q, BigInt *r) const
Compute q = a / b and r = a mod b.
BigInt & operator=(const BigInt &other)
BigInt operator-(const BigInt &b)
Compute result = this - b.
void sqr(BigInt *b) const
BigInt operator+=(const BigInt &b)
Compute this += b.
void exptmod(const BigInt *b, const BigInt *m, BigInt *c) const
Compute c = (a ** b) mod m.
void set_bit(unsigned int bit_number, unsigned int value)
bool pprime(int nt) const
Performs nt iteration of the Miller-Rabin probabilistic primality test on a.
int unsigned_octet_size() const
bool make_prime(unsigned int num_bits)
void to_unsigned_octets(unsigned char *output_str, unsigned int output_length) const
BigInt operator/(const BigInt &b)
Compute result = this / b.
bool is_odd() const
Returns a true if number is odd.
unsigned long long ubyte64
Definition: cl_platform.h:66
int cmp_z() const
Compare a <=> 0. Returns <0 if a<0, 0 if a=0, >0 if a>0.
void exch(BigInt *mp2)
Exchange mp1 and mp2 without allocating any intermediate memory.
BigInt operator*=(const BigInt &b)
Compute this *= b.
void mod(const BigInt *m, BigInt *c) const
Compute c = a (mod m). Result will always be 0 <= c < m.
void div_2(BigInt *c) const
Compute c = a / 2, disregarding the remainder.
void read_unsigned_octets(const unsigned char *input_str, unsigned int input_length)
ubyte32 mod_d(ubyte32 d) const
Compute c = a (mod d). Result will always be 0 <= c < d.
bool fermat(ubyte32 w) const
Using w as a witness, try pseudo-primality testing based on Fermat's little theorem.
void sieve(const ubyte32 *primes, unsigned int num_primes, std::vector< unsigned char > &sieve)
void sqrmod(const BigInt *m, BigInt *c) const
int byte32
Definition: cl_platform.h:63
long long byte64
Definition: cl_platform.h:65
int cmp(const BigInt *b) const
bool is_even() const
Returns a true if number is even.
BigInt operator%=(const BigInt &b)
Compute this %= b.
void div_d(ubyte32 d, BigInt *q, ubyte32 *r) const
Compute the quotient q = a / d and remainder r = a mod d, for a single digit d. Respects the sign of ...
void xgcd(const BigInt *b, BigInt *g, BigInt *x, BigInt *y) const
Compute g = (a, b) and values x and y satisfying Bezout's identity.
BigInt operator*(const BigInt &b)
Compute result = this * b.
int significant_bits() const
bool invmod(const BigInt *m, BigInt *c) const
Compute c = a^-1 (mod m), if there is an inverse for a (mod m).
BigInt operator%(const BigInt &b)
Compute result = this % b.
unsigned int trailing_zeros() const
BigInt()
Constructs a big integer (initialised to zero)
BigInt operator/=(const BigInt &b)
Compute this /= b.
BigInt operator+(const BigInt &b)
Compute result = this + b.
void random()
Assigns a random value to a.
int cmp_d(ubyte32 d) const
Compare a <=> d. Returns <0 if a<d, 0 if a=d, >0 if a>d.
void neg(BigInt *b) const
Compute b = -a. 'a' and 'b' may be identical.
unsigned int ubyte32
Definition: cl_platform.h:64
void abs(BigInt *b) const
Compute b = |a|. 'a' and 'b' may be identical.
BigInt operator-=(const BigInt &b)
Compute this -= b.
~BigInt()
Destructor.
Big Integer class.
Definition: big_int.h:62
void set(byte32 d)
Sets a value.