multiple precision integer and basic arithmetics More...
#include <integer.h>
Classes | |
class | DivideByZero |
division by zero exception More... | |
class | OpenPGPDecodeErr |
class | RandomNumberNotFound |
Public Member Functions | |
virtual void | BEREncode (BufferedTransformation &bt) const |
encode this object into a BufferedTransformation, using BER | |
Friends | |
class | ModularArithmetic |
class | MontgomeryRepresentation |
class | HalfMontgomeryRepresentation |
void | PositiveAdd (Integer &sum, const Integer &a, const Integer &b) |
void | PositiveSubtract (Integer &diff, const Integer &a, const Integer &b) |
void | PositiveMultiply (Integer &product, const Integer &a, const Integer &b) |
void | PositiveDivide (Integer &remainder, Integer "ient, const Integer ÷nd, const Integer &divisor) |
ENUMS, EXCEPTIONS, and TYPEDEFS | |
| |
enum | Sign { POSITIVE = 0, NEGATIVE = 1 } |
enum | Signedness { UNSIGNED, SIGNED } |
enum | RandomNumberType { ANY, PRIME } |
OTHER ARITHMETIC FUNCTIONS | |
| |
Integer | a_times_b_mod_c (const Integer &x, const Integer &y, const Integer &m) |
modular multiplication | |
Integer | a_exp_b_mod_c (const Integer &x, const Integer &e, const Integer &m) |
modular exponentiation | |
Integer | AbsoluteValue () const |
Integer | Doubled () const |
Integer | Squared () const |
Integer | SquareRoot () const |
extract square root, if negative return 0, else return floor of square root | |
bool | IsSquare () const |
return whether this integer is a perfect square | |
bool | IsUnit () const |
is 1 or -1 | |
Integer | MultiplicativeInverse () const |
return inverse if 1 or -1, otherwise return 0 | |
Integer | InverseMod (const Integer &n) const |
calculate multiplicative inverse of *this mod n | |
word | InverseMod (word n) const |
static void | Divide (Integer &r, Integer &q, const Integer &a, const Integer &d) |
calculate r and q such that (a == d*q + r) && (0 <= r < abs(d)) | |
static void | Divide (word &r, Integer &q, const Integer &a, word d) |
use a faster division algorithm when divisor is short | |
static void | DivideByPowerOf2 (Integer &r, Integer &q, const Integer &a, unsigned int n) |
returns same result as Divide(r, q, a, Power2(n)), but faster | |
static Integer | Gcd (const Integer &a, const Integer &n) |
greatest common divisor | |
INPUT/OUTPUT | |
| |
std::istream & | operator>> (std::istream &in, Integer &a) |
std::ostream & | operator<< (std::ostream &out, const Integer &a) |
CREATORS | |
| |
Integer () | |
creates the zero integer | |
Integer (const Integer &t) | |
copy constructor | |
Integer (signed long value) | |
convert from signed long | |
Integer (Sign s, lword value) | |
convert from lword | |
Integer (Sign s, word highWord, word lowWord) | |
convert from two words | |
Integer (const char *str) | |
convert from string | |
Integer (const wchar_t *str) | |
Integer (const byte *encodedInteger, size_t byteCount, Signedness s=UNSIGNED) | |
convert from big-endian byte array | |
Integer (BufferedTransformation &bt, size_t byteCount, Signedness s=UNSIGNED) | |
convert from big-endian form stored in a BufferedTransformation | |
Integer (BufferedTransformation &bt) | |
convert from BER encoded byte array stored in a BufferedTransformation object | |
Integer (RandomNumberGenerator &rng, size_t bitcount) | |
create a random integer | |
Integer (RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType=ANY, const Integer &equiv=Zero(), const Integer &mod=One()) | |
create a random integer of special type | |
static const Integer & | Zero () |
avoid calling constructors for these frequently used integers | |
static const Integer & | One () |
avoid calling constructors for these frequently used integers | |
static const Integer & | Two () |
avoid calling constructors for these frequently used integers | |
static Integer | Power2 (size_t e) |
return the integer 2**e | |
ENCODE/DECODE | |
| |
size_t | MinEncodedSize (Signedness=UNSIGNED) const |
minimum number of bytes to encode this integer | |
void | Encode (byte *output, size_t outputLen, Signedness=UNSIGNED) const |
encode in big-endian format | |
void | Encode (BufferedTransformation &bt, size_t outputLen, Signedness=UNSIGNED) const |
void | DEREncode (BufferedTransformation &bt) const |
encode using Distinguished Encoding Rules, put result into a BufferedTransformation object | |
void | DEREncodeAsOctetString (BufferedTransformation &bt, size_t length) const |
encode absolute value as big-endian octet string | |
size_t | OpenPGPEncode (byte *output, size_t bufferSize) const |
encode absolute value in OpenPGP format, return length of output | |
size_t | OpenPGPEncode (BufferedTransformation &bt) const |
encode absolute value in OpenPGP format, put result into a BufferedTransformation object | |
void | Decode (const byte *input, size_t inputLen, Signedness=UNSIGNED) |
void | Decode (BufferedTransformation &bt, size_t inputLen, Signedness=UNSIGNED) |
void | BERDecode (const byte *input, size_t inputLen) |
void | BERDecode (BufferedTransformation &bt) |
decode this object from a BufferedTransformation, using BER (Basic Encoding Rules) | |
void | BERDecodeAsOctetString (BufferedTransformation &bt, size_t length) |
decode nonnegative value as big-endian octet string | |
void | OpenPGPDecode (const byte *input, size_t inputLen) |
void | OpenPGPDecode (BufferedTransformation &bt) |
ACCESSORS | |
| |
bool | IsConvertableToLong () const |
return true if *this can be represented as a signed long | |
signed long | ConvertToLong () const |
return equivalent signed long if possible, otherwise undefined | |
unsigned int | BitCount () const |
number of significant bits = floor(log2(abs(*this))) + 1 | |
unsigned int | ByteCount () const |
number of significant bytes = ceiling(BitCount()/8) | |
unsigned int | WordCount () const |
number of significant words = ceiling(ByteCount()/sizeof(word)) | |
bool | GetBit (size_t i) const |
return the i-th bit, i=0 being the least significant bit | |
byte | GetByte (size_t i) const |
return the i-th byte | |
lword | GetBits (size_t i, size_t n) const |
return n lowest bits of *this >> i | |
bool | IsZero () const |
bool | NotZero () const |
bool | IsNegative () const |
bool | NotNegative () const |
bool | IsPositive () const |
bool | NotPositive () const |
bool | IsEven () const |
bool | IsOdd () const |
MANIPULATORS | |
| |
Integer & | operator= (const Integer &t) |
Integer & | operator+= (const Integer &t) |
Integer & | operator-= (const Integer &t) |
Integer & | operator*= (const Integer &t) |
Integer & | operator/= (const Integer &t) |
Integer & | operator%= (const Integer &t) |
Integer & | operator/= (word t) |
Integer & | operator%= (word t) |
Integer & | operator<<= (size_t) |
Integer & | operator>>= (size_t) |
void | Randomize (RandomNumberGenerator &rng, size_t bitcount) |
void | Randomize (RandomNumberGenerator &rng, const Integer &min, const Integer &max) |
bool | Randomize (RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType, const Integer &equiv=Zero(), const Integer &mod=One()) |
set this Integer to a random element of {x | min <= x <= max and x is of rnType and x % mod == equiv} | |
bool | GenerateRandomNoThrow (RandomNumberGenerator &rng, const NameValuePairs ¶ms=g_nullNameValuePairs) |
void | GenerateRandom (RandomNumberGenerator &rng, const NameValuePairs ¶ms=g_nullNameValuePairs) |
void | SetBit (size_t n, bool value=1) |
set the n-th bit to value | |
void | SetByte (size_t n, byte value) |
set the n-th byte to value | |
void | Negate () |
void | SetPositive () |
void | SetNegative () |
void | swap (Integer &a) |
UNARY OPERATORS | |
| |
bool | operator! () const |
Integer | operator+ () const |
Integer | operator- () const |
Integer & | operator++ () |
Integer & | operator-- () |
Integer | operator++ (int) |
Integer | operator-- (int) |
BINARY OPERATORS | |
| |
int | Compare (const Integer &a) const |
signed comparison | |
Integer | Plus (const Integer &b) const |
Integer | Minus (const Integer &b) const |
Integer | Times (const Integer &b) const |
Integer | DividedBy (const Integer &b) const |
Integer | Modulo (const Integer &b) const |
Integer | DividedBy (word b) const |
word | Modulo (word b) const |
Integer | operator>> (size_t n) const |
Integer | operator<< (size_t n) const |
multiple precision integer and basic arithmetics
This class can represent positive and negative integers with absolute value less than (256**sizeof(word)) ** (256**sizeof(int)).
Definition at line 26 of file integer.h.
Integer::Integer | ( | const char * | str | ) | [explicit] |
convert from string
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.
Definition at line 3028 of file integer.cpp.
Integer::Integer | ( | RandomNumberGenerator & | rng, | |
size_t | bitcount | |||
) |
create a random integer
The random integer created is uniformly distributed over [0, 2**bitcount).
Definition at line 2835 of file integer.cpp.
Integer::Integer | ( | RandomNumberGenerator & | rng, | |
const Integer & | min, | |||
const Integer & | max, | |||
RandomNumberType | rnType = ANY , |
|||
const Integer & | equiv = Zero() , |
|||
const Integer & | mod = One() | |||
) |
create a random integer of special type
Ideally, the random integer created should be uniformly distributed over {x | min <= x <= max and x is of rnType and x % mod == equiv}. However the actual distribution may not be uniform because sequential search is used to find an appropriate number from a random starting point. May return (with very small probability) a pseudoprime when a prime is requested and max > lastSmallPrime*lastSmallPrime (lastSmallPrime is declared in nbtheory.h).
RandomNumberNotFound | if the set is empty. |
Definition at line 2840 of file integer.cpp.
size_t Integer::MinEncodedSize | ( | Signedness | signedness = UNSIGNED |
) | const |
minimum number of bytes to encode this integer
MinEncodedSize of 0 is 1
Definition at line 3100 of file integer.cpp.
References ByteCount(), GetByte(), and Power2().
Referenced by DEREncode().
void Integer::Encode | ( | byte * | output, | |
size_t | outputLen, | |||
Signedness | signedness = UNSIGNED | |||
) | const |
encode in big-endian format
unsigned means encode absolute value, signed means encode two's complement if negative. if outputLen < MinEncodedSize, the most significant bytes will be dropped if outputLen > MinEncodedSize, the most significant bytes will be padded
Definition at line 3112 of file integer.cpp.
Referenced by DEREncode(), DEREncodeAsOctetString(), DSAConvertSignatureFormat(), DL_SimpleKeyAgreementDomainBase< GROUP_PARAMETERS::Element >::GeneratePrivateKey(), MQV_Domain< GROUP_PARAMETERS, COFACTOR_OPTION >::GenerateStaticPrivateKey(), and OpenPGPEncode().
bool Integer::Randomize | ( | RandomNumberGenerator & | rng, | |
const Integer & | min, | |||
const Integer & | max, | |||
RandomNumberType | rnType, | |||
const Integer & | equiv = Zero() , |
|||
const Integer & | mod = One() | |||
) |
set this Integer to a random element of {x | min <= x <= max and x is of rnType and x % mod == equiv}
returns false if the set is empty
Definition at line 3227 of file integer.cpp.
int Integer::Compare | ( | const Integer & | a | ) | const |
signed comparison
-1 | if *this < a | |
0 | if *this = a | |
1 | if *this > a |
Definition at line 3890 of file integer.cpp.
virtual void ASN1Object::BEREncode | ( | BufferedTransformation & | bt | ) | const [inline, virtual, inherited] |
encode this object into a BufferedTransformation, using BER
this may be useful if DEREncode() would be too inefficient
Definition at line 1644 of file cryptlib.h.