---

Integer Class Reference

multiple precision integer and basic arithmetics. More...

#include <integer.h>

List of all members.

ENUMS, EXCEPTIONS, and TYPEDEFS
enum	Signedness { UNSIGNED, SIGNED }
enum	RandomNumberType { ANY, PRIME }
CREATORS
	Integer ()
	creates the zero integer. More...
	Integer (const Integer &t)
	copy constructor. More...
	Integer (signed long value)
	convert from signed long. More...
	Integer (const char *str)
	convert from string. More...
	Integer (const byte *encodedInteger,unsigned int byteCount,Signedness s=UNSIGNED)
	convert from big-endian byte array. More...
	Integer (BufferedTransformation &bt,unsigned int byteCount,Signedness s=UNSIGNED)
	convert from big-endian form stored in a BufferedTransformation. More...
	Integer (BufferedTransformation &bt)
	convert from BER encoded byte array stored in a BufferedTransformation object. More...
	Integer (RandomNumberGenerator &rng,unsigned int 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...
const Integer&	Zero ()
	avoid calling constructors for these frequently used integers. More...
const Integer&	One ()
	avoid calling constructors for these frequently used integers. More...
Integer	Power2 (unsigned int e)
	return the integer 2**e. More...
ENCODE/DECODE
unsigned int	MinEncodedSize (Signedness=UNSIGNED)const
	minimum number of bytes to encode this integer. More...
unsigned int	Encode (byte *output,unsigned int outputLen,Signedness=UNSIGNED)const
	encode in big-endian format. More...
unsigned int	Encode (BufferedTransformation &bt,unsigned int outputLen,Signedness=UNSIGNED)const
void	DEREncode (BufferedTransformation &bt)const
	encode using Distinguished Encoding Rules, put result into a BufferedTransformation object. More...
void	DEREncodeAsOctetString (BufferedTransformation &bt,unsigned int length)const
	encode absolute value as big-endian octet string. More...
unsigned int	OpenPGPEncode (byte *output,unsigned int bufferSize)const
	encode absolute value in OpenPGP format, return length of output. More...
unsigned int	OpenPGPEncode (BufferedTransformation &bt)const
	encode absolute value in OpenPGP format, put result into a BufferedTransformation object. More...
void	Decode (const byte *input,unsigned int inputLen,Signedness=UNSIGNED)
void	Decode (BufferedTransformation &bt,unsigned int inputLen,Signedness=UNSIGNED)
void	BERDecode (const byte *input,unsigned int inputLen)
void	BERDecode (BufferedTransformation &bt)
void	BERDecodeAsOctetString (BufferedTransformation &bt,unsigned int length)
	decode nonnegative value as big-endian octet string. More...
void	OpenPGPDecode (const byte *input,unsigned int inputLen)
void	OpenPGPDecode (BufferedTransformation &bt)
ACCESSORS
bool	IsConvertableToLong ()const
	return true if *this can be represented as a signed long. More...
signed long	ConvertToLong ()const
	return equivalent signed long if possible, otherwise undefined. More...
unsigned int	BitCount ()const
	number of significant bits = floor(log2(abs(*this))) + 1. More...
unsigned int	ByteCount ()const
	number of significant bytes = ceiling(BitCount()/8). More...
unsigned int	WordCount ()const
	number of significant words = ceiling(ByteCount()/sizeof(word)). More...
bool	GetBit (unsigned int i)const
	return the i-th bit, i=0 being the least significant bit. More...
byte	GetByte (unsigned int i)const
	return the i-th byte. More...
unsigned long	GetBits (unsigned int i,unsigned int n)const
	return n lowest bits of *this >> i. More...
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<<= (unsigned int)
Integer&	operator>>= (unsigned int)
void	Randomize (RandomNumberGenerator &rng,unsigned int 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...
void	SetBit (unsigned int n,bool value=1)
	set the n-th bit to value. More...
void	SetByte (unsigned int n,byte value)
	set the n-th byte to value. More...
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>> (unsigned int n)const
Integer	operator<< (unsigned int n)const
OTHER ARITHMETIC FUNCTIONS
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. More...
bool	IsSquare ()const
	return whether this integer is a perfect square. More...
bool	IsUnit ()const
	is 1 or -1. More...
Integer	MultiplicativeInverse ()const
	return inverse if 1 or -1, otherwise return 0. More...
Integer	InverseMod (const Integer &n)const
	calculate multiplicative inverse of *this mod n. More...
word	InverseMod (word n)const
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)). More...
void	Divide (word &r,Integer &q,const Integer &a,word d)
	use a faster division algorithm when divisor is short. More...
void	DivideByPowerOf2 (Integer &r,Integer &q,const Integer &a,unsigned int n)
	returns same result as Divide(r, q, a, Power2(n)), but faster. More...
Integer	Gcd (const Integer &a,const Integer &n)
	greatest common divisor. More...
Integer	a_times_b_mod_c (const Integer &x,const Integer &y,const Integer &m)
	modular multiplication. More...
Integer	a_exp_b_mod_c (const Integer &x,const Integer &e,const Integer &m)
	modular exponentiation. More...
INPUT/OUTPUT
class	operator>>
class	operator<<
Friends
class	ModularArithmetic
class	MontgomeryRepresentation
class	HalfMontgomeryRepresentation
class	PositiveAdd
class	PositiveSubtract
class	PositiveMultiply
class	PositiveDivide

---

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 18 of file integer.h.

---

Member Enumeration Documentation

enum Integer::RandomNumberType

Definition at line 45 of file integer.h.

enum Integer::Signedness

Definition at line 38 of file integer.h.

---

Constructor & Destructor Documentation

Integer::Integer ( )

creates the zero integer. Definition at line 1403 of file integer.cpp.

Integer::Integer ( const Integer & t )

copy constructor. Definition at line 1409 of file integer.cpp.

Integer::Integer ( signed long value )

convert from signed long. Definition at line 1415 of file integer.cpp.

Integer::Integer ( const char * str )

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 1585 of file integer.cpp.

Integer::Integer ( const byte * encodedInteger, unsigned int byteCount, Signedness s = UNSIGNED )

convert from big-endian byte array. Definition at line 1455 of file integer.cpp.

Integer::Integer ( BufferedTransformation & bt, unsigned int byteCount, Signedness s = UNSIGNED )

convert from big-endian form stored in a BufferedTransformation. Definition at line 1450 of file integer.cpp.

Integer::Integer ( BufferedTransformation & bt )

convert from BER encoded byte array stored in a BufferedTransformation object. Definition at line 1460 of file integer.cpp.

Integer::Integer ( RandomNumberGenerator & rng, unsigned int bitcount )

create a random integer. The random integer created is uniformly distributed over [0, 2**bitcount). Definition at line 1465 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). Exceptions: RandomNumberNotFound   if the set is empty. Definition at line 1470 of file integer.cpp.

---

Member Function Documentation

Integer Integer::AbsoluteValue ( ) const

Definition at line 1564 of file integer.cpp.

void Integer::BERDecode ( BufferedTransformation & bt )

Definition at line 1749 of file integer.cpp.

void Integer::BERDecode ( const byte * input, unsigned int inputLen )

Definition at line 1743 of file integer.cpp.

void Integer::BERDecodeAsOctetString ( BufferedTransformation & bt, unsigned int length )

decode nonnegative value as big-endian octet string. Definition at line 1765 of file integer.cpp.

unsigned int Integer::BitCount ( ) const

number of significant bits = floor(log2(abs(*this))) + 1. Definition at line 1655 of file integer.cpp. Referenced by OpenPGPEncode(), and SquareRoot().

unsigned int Integer::ByteCount ( ) const

number of significant bytes = ceiling(BitCount()/8). Definition at line 1646 of file integer.cpp. Referenced by XTR_DH::AgreedValueLength(), LUCDIF::AgreedValueLength(), IsConvertableToLong(), MinEncodedSize(), XTR_DH::PrivateKeyLength(), LUCDIF::PrivateKeyLength(), XTR_DH::PublicKeyLength(), and LUCDIF::PublicKeyLength().

int Integer::Compare ( const Integer & a ) const

signed comparison. Return values: -1   if *this < a 0   if *this = a 1   if *this > a Definition at line 2412 of file integer.cpp.

signed long Integer::ConvertToLong ( ) const

return equivalent signed long if possible, otherwise undefined. Definition at line 1443 of file integer.cpp.

void Integer::DEREncode ( BufferedTransformation & bt ) const

encode using Distinguished Encoding Rules, put result into a BufferedTransformation object. Definition at line 1736 of file integer.cpp.

void Integer::DEREncodeAsOctetString ( BufferedTransformation & bt, unsigned int length ) const

encode absolute value as big-endian octet string. Definition at line 1758 of file integer.cpp.

void Integer::Decode ( BufferedTransformation & bt, unsigned int inputLen, Signedness s = UNSIGNED )

Definition at line 1670 of file integer.cpp.

void Integer::Decode ( const byte * input, unsigned int inputLen, Signedness s = UNSIGNED )

Definition at line 1664 of file integer.cpp.

void Integer::Divide ( word & r, Integer & q, const Integer & a, word d ) [static]

use a faster division algorithm when divisor is short. Definition at line 2316 of file integer.cpp.

void Integer::Divide ( Integer & r, Integer & q, const Integer & a, const Integer & d ) [static]

calculate r and q such that (a == d*q + r) && (0 <= r < abs(d)). Definition at line 2256 of file integer.cpp.

void Integer::DivideByPowerOf2 ( Integer & r, Integer & q, const Integer & a, unsigned int n ) [static]

returns same result as Divide(r, q, a, Power2(n)), but faster. Definition at line 2274 of file integer.cpp.

Integer Integer::DividedBy ( word b ) const

Definition at line 2352 of file integer.cpp.

Integer Integer::DividedBy ( const Integer & b ) const

Definition at line 2302 of file integer.cpp.

Integer Integer::Doubled ( ) const [inline]

Definition at line 296 of file integer.h.

unsigned int Integer::Encode ( BufferedTransformation & bt, unsigned int outputLen, Signedness signedness = UNSIGNED ) const

Definition at line 1719 of file integer.cpp.

unsigned int Integer::Encode ( byte * output, unsigned int 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 1713 of file integer.cpp. Referenced by LUCDIF::Agree(), DEREncode(), DEREncodeAsOctetString(), LUCELG_Decryptor::Decrypt(), ElGamalDecryptor::Decrypt(), LUCELG_Encryptor::Encrypt(), XTR_DH::GenerateKeyPair(), LUCDIF::GenerateKeyPair(), and OpenPGPEncode().

Integer Integer::Gcd ( const Integer & a, const Integer & n ) [static]

greatest common divisor. Definition at line 2475 of file integer.cpp.

bool Integer::GetBit ( unsigned int i ) const

return the i-th bit, i=0 being the least significant bit. Definition at line 1511 of file integer.cpp. Referenced by PublicBlumBlumShub::GenerateBit(), and GetBits().

unsigned long Integer::GetBits ( unsigned int i, unsigned int n ) const

return n lowest bits of *this >> i. Definition at line 1548 of file integer.cpp.

byte Integer::GetByte ( unsigned int i ) const

return the i-th byte. Definition at line 1533 of file integer.cpp. Referenced by MinEncodedSize().

word Integer::InverseMod ( word n ) const

Definition at line 2505 of file integer.cpp.

Integer Integer::InverseMod ( const Integer & n ) const

calculate multiplicative inverse of *this mod n. Definition at line 2480 of file integer.cpp.

bool Integer::IsConvertableToLong ( ) const

return true if *this can be represented as a signed long. Definition at line 1429 of file integer.cpp.

bool Integer::IsEven ( ) const [inline]

Definition at line 189 of file integer.h.

bool Integer::IsNegative ( ) const [inline]

Definition at line 181 of file integer.h.

bool Integer::IsOdd ( ) const [inline]

Definition at line 191 of file integer.h.

bool Integer::IsPositive ( ) const [inline]

Definition at line 185 of file integer.h.

bool Integer::IsSquare ( ) const

return whether this integer is a perfect square. Definition at line 2448 of file integer.cpp.

bool Integer::IsUnit ( ) const

is 1 or -1. Definition at line 2454 of file integer.cpp. Referenced by MultiplicativeInverse().

bool Integer::IsZero ( ) const [inline]

Definition at line 177 of file integer.h.

unsigned int Integer::MinEncodedSize ( Signedness signedness = UNSIGNED ) const

minimum number of bytes to encode this integer. MinEncodedSize of 0 is 1 Definition at line 1701 of file integer.cpp. Referenced by DEREncode().

Integer Integer::Minus ( const Integer & b ) const

Definition at line 2106 of file integer.cpp.

word Integer::Modulo ( word b ) const

Definition at line 2360 of file integer.cpp.

Integer Integer::Modulo ( const Integer & b ) const

Definition at line 2309 of file integer.cpp.

Integer Integer::MultiplicativeInverse ( ) const

return inverse if 1 or -1, otherwise return 0. Definition at line 2459 of file integer.cpp.

void Integer::Negate ( )

Definition at line 2396 of file integer.cpp.

bool Integer::NotNegative ( ) const [inline]

Definition at line 183 of file integer.h.

bool Integer::NotPositive ( ) const [inline]

Definition at line 187 of file integer.h.

bool Integer::NotZero ( ) const [inline]

Definition at line 179 of file integer.h.

const Integer & Integer::One ( ) [static]

avoid calling constructors for these frequently used integers. Definition at line 1489 of file integer.cpp. Referenced by InverseMod(), and Randomize().

void Integer::OpenPGPDecode ( BufferedTransformation & bt )

Definition at line 1793 of file integer.cpp.

void Integer::OpenPGPDecode ( const byte * input, unsigned int inputLen )

Definition at line 1787 of file integer.cpp.

unsigned int Integer::OpenPGPEncode ( BufferedTransformation & bt ) const

encode absolute value in OpenPGP format, put result into a BufferedTransformation object. Definition at line 1780 of file integer.cpp.

unsigned int Integer::OpenPGPEncode ( byte * output, unsigned int bufferSize ) const

encode absolute value in OpenPGP format, return length of output. Definition at line 1774 of file integer.cpp.

Integer Integer::Plus ( const Integer & b ) const

Definition at line 2060 of file integer.cpp.

Integer Integer::Power2 ( unsigned int e ) [static]

return the integer 2**e. Definition at line 1476 of file integer.cpp. Referenced by DivideByPowerOf2(), MinEncodedSize(), and SquareRoot().

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 1827 of file integer.cpp. Referenced by Integer().

void Integer::Randomize ( RandomNumberGenerator & rng, const Integer & min, const Integer & max )

Definition at line 1811 of file integer.cpp.

void Integer::Randomize ( RandomNumberGenerator & rng, unsigned int bitcount )

Definition at line 1801 of file integer.cpp.

void Integer::SetBit ( unsigned int n, bool value = 1 )

set the n-th bit to value. Definition at line 1519 of file integer.cpp. Referenced by Power2().

void Integer::SetByte ( unsigned int n, byte value )

set the n-th byte to value. Definition at line 1541 of file integer.cpp.

void Integer::SetNegative ( ) [inline]

Definition at line 237 of file integer.h.

void Integer::SetPositive ( ) [inline]

Definition at line 235 of file integer.h.

Integer Integer::SquareRoot ( ) const

extract square root, if negative return 0, else return floor of square root. Definition at line 2430 of file integer.cpp. Referenced by IsSquare().

Integer Integer::Squared ( ) const [inline]

Definition at line 298 of file integer.h. Referenced by XTR_DH::ValidateDomainParameters().

Integer Integer::Times ( const Integer & b ) const

Definition at line 2198 of file integer.cpp.

unsigned int Integer::WordCount ( ) const

number of significant words = ceiling(ByteCount()/sizeof(word)). Definition at line 1641 of file integer.cpp. Referenced by BitCount(), ByteCount(), Divide(), DivideByPowerOf2(), and IsUnit().

const Integer & Integer::Zero ( ) [static]

avoid calling constructors for these frequently used integers. Definition at line 1483 of file integer.cpp. Referenced by InverseMod(), MultiplicativeInverse(), Randomize(), SquareRoot(), and XTR_DH::ValidateDomainParameters().

Integer & Integer::operator *= ( const Integer & t ) [inline]

Definition at line 204 of file integer.h.

bool Integer::operator! ( ) const

Definition at line 1495 of file integer.cpp.

Integer & Integer::operator%= ( word t ) [inline]

Definition at line 212 of file integer.h.

Integer & Integer::operator%= ( const Integer & t ) [inline]

Definition at line 208 of file integer.h.

Integer Integer::operator+ ( ) const [inline]

Definition at line 248 of file integer.h.

Integer Integer::operator++ ( int ) [inline]

Definition at line 256 of file integer.h.

Integer & Integer::operator++ ( )

Definition at line 1958 of file integer.cpp.

Integer & Integer::operator+= ( const Integer & t )

Definition at line 2083 of file integer.cpp.

Integer Integer::operator- ( ) const

Definition at line 1557 of file integer.cpp.

Integer Integer::operator-- ( int ) [inline]

Definition at line 258 of file integer.h.

Integer & Integer::operator-- ( )

Definition at line 1978 of file integer.cpp.

Integer & Integer::operator-= ( const Integer & t )

Definition at line 2129 of file integer.cpp.

Integer & Integer::operator/= ( word t ) [inline]

Definition at line 210 of file integer.h.

Integer & Integer::operator/= ( const Integer & t ) [inline]

Definition at line 206 of file integer.h.

Integer Integer::operator<< ( unsigned int n ) const [inline]

Definition at line 288 of file integer.h.

Integer & Integer::operator<<= ( unsigned int n )

Definition at line 2152 of file integer.cpp.

Integer & Integer::operator= ( const Integer & t )

Definition at line 1500 of file integer.cpp.

Integer Integer::operator>> ( unsigned int n ) const [inline]

Definition at line 286 of file integer.h.

Integer & Integer::operator>>= ( unsigned int n )

Definition at line 2164 of file integer.cpp.

void Integer::swap ( Integer & a )

Definition at line 1571 of file integer.cpp.

---

Friends And Related Function Documentation

class HalfMontgomeryRepresentation [friend]

Definition at line 341 of file integer.h.

class ModularArithmetic [friend]

Definition at line 339 of file integer.h.

class MontgomeryRepresentation [friend]

Definition at line 340 of file integer.h.

void PositiveAdd ( Integer & sum, const Integer & a, const Integer & b ) [friend]

Definition at line 1996 of file integer.cpp.

void PositiveDivide ( Integer & remainder, Integer & quotient, const Integer & a, const Integer & b ) [friend]

Definition at line 2227 of file integer.cpp.

void PositiveMultiply ( Integer & product, const Integer & a, const Integer & b ) [friend]

Definition at line 2178 of file integer.cpp.

void PositiveSubtract ( Integer & diff, const Integer & a, const Integer & b ) [friend]

Definition at line 2022 of file integer.cpp.

Integer a_exp_b_mod_c ( const Integer & x, const Integer & e, const Integer & m ) [friend]

modular exponentiation. Definition at line 2469 of file integer.cpp.

Integer a_times_b_mod_c ( const Integer & x, const Integer & y, const Integer & m ) [friend]

modular multiplication. Definition at line 2464 of file integer.cpp.

ostream & operator<< ( ::ostream & out, const Integer & a ) [friend]

Definition at line 1903 of file integer.cpp.

istream & operator>> ( ::istream & in, Integer & a ) [friend]

Definition at line 1878 of file integer.cpp.

---

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

• integer.h
• integer.cpp

---