Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Erlang module to test for primality of integer numbers
Erlang
branch: master

This branch is 1 commit ahead of febeling:master

Fetching latest commit…

Cannot retrieve the latest commit at this time

Failed to load latest commit information.
src
.gitignore
MIT-LICENSE
README.md

README.md

miller_rabin

An Erlang module implementing the Miller-Rabin test. This test is a probabilistic test for primality of numbers. It is the alogrithm used in Mathematica.

The module exports three functions that can be used to check for primality:

is_probable_prime(N)

and

is_probable_prime(N, K)

These functions use the original, undeterministic version of the algorithm. That means it can yield true for a number that is composite, but this is very rare. The first function tests against K = 20 random bases per default.

is_prime(N)

This function uses the deterministic variant of the algorithm. It is reliable for numbers N < 341,550,071,728,321. This version uses not random sets of bases, like the original version, which could yield false positives. Instead it uses sets which have been shown to not yield false positives for the intervals in which the function is defined.

Example Usage

This example prints all primes up to 1000.

-module(example).

-import(miller_rabin, [is_prime/1]).

-compile([export_all]).

primes_below_1000() ->
    L = lists:seq(1, 1000),
    lists:map(fun(X) ->
                      case is_prime(X) of
                          true  -> io:format("~w~n", [X]);
                          false -> false
                      end
              end,
              L),
    ok.

Links

License

MIT. See MIT-LICENSE file.

Something went wrong with that request. Please try again.