10 stable releases
new 1.5.2 | Jan 2, 2025 |
---|---|
1.4.1 | Dec 28, 2024 |
1.3.1 | Nov 12, 2024 |
1.3.0 |
|
1.2.0 | Jul 1, 2023 |
#96 in Math
713 downloads per month
Used in 4 crates
(3 directly)
1.5MB
17K
SLoC
Machine prime is a simple, efficient primality test for 64-bit integers, targeting research applications and casual use. Enabling the "wide" feature allows primality testing for 128-bit integers.
Two functions are provided with a C-style api to enable calling in other languages. Both can be called in const contexts.
- is_prime
- is_prime_wc (worst case)
is_prime is optimised for the average case and is intended as a general primality test. is_prime_wc is optimised for the worst case and is intended to be used in functions that the number is already suspected to be prime.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. is_prime will always correctly evaluate any 64/128-bit integer, however is_prime_wc failure points may change.See source code or documentation for a list of these failure points.
Usage
Machine-prime has 5 features, 3 of which are exclusive, and 2 of which can be combined with others
- Lucas - Uses a lucas-v test and adds trial division
- Table - Uses a hashtable
- SSMR - branches for faster primality for n < 2^47
- Wide - implements primality for 2^64;2^128
- Internal - Exposes internal algorithms and data, in Rust api (not C-api)
Machine-prime implements feature precedence going Lucas -> Table -> SSMR. In other words if the Table is implemented in one dependency it will override another Machine-prime dependency using "Lucas" feature. Likewise SSMR will override both "Table" and "Lucas". By default, Machine-prime implements the "Table" feature. Overriding this will implement a slower variant of the "Lucas" algorithm. It is strongly recommended that you use one of the features, as this algorithm is very slow in the average case.
Implementing "Wide" adds the is_prime_128 and is_prime_wc_128 functions, which branches to whichever algorithm the other features define for values below 2^64, and uses a BPSW test for n > 2^64. Implementing the "internal" feature exposes the internal arithmetic and data used. You cannot call these functions outside of Rust.
Bindings
To use as a dynamic library, make sure you are running rustc nightly; git clone
this repository and run make
to compile the default algorithm, make lucas
for the "Lucas" mode, make table
for the Table mode and make ssmr
for
the SSMR mode. To extend to 128-bit add "wide" to the feature word, e.g make tablewide
. Calling 128-bit FFI may result
in errors.
make install
will install the created library to /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.
Alternately, if on Windows, use the provided batch file.
See the "binding" folder in the repository for various language bindings. Several languages including the following are supported. 128-bit may not work on all architectures.
- Ada
- C/C++
- Fortran
- Haskell
- Julia
- Python
Applications
Due to Machine-primes speed, quite a few applications can be found for it, including in research projects.
is_prime
- Searching for primes, particularly in intervals that would require large computations for sieves, or primes out of sequence.
- Searching for "rare" forms of primes, used to construct Carmichael numbers, Monier-Rabin semiprimes and other special composites.
is_prime_wc is much more useful as it is faster against numbers that are already very likely to be prime
- Factorisation; determining that the factors returned are actually primes, and when to halt the factorisation
- Legendre symbol
- Verifying Erastothenes sieves, and other primality tests; checking that prime_test(n) == is_prime_wc(n)
- Verifying small primes used in prime certification, like the Pratt certificate
- Searching for Fermat pseudoprimes; verifying that certain numbers that satisfy a^(n-1) mod n =1 are infact composite
Notes
See Performance for some benchmarks and comparison to other efficient primality tests.
Approximate size of binary dynamic library varies with your compiler however the following are reasonable estimates after stripping:
- SSMR-Wide - 540kb
- Default/SSMR-533kb
- Lucas-10kb
- Tiny-7kb
Building for embedded systems has not been tested, however there is no known cause for failure.
This software is in public domain, and can be constructed in a reproducible manner with the f-analysis library, and Feitsma/Galway's base-2 pseudoprime table. It is available on crates.io