BTC#: Big Integers in C#

BitcoinInCSharpTitle

Series: BTC# – Learning to Program Bitcoin in C#

« Previous: Big Numbers Are Big

Next: Finite Fields in C# »

Programming Bitcoin means using some very big numbers. We talked about why in the previous post. In Python, which Programming Bitcoin uses for all its code, the way integers are implemented is hidden from the user. The sample code in the book starts off using small numbers to illustrate the ideas and then shifts seamlessly into using the huge numbers required by the cryptographic algorithms.

In Python you can say

>>> p = 19

and just as easily say

>>> p = 2**256 - 2**32 - 977

It all works as expected.

In C# if you try the equivalent

> var p = Math.Pow(2, 256) - Math.Pow(2, 32) - 977;

the result will be a floating point number and precision will be lost. The result doesn’t store all of the significant figures and so it’s inexact. You can see this if you compare the prime number we’ll be using for our cryptography, which is slightly lower than 2256, with 2256. Because the least significant figures have been thrown away, the two numbers are equal. This is no good for our purposes.

> Math.Pow(2, 256) - Math.Pow(2, 32) - 977
1.157920892373162E+77
> Math.Pow(2, 256) - Math.Pow(2, 32) - 977 == Math.Pow(2, 256)
true

If we convert the results of the Math.Pow operations to integer types they will truncate (and flip the sign bit if we’re using signed types):

> (long)Math.Pow(2, 256)
-9223372036854775808

To translate the examples into C# we need to know how to handle big integers. The standard integer type, Int32, is a 32-bit integer, with a maximum value of 2,147,483,647 (or 4,294,967,295 if you use unsigned integers). This is microscopic compared to the huge numbers we’ll be dealing with. Int64s don’t get us much closer.

BigBiggerBiggest.png

The answer is the BigInteger struct, in the System.Numerics namespace.

We can create BigInteger objects in various ways. For small numbers they can be assigned from an int or a long:

public static BigInteger B = new BigInteger(7);

For bigger numbers, such as the cryptographic parameters we’ll be using, we can create a BigInteger from an array of bytes or parse a string.

We can specify a string of hexadecimal characters to be parsed. One thing to be aware of is that the highest order bit will be parsed as the sign, so lead with “00”.

public static BigInteger P { get; } = BigInteger.Parse("00FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", NumberStyles.AllowHexSpecifier);

We’re peeking ahead a bit here. In Programming Bitcoin we don’t start seeing these huge numbers until the chapter on Elliptic Curve Cryptography but I’ve mentioned this here because I’ll use the BigInteger type everywhere right from the start so I don’t have to change everything later.

« Previous: Big Numbers Are Big

Next: Finite Fields in C# »

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s