C# BigInteger Class

• Download source files - 26 Kb
• Download demo - 11 Kb

Contents

• Introduction
• Features
• Implementation Details
• Addition of Big Integers
• Subtraction of Big Integers
• Multiplication of Big Integers
• Division of Big Integers
• Primality Testing using Fermat's Little Theorem
• Sample Code
• Performance Evaluation
• Basic Arithmetic Operators
• Modular Exponentiation
• Jacobi Symbol Computation
• Speed of Primality Testing
• Limitations<
• Future Work
• Conclusion
• Change Log
• References

Introduction

The implementation of asymmetrical cryptographic schemes often requires the use of numbers that are many times larger than the integer data types that are supported natively by the compiler. In this article, we give an introduction to the implementation of arithmetic operations involving large integers. We do not attempt to give a full coverage of this topic since it is both complex and lengthy. For a more detailed treatment, the reader is referred to the listed references.

The source code that accompanies this article implements the BigInteger class supporting large integer arithmetic operations. Overloaded operators includes +, -, *, /, %, >>, <<, ==, !=, >, <, >=, <=, &, |, ^, ++, -- and ~. Other additional features such as modular exponential, modular inverse, pseudoprime generation and probabilistic primality testing are also supported.

Features

• Arithmetic operations involving large signed integers in 2's complement representation.
• Prime number tests using Fermat's Little Theorem, Rabin Miller's method and Solovay Strassen's method.
• Modular exponential with Barrett reduction.
• Modular inverse.
• Random Pseudoprime generation.
• Random Coprime generation.
• Greatest common divisor.

Implementation Details

The most common way of representing numbers is by using the positional notation system. Numbers are written using digits to represent multiples of powers of the specified base. The base that we are most familiar with and use everyday, is base 10. When we write the number 12345 in base 10, it actually means

12345₁₀= 1x10⁴ + 2x10³ + 3x10² + 4x10¹ + 5x10⁰

Similarly, if the same number is specified in base 16, then

12345₁₆= 1x16⁴ + 2x16³ + 3x16² + 4x16¹ + 5x16⁰

Hence, it is important to know the base that the number is specified in, since the same representation could represent different values when interpreted in different bases. In general, a positive number can be written as a polynomial of order k, where k is non-negative and a_k != 0.

n = a_kb^k + a_k-1b^k-1 + ... + a₁b¹ + a₀

b represents the base with 0 <= a <= b-1.

For base 10 representation, b = 10 and the digits allowed at each position is 0 <= a <= 9.

Addition of Big Integers

The addition of two numbers can be represented as the addition of two polynomials as shown below.

Let
n = a_kb^k + a_k-1b^k-1 + ... + a₁b¹ + a₀
m = c_kb^k + c_k-1b^k-1 + ... + c₁b¹ + c₀

Then
n + m = (a_k + c_k)b^k + (a_k-1 + c_k-1)b^k-1 + ... + (a₁ + c₁)b¹ + (a₀ + c₀)

However, it is often easier to visualize the addition of two large numbers as the digit-by-digit addition at each position. When we add the digits at a particular position, the largest resulting value is 2b - 2.

Proof

Since the maximum value of each digit is b - 1, we have

(b - 1) + (b - 1) = 2b - 2.

Since 2b - 2 < 2b, the maximum value that we have to carry over to the next higher position is 1. For example, if we add 9 and 9 in base 10, we get 18, where 8 remains in the current position and the 1 gets carried out to the next higher position. When adding the two digits in the next position, we must remember to add the carry as well.

In our BigInteger implementation, we store the number as an array of consecutive bytes. This is equivalent to the representation of the number in base 256 with each digit having values 0 to FF. A numerical example that shows the addition of two numbers in this base is given below.

      1  1
     FE A6 FF
  +     FF FF
  -----------
     FF A6 FE
  -----------

In this example, FF + FF = 1FE. This exceeds the maximum value of each digit in base 256. Hence, we retain FE in the current position and carry 1 to the next higher position. This code segment that shows how this is done is given below.

// code segment that performs byte-by-byte addition

int carry = 0;
for(int i = 0; i < len; i++)
{
        // bi1 and bi2 are the two large numbers to add.

        // data is the byte array holding the large number.


        int sum = bi1.data[i] + bi2.data[i] + carry;
        carry  = sum >> 8;
        result.data[i] = (byte)(sum & 0xFF);
}

Subtraction of Big Integers

The subtraction of two numbers is very similar to addition and can be easily implemented as byte-by-byte subtraction. However, when subtracting two digits, we often encounter the situation where the first digit is smaller than the second. In this case, we have to borrow 1 from the digit in the next position. This is actually done by subtracting 1 from the digit in the next higher position and adding the value of the base to the current digit. For example,

     2 AF
  -    FF
    -----
     1 B0
    -----

In this case, since AF < FF, we subtract 1 from the next higher digit 2 and compute 1AF - FF = B0. The following code segment shows how byte-by-byte subtraction is performed.

// code segment that performs byte-by-byte subtraction


int carryIn = 0;

for(int i = 0; i < len; i++)
{
    int diff, totalSub;

    // calculate the total value to be subtracted

    // from the current

    // digit.

    totalSub = bi2.data[i] + carryIn;

    // if total value to be subtracted is larger than the

    // currentdigit.


    if(bi1.data[i] < totalSub)
    {
        // we add the value of the base to the current

        // digit and remember to subtract 1 from the

        // next higher digit.


        diff = (bi1.data[i] + 0x100) - totalSub;
        carryIn = 1;
    }
    else
    {
        diff = bi1.data[i] - totalSub;
        carryIn = 0;
    }

    result.data[i] = (byte)diff;
}

Multiplication of Big Integers

The simplest way to implement multiplication is by using repeated addition. For simplicity of analysis, we assume that both the multiplier and the multiplicand has the same number of digits. To compute a * b, we set the result to 0, then we repeatedly add a to the result for b number of times. Although this approach is simple, its complexity is O(b) large integer additions and is equivalent to O(bn) byte-by-byte additions, where n is the number of digits in the large integer. For large b, O(bn) > O(n²). Hence, this approach does not scale to large multipliers.

The next easiest approach is by using techniques that we have learnt in elementary schools. More precisely, we multiply a by the each digit of b and sum the partial results. In the following example, we illustrate in base 256 the computation of 02AF x 01FF.

We first compute 02AF x FF

     AE
     02 AF
  x     FF
   -------
   2 AC 51
   -------

Note that when we multiply AF by FF, we get AE51. Since this exceeds base 256, we retain 51 in the current position and carry AF over to the next higher position. We then proceed to the next position and multiply 02 by FF, remembering to add the carry to get 02AC.

Next, we compute 02AF x 01

     02 AF
  x     01
   -------
     02 AF
   -------

Finally, we sum the partial results.

      1
     02 AC 51   (result from 02AF x FF)
  +  02 AF 00   (result from 02AF x 01 with 00 appended)
   ----------
     05 5B 51
   ----------

From this illustration, it is clear that the time complexity of multiplying two large integers is O(n²) byte multiplications where n is the number of digits in the number. The process of adding the partial results has a complexity of O(n) large integer additions, equivalent to O(n²) byte additions. Thus, the total complexity is O(n²) byte multiplications and O(n²) byte additions. We have implemented this approach in our BigInteger class as shown in the following code segment.

for(int i = 0; i < bi1.byteLength; i++)
{
    int mcarry = 0;
    for(int j = 0; j < bi2.byteLength; j++)
    {
        // compute the byte multiplication and the addition

        // of the partial results in a single step.


        int val = (bi1.data[i] * bi2.data[j]) +
            tempResult[i+j] + mcarry;

        tempResult[i+j] = (byte)(val & 0xFF);
        mcarry = (val >> 8);
    }

    tempResult[i+bi2.byteLength] = (byte)mcarry;
}

Division of Big Integers

Please refer to the listed references.

Primality Testing using Fermat's Little Theorem

The purpose of primality testing is to find out whether a given number is prime. A prime number is a number that is only divisible by 1 and itself. It is easy to determine the primality of a small number n by testing whether it is divisible by a prime number that is less than sqrt(n). For a large integer, this method is not practical. Instead, we can only determine whether the large integer is probably prime. This is known as probabilistic primality testing and numbers that passes the test are known as pseudoprimes. There are many probabilistic primality testing methods, but in this article, we will discuss only the method based on Fermat's Little Theorem.

From Fermat's Little Theorem, we know that

aⁿ mod n = a

for any integer a and any prime n. This means that if n is prime then aⁿ mod n = a for any integer a. The contrapositive of this statement says that if aⁿ mod n != a for some integer a then n is NOT prime.

Unfortunately, the converse of the theorem is not true. This means that if aⁿ mod n = a, we cannot be sure whether n is prime. However, we can make use of the contrapositive to determine if n is composite. In other words, if there exists an integer a such that aⁿ mod n != a, then n is not prime. By testing out sufficient numbers of a's, we can exclude numbers that are composite and retain numbers that are probably prime. The following source code illustrates this.

// confidence determines the number of times to test.


for(int round = 0; round < confidence; round++)
{
    // generate random a < n

    a.genRandomBits(testBits, rand);

    // calculate a^(n) mod n, where thisVal = n

    BigInteger expResult = a.modPow(thisVal, thisVal);

    // is NOT prime if a^(p) mod p != a

    if(expResult != a)
        return false;
}

return true;

There is a class of composite integer known as Carmichael number that cannot be differentiated from real primes using this test. Such integers satisfy aⁿ mod n = a for all positive integers a with gcd(a,n) = 1.

Sample Code

The generation of a 512-bits random pseudoprime number.

public static void Main(string[] args)
{
    Console.Write(
        "\nGenerating 512-bits random pseudoprime. . .");

    Random rand = new Random();
    BigInteger prime = BigInteger.genPseudoPrime(
        512, 5, rand);

    Console.WriteLine("\n" + prime);
}

Arithmetic operations involving BigInteger.

public static void Main(string[] args)
{
    // define two BigIntegers in base 10

    BigInteger bn1 = new BigInteger("12345678901234567890",
        10);
    BigInteger bn2 = new BigInteger("4321", 10);

    // Determine the quotient and remainder by dividing

    // the first number by the second.

    BigInteger bn3 = bn1 / bn2;
    BigInteger bn4 = bn1 % bn2;

    // Recalculate the number

    BigInteger bn5 = (bn3 * bn2) + bn4;

    Console.WriteLine("bn1 = " + bn1);
    Console.WriteLine("bn5 = " + bn5);
}

Asymmetrical encryption and decryption.

public static void Main(string[] args)
{
    // private and public key

    BigInteger bi_e = new BigInteger(
        "a932b948feed4fb2b692609bd22164fc9edb" +
        "59fae7880cc1eaff7b3c9626b7e5b241c27a" +
        "974833b2622ebe09beb451917663d4723248" +
        "8f23a117fc97720f1e7", 16);

    BigInteger bi_d = new BigInteger(
        "4adf2f7a89da93248509347d2ae506d683dd" +
        "3a16357e859a980c4f77a4e2f7a01fae289f" +
        "13a851df6e9db5adaa60bfd2b162bbbe31f7" +
        "c8f828261a6839311929d2cef4f864dde65e" +
        "556ce43c89bbbf9f1ac5511315847ce9cc8d" +
        "c92470a747b8792d6a83b0092d2e5ebaf852" +
        "c85cacf34278efa99160f2f8aa7ee7214de07b7", 16);

    BigInteger bi_n = new BigInteger(
        "e8e77781f36a7b3188d711c2190b560f205a" +
        "52391b3479cdb99fa010745cbeba5f2adc08" +
        "e1de6bf38398a0487c4a73610d94ec36f17f" +
        "3f46ad75e17bc1adfec99839589f45f95ccc" +
        "94cb2a5c500b477eb3323d8cfab0c8458c96" +
        "f0147a45d27e45a4d11d54d77684f65d48f1" +
        "5fafcc1ba208e71e921b9bd9017c16a5231af7f", 16);

    Console.WriteLine("e =\n" + bi_e.ToString(10));
    Console.WriteLine("\nd =\n" + bi_d.ToString(10));
    Console.WriteLine("\nn =\n" + bi_n.ToString(10) + "\n");

    // data

    BigInteger bi_data = new BigInteger(
        "12345678901234567890", 10);

    // encrypt and decrypt data

    BigInteger bi_encrypted = bi_data.modPow(bi_e, bi_n);
    BigInteger bi_decrypted = bi_encrypted.modPow(
        bi_d, bi_n);

    Console.WriteLine("bi_data = " + bi_data);
    Console.WriteLine("\nbi_encrypted =\n" + bi_encrypted);
    Console.WriteLine("\nbi_decrypted = " + bi_decrypted);
}

Performance Evaluation

The performance of basic arithmetic operators were evaluated and presented in this section. We observe significant performance improvements by moving from byte-level to 32-bit word-level operations. The use of Barrett reduction in modular exponentiation, and the use of a faster algorithm for the computation of the Jacobi symbol has contributed significantly to improved speed in RSA and probabilistic primality testing.

All evaluation code was compiled using csc BigInteger.cs /o and executed on a Pentium III 800Mhz laptop. For tests that involve the generation of random numbers, we use the built-in Random class and the same initial seed value of 1 for each test. Timing of the operations were done using the following code.

    int dwStart = System.Environment.TickCount;

    // Perform the test.


    Console.WriteLine(System.Environment.TickCount - dwStart);

Basic Arithmetic Operators

To test the performance of the addition operator, we generated two random BigIntegers of 1024-bits each and added them. This test was repeated 100000 times and the total time taken to complete the task was recorded. The subtraction and multiplication operators were tested in the similar manner. For the division operator, we generated two random BigIntegers, each having random length between 2 to 1024 bits. The larger of the two is then divided by the smaller value. This test was repeated 100000 times and the total time taken to complete the test was recorded. The results are shown in the following graph.

Modular Exponentiation

The speed of modular exponentiation was evaluated by generating three random BigIntegers with a = 512 bits, e = 512 bits and n = 1024 bits. The exponentiation is then computed as a^e mod n. The test was repeated with 100 different values of a, e, n, and the average time required for each exponentiation was calculated. The following graph shows the result.

Jacobi Symbol Computation

The speed of computing the Jacobi symbol was evaluated by generating two random BigIntegers of 1024 bits each. The value of the Jacobi symbol was computed for the two numbers, and the test was repeated 100 times using different pairs of numbers. The following graph shows the average time required for each computation.

Speed of Primality Testing

In our BigInteger class, we provided two functions that performs probabilitic primality testing of an integer. The first method bool isProbablePrime(int confidence), uses Rabin-Miller's strong pseudoprime test to determine whether the integer is probably prime. The algorithm is described as follows.

1. Test the number for divisibility by prime numbers below 2000.
2. Perform strong pseudoprime test on the number using n random bases. The number of random bases used in the test depends on the confidence parameter.
3. The function returns true if the number passes both step 1 and 2.

The second primality test method bool isProbablePrime() does not require the specification of a confidence parameter. A brief description of the test is given as follows.

1. Test the number for divisibility by prime numbers below 2000.
2. Test whether the number is a strong pseudoprime to base 2. If the number passes this test, proceed on to the next step.
3. Test whether the number is a strong Lucas pseudoprime.
4. The function returns true if the number passes steps 1, 2 and 3.

This test works based on the assumption that it is extremely rare for a composite number to be both a base 2 strong pseudoprime and a strong Lucas pseudoprime. For a detailed discussion of this method, the reader is referred to [6],[7] and [8].

We compare the performance of the two algorithms by measuring the time it takes for each algorithm to declare a known prime number as probably prime. The result for 512 and 1024-bit numbers is given in the following graph.

From the results, it is evident that for a 512-bit prime number, isProbablePrime() is marginally slower than isProbablePrime(10), which uses 10 rounds of Rabin-Miller test. However, for a 1024-bit prime number, isProbablePrime() is significantly faster than isProbablePrime(10).

Limitations

The following positive pseudoprime and several others passes our implementation of primality test but failed in JDK's isProbablePrime test. Any advice on why this is so would be greatly appreciated.

byte[] pseudoPrime1 = { (byte)0x00,
        (byte)0x85, (byte)0x84, (byte)0x64, (byte)0xFD,
        (byte)0x70, (byte)0x6A, (byte)0x9F, (byte)0xF0,
        (byte)0x94, (byte)0x0C, (byte)0x3E, (byte)0x2C,
        (byte)0x74, (byte)0x34, (byte)0x05, (byte)0xC9,
        (byte)0x55, (byte)0xB3, (byte)0x85, (byte)0x32,
        (byte)0x98, (byte)0x71, (byte)0xF9, (byte)0x41,
        (byte)0x21, (byte)0x5F, (byte)0x02, (byte)0x9E,
        (byte)0xEA, (byte)0x56, (byte)0x8D, (byte)0x8C,
        (byte)0x44, (byte)0xCC, (byte)0xEE, (byte)0xEE,
        (byte)0x3D, (byte)0x2C, (byte)0x9D, (byte)0x2C,
        (byte)0x12, (byte)0x41, (byte)0x1E, (byte)0xF1,
        (byte)0xC5, (byte)0x32, (byte)0xC3, (byte)0xAA,
        (byte)0x31, (byte)0x4A, (byte)0x52, (byte)0xD8,
        (byte)0xE8, (byte)0xAF, (byte)0x42, (byte)0xF4,
        (byte)0x72, (byte)0xA1, (byte)0x2A, (byte)0x0D,
        (byte)0x97, (byte)0xB1, (byte)0x31, (byte)0xB3,
};

byte[] pseudoPrime2 = { (byte)0x00,
        (byte)0x99, (byte)0x98, (byte)0xCA, (byte)0xB8,
        (byte)0x5E, (byte)0xD7, (byte)0xE5, (byte)0xDC,
        (byte)0x28, (byte)0x5C, (byte)0x6F, (byte)0x0E,
        (byte)0x15, (byte)0x09, (byte)0x59, (byte)0x6E,
        (byte)0x84, (byte)0xF3, (byte)0x81, (byte)0xCD,
        (byte)0xDE, (byte)0x42, (byte)0xDC, (byte)0x93,
        (byte)0xC2, (byte)0x7A, (byte)0x62, (byte)0xAC,
        (byte)0x6C, (byte)0xAF, (byte)0xDE, (byte)0x74,
        (byte)0xE3, (byte)0xCB, (byte)0x60, (byte)0x20,
        (byte)0x38, (byte)0x9C, (byte)0x21, (byte)0xC3,
        (byte)0xDC, (byte)0xC8, (byte)0xA2, (byte)0x4D,
        (byte)0xC6, (byte)0x2A, (byte)0x35, (byte)0x7F,
        (byte)0xF3, (byte)0xA9, (byte)0xE8, (byte)0x1D,
        (byte)0x7B, (byte)0x2C, (byte)0x78, (byte)0xFA,
        (byte)0xB8, (byte)0x02, (byte)0x55, (byte)0x80,
        (byte)0x9B, (byte)0xC2, (byte)0xA5, (byte)0xCB,
};

Future Work

• Faster implementation of arithmetic operations.
• More robust primality testing methods.
• Faster pseudoprime generation

Conclusion

In this article, we have provided a short introduction to the topic of large integer arithmetic. We have looked at how large integer addition, subtraction and multiplication can be implemented. We have also examined the problem of primality testing and introduced the concept of primality testing based on Fermat's Little Theorem. Our implementation of BigInteger class can be downloaded from this page and provides the overloading of most arithmetic operators. We have pointed out the limitations of our implementations of primality testing and we are working towards more robust primality testing methods and faster implementation of arithmetic operators.

Change Log

• September 23, 2002
  • Version 1.03
  • Fixed operator- to give correct data length.
  • Added Lucas sequence generation.
  • Added Strong Lucas Primality test.
  • Added integer square root method.
  • Added setBit/unsetBit methods.
  • New isProbablePrime() method which do not require the confidence parameter.
• August 29, 2002
  • Version 1.02
  • Fixed bug in the exponentiation of negative numbers.
  • Faster modular exponentiation using Barrett reduction.
  • Added getBytes() method.
  • Fixed bug in ToHexString method.
  • Added overloading of ^ operator.
  • Faster computation of Jacobi symbol.
• August 19, 2002
  • Version 1.01
  • Big integer is stored and manipulated as unsigned integers (4 bytes) instead of individual bytes. This gives significant performance improvement.
  • Updated Fermat's Little Theorem test to use a^(p-1) mod p = 1
  • Added isProbablePrime method.
  • Updated documentation.
• August 9, 2002
  • Version 1.0
  • Initial Release.

References

[1] D. E. Knuth, "Seminumerical Algorithms", The Art of Computer Programming Vol. 2, 3rd Edition, Addison-Wesley, 1998.

[2] K. H. Rosen, "Elementary Number Theory and Its Applications", 3rd Ed, Addison-Wesley, 1993.

[3] B. Schneier, "Applied Cryptography", 2nd Ed, John Wiley & Sons, 1996.

[4] A. Menezes, P. van Oorschot, and S. Vanstone, "Handbook of Applied Cryptography", CRC Press, 1996, www.cacr.math.uwaterloo.ca/hac

[5] A. Bosselaers, R. Govaerts, and J. Vandewalle, "Comparison of Three Modular Reduction Functions", Proc. CRYPTO'93, pp.175-186.

[6] R. Baillie and S. S. Wagstaff Jr, "Lucas Pseudoprimes", Mathematics of Computation, Vol. 35, No. 152, Oct 1980, pp. 1391-1417.

[7] H. C. Williams, "�douard Lucas and Primality Testing", Canadian Mathematical Society Series of Monographs and Advance Texts, vol. 22, John Wiley & Sons, New York, NY, 1998.

[8] P. Ribenboim, "The new book of prime number records", 3rd edition, Springer-Verlag, New York, NY, 1995.

[9] M. Joye and J.-J. Quisquater, "Efficient computation of full Lucas sequences", Electronics Letters, 32(6), 1996, pp 537-538.

You must Sign In to use this message board.

FAQ    Noise Tolerance Very HighHighMediumLowVery Low   Layout Expand Posts & RepliesThread ViewNo JavascriptNo JS + Preview   Per page 102550

Msgs 1 to 25 of 145 (Total in Forum: 145) (Refresh) FirstPrevNext

Great article! If possible a question real_coder 4:29 15 Apr '09   Hi, First, thank you very much for the useful article and code. If possible, I'd ask something: I'm creating my own implementation of RSA, I generate random numbers (p, q) with using BigInteger's class, my code look like that: BigInteger p = BigInteger.genPseudoPrime(64, 5, new System.Random()); BigInteger q = BigInteger.genPseudoPrime(64, 5, new System.Random()); BigInteger n = new BigInteger(p*q); BigInteger phi = new BigInteger((p-1)*(q-1)); BigInteger e = phi.genCoPrime((n.bitCount()-1), new System.Random()); BigInteger d = e.modInverse(phi); n and e represent the public key, but I have to peresent the public key as single string, is there way how to this conversions: n, e ---> public_key_as_string_variable public_key_as_string -> n and e BigInteger variables n, d ---> private_key_as_string_variable private_key_as_string_variable ---> n, d Thanks you very much in advanced for every help Life is Coding Sign In·View Thread·PermaLink My Fixes. snake-86 4:11 22 Dec '08   Great thanks!! I'm found and fix some bugs )) 1) BigInteger _bi1 = new BigInteger(new byte[] { 0x11, 0x22, 0x55, 0x00, 0x12, 0x34, 0x56, 0x78 }); byte[] _b = _bi1.getBytes(); BigInteger _bi2 = new BigInteger(_b); Console.WriteLine(_bi1 == _bi2);//print false It's a bug Fix. in getbytes() replace if((tempVal = (val >> 24 & 0xFF)) != 0) result[pos++] = (byte)tempVal; if((tempVal = (val >> 16 & 0xFF)) != 0) result[pos++] = (byte)tempVal; if((tempVal = (val >> 8 & 0xFF)) != 0) result[pos++] = (byte)tempVal; if((tempVal = (val & 0xFF)) != 0) result[pos++] = (byte)tempVal; to this if ((tempVal = (val >> 24 & 0xFF)) != 0) result[pos++] = (byte)tempVal; if ((tempVal = (val >> 16 & 0xFF)) != 0) result[pos++] = (byte)tempVal; else if (pos > 0) pos++; if ((tempVal = (val >> 8 & 0xFF)) != 0) result[pos++] = (byte)tempVal; else if (pos > 0) pos++; if ((tempVal = (val & 0xFF)) != 0) result[pos++] = (byte)tempVal; else if (pos > 0) pos++; 2) BigInteger _bi1 = new BigInteger(new uint[] { 2, 0 }); Console.WriteLine(_bi1 >> 1); //throw an arithmetic overflow (if compiller overflow check is true) Fix. in shiftRight() function replace this carry = ((ulong)buffer[i]) << invShift; to this carry = (((ulong)buffer[i]) << invShift) & 0xFFFFFFFF; 3) In public BigInteger(byte[] inData) constructor an overflow if it on BigInteger _bi1 = new BigInteger(new byte[] { 0xFF,0xFF,0xFF,0xFF}); //throw an arithmetic overflow (if compiller overflow check is true) Fix. replace in public BigInteger(byte[] inData) data[j] = (uint)((inData[i - 3] << 24) + (inData[i - 2] << 16) + (inData[i - 1] << 8) + inData[i]); to this data[j] = ((uint)(inData[i - 3]) << 24) + ((uint)(inData[i - 2]) << 16) + ((uint)(inData[i - 1] << 8)) + ((uint)(inData[i])); Uff. that's all. waiting for the Version 1.04 ... Sign In·View Thread·PermaLink 5.00/5 (2 votes) Re: My Fixes. jazper 11:43 30 Mar '09   Wow, just fabulous! Many many many thanks for these fixes i was looking for. I nearly went crazy! Regards, Jazper Sign In·View Thread·PermaLink Looking for BigInteger replacement for more System.Math functions diggitbuddy76 12:37 28 Nov '08   Thank you for creating the start of a good BigInteger library. Many of your methods are well suited for cryptography. However, I've been searching for good replacements for many of the basic math functions in System.Math. For instance, after constructing a BigInteger with a value, I would like to be able to raise it to the 100th power, a value that certainly wouldn't fit into an Int32 or Int64. This would include functions like Pow, Sin, Cos, Exp, Log, and so forth. If you have the opportunity, please consider adding some of the basic functions from System.Math, which would make it a much more robust and general purpose library. Thanks! - Mike Sign In·View Thread·PermaLink What am I doing wrong? cportela 17:23 16 Nov '08   I have tried to make a poor man's RSA class using BigInteger but I can get it to fail rather easily and I suspect I am doing something wrong but I can't figure out what it is I am missing. The code below basically creates a public key and a private key and enters a loops that: 1) Generates a random 32-byte block. 2) Encrypts it with a call to modPow of the public key. 3) Dencrypts it with a call to modPow of the private key. 4) Compares the original array to the decrypted array. The CompareArrays() method returns true most of the times but it returns false every now and then which tells me something is wrong with my approach. During a run of 10,000 iterations I got approximately 198 failures. Have yuou any clue as to why this happens? private static bool GenerateKeyPair(int bits, out BigInteger privateKey, out BigInteger publicKey, out BigInteger modulo) { bool rc = true; privateKey = null; publicKey = null; modulo = null; try { BigInteger p, q, phi; Random rand = new Random(unchecked((int)(DateTime.Now.Ticks))); p = BigInteger.genPseudoPrime(bits/2, 5, rand); q = BigInteger.genPseudoPrime(bits - (bits / 2), 5, rand); modulo = p * q; phi = (p - 1) * (q - 1); privateKey = BigInteger.genPseudoPrime(bits, 5, rand); publicKey = privateKey.modInverse(phi); // Perform a quick sanity check string clearText = "01234567890123456789012345678901234567890123456789"; BigInteger message = new BigInteger(UTF8Encoding.UTF8.GetBytes(clearText)); BigInteger cypherText = message.modPow(publicKey, modulo); message = cypherText.modPow(privateKey, modulo); rc = UTF8Encoding.UTF8.GetString(message.getBytes()).CompareTo(clearText) == 0; if (!rc) { Console.WriteLine("\nSanity check failed for:\n\nPrivate= {0}\nPublic = {1}\nModulo = {2}", privateKey.ToHexString(), publicKey.ToHexString(), modulo.ToHexString()); } } catch (Exception ex) { rc = false; Console.WriteLine(ex.Message); } return rc; } private const int MAX_ITERATIONS = 10000; private static bool CompareArrays(byte[] b1, byte[] b2) { if (b1.Length != b2.Length) return false; for (int i = 0; i < b1.Length; i++) { if (b1[i] != b2[i]) return false; } return true; } public static void Main(string[] args) { BigInteger privateKey, publicKey, modulo; BigInteger clearMessage, encryptedMessage, decryptedMessage; Random rand = new Random(unchecked((int) (DateTime.Now.Ticks))); byte[] data = new byte[32]; Console.WriteLine("Single key, multiple message blocks\n"); bool rc = GenerateKeyPair(1024, out privateKey, out publicKey, out modulo); if (rc) { for (int i = 0; i < MAX_ITERATIONS; i++) { rand.NextBytes(data); clearMessage = new BigInteger(data); encryptedMessage = clearMessage.modPow(publicKey, modulo); decryptedMessage = encryptedMessage.modPow(privateKey, modulo); byte[] bytes = decryptedMessage.getBytes(); if (!CompareArrays(data, bytes)) { Console.WriteLine("\n{0} - Encryption/decryption failed for:\n\nPrivate= {1}\nPublic = {2}\nModulo = {3}\n", i, privateKey.ToHexString(), publicKey.ToHexString(), modulo.ToHexString()); } else Console.Write("."); } } } Sign In·View Thread·PermaLink Re: What am I doing wrong? cportela 18:46 16 Nov '08   Just a quick clarification, I have read through all the messages related to getBytes() and I have implemented all the changes suggested by the author and by others. My problem is related to getBytes() as it occurs when the message's first byte is 0. Sign In·View Thread·PermaLink Great help for my project, made small change to ToString for Radix 94 Mark Oliver 12:08 14 Oct '08   My application encoding a string of 45 decimal digits in DataMatrix 2D barcodes for a system that supports a max of 25 characters needed to use a radix - 94 - of every non-blank printable 7 bit ASCII character to fit the available space.                           public string ToString(int radix)             {                   string result = "";                   try                   {                         if (radix < 2 || (radix > 36 ? radix != 94 : false))                               throw (new ArgumentException("Radix must be >= 2 and <= 36 || 94"));                         string charSet = (radix != 94 ? "ABCDEFGHIJKLMNOPQRSTUVWXYZ" :                                  "!\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~");                         BigInteger a = this;                         bool negative = false;                         if ((a.data[maxLength - 1] & 0x80000000) != 0)                         {                               negative = true;                               try                               {                                     a = -a;                               }                               catch (Exception) { }                         }                         BigInteger quotient = new BigInteger();                         BigInteger remainder = new BigInteger();                         BigInteger biRadix = new BigInteger(radix);                         if (a.dataLength == 1 && a.data[0] == 0)                               result = "0";                         else                         {                               while (a.dataLength > 1 || (a.dataLength == 1 && a.data[0] != 0))                               {                                     singleByteDivide(a, biRadix, quotient, remainder);                                     if (remainder.data[0] < 10 && radix <= 36)                                           result = remainder.data[0] + result;                                     else                                           result = charSet[(int)remainder.data[0] - (radix <= 36 ? 10 : 0)] + result;                                     a = quotient;                               }                               if (negative)                                     result = "-" + result;                         }                   }                   catch (Exception ex)                   {                         throw ex;                   }                   return result;             } Sign In·View Thread·PermaLink Exception netsu 2:22 5 Jul '08   Hello, I explored the limits and hit an exception in the multiplication: BigInteger result = new BigInteger(1); for (int counter = 600; counter > 0; counter--) { BigInteger c = new BigInteger(counter); result = result * c; Console.WriteLine("{0} {1}", counter, result.ToHexString()); } Am I using the class wrongly? Sign In·View Thread·PermaLink Re: Exception netsu 2:33 5 Jul '08   I found out changing the maxLength field in the BigInteger solves my problem. Would a List object instead of a int[] array solve this hardcoded limit? Sign In·View Thread·PermaLink Is that a valid comparison? swtrse 2:56 15 May '08   Since I have a very time intensive problem I wrote a litte Bigint class (only adding at the moment) and tried to Compare the time for 10000 operations. Each Test has 3 cycles. And for every cycle the duration is evaluated. Code for Testcycle MyBigInt val = new MyBigInt(initalValue); for(int i = 0; i < 10000; ++i) { val = val + val; } The time for this cycle is evaluated an Printet on the Sceen. The initalValues are 1, long.MaxValue, and ulong.MaxValue. So there are 3 durations for my class. I did the same with the BigInteger class. Well the result was pretty suprising thats why I am asking. (Times are in milliseconds) MyBigint (tricky) 1: 2328,0952 long.MaxValue: 2312,4704 ulong.MaxValue: 2359,9696 MyBigint (normal) 1: 2593,7168 long.MaxValue: 2562,4672 ulong.MaxValue: 2562,4672 BigInteger 1: 3471,8344 long.MaxValue: 3418,7088 ulong.MaxValue: 3540,5848 ------ Well My class is working internaly with 64Bit values so the difference should be greater at 64Bit Systems. The difference between tricky and normal is that in the tricky version I tried to get some sort of carry flag for the addition. but I'm not sure if this will work for -, *, /,... too. So better not rely on that speed but that was not the question ^^. Remember ^^: Is that a valid comparison for BigIntclasses? BTW my class has no restriction in Size like the BigInteger (for the thest I had to change the arraysize to 3128 to get no overflow exception) Sign In·View Thread·PermaLink Incorrect In .getBytes() and .ToString() ikang 2:08 27 Jan '08   Take A Look At The Code Below: BigInteger bn1 = new BigInteger("65537", 10); byte[] bn1Bytes = bn1.getBytes(); WriteLog("bn1", bn1.ToString(10)); // bn1= 65537 BigInteger bn2 = new BigInteger(bn1Bytes); byte[] bn2Bytes = bn2.getBytes(); WriteLog("bn2", bn2.ToString(10)); // bn2=65792 ::Strange!! Why not 65537 ?? Sign In·View Thread·PermaLink 3.83/5 (3 votes) Re: Incorrect In .getBytes() and .ToString() dudubravo 6:27 28 Mar '08   On behalf of the author, I want to extend you my sincere apologies. I think he was when he wrote that part of the code. In the method getBytes() When you find this: if((tempVal = (val >> 24 & 0xFF)) != 0) result[pos++] = (byte)tempVal; if((tempVal = (val >> 16 & 0xFF)) != 0) result[pos++] = (byte)tempVal; if((tempVal = (val >> 8 & 0xFF)) != 0) result[pos++] = (byte)tempVal; if((tempVal = (val & 0xFF)) != 0) result[pos++] = (byte)tempVal; Replace with this: if( ( tempVal = ( val >> 24 & 0xFF ) ) != 0 ) result[ pos++ ] = ( byte )tempVal; if( ( tempVal = ( val >> 16 & 0xFF ) ) != 0 ) result[ pos++ ] = ( byte )tempVal; else if( pos > 0 ) pos++; if( ( tempVal = ( val >> 8 & 0xFF ) ) != 0 ) result[ pos++ ] = ( byte )tempVal; else if( pos > 0 ) pos++; if( ( tempVal = ( val & 0xFF ) ) != 0 ) result[ pos++ ] = ( byte )tempVal; If you have any further questions, please refrain from asking them to me Sign In·View Thread·PermaLink 3.50/5 (2 votes) Still a bug with .getbytes in v1.03 JS3141765 4:40 31 Dec '07   in my test, by BigInteger value started with (hex) 0040006A etc.. when calling .getbytes, it removes the leading 00 and the 3rd byte which is also 00. then since the result is 1 byte shorter than expected, the last byte of the array is left 00. This is the patch I did to fix the problem.. bool flag = false; if ((tempVal = (val >> 24 & 0xFF)) != 0) { result[pos++] = (byte)tempVal; flag = true; } if ((tempVal = (val >> 16 & 0xFF)) != 0 || flag) { result[pos++] = (byte)tempVal; flag = true; } if ((tempVal = (val >> 8 & 0xFF)) != 0 || flag) { result[pos++] = (byte)tempVal; flag = true; } if ((tempVal = (val & 0xFF)) != 0 || flag) { result[pos++] = (byte)tempVal; flag = true; } This will keep it from skiping the 2nd thru 4th bytes if they are zero but the MSB has already been found.. Sign In·View Thread·PermaLink 2.00/5 (1 vote) How did you get around the 'value semantics' issue ? Michael B Pliam 7:50 13 Dec '07   Thank you for making this wonderful code available. I have been working for some time on a similar class, but mine operates on a byte level and is pretty much out of NRC algorithms. However, it has no size limit, uses FFT and Newton's reciprocal convergence algorithms for multiplication and division. Works great in C++, but porting to C# has been painful and I cannot get division to work properly. My attempts to use C# for numerical analysis has led me to use structs rather than classes because structs have what is widely referred to as 'semantic value'. I cannot demonstrate the problem of lack of 'semantic value', that is, when one uses a class assignment operator '=', usually both the assignor and assignee are pointing to a specific memory site such that any change to one results in identical changes to the other. In order to obviate that, C# programmers appear to take either of 2 routes: 1) use a struct instead of a class, or 2) implement ICloneable. Since your class appears to do neither, I am puzzled as to why the problem does not exist (it does not as far as I have tested it) in your code. Perhaps you would shed some light on this. Sign In·View Thread·PermaLink Multiplication Threading foubar 17:49 4 Dec '07   Hello there Chew. I have been working with your class for a while now and I have made a few additions (such as logarithm and faster roots, etc.), but I can not figure out how I could actually thread out the multiplication operation. It is the ONLY operation that takes a tremendous amount of time with numbers with digits from 100,000 to 10 million. If i can figure out a way to extend this multiplication operation to thread itself out I can utilize more than just one core per multiplication operation. Sign In·View Thread·PermaLink Re: Multiplication Threading Member 1528249 6:24 12 Feb '08   Maybe it's better to use faster multiplication algorithm like multiplication using FFT (or FHT)? Take a look at my library IntX: http://contest2005.gotdotnet.ru/Request/Tools/UtilitiesLib/Downloads_GetFile.aspx?id=169728[^] (there is also a description in Russian: http://contest2005.gotdotnet.ru/Request/Tools/UtilitiesLib/169728.aspx[^]) - it multiplies using FFT which takes O(N*log N) instead of classic O(N^2). Sign In·View Thread·PermaLink Nice but lacking infinite precision Jehu Galeahsa 7:08 13 Nov '07   Hello: I was looking at your code and I see how you implemented it. I am impressed with your prime methods. Unfortunately, your BigInteger class has a fixed maximum size, which doesn't help me. It also requires that every BigInteger use a huge amount of space "new uint[maxLength]" every time your instantiate a new one. I am modifying your code. I have already rewritten many of your operators for working with dynamically growing values. I don't use primes that much (that exceed Int32.MaxValue) and so I removed those methods. Finally, I added some features such as FlipBit, unary operator +, DivRem and Pow. Keep up the good work. Sign In·View Thread·PermaLink 1.00/5 (1 vote) Re: Nice but lacking infinite precision foubar 13:56 30 Dec '07   Could i get my hands on this? X.x foubar_420 at hotmail dot com Sign In·View Thread·PermaLink 5.00/5 (1 vote) Functions power/root are nedeed IhorK 6:04 7 Nov '07   It will be very nice to have also functions to compute roots of any power (cubic, 1/19 etc.) Thank you. Sign In·View Thread·PermaLink Re: Functions power/root are nedeed watto86 13:03 7 May '08   Actually, it is not a big problem to implement them yourself. Here's what I did: //power function public BigInteger Pow( int exp ) { return power( this, exp ); } private static BigInteger power( BigInteger number, int exponent ) { if ( exponent == 0 ) throw new ArgumentException( "Dude, number " + number.ToString() + " f***ed up" ); if ( exponent == 1 ) return number; if ( exponent % 2 == 0 ) return square( power( number, exponent / 2 ) ); else return number * square( power( number, ( exponent - 1 ) / 2 ) ); } private static BigInteger square( BigInteger num ) { return num * num; } //root function public BigInteger root( int order ) { uint numBits = (uint)this.bitCount(); if ( ( numBits & 0x1 ) != 0 ) // odd number of bits numBits = ( numBits >> 1 ) + 1; else numBits = ( numBits >> 1 ); uint bytePos = numBits >> 5; byte bitPos = (byte)( numBits & 0x1F ); uint mask; BigInteger result = new BigInteger(); if ( bitPos == 0 ) mask = 0x80000000; else { mask = (uint)1 << bitPos; bytePos++; } result.dataLength = (int)bytePos; for ( int i = (int)bytePos - 1; i >= 0; i-- ) { while ( mask != 0 ) { // guess result.data[i] ^= mask; // undo the guess if its square is larger than this if ( ( result.Pow( order ) ) > this ) result.data[i] ^= mask; mask >>= 1; } mask = 0x80000000; } return result; } P.S. I don't guarantee these are correct, i didn't test it extensively. Sign In·View Thread·PermaLink Re: Functions power/root are nedeed watto86 2:32 8 May '08   The root function is just a minor modification of original sqrt function, where instead of "result * result", you check "result.pow(order)". BTW, sorry for the offensive language in the body of the ArgumentException, I simply copied it straight from my source code without scrutinizing it . Sign In·View Thread·PermaLink Re: Functions power/root are nedeed dzCepheus 13:09 8 Oct '08   Any number ^ 0 = 1... So instead of throwing an exception, you should be returning the number 1. PS: This is what part of the alphabet would look like if the letters Q and R were removed. Sign In·View Thread·PermaLink Brilliant Article, thank you so much... Paul Sanders (AlpineSoft) 5:16 20 Oct '07   ... saved my bacon. Will post an RSA implementation based on it soon. Thanks again. Paul Sanders http://www.alpinesoft.co.uk PS if you are still out there, could you possibly add the getBytes () bugfix described further down this thread to your reference sources. I tripped over this too. Sign In·View Thread·PermaLink The Mary Poppins Of Integer Classes [modified] Bassam Abdul-Baki 9:22 17 Sep '07   Practically perfect in every way. However, what is the maximum number that BigInteger could be? I tried changing maxLength to (UINT -1) at the very top, but that was unacceptable. So I made it 10,000 instead. It would be nice if you could do away with this part. Additionally, you may wish to separate it into multiple classes. One just for the number itself and another for primality testing and all. Your test cases, which I deleted, should go in a separate file. Finally, it would be nice to see some UML diagrams of all this. This isn't as easy as you make it appear to be. 5+ Last modified: 1hr 4mins after originally posted -- "Patriotism is your conviction that this country is superior to all other countries because you were born in it." - George Bernard Shaw Web - Blog - RSS - Math - LinkedIn - BM Sign In·View Thread·PermaLink not work in vb.net if the number is negative icon1982 10:05 12 Sep '07   I writeing a vb.net class, now implementing the costructor and test it, but if insert negative number the conversion type (...ctype(int64 and &hffffffff),system.uint32)..) return 0 and the loop go to the max size of array the problem is the conversion or type of variabile uint32 use for array? Sign In·View Thread·PermaLink 5.00/5 (1 vote)

Last Visit: 19:04 5 Jul '09     Last Update: 19:04 5 Jul '09 123456 Next »