Golang : How to determine a prime number?

In mathematics and computer security, it is very important to determine if a given number is a prime number or not. For this tutorial, we will learn how to find out if a number is prime or not.

For the uninitiated, a number is prime if the only divisors it has are 1 and itself.

First, we generate our own function to determine a prime number. However, it has limitation(inefficient) in determining and handling a large prime number.

Golang's standard library has good prime number generator and prime number validation functions. We will use the standard functions for the code that follows to validate large prime number (big.Int type)

Here we go!

---

 package main

 import (
 "crypto/rand"
 "fmt"
 "math/big"
 )

 // for small prime
 func isPrime(num int) bool {
 for i := 2; i < num; i++ {
 if num%i == 0 {
 return false
 }
 }
 return true
 }

 func main() {

 fmt.Println("Is 1 a prime number? : ", isPrime(1))
 fmt.Println("Is 2 a prime number? : ", isPrime(2))
 fmt.Println("Is 3 a prime number? : ", isPrime(3))
 fmt.Println("Is 4 a prime number? : ", isPrime(4))
 fmt.Println("Is 5 a prime number? : ", isPrime(5))
 fmt.Println("Is 6 a prime number? : ", isPrime(6))
 fmt.Println("Is 7 a prime number? : ", isPrime(7))
 fmt.Println("Is 8 a prime number? : ", isPrime(8))
 fmt.Println("Is 9 a prime number? : ", isPrime(9))
 fmt.Println("Is 10 a prime number? : ", isPrime(10))

 // for security purpose, it is good to have big prime number
 // Golang's crypto/rand package has builtin prime number generator
 // see https://www.socketloop.com/references/golang-crypto-rand-prime-function-example

 var bigPrime *big.Int
 var bits int
 var err error

 bits = 999

 bigPrime, err = rand.Prime(rand.Reader, bits)

 if err != nil {
 fmt.Println(err)
 }

 fmt.Printf("Generated big prime number : %d\n", bigPrime)
 fmt.Println("------------------------------------------------")
 fmt.Printf("Is %d a prime number? : %v\n", bigPrime, bigPrime.ProbablyPrime(50))

 // just to test how good is ProbablyPrime() function
 // we create a false prime

 falsePrime := new(big.Int)
 // to avoid constant 554378014529860247248431469761 overflows uint64
 // we use SetString instead
 // see https://www.socketloop.com/tutorials/golang-convert-string-or-integer-to-big-int-type

 falsePrime.SetString("554378014529860247248431469761", 10) // base 10
 fmt.Printf("Is %d a prime number? : %v\n", falsePrime, falsePrime.ProbablyPrime(50))

 // now DO NOT use ProbablyPrime for 1, it will give wrong results
 falsePrime.SetString("1", 10) // base 10
 fmt.Printf("Is %d a prime number? : %v\n", falsePrime, falsePrime.ProbablyPrime(50))
 fmt.Printf("Is %d a prime number? : %v\n", falsePrime, falsePrime.ProbablyPrime(2))

 // but ok for 3
 falsePrime.SetString("3", 10) // base 10
 fmt.Printf("Is %d a prime number? : %v\n", falsePrime, falsePrime.ProbablyPrime(50))
 fmt.Printf("Is %d a prime number? : %v\n", falsePrime, falsePrime.ProbablyPrime(2))

 // and the rest...
 falsePrime.SetString("4", 10) // base 10
 fmt.Printf("Is %d a prime number? : %v\n", falsePrime, falsePrime.ProbablyPrime(50))
 fmt.Printf("Is %d a prime number? : %v\n", falsePrime, falsePrime.ProbablyPrime(2))
 }

---

output:

Is 1 a prime number? : true

Is 2 a prime number? : true

Is 3 a prime number? : true

Is 4 a prime number? : false

Is 5 a prime number? : true

Is 6 a prime number? : false

Is 7 a prime number? : true

Is 8 a prime number? : false

Is 9 a prime number? : false

Is 10 a prime number? : false

Generated big prime number : 4330246321548259.....1372849

---

Is 4330246321548259.....1372849 a prime number? : true

Is 554378014529860247248431469761 a prime number? : false

Is 1 a prime number? : false

Is 1 a prime number? : false

Is 3 a prime number? : true

Is 3 a prime number? : true

Is 4 a prime number? : false

Is 4 a prime number? : false

---

NOTES:

Can you write your own functions that are more efficient and secure than those functions found in the standard package? Yes, of course you can. After all, the ProbablyPrime() function has a disclaimer that - "it is not suitable for judging primes that an adversary may have crafted to fool this test".

Happy priming!

References:

https://golang.org/pkg/math/big/#Int.ProbablyPrime

https://www.socketloop.com/tutorials/golang-convert-string-or-integer-to-big-int-type

https://golang.org/src/crypto/elliptic/elliptic.go?s=871:1509#L55