Machine prime is a simple efficient primality test for 64-bit integers, constructed in a reproducible manner with the f-analysis library, and Feitsma/Galway's base-2 pseudoprime table. (Note that while f-analysis does use this library, it is not a circular dependency as it is not actually used in the computations to produce the fermat bases or hashtable. It is primarily to strip primes from a set of integers before evaluation, and some heuristic pseudoprime generation)
Two functions are provided with a C-style api to enable calling in other languages.
isprime is optimised for the average case and is intended as a general primality test. isprime_wc is optimised for the worst case and is intended to be used in functions that the number is already suspected to be prime. For instance factorisation where trial division has already been performed. It performs absolutely minimal checks, and is permitted to have a handful of known failure points leaving it up to the user to decide if it is necessary to expend the cost to check for them.
This function api will never change. isprime will always correctly evaluate any 64-bit integer, however isprime_wc failure points may change.
Three modes are available for these functions, Default and Small and Tiny. Memory use decreases but the complexity increases with each successive mode.
The Default utilizes a large hashtable, and trial division by prime inverse multiplication
to_hashtable(Some(262144),Some(1276800789),Some(65535)).
Compute the EPF pseudoprimes to Feitsma's table and apply the hashtable method to reproduce the
hashtable used. See the "hashtable" example in f-analysis for an explicit implementation. Small forgoes the hashtable but still uses the trial division - isprime complexity: Worst-case 2.8 * Fermat test, Average case < 0.567 * Fermat test - is-primewc complexity: Worst case 2.5 * Fermat test, Average-case < 1.31 * Fermat test - isprimewc failures: Panics at 0, flags 1 as prime, 2 as composite, 1194649 and 12327121 infinitely loop - Uses a modified Lucas sequence test in addition to the initial fermat test
Tiny simply uses the Fermat bases implemented in Small, the only difference therefore between isprime and isprime_wc is the latter forgoes any additional checks to ensure correctness. It saves a small amount of memory over Small.
Note that all failures will panic in debug mode but are overridden by optimization, the dynamic library produced by the Makefile will not panic for any.
Due to some barriers to compiling no-std libraries, the version in crates.io and the repository are slightly different, although using the exact same algorithms. crates.io version is configured for stable compilers, while the repository is configured for nightly compiler, as the intention is to use it to build dynamic libraries.
To use from crates.io, simply include it in your cargo.toml file with the feature "small" or "tiny" if you want those versions. Default will be the fastest with the hashtable.
To use as a dynamic library, make sure you are running rustc nightly; git clone this repository and run make to compile the Default mode, make small for the Small mode and make tiny for the Tiny mode. This will create the library, and make install will install it to /usr/lib/libprime.so. (Make sure you are superuser). Installing the library is recommended but not strictly necessary. Link to it using -lprime if you are using gcc.
Many number-theoretic functions either require a primality test or use a primality test for greater efficiency. Examples include the Legendre symbol and factorization.While primality testing is rarely the bottleneck for these functions, it is a limiting factor in highly optimized computations. By providing an fast public domain implementation that can be called in many languages and architectures, the work towards constructing such a function is minimised.
This primality test is not intended to be the fastest in every interval, but rather faster in general and the average case. There are small tests that are faster for 32-bit, however this is such a miniscule interval that branching to account for them would result in a reduction in efficiency in general.
There are fast functions that can be used to optimise for memory better. However, they use floating point arithmetic. The intent of this library is to be extremely fast, but flexible enough to be used when only integer arithmetic is supported. Consequently, floating point arithmetic, inline assembly and SIMD are not utilised. Additionally this is why low memory variants are provided, as not everyone is able or willing to use over 500 kilobytes of memory.
Approximate size of binary dynamic library varies with your compiler however the following are reasonable estimates: Default-542.4kb, Small-18.1kb, Tiny-14kb
Building for Windows OS, and embedded systems has not been tested, however there is no known cause for failure.
The default mode has marginally lower theoretical worst-case complexity than Forisek & Jancina's FJ64_262K.cc similar hashtable implementation, however machine-prime is considerably faster (3x <) in actual implementation, due to 128-bit arithmetic, Hensel lifting inversion and prime-inverses.
This software is in public domain, and all the values can be deterministically recomputed using the open-source auditable f-analysis library.