README
¶
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
- Arbitrarily large integer support (
big.Int)
AKS
- Deterministic primality test
- Slow on larger integers
intsupport only
TODOs
- Fix false positives with AKS method
- Add unit tests
- Improve speed of the AKS method
- Specifically step 5
- Make the AKS method work on arbitrarily sized integers
- use
big.Ints overints
- use
Documentation
¶
Overview ¶
Package aks provides an implementation of the deterministic AKS Primality Test, as well as the Miller-Rabin probabilistic primality test. The library also provides prime number generators such as the Sieve of Eratosthenes as well as more modern algorithms.
Ref: https://en.wikipedia.org/wiki/AKS_primality_test Ref: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func AKS ¶
AKS is an implementation of the AKS deterministic primality test. Step 5 takes up the majority of the time and as such results in a slow test.
func MaskOfEratosthenes ¶ added in v1.1.0
MaskOfEratosthenes uses a bitmask produced by a modified sieve of Eratosthenes in order to compare the desired integer against the corresponding index in the mask, determining if it is prime or not
func MillerRabin ¶
MillerRabin is an implementation of the Miller-Rabin primality test, it is a probabilistic method - and as such using 25 repetitions/rounds is recommended as it ensures a higher probability of accuracy of the result. The test is 100% accurate up to 2^64 and some values higher - forcing the use of base 2 when randomly generating bases for the
func SieveOfEratosthenes ¶
SieveOfEratosthenes is an implementation of the ancient sieve of Eratosthenes to generate a list of primes up to the provided integer.
Types ¶
This section is empty.
Source Files