Go Big Int (or go home)

30 November 2022

5 min Read

Scott Lester

Tobias Keller on Unsplash

This blog exists largely because I was pleased with the title. But also because there aren’t many resources or examples of doing things with the big number library in Go.

What is it?

The math/big package implements three types, big.Int, big.Float, and big.Rat (for rational numbers) for “arbitrary-precision arithmetic (big numbers)”, as well as a bunch of useful functions for working with big numbers. See the documentation here.

If you’re doing anything with properly big numbers, like those found in cryptographic primitives, you can’t avoid using them. But they are somewhat idiosyncratic, and require a different way of doing even basic operations.

Declaring Variables

You can create a new big.Int from an int64, or from an int with a cast to int64:

newBigInt := big.newInt(int64(43))

Or you can convert from a string, with a base:

decimalBase := 10
var bigInt, okay = new(big.Int).SetString("182290218004993891798109999841472943166944811522599991787800743914298", decimalBase)

if !okay {
	log.Fatalln("Failed to create big.Int from string")
}

The same goes for the other big number types, with float having the extra complication of precision.

Arithmetic

When using the big numbers you can’t use the regular arithmetic operators; Instead you have to use the methods defined in the types. For example, for a big.Int:

Operation	Name	Syntax	Operation
+	Add	(z Int) Add(x, y Int) *Int	sets z to the sum x+y and returns z
-	Sub	(z Int) Sub(x, y Int) *Int	sets z to the difference x-y and returns z
*	Mul	(z Int) Mul(x, y Int) *Int	sets z to the product x*y and returns z
/, %	Quo (quotient), Rem (remainder)	(z Int) Quo(x, y Int) Int, (z Int) Rem(x, y Int) Int	Quo sets z to the quotient x/y for y != 0 and returns z. Rem sets z to the remainder x%y for y != 0 and returns z
**	Exp	(z Int) Exp(x, y, m Int) *Int	sets z = x**y mod \|m\| (i.e. the sign of m is ignored), and returns z
==	Cmp	(xInt) Cmp(y Int) (r int)	0 if x == y

(There’s also QuoRem, for quotient and remainder in a single method)

Note that many of the methods return the answer in the instance that called the method. As stated in the docs:

For instance, given three *Int values a, b and c, the invocation c.Add(a, b) computes the sum a + b and stores the result in c, overwriting whatever value was held in c before. math.big package documentation

This syntax allows for the easy chaining of multiple operations, but it can be hard to follow. And that can allow mistakes to creep in, if you accidentally overwrite a value that you want to reuse later on. For example:

var one = big.NewInt(1)
var two = big.NewInt(2)

one.Add(one, two)

Calling add on the instance one means it would equal 3.

Erring on the side of clarity, you could instead create a new big.Int each time you call a method and store the result, for example:

var one = big.NewInt(1)
var two = big.NewInt(2)

var sum = new(big.Int)
sum.Add(one, two)

In this case, one and two are still at their original values, and we have a new instance sum for the result.

Putting it to use for crypto (which is short for cryptography, of course)

Now we’ve covered some of the basics, let’s look at putting it into practice. We’re using the big.Int for some TLS testing, specifically testing certificates and their RSA public keys for a variety of security and cryptographic issues. The Go crypto/rsa library uses big.Int to store a crucial value, the public key modulus, N:

// A PublicKey represents the public part of an RSA key.
type PublicKey struct {
	N *big.Int // modulus
	E int      // public exponent
}

Doing anything serious with the modulus means making use of big.Int and many of its methods.

Testing for Square Numbers

Taking a square root is easy, as big.Int has it’s own square root method (sqrt). However, to test whether a big.Int is square requires a little bit of arithmetic:

// Check if it's a perfect square, i.e. it's square root is a whole number
// test sqrt(n) == n^2
func isSquare(n *big.Int) bool {
	// take the root
	var squareRt = new(big.Int)
	squareRt.Sqrt(n)

	// square the root
	var square = new(big.Int)
	square.Mul(squareRt, squareRt)

	// compare the two - a perfect square is back at n
	if square.Cmp(n) == 0 {
		return true
	} else {
		return false
	}
}

Greatest Common Divisor

The method definition for GCD looks quite complex: func (z *Int) GCD(x, y, a, b *Int) *Int. But as the documentation says:

GCD sets z to the greatest common divisor of a and b and returns z. If x or y are not nil, GCD sets their value such that z = ax + by.

So you can call it simply for two values a and b:

var factor = new(big.Int)
factor.GCD(nil, nil, a, b)

Testing Primality

Finally, say you want to test whether a big.Int is a prime number. big.Int (and big.Rat) have a method for testing whether they’re prime, amusingly called ProbablyPrime. The probably is explained in the documentation:

ProbablyPrime is 100% accurate for inputs less than 2⁶⁴. See Menezes et al., Handbook of Applied Cryptography, 1997, pp. 145-149, and FIPS 186-4 Appendix F for further discussion of the error probabilities.

For example, if we want to list all the primes between 3 and 65537:

package main

import (
	"fmt"
	"math/big"
)

const maxPrime = 65537

func main() {
    // skip 2, test all odd numbers
    for i := 3; i <= maxPrime; i += 2 {
        // create a new big int, with i cast to an int64
        num := big.NewInt(int64(i))
        
        // check if it's probably prime
        if num.ProbablyPrime(0) {
            fmt.Printf("Found New prime: %s.\n", num.String())
        }
    }
}