h5law/primality

A Go library for checking whether an integer is prime or not, using either the AKS or Miller-Rabin algorithms.

primality

Primality is a Golang library for determining whether any given integer $i\in\mathbb{Z}^+,~i\ge1$. The library provides two implementations of algorithms for determining the primality of an arbitrarily sized integer, using the math/big library.

The two methods provided are the Miller-Rabin and AKS primality test the former being probabilistic and the latter deterministic, meaning that the Miller-Rabin primality test doesn't guarantee 100% accuracy in certain situations. Whereas the AKS primality test is always 100% accurate - but a lot slower on larger integers.

Features

Miller-Rabin:

• Highly accurate probabilistic primality test
  • 25 rounds and force usage of base 2 recommended for near 100% accuracy
• Arbitrarily large integer support (big.Int)
• $\mathcal{O}(r\cdot s)$ time complexity (assuming big.Int operations are $\mathcal{O}(1)$ where $r$ is the number of repetitions and $s$ the number of trailing zeros on $n$, the number being tested - otherwise it is related to the operations of big.Int integers and $n$ itself.
  • As a prime must be odd $s\le7$ meaning the time complexity in its worst case is $\mathcal{O}(175)=\mathcal{O}(1)$ with 25 repetitions.

AKS

• Deterministic primality test
  • Slow overall - but guarantees 100% a valid outcome
• int support only

TODOs

• Improve speed of the AKS method
  • Specifically step 5 but overall it is slow
• Make the AKS method work on arbitrarily sized integers
  • use big.Ints over ints
• Determine the true time and space complexities for both methods

primality's Issues

Bug: Determine the cause and fix the issue with false positives in the AKS method

Overview

The AKS method produces false positive outputs as can be seen by running the following code and confirming the resulting array of primes is indeed correct.

package main

import (
	"fmt"
	"math/big"

	"github.com/h5law/primality"
)

func main() {
	res := make([]int, 0, 1000)
	for i := 1; i <= 1000; i++ {
		aks := primality.AKS(i)
		mr := primality.MillerRabin(big.NewInt(int64(i)), 25, true)
		if aks != mr {
			fmt.Printf("%d: AKS(%v) - MillerRabin(%v)\n", i, aks, mr)
		} else if aks && mr {
			res = append(res, i)
		}
	}
	fmt.Println("Total found: ", len(res))
	fmt.Println(res)
}

Issue

Determine if this was introduced through code change or whether the implementation has been incorrect the entire time.