Integer Class Reference

multiple precision integer and basic arithmetics More...

#include <integer.h>

Inheritance diagram for Integer:

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 More...

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 &quotient, const Integer &dividend, const Integer &divisor)

ENUMS, EXCEPTIONS, and TYPEDEFS
enum	Sign { POSITIVE =0, NEGATIVE =1 }
enum	Signedness { UNSIGNED, SIGNED }
enum	RandomNumberType { ANY, PRIME }

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 More...
	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 More...
	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 More...
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 More...
void	Encode (byte *output, size_t outputLen, Signedness=UNSIGNED) const
	encode in big-endian format More...
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} More...
bool	GenerateRandomNoThrow (RandomNumberGenerator &rng, const NameValuePairs &params=g_nullNameValuePairs)
void	GenerateRandom (RandomNumberGenerator &rng, const NameValuePairs &params=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 More...
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

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)

Detailed Description

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.

Constructor & Destructor Documentation

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.

Integer::Integer	(	RandomNumberGenerator &	rng,
		size_t	bitcount
	)

create a random integer

The random integer created is uniformly distributed over [0, 2**bitcount).

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).

Exceptions

RandomNumberNotFound

if the set is empty.

Member Function Documentation

size_t Integer::MinEncodedSize

(

Signedness

= UNSIGNED

)

const

minimum number of bytes to encode this integer

MinEncodedSize of 0 is 1

void Integer::Encode	(	byte *	output,
		size_t	outputLen,
		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

Referenced by MQV_Domain< GROUP_PARAMETERS, COFACTOR_OPTION >::GenerateEphemeralPrivateKey(), DL_SimpleKeyAgreementDomainBase< GROUP_PARAMETERS::Element >::GeneratePrivateKey(), MQV_Domain< GROUP_PARAMETERS, COFACTOR_OPTION >::GenerateStaticPrivateKey(), and DL_VerifierBase< SCHEME_OPTIONS::Element >::RecoverAndRestart().

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

int Integer::Compare

(

const Integer &

a

)

const

signed comparison

Return values

-1	if *this < a
0	if *this = a
1	if *this > a

virtual void ASN1Object::BEREncode ( BufferedTransformation &  bt ) const

inlinevirtualinherited

encode this object into a BufferedTransformation, using BER

this may be useful if DEREncode() would be too inefficient

Definition at line 1643 of file cryptlib.h.

---

The documentation for this class was generated from the following file:

• integer.h