 # Using BigInteger in Visual Basic 2010

by Paul Kimmel

Encryption and keeping secrets depends on large prime numbers that are too big to crack by brute force. .NET framework 4.0 introduces the BigInteger that has no theoretical upper and lower bounds.

## Introduction

I was sitting on a plane from Montreal a few years back next to a math professor from McGill University and casually asked him what was new and hot in mathematics. He said: cryptography and encryption. Of course, secrets. In an information age, secrets and secret data are going to be pretty important. More recently I read that the European Union suspended Blackberry text messaging because Blackberry encrypts text messages and routes them through Canada, so the stories seem to suggest. Encrypted messages that can't be intercepted are a risky prospect in this day and age.

Public encryption depends on huge prime numbers. The basic idea is that data encrypted based on primes could theoretically be cracked by brute force, by testing all prime candidates. However, since the primes used for encryption are so big by the time all possibilities are tested for primality the data is no longer relevant, or so that's the basic theory. There is a lot more to prime numbers and encryption, but that represents the broad strokes as I understand them.

Up until now calculating huge prime numbers in .NET required a lot of work. There weren't even primitive data types that could represent very large numbers. .NET framework 4.0 introduced the BigInteger type. The example in this article explores calculating the square root of BigInteger numbers and calculating large prime numbers.

## Introducing the BigInteger

The retired Major League Baseball player Randy Johnson was referred to as the "Big Unit". This 6' 10 left handed pitcher occasionally threw a fast ball at more than 100 miles per hour. A 100 mile per hour pitch is approximately 147 feet per second; in other words from pitcher to batter a Randy Johnson fastball covered the 90 feet in two-thirds of second. When I was much younger and stronger I could hit an 85 miler as long as I knew it was coming and it came straight down the pipe. I doubt I could even see a 100 mile an hour pitch or get the bat around fast enough. Perhaps it is better I don't have that pressure.

BigInteger refers to a new data type in the .NET framework. Defined in `System.Numerics` BigInteger has methods and overloaded operators that make it easier to use like smaller integral native data types, but using it with the Math class and Math's static methods is not supported. For the most part you can use BigInteger like any other integer type.

BigInteger is stored such that the most significant bit of the last byte is the sign bit. If you initialize a BigInteger with an array of bytes then include an additional byte whose value is zero, for the sign bit.

The biggest difference between BigInteger and smaller integer types in .NET is that BigInteger is the only one that doesn't have `MinValue` and `MaxValue` properties. The absence of these properties means that BigInteger can grow arbitrarily large and consequently take up a huge amount of memory. The real limitation to BigInteger is the physical resources on your computer. BigInteger types are immutable, so if you increment a BigInteger number then what really happens is the creation of a new BigInteger object though this process is invisible to the developer. Too many small operations on very big BigInteger values or if a BigInteger grows too large then an `OutOfMemoryException` will be thrown.

Oddly enough there is no Square Root method for BigInteger types. So, the solution I picked to introduce BigInteger is a solution that calculates huge prime numbers using the Sieve of Eratosthenes and a couple of ways of calculating the square root of BigIntegers.

## Calculating Square Roots Up To Double.MaxValue

One method for calculating the square root is calculating . You can use the Math class and calculate the square root of a BigInteger up to `Double.MaxValue` with the following formula:

```  Math.Exp(BigInteger.Log(value) / 2)
```

If the result is greater than `Double.MaxValue` then the result is `Double.PositiveInfinity`, making this a reasonable approach for calculating the square root of smaller numbers. Think of this as a quick square root solution for some small-valued BigIntegers but not huge ones.

## Calculating the Square Root of Arbitrarily Large BigIntegers

If you need to whip out a square root calculator for really BigIntegers then you can use Newton's method which is substantially more complex. The example for calculating the square root of a BigInteger in Listing 1 is based on John Wein's post of Newton's method, posted on social.msdn.microsoft.com. I translated it to VB, so any mistake in translation is my fault.

```  Private Function Sqrt(ByVal number As BigInteger) As BigInteger
' problem with lower numbers to right bit shift
Dim bitLength As Integer = number.ToByteArray().Length * 8 + 1
Dim G As BigInteger = number >> bitLength / 2
Dim LastG As BigInteger = BigInteger.Zero
Dim one As BigInteger = New BigInteger(1)
While (True)
LastG = G
G = (number / G + G) >> 1
Dim i As Integer = G.CompareTo(LastG)
If i = 0 Then Return G
If i < 0 Then
If (LastG - G).CompareTo(one) = 0 Then
If (G * G).CompareTo(number) < 0 And
(LastG * LastG).CompareTo(number) > 0 Then Return G
End If
ElseIf (G - LastG).CompareTo(one) = 0 Then
If (LastG * LastG).CompareTo(number) < 0 And
((G * G).CompareTo(number) > 0) Then Return LastG
End If
End While
Return G
End Function
```

Listing 1: Calculating the square root of really large BigInteger values in VB2010.

Wein's solution didn't seem to work for very low prime candidates. The reason for this seems to be in the fragment number >> bitLength / 2. This fragment shifts the value of the variable number right by the bit length of number. Very small numbers are going to be shifted to be equal to zero and assigned to G. G is used as a divisor in G = (number / G + G) >> 1, which causes a division by zero error. You can follow this link http://social.msdn.microsoft.com/Forums/en-SG/csharplanguage/thread/c13d3fec-21d9-4f74-92de-a6132d5e9915 for John Wein's original post. For more information on Newton's method you can start with the Wikipedia post http://en.wikipedia.org/wiki/Newton-Raphson. (I think of Wikipedia as a pretty good starting point, but scholarship and accuracy is encouraged based altruism not guaranteed.)

Now we can combine all of these elements and employ the Sieve of Eratosthenes to calculate huge prime numbers based on the BigInteger type.

## Calculating Huge Prime Numbers with BigInteger

My implementation of the Sieve of Eratosthenes for calculating prime numbers is to start with a seed number, get the next number in the sequence, and check to see if earlier primes are divisors. Since all numbers are the product of primes then if any previous prime is a divisor then the number is not prime. A refinement to this approach is to test just the earlier primes that are less than the square root of the candidate number-see Listing 2.

```  #Const SIMPLE = True
Imports System.Collections.Generic
Imports System.Linq
Imports System.Text
Imports System.Numerics
Imports System.Timers

Module Module1

Private timer As Timer = New Timer()

Sub Main()

' Calculate huge primes
keepGoing = True
timer.Interval = 1000000
timer.Start()
Console.WriteLine("Calculating Primes")
BuildPrimes()

End Sub

Private keepGoing As Boolean = True
Sub timer_Elapsed(ByVal sender As Object, ByVal e As ElapsedEventArgs)
keepGoing = False
timer.Stop()
End Sub

Private primes As List(Of BigInteger) = New List(Of BigInteger)()
Private Sub BuildPrimes()
Dim number As BigInteger = 3
While (keepGoing)
If IsPrime(number) Then
Console.WriteLine("is prime: {0}", number)
End If
number += 1
End While
End Sub

Private Function IsPrime(ByVal number As BigInteger) As Boolean
Dim index As BigInteger = 0

For Each test As BigInteger In primes
Dim remainder As BigInteger = 0
BigInteger.DivRem(number, test, remainder)
If remainder = 0 Then Return False

#If Not SIMPLE Then
If test * test > number Then Return True
#Else
' Use shorter method for numbers up to Double.MaxValue
Dim result As Double = Math.Exp(BigInteger.Log(number) / 2)
If result <> Double.PositiveInfinity Then
If test >= New BigInteger(result) Then Return True
ElseIf test >= Sqrt(number) Then
Return True
End If
#End If
Next

Return True
End Function

' test known primes with this web site.
' adapted from John Wein's implementation of Newton's method
' posted on   social.msdn.microsoft.com
' http://primes.utm.edu/curios/includes/primetest.php
Private Function Sqrt(ByVal number As BigInteger) As BigInteger
' problem with lower numbers to right bit shift
Dim bitLength As Integer = number.ToByteArray().Length * 8 + 1
Dim G As BigInteger = number >> bitLength / 2
Dim LastG As BigInteger = BigInteger.Zero
Dim one As BigInteger = New BigInteger(1)
While (True)
LastG = G
G = (number / G + G) >> 1
Dim i As Integer = G.CompareTo(LastG)
If i = 0 Then Return G
If i < 0 Then
If (LastG - G).CompareTo(one) = 0 Then
If (G * G).CompareTo(number) < 0 And
(LastG * LastG).CompareTo(number) > 0 Then Return G
End If
ElseIf (G - LastG).CompareTo(one) = 0 Then
If (LastG * LastG).CompareTo(number) < 0 And
((G * G).CompareTo(number) > 0) Then Return LastG
End If
End While
Return G
End Function
End Module
```

Listing 2: Generating very, very large prime numbers.

The example includes a couple of approaches to testing for prime numbers. The reason I included a couple of methods is because it introduces you to a lot of the behaviors supported by BigInteger, including methods and overloaded operators. Let's walk through the code so you can see what BigInteger is doing.

The first statement defines a conditional compiler directive to permit switching between chunks of code used. The Imports statement, including `System.Numerics` which contains BigInteger, follows the compiler constant.

The Main function uses a timer and a collection of BigInteger values seeded with the first prime number, 2, to start things off. The timer is just an easy way to stop processing. (It might be interesting to see how far this thing might run by itself.) The `timer.Elapsed` handler turns off the timer. `BuildPrimes` really does all of the coordination work.

`BuildPrimes` is pretty straight forward. As long as the flag `keepGoing` is true the loop will run and generate primes until you run out of memory. If you moved the primes to a database then you could run the program until you ran out of disk space, but the solution would probably be a lot slower. `IsPrime` and `Sqrt` are the workhorses of the solution. If `IsPrime` returns true then the prime number is added to the collection.

`IsPrime` calls `DivRem` to obtain the remainder of the argument number divided by the test number. If number is evenly divisible by test--a known prime--then the number is not prime and `IsPrime` returns false. In the #If part of the conditional code if test squared is greater than the candidate number then all of the possible known primes that need to be tested have been; that is, if test squared is greater than number then all of the remaining prime numbers are too big to be divisors so number is prime. In the #Else part of the solution the [sample2.jpg] algorithm is used for numbers less than `Double.Max` and the local `Sqrt` method is used when [sample3.jpg] returns `Double.PositiveInfinity`. (Note that `IsPrime` demonstrates how to use `BigInteger.DivRem` and construct a BigInteger from a Double.)

`Sqrt` uses several BigInteger methods and overloaded operators. The first statement in Sqrt converts a BigInteger to a byte array and a bit array by multiplying by 8. The next statement shows the shift right operator for BigInteger which shifts all of the bits right by the number on the right hand side of the operator. The next two statements--`BigInteger.Zero` and New `BigInteger(1)`--demonstrate how to obtain a zero-valued BigInteger and explicitly call the BigInteger constructor. If you look at the rest of the code you will see a call to CompareTo, subtraction, multiplication, and comparison operators for BigInteger.

When you are ready to test the results of the solution you can try http://primes.utm.edu/curios/includes/primetest.php. Of course, if you have to depend on this solution for some really secret squirrel stuff then carefully debug the `Sqrt` function and check the results against a very reliable source of prime numbers. I wouldn't want to be responsible for a national security crisis.

## Summary

.NET framework 4.0 defines a new type, the BigInteger. The BigInteger can be used for the most part like any other integer number. The biggest difference is that BigInteger has no `MinValue` or `MaxValue` properties and theoretically can consume as much memory as is available on your computer. Really big numbers eventually are going to consume a lot of memory, which may cause performance problems. If you need BigInteger then use it, but if you can work with smaller integer types then use those instead.

Think of BigInteger memory usage in the way that you think of string memory. BigIntegers, like strings, are immutable and can contain a lot of data per instance. If you have huge BigIntegers or big strings you may run into memory problems. That of course doesn't stop you from using strings.