kitfre/OCaml-Primes

is_prime implementation

Opened this issue · 4 comments

danaj commented

primes.mli indicates the implementation is 1000 (!) iterations of Miller-Rabin.

README.md indicates the test is AKS.

primes.ml seems to implement an exponential time binomial test, which is a very inefficient way to implement naive trial division. Perhaps this idea came from the numberphile video, which incorrectly describes this opening lemma as AKS (it is not), or from the Rosettacode page which is incorrectly named.

Very true, I've make the AKS test much more efficient using the gen library and updated the .mli to reflect this

danaj commented

It's still not the AKS test though.

Noted - making it true to the AKS test will be added to the list of things to update, I'll update the readme to reflect this addition to the todo list

I added the Miller-Rabin probablistic test for the mean time with PR #3 .