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 | (x*Int) 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())
}
}
}
More Links
- https://pkg.go.dev/math/big
- https://blog.devgenius.io/big-int-in-go-handling-large-numbers-is-easy-157cb272dd4f
- https://livebook.manning.com/book/get-programming-with-go/chapter-8/
- https://medium.com/orbs-network/big-integers-in-go-14534d0e490d