other versions

- wheezy 3.01.00-1+b1
- jessie 3.23.01-1
- testing 4.04.00-1
- unstable 4.04.00-1
- experimental 4.07.00-1

other sections

FBB::BigInt(3bobcat) | Big Integers | FBB::BigInt(3bobcat) |

# NAME¶

FBB::BigInt - Arithmetic on Integers of Unlimited Size# SYNOPSIS¶

**#include <bobcat/bigint>**

*-lbobcat*

# DESCRIPTION¶

This class is defined as a wrapper class around the*openSSL*

*BN*series of functions, offering members to perform arithmetic on integral values of unlimited sizes. Members are offered to generate primes and to perform all kinds of common arithmetic operations on

*BigInt*objects. Also, conversions to characters and standard numerical value types are offered. Below, the phrase

*the object*may also refer to the object’s value. The context in which this occurs will make clear that the object’s value rather than the object as-is is referred to. Various constructors accept

*BIGNUM*arguments. Type

*BIGNUM*is the type containing an integer of unlimited precision as defined by OpenSSL. Signs of

*BigInt*are handled in a special way. Whether a

*BigInt*is negative or positive is determined by its sign-flag, and not by a sign bit as is the case with

*int*typed values. Since

*BigInt*values have unlimited precision shifting values to the left won’t change their signs. Operators return either a reference to the current (modified) object or return a

*BigInt*object containing the computed value. The rule followed here was to implement the operators analogously to the way the operators work on

*int*type values and variables. E.g.,

*operator+()*returns a

*BigInt*value whereas

*operator+=()*returns a

*BigInt &*reference. All members modifying their objects return a reference to the current (modified) object. All members not modifying the current object return a

*BigInt*object. If both members exists performing the same functionality the name of the member returning a

*BigInt*object ends in a

*c*(const) (e.g.,

*addMod*and

*addModc*. Almost all operators, members and constructors (except for the default constructor) throw

*Errno*exceptions on failure.

# INHERITS FROM¶

-# ENUMERATIONS¶

**Msb**

- o
**MSB_UNKNOWN**:

- o
**MSB_IS_ONE**:

- o
**TOP_TWO_BITS_ONE**:*nBits*having*2 * nBits*bits.

**Lsb**

- o
**EVEN**:

- o
**ODD**:

# CONSTRUCTORS¶

- o
**BigInt()**:*BigInt*value to 0.

- o
**BigInt(BIGNUM const &value)**:*BigInt*from a*BIGNUM*.

- o
**BigInt(BIGNUM const *value)**:*BigInt*from a pointer to a*const BIGNUM*.

- o
**BigInt(Type value)**:*unsigned long*can be used as argument to this constructor. Promotion is allowed, so in many situations where*BigInt*s are expected a plain numerical value can be used as well.

# MEMBER FUNCTIONS¶

- o
**BigInt &addMod(BigInt const &rhs, BigInt const &mod)**:*Rhs*is added (modulo*mod*) to the current object.

- o
**BigInt addModc(BigInt const &rhs, BigInt const &mod)**:*mod*) of the current object and*rhs*is returned.

- o
**BIGNUM const &bignum() const**:*BIGNUM*value maintained by the current*BigInt*object is returned.

- o
**char *bigEndian() const**:*char*typed values in big-endian order. If a value consists of 5*char*s the eight most significant bits will be stored in the*char*having index value 0, the eight least significant bits will be stored in the*char*having index value 4. When needed simply swap*char[i]*with*char[j]*(i = 0 .. nBytes/2, j = nBytes-1 .. nBytes/2) to convert to little-endian order. The return value consists of a series of*sizeInBytes()*(see below) dynamically allocated*char*values. The caller of*bigEndian*owns the allocated memory and should eventually delete it again using*delete[]*. Note that the current object’s*sign*cannot be inferred from the return value.

- o
**BigInt &clearBit(size_t index)**:*index*is cleared.

- o
**BigInt clearBit(size_t index) const**:*index*cleared.

- o
**BigInt &div(BigInt *remainder, BigInt const &rhs)**:*rhs*. The division’s remainder is returned in**remainder*.

- o
**BigInt divc(BigInt *remainder, BigInt const &rhs) const**:*rhs*is returned. The division’s remainder is returned in**remainder*.

- o
**int compare(BigInt const &rsh) const**:*rhs*-1 is returned; if they are equal 0 is returned; if the current object is larger than*ths*1 is returned (see also*uCompare*).

- o
**BigInt &exp(BigInt const &exponent)**:*exponent*.

- o
**BigInt expc(BigInt const &exponent) const**:*exponent*is returned.

- o
**BigInt &expMod(BigInt const &exponent, BigInt const &mod)**:*exponent*modulo*mod*.

- o
**BigInt expModc(BigInt const &exponent, BigInt const &mod) const**:*exponent*modulo*mod*is returned.

- o
**BigInt &gcd(BigInt const &rhs)**:*rhs*is assigned to the current object. To compute the least common multiple (lcm) the following relationship can be used:lcm(a, b) = a * b / a.gcd(b)

- o
**BigInt gcdc(BigInt const &rhs) const**:*rhs*is returned. To compute the least common multiple (lcm) the following relationship can be used:lcm(a, b) = a * b / a.gcd(b)

- o
**bool hasBit(size_t index)**:*True*is returned if the bit at index position*index*has been set,*false*otherwise.

- o
**BigInt &inverseMod(BigInt const &mod)**:*mod*is assigned to the current object. This is the value*ret*for which the following expression holds true:(*this * ret) % mod = 1

- o
**BigInt inverseModc(BigInt const &mod) const**:*mod*is returned.

- o
**bool isNegative() const**:*true*if the current object contains a negative value.

- o
**bool isOdd() const**:*true*if the current object is an odd value.

- o
**bool isOne() const**:*true*if the current object equals one (1).

- o
**BigInt &isqrt()**:*x*is the biggest integral value whose square does not exceed*x*. E.g.,*isqrt(17) == 4*. An*Errno*exception is thrown if the current object’s value is smaller than one.

- o
**BigInt isqrtc() const**:*Errno*exception is thrown if the current object’s value is smaller than one.

- o
**bool isZero() const**:*true*if the current object equals zero (0).

- o
**BigInt &lshift()**:

- o
**BigInt lshiftc()**:

- o
**BigInt &lshift(size_t nBits)**:*nBits*to the left. The object’s sign remains unaltered.

- o
**BigInt lshiftc(size_t nBits) const**:*nBits*bit to the left are returned. The object’s sign will be equal to the current object’s sign.

- o
**BigInt &maskBits(size_t lowerNBits)**:*lowerNBits*lower bits are kept, its higher order bits are cleared. The object’s sign is not affected.

- o
**BigInt maskBitsc(size_t lowerNBits) const**:*lowerNBits*lower bits cleared. The sign of the returned object will be equal to the current object’s sign.

- o
**BigInt &mulMod(BigInt const &rhs, BigInt const &mod)**:*mod*) by*rhs*.

- o
**BigInt mulModc(BigInt const &rhs, BigInt const &mod) const**:*mod*) by*rhs*is returned.

- o
**BigInt &negate()**:

- o
**BigInt negatec() const**:

- o
**BigInt &rshift()**:

- o
**BigInt rshiftc()**:

- o
**BigInt &rshift(size_t nBits)**:*nBits*to the right. The object’s sign remains unaltered.

- o
**BigInt rshiftc(size_t nBits) const**:*nBits*bit to the right are returned. The object’s sign will be equal to the current object’s sign.

- o
**BigInt &setBit(size_t index)**:*index*is set.

- o
**BigInt setBitc(size_t index) const**:*index*set.

- o
**BigInt &setBit(size_t index, bool value)**:*index*is set to*value*.

- o
**BigInt setBitc(size_t index, bool value) const**:*index*set to*value*.

- o
**BigInt &setNegative(bool negative)**:*true*, it will be set to positive if the function’s argument is*false*.

- o
**BigInt setNegativec(bool negative) const**:*true*and a positive sign if the function’s argument is*false*.

- o
**size_t size() const**:*BIGNUM*value is returned.

- o
**size_t sizeInBits() const**:*BIGNUM*value is returned. If you want to know the key size of RSA, DH or DSA keys functions like*RSA_size(), DH_size(),*or*DSA_size()*should be used.

- o
**BigInt &sqr()**:

- o
**BigInt sqrc() const**:

- o
**BigInt &sqrMod(BigInt const &mod) const**:*mod*.

- o
**BigInt sqrModc(BigInt const &mod) const**:*mod*) of the current object is returned.

- o
**BigInt &subMod(BigInt const &rhs, BigInt const &mod)**:*Rhs*is subtracted modulo*mod*from the current object.

- o
**BigInt subModc(BigInt const &rhs, BigInt const &mod) const**:*mod*) of the current object and*rhs*is returned.

- o
**void swap(BigInt &other)**:*other*.

- o
**BigInt &tildeBits()**:Bigint b(5); b.tildeBits();

*b*contains the value -250. Also see the discussion with*operator~()*below.

- o
**BigInt tildeBitsc() const**:

- o
**BigInt &tildeInt()**:*int*semantics. E.g., ~5 results in -6. Also see the discussion with*operator~()*below.

- o
**BigInt tildeIntc() const**:*int*semantics.

- o
**unsigned long ulong() const**:*0xffffffffL*.

- o
**int uCompare(BigInt const &rsh) const**:*rhs*-1 is returned; if they are equal 0 is returned; if the current object is larger than*ths*1 is returned (see also*uCompare*).

# OVERLOADED OPERATORS¶

Except for some operators all operators perform their intuitive operations. Where that isn’t completely true an explanatory remark is provided. E.g.,*operator*()*multiplies two

*BigInt*s, possibly promoting one of the operands;

*operator*=()*multiplies the lhs by the rhs

*BigInt*, possibly promoting the rhs operand. Here are the available operators:

**Unary operators:**

- o
**BigInt &operator++()**:

- o
**BigInt operator++(int)**:

- o
**BigInt &operator--()**:

- o
**BigInt operator--(int)**:

- o
**BigInt operator-()**:

- o
**int operator[](size_t idx) const**:*BigInt*objects it returns the bit-value of the object’s*idx*th bit as the value 0 or 1.

- o
**BigInt::Bit operator[](size_t idx)**:*BigInt*objects it returns a reference to the bit-value of the object’s*idx*th bit. When used as*lvalue*assigning a 0 or non-zero value to the operator’s return value will either clear or set the bit. Likewise, the following arithmetic assignment operators may be used: binary or (*|=*), binary and (*&=*) or binary xor (*^=*). When used as*rvalue*the value of the object’s*idx*th bit is returned as a*bool*value. When inseerted into a*std::ostream*the bit’s value is displayed as 0 or 1.

- o
**BigInt operator~()**:*not*implemented as it cannot be implemented so that it matches the actions of this operator when applied to*int*type values.

- When used on
*int*values this operator toggles all the*int*’s bits. E.g., ~5 represents -6, and ~-6 again equals five. The -6 is the result of the sign bit of*int*values. The obvious implementation of*BigInt::operator~()*is to toggle all the value’s bits and to toggle its sign bit. For 5 this would result in -250: 5, being 101 (binary), fits in one byte, so ~5 becomes 11111010 (binary), which is 250. Its sign must be reversed as well, so it becomes -250. This clearly differs from the value represented by the*int*constant ~5: when constructing*BigInt(~5)*, the value -6 is obtained.

- It is possible to change the implementation. E.g., after
Bigint b(5); b = ~b;

*~b*could be implemented so that it results in the value -6. But this too leads to unexpected results. While*5 & ~5 == 0*, this would no longer hold true for*BigInt*objects: Assuming*b*contains 5 then*b & ~b*would expand to (binary)*101 &**(negative)110*which equals (binary) 100.

- Since either implementation produces unexpected results
*BigInt::operator~()*was not implemented. Instead two members are offered:*tildeBits()*, toggling all the bits of all the*BigInt*bytes and toggling its sign (soBigint b(5); b.tildeBits();

changes*b*’s value into -250), and*tildeInt()*changing the object’s value into the value that would have been obtained if a*BigInt*was a mere*int*(soBigint b(5); b.tildeInt();

changes*b*’s value into -6).

**Binary operators:**

- o
**BigInt operator*(BigInt const &lhs, BigInt const &rhs)**:

- o
**BigInt operator/(BigInt const &lhs, BigInt const &rhs)**:*lhs*object divided by the*rhs*object. The remainder is lost (The member*div*performs the division and makes the remainder available as well).

- o
**BigInt operator%(BigInt const &lhs, BigInt const &rhs)**:

- o
**BigInt operator+(BigInt const &lhs, BigInt const &rhs)**:

- o
**BigInt operator-(BigInt const &lhs, BigInt const &rhs)**:

- o
**BigInt operator<<(BigInt const &lhs, size_t nBits)**:*lshift*members. If*lhs*is positive,

- o
**BigInt operator>>=(BigInt const &lhs, size_t nBits)**:*rshift*members.

- o
**BigInt operator&(BigInt const &lhs, BigInt const &rhs)**:*BigInt*value consisting of the*bit_and*-ed bits and sign flags of lhs and rhs operands. Consequently, if one operand is positive, the resulting value will be positive.

- o
**BigInt operator|(BigInt const &lhs, BigInt const &rhs)**:*BigInt*value consisting of the*bit_or*-ed bits and sign flags of lhs and rhs operands. Consequently, if either operand is negative, the result will be negative.

- o
**BigInt operator^(BigInt const &lhs, BigInt const &rhs)**:*BigInt*value consisting of the*bit_xor*-ed bits and sign flags of lhs and rhs operands. Consequently, if exactly one operand is negative, the result will be negative.

**(Arithmetic) assignment operator(s):**

- o
**BigInt &operator=(BigInt const &rhs)**:

- o
**BigInt &operator*=(BigInt const &rhs)**:

- o
**BigInt &operator/=(BigInt const &rhs)**:*BigInt*object by*ths*to the current object. The remainder is lost. The member*div*divides and makes the remainder available as well.

- o
**BigInt &operator%=(BigInt const &rhs)**:

- o
**BigInt &operator+=(BigInt const &rhs)**:

- o
**BigInt &operator-=(BigInt const &rhs)**:

- o
**BigInt &operator<<=(size_t nBits)**:*lshift*members.

- o
**BigInt &operator>>=(size_t nBits)**:*rshift*members.

- o
**BigInt &operator&(BigInt const &rhs)**:*bit_and*s the bits and sign flags of the current object and the rhs operand.

- o
**BigInt &operator|(BigInt const &rhs)**:*bit_or*s the bits and sign flags of the current object and the rhs operand.

- o
**BigInt &operator^(BigInt const &rhs)**:*bit_xor*s the bits and sign flags of the current object and the rhs operand.

# STATIC MEMBERS¶

All members returning a*BigInt*computed from a set of arguments and not requiring an existing

*BigInt*object are defined as static members.

- o
**BigInt fromText(std::string text, int mode = 0)**:*BigInt*value. Conversion continues until the end of*text*or until a character outside of an expected range is encountered.

- The expected range may be preset by specifying
*mode*as*ios::dec,**ios::oct,*or*ios::hex*or (the default) the expected range is determined by*fromText*itself by inspecting the characters in*text*.

- By default if
*text*contains hexadecimal characters then*fromText*assumes that the number is represented as a hexadecimal value (e.g.,*"abc"*is converted to the (decimal) value 2748); if*text*starts with 0 and contains only characters in the range 0 until (including) 7 then*fromText*assumes the number is represented as an octal value (e.g.,*"01234"*is converted to the (decimal) value 668). Otherwise a decimal value is assumed.

- If the text does not represent a valid numerical value (of
the given extraction mode) then a
*FBB::Errno*exception is thrown (*fromText: text does not represent a BigInt value*).

- o
**BigInt rand(size_t size, Msb msb = MSB_IS_ONE, Lsb lsb = ODD)**:*size*bits. The most significant bit(s) can be controlled by*msb*(by default**MSB_IS_ONE**), the least significant bit can be controlled by*lsb*(by default**ODD**). Before calling this member the random number generator must have been seeded.

- o
**BigInt randRange(BigInt const &max)**:*0 <= number < max*. Before calling this member the random number generator must have been seeded.

- o
**BigInt setBigEndian(std::string const &bytes)**:*bytes.length()*bytes of*bytes*are used to compute a*BigInt*object which is returned by this function. The characters in*bytes*are interpreted as a series of bytes in big-endian order. See also the member function*bigEndian()*above. The returned*BigInt*has a positive value.

- o
**BigInt prime(size_t nBits,****BigInt const *mod = 0, BigInt const *rem = 0,****PrimeType primeType = ANY)**:*bBits*bits. If both*mod*and*rem*are non-zero, the condition prime % mod == rem. (E.g., use*prime % mod == 1*in order to suit a given generator). The parameter*primeType*can be*ANY*,*(prime - 1)**/ 2*may or may not be a prime. If it is*SAFE*then*(prime - 1)**/ 2*will be a (so-called*safe*) prime.

- o
**BigInt pseudoRand(size_t size, Msb msb = MSB_IS_ONE, Lsb lsb =****ODD)**:*size*bits. The most significant bit(s) can be controlled by*msb*(by default**MSB_IS_ONE**), the least significant bit can be controlled by*lsb*(by default**ODD**). It can be used for non-cryptographic purposes and for certain purposes in cryptographic protocols, but usually not for key generation.

- o
**BigInt pseudoRandRange(BigInt const &max)**:*0 <= number < max*.

# FREE FUNCTIONS IN THE FBB NAMESPACE¶

- o
**std::ostream &operator<<(ostream &out, BigInt const &value)**:*value*into the provided*ostream*. If the*hex*manipulator has been inserted into the stream before inserting the*BigInt*value the value will be displayed as a hexadecimal value (without a leading*0x*); if the*oct*manipulator has been inserted the value will be represented as an octal value (starting with a 0). The value will be displayed as a decimal value if the*dec*manipulator is active. If the*BigInt*value is negative its value will be preceded by a minus character.

- o
**std::istream &operator>>(istream &in, BigInt &value)**:*value*from the provided*istream*. Depending on the currently set extraction mode (*dec, oct,*or*hex*) the matching set of characters will be extracted from*in*and converted to a number which is stored in*value*. Extraction stops at EOF or at the first character outside of the range of characters matching the extraction mode. if no numerical characters were extracted the stream’s*failbit*is set. The extracted value may be preceded by a minus character, resulting in an extracted negative value.

# EXAMPLE¶

#include <iostream> #include <bobcat/bigint> using namespace std; using namespace FBB; int main(int argc, char **argv) { BigInt value(BigInt::prime(100)); BigInt mod(BigInt::rand(50)); BigInt inverse(value.inverseModc(mod)); cout << ’(’ << value << " * " << inverse << ") % " << mod << " = " << ( value * inverse ) % mod << endl; }

# FILES¶

*bobcat/bigint*- defines the class interface

# SEE ALSO¶

bobcat(7), RAND_seed(3)# BUGS¶

None Reported.# DISTRIBUTION FILES¶

- o
*bobcat_3.01.00-x.dsc*: detached signature;

- o
*bobcat_3.01.00-x.tar.gz*: source archive;

- o
*bobcat_3.01.00-x_i386.changes*: change log;

- o
*libbobcat1_3.01.00-x_*.deb*: debian package holding the libraries;

- o
*libbobcat1-dev_3.01.00-x_*.deb*: debian package holding the libraries, headers and manual pages;

- o
*http://sourceforge.net/projects/bobcat*: public archive location;

# BOBCAT¶

Bobcat is an acronym of `Brokken’s Own Base Classes And Templates’.# COPYRIGHT¶

This is free software, distributed under the terms of the GNU General Public License (GPL).# AUTHOR¶

Frank B. Brokken (**f.b.brokken@rug.nl**).

2005-2012 | libbobcat1-dev_3.01.00-x.tar.gz |