Index of Big Integers


1. Introduction

This page introduces BigInteger implementation of the Zeus-Framework. The big integer implementation is available since version 2.0.

Big integers are used for arithmetic operations with huge numbers (larger than 64 or 128 bits). To add, subtract multiply and divide a special implementation is needed since a processor is not able to perform these tasks in one step.

This documents should give you a good start on how to use TBigInteger from Zeus-Framework. Nevertheless we give you also some helpful hints how to implement your own big number classes. Please forward to section 3. BigInteger implementation.


2. Using Big Integers

The Framework provides two classes to implement and use big numbers.

  • TBigInteger<N> : Template to wrap big numbers for arithmetic operations
  • TBigIntegerBase : Basic functionality of big numbers

The big number is represented by a Uint8-Array where as the first item represents the lowest significant byte of the number.

In this document we represent the number in the string notation whereas the hex notation starts with the most significant byte first.

2.1 Assigning Numbers

There are different ways to assing a number to a big integer. The simplest way is to assign a integer directly to the big-integer. To assign hugh values we use decimal or hexadecimal notation and transform it to a big integer.

For instance we can transform a decimal number stored in a string to a big integer using the TBitCodedValue::convertDecimalToByteArray().

  bool bError = false;
  TByteArray aValue1;
  TBitCodedValue::convertDecimalToByteArray(L"\
1911265680649749718481333\
4333402686093430162395366\
6358603884398457078662574\
0792044070418666832433497", bError, aValue1);

  Int1024 i1024_P1(aValue1);

To transform a hexadecimal number into a big integer we use the method TBitCodedValue::convertHexToByteArray().

  TByteArray aPrime2;
  TBitCodedValue::convertHexToByteArray(TString(L"\
d32737e7267ffe1341b2d5c0d150a81b\
586fb3132bed2f8d5262864a9cb9f30a\
f38be448598d413a172efb802c21acf1\
c11c520c2f26a471dcad212eac7ca39d"), bError, aPrime2);

If you want to transform a byte string into a big integer you might use TBitCodedValue::convertByteStringToByteArray(). The difference between this method and TBitCodedValue::convertHexToByteArray() is that the first byte in the string represents the lowest significant byte of the big number where as the first byte in the hex string represents the top most significant byte.

2.2 Mathematical Operations

The TBigInteger implements operators to create mathematical expressions. Please note that using operators are less performant than using modification methods directly. For instance:

  Int512 i512Val1 = 45;
  Int512 i512Val2 = 34;
  Int512 i512ValSum = i512Val1 + i512Val2;

More efficient is:

  Int512 i512Val1 = 45;
  i512Val1.add(34);

In i512Val1 + i512Val2 the operator creates a new object and assigns it to i512ValSum. The method add() directly manipulates the content of i512Val1.


3. BigInteger implementation

3.1 General

The class TBigInteger is implemented as template of size N. N represents the number of bytes. Internally a byte array is allocated of size N. Additionally a factor value (could also be a boolean value) contains the information if the number is positive (=1) or negative (=-1).

3.1.1 Negation of a number

A binary number can be simply negated by inverting the bytes and adding 1 at the end. See Two's complement.

inline void TBigIntegerBase::negate(Uint8* pui8Data, Int iSize)
{
  register Int i;
  for (i = 0; i < iSize; i++)
  {
    pui8Data[i] = (Uint8)(~pui8Data[i]);
  }

  Uint8 ui8Data = 1;
  TBigIntegerBase::add(&ui8Data, 1, pui8Data, iSize);
}

The method TBigIntegerBase::add() adds two byte arrays and returns the result by the second array parameter.

3.1.2 Addign numbers

Adding is very simple. We have to concern only the carry when adding bytes. The first loop adds all bytes of Array A and B and keeps the carry in Temp. The second loop just adds the carry to array B until it turns to zero.

INPUT: Array A and B
OUTPUT: Result B = A + B

Temp  = 0;
Count = MIN(A.Length, B.Length)

for i from 0 to Count-1 do
begin
  Temp = Temp + B[i] + A[i]
  B[i] = Temp & 0xFF
  Temp = Temp >> 8
end

i = Count
while i < B.Length and Temp != 0 do
begin
  Temp = Temp + B[i]
  B[i] = Temp & 0xFF
  Temp = Temp >> 8
  i    = i + 1
end

Note if the array A is larger than B it is truncated. The second loop is skipped totally.

3.1.3 Subtracting numbers

With negation and adding numbers we can simply implement the subtraction method.

  inline TBigInteger& subtract(const TBigInteger& rParam)
  {
    return this->add(rParam.getNegated());
  }

3.2 Multiplication

Lets have a look at the multiplication. We introduce two variants of multiplication. The first is a naive algorithm which helps to understand the method. The second is a speed optimized method.

3.2.1 Naive Multiplication Method

The naive method used a double for-loop. Therefore the time complexity is O(n^2).

INPUT: Array A and B
OUTPUT: Result C = A * B
Carry = 0

for i from 0 to B.Length do
begin
  Target = i

  for j from 0 to A.Length do
  begin
    Target    = Target + 1
    Temp      = (A[j] * B[i]) + Carry
    Temp      = Temp + C[Target]

    C[Target] = Temp & 0xFF
    Carry     = Temp >> 8
  end

  //Handles the carry
  while Carry != 0 do
  begin
    Temp      = C[Target] + Carry
    C[Target] = Temp & 0xFF
    Carry     = Temp >> 8
    Target    = Target + 1
  end
end

3.2.2 Comba Multiplication Method

A more efficient method to multiply two numbers is the Comba Multiplication Algorithm 25 (page 29). The method is about 30% faster than the naive method due to its improved carry handling.

  Int iCount1 =  iSize1 + iSize2;
  Uint uiVal = 0;

  for (Int i = 0; i < iCount1; i++)
  {
    Int iBO = (i < iSize2-1) ? i : iSize2-1;
    Int iAO = i - iBO;
    Int iCount2 = (iSize1 - iAO < iBO + 1) ? iSize1 - iAO : iBO + 1;

    for (Int j = 0; j < iCount2; j++)
    {
      uiVal += (pui8Data1[iAO + j] * pui8Data2[iBO - j]);
    }

    pui8Result[i] = (Uint8)(uiVal & 0xFF);
    uiVal >>= 8;
  }

Note that the length of the array C must be the sum of array length A and B.

3.2 Division and Modulus

The division and modulus are more time consuming than the addition or subtraction. A simple but very exhaustive method is to subtract the divisor until the rest is smaller than the divisor. The number of subtraction is the result.

More efficient is the local substraction (see below).

inline /*static*/ void TBigIntegerBase::divide(const Uint8* pui8DivPos,
                                               const Uint8* pui8DivNeg,
                                               Uint8* pui8BaseAndModulo,
                                               Uint8* pui8Result,
                                               Int iNSize)
{
  //clear result
  ::memset(pui8Result, 0x00, iNSize);

  register Int iBN = TBigIntegerBase::getLastSignPos(pui8BaseAndModulo, iNSize);
  register Int iDN = TBigIntegerBase::getLastSignPos(pui8DivPos, iNSize);
  register Int iRN = iBN - iDN;
  register Int iCarry = 0;
  while(iDN <= iBN)
  {
    Uint8* pui8TempBase = pui8BaseAndModulo + iBN - iDN;

    register Uint uiCount = 0;
    register Int iCmpSize = iDN + 1 + iCarry;
    while(TBigIntegerBase::compareTo_positive(pui8DivPos, 
                                              iCmpSize, 
                                              pui8TempBase, 
                                              iCmpSize) <= 0)
    {
      TBigIntegerBase::add(pui8DivNeg, 
                           iNSize, 
                           pui8TempBase, 
                           iNSize - iBN + iDN);
      uiCount++;
    }
    pui8Result[iRN] = (Uint8)uiCount;
    iBN--;
    iRN--;

    if (iCarry == 0) { iCarry = 1; }
  }
}

3.3 Multiplication and Exponentiation with Modulus

Even more time consuming are exponentiations combined with modulus. Following method is not really optimal in speed but illustrates pretty well how exponentiation can be combined with the modulus:

INPUT: Base b, Exponent exp and Modulus m
OUTPUT: Result C = b ^ exp (mod m)
C = 1

while exp != 0 do
begin
  if (exp & 0x01) then C = b * C (mod m)

  b = b * b (mod m)

  exp = exp >> 1
end

Using the Montgomery Exponentiation Algorithm we can speed up the proceeding. A good description is given in Handbook of Applied Cryptography. The Montgomery Multiplication is explained by algorithm 14.36 and can be done as follows:

INPUT: Base b, Exponent exp and Modulus m
OUTPUT: Result C = b ^ exp (mod m)