File: integer.h

package info (click to toggle)
libcrypto++ 5.6.4-7
  • links: PTS
  • area: main
  • in suites: stretch
  • size: 11,892 kB
  • ctags: 13,256
  • sloc: cpp: 69,231; sh: 4,117; asm: 4,090; makefile: 363
file content (618 lines) | stat: -rw-r--r-- 25,841 bytes parent folder | download | duplicates (3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
// integer.h - written and placed in the public domain by Wei Dai

//! \file integer.h
//! \brief Multiple precision integer with arithmetic operations
//! \details The Integer class can represent positive and negative integers
//!   with absolute value less than (256**sizeof(word))<sup>(256**sizeof(int))</sup>.
//! \details Internally, the library uses a sign magnitude representation, and the class
//!   has two data members. The first is a IntegerSecBlock (a SecBlock<word>) and it is
//!   used to hold the representation. The second is a Sign, and its is used to track
//!   the sign of the Integer.

#ifndef CRYPTOPP_INTEGER_H
#define CRYPTOPP_INTEGER_H

#include "cryptlib.h"
#include "secblock.h"
#include "stdcpp.h"

#include <iosfwd>

NAMESPACE_BEGIN(CryptoPP)

//! \struct InitializeInteger
//! Performs static intialization of the Integer class
struct InitializeInteger
{
	InitializeInteger();
};

// http://github.com/weidai11/cryptopp/issues/256
#if defined(CRYPTOPP_WORD128_AVAILABLE)
typedef SecBlock<word, AllocatorWithCleanup<word, true> > IntegerSecBlock;
#else
typedef SecBlock<word, AllocatorWithCleanup<word, CRYPTOPP_BOOL_X86> > IntegerSecBlock;
#endif

//! \brief Multiple precision integer with arithmetic operations
//! \details The Integer class can represent positive and negative integers
//!   with absolute value less than (256**sizeof(word))<sup>(256**sizeof(int))</sup>.
//! \details Internally, the library uses a sign magnitude representation, and the class
//!   has two data members. The first is a IntegerSecBlock (a SecBlock<word>) and it is
//!   used to hold the representation. The second is a Sign, and its is used to track
//!   the sign of the Integer.
//! \nosubgrouping
class CRYPTOPP_DLL Integer : private InitializeInteger, public ASN1Object
{
public:
	//! \name ENUMS, EXCEPTIONS, and TYPEDEFS
	//@{
		//! \brief Exception thrown when division by 0 is encountered
		class DivideByZero : public Exception
		{
		public:
			DivideByZero() : Exception(OTHER_ERROR, "Integer: division by zero") {}
		};

		//! \brief Exception thrown when a random number cannot be found that
		//!   satisfies the condition
		class RandomNumberNotFound : public Exception
		{
		public:
			RandomNumberNotFound() : Exception(OTHER_ERROR, "Integer: no integer satisfies the given parameters") {}
		};

		//! \enum Sign
		//! \brief Used internally to represent the integer
		//! \details Sign is used internally to represent the integer. It is also used in a few API functions.
		//! \sa Signedness
		enum Sign {
			//! \brief the value is positive or 0
			POSITIVE=0,
			//! \brief the value is negative
			NEGATIVE=1};

		//! \enum Signedness
		//! \brief Used when importing and exporting integers
		//! \details Signedness is usually used in API functions.
		//! \sa Sign
		enum Signedness {
			//! \brief an unsigned value
			UNSIGNED,
			//! \brief a signed value
			SIGNED};

		//! \enum RandomNumberType
		//! \brief Properties of a random integer
		enum RandomNumberType {
			//! \brief a number with no special properties
			ANY,
			//! \brief a number which is probabilistically prime
			PRIME};
	//@}

	//! \name CREATORS
	//@{
		//! \brief Creates the zero integer
		Integer();

		//! copy constructor
		Integer(const Integer& t);

		//! \brief Convert from signed long
		Integer(signed long value);

		//! \brief Convert from lword
		//! \param sign enumeration indicating Sign
		//! \param value the long word
		Integer(Sign sign, lword value);

		//! \brief Convert from two words
		//! \param sign enumeration indicating Sign
		//! \param highWord the high word
		//! \param lowWord the low word
		Integer(Sign sign, word highWord, word lowWord);

		//! \brief Convert from a C-string
		//! \param str C-string value
		//! \param order byte order
		//! \details \p str can be in base 2, 8, 10, or 16. Base is determined by a case
		//!   insensitive suffix of 'h', 'o', or 'b'.  No suffix means base 10.
		//! \details Byte order was added at Crypto++ 5.7 to allow use of little-endian
		//!   integers with curve25519, Poly1305 and Microsoft CAPI.
		explicit Integer(const char *str);
		explicit Integer(const char *str, ByteOrder order);

		//! \brief Convert from a wide C-string
		//! \param str wide C-string value
		//! \param order byte order
		//! \details \p str can be in base 2, 8, 10, or 16. Base is determined by a case
		//!   insensitive suffix of 'h', 'o', or 'b'.  No suffix means base 10.
		//! \details Byte order was added at Crypto++ 5.7 to allow use of little-endian
		//!   integers with curve25519, Poly1305 and Microsoft CAPI.
		explicit Integer(const wchar_t *str);
		explicit Integer(const wchar_t *str, ByteOrder order);

		//! \brief Convert from a big-endian byte array
		//! \param encodedInteger big-endian byte array
		//! \param byteCount length of the byte array
		//! \param sign enumeration indicating Signedness
		//! \param order byte order
		//! \details Byte order was added at Crypto++ 5.7 to allow use of little-endian
		//!   integers with curve25519, Poly1305 and Microsoft CAPI.
		Integer(const byte *encodedInteger, size_t byteCount, Signedness sign=UNSIGNED);
		Integer(const byte *encodedInteger, size_t byteCount, Signedness sign, ByteOrder order);

		//! \brief Convert from a big-endian array
		//! \param bt BufferedTransformation object with big-endian byte array
		//! \param byteCount length of the byte array
		//! \param sign enumeration indicating Signedness
		//! \param order byte order
		//! \details Byte order was added at Crypto++ 5.7 to allow use of little-endian
		//!   integers with curve25519, Poly1305 and Microsoft CAPI.
		Integer(BufferedTransformation &bt, size_t byteCount, Signedness sign=UNSIGNED);
		Integer(BufferedTransformation &bt, size_t byteCount, Signedness sign, ByteOrder order);

		//! \brief Convert from a BER encoded byte array
		//! \param bt BufferedTransformation object with BER encoded byte array
		explicit Integer(BufferedTransformation &bt);

		//! \brief Create a random integer
		//! \param rng RandomNumberGenerator used to generate material
		//! \param bitCount the number of bits in the resulting integer
		//! \details The random integer created is uniformly distributed over <tt>[0, 2<sup>bitCount</sup>]</tt>.
		Integer(RandomNumberGenerator &rng, size_t bitCount);

		//! \brief Integer representing 0
		//! \returns an Integer representing 0
		//! \details Zero() avoids calling constructors for frequently used integers
		static const Integer & CRYPTOPP_API Zero();
		//! \brief Integer representing 1
		//! \returns an Integer representing 1
		//! \details One() avoids calling constructors for frequently used integers
		static const Integer & CRYPTOPP_API One();
		//! \brief Integer representing 2
		//! \returns an Integer representing 2
		//! \details Two() avoids calling constructors for frequently used integers
		static const Integer & CRYPTOPP_API Two();

		//! \brief Create a random integer of special form
		//! \param rng RandomNumberGenerator used to generate material
		//! \param min the minimum value
		//! \param max the maximum value
		//! \param rnType RandomNumberType to specify the type
		//! \param equiv the equivalence class based on the parameter \p mod
		//! \param mod the modulus used to reduce the equivalence class
		//! \throw RandomNumberNotFound if the set is empty.
		//! \details Ideally, the random integer created should be uniformly distributed
		//!   over <tt>{x | min \<= x \<= max</tt> and \p x is of rnType and <tt>x \% mod == equiv}</tt>.
		//!   However the actual distribution may not be uniform because sequential
		//!   search is used to find an appropriate number from a random starting
		//!   point.
		//! \details May return (with very small probability) a pseudoprime when a prime
		//!   is requested and <tt>max \> lastSmallPrime*lastSmallPrime</tt>. \p lastSmallPrime
		//!   is declared in nbtheory.h.
		Integer(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType=ANY, const Integer &equiv=Zero(), const Integer &mod=One());

		//! \brief Exponentiates to a power of 2
		//! \returns the Integer 2<sup>e</sup>
		//! \sa a_times_b_mod_c() and a_exp_b_mod_c()
		static Integer CRYPTOPP_API Power2(size_t e);
	//@}

	//! \name ENCODE/DECODE
	//@{
		//! \brief The minimum number of bytes to encode this integer
		//! \param sign enumeration indicating Signedness
		//! \note The MinEncodedSize() of 0 is 1.
		size_t MinEncodedSize(Signedness sign=UNSIGNED) const;

		//! \brief Encode in big-endian format
		//! \param output big-endian byte array
		//! \param outputLen length of the byte array
		//! \param sign enumeration indicating Signedness
		//! \details Unsigned means encode absolute value, signed means encode two's complement if negative.
		//! \details outputLen can be used to ensure an Integer is encoded to an exact size (rather than a
		//!   minimum size). An exact size is useful, for example, when encoding to a field element size.
		void Encode(byte *output, size_t outputLen, Signedness sign=UNSIGNED) const;

		//! \brief Encode in big-endian format
		//! \param bt BufferedTransformation object
		//! \param outputLen length of the encoding
		//! \param sign enumeration indicating Signedness
		//! \details Unsigned means encode absolute value, signed means encode two's complement if negative.
		//! \details outputLen can be used to ensure an Integer is encoded to an exact size (rather than a
		//!   minimum size). An exact size is useful, for example, when encoding to a field element size.
		void Encode(BufferedTransformation &bt, size_t outputLen, Signedness sign=UNSIGNED) const;

		//! \brief Encode in DER format
		//! \param bt BufferedTransformation object
		//! \details Encodes the Integer using Distinguished Encoding Rules
		//!   The result is placed into a BufferedTransformation object
		void DEREncode(BufferedTransformation &bt) const;

		//! encode absolute value as big-endian octet string
		//! \param bt BufferedTransformation object
		//! \param length the number of mytes to decode
		void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const;

		//! \brief Encode absolute value in OpenPGP format
		//! \param output big-endian byte array
		//! \param bufferSize length of the byte array
		//! \returns length of the output
		//! \details OpenPGPEncode places result into a BufferedTransformation object and returns the
		//!   number of bytes used for the encoding
		size_t OpenPGPEncode(byte *output, size_t bufferSize) const;

		//! \brief Encode absolute value in OpenPGP format
		//! \param bt BufferedTransformation object
		//! \returns length of the output
		//! \details OpenPGPEncode places result into a BufferedTransformation object and returns the
		//!   number of bytes used for the encoding
		size_t OpenPGPEncode(BufferedTransformation &bt) const;

		//! \brief Decode from big-endian byte array
		//! \param input big-endian byte array
		//! \param inputLen length of the byte array
		//! \param sign enumeration indicating Signedness
		void Decode(const byte *input, size_t inputLen, Signedness sign=UNSIGNED);

		//! \brief Decode nonnegative value from big-endian byte array
		//! \param bt BufferedTransformation object
		//! \param inputLen length of the byte array
		//! \param sign enumeration indicating Signedness
		//! \note <tt>bt.MaxRetrievable() \>= inputLen</tt>.
		void Decode(BufferedTransformation &bt, size_t inputLen, Signedness sign=UNSIGNED);

		//! \brief Decode from BER format
		//! \param input big-endian byte array
		//! \param inputLen length of the byte array
		void BERDecode(const byte *input, size_t inputLen);

		//! \brief Decode from BER format
		//! \param bt BufferedTransformation object
		void BERDecode(BufferedTransformation &bt);

		//! \brief Decode nonnegative value from big-endian octet string
		//! \param bt BufferedTransformation object
		//! \param length length of the byte array
		void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length);

		//! \brief Exception thrown when an error is encountered decoding an OpenPGP integer
		class OpenPGPDecodeErr : public Exception
		{
		public:
			OpenPGPDecodeErr() : Exception(INVALID_DATA_FORMAT, "OpenPGP decode error") {}
		};

		//! \brief Decode from OpenPGP format
		//! \param input big-endian byte array
		//! \param inputLen length of the byte array
		void OpenPGPDecode(const byte *input, size_t inputLen);
		//! \brief Decode from OpenPGP format
		//! \param bt BufferedTransformation object
		void OpenPGPDecode(BufferedTransformation &bt);
	//@}

	//! \name ACCESSORS
	//@{
		//! \brief Determines if the Integer is convertable to Long
		//! \returns true if *this can be represented as a signed long
		//! \sa ConvertToLong()
		bool IsConvertableToLong() const;
		//! \brief Convert the Integer to Long
		//! \return equivalent signed long if possible, otherwise undefined
		//! \sa IsConvertableToLong()
		signed long ConvertToLong() const;

		//! \brief Determines the number of bits required to represent the Integer
		//! \returns number of significant bits = floor(log2(abs(*this))) + 1
		unsigned int BitCount() const;
		//! \brief Determines the number of bytes required to represent the Integer
		//! \returns number of significant bytes = ceiling(BitCount()/8)
		unsigned int ByteCount() const;
		//! \brief Determines the number of words required to represent the Integer
		//! \returns number of significant words = ceiling(ByteCount()/sizeof(word))
		unsigned int WordCount() const;

		//! \brief Provides the i-th bit of the Integer
		//! \returns the i-th bit, i=0 being the least significant bit
		bool GetBit(size_t i) const;
		//! \brief Provides the i-th byte of the Integer
		//! \returns the i-th byte
		byte GetByte(size_t i) const;
		//! \brief Provides the low order bits of the Integer
		//! \returns n lowest bits of *this >> i
		lword GetBits(size_t i, size_t n) const;

		//! \brief Determines if the Integer is 0
		//! \returns true if the Integer is 0, false otherwise
		bool IsZero() const {return !*this;}
		//! \brief Determines if the Integer is non-0
		//! \returns true if the Integer is non-0, false otherwise
		bool NotZero() const {return !IsZero();}
		//! \brief Determines if the Integer is negative
		//! \returns true if the Integer is negative, false otherwise
		bool IsNegative() const {return sign == NEGATIVE;}
		//! \brief Determines if the Integer is non-negative
		//! \returns true if the Integer is non-negative, false otherwise
		bool NotNegative() const {return !IsNegative();}
		//! \brief Determines if the Integer is positive
		//! \returns true if the Integer is positive, false otherwise
		bool IsPositive() const {return NotNegative() && NotZero();}
		//! \brief Determines if the Integer is non-positive
		//! \returns true if the Integer is non-positive, false otherwise
		bool NotPositive() const {return !IsPositive();}
		//! \brief Determines if the Integer is even parity
		//! \returns true if the Integer is even, false otherwise
		bool IsEven() const {return GetBit(0) == 0;}
		//! \brief Determines if the Integer is odd parity
		//! \returns true if the Integer is odd, false otherwise
		bool IsOdd() const	{return GetBit(0) == 1;}
	//@}

	//! \name MANIPULATORS
	//@{
		//!
		Integer&  operator=(const Integer& t);

		//!
		Integer&  operator+=(const Integer& t);
		//!
		Integer&  operator-=(const Integer& t);
		//!
		//! \sa a_times_b_mod_c() and a_exp_b_mod_c()
		Integer&  operator*=(const Integer& t)	{return *this = Times(t);}
		//!
		Integer&  operator/=(const Integer& t)	{return *this = DividedBy(t);}
		//!
		//! \sa a_times_b_mod_c() and a_exp_b_mod_c()
		Integer&  operator%=(const Integer& t)	{return *this = Modulo(t);}
		//!
		Integer&  operator/=(word t)  {return *this = DividedBy(t);}
		//!
		//! \sa a_times_b_mod_c() and a_exp_b_mod_c()
		Integer&  operator%=(word t)  {return *this = Integer(POSITIVE, 0, Modulo(t));}

		//!
		Integer&  operator<<=(size_t);
		//!
		Integer&  operator>>=(size_t);

		//! \brief Set this Integer to random integer
		//! \param rng RandomNumberGenerator used to generate material
		//! \param bitCount the number of bits in the resulting integer
		//! \details The random integer created is uniformly distributed over <tt>[0, 2<sup>bitCount</sup>]</tt>.
		void Randomize(RandomNumberGenerator &rng, size_t bitCount);

		//! \brief Set this Integer to random integer
		//! \param rng RandomNumberGenerator used to generate material
		//! \param min the minimum value
		//! \param max the maximum value
		//! \details The random integer created is uniformly distributed over <tt>[min, max]</tt>.
		void Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max);

		//! \brief Set this Integer to random integer of special form
		//! \param rng RandomNumberGenerator used to generate material
		//! \param min the minimum value
		//! \param max the maximum value
		//! \param rnType RandomNumberType to specify the type
		//! \param equiv the equivalence class based on the parameter \p mod
		//! \param mod the modulus used to reduce the equivalence class
		//! \throw RandomNumberNotFound if the set is empty.
		//! \details Ideally, the random integer created should be uniformly distributed
		//!   over <tt>{x | min \<= x \<= max</tt> and \p x is of rnType and <tt>x \% mod == equiv}</tt>.
		//!   However the actual distribution may not be uniform because sequential
		//!   search is used to find an appropriate number from a random starting
		//!   point.
		//! \details May return (with very small probability) a pseudoprime when a prime
		//!   is requested and <tt>max \> lastSmallPrime*lastSmallPrime</tt>. \p lastSmallPrime
		//!   is declared in nbtheory.h.
		bool Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType, const Integer &equiv=Zero(), const Integer &mod=One());

		bool GenerateRandomNoThrow(RandomNumberGenerator &rng, const NameValuePairs &params = g_nullNameValuePairs);
		void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &params = g_nullNameValuePairs)
		{
			if (!GenerateRandomNoThrow(rng, params))
				throw RandomNumberNotFound();
		}

		//! \brief Set the n-th bit to value
		//! \details 0-based numbering.
		void SetBit(size_t n, bool value=1);

		//! \brief Set the n-th byte to value
		//! \details 0-based numbering.
		void SetByte(size_t n, byte value);

		//! \brief Reverse the Sign of the Integer
		void Negate();

		//! \brief Sets the Integer to positive
		void SetPositive() {sign = POSITIVE;}

		//! \brief Sets the Integer to negative
		void SetNegative() {if (!!(*this)) sign = NEGATIVE;}

		//! \brief Swaps this Integer with another Integer
		void swap(Integer &a);
	//@}

	//! \name UNARY OPERATORS
	//@{
		//!
		bool		operator!() const;
		//!
		Integer 	operator+() const {return *this;}
		//!
		Integer 	operator-() const;
		//!
		Integer&	operator++();
		//!
		Integer&	operator--();
		//!
		Integer 	operator++(int) {Integer temp = *this; ++*this; return temp;}
		//!
		Integer 	operator--(int) {Integer temp = *this; --*this; return temp;}
	//@}

	//! \name BINARY OPERATORS
	//@{
		//! \brief Perform signed comparison
		//! \param a the Integer to comapre
		//!   \retval -1 if <tt>*this < a</tt>
		//!   \retval  0 if <tt>*this = a</tt>
		//!   \retval  1 if <tt>*this > a</tt>
		int Compare(const Integer& a) const;

		//!
		Integer Plus(const Integer &b) const;
		//!
		Integer Minus(const Integer &b) const;
		//!
		//! \sa a_times_b_mod_c() and a_exp_b_mod_c()
		Integer Times(const Integer &b) const;
		//!
		Integer DividedBy(const Integer &b) const;
		//!
		//! \sa a_times_b_mod_c() and a_exp_b_mod_c()
		Integer Modulo(const Integer &b) const;
		//!
		Integer DividedBy(word b) const;
		//!
		//! \sa a_times_b_mod_c() and a_exp_b_mod_c()
		word Modulo(word b) const;

		//!
		Integer operator>>(size_t n) const	{return Integer(*this)>>=n;}
		//!
		Integer operator<<(size_t n) const	{return Integer(*this)<<=n;}
	//@}

	//! \name OTHER ARITHMETIC FUNCTIONS
	//@{
		//!
		Integer AbsoluteValue() const;
		//!
		Integer Doubled() const {return Plus(*this);}
		//!
		//! \sa a_times_b_mod_c() and a_exp_b_mod_c()
		Integer Squared() const {return Times(*this);}
		//! extract square root, if negative return 0, else return floor of square root
		Integer SquareRoot() const;
		//! return whether this integer is a perfect square
		bool IsSquare() const;

		//! is 1 or -1
		bool IsUnit() const;
		//! return inverse if 1 or -1, otherwise return 0
		Integer MultiplicativeInverse() const;

		//! calculate r and q such that (a == d*q + r) && (0 <= r < abs(d))
		static void CRYPTOPP_API Divide(Integer &r, Integer &q, const Integer &a, const Integer &d);
		//! use a faster division algorithm when divisor is short
		static void CRYPTOPP_API Divide(word &r, Integer &q, const Integer &a, word d);

		//! returns same result as Divide(r, q, a, Power2(n)), but faster
		static void CRYPTOPP_API DivideByPowerOf2(Integer &r, Integer &q, const Integer &a, unsigned int n);

		//! greatest common divisor
		static Integer CRYPTOPP_API Gcd(const Integer &a, const Integer &n);
		//! calculate multiplicative inverse of *this mod n
		//! \sa a_times_b_mod_c() and a_exp_b_mod_c()
		Integer InverseMod(const Integer &n) const;
		//!
		//! \sa a_times_b_mod_c() and a_exp_b_mod_c()
		word InverseMod(word n) const;
	//@}

	//! \name INPUT/OUTPUT
	//@{
		//! \brief Extraction operator
		//! \param in a reference to a std::istream
		//! \param a a reference to an Integer
		//! \returns a reference to a std::istream reference
		friend CRYPTOPP_DLL std::istream& CRYPTOPP_API operator>>(std::istream& in, Integer &a);
		//!
		//! \brief Insertion operator
		//! \param out a reference to a std::ostream
		//! \param a a constant reference to an Integer
		//! \returns a reference to a std::ostream reference
		//! \details The output integer responds to std::hex, std::oct, std::hex, std::upper and
		//!   std::lower. The output includes the suffix \a \b h (for hex), \a \b . (\a \b dot, for dec)
		//!   and \a \b o (for octal). There is currently no way to supress the suffix.
		//! \details If you want to print an Integer without the suffix or using an arbitrary base, then
		//!   use IntToString<Integer>().
		//! \sa IntToString<Integer>
		friend CRYPTOPP_DLL std::ostream& CRYPTOPP_API operator<<(std::ostream& out, const Integer &a);
	//@}

#ifndef CRYPTOPP_DOXYGEN_PROCESSING
	//! modular multiplication
	CRYPTOPP_DLL friend Integer CRYPTOPP_API a_times_b_mod_c(const Integer &x, const Integer& y, const Integer& m);
	//! modular exponentiation
	CRYPTOPP_DLL friend Integer CRYPTOPP_API a_exp_b_mod_c(const Integer &x, const Integer& e, const Integer& m);
#endif

private:

	Integer(word value, size_t length);
	int PositiveCompare(const Integer &t) const;

	IntegerSecBlock reg;
	Sign sign;

#ifndef CRYPTOPP_DOXYGEN_PROCESSING
	friend class ModularArithmetic;
	friend class MontgomeryRepresentation;
	friend class HalfMontgomeryRepresentation;

	friend void PositiveAdd(Integer &sum, const Integer &a, const Integer &b);
	friend void PositiveSubtract(Integer &diff, const Integer &a, const Integer &b);
	friend void PositiveMultiply(Integer &product, const Integer &a, const Integer &b);
	friend void PositiveDivide(Integer &remainder, Integer &quotient, const Integer &dividend, const Integer &divisor);
#endif
};

//!
inline bool operator==(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)==0;}
//!
inline bool operator!=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)!=0;}
//!
inline bool operator> (const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)> 0;}
//!
inline bool operator>=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)>=0;}
//!
inline bool operator< (const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)< 0;}
//!
inline bool operator<=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)<=0;}
//!
inline CryptoPP::Integer operator+(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Plus(b);}
//!
inline CryptoPP::Integer operator-(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Minus(b);}
//!
//! \sa a_times_b_mod_c() and a_exp_b_mod_c()
inline CryptoPP::Integer operator*(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Times(b);}
//!
inline CryptoPP::Integer operator/(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.DividedBy(b);}
//!
//! \sa a_times_b_mod_c() and a_exp_b_mod_c()
inline CryptoPP::Integer operator%(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Modulo(b);}
//!
inline CryptoPP::Integer operator/(const CryptoPP::Integer &a, CryptoPP::word b) {return a.DividedBy(b);}
//!
//! \sa a_times_b_mod_c() and a_exp_b_mod_c()
inline CryptoPP::word    operator%(const CryptoPP::Integer &a, CryptoPP::word b) {return a.Modulo(b);}

NAMESPACE_END

#ifndef __BORLANDC__
NAMESPACE_BEGIN(std)
inline void swap(CryptoPP::Integer &a, CryptoPP::Integer &b)
{
	a.swap(b);
}
NAMESPACE_END
#endif

#endif