Skip to content

Files

Latest commit

94b3912 · May 22, 2024

History

History
40 lines (31 loc) · 1.55 KB

README.md

File metadata and controls

40 lines (31 loc) · 1.55 KB

primality

Primality is a Golang library for determining whether any given integer i Z + ,   i 1 . 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)
  • O ( r s ) time complexity (assuming big.Int operations are 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 7 meaning the time complexity in its worst case is O ( 175 ) = 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